oj.uz

Submission #646818

# Submission time Handle Problem Language Result Execution time Memory
646818 2022-09-30T18:50:36 Z jasmin Homecoming (BOI18_homecoming) C++14
0 / 100
 35 ms 16136 KB 
#include<homecoming.h>
#include<bits/stdc++.h>
using namespace std;

const long long inf=1e18;

long long solve(int n, int k, int* a, int* b1){
    vector<int> b(n*2);
    for(int i=0; i<n; i++){
        b[i]=b[i+n]=b1[i];
    }
    vector<int> prefixsum(n*2+1, 0);
    //cout << 0 << " ";
    for(int i=1; i<=n*2; i++){
        prefixsum[i]=prefixsum[i-1]+b[i-1];
        //cout << prefixsum[i] << " ";
    }
    //cout << "\n";

    vector<long long> dp(n+1, -inf);
    long long ans=0;
    dp[0]=-prefixsum[k-1];
    long long mmax=0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<k; j++){
            if(i-j<0) continue;

            long long cost=prefixsum[i+k-1]-prefixsum[i-j+k-1];
            //cout << i << " " << j << ": " << dp[i-j] << " " << a[i-1] << " " << cost << "\n";
            dp[i]=max(dp[i], dp[i-j]+a[i-1]-cost);
        }


        if(i-k>=0){
            mmax=max(mmax, dp[i-k]);
        }
        dp[i]=max(dp[i], mmax+a[i-1]-(prefixsum[i+k-1]-prefixsum[i-1]));
        ans=max(ans, dp[i]);

        //cout << dp[i] << "\n";
    }
    return ans;
}

/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    vector<int> b(n);

    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) << "\n";
}*/

Subtask #1
0 / 13.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 31.0

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

Subtask #4
0 / 38.0

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