Submission #669143

#	Time	Username	Problem	Language	Result	Execution time	Memory
669143		emuyumi	휴가 (IOI14_holiday)	C++17	100 / 100	1629 ms	14940 KiB

holiday

#include <bits/stdc++.h>
#include "holiday.h"
 
using namespace std;
#define ms(x, a) memset(x, a, sizeof x)
typedef long long ll;
const int mod = 1e9 + 7, inf = 0x3f3f3f3f;
const int MN = 1e5;
 
vector<ll> calc(int n, int src, int ld, const vector<ll> &a){
    vector<ll> ret(4 * MN + 1);
    if (src == n - 1) return ret;
    struct Seg{ int dl, dr, r; };
    vector<Seg> q, nxt = {{1, 3 * (n - 1 - src), n - 1}};
// nxt[0] = {7, 7, n - 1};
    priority_queue<ll> off;
    priority_queue<ll, vector<ll>, greater<ll>> on;
    while (!nxt.empty()){
        swap(nxt, q);
// for (auto [dl, dr, r] : q) cout << dl << " " << dr << " " << r << '\n';
// cout << '\n';
        nxt.clear();
        while (!off.empty()) off.pop();
        while (!on.empty()) on.pop();
        int i = src;
        ll cur = 0;
        for (auto [dl, dr, r] : q){
            int d = (dl + dr) >> 1;
            int k = r;
            while (true){
                while (!off.empty() && (i - src) * ld + on.size() < d) cur += off.top(), on.push(off.top()), off.pop();
                while (!on.empty() && (i - src) * ld + on.size() > d) cur -= on.top(), off.push(on.top()), on.pop();
                if (cur > ret[d]) k = i, ret[d] = cur;
// cout << cur << " ";
                if (i == r) break;
                cur += a[++i], on.push(a[i]);
            }
// cout << d << " -> " << ret[d] << '\n';
            if (d != dl) nxt.push_back({dl, d - 1, k});
            if (d != dr) nxt.push_back({d + 1, dr, r});
        }
    }
// cout << "done" << '\n';
    return ret;
}
 
ll solve(int n, int start, int d, vector<ll> a){
    vector<ll> r = calc(n, start, 1, a);
    reverse(a.begin(), a.end()); start = n - start - 1;
    vector<ll> l = calc(n, start, 2, a);
    ll ans = 0;
    for (int i = 0; i <= d; ++i){
        ans = max(ans, l[i] + r[d - i]);
    }
    for (int i = 0; i <= d - 1; ++i){
        ans = max(ans, l[i] + r[(d - 1) - i] + a[start]);
    }
// for (int i = 0; i <= 10; ++i) cout << i << ": " << r[i] << '\n';
    return ans;
}
 
ll findMaxAttraction(int n, int start, int d, int attraction[]){
    vector<ll> vec;
    for (int i = 0; i < n; ++i) vec.push_back(attraction[i]);
    ll ans = solve(n, start, d, vec);
// cout << ans << " ";
    start = n - start - 1;
    reverse(vec.begin(), vec.end());
    ans = max(ans, solve(n, start, d, vec));
// cout << solve(n, start, d, vec) << '\n';
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'std::vector<long long int> calc(int, int, int, const std::vector<long long int>&)':
holiday.cpp:31:67: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |                 while (!off.empty() && (i - src) * ld + on.size() < d) cur += off.top(), on.push(off.top()), off.pop();
      |                                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
holiday.cpp:32:66: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |                 while (!on.empty() && (i - src) * ld + on.size() > d) cur -= on.top(), off.push(on.top()), on.pop();
      |                                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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