oj.uz

Submission #69766

# Submission time Handle Problem Language Result Execution time Memory
69766 2018-08-21T13:08:56 Z 3zp Homecoming (BOI18_homecoming) C++14
31 / 100
 836 ms 263168 KB 
#include<bits/stdc++.h>
#include "homecoming.h"
using namespace std;
long long sa[6000009], sb[6000009];
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 Sb(long long l, long long r){
    if(!l) return sb[r];
    else return sb[r] - sb[l-1];
}
long long M[4000009][22];
long long dp[4000009][2];
long long A1[2000009];
long long B1[2000009];
long long int solve(int N, int K, int *A, int *B){
    //if(N > 1e5) return 1/0;
    for(long long i = 0; i < N; i++)
        A1[i] = A[i],
        B1[i] = B[i];
    for(long long i = 0; i < 2*N; i++)
        A1[i+N] = A1[i],
        B1[i+N] = B1[i];
    sa[0] = A1[0];
    sb[0] = B1[0];
    for(long long i = 1; i < 3*N; i++)
        sa[i] = sa[i-1] + A1[i],
        sb[i] = sb[i-1] + B1[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 = 1e18, FI = -1;
    for(long long i = N; i < 2*N; i++){
        long long S = A1[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;
            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;
        }
    }
    if(FI == -1 || N == K) return max((long long)0, sa[N-1] - sb[N-1]);
    FI -= N;
    dp[FI][0] = -1e18;
    dp[FI][1] = A1[FI] - Sb(FI, FI+K-1);
    for(long long i = FI + 1; i < FI + N - K; i++){
        dp[i][0] = max(dp[i-1][0] , dp[i-1][1]);
        dp[i][1] = dp[i-1][1] + A1[i] - B1[i + K - 1];
        if(i - K >= FI) dp[i][1] =max(dp[i][1],
                                      max(dp[i - K][0] , dp[i - K][1]) +
                                                A1[i] - Sb(i, i+K-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 += A1[i+N] - B1[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]);
    return 0;
}

Compilation message

homecoming.cpp: In function 'long long int solve(int, int, int*, int*)':
homecoming.cpp:37:37: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
                           su(j+(1<<i-1), j+(1<<i) - 1));
                                    ~^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 744 KB Output is correct
3 Correct 2 ms 744 KB Output is correct
4 Correct 2 ms 744 KB Output is correct
5 Correct 2 ms 748 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 744 KB Output is correct
3 Correct 2 ms 744 KB Output is correct
4 Correct 2 ms 744 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 5 ms 2680 KB Output is correct
7 Correct 4 ms 2804 KB Output is correct
8 Correct 4 ms 2804 KB Output is correct
9 Correct 5 ms 2872 KB Output is correct
10 Correct 3 ms 2872 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 836 ms 231792 KB Output is correct
2 Correct 14 ms 231792 KB Output is correct
3 Runtime error 692 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 744 KB Output is correct
3 Correct 2 ms 744 KB Output is correct
4 Correct 2 ms 744 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 5 ms 2680 KB Output is correct
7 Correct 4 ms 2804 KB Output is correct
8 Correct 4 ms 2804 KB Output is correct
9 Correct 5 ms 2872 KB Output is correct
10 Correct 3 ms 2872 KB Output is correct
11 Correct 836 ms 231792 KB Output is correct
12 Correct 14 ms 231792 KB Output is correct
13 Runtime error 692 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -