Submission #61683

#TimeUsernameProblemLanguageResultExecution timeMemory
61683hamzqq9Homecoming (BOI18_homecoming)C++14
Compilation error
0 ms0 KiB
#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;*/ }

Compilation message (stderr)

/tmp/cc3qvRoS.o: In function `main':
homecoming.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccva7k3T.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status