Submission #446003

#	Time	Username	Problem	Language	Result	Execution time	Memory
446003		Aryan_Raina	Schools (IZhO13_school)	C++17	100 / 100	130 ms	12116 KiB

school

#include <bits/stdc++.h>
using namespace std;
 
#define int int64_t
#define ld long double
#define ar array
#define all(a) a.begin(), a.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 1e15;
const int MOD = 1e9+7;

void solve() {
    int N, M, S; cin >> N >> M >> S;
    vector<ar<int,2>> shit(N);
    for (ar<int,2> &i : shit) cin >> i[0] >> i[1];

    sort(shit.begin(), shit.end(), [&](ar<int,2> x, ar<int,2> y) {
        return x[0] - x[1] > y[0] - y[1];
    });

    vector<int> ansA(N,0), ansB(N,0);

    priority_queue<int> pq;
    pq.push(-(ansA[0] = shit[0][0]));
    if (pq.size() > M) {
        ansA[0] += pq.top(); pq.pop();
    }
    for (int i = 1; i < N; i++) {
        ansA[i] = ansA[i-1] + shit[i][0];
        pq.push(-shit[i][0]);
        if (pq.size() > M) {
            ansA[i] += pq.top(); pq.pop();
        }
    }

    priority_queue<int>().swap(pq);
    pq.push(-(ansB[N-1] = shit[N-1][1]));
    if (pq.size() > S) {
        ansB[N-1] += pq.top(); pq.pop();
    }
    for (int i = N-2; i >= 0; i--) {
        ansB[i] = ansB[i+1] + shit[i][1];
        pq.push(-shit[i][1]);
        if (pq.size() > S) {
            ansB[i] += pq.top(); pq.pop();
        }
    }

    int ans = max(ansB[0], ansA[N-1]);
    for (int i = 0; i < N-1; i++)
        ans = max(ans, ansA[i] + ansB[i+1]);

    cout << ans << '\n';
} 
 
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0); 
 
    int t = 1; //cin >> t;
    while (t--) solve();   
}  

Compilation message (stderr)

school.cpp: In function 'void solve()':
school.cpp:26:19: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
   26 |     if (pq.size() > M) {
      |         ~~~~~~~~~~^~~
school.cpp:32:23: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
   32 |         if (pq.size() > M) {
      |             ~~~~~~~~~~^~~
school.cpp:39:19: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
   39 |     if (pq.size() > S) {
      |         ~~~~~~~~~~^~~
school.cpp:45:23: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
   45 |         if (pq.size() > S) {
      |             ~~~~~~~~~~^~~

• Subtask 1: 100 / 100