Submission #235478

#TimeUsernameProblemLanguageResultExecution timeMemory
235478mielloSalesman (IOI09_salesman)C++14
17 / 100
3099 ms8568 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> ii; typedef pair<int, ii> iii; const int MXN = 5e5 + 5; const int INF = 1e9 + 7; vector<iii> fair; int dp[MXN], n, u, d, s; int dist(int start, int stop) { int now, fi, sc; if(start == -1) { fi = s, sc = fair[stop].second.first; } else if(stop == -1) { fi = fair[start].second.first, sc = s; } else { fi = fair[start].second.first, sc = fair[stop].second.first; } if(fi < sc) { now = u * (sc - fi); } else { now = d * (fi - sc); } return now; } int main() { scanf("%d %d %d %d", &n, &u, &d, &s); for(int i = 0; i < n; i++) { int t, l, m; scanf("%d %d %d", &t, &l, &m); fair.emplace_back(t, ii(l, m)); } sort(fair.begin(), fair.end(), [](iii a, iii b) { return a.first < b.first; }); fill(dp + 1, dp + MXN, -INF); for(int i = 1, stop = 0; i <= n; i++, stop++) { int mx = -INF; for(int j = 0, start = -1; j < i; j++, start++) { mx = max(mx, dp[j] - dist(start, stop)); } dp[i] = mx + fair[stop].second.second; } int p = 0; for(int i = 1; i <= n; i++) { p = max(p, dp[i] - dist(i - 1, -1)); } printf("%d", p); }

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", &n, &u, &d, &s);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &t, &l, &m);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...