oj.uz

Submission #152044

# Submission time Handle Problem Language Result Execution time Memory
152044 2019-09-06T07:01:49 Z souhhcong Homecoming (BOI18_homecoming) C++14
0 / 100
 49 ms 12920 KB 
#include <iostream>
//#include <homecoming.h>
using namespace std;

const int MAXN = 2e6+2;
//int n, k;
//int a[MAXN], b[MAXN];
long long dp[MAXN], pref[MAXN], ans = 0;

long long get_sum(int l, int r, int N)
{
    if (l == 0) return pref[r];
    if (l <= r)
        return pref[r] - pref[l-1];
    else
        return get_sum(l,N-1,N) + pref[r];
}

long long int solve(int N, int K, int *A, int *B)
{
    pref[0] = B[0];
    for (int i = 1; i < N; i++)
    {
        pref[i] = pref[i-1] + B[i];
    }
    dp[0] = max(0LL,A[0]-get_sum(0,K-1,N));
    for (int i = 1; i < N; i++)
    {
        if (i >= K)
            dp[i] = max(dp[i], max(dp[i-1] + A[i] - B[(i+K-1)%N], dp[i-K] + A[i] - get_sum(i,(i+K-1)%N, N)));
        else
            dp[i] = max(dp[i], dp[i-1] + A[i] - B[(i+K-1)%N]);
    }
    for (int i = 0; i < N; i++)
        ans = max(ans,dp[i]);
    //cout << dp[0] << ' ' << dp[1] << ' ' << dp[2] << endl;
    return ans;
}

/*
int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];
    cout << solve(n,k,a,b);
}
*/
/*
3 2
40 80 100
140 0 20
*/

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 12920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -