oj.uz

Submission #73917

# Submission time Handle Problem Language Result Execution time Memory
73917 2018-08-29T09:24:47 Z jiaqing23 Homecoming (BOI18_homecoming) C++14
0 / 100
 59 ms 20084 KB 
#include <bits/stdc++.h>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector<ll> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;
typedef pair<int,pair<int,int> > tri;

ll dp[2000050][2];
ll ans = 0;
ll sum[4000050];

long long solve(int N, int K, int *A, int *B){
    //din pass first subject
    dp[0][0] = 0;
    dp[0][1] = -(ll)1e18;
    sum[0] = B[0];
    for(int i = 1; i < N; i++) sum[i] = sum[i-1] + (ll)B[i];
    for(int i = N; i < 2 * N; i++) sum[i] = sum[N-1] + sum[i-N];
    for(int i = 1; i < N; i++){
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
        dp[i][1] = (ll)A[i] + max(dp[i-1][0] - (sum[i+K-1]-sum[i-1]), dp[i-1][1] - (ll)B[(i+K-1)%N]);
    }
    ans = max(ans, max(dp[N-1][0], dp[N-1][1]));

    //pass the first subject
    dp[0][1] = (ll)A[0] - sum[K-1];
    dp[0][0] = -(ll)1e18;
    for(int i = 0; i < K; i++) B[i] = 0;
    sum[0] = B[0];
    for(int i = 1; i < N; i++) sum[i] = sum[i-1] + (ll)B[i];
    for(int i = N; i < 2 * N; i++) sum[i] = sum[N-1] + sum[i-N];
    for(int i = 1; i < N ; i++){
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
        if(i < N-K+1) dp[i][1] = (ll)A[i] + max(dp[i-1][0] - (sum[i+K-1]-sum[i-1]), dp[i-1][1] - (ll)B[i+K-1]);
        else dp[i][1] = (ll)A[i] + max(dp[i-1][0] - (sum[N-1]-sum[i-1]), dp[i-1][1]);
        //cout<<i<<' '<<dp[i][0]<<' '<<dp[i][1] <<endl;

    }
    ans = max(ans, max(dp[N-1][0], dp[N-1][1]));

   /* cout<<dp[N-1][0]<<' '<<dp[N-1][1]<<endl;
    cout<<endl;
    for(int i = 0; i < 2*N; i++) cout<<sum[i]<<' ';
    cout<<endl;*/

    return ans;
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 31.0

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