| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1227892 | Sir_Ahmed_Imran | Homecoming (BOI18_homecoming) | C++17 | 0 ms | 0 KiB |
// 01001100 01001111 01010100 01000001 \\
// \\
// ╦ ╔═╗╔╦╗╔═╗ \\
// ║ ║ ║ ║ ╠═╣ \\
// ╩═╝╚═╝ ╩ ╩ ╩ \\
// \\
// 01001100 01001111 01010100 01000001 \\
#include "homecoming.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 2000001
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
int n;
ll p[MAXN];
ll dp[MAXN][2][2];
ll get(int l, int r){
if(l > r)
return p[n - 1] - p[l - 1] + p[r];
if(!l) return p[r];
return p[r] - p[l - 1];
}
ll solve(int N, int k, vector<int> a, vector<int> b){
n = N;
p[0] = b[0];
for(int i = 1; i < n; i++)
p[i] = p[i - 1] + b[i];
for(int i = 0; i < n; i++)
for(int j = 0; j < 2; j++)
for(int l = 0; l < 2; l++)
dp[i][j][l] = -1e17;
dp[0][0][0] = 0;
dp[0][1][1] = a[0] - get(0, k - 1);
for(int i = 1; i < n; i++){
for(int j = 0; j < 2; j++){
for(int l = 0; l < 2; l++){
dp[i][0][l] = max(dp[i][0][l], dp[i - 1][j][l]);
if(i + k - 1 < n){
if(j) dp[i][1][l] = max(dp[i][1][l], dp[i - 1][j][l] + a[i] - b[i + k - 1]);
else dp[i][1][l] = max(dp[i][1][l], dp[i - 1][j][l] + a[i] - get(i, i + k - 1));
}
else{
if(l){
if(j) dp[i][1][l] = max(dp[i][1][l], dp[i - 1][j][l] + a[i]);
else dp[i][1][l] = max(dp[i][1][l], dp[i - 1][j][l] + a[i] - get(i, n - 1));
}
else{
if(j) dp[i][1][l] = max(dp[i][1][l], dp[i - 1][j][l] + a[i] - b[(i + k - 1) % n]);
else dp[i][1][l] = max(dp[i][1][l], dp[i - 1][j][l] + a[i] - get(i, (i + k - 1) % n));
}
}
}
}
}
ll ans = 0;
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++)
ans = max(ans, dp[n - 1][i][j]);
return ans;
}
/*
void solve(){
int n, k;
cin >> n >> k;
vector<int> a(n), 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) << nl;
}
int terminator(){
L0TA;
solve();
return 0;
}