Submission #669103

#	Time	Username	Problem	Language	Result	Execution time	Memory
669103		emuyumi	Holiday (IOI14_holiday)	C++17	Compilation error	0 ms	0 KiB

holiday

#include <bits/stdc++.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 = 2e5;

vector<ll> calc(int n, int src, int ld, const vector<ll> &a){
    vector<ll> ret(3 * n + 10);
    if (src == n - 1) return ret;
    struct Seg{ int dl, dr, r; };
    vector<Seg> q, nxt = {{1, 3 * (n - 1 - src), n - 1}};
    priority_queue<ll> off;
    priority_queue<ll, vector<ll>, greater<ll>> on;
    while (!nxt.empty()){
        swap(nxt, q);
        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;
                if (i == r) break;
                cur += a[++i], on.push(a[i]);
            }
            if (d != dl) nxt.push_back({dl, d - 1, k});
            if (d != dr) nxt.push_back({d + 1, dr, r});
        }
    }
    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]);
    }
    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);
    start = n - start - 1;
    reverse(vec.begin(), vec.end());
    ans = max(ans, solve(n, start, d, vec));
    return ans;
}

int attraction[MN];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n;
    int start; cin >> start;
    int d; cin >> d;
assert(d <= n * 2 + n / 2);
    for (int i = 0; i < n; ++i) cin >> attraction[i];
    cout << findMaxAttraction(n, start, d, attraction) << '\n';
}

Compilation message (stderr)

holiday.cpp: In function 'std::vector<long long int> calc(int, int, int, const std::vector<long long int>&)':
holiday.cpp:27: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]
   27 |                 while (!off.empty() && (i - src) * ld + on.size() < d) cur += off.top(), on.push(off.top()), off.pop();
      |                                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
holiday.cpp:28: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]
   28 |                 while (!on.empty() && (i - src) * ld + on.size() > d) cur -= on.top(), off.push(on.top()), on.pop();
      |                                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/bin/ld: /tmp/cc74CLIk.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc68LIAj.o:holiday.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status