Submission #1160325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160325		InvMOD	Holiday (IOI14_holiday)	C++20	7 / 100	5094 ms	808 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)));

    dp_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][i] != -INF)
                dp_Up[1][day][i] = dp_Up[0][day - 1][i] + a[i];
            ckmx(dp_Up[0][day][i], dp_Up[0][day - 1][i - 1]);
            ckmx(dp_Up[0][day][i], dp_Up[1][day - 1][i - 1]);
        }
    }

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

    dp_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][i] != -INF)
                dp_Down[1][day][i] = dp_Down[0][day - 1][i] + a[i];
            ckmx(dp_Down[0][day][i], dp_Down[0][day - 1][i + 1]);
            ckmx(dp_Down[0][day][i], dp_Down[1][day - 1][i + 1]);
        }
    }

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

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

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

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

    ll answer = 0;
    for(int i = 1; i <= n; i++){
        ckmx(answer, dp_Up[0][d][i]);
        ckmx(answer, dp_Up[1][d][i]);
        ckmx(answer, dp_Down[0][d][i]);
        ckmx(answer, dp_Down[1][d][i]);
    }
    return answer;
}
*/

ll findMaxAttraction(int n, int start, int d, int attraction[]){
    ll answer = 0;
    for(int mask = 1; mask < (1 << n); mask++){
        int L = INT_MAX, R = INT_MIN;

        ll sum = 0, cnt = __builtin_popcount(mask);
        for(int i = 0; i < n; i++){
            if(mask >> i & 1){
                sum += attraction[i];
                L = min(L, i);
                R = max(R, i);
            }
        }

        if(start < L){
            if(R - start + cnt <= d){
                answer = max(answer, sum);
            }
        }
        else if(start > R){
            if(start - L + cnt <= d){
                answer = max(answer, sum);
            }
        }
        else{
            ll needD = min(start - L, R - start) + (R - L) + cnt;
            if(needD <= d){
                answer = max(answer, sum);
            }
        }
    }

    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