| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1100910 | Tame | Holiday (IOI14_holiday) | 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 <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#define pu push
#define pf push_front
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fi first
#define se second
#define el cout<<"\n"
#define ll long long
#define ld long double
#define MASK(i) (1LL<<(i))
#define BIT(x, i) (((x)>>(i))&1)
#define SET_ON(x, i) ((x)|MASK(i))
#define c_bit(i) __builtin_popcount(i)
const int MAX_SIZE = 100003;
const ll INF = (ll)1e18;
using namespace std;
template<class T1, class T2>
bool maximize(T1 &x, T2 y){if(x<y){x=y; return true;} return false;}
template<class T1, class T2>
bool minimize(T1 &x, T2 y){if(x>y){x=y; return true;} return false;}
int nLength, nStep, nStart;
int a[MAX_SIZE];
ll res=0;
void init(){
cin>>nLength>>nStart>>nStep;
for (int i=0; i<nLength; i++){
cin>>a[i];
}
}
namespace subtask1{
bool check(){
return nLength<=20;
}
void solve(){
ll sum;
for (int mask=0; mask<MASK(nLength); mask++){
sum=0; int rest = nStep, last=-1;
for (int i=nStart; i>=0; i--) if (BIT(mask, i)) last = i;
for (int i=nStart; i>=last; i--){
if (last==-1) break;
if (i!=nStart) {
rest--;
if (rest<=0) break;
}
if (BIT(mask, i)){
sum+=a[i]; rest--;
if (rest<=0) break;
}
}
if (last!=-1) rest-=(nStart - last);
last = -1;
for (int i=nStart+1; i<nLength; i++) if (BIT(mask, i)==1) last = i;
for (int i=nStart+1; i<=last; i++){
if (rest<=0 || last==-1) break;
rest--; if (rest<=0) break;
if (BIT(mask, i)==1){
sum+=a[i]; rest--;
if (rest <= 0) break;
}
}
maximize(res, sum);
}
cout<<res<<"\n";
}
}
namespace subtask2{
bool check(){
return (nStart==0);
}
ll curSum = 0;
priority_queue<int, vector<int>, greater<int>>pq;
void solve(){
int maxGo = nStep;
for (int i=0; i<min(nLength, maxGo); i++){
curSum+=a[i]; pq.pu(a[i]);
while ((int)pq.size() > (maxGo - i)){
curSum-=pq.top(); pq.pop();
}
maximize(res, curSum);
}
cout<<res<<"\n";
}
}
namespace subtask3{
bool check(){
return true;
}
ll dp[2][MAX_SIZE], Right[MAX_SIZE], Left[MAX_SIZE];
void solve(){
//Central -> Right -> Left
//calculate on Right
if (nStart+1<nLength){
memset(dp, -0x3f, sizeof(dp));
dp[(nStart+1)&1][1] = 0; maximize(Right[1], dp[(nStart+1)&1][1]);
dp[(nStart+1)&1][2] = a[nStart+1]; maximize(Right[2], dp[(nStart+1)&1][2]);
for (int i=nStart+2; i<nLength; i++){
for (int j=0; j<=nStep; j++) dp[i&1][j] = -INF;
for (int j=1; j<=nStep; j++){
if (dp[!(i&1)][j-1]>-INF) maximize(dp[i&1][j], dp[!(i&1)][j-1]);
if (j>=2) if (dp[!(i&1)][j-2]>-INF){
maximize(dp[i&1][j], dp[!(i&1)][j-2] + a[i]);
}
if (dp[i&1][j]>=0){
maximize(Right[j], dp[i&1][j]);
maximize(res, dp[i&1][j]);
}
}
}
}
for (int j=1; j<=nStep; j++) maximize(Right[j], Right[j-1]);
//calculate on Left
memset(dp, -0x3f, sizeof(dp));
dp[nStart&1][0] = 0; maximize(res, dp[nStart&1][0] + Right[nStep]);
dp[nStart&1][1] = a[nStart]; if (1<=nStep) maximize(res, dp[nStart&1][1] + Right[nStep-1]);
for (int i=nStart-1; i>=0; i--){
for (int j=0; j<=nStep; j++) dp[i&1][j] = -INF;
for (int j=1; j<=nStep; j++){
if (dp[!(i&1)][j-1]>-INF) maximize(dp[i&1][j], dp[!(i&1)][j-1]);
if (j>=2) if (dp[!(i&1)][j-2]>-INF){
maximize(dp[i&1][j], dp[!(i&1)][j-2] + a[i]);
maximize(res, dp[i&1][j]);
}
int used = j + (nStart-i);
if (used<=nStep) maximize(res, dp[i&1][j] + Right[nStep - used]);
}
}
// Central -> Left -> Right
// calculate on Left
memset(dp, -0x3f, sizeof(dp));
dp[nStart&1][0] = 0; maximize(Left[0], dp[nStart&1][0]);
dp[nStart&1][1] = a[nStart]; maximize(Left[1], dp[nStart&1][1]);
for (int i=nStart-1; i>=0; i--){
for (int j=0; j<=nStep; j++) dp[i&1][j] = -INF;
for (int j=1; j<=nStep; j++){
if (dp[!(i&1)][j-1]>-INF) maximize(dp[i&1][j], dp[!(i&1)][j-1]);
if (j>=2) if (dp[!(i&1)][j-2]>-INF) {
maximize(dp[i&1][j], dp[!(i&1)][j-2] + a[i]);
}
if (dp[i&1][j]>=0){
maximize(Left[j], dp[i&1][j]);
maximize(res, dp[i&1][j]);
}
}
}
for (int j=1; j<=nStep; j++) maximize(Left[j], Left[j-1]);
//calculate on Right
memset(dp, -0x3f, sizeof(dp));
if (nStart+1<nLength){
dp[(nStart+1)&1][1] = 0; if (2<=nStep) maximize(res, dp[(nStart+1)&1][1] + Left[nStep-2]);
dp[(nStart+1)&1][2] = a[nStart+1]; if (3<=nStep) maximize(res, dp[(nStart+1)&1][2] + Left[nStep-3]);
for (int i=nStart+2; i<nLength; i++){
for (int j=0; j<=nStep; j++) dp[i&1][j] = -INF;
for (int j=1; j<=nStep; j++){
if (dp[!(i&1)][j-1]>-INF) maximize(dp[i&1][j], dp[!(i&1)][j-1]);
if (j>=2) if (dp[!(i&1)][j-2]>-INF) {
maximize(dp[i&1][j], dp[!(i&1)][j-2] + a[i]);
maximize(res, dp[i&1][j]);
}
int used = j + (i-nStart);
if (used<=nStep) maximize(res, dp[i&1][j] + Left[nStep - used]);
}
}
}
cout<<res<<"\n";
}
}
void ilovesunshine(){
init();
if (subtask2::check()) return subtask2::solve();
if (subtask3::check()) return subtask3::solve();
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("holiday.INP", "r", stdin);
// freopen("holiday.OUT", "w", stdout);
ilovesunshine();
return 0;
}