Submission #1116952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116952		vladilius	Holiday (IOI14_holiday)	C++17	0 / 100	5040 ms	3400 KiB

holiday

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
#define pb push_back
#define ff first
#define ss second

ll get(vector<int> a, int n, int x, int d){
    auto f = [&](int l, int r){
        int f = d - (x - l) - (r - l);
        vector<int> p;
        for (int i = l; i <= r; i++){
            p.pb(a[i]);
        }
        sort(p.begin(), p.end(), greater<int>());
        ll sum = 0;
        for (int i = 0; i < min(f, (int) p.size()); i++){
            sum += p[i];
        }
        return sum;
    };
    ll out = 0;
    function<void(int, int, int, int)> solve = [&](int l, int r, int l1, int r1){
        if (l > r) return;
        int m = (l + r) / 2;
        pli mx = {-1, 0};
        for (int i = l1; i <= r1; i++){
            mx = max(mx, {f(m, i), -i});
        }
        out = max(out, mx.ff);
        mx.ss = -mx.ss;
        
        solve(l, m - 1, l1, mx.ss);
        solve(m + 1, r, mx.ss, r1);
    };
    solve(1, x, x, n);
    return out;
}

ll findMaxAttraction(int n, int x, int d, int A[]){
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++){
        a[i] = A[i - 1];
    }
    x++;
    ll out = get(a, n, x, d);
    reverse(a.begin() + 1, a.end());
    out = max(out, get(a, n, x, d));
    return out;
}

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