oj.uz

답안 #69786

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
69786 2018-08-21T13:34:28 Z 3zp Homecoming (BOI18_homecoming) C++14
31 / 100
 796 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];//,cout<<A[i]-B[i]<<endl;
    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);//, cout<<M[i][0]<<endl;
    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));
            //cout << j << " "<<(1<<i)<<" "<<M[j][i]<<endl;
        }
    }
    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) <= i -N)  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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 4 ms 620 KB Output is correct
5 Correct 3 ms 620 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 4 ms 620 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 7 ms 1864 KB Output is correct
7 Correct 6 ms 2036 KB Output is correct
8 Correct 4 ms 2036 KB Output is correct
9 Correct 5 ms 2204 KB Output is correct
10 Correct 4 ms 2204 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 796 ms 126292 KB Output is correct
2 Correct 11 ms 126292 KB Output is correct
3 Runtime error 642 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 4 ms 620 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 7 ms 1864 KB Output is correct
7 Correct 6 ms 2036 KB Output is correct
8 Correct 4 ms 2036 KB Output is correct
9 Correct 5 ms 2204 KB Output is correct
10 Correct 4 ms 2204 KB Output is correct
11 Correct 796 ms 126292 KB Output is correct
12 Correct 11 ms 126292 KB Output is correct
13 Runtime error 642 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -