| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 61683 | hamzqq9 | Homecoming (BOI18_homecoming) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "homecoming.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000000000000000
#define umax(x,y) x=max(x,(y))
#define pw(x) (1<<(x))
ll psum[2000002],psum2[2000002];
vector<ll> dp[2][2000002];
long long solve(int N, int K, int *A, int *B) {
for(int i=0;i<2;i++) {
for(int j=0;j<N+2;j++) {
dp[i][j].resize(min(j,K+1));
}
}
for(int i=1;i<=N;i++) {psum[i]=psum[i-1]+B[i-1];psum2[i]=psum2[i-1]+A[i-1];}
for(int i=1;i<=N+1;i++) for(int j=0;j<=min(i-1,K);j++) for(int t=0;t<2;t++) dp[t][i][j]=-inf;
dp[1][1][0]=0;
for(int i=1;i<=N;i++) {
for(int j=0;j<=min(i-1,K);j++) {
if(dp[1][i][j]!=-inf) {
if(i<N) umax(dp[1][i+1][min(K,j+(j==i-1))],dp[1][i][j]-B[i-1]+(i-K+1>=1?A[i-K+1-1]:0));
else {
int amount=max(0,min(j+1,K));
umax(dp[1][N+1][min(K,j+(j==i-1))],dp[1][i][j]-B[i-1]+psum2[i-K+amount]-psum2[i-K]);
}
umax(dp[0][i+1][j],dp[1][i][j]);
}
if(dp[0][i][j]!=-inf) {
if(i+K<=N) {
umax(dp[1][i+K][j],dp[0][i][j]+A[i-1]-(psum[i+K-1]-psum[i-1]));
}
else {
int amount=max(0,min(N+1-i,j+N+1-i-K+1));
umax(dp[1][N+1][j],dp[0][i][j]+psum2[i+amount-1]-psum2[i-1]-(psum[N]-psum[i-1]));
}
umax(dp[0][i+1][j],dp[0][i][j]);
}
}
}
ll res=0;
for(int i=0;i<=min(N,K);i++) {
umax(res,max(dp[0][N+1][i],dp[1][N+1][i]));
}
umax(res,psum2[N]-psum[N]);
return res;
}
int main() {
srand(time(NULL));
while(1) {
int a[15],b[15];
int n=rand()%10+1;
int k=rand()%n+1;
for(int i=0;i<n;i++) {
a[i]=rand()%16;
b[i]=rand()%16;
}
//n=7;k=2;
//a[0]=7;a[1]=0;a[2]=12;a[3]=13;a[4]=14;a[5]=7;a[6]=4;a[7]=14;a[8]=6;
//b[0]=12;b[1]=7;b[2]=3;b[3]=14;b[4]=6;b[5]=12;b[6]=1;b[7]=14;b[8]=4;
ll res2=0;
int state=0;
for(int i=0;i<pw(n);i++) {
int ok[15]={0};
ll pro=0;
for(int j=0;j<n;j++) {
if(i&pw(j)) {
for(int w=0;w<k;w++) {
ok[(j+w)%n]=1;
}
pro+=a[j];
}
}
for(int j=0;j<n;j++) pro-=b[j]*ok[j];
if(pro>res2) {
res2=pro;
state=i;
}
}
ll res1=solve(n,k,a,b);
if(res2!=res1) {
printf("%d %d\n",n,k);
for(int i=0;i<n;i++) printf("%d ",a[i]);
puts("");
for(int i=0;i<n;i++) printf("%d ",b[i]);
puts("");
int okey[15]={0};
for(int i=0;i<n;i++) {
if(state&pw(i)) {
for(int w=0;w<k;w++) okey[(i+w)%n]=1;
}
}
for(int i=0;i<n;i++) printf("%d ",okey[i]);
puts("");
printf("yours-->%lld real-->%lld\n",res1,res2);
return 0;
}
}
/*freopen("in.txt","r",stdin);
int T; assert(scanf("%d", &T) == 1);
for(int t = 0; t < T; t++) {
int N, K; assert(scanf("%d%d", &N, &K) == 2);
int *A = new int[N];
int *B = new int[N];
for(int i = 0; i < N; i++) assert(scanf("%d", &A[i]) == 1);
for(int i = 0; i < N; i++) assert(scanf("%d", &B[i]) == 1);
printf("%lld\n", solve(N, K, A, B));
delete[] A;
delete[] B;
}
return 0;*/
}