Submission #1290054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290054		vpinx	나일강 (IOI24_nile)	C++20	23 / 100	2095 ms	6932 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;

vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) {
    long long n = w.size(), mx = 0;
    vector<pair<int, int>> v(n);
    for (int i = 0; i < n; i++) {
        v[i] = {w[i], a[i] - b[i]};
        mx += a[i];
    }
    sort(v.begin(), v.end());
    
    auto op = [&](vector<pair<int, int>> &c, int sm) -> long long {
        long long sum = 0;
        for (int i = 0; i < c.size(); i++) sum += c[i].second;
        if ((int)c.size() % 2 == 0) return sum;
        
        long long ans = sum - min(c[0].second, c.back().second);
        for (int i = 1; i < c.size() - 1; i++) {
            if (c[i + 1].first - c[i - 1].first <= sm) ans = max(ans, sum - c[i].second);
        }
        return ans;
    };
    
    int q = e.size();
    vector<long long> ans(q);
    for (int t = 0; t < q; t++) {
        long long val = 0;
        vector<pair<int, int>> cur = {v[0]};
        for (int i = 1; i < n; i++) {
            if (v[i].first - v[i - 1].first > e[t]) {
                val += op(cur, e[t]); 
                cur.clear();
            }
            cur.push_back(v[i]);
        }
        ans[t] = mx - val - op(cur, e[t]);
    }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 0 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18