제출 #1147912

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147912		adriines06	Holiday (IOI14_holiday)	C++20	47 / 100	5091 ms	6216 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

long long int findMaxAttraction(int n, int s, int d, int attraction[]) {
    vector<ll> v(n);
    for(ll i=0;i<n;i++){
        v[i]=attraction[i];
    }
    if(s==0){
        multiset<ll>ms;
        ll sum=0,ans=0;
        for(int i=0;i<n;i++){
            sum+=v[i];
            ms.insert(v[i]);

            while(ms.size()>0 && ms.size()>d-i){
                sum-=*ms.begin();
                ms.erase(ms.begin());
            }
            ans=max(ans,sum);
        }
        return ans;
    }
    else{
        ll ans=0,dv;
        for(int i=0;i<n;i++){
            multiset<ll>ms;
            ll sum=0;
            for(int j=i;j<n;j++){
                sum+=v[j];
                ms.insert(v[j]);
                if(i<=s && j<=s){
                    dv=abs(s-i);
                }
                else if(i>=s && j>=s){
                    dv=abs(s-j);
                }
                else{
                    dv=2*abs(j-i)-max(abs(s-i),abs(s-j));
                }

                while(ms.size()>max(0ll,(d-dv))){
                    sum-=*ms.begin();
                    ms.erase(ms.begin());
                }
                ans=max(ans,sum);
            }

        }
        return ans;
    }

}

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