Submission #585144

#	Time	Username	Problem	Language	Result	Execution time	Memory
585144		wdjpng	Holiday (IOI14_holiday)	C++17	47 / 100	370 ms	4916 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 brute2(int n, int start, int d, vector<int>x)
{
    int maxx = 0;

    rep(cs,n) 
    {
        if(n>3000&&cs) break;
        int sum = 0;
        priority_queue<int, vector<int>, greater<int>>pq;
        for(int i = cs; i < n; i++)
        {
            sum+=x[i];
            pq.push(x[i]);
            int mamds=d-abs(cs-start)-abs(i-cs);
            while (pq.size()&&((int)pq.size())>d-abs(cs-start)-abs(i-cs)) {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 maxx = brute2(n,start,d,x);
    reverse(all(x));
    return max(maxx, brute2(n,n-start-1,d,x));
}

Compilation message (stderr)

holiday.cpp: In function 'long long int brute2(long long int, long long int, long long int, std::vector<long long int>)':
holiday.cpp:43:17: warning: unused variable 'mamds' [-Wunused-variable]
   43 |             int mamds=d-abs(cs-start)-abs(i-cs);
      |                 ^~~~~

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