# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
344946 | 2021-01-06T19:44:44 Z | ogibogi2004 | Boxes with souvenirs (IOI15_boxes) | C++14 | 682 ms | 282688 KB |
#include "boxes.h" #include <bits/stdc++.h> using namespace std; #define ll long long ll ans=2e17; const ll MAXN=1e7+6; ll pref[MAXN]; ll suf[MAXN]; long long delivery(int N, int K, int L, int p[]) { vector<ll>xd; for(ll i=0;i<N;i++)xd.push_back(p[i]); ll l=0,r=N-1,k=K,n=N,of=L,s,sl=0,sr=0; for(ll i=0;i<N;i++) { if(i-k>=0)pref[i]=pref[i-k]; pref[i]+=xd[i]*2; } for(ll i=N-1;i>=0;i--) { if(i+k<=N-1)suf[i]=suf[i+k]; suf[i]+=(of-xd[i])*2; } for(ll i=n-1;i>min(k-1,n-1);i--) { if((n-i)%k==0||i-1<=min(k-1,n-1)) { sr+=(of-xd[i])*2; } } sr=suf[min(k-1,n-1)+1]; for(ll i=0;i<n+1;i++) { ll i2=min(i+k-1,n-1);s=0; if(i2>=i) { s+=of; } ans=min(ans,sl+sr+s); //cout<<i<<":"<<sl<<" "<<sr<<" "<<s<<endl; /*if(i%k==0) { sl+=xd[i]*2; } else { sl-=xd[i-1]*2; sl+=xd[i]*2; } if(i+k<n) { sr-=(of-xd[i+k])*2; if((n-(i+k))%k!=0&&i+k+1<n) { sr+=(of-xd[i+k+1])*2; } }*/ sl=pref[i]; sr=suf[min(n,i+k+1)]; } sl=0;sr=0; for(ll i=n-1;i>=0;i--) { if((n-i)%k==0||i==0) { sr+=(of-xd[i])*2; } } sr=suf[0]; //cout<<sl<<" "<<sr<<endl; ans=min(ans,sr); for(ll i=0;i<n;i++) { /*if(i%k==k-1||i==0)sl+=xd[i]*2; else sl+=(xd[i]-xd[i-1])*2; sr-=(of-xd[i])*2; if(i+1<n) { if((n-(i+1))%k!=0) { sr+=(of-xd[i+1])*2; } }*/ sl=pref[i]; sr=suf[i+1]; //cout<<i<<" "<<sl<<" "<<sr<<endl; ans=min(ans,sl+sr); } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 1 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 1 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 1 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 384 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 1 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 1 ms | 384 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 364 KB | Output is correct |
13 | Correct | 1 ms | 364 KB | Output is correct |
14 | Correct | 1 ms | 364 KB | Output is correct |
15 | Correct | 1 ms | 384 KB | Output is correct |
16 | Correct | 1 ms | 364 KB | Output is correct |
17 | Correct | 1 ms | 364 KB | Output is correct |
18 | Correct | 1 ms | 364 KB | Output is correct |
19 | Correct | 1 ms | 364 KB | Output is correct |
20 | Correct | 1 ms | 364 KB | Output is correct |
21 | Correct | 1 ms | 384 KB | Output is correct |
22 | Correct | 1 ms | 364 KB | Output is correct |
23 | Correct | 1 ms | 364 KB | Output is correct |
24 | Correct | 1 ms | 364 KB | Output is correct |
25 | Correct | 1 ms | 364 KB | Output is correct |
26 | Correct | 1 ms | 364 KB | Output is correct |
27 | Correct | 1 ms | 364 KB | Output is correct |
28 | Correct | 1 ms | 364 KB | Output is correct |
29 | Correct | 1 ms | 364 KB | Output is correct |
30 | Correct | 1 ms | 384 KB | Output is correct |
31 | Correct | 1 ms | 380 KB | Output is correct |
32 | Correct | 1 ms | 364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 1 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 1 ms | 384 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 364 KB | Output is correct |
13 | Correct | 1 ms | 364 KB | Output is correct |
14 | Correct | 1 ms | 364 KB | Output is correct |
15 | Correct | 1 ms | 384 KB | Output is correct |
16 | Correct | 1 ms | 364 KB | Output is correct |
17 | Correct | 1 ms | 364 KB | Output is correct |
18 | Correct | 1 ms | 364 KB | Output is correct |
19 | Correct | 1 ms | 364 KB | Output is correct |
20 | Correct | 1 ms | 364 KB | Output is correct |
21 | Correct | 1 ms | 384 KB | Output is correct |
22 | Correct | 1 ms | 364 KB | Output is correct |
23 | Correct | 1 ms | 364 KB | Output is correct |
24 | Correct | 1 ms | 364 KB | Output is correct |
25 | Correct | 1 ms | 364 KB | Output is correct |
26 | Correct | 1 ms | 364 KB | Output is correct |
27 | Correct | 1 ms | 364 KB | Output is correct |
28 | Correct | 1 ms | 364 KB | Output is correct |
29 | Correct | 1 ms | 364 KB | Output is correct |
30 | Correct | 1 ms | 384 KB | Output is correct |
31 | Correct | 1 ms | 380 KB | Output is correct |
32 | Correct | 1 ms | 364 KB | Output is correct |
33 | Correct | 73 ms | 37588 KB | Output is correct |
34 | Correct | 44 ms | 29780 KB | Output is correct |
35 | Correct | 39 ms | 30292 KB | Output is correct |
36 | Correct | 71 ms | 37588 KB | Output is correct |
37 | Correct | 71 ms | 37584 KB | Output is correct |
38 | Correct | 70 ms | 37716 KB | Output is correct |
39 | Correct | 63 ms | 36052 KB | Output is correct |
40 | Correct | 43 ms | 31444 KB | Output is correct |
41 | Correct | 70 ms | 37588 KB | Output is correct |
42 | Correct | 47 ms | 31848 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 1 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 1 ms | 384 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 364 KB | Output is correct |
13 | Correct | 1 ms | 364 KB | Output is correct |
14 | Correct | 1 ms | 364 KB | Output is correct |
15 | Correct | 1 ms | 384 KB | Output is correct |
16 | Correct | 1 ms | 364 KB | Output is correct |
17 | Correct | 1 ms | 364 KB | Output is correct |
18 | Correct | 1 ms | 364 KB | Output is correct |
19 | Correct | 1 ms | 364 KB | Output is correct |
20 | Correct | 1 ms | 364 KB | Output is correct |
21 | Correct | 1 ms | 384 KB | Output is correct |
22 | Correct | 1 ms | 364 KB | Output is correct |
23 | Correct | 1 ms | 364 KB | Output is correct |
24 | Correct | 1 ms | 364 KB | Output is correct |
25 | Correct | 1 ms | 364 KB | Output is correct |
26 | Correct | 1 ms | 364 KB | Output is correct |
27 | Correct | 1 ms | 364 KB | Output is correct |
28 | Correct | 1 ms | 364 KB | Output is correct |
29 | Correct | 1 ms | 364 KB | Output is correct |
30 | Correct | 1 ms | 384 KB | Output is correct |
31 | Correct | 1 ms | 380 KB | Output is correct |
32 | Correct | 1 ms | 364 KB | Output is correct |
33 | Correct | 73 ms | 37588 KB | Output is correct |
34 | Correct | 44 ms | 29780 KB | Output is correct |
35 | Correct | 39 ms | 30292 KB | Output is correct |
36 | Correct | 71 ms | 37588 KB | Output is correct |
37 | Correct | 71 ms | 37584 KB | Output is correct |
38 | Correct | 70 ms | 37716 KB | Output is correct |
39 | Correct | 63 ms | 36052 KB | Output is correct |
40 | Correct | 43 ms | 31444 KB | Output is correct |
41 | Correct | 70 ms | 37588 KB | Output is correct |
42 | Correct | 47 ms | 31848 KB | Output is correct |
43 | Correct | 679 ms | 282688 KB | Output is correct |
44 | Correct | 372 ms | 276040 KB | Output is correct |
45 | Correct | 397 ms | 276640 KB | Output is correct |
46 | Correct | 678 ms | 282440 KB | Output is correct |
47 | Correct | 681 ms | 282440 KB | Output is correct |
48 | Correct | 676 ms | 282140 KB | Output is correct |
49 | Correct | 623 ms | 280916 KB | Output is correct |
50 | Correct | 437 ms | 277448 KB | Output is correct |
51 | Correct | 682 ms | 282464 KB | Output is correct |
52 | Correct | 456 ms | 277984 KB | Output is correct |