Submission #585019

#	Time	Username	Problem	Language	Result	Execution time	Memory
585019		Mazaalai	Holiday (IOI14_holiday)	C++17	24 / 100	573 ms	65536 KiB

holiday

#include <bits/stdc++.h>
#include"holiday.h"
#define ALL(x) x.begin(),x.end()
#define LLA(x) x.rbegin(),x.rend()
#define pb push_back
using namespace std;
using PII = pair <int, int>;
using ll = long long;
const int N = 3001;
const int D = 6000;
const int D1 = 7500;
ll dp[2][N][D+1];
ll dp1[2][D1+1];
long long int findMaxAttraction(int n, int st, int d, int nums[]) {
    ll ans = 0;
    // return 0;
 
    {
        for (int i = st; i >= 0; i--) {
            multiset <int> vals;
            ll sum = 0;
            int a = st - i;
            for (int j = i; j <= st; j++) {
                vals.insert(nums[j]);
                sum += nums[j];
            }
            for (int j = vals.size(); j > 0; j--) {
 
                if (a+j <= d) {
                    ans = max(ans, sum);
                    dp[0][i][a+j] = sum;
                    dp1[0][a+j] = max(dp1[0][a+j], sum);
                }
                sum -= *vals.begin();
                vals.erase(vals.begin());
            }
        }
        for (int i = st+1; i < n; i++) {
            multiset <int> vals;
            ll sum = 0;
            int b = i - st;
            for (int j = st+1; j <= i; j++) {
                vals.insert(nums[j]);
                sum += nums[j];
            }
            for (int j = vals.size(); j > 0; j--) {
                if (j+b <= d) {
                    ans = max(ans, sum);
                    dp[1][i][j+b] = sum;
                    dp1[1][j+b] = max(dp1[1][j+b], sum);
                }
                sum -= *vals.begin();
                vals.erase(vals.begin());
            }
        }
    }
    for (int i = 1; i <= d; i++) {
        dp1[0][i]=max(dp1[0][i], dp1[0][i-1]);
        dp1[1][i]=max(dp1[1][i], dp1[1][i-1]);
    }
    for (int i = 0; i <= st; i++) 
    for (int j = 0; j <= d; j++) {
        if (d-j-st+i >= 0){
            // if (dp[0][i][j] + dp1[1][d-j-st+i] == 72) {
            //     cout << "00 " << i << " " << j << "\n";
            //     cout << "01 " << d-j-st+i << "\n";
            //     cout << "02 " << dp[0][i][j] << ' ' << dp1[1][d-j-st+i] << "\n";
            // }
            ans = max(ans, dp[0][i][j] + dp1[1][min(D, d-j-st+i)]);
        }
    }
 
    for (int i = st; i < n; i++) 
    for (int j = 0; j <= d; j++) {
        if (d-j-i+st >= 0) {
 
            // if (dp[1][i][j] + dp1[0][d-j-i+st] == 72) {
            //     cout << "10 " << i << " " << j << "\n";
            //     cout << "11 " << d-j-i+st<< "\n";
            //     cout << "12 " << dp[1][i][j] << ' ' << dp1[0][d-j-i+st] << "\n";
            // }
            ans = max(ans, dp[1][i][j] + dp1[0][min(D, d-j-i+st)]);
        }
    }
        
    
    return ans;
}

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