oj.uz

Submission #69807

# Submission time Handle Problem Language Result Execution time Memory
69807 2018-08-21T14:27:13 Z 3zp Homecoming (BOI18_homecoming) C++14
0 / 100
 406 ms 237204 KB 
#include<bits/stdc++.h>
#include "homecoming.h"
using namespace std;
long long 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];
long long T[2000009];
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){
    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],
        T[i] = A1[i] - B1[i];
    if(N == K)  return max((long long)0, sa[N-1] - sb[N-1]);
    deque<pair<long long,long long> > q;
    long long H = 0, D = 0;
    for(long long i = N-K-1; i >= 0; i--){
        H += T[i];
        if(q.size() == 0 || H > q.front().first) q.push_front({T[i],i});
    }
    for(long long i = N-K-1; i < N+N-K-1; i++){
        M[i%N] = q.front().second ;
        if(q.front().second == i-N+K+1) q.pop_front();
        D += T[i%N];
        long long p = T[i%N] - D;
        while(q.size() && q.back().first <= p)  q.pop_back();
        q.push_back({p,i%N});
    }
    long long masof = 1e18, FI = -1;
    for(long long i =  0; i < N; i++){
        long long le = M[i];
        long long si = i - le;
        if(si < 0) si += N;
        if(si < masof) masof = si, FI = i;
    }
    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;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 616 KB Output is correct
3 Correct 2 ms 616 KB Output is correct
4 Correct 3 ms 616 KB Output is correct
5 Incorrect 2 ms 616 KB Output isn't 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 616 KB Output is correct
3 Correct 2 ms 616 KB Output is correct
4 Correct 3 ms 616 KB Output is correct
5 Incorrect 2 ms 616 KB Output isn't correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 59628 KB Output is correct
2 Correct 6 ms 59628 KB Output is correct
3 Correct 406 ms 237204 KB Output is correct
4 Incorrect 7 ms 237204 KB Output isn't correct
5 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 616 KB Output is correct
3 Correct 2 ms 616 KB Output is correct
4 Correct 3 ms 616 KB Output is correct
5 Incorrect 2 ms 616 KB Output isn't correct