# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
279933 | 2020-08-22T12:07:02 Z | MKopchev | Two Antennas (JOI19_antennas) | C++14 | 3000 ms | 25976 KB |
#include<bits/stdc++.h> using namespace std; const int nmax=2e5+42,inf=1e9+42; int n,q; int inp[nmax]; int a[nmax],b[nmax]; vector< pair<int/*left*/,int/*id*/> > seen[nmax]; int outp[nmax]; vector<int> in[nmax],out[nmax]; int value[nmax],mx[nmax]; void solve() { for(int i=1;i<=n;i++) { value[i]=-inf; mx[i]=-inf; } for(int i=1;i<=n;i++) { for(auto k:in[i]) { value[k]=-inp[k]; } for(int j=max(i-b[i],1);j<=i-a[i];j++) mx[j]=max(mx[j],inp[i]+value[j]); for(auto k:seen[i]) { for(int j=k.first;j<=i;j++) { outp[k.second]=max(outp[k.second],mx[j]); } } for(auto k:out[i]) { value[k]=-inf; } } } int main() { memset(outp,-1,sizeof(outp)); scanf("%i",&n); for(int i=1;i<=n;i++) { scanf("%i%i%i",&inp[i],&a[i],&b[i]); if(i+a[i]<=n)in[i+a[i]].push_back(i); if(i+b[i]<=n)out[i+b[i]].push_back(i); } scanf("%i",&q); for(int i=1;i<=q;i++) { int l,r; scanf("%i%i",&l,&r); seen[r].push_back({l,i}); } solve(); for(int i=1;i<=n;i++)inp[i]=-inp[i]; solve(); for(int i=1;i<=q;i++) printf("%i\n",outp[i]); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 15232 KB | Output is correct |
2 | Correct | 13 ms | 15232 KB | Output is correct |
3 | Correct | 12 ms | 15208 KB | Output is correct |
4 | Correct | 11 ms | 15232 KB | Output is correct |
5 | Correct | 10 ms | 15232 KB | Output is correct |
6 | Correct | 10 ms | 15232 KB | Output is correct |
7 | Correct | 10 ms | 15232 KB | Output is correct |
8 | Correct | 10 ms | 15232 KB | Output is correct |
9 | Correct | 10 ms | 15232 KB | Output is correct |
10 | Correct | 11 ms | 15232 KB | Output is correct |
11 | Correct | 10 ms | 15232 KB | Output is correct |
12 | Correct | 10 ms | 15232 KB | Output is correct |
13 | Correct | 11 ms | 15232 KB | Output is correct |
14 | Correct | 10 ms | 15264 KB | Output is correct |
15 | Correct | 11 ms | 15232 KB | Output is correct |
16 | Correct | 11 ms | 15232 KB | Output is correct |
17 | Correct | 13 ms | 15232 KB | Output is correct |
18 | Correct | 10 ms | 15232 KB | Output is correct |
19 | Correct | 9 ms | 15232 KB | Output is correct |
20 | Correct | 13 ms | 15232 KB | Output is correct |
21 | Correct | 11 ms | 15232 KB | Output is correct |
22 | Correct | 10 ms | 15252 KB | Output is correct |
23 | Correct | 10 ms | 15232 KB | Output is correct |
24 | Correct | 10 ms | 15232 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 15232 KB | Output is correct |
2 | Correct | 13 ms | 15232 KB | Output is correct |
3 | Correct | 12 ms | 15208 KB | Output is correct |
4 | Correct | 11 ms | 15232 KB | Output is correct |
5 | Correct | 10 ms | 15232 KB | Output is correct |
6 | Correct | 10 ms | 15232 KB | Output is correct |
7 | Correct | 10 ms | 15232 KB | Output is correct |
8 | Correct | 10 ms | 15232 KB | Output is correct |
9 | Correct | 10 ms | 15232 KB | Output is correct |
10 | Correct | 11 ms | 15232 KB | Output is correct |
11 | Correct | 10 ms | 15232 KB | Output is correct |
12 | Correct | 10 ms | 15232 KB | Output is correct |
13 | Correct | 11 ms | 15232 KB | Output is correct |
14 | Correct | 10 ms | 15264 KB | Output is correct |
15 | Correct | 11 ms | 15232 KB | Output is correct |
16 | Correct | 11 ms | 15232 KB | Output is correct |
17 | Correct | 13 ms | 15232 KB | Output is correct |
18 | Correct | 10 ms | 15232 KB | Output is correct |
19 | Correct | 9 ms | 15232 KB | Output is correct |
20 | Correct | 13 ms | 15232 KB | Output is correct |
21 | Correct | 11 ms | 15232 KB | Output is correct |
22 | Correct | 10 ms | 15252 KB | Output is correct |
23 | Correct | 10 ms | 15232 KB | Output is correct |
24 | Correct | 10 ms | 15232 KB | Output is correct |
25 | Correct | 174 ms | 19388 KB | Output is correct |
26 | Correct | 36 ms | 15736 KB | Output is correct |
27 | Correct | 292 ms | 21228 KB | Output is correct |
28 | Correct | 344 ms | 21240 KB | Output is correct |
29 | Correct | 148 ms | 19424 KB | Output is correct |
30 | Correct | 224 ms | 19320 KB | Output is correct |
31 | Correct | 113 ms | 20344 KB | Output is correct |
32 | Correct | 350 ms | 21264 KB | Output is correct |
33 | Correct | 228 ms | 20804 KB | Output is correct |
34 | Correct | 171 ms | 18188 KB | Output is correct |
35 | Correct | 277 ms | 21272 KB | Output is correct |
36 | Correct | 336 ms | 21296 KB | Output is correct |
37 | Correct | 184 ms | 18188 KB | Output is correct |
38 | Correct | 332 ms | 20360 KB | Output is correct |
39 | Correct | 52 ms | 16024 KB | Output is correct |
40 | Correct | 315 ms | 20344 KB | Output is correct |
41 | Correct | 237 ms | 18936 KB | Output is correct |
42 | Correct | 349 ms | 20344 KB | Output is correct |
43 | Correct | 111 ms | 17016 KB | Output is correct |
44 | Correct | 316 ms | 20344 KB | Output is correct |
45 | Correct | 61 ms | 16120 KB | Output is correct |
46 | Correct | 319 ms | 20472 KB | Output is correct |
47 | Correct | 92 ms | 16596 KB | Output is correct |
48 | Correct | 318 ms | 20392 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3048 ms | 25976 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 15232 KB | Output is correct |
2 | Correct | 13 ms | 15232 KB | Output is correct |
3 | Correct | 12 ms | 15208 KB | Output is correct |
4 | Correct | 11 ms | 15232 KB | Output is correct |
5 | Correct | 10 ms | 15232 KB | Output is correct |
6 | Correct | 10 ms | 15232 KB | Output is correct |
7 | Correct | 10 ms | 15232 KB | Output is correct |
8 | Correct | 10 ms | 15232 KB | Output is correct |
9 | Correct | 10 ms | 15232 KB | Output is correct |
10 | Correct | 11 ms | 15232 KB | Output is correct |
11 | Correct | 10 ms | 15232 KB | Output is correct |
12 | Correct | 10 ms | 15232 KB | Output is correct |
13 | Correct | 11 ms | 15232 KB | Output is correct |
14 | Correct | 10 ms | 15264 KB | Output is correct |
15 | Correct | 11 ms | 15232 KB | Output is correct |
16 | Correct | 11 ms | 15232 KB | Output is correct |
17 | Correct | 13 ms | 15232 KB | Output is correct |
18 | Correct | 10 ms | 15232 KB | Output is correct |
19 | Correct | 9 ms | 15232 KB | Output is correct |
20 | Correct | 13 ms | 15232 KB | Output is correct |
21 | Correct | 11 ms | 15232 KB | Output is correct |
22 | Correct | 10 ms | 15252 KB | Output is correct |
23 | Correct | 10 ms | 15232 KB | Output is correct |
24 | Correct | 10 ms | 15232 KB | Output is correct |
25 | Correct | 174 ms | 19388 KB | Output is correct |
26 | Correct | 36 ms | 15736 KB | Output is correct |
27 | Correct | 292 ms | 21228 KB | Output is correct |
28 | Correct | 344 ms | 21240 KB | Output is correct |
29 | Correct | 148 ms | 19424 KB | Output is correct |
30 | Correct | 224 ms | 19320 KB | Output is correct |
31 | Correct | 113 ms | 20344 KB | Output is correct |
32 | Correct | 350 ms | 21264 KB | Output is correct |
33 | Correct | 228 ms | 20804 KB | Output is correct |
34 | Correct | 171 ms | 18188 KB | Output is correct |
35 | Correct | 277 ms | 21272 KB | Output is correct |
36 | Correct | 336 ms | 21296 KB | Output is correct |
37 | Correct | 184 ms | 18188 KB | Output is correct |
38 | Correct | 332 ms | 20360 KB | Output is correct |
39 | Correct | 52 ms | 16024 KB | Output is correct |
40 | Correct | 315 ms | 20344 KB | Output is correct |
41 | Correct | 237 ms | 18936 KB | Output is correct |
42 | Correct | 349 ms | 20344 KB | Output is correct |
43 | Correct | 111 ms | 17016 KB | Output is correct |
44 | Correct | 316 ms | 20344 KB | Output is correct |
45 | Correct | 61 ms | 16120 KB | Output is correct |
46 | Correct | 319 ms | 20472 KB | Output is correct |
47 | Correct | 92 ms | 16596 KB | Output is correct |
48 | Correct | 318 ms | 20392 KB | Output is correct |
49 | Execution timed out | 3048 ms | 25976 KB | Time limit exceeded |
50 | Halted | 0 ms | 0 KB | - |