Submission #1160363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160363		InvMOD	Holiday (IOI14_holiday)	C++20	7 / 100	61 ms	131072 KiB

holiday

#include<bits/stdc++.h>

//#define name "InvMOD"
#ifndef name
    #include "holiday.h"
#endif // name

using namespace std;

using ll = long long;

template<typename T> bool ckmx(T& a, const T& b){
    if(a < b)
        return a = b, true;
    return false;
}

const int N = 1e5 + 5;
const ll INF = 1e15;

int n, start, d, a[N];

ll findMaxAttraction(int iN, int iStart, int iDay, int attraction[]){
    n = iN, start = iStart + 1, d = iDay;

    for(int i = 1; i <= n; i++){
        a[i] = attraction[i - 1];
    }
    vector<vector<vector<ll>>> dp_Up(2, vector<vector<ll>>(d + 1, vector<ll>(n + 1, -INF)));
    vector<vector<vector<ll>>> pdp_Up(2, vector<vector<ll>>(d + 1, vector<ll>(n + 1, -INF)));

    ll answer = 0;

    dp_Up[0][0][start] = pdp_Up[0][0][start] = 0;
    for(int day = 1; day <= d; day++){
        for(int i = start; i <= n; i++){
            if(dp_Up[0][(day - 1) & 1][i] != -INF)
                dp_Up[1][(day & 1)][i] = dp_Up[0][(day - 1) & 1][i] + a[i];
            if(i > 1) ckmx(dp_Up[0][(day & 1)][i], dp_Up[0][(day - 1) & 1][i - 1]);
            if(i > 1) ckmx(dp_Up[0][(day & 1)][i], dp_Up[1][(day - 1) & 1][i - 1]);
        }
        pdp_Up[0][(day & 1)] = dp_Up[0][(day & 1)];
        pdp_Up[1][(day & 1)] = dp_Up[1][(day & 1)];

        for(int i = n - 1; i >= start; i--){
            ckmx(pdp_Up[0][(day & 1)][i], pdp_Up[0][(day - 1) & 1][i + 1]);
            ckmx(pdp_Up[1][(day & 1)][i], pdp_Up[1][(day - 1) & 1][i + 1]);
        }

        for(int i = start - 1; i >= 1; i--){
            if(pdp_Up[0][(day - 1) & 1][i] != -INF)
                pdp_Up[1][(day & 1)][i] = pdp_Up[0][(day - 1) & 1][i] + a[i];
            if(i < n) ckmx(pdp_Up[0][(day & 1)][i], pdp_Up[0][(day - 1) & 1][i + 1]);
            if(i < n) ckmx(pdp_Up[0][(day & 1)][i], pdp_Up[1][(day - 1) & 1][i + 1]);
        }

        for(int i = 1; i <= n; i++){
            ckmx(answer, pdp_Up[0][(day & 1)][i]);
            ckmx(answer, pdp_Up[1][(day & 1)][i]);
        }
    }

    vector<vector<vector<ll>>> dp_Down(2, vector<vector<ll>>(2, vector<ll>(n + 1, -INF)));
    vector<vector<vector<ll>>> pdp_Down(2, vector<vector<ll>>(2, vector<ll>(n + 1, -INF)));

    dp_Down[0][0][start] = pdp_Down[0][0][start] = 0;
    for(int day = 1; day <= d; day++){
        for(int i = start; i >= 1; i--){
            if(dp_Down[0][(day - 1) & 1][i] != -INF)
                dp_Down[1][(day & 1)][i] = dp_Down[0][(day - 1) & 1][i] + a[i];
            if(i < n) ckmx(dp_Down[0][(day & 1)][i], dp_Down[0][(day - 1) & 1][i + 1]);
            if(i < n) ckmx(dp_Down[0][(day & 1)][i], dp_Down[1][(day - 1) & 1][i + 1]);
        }
        pdp_Down[0][(day & 1)] = dp_Down[0][(day & 1)];
        pdp_Down[1][(day & 1)] = dp_Down[1][(day & 1)];

        for(int i = 2; i <= start; i++){
            ckmx(pdp_Down[0][(day & 1)][i], pdp_Down[0][(day - 1) & 1][i - 1]);
            ckmx(pdp_Down[1][(day & 1)][i], pdp_Down[1][(day - 1) & 1][i - 1]);
        }

        for(int i = start + 1; i <= n; i++){
            if(pdp_Down[0][(day - 1) & 1][i] != -INF)
                pdp_Down[1][(day & 1)][i] = pdp_Down[0][(day - 1) & 1][i] + a[i];
            if(i > 1) ckmx(pdp_Down[0][(day & 1)][i], pdp_Down[0][(day - 1) & 1][i - 1]);
            if(i > 1) ckmx(pdp_Down[0][(day & 1)][i], pdp_Down[1][(day - 1) & 1][i - 1]);
        }

        for(int i = 1; i <= n; i++){
            ckmx(answer, pdp_Down[0][(day & 1)][i]);
            ckmx(answer, pdp_Down[1][(day & 1)][i]);
        }
    }

    return answer;
}


#ifdef name
    int32_t main(){
        if(fopen(name".INP", "r")){
            freopen(name".INP", "r", stdin);
            freopen(name".OUT", "w", stdout);
        }

        int n,start,d; cin >> n >> start >> d;

        int attraction[n];
        for(int i = 0; i < n; i++){
            cin >> attraction[i];
        }

        cout << findMaxAttraction(n, start, d, attraction) << "\n";

        return 0;
    }
#endif // name

• Subtask 1: 7 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53