Submission #1327011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1327011		puidiz	학교 설립 (IZhO13_school)	C++20	95 / 100	61 ms	8340 KiB

school

#include <bits/stdc++.h>
#define el cout << '\n'
#define fi first
#define se second
#define ll long long
#define pb push_back
#define num(_a) (_a-'0')
#define sz(__v) (int)(__v).size()
using namespace std;
template <typename T>
void debug_out(const T& value) {
    cerr << value << endl;
}
template <typename T, typename... Args>
void debug_out(const T& first, const Args&... args) {
    cerr << first << ", ";
    debug_out(args...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
const int mod = (int)1e9 + 7;
template<class T> bool minimize(T& cur, const T& val) { return val < cur ? cur = val, 1 : 0; }
template<class T> bool maximize(T& cur, const T& val) { return val > cur ? cur = val, 1 : 0; }
using namespace std;
const int maxn = (long long)1e6;
pair<int,int> x[maxn + 5];
ll pre[maxn + 5];
ll suf[maxn + 5];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, m, s;
    cin >> n >> m >> s;
    for(int i = 1; i <= n; i++){
        cin >> x[i].fi >> x[i].se;
    }
    sort(x + 1, x + n + 1, [&](pair<int,int> &a, pair<int,int> &b){
        int da = a.fi - a.se;
        int db = b.fi - b.se;
        return da < db;
        });
//    for(int i = 1; i <= n; i++){
//        debug(x[i].fi,x[i].se,x[i].fi - x[i].se);
//    }
    priority_queue<int, vector<int>, greater<int>> q;
    ll sumb = 0;
       for(int i = 1; i <= n; i++){
        if(i <= s){
            sumb += x[i].se;
             q.push(x[i].se);
             pre[i] = sumb;
             continue;
        }
        if(q.size() == s && x[i].se > q.top()){
            sumb -= q.top();
            q.pop();
            q.push(x[i].se);
            sumb += x[i].se;
        }
        pre[i] = sumb;
     }
     priority_queue<int, vector<int>, greater<int>> p;
    ll suma = 0;
       for(int i = n; i >= 1; i--){
        if(n - i + 1 <= m){
            suma += x[i].fi;
             p.push(x[i].fi);
             suf[i] = suma;
             continue;
        }
        if(p.size() == m && x[i].fi > p.top()){
            suma -= p.top();
            p.pop();
            p.push(x[i].fi);
            suma += x[i].fi;
        }
        suf[i] = suma;
      }
     ll ans = -1;
     for(int i = 0; i <= n; i++){
        ans = max(ans, pre[i] + suf[i + 1]);
     }
     cout << ans;
}

• Subtask 1: 95 / 100