Submission #1149842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149842		onbert	Cake 3 (JOI19_cake3)	C++20	0 / 100	1 ms	328 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5, INF = 1e10;
int n, m;
pair<int,int> a[maxn];

bool cmp(pair<int,int> a, pair<int,int> b) {
    if (a.second != b.second) return a.second < b.second;
    return a.first < b.first;
}

int cal(vector<pair<int,int>> vec) {
    sort(vec.begin(), vec.end(), cmp);
    int sz = vec.size();
    // cout << sz << endl;
    for (int i=1;i<sz;i++) vec[i].first += vec[i-1].first;
    int ans = 0;
    for (int r = m-1; r < sz; r++) {
        int l = r - m + 1;
        int curans = vec[r].first;
        if (l > 0) curans -= vec[l-1].first;
        curans -= (vec[r].second - vec[l].second) * 2;
        // cout << sz << " " << r << " " << curans << endl;
        ans = max(curans, ans);
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i=1;i<=n;i++) cin >> a[i].first >> a[i].second;
    sort(a+1, a+n+1);
    reverse(a+1, a+n+1);
    vector<pair<int,int>> vec;
    int ans = 0;
    for (int i=1;i<=n;i++) {
        vec.push_back(a[i]);
        if (i >= m) ans = max(cal(vec), ans);
    }
    cout << ans << "\n";
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 19
• Subtask 3: 0 / 76