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