Submission #585024

#	Time	Username	Problem	Language	Result	Execution time	Memory
585024		Mazaalai	Holiday (IOI14_holiday)	C++17	47 / 100	570 ms	48504 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;
    if (st == 0) {
        ll ans = 0;
        for (int i = st; i >= 0; i--) {
            int l = st - i;
            multiset <int> vals;
            ll sum = 0;
            for (int p = i; p <= st; p++) {
                vals.insert(nums[p]);
                sum += nums[p];
            }
            for (int j = st+1; j < n; j++) {
                int r = j - st;
                int move = l + r + min(l, r);
                int need = d - move;
                if (need <= 0) break;
                vals.insert(nums[j]);
                sum += nums[j];
                while(need < vals.size()) {
                    sum -= *vals.begin();
                    vals.erase(vals.begin());
                }
                ans = max(ans, sum);
            }
        }
        return ans;
    }
    {
        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){
            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) {
            ans = max(ans, dp[1][i][j] + dp1[0][min(D, d-j-i+st)]);
        }
    }
        
    
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:33:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |                 while(need < vals.size()) {
      |                       ~~~~~^~~~~~~~~~~~~

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