oj.uz

Submission #69781

# Submission time Handle Problem Language Result Execution time Memory
69781 2018-08-21T13:25:38 Z 3zp Homecoming (BOI18_homecoming) C++14
13 / 100
 746 ms 263168 KB 
#include<bits/stdc++.h>
#include "homecoming.h"
using namespace std;
int N1;
long long sa[2000009], sb[2000009];
long long Sb(long long l, long long r){
    while(l >= N1) l -=N1;
    while(r >= N1) r -=N1;
    if(!l) return sb[r];
    if(l <= r) return sb[r] - sb[l-1];
    return sb[N1-1] - sb[l - 1] + sb[r];
}
long long Sa(long long l, long long r){
    while(l >= N1) l -=N1;
    while(r >= N1) r -=N1;
    if(!l) return sa[r];
    if(l <= r) return sa[r] - sa[l-1];
    return sa[N1-1] - sa[l - 1] + sa[r];
}
long long su(long long l, long long r){
    return Sa(l,r) - Sb(l,r);
}
long long M[2000009][21];
long long dp[4000009][2];
long long A1[6000009];
long long B1[6000009];
long long int solve(int N, int K, int *A, int *B){
    //if(N > 1e5) return 1/0;
    N1 = N;
    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 < N; i++)
        sa[i] = sa[i-1] + A1[i],
        sb[i] = sb[i-1] + B1[i];
    for(int i = 0 ;i < N; i++)
        M[i][0] = su(i,i);
    for(long long i = 1; (1 << i) <= N; i++){
        for(long long j = 0; j < N; j++){
            long long m1 = M[j][i-1];
            int K =j+(1<<(i-1));
            if(K >= N) K -= N;
            long long m2 = M[K][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, i+K-1);
        long long x = i, ss = 0;
        for(long long L = 20; L >= 0; L--){
            if(x - (1<<L) < 0)  continue;
            int t =(x - (1<<L));
            if(t >= N) t -=N;
            if(M[t][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:50: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 3 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 3 ms 736 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 3 ms 736 KB Output is correct
6 Correct 6 ms 1844 KB Output is correct
7 Correct 6 ms 1984 KB Output is correct
8 Correct 5 ms 1984 KB Output is correct
9 Correct 6 ms 2392 KB Output is correct
10 Incorrect 5 ms 2392 KB Output isn't correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 746 ms 126172 KB Output is correct
2 Correct 11 ms 126172 KB Output is correct
3 Runtime error 557 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 3 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 3 ms 736 KB Output is correct
6 Correct 6 ms 1844 KB Output is correct
7 Correct 6 ms 1984 KB Output is correct
8 Correct 5 ms 1984 KB Output is correct
9 Correct 6 ms 2392 KB Output is correct
10 Incorrect 5 ms 2392 KB Output isn't correct