Submission #288207

#	Time	Username	Problem	Language	Result	Execution time	Memory
288207		Atill83	Holiday (IOI14_holiday)	C++14	17 / 100	5091 ms	4488 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = (int) 1e5 + 5;
ll dp1[MAXN][2];
ll dp2[MAXN][2];

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    multiset<ll> st;
    for(int j = start; j >= 0; j--){
        st.insert(attraction[j]);
        int cnt = 0;
        ll top = 0;
        for(auto u = st.rbegin(); u != st.rend(); u++){
            cnt++;
            top += *u;
            dp1[start - j + cnt][1] = max(dp1[start - j + cnt][1], top);
            dp1[2*(start - j) + cnt][0] = max(dp1[2*(start - j) + cnt][0], top);
        }
    }
    st.clear();
    for(int j = start + 1; j < n; j++){
        st.insert(attraction[j]);
        int cnt = 0;
        ll top = 0;
        for(auto u = st.rbegin(); u != st.rend(); u++){
            cnt++;
            top += *u;
            dp2[j - start + cnt][1] = max(dp2[j - start + cnt][1], top);
            dp2[2*(j - start) + cnt][0] = max(dp2[2*(j - start) + cnt][0], top);
        }
    }
    ll ans = 0;
    for(int i = 0; i <= d; i++){
        ans = max(ans, dp1[i][0] + dp2[d - i][1]);
        ans = max(ans, dp1[d - i][1] + dp2[i][0]);
    }
    return ans;
}

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