#include <bits/stdc++.h>
using namespace std;
#define oo 1e15
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) ((xxxx>>(aaaa-1))&1)
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;
const ll base=361;
const ll mod=998244353;
const ld eps=1e-5;
const ll maxn=1e6;
ll n,s,k,res,pos,sum[19][1000009],pre[1000009],a[1000009],ans;
int g[19][1000009],r[1000009],l[1000009],v[1000009],p[1000009],i,j;
ll calc(int x,int y) {
ll kq=0;
if (getbit(y,20)==1) {
kq+=sum[18][x];
x=g[18][x];
kq+=sum[18][x];
x=g[18][x];
kq+=sum[18][x];
x=g[18][x];
kq+=sum[18][x];
x=g[18][x];
}
if (getbit(y,19)==1) {
kq+=sum[18][x];
x=g[18][x];
kq+=sum[18][x];
x=g[18][x];
}
for (ll ii=18;ii>=0;ii--) {
if (getbit(y,ii+1)==1) {
kq+=sum[ii][x];
x=g[ii][x];
}
}
return kq;
}
void Trace(ll x,ll y) {
if (y==s) {
cout<<s<<'\n';
return;
}
if (x==n+1) {
cout<<y<<'\n';
return;
}
Trace(r[p[x]]+1,y+1);
cout<<p[x]<<' ';
}
int main(){
IO;
cin>>n>>s>>k;
for (i=1;i<n;i++) {
cin>>a[i+1];
a[i+1]+=a[i];
}
for (i=1;i<=n;i++) {
cin>>v[i];
}
for (i=n;i>0;i--) {
ans=i;
for (j=ans-1;j>0;j/=2) {
while (ans-j>0&&a[ans-j]>=a[i]-k) {
ans-=j;
}
}
l[i]=ans;
p[l[i]]=max(p[l[i]],i);
}
for (i=1;i<=n;i++) {
ans=i;
for (j=n;j>0;j/=2) {
while (ans+j<=n&&a[ans+j]<=a[i]+k) {
ans+=j;
}
}
r[i]=ans;
}
for (i=1;i<=n;i++) {
p[i]=max(p[i-1],p[i]);
}
for (i=1;i<=n;i++) {
pre[i]=pre[i-1]+v[i];
}
for (i=1;i<=n;i++) {
g[0][i]=r[p[i]]+1;
}
g[0][n+1]=n+1;
sum[0][n+1]=0;
for (i=1;i<=n;i++) {
sum[0][i]=pre[g[0][i]-1]-pre[i-1];
}
for (i=1;i<=18;i++) {
for (j=1;j<=n+1;j++) {
g[i][j]=g[i-1][g[i-1][j]];
sum[i][j]=sum[i-1][j]+sum[i-1][g[i-1][j]];
}
}
//cout<<k<<'\n';
for (i=1;i<=n;i++) {
ans=calc(i,s)-sum[0][i]+pre[r[p[i]]]-pre[l[p[i]]-1];
if (ans>res) {
//cout<<ans<<' '<<res<<' '<<i<<' '<<p[i]<<'\n';
res=ans;
pos=i;
}
}
//cout<<res<<'\n';
Trace(pos,0);
return 0;
for (i=1;i<=n;i++) {
cout<<a[i]<<' ';
}
cout<<'\n';
for (i=1;i<=n;i++) {
cout<<p[i]<<' ';
}
cout<<'\n';
for (i=1;i<=n;i++) {
cout<<l[i]<<' ';
}
cout<<'\n';
for (i=1;i<=n;i++) {
cout<<r[i]<<' ';
}
cout<<'\n';
for (i=1;i<=n;i++) {
cout<<pre[i]<<' ';
}
cout<<'\n';
for (i=1;i<=n;i++) {
cout<<g[1][i]<<' ';
}
cout<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
6 ms |
2892 KB |
Output is correct |
3 |
Correct |
5 ms |
3148 KB |
Output is correct |
4 |
Correct |
3 ms |
1740 KB |
Output is correct |
5 |
Correct |
1 ms |
588 KB |
Output is correct |
6 |
Correct |
6 ms |
2708 KB |
Output is correct |
7 |
Correct |
8 ms |
2764 KB |
Output is correct |
8 |
Correct |
5 ms |
3148 KB |
Output is correct |
9 |
Correct |
4 ms |
2252 KB |
Output is correct |
10 |
Correct |
5 ms |
3020 KB |
Output is correct |
11 |
Correct |
6 ms |
3148 KB |
Output is correct |
12 |
Correct |
3 ms |
1612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
382 ms |
218692 KB |
Output is correct |
2 |
Correct |
269 ms |
139204 KB |
Output is correct |
3 |
Correct |
282 ms |
149160 KB |
Output is correct |
4 |
Correct |
275 ms |
162640 KB |
Output is correct |
5 |
Correct |
348 ms |
190680 KB |
Output is correct |
6 |
Correct |
453 ms |
254064 KB |
Output is correct |
7 |
Correct |
303 ms |
167956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
6 ms |
2892 KB |
Output is correct |
3 |
Correct |
5 ms |
3148 KB |
Output is correct |
4 |
Correct |
3 ms |
1740 KB |
Output is correct |
5 |
Correct |
1 ms |
588 KB |
Output is correct |
6 |
Correct |
6 ms |
2708 KB |
Output is correct |
7 |
Correct |
8 ms |
2764 KB |
Output is correct |
8 |
Correct |
5 ms |
3148 KB |
Output is correct |
9 |
Correct |
4 ms |
2252 KB |
Output is correct |
10 |
Correct |
5 ms |
3020 KB |
Output is correct |
11 |
Correct |
6 ms |
3148 KB |
Output is correct |
12 |
Correct |
3 ms |
1612 KB |
Output is correct |
13 |
Correct |
382 ms |
218692 KB |
Output is correct |
14 |
Correct |
269 ms |
139204 KB |
Output is correct |
15 |
Correct |
282 ms |
149160 KB |
Output is correct |
16 |
Correct |
275 ms |
162640 KB |
Output is correct |
17 |
Correct |
348 ms |
190680 KB |
Output is correct |
18 |
Correct |
453 ms |
254064 KB |
Output is correct |
19 |
Correct |
303 ms |
167956 KB |
Output is correct |
20 |
Correct |
302 ms |
138984 KB |
Output is correct |
21 |
Correct |
308 ms |
170216 KB |
Output is correct |
22 |
Correct |
425 ms |
202052 KB |
Output is correct |
23 |
Correct |
427 ms |
208216 KB |
Output is correct |
24 |
Correct |
428 ms |
188088 KB |
Output is correct |
25 |
Correct |
411 ms |
188124 KB |
Output is correct |
26 |
Correct |
297 ms |
140216 KB |
Output is correct |
27 |
Correct |
380 ms |
180048 KB |
Output is correct |
28 |
Correct |
396 ms |
178120 KB |
Output is correct |
29 |
Correct |
485 ms |
231216 KB |
Output is correct |
30 |
Correct |
404 ms |
189396 KB |
Output is correct |
31 |
Correct |
327 ms |
166024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
447 ms |
237140 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
6 ms |
2892 KB |
Output is correct |
3 |
Correct |
5 ms |
3148 KB |
Output is correct |
4 |
Correct |
3 ms |
1740 KB |
Output is correct |
5 |
Correct |
1 ms |
588 KB |
Output is correct |
6 |
Correct |
6 ms |
2708 KB |
Output is correct |
7 |
Correct |
8 ms |
2764 KB |
Output is correct |
8 |
Correct |
5 ms |
3148 KB |
Output is correct |
9 |
Correct |
4 ms |
2252 KB |
Output is correct |
10 |
Correct |
5 ms |
3020 KB |
Output is correct |
11 |
Correct |
6 ms |
3148 KB |
Output is correct |
12 |
Correct |
3 ms |
1612 KB |
Output is correct |
13 |
Correct |
6 ms |
3148 KB |
Output is correct |
14 |
Correct |
5 ms |
2636 KB |
Output is correct |
15 |
Correct |
5 ms |
2636 KB |
Output is correct |
16 |
Correct |
3 ms |
1996 KB |
Output is correct |
17 |
Correct |
5 ms |
2504 KB |
Output is correct |
18 |
Correct |
5 ms |
3020 KB |
Output is correct |
19 |
Correct |
5 ms |
2636 KB |
Output is correct |
20 |
Correct |
5 ms |
2324 KB |
Output is correct |
21 |
Correct |
7 ms |
3708 KB |
Output is correct |
22 |
Correct |
5 ms |
3148 KB |
Output is correct |
23 |
Correct |
8 ms |
3020 KB |
Output is correct |
24 |
Correct |
6 ms |
2764 KB |
Output is correct |
25 |
Correct |
7 ms |
3020 KB |
Output is correct |
26 |
Correct |
5 ms |
3020 KB |
Output is correct |
27 |
Correct |
4 ms |
2380 KB |
Output is correct |
28 |
Correct |
4 ms |
2508 KB |
Output is correct |
29 |
Correct |
5 ms |
2636 KB |
Output is correct |
30 |
Correct |
5 ms |
3020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
6 ms |
2892 KB |
Output is correct |
3 |
Correct |
5 ms |
3148 KB |
Output is correct |
4 |
Correct |
3 ms |
1740 KB |
Output is correct |
5 |
Correct |
1 ms |
588 KB |
Output is correct |
6 |
Correct |
6 ms |
2708 KB |
Output is correct |
7 |
Correct |
8 ms |
2764 KB |
Output is correct |
8 |
Correct |
5 ms |
3148 KB |
Output is correct |
9 |
Correct |
4 ms |
2252 KB |
Output is correct |
10 |
Correct |
5 ms |
3020 KB |
Output is correct |
11 |
Correct |
6 ms |
3148 KB |
Output is correct |
12 |
Correct |
3 ms |
1612 KB |
Output is correct |
13 |
Correct |
382 ms |
218692 KB |
Output is correct |
14 |
Correct |
269 ms |
139204 KB |
Output is correct |
15 |
Correct |
282 ms |
149160 KB |
Output is correct |
16 |
Correct |
275 ms |
162640 KB |
Output is correct |
17 |
Correct |
348 ms |
190680 KB |
Output is correct |
18 |
Correct |
453 ms |
254064 KB |
Output is correct |
19 |
Correct |
303 ms |
167956 KB |
Output is correct |
20 |
Correct |
302 ms |
138984 KB |
Output is correct |
21 |
Correct |
308 ms |
170216 KB |
Output is correct |
22 |
Correct |
425 ms |
202052 KB |
Output is correct |
23 |
Correct |
427 ms |
208216 KB |
Output is correct |
24 |
Correct |
428 ms |
188088 KB |
Output is correct |
25 |
Correct |
411 ms |
188124 KB |
Output is correct |
26 |
Correct |
297 ms |
140216 KB |
Output is correct |
27 |
Correct |
380 ms |
180048 KB |
Output is correct |
28 |
Correct |
396 ms |
178120 KB |
Output is correct |
29 |
Correct |
485 ms |
231216 KB |
Output is correct |
30 |
Correct |
404 ms |
189396 KB |
Output is correct |
31 |
Correct |
327 ms |
166024 KB |
Output is correct |
32 |
Correct |
479 ms |
222048 KB |
Output is correct |
33 |
Correct |
383 ms |
170264 KB |
Output is correct |
34 |
Correct |
478 ms |
233992 KB |
Output is correct |
35 |
Correct |
287 ms |
140936 KB |
Output is correct |
36 |
Correct |
285 ms |
150820 KB |
Output is correct |
37 |
Correct |
315 ms |
166424 KB |
Output is correct |
38 |
Correct |
478 ms |
252820 KB |
Output is correct |
39 |
Correct |
403 ms |
189896 KB |
Output is correct |
40 |
Correct |
466 ms |
254724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
6 ms |
2892 KB |
Output is correct |
3 |
Correct |
5 ms |
3148 KB |
Output is correct |
4 |
Correct |
3 ms |
1740 KB |
Output is correct |
5 |
Correct |
1 ms |
588 KB |
Output is correct |
6 |
Correct |
6 ms |
2708 KB |
Output is correct |
7 |
Correct |
8 ms |
2764 KB |
Output is correct |
8 |
Correct |
5 ms |
3148 KB |
Output is correct |
9 |
Correct |
4 ms |
2252 KB |
Output is correct |
10 |
Correct |
5 ms |
3020 KB |
Output is correct |
11 |
Correct |
6 ms |
3148 KB |
Output is correct |
12 |
Correct |
3 ms |
1612 KB |
Output is correct |
13 |
Correct |
382 ms |
218692 KB |
Output is correct |
14 |
Correct |
269 ms |
139204 KB |
Output is correct |
15 |
Correct |
282 ms |
149160 KB |
Output is correct |
16 |
Correct |
275 ms |
162640 KB |
Output is correct |
17 |
Correct |
348 ms |
190680 KB |
Output is correct |
18 |
Correct |
453 ms |
254064 KB |
Output is correct |
19 |
Correct |
303 ms |
167956 KB |
Output is correct |
20 |
Correct |
302 ms |
138984 KB |
Output is correct |
21 |
Correct |
308 ms |
170216 KB |
Output is correct |
22 |
Correct |
425 ms |
202052 KB |
Output is correct |
23 |
Correct |
427 ms |
208216 KB |
Output is correct |
24 |
Correct |
428 ms |
188088 KB |
Output is correct |
25 |
Correct |
411 ms |
188124 KB |
Output is correct |
26 |
Correct |
297 ms |
140216 KB |
Output is correct |
27 |
Correct |
380 ms |
180048 KB |
Output is correct |
28 |
Correct |
396 ms |
178120 KB |
Output is correct |
29 |
Correct |
485 ms |
231216 KB |
Output is correct |
30 |
Correct |
404 ms |
189396 KB |
Output is correct |
31 |
Correct |
327 ms |
166024 KB |
Output is correct |
32 |
Incorrect |
447 ms |
237140 KB |
Output isn't correct |
33 |
Halted |
0 ms |
0 KB |
- |