Submission #1033250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033250		vjudge1	Holiday (IOI14_holiday)	C++17	47 / 100	5069 ms	35008 KiB

holiday

#include"holiday.h"

#include<bits/stdc++.h>
using namespace std;

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    if(start==0){
        int64_t ans=0,cur=0;
        multiset<int>tovis;
        for(int i=0;i<n;i++){
            cur+=attraction[i];
            tovis.insert(attraction[i]);
            while(d-i<tovis.size()){
                cur-=*tovis.begin();
                tovis.erase(tovis.begin());
            }
            ans=max(ans,cur);
        }
        return ans;
    }
    int64_t l[10*n],r[10*n],ll[10*n],rr[10*n];
    memset(l,0,sizeof(l));
    memset(ll,0,sizeof(l));
    memset(r,0,sizeof(l));
    memset(rr,0,sizeof(l));
    multiset<int,greater<int>>tovis;
    for(int i=start+1;i<n;i++){
        tovis.insert(attraction[i]);
        int cnt=0;
        int64_t cur=0;
        for(int j:tovis){
            cnt++;
            cur+=j;
            r[i-start+cnt]=max(r[i-start+cnt],cur);
            rr[(i-start)*2+cnt]=max(rr[(i-start)*2+cnt],cur);
        }
    }
    tovis.clear();
    for(int i=start-1;0<=i;i--){
        tovis.insert(attraction[i]);
        int cnt=0;
        int64_t cur=0;
        for(int j:tovis){
            cnt++;
            cur+=j;
            l[start-i+cnt]=max(l[start-i+cnt],cur);
            ll[(start-i)*2+cnt]=max(ll[(start-i)*2+cnt],cur);
        }
    }
    int64_t ans=max({l[d],r[d],l[d-1]+attraction[start],r[d-1]+attraction[start]});
    for(int i=0;i<d;i++){
        ans=max({ans,l[i]+rr[d-i],ll[i]+r[d-i]});
        if(i)ans=max({ans,l[i-1]+rr[d-i]+attraction[start],ll[i-1]+r[d-i]+attraction[start]});
    }
    return ans;
}

Compilation message (stderr)

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

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