Submission #1870504
Source Code Expand
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N=300005;
LL q[N],c[N],f[N],g[N],f1[N],f2[N],sum1[N],sum2[N],ans[N];
int a[N],n,m;
void dp(LL *sum){
memset(f,-0x3f,sizeof f);
f[0]=0;
int t=0;q[0]=c[0]=0;
for (LL i=1;i<=n;i++){
for (;t && (c[t]-c[t-1])<i*(q[t]-q[t-1]);t--);
f[i]=max(f[i-1],i*(i+1)/2-sum[i]+c[t]-q[t]*i);
LL j=f[i]+i*(i-1)/2+sum[i];
for (;t && (c[t]-c[t-1])*(i-q[t])<(j-c[t])*(q[t]-q[t-1]);t--);
q[++t]=i;c[t]=j;
}
}
void dp2(LL *ff,LL *sum,int l,int mid,int r){
int t=0;
for (LL i=l-1;i<mid;i++){
LL j=ff[i]+i*(i-1)/2+sum[i];
for (;t>1 && (c[t]-c[t-1])*(i-q[t])<(j-c[t])*(q[t]-q[t-1]);t--);
q[++t]=i;c[t]=j;
}
for (LL i=mid+1;i<=r;i++){
for (;t>1 && (c[t]-c[t-1])<i*(q[t]-q[t-1]);t--);
f[i]=i*(i+1)/2-sum[i]+c[t]-q[t]*i;
}
}
void solve(int l,int r){
if (l==r){
ans[l]=max(ans[l],f1[l-1]+f2[n-l]+1-a[l]);
return;
}
int mid=(l+r)>>1;
dp2(f1,sum1,l,mid,r);
for (int i=r;i>mid;i--) g[i]=f[i]+f2[n-i];
for (int i=r-1;i>mid;i--) g[i]=max(g[i],g[i+1]);
dp2(f2,sum2,n-r+1,n-mid,n-l+1);
for (int i=l;i<=mid;i++) g[i]=f[n-i+1]+f1[i-1];
for (int i=l+1;i<=mid;i++) g[i]=max(g[i],g[i-1]);
for (int i=l;i<=r;i++) ans[i]=max(ans[i],g[i]);
solve(l,mid);solve(mid+1,r);
}
int main(){
scanf("%d\n",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<=n;i++) sum1[i]=sum1[i-1]+a[i];
dp(sum1);
memcpy(f1,f,sizeof f);
for (int i=1;i<=n;i++) sum2[i]=sum2[i-1]+a[n-i+1];
dp(sum2);
memcpy(f2,f,sizeof f);
memset(ans,-0x3f,sizeof ans);
solve(1,n);
scanf("%d\n",&m);
for (int i=1;i<=m;i++){
int p,x;
scanf("%d%d",&p,&x);
printf("%lld\n",max(f1[p-1]+f2[n-p],ans[p]+a[p]-x));
}
}
Submission Info
Submission Time |
|
Task |
F - Contest with Drinks Hard |
User |
aufeas |
Language |
C++14 (GCC 5.4.1) |
Score |
1400 |
Code Size |
1769 Byte |
Status |
AC |
Exec Time |
235 ms |
Memory |
22912 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:49:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d\n",&n);
^
./Main.cpp:50:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
^
./Main.cpp:59:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d\n",&m);
^
./Main.cpp:62:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&p,&x);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1400 / 1400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt |
All |
sample_01.txt, sample_02.txt, subtask_1_high_equaly_01.txt, subtask_1_high_equaly_02.txt, subtask_1_high_equaly_03.txt, subtask_1_high_equaly_04.txt, subtask_1_high_rand_01.txt, subtask_1_high_rand_02.txt, subtask_1_high_rand_03.txt, subtask_1_high_rand_04.txt, subtask_1_killer_01.txt, subtask_1_killer_02.txt, subtask_1_low_equaly_01.txt, subtask_1_low_equaly_02.txt, subtask_1_low_equaly_03.txt, subtask_1_low_equaly_04.txt, subtask_1_low_rand_01.txt, subtask_1_low_rand_02.txt, subtask_1_low_rand_03.txt, subtask_1_low_rand_04.txt, subtask_1_max_high_equaly_01.txt, subtask_1_max_high_equaly_02.txt, subtask_1_max_high_equaly_03.txt, subtask_1_max_high_equaly_04.txt, subtask_1_max_high_rand_01.txt, subtask_1_max_high_rand_02.txt, subtask_1_max_high_rand_03.txt, subtask_1_max_high_rand_04.txt, subtask_1_max_low_equaly_01.txt, subtask_1_max_low_equaly_02.txt, subtask_1_max_low_equaly_03.txt, subtask_1_max_low_equaly_04.txt, subtask_1_max_low_rand_01.txt, subtask_1_max_low_rand_02.txt, subtask_1_max_low_rand_03.txt, subtask_1_max_low_rand_04.txt, subtask_1_max_rand_equaly_01.txt, subtask_1_max_rand_equaly_02.txt, subtask_1_max_rand_equaly_03.txt, subtask_1_max_rand_equaly_04.txt, subtask_1_max_rand_rand_01.txt, subtask_1_max_rand_rand_02.txt, subtask_1_max_rand_rand_03.txt, subtask_1_max_rand_rand_04.txt, subtask_1_min_rand_rand_01.txt, subtask_1_min_rand_rand_02.txt, subtask_1_rand_equaly_01.txt, subtask_1_rand_equaly_02.txt, subtask_1_rand_equaly_03.txt, subtask_1_rand_equaly_04.txt, subtask_1_rand_rand_01.txt, subtask_1_rand_rand_02.txt, subtask_1_rand_rand_03.txt, subtask_1_rand_rand_04.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
5 ms |
17408 KB |
sample_02.txt |
AC |
5 ms |
17408 KB |
subtask_1_high_equaly_01.txt |
AC |
96 ms |
20352 KB |
subtask_1_high_equaly_02.txt |
AC |
70 ms |
20096 KB |
subtask_1_high_equaly_03.txt |
AC |
23 ms |
17536 KB |
subtask_1_high_equaly_04.txt |
AC |
150 ms |
20864 KB |
subtask_1_high_rand_01.txt |
AC |
96 ms |
20352 KB |
subtask_1_high_rand_02.txt |
AC |
70 ms |
20224 KB |
subtask_1_high_rand_03.txt |
AC |
101 ms |
20352 KB |
subtask_1_high_rand_04.txt |
AC |
133 ms |
20608 KB |
subtask_1_killer_01.txt |
AC |
5 ms |
17408 KB |
subtask_1_killer_02.txt |
AC |
5 ms |
17408 KB |
subtask_1_low_equaly_01.txt |
AC |
160 ms |
22016 KB |
subtask_1_low_equaly_02.txt |
AC |
97 ms |
20608 KB |
subtask_1_low_equaly_03.txt |
AC |
111 ms |
20864 KB |
subtask_1_low_equaly_04.txt |
AC |
54 ms |
19968 KB |
subtask_1_low_rand_01.txt |
AC |
126 ms |
21632 KB |
subtask_1_low_rand_02.txt |
AC |
93 ms |
20736 KB |
subtask_1_low_rand_03.txt |
AC |
81 ms |
20736 KB |
subtask_1_low_rand_04.txt |
AC |
155 ms |
22016 KB |
subtask_1_max_high_equaly_01.txt |
AC |
234 ms |
21760 KB |
subtask_1_max_high_equaly_02.txt |
AC |
232 ms |
22144 KB |
subtask_1_max_high_equaly_03.txt |
AC |
235 ms |
22400 KB |
subtask_1_max_high_equaly_04.txt |
AC |
230 ms |
21504 KB |
subtask_1_max_high_rand_01.txt |
AC |
233 ms |
22400 KB |
subtask_1_max_high_rand_02.txt |
AC |
231 ms |
21760 KB |
subtask_1_max_high_rand_03.txt |
AC |
231 ms |
21760 KB |
subtask_1_max_high_rand_04.txt |
AC |
234 ms |
22144 KB |
subtask_1_max_low_equaly_01.txt |
AC |
214 ms |
22656 KB |
subtask_1_max_low_equaly_02.txt |
AC |
212 ms |
22912 KB |
subtask_1_max_low_equaly_03.txt |
AC |
218 ms |
22656 KB |
subtask_1_max_low_equaly_04.txt |
AC |
217 ms |
22912 KB |
subtask_1_max_low_rand_01.txt |
AC |
218 ms |
22912 KB |
subtask_1_max_low_rand_02.txt |
AC |
222 ms |
22656 KB |
subtask_1_max_low_rand_03.txt |
AC |
214 ms |
22912 KB |
subtask_1_max_low_rand_04.txt |
AC |
207 ms |
22912 KB |
subtask_1_max_rand_equaly_01.txt |
AC |
228 ms |
21248 KB |
subtask_1_max_rand_equaly_02.txt |
AC |
228 ms |
21248 KB |
subtask_1_max_rand_equaly_03.txt |
AC |
230 ms |
21248 KB |
subtask_1_max_rand_equaly_04.txt |
AC |
230 ms |
21248 KB |
subtask_1_max_rand_rand_01.txt |
AC |
233 ms |
21248 KB |
subtask_1_max_rand_rand_02.txt |
AC |
228 ms |
21248 KB |
subtask_1_max_rand_rand_03.txt |
AC |
228 ms |
21248 KB |
subtask_1_max_rand_rand_04.txt |
AC |
229 ms |
21248 KB |
subtask_1_min_rand_rand_01.txt |
AC |
5 ms |
17408 KB |
subtask_1_min_rand_rand_02.txt |
AC |
5 ms |
17408 KB |
subtask_1_rand_equaly_01.txt |
AC |
14 ms |
17536 KB |
subtask_1_rand_equaly_02.txt |
AC |
138 ms |
20480 KB |
subtask_1_rand_equaly_03.txt |
AC |
65 ms |
19968 KB |
subtask_1_rand_equaly_04.txt |
AC |
107 ms |
20352 KB |
subtask_1_rand_rand_01.txt |
AC |
155 ms |
20736 KB |
subtask_1_rand_rand_02.txt |
AC |
97 ms |
20224 KB |
subtask_1_rand_rand_03.txt |
AC |
138 ms |
20608 KB |
subtask_1_rand_rand_04.txt |
AC |
72 ms |
19968 KB |