oj.uz

Submission #671019

# Submission time Handle Problem Language Result Execution time Memory
671019 2022-12-11T17:05:11 Z Do_you_copy Schools (IZhO13_school) C++17
100 / 100
 101 ms 7380 KB 
/*
    I find it wholesome to be alone the greater part of the time.
    To be in company, even with the best, is soon wearisome and dissipating.
    I love to be alone.
    I never found the companion that was so companionable as solitude.
*/
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define faster ios_base::sync_with_stdio(0); cin.tie(0);

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 3e5 + 10;
//const int Mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, m, k;
pii a[maxN];
bool visited[maxN];
void Init(){
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i){
        cin >> a[i].fi >> a[i].se;
    }
    ll ans = 0;
    sort(a + 1, a + n + 1, greater <pii>());
    priority_queue <int> PQ;
    priority_queue <pii> PQ1, PQ2;
    PQ.push(-inf);
    for (int i = 1; i <= m; ++i){
        ans += a[i].fi;
        PQ.push(a[i].se - a[i].fi);
        visited[i] = 1;
    }
    for (int i = m + 1; i <= n; ++i){
        PQ1.push({a[i].se, i});
        PQ2.push({a[i].fi, i});
    }
    for (int i = 1; i <= k; ++i){
        while (!PQ1.empty() && visited[PQ1.top().se]) PQ1.pop();
        while (!PQ2.empty() && visited[PQ2.top().se]) PQ2.pop();
        auto u = PQ.top() + PQ2.top().fi;
        auto v = PQ1.top();
        if (u >= v.fi){
            ans += u;
            PQ.pop();
            int j = PQ2.top().se;
            visited[j] = 1;
            PQ.push(a[j].se - a[j].fi);
            PQ2.pop();
        }
        else{
            ans += v.fi;
            visited[v.se] = 1;
            PQ1.pop();
        }
    }
    cout << ans;
}

#define debug
#define taskname "test"
signed main(){
    faster
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    int tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
    if (fopen("timeout.txt", "r")){
        ofstream timeout("timeout.txt");
        timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000);
        timeout.close();
        #ifndef debug
        cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n";
        #endif // debug
    }
}

Compilation message

school.cpp: In function 'void Init()':
school.cpp:33:13: warning: overflow in conversion from 'long long int' to 'std::priority_queue<int>::value_type' {aka 'int'} changes value from '-4557430888798830399' to '-1061109567' [-Woverflow]
   33 |     PQ.push(-inf);
      |             ^~~~
school.cpp: In function 'int main()':
school.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
school.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 10 ms 852 KB Output is correct
14 Correct 25 ms 2708 KB Output is correct
15 Correct 54 ms 4868 KB Output is correct
16 Correct 85 ms 5196 KB Output is correct
17 Correct 83 ms 6376 KB Output is correct
18 Correct 74 ms 6528 KB Output is correct
19 Correct 83 ms 6696 KB Output is correct
20 Correct 101 ms 7380 KB Output is correct