Submission #256483

#	Time	Username	Problem	Language	Result	Execution time	Memory
256483		PedroBigMan	Holiday (IOI14_holiday)	C++14	47 / 100	5079 ms	7796 KiB

holiday

#include"holiday.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=99824LL;


ll findMaxAttraction(int n, int start_pos, int days, int attraction[]) 
{
    ll N = (ll) n; ll start = (ll) start_pos; ll d = (ll) days; vector<ll> a; REP(i,0,N) {a.pb((ll) attraction[i]);}
    multiset<pl> s; ll ans=0LL;
    for(ll l=start;l>=0;l--)
    {
        ll val=0LL;
        s.clear();
        ll r=2*start-l;
        if(r>=N) {break;}
        ll dl = d - 3*(start-l);
        while(dl>r-l+1) {r++; if(r==N) {r--; break;} dl--;}
        REP(i,l,r+1) {s.insert(mp(a[i],0));}
        ll sum=0LL; multiset<pl>::iterator it=s.end();
        REP(i,0,dl) {it--; sum+=(it->ff); if(it==s.begin()) {break;}} val=sum;
        while(r<N-1)
        {
            r++; dl--; if(dl==0) {break;} s.insert(mp(a[r],it->ss-1));
            if(a[r]>it->ff)
            {
                sum+=a[r]; sum-=(it->ff); it++; sum-=(it->ff); it++;
            }
            else if(a[r]<=it->ff)
            {
                sum-=(it->ff); it++;
            }
            val=max(val,sum);
        }
        ans=max(ans,val);
    }
    s.clear();
    for(ll r=start;r<N;r++)
    {
        ll val=0LL;
        s.clear();
        ll l=2*start-r;
        if(l<0) {break;}
        ll dl = d - 3*(r-start);
        while(dl>r-l+1) {l--; if(l<0) {l++; break;} dl--;}
        REP(i,l,r+1) {s.insert(mp(a[i],0));}
        ll sum=0LL; multiset<pl>::iterator it=s.end();
        REP(i,0,dl) {it--; sum+=(it->ff); if(it==s.begin()) {break;}} val=sum;
        while(l>0)
        {
            l--; dl--; if(dl==0) {break;} s.insert(mp(a[l],it->ss-1));
            if(a[l]>it->ff) 
            {
                sum+=a[l]; sum-=(it->ff); it++; sum-=(it->ff); it++;
            }
            else
            {
                sum-=(it->ff); it++;
            }
            val=max(val,sum);
        }
        ans=max(ans,val);
    }
    return ans;
}

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