Submission #69645

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
69645	2018-08-21T10:32:13 Z	3zp	Homecoming (BOI18_homecoming)	C++14	Compilation error	0 ms	0 KB

homecoming

#include<bits/stdc++.h>
#include "homecoming.h"
using namespace std;
long long sa[600009], sb[600009];
long long su (long long l, long long r){
    if(!l) return -sb[r]+sa[r];
    return -sb[r] + sa[r] + sb[l-1] - sa[l-1];
}
long long M[5009][22];
long long dp[40009][2];
long long int solve(int N, int K, int *A, int *B){
    for(long long i = 0; i < 2*N; i++)
        A[i+N] = A[i],
        B[i+N] = B[i];
    sa[0] = A[0];
    sb[0] = B[0];

    for(long long i = 1; i < 3*N; i++)
        sa[i] = sa[i-1] + A[i],
        sb[i] = sb[i-1] + B[i];
    for(int i = 0 ;i < 2*N; i++)
        M[i][0] = su(i,i);
    for(long long i = 1; (1 << i) < 2*N; i++){
        for(long long j = 0; j + (1<<i) - 1 < 2*N; j++){
            long long m1 = M[j][i-1];
            long long m2 = M[j+(1<<(i-1))][i-1];
            M[j][i] = max(m2, m1 + su(j+(1<<i-1), j+(1<<i) - 1));
        }
    }
    long long masof = 1e9, FI = -1;
    for(long long i = N; i < 2*N; i++){
        long long S = A[i] - sb[i+K-1] + sb[i-1];
        long long x = i, ss = 0;
        for(long long L = 21; L >= 0; L--){
            if(x - (1<<L) < 0)  continue;
             //cout << ss <<" "<< x- (1<<L) <<" "<<L<<" "<<M[x-(1<<L)][L]<<" "<<S<<endl;
            if(M[x - (1<<L)][L] + ss + S >= 0) continue;
            ss += su(x - (1 << L), x -1);
            x = x - (1 << L);
        }
        int l;
        if(S >= 0) l = i;
        else l = x - 1;
        if(l <= i - N) l = -1;
        if(l != -1 && masof > i - l) {
            FI = i;
            masof = i - l;
        }
      //  cout << i <<" "<<l << " "<<S<<" "<<A[i]<<" "<<sb[i+K-1]<<" "<<sb[i-1]<<endl;
    }
    if(FI == -1) return 0;
    FI -= N;
    dp[FI][0] = -1e18;
    dp[FI][1] = A[FI] - sb[K+FI-1] + sb[FI-1];
    for(long long i = FI + 1; i < FI + N - K; i++){
        dp[i][0] = dp[i-1][0] + dp[i-1][1];
        dp[i][1] = dp[i-1][1] + A[i] - B[i + K - 1];
        if(i - K >= FI) dp[i][1] =max(dp[i][1], dp[i - K][0] + dp[i - K][1] +
                                                A[i] - sb[i+ K - 1] + sb[i-1]);
    }
    long long ans = max(dp[FI + N - K - 1][0], dp[FI+ N - K - 1][1]);
    long long s = 0;
    for(long long i =  FI - 1; i > FI - N + K; i --){
        s += A[i+N] - B[i+N];
        ans =max(ans, s + max(dp[i + N - K - 1][0], dp[i + N - K - 1][1]));
    }
    return max(max((long long)0,ans), sa[N-1]-sb[N-1]);
}
long long a[100009], b[100009];
main(){
    long long n, K;
    cin >> n >> K;
    for(long long i= 0 ; i < n; i++)
        cin >> a[i];
    for(long long i = 0; i < n; i++){
        cin >> b[i];
    }
    cout << solve(n, K, a, b) << endl;
}

Compilation message

homecoming.cpp: In function 'long long int solve(int, int, int*, int*)':
homecoming.cpp:27:46: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
             M[j][i] = max(m2, m1 + su(j+(1<<i-1), j+(1<<i) - 1));
                                             ~^~
homecoming.cpp: At global scope:
homecoming.cpp:70:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
homecoming.cpp: In function 'int main()':
homecoming.cpp:78:29: error: cannot convert 'long long int*' to 'int*' for argument '3' to 'long long int solve(int, int, int*, int*)'
     cout << solve(n, K, a, b) << endl;
                             ^