#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;
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 |
5 ms |
2892 KB |
Output is correct |
3 |
Correct |
6 ms |
3276 KB |
Output is correct |
4 |
Correct |
3 ms |
1736 KB |
Output is correct |
5 |
Correct |
2 ms |
588 KB |
Output is correct |
6 |
Correct |
6 ms |
2764 KB |
Output is correct |
7 |
Correct |
5 ms |
2896 KB |
Output is correct |
8 |
Correct |
7 ms |
3332 KB |
Output is correct |
9 |
Correct |
5 ms |
2252 KB |
Output is correct |
10 |
Correct |
6 ms |
3152 KB |
Output is correct |
11 |
Correct |
6 ms |
3344 KB |
Output is correct |
12 |
Correct |
4 ms |
1740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
436 ms |
218672 KB |
Output is correct |
2 |
Correct |
322 ms |
139204 KB |
Output is correct |
3 |
Correct |
302 ms |
149392 KB |
Output is correct |
4 |
Correct |
323 ms |
162944 KB |
Output is correct |
5 |
Correct |
384 ms |
190868 KB |
Output is correct |
6 |
Correct |
474 ms |
262144 KB |
Output is correct |
7 |
Correct |
305 ms |
173632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
5 ms |
2892 KB |
Output is correct |
3 |
Correct |
6 ms |
3276 KB |
Output is correct |
4 |
Correct |
3 ms |
1736 KB |
Output is correct |
5 |
Correct |
2 ms |
588 KB |
Output is correct |
6 |
Correct |
6 ms |
2764 KB |
Output is correct |
7 |
Correct |
5 ms |
2896 KB |
Output is correct |
8 |
Correct |
7 ms |
3332 KB |
Output is correct |
9 |
Correct |
5 ms |
2252 KB |
Output is correct |
10 |
Correct |
6 ms |
3152 KB |
Output is correct |
11 |
Correct |
6 ms |
3344 KB |
Output is correct |
12 |
Correct |
4 ms |
1740 KB |
Output is correct |
13 |
Correct |
436 ms |
218672 KB |
Output is correct |
14 |
Correct |
322 ms |
139204 KB |
Output is correct |
15 |
Correct |
302 ms |
149392 KB |
Output is correct |
16 |
Correct |
323 ms |
162944 KB |
Output is correct |
17 |
Correct |
384 ms |
190868 KB |
Output is correct |
18 |
Correct |
474 ms |
262144 KB |
Output is correct |
19 |
Correct |
305 ms |
173632 KB |
Output is correct |
20 |
Correct |
314 ms |
146328 KB |
Output is correct |
21 |
Correct |
327 ms |
179320 KB |
Output is correct |
22 |
Correct |
396 ms |
212704 KB |
Output is correct |
23 |
Correct |
406 ms |
216804 KB |
Output is correct |
24 |
Correct |
391 ms |
198028 KB |
Output is correct |
25 |
Correct |
392 ms |
198212 KB |
Output is correct |
26 |
Correct |
290 ms |
147608 KB |
Output is correct |
27 |
Correct |
363 ms |
189556 KB |
Output is correct |
28 |
Correct |
369 ms |
187464 KB |
Output is correct |
29 |
Correct |
463 ms |
243780 KB |
Output is correct |
30 |
Correct |
372 ms |
199364 KB |
Output is correct |
31 |
Correct |
305 ms |
174916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
378 ms |
217152 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 |
5 ms |
2892 KB |
Output is correct |
3 |
Correct |
6 ms |
3276 KB |
Output is correct |
4 |
Correct |
3 ms |
1736 KB |
Output is correct |
5 |
Correct |
2 ms |
588 KB |
Output is correct |
6 |
Correct |
6 ms |
2764 KB |
Output is correct |
7 |
Correct |
5 ms |
2896 KB |
Output is correct |
8 |
Correct |
7 ms |
3332 KB |
Output is correct |
9 |
Correct |
5 ms |
2252 KB |
Output is correct |
10 |
Correct |
6 ms |
3152 KB |
Output is correct |
11 |
Correct |
6 ms |
3344 KB |
Output is correct |
12 |
Correct |
4 ms |
1740 KB |
Output is correct |
13 |
Correct |
6 ms |
3148 KB |
Output is correct |
14 |
Correct |
5 ms |
2636 KB |
Output is correct |
15 |
Correct |
4 ms |
2636 KB |
Output is correct |
16 |
Correct |
3 ms |
1996 KB |
Output is correct |
17 |
Correct |
6 ms |
2508 KB |
Output is correct |
18 |
Correct |
6 ms |
3020 KB |
Output is correct |
19 |
Correct |
4 ms |
2552 KB |
Output is correct |
20 |
Correct |
4 ms |
2252 KB |
Output is correct |
21 |
Correct |
7 ms |
3660 KB |
Output is correct |
22 |
Correct |
7 ms |
3256 KB |
Output is correct |
23 |
Correct |
5 ms |
3020 KB |
Output is correct |
24 |
Correct |
5 ms |
2824 KB |
Output is correct |
25 |
Correct |
5 ms |
3020 KB |
Output is correct |
26 |
Correct |
5 ms |
3008 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 |
5 ms |
2892 KB |
Output is correct |
3 |
Correct |
6 ms |
3276 KB |
Output is correct |
4 |
Correct |
3 ms |
1736 KB |
Output is correct |
5 |
Correct |
2 ms |
588 KB |
Output is correct |
6 |
Correct |
6 ms |
2764 KB |
Output is correct |
7 |
Correct |
5 ms |
2896 KB |
Output is correct |
8 |
Correct |
7 ms |
3332 KB |
Output is correct |
9 |
Correct |
5 ms |
2252 KB |
Output is correct |
10 |
Correct |
6 ms |
3152 KB |
Output is correct |
11 |
Correct |
6 ms |
3344 KB |
Output is correct |
12 |
Correct |
4 ms |
1740 KB |
Output is correct |
13 |
Correct |
436 ms |
218672 KB |
Output is correct |
14 |
Correct |
322 ms |
139204 KB |
Output is correct |
15 |
Correct |
302 ms |
149392 KB |
Output is correct |
16 |
Correct |
323 ms |
162944 KB |
Output is correct |
17 |
Correct |
384 ms |
190868 KB |
Output is correct |
18 |
Correct |
474 ms |
262144 KB |
Output is correct |
19 |
Correct |
305 ms |
173632 KB |
Output is correct |
20 |
Correct |
314 ms |
146328 KB |
Output is correct |
21 |
Correct |
327 ms |
179320 KB |
Output is correct |
22 |
Correct |
396 ms |
212704 KB |
Output is correct |
23 |
Correct |
406 ms |
216804 KB |
Output is correct |
24 |
Correct |
391 ms |
198028 KB |
Output is correct |
25 |
Correct |
392 ms |
198212 KB |
Output is correct |
26 |
Correct |
290 ms |
147608 KB |
Output is correct |
27 |
Correct |
363 ms |
189556 KB |
Output is correct |
28 |
Correct |
369 ms |
187464 KB |
Output is correct |
29 |
Correct |
463 ms |
243780 KB |
Output is correct |
30 |
Correct |
372 ms |
199364 KB |
Output is correct |
31 |
Correct |
305 ms |
174916 KB |
Output is correct |
32 |
Correct |
453 ms |
233940 KB |
Output is correct |
33 |
Correct |
405 ms |
179172 KB |
Output is correct |
34 |
Correct |
501 ms |
246304 KB |
Output is correct |
35 |
Correct |
295 ms |
148260 KB |
Output is correct |
36 |
Correct |
314 ms |
158852 KB |
Output is correct |
37 |
Correct |
343 ms |
175236 KB |
Output is correct |
38 |
Correct |
480 ms |
262144 KB |
Output is correct |
39 |
Correct |
360 ms |
199932 KB |
Output is correct |
40 |
Correct |
461 ms |
262144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
5 ms |
2892 KB |
Output is correct |
3 |
Correct |
6 ms |
3276 KB |
Output is correct |
4 |
Correct |
3 ms |
1736 KB |
Output is correct |
5 |
Correct |
2 ms |
588 KB |
Output is correct |
6 |
Correct |
6 ms |
2764 KB |
Output is correct |
7 |
Correct |
5 ms |
2896 KB |
Output is correct |
8 |
Correct |
7 ms |
3332 KB |
Output is correct |
9 |
Correct |
5 ms |
2252 KB |
Output is correct |
10 |
Correct |
6 ms |
3152 KB |
Output is correct |
11 |
Correct |
6 ms |
3344 KB |
Output is correct |
12 |
Correct |
4 ms |
1740 KB |
Output is correct |
13 |
Correct |
436 ms |
218672 KB |
Output is correct |
14 |
Correct |
322 ms |
139204 KB |
Output is correct |
15 |
Correct |
302 ms |
149392 KB |
Output is correct |
16 |
Correct |
323 ms |
162944 KB |
Output is correct |
17 |
Correct |
384 ms |
190868 KB |
Output is correct |
18 |
Correct |
474 ms |
262144 KB |
Output is correct |
19 |
Correct |
305 ms |
173632 KB |
Output is correct |
20 |
Correct |
314 ms |
146328 KB |
Output is correct |
21 |
Correct |
327 ms |
179320 KB |
Output is correct |
22 |
Correct |
396 ms |
212704 KB |
Output is correct |
23 |
Correct |
406 ms |
216804 KB |
Output is correct |
24 |
Correct |
391 ms |
198028 KB |
Output is correct |
25 |
Correct |
392 ms |
198212 KB |
Output is correct |
26 |
Correct |
290 ms |
147608 KB |
Output is correct |
27 |
Correct |
363 ms |
189556 KB |
Output is correct |
28 |
Correct |
369 ms |
187464 KB |
Output is correct |
29 |
Correct |
463 ms |
243780 KB |
Output is correct |
30 |
Correct |
372 ms |
199364 KB |
Output is correct |
31 |
Correct |
305 ms |
174916 KB |
Output is correct |
32 |
Incorrect |
378 ms |
217152 KB |
Output isn't correct |
33 |
Halted |
0 ms |
0 KB |
- |