Submission #582384

#	Time	Username	Problem	Language	Result	Execution time	Memory
582384		wdjpng	Holiday (IOI14_holiday)	C++17	7 / 100	33 ms	1620 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>

#define int long long
#define rep(i,n) for(int i = 0; i < ((int) n); i++)
#define all(a) a.begin(), a.end()

using namespace std;

int brute(int n, int start, int d, vector<int>x)
{
    int maxx=0;
    rep(i,n)
    {
        for(int j = i; j < n; j++)
        {
            priority_queue<int>pq;
            for(int k = i; k <= j; k++)
            {
                pq.push(x[k]);
            }
            int sum = 0;
            rep(b,(d-min(abs(start-i),abs(j-start))-abs(i-j))) if(pq.size()){sum+=pq.top(); pq.pop();}
            maxx=max(sum,maxx);
        }
    }
    return maxx;
}
int findMaxAttraction(signed n, signed start, signed d, signed attraction[]) {
    vector<int>x(n);
    rep(i,n) x[i] = attraction[i];
    if(n<=20) return brute(n,start,d,x);
    
    int dorg=d;
    int maxx = 0;
    for(int mat = 0; mat <= 100; mat++){
        int sum = 0;
        int i = 0;
        while(i<n&&d>=1)
        {
            if(x[i]>=mat) {
                sum+=x[i];
                d--;
            }
            d--;
            i++;
        }
        d=dorg;
        maxx=max(maxx,sum);
    }

    // assert(maxx==brute(n,start,dorg,x));

    return maxx;
}

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