oj.uz

Submission #152038

# Submission time Handle Problem Language Result Execution time Memory
152038 2019-09-06T06:51:21 Z souhhcong Homecoming (BOI18_homecoming) C++14
0 / 100
 1000 ms 18216 KB 
#include <iostream>
#include <homecoming.h>
using namespace std;

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

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

long long 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));
    for (int i = 1; i < N; i++)
    {
        if (i >= K)
            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));
        else
            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 Execution timed out 1080 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1061 ms 18216 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -