| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 69510 | 2018-08-21T06:55:51 Z | top34051 | Salesman (IOI09_salesman) | C++17 | 493 ms | 66560 KB |
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 5e5 + 5;
const int maxv = 5e5 + 5;
const ll inf = 1e15;
struct node {
int t,x,val;
};
int n,st;
ll U,D;
node a[maxn];
ll fenL[maxv+5], fenR[maxv+5], res[maxv+5];
void update(int x) {
for(int i=x;i<=maxv;i+=(i&-i)) fenL[i] = max(fenL[i], res[x] + U*x);
for(int i=x;i>=1;i-=(i&-i)) fenR[i] = max(fenR[i], res[x] - D*x);
}
ll query(int x) {
ll ret = -inf;
for(int i=x;i>=1;i-=(i&-i)) ret = max(ret, fenL[i] - U*x);
for(int i=x;i<=maxv;i+=(i&-i)) ret = max(ret, fenR[i] + D*x);
return ret;
}
int main() {
scanf("%d%lld%lld%d",&n,&D,&U,&st);
for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].t,&a[i].x,&a[i].val);
sort(&a[1],&a[n+1],[&](node x, node y) {return x.t < y.t;});
for(int i=1;i<=maxv;i++) {
fenL[i] = fenR[i] = res[i] = -inf;
}
res[st] = 0;
update(st);
for(int i=1;i<=n;i++) {
int x = a[i].x, val = a[i].val;
res[x] = max(res[x], val + query(x));
update(x);
// printf("\tdp %d %d = %lld\n",a[i].t,a[i].x,res[x]);
}
printf("%lld",query(st));
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 15 ms | 12152 KB | Output is correct |
| 2 | Correct | 13 ms | 12272 KB | Output is correct |
| 3 | Correct | 16 ms | 12324 KB | Output is correct |
| 4 | Correct | 16 ms | 12440 KB | Output is correct |
| 5 | Correct | 17 ms | 12484 KB | Output is correct |
| 6 | Correct | 32 ms | 13200 KB | Output is correct |
| 7 | Correct | 62 ms | 14560 KB | Output is correct |
| 8 | Correct | 129 ms | 16968 KB | Output is correct |
| 9 | Correct | 131 ms | 19800 KB | Output is correct |
| 10 | Correct | 208 ms | 26384 KB | Output is correct |
| 11 | Correct | 287 ms | 31868 KB | Output is correct |
| 12 | Correct | 348 ms | 39136 KB | Output is correct |
| 13 | Correct | 355 ms | 45388 KB | Output is correct |
| 14 | Correct | 493 ms | 55544 KB | Output is correct |
| 15 | Correct | 440 ms | 63708 KB | Output is correct |
| 16 | Runtime error | 459 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 17 | Runtime error | 14 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 18 | Runtime error | 12 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 19 | Runtime error | 14 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 20 | Runtime error | 13 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 21 | Runtime error | 18 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 22 | Runtime error | 15 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 23 | Runtime error | 16 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 24 | Runtime error | 17 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 25 | Runtime error | 124 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 26 | Runtime error | 189 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 27 | Runtime error | 302 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 28 | Runtime error | 295 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 29 | Runtime error | 418 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 30 | Runtime error | 456 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |