| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
本以为会超时#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
const int MAX_N = 10005;
struct Node{int first, second, pos, cost;} p[MAX_N], p2[MAX_N];
int n, s;
bool cmp(Node a, Node b){return a.first < b.first;}
void solve()
{
sort(p2, p2+n, cmp);
for (int i=n-1; i>=0; --i)
{
int j=0;
int max_cost = 0;
while (j < n && p[i].first - p2[j].first > s)
{
int dia1 = p[i].first - p2[j].first;//生产成本之差
int dia2 = (p[i].pos - p2[j].pos) * s;//储存费用
if (dia2 > 0 && (dia1 - dia2) > max_cost)
{
max_cost = dia1 - dia2;
}
++j;
}
p[i].cost = (p[i].first - max_cost) * p[i].second;
}
long long res = 0;
for (int i=0; i<n; ++i) res += p[i].cost;
printf("%lld\n", res);
return;
}
int main()
{
while (scanf("%d %d", &n, &s) != EOF)
{
for (int i=0; i<n; ++i)
{
scanf("%d %d", &p[i].first, &p[i].second);
p2[i].first = p[i].first;
p2[i].second = p[i].second;
p2[i].pos = p[i].pos = i;
}
solve();
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator