제출 #1065695

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1065695		Mr_Husanboy	휴가 (IOI14_holiday)	C++17	47 / 100	5059 ms	5468 KiB

holiday

#include"holiday.h"
#include <vector>
#include <algorithm>
#include <set>
#include <iostream>


using namespace std;

#define ll long long


long long int findMaxAttraction(int n, int start, int d, int a[]){
    if(d == 0){
        return 0;
    }
    if(d == 1){
        return a[start];
    }
    ll ans = 0;
    if(start != 0)
    for(int i = 0; i <= start; i ++){
        multiset<ll> st;
        if(start - i + 1 > d){
            continue;
        }
        ll sum = a[i];
        ans = max(ans, sum);
        int rem = d - (start - i + 1);
        for(int j = i + 1; j < n; j ++){
            rem --;
            if(rem < 0){
                if(st.empty()){
                    break;
                }
                sum -= *st.begin();
                st.erase(st.begin());
                rem ++;
            }
            if(rem > 0){
                rem --;
                st.insert(a[j]); sum += a[j];
            }else{
                if(st.empty()){
                    break;
                }
                if(*st.begin() > a[j]){
                    continue;
                }
                sum -= *st.begin();
                st.erase(st.begin());
                st.insert(a[j]);
                sum += a[j];
            }
            ans = max(ans, sum);
        }
    }

    if(start != 0)
    for(int i = start + 1; i < n; i ++){
        multiset<ll> st;
        if(i - start + 1 > d){
            continue;
        }
        ll sum = a[i];
        ans = max(ans, sum);
        int rem = d - (i - start + 1);
        for(int j = i - 1; j >= 0; j --){
            rem --;
            if(rem < 0){
                if(st.empty()){
                    break;
                }
                sum -= *st.begin();
                st.erase(st.begin());
                rem ++;
            }
            if(rem > 0){
                rem --;
                st.insert(a[j]); sum += a[j];
            }else{
                if(st.empty()){
                    break;
                }
                if(*st.begin() > a[j]){
                    continue;
                }
                sum -= *st.begin();
                st.erase(st.begin());
                st.insert(a[j]);
                sum += a[j];
            }
            ans = max(ans, sum);
        }
    }


{
    ll sum = 0;
    multiset<ll> st;
    int rem = d + 1;
    for(int j = start; j < n; j ++){
        rem --;
        if(rem < 0){
            if(st.empty()){
                break;
            }
            sum -= *st.begin();
            st.erase(st.begin());
            rem ++;
        }
        if(rem > 0){
            rem --;
            st.insert(a[j]); sum += a[j];
        }else{
            if(st.empty()){
                break;
            }
            if(*st.begin() > a[j]){
                continue;
            }
            sum -= *st.begin();
            st.erase(st.begin());
            st.insert(a[j]);
            sum += a[j];
        }
        ans = max(ans, sum);
    }
}
{
    ll sum = 0;
    multiset<ll> st;
    int rem = d + 1;
    for(int j = start; j >= 0; j --){
        rem --;
        if(rem < 0){
            if(st.empty()){
                break;
            }
            sum -= *st.begin();
            st.erase(st.begin());
            rem ++;
        }
        if(rem > 0){
            rem --;
            st.insert(a[j]); sum += a[j];
        }else{
            if(st.empty()){
                break;
            }
            if(*st.begin() > a[j]){
                continue;
            }
            sum -= *st.begin();
            st.erase(st.begin());
            st.insert(a[j]);
            sum += a[j];
        }
        ans = max(ans, sum);
    }
}

    return ans;
}

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