제출 #70219

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70219		zubec	휴가 (IOI14_holiday)	C++14	47 / 100	5083 ms	3996 KiB

holiday

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

const int N = 100100;

int n, a[N], suff[N];

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    ::n = n;
    for (int i = 1; i <= n; i++)
        a[i] = attraction[i-1];
    ++start;
    if (start == 1){
        ll ans = 0;
        set<pair<int, int> > q;
        int curd = 0;
        ll sum = 0;
        for (int i = 1; i <= n; i++){
            ++curd;
            auto it = q.lower_bound({a[i], 0});
            if (it == q.end() || it->first != a[i]){
                q.insert({a[i], 1});
            } else {
                int cnt = it->second;
                q.erase(it);
                q.insert({a[i], cnt+1});
            }
            sum += a[i];
            while(!q.empty() && curd > d){
                int num = q.begin()->first;
                sum -= num;
                auto it = q.lower_bound({num, 0});
                int cnt = it->second;
                q.erase(it);
                --cnt;
                if (cnt > 0)
                    q.insert({num, cnt});
                --curd;
            }
            if (curd <= d){
                ans = max(ans, sum);
            }
            ++curd;
        }

        return ans;
    }
    ll ans = 0;
    set<pair<int, int> > qq;
    int curdd = 0;
    ll summ = 0;
    for (int i = start; i >= 1; i--){
        if (i < start){
            ++curdd;
            ++curdd;
            summ += a[i];
            auto it = qq.lower_bound({a[i], 0});
            if (it == qq.end() || it->first != a[i]){
                qq.insert({a[i], 1});
            } else {
                int cnt = it->second;
                qq.erase(it);
                qq.insert({a[i], cnt+1});
            }
        }
        set<pair<int, int> > q = qq;
        int curd = curdd;
        ll sum = summ;
        curd += abs(i-start);
        for (int j = start; j <= n; j++){
            ++curd;
            sum += a[j];
            auto it = q.lower_bound({a[j], 0});
            if (it == q.end() || it->first != a[j]){
                q.insert({a[j], 1});
            } else {
                int cnt = it->second;
                q.erase(it);
                q.insert({a[j], cnt+1});
            }

            while(!q.empty() && curd > d){
                int num = q.begin()->first;
                sum -= num;
                auto it = q.lower_bound({num, 0});
                int cnt = it->second;
                q.erase(it);
                --cnt;
                if (cnt > 0)
                    q.insert({num, cnt});
                --curd;
            }
            //cout << i << ' ' << j << ' ' << curd << ' ' << sum << endl;
            if (curd <= d){
                ans = max(ans, sum);
            }
            ++curd;
        }
    }

    reverse(a+1, a+n+1);
    start = n-start+1;

    qq.clear();
    curdd = 0;
    summ = 0;
    for (int i = start; i >= 1; i--){
        if (i < start){
            ++curdd;
            ++curdd;
            summ += a[i];
            auto it = qq.lower_bound({a[i], 0});
            if (it == qq.end() || it->first != a[i]){
                qq.insert({a[i], 1});
            } else {
                int cnt = it->second;
                qq.erase(it);
                qq.insert({a[i], cnt+1});
            }
        }
        set<pair<int, int> > q = qq;
        int curd = curdd;
        ll sum = summ;
        curd += abs(i-start);
        for (int j = start; j <= n; j++){
            ++curd;
            sum += a[j];
            auto it = q.lower_bound({a[j], 0});
            if (it == q.end() || it->first != a[j]){
                q.insert({a[j], 1});
            } else {
                int cnt = it->second;
                q.erase(it);
                q.insert({a[j], cnt+1});
            }

            while(!q.empty() && curd > d){
                int num = q.begin()->first;
                sum -= num;
                auto it = q.lower_bound({num, 0});
                int cnt = it->second;
                q.erase(it);
                --cnt;
                if (cnt > 0)
                    q.insert({num, cnt});
                --curd;
            }
            //cout << i << ' ' << j << ' ' << curd << ' ' << sum << endl;
            if (curd <= d){
                ans = max(ans, sum);
            }
            ++curd;
        }
    }

    return ans;

}

컴파일 시 표준 에러 (stderr) 메시지

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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