| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 53565 |
2018-06-30T08:21:11 Z |
시제연(#2016) |
Salesman (IOI09_salesman) |
C++11 |
|
1000 ms |
99392 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 500005, sz = 524288;
const ll INF = ll(1e18);
struct Seg{
ll d[2 * sz];
void ini(){ fill(d + 1, d + 2 * sz, -INF); }
int upd(int x, ll v){
x += sz;
d[x] = max(d[x], v);
for(x >>= 1; x; x >>= 1) d[x] = max(d[2 * x], d[2 * x + 1]);
}
ll get(int s, int e){
ll r = -INF;
for(s += sz, e += sz; s <= e; s >>= 1, e >>= 1){
if( s & 1) r = max(r, d[s++]);
if(~e & 1) r = max(r, d[e--]);
}
return r;
}
} PDS, MUS;
int n, d, u, sx;
ll lm[N], rm[N];
vector<pii> v[N];
vector<int> s[N], p[N];
void upd(int x, ll v){
PDS.upd(x, v + d * x);
MUS.upd(x, v - u * x);
}
int main(){
scanf("%d%d%d%d", &n, &d, &u, &sx);
for(int x, y, z; n--; ){
scanf("%d%d%d", &x, &y, &z);
v[x].push_back({y, z});
}
s[N - 1].push_back(0);
p[N - 1].push_back(sx);
for(int i = 1; i < N; i++){
sort(v[i].begin(), v[i].end());
for(pii j : v[i]){
p[i].push_back(j.first);
s[i].push_back(j.second);
}
}
PDS.ini(); MUS.ini();
upd(sx, 0);
for(int t = 1; t < N; t++){
vector<int> &p = ::p[t], &s = ::s[t];
int k = s.size();
for(int j = 0; j < k; j++){
int l = (j ? p[j - 1] : 0) + 1, r = p[j];
lm[j] = PDS.get(l, r) - d * p[j] + s[j];
if(j){
lm[j] = max(lm[j],
MUS.get(l, r) + u * p[j - 1] - d * (p[j] - p[j - 1]) + lm[j - 1] + s[j]);
}
}
for(int j = k - 1; j >= 0; j--){
int l = p[j], r = (j < k - 1 ? p[j + 1] : sz) - 1;
rm[j] = MUS.get(l, r) + u * p[j] + s[j];
if(j < k - 1){
rm[j] = max(rm[j],
PDS.get(l, r) - d * p[j + 1] - u * (p[j + 1] - p[j]) + rm[j + 1] + s[j]);
}
}
for(int j = 0; j < k; j++) upd(p[j], max(lm[j], rm[j]));
}
printf("%lld\n", PDS.get(sx, sx) - d * sx);
}
Compilation message
salesman.cpp: In member function 'int Seg::upd(int, ll)':
salesman.cpp:17:5: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
salesman.cpp: In function 'int main()':
salesman.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &n, &d, &u, &sx);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &x, &y, &z);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
51960 KB |
Output is correct |
| 2 |
Correct |
52 ms |
52068 KB |
Output is correct |
| 3 |
Correct |
54 ms |
52136 KB |
Output is correct |
| 4 |
Correct |
50 ms |
52292 KB |
Output is correct |
| 5 |
Correct |
54 ms |
52676 KB |
Output is correct |
| 6 |
Correct |
84 ms |
54004 KB |
Output is correct |
| 7 |
Correct |
144 ms |
56852 KB |
Output is correct |
| 8 |
Correct |
249 ms |
61724 KB |
Output is correct |
| 9 |
Correct |
312 ms |
66248 KB |
Output is correct |
| 10 |
Correct |
625 ms |
80536 KB |
Output is correct |
| 11 |
Correct |
762 ms |
80536 KB |
Output is correct |
| 12 |
Correct |
758 ms |
89860 KB |
Output is correct |
| 13 |
Correct |
760 ms |
89896 KB |
Output is correct |
| 14 |
Execution timed out |
1016 ms |
99272 KB |
Time limit exceeded |
| 15 |
Correct |
827 ms |
99392 KB |
Output is correct |
| 16 |
Execution timed out |
1044 ms |
99392 KB |
Time limit exceeded |
| 17 |
Incorrect |
55 ms |
99392 KB |
Output isn't correct |
| 18 |
Incorrect |
60 ms |
99392 KB |
Output isn't correct |
| 19 |
Incorrect |
56 ms |
99392 KB |
Output isn't correct |
| 20 |
Incorrect |
56 ms |
99392 KB |
Output isn't correct |
| 21 |
Incorrect |
60 ms |
99392 KB |
Output isn't correct |
| 22 |
Incorrect |
56 ms |
99392 KB |
Output isn't correct |
| 23 |
Incorrect |
57 ms |
99392 KB |
Output isn't correct |
| 24 |
Incorrect |
72 ms |
99392 KB |
Output isn't correct |
| 25 |
Incorrect |
159 ms |
99392 KB |
Output isn't correct |
| 26 |
Incorrect |
240 ms |
99392 KB |
Output isn't correct |
| 27 |
Incorrect |
340 ms |
99392 KB |
Output isn't correct |
| 28 |
Incorrect |
496 ms |
99392 KB |
Output isn't correct |
| 29 |
Incorrect |
661 ms |
99392 KB |
Output isn't correct |
| 30 |
Incorrect |
599 ms |
99392 KB |
Output isn't correct |
