| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 155059 | Charis02 | Homecoming (BOI18_homecoming) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#define ll long long
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 200003
#define INF 1e12
using namespace std;
ll books[N],prize[N],sum[N];
ll dp[N][2];
const ll PASSED=1,NPASSED=0;
ll get_sum(ll i,ll j)
{
if(i == 0)
return sum[j];
return sum[j] - sum[i-1];
}
ll solve(int n,int k,int A[],int B[])
{
rep(i,0,n)
{
prize[i] = A[i];
books[i] = B[i];
if(i == 0)
sum[i] = books[i];
else
sum[i] = sum[i-1]+books[i];
}
/*
if you pass class i and class j and j-i < k it is optimal to pass all classes in between.
*/
// fix that class 0 is passed
dp[0][PASSED] = prize[0] - get_sum(0,k-1);
dp[0][NPASSED] = -INF;
rep(i,1,n)
{
ll nextbook = i+k-1;
// passed previous class
ll cur = dp[i-1][PASSED];
if(nextbook < n)
cur -= books[nextbook];
cur+=prize[i];
dp[i][PASSED] = cur;
//didn't pass previous class
cur = dp[i-1][NPASSED];
cur -= get_sum(i,min(n-1,nextbook)); // if we add stuff that is already in dp[i-1][NPASSED], then optimal answer isn't here since we could just pass class i-1
cur+=prize[i];
dp[i][PASSED] = max(dp[i][PASSED],cur);
dp[i][NPASSED] = max(dp[i-1][NPASSED],dp[i-1][PASSED]);
}
ll ans = max(dp[n-1][PASSED],dp[n-1][NPASSED]);
// fix that he didn't pass class 0
dp[0][NPASSED] = 0;
dp[0][PASSED] = -INF;
rep(i,1,n)
{
ll nextbook = (i+k-1)%n;
// passed previous class
ll cur = dp[i-1][PASSED];
cur -= books[nextbook];
cur+=prize[i];
dp[i][PASSED] = cur;
//didn't pass previous class
cur = dp[i-1][NPASSED];
if(nextbook < i)
cur -= get_sum(i,n-1) + get_sum(0,nextbook);
else
cur -= get_sum(i,nextbook);
cur+=prize[i];
dp[i][PASSED] = max(dp[i][PASSED],cur);
dp[i][NPASSED] = max(dp[i-1][NPASSED],dp[i-1][PASSED]);
}
ans = max(ans,dp[n-1][PASSED]);
ans = max(ans,dp[n-1][NPASSED]);
return ans;
}