oj.uz

Submission #441213

# Submission time Handle Problem Language Result Execution time Memory
441213 2021-07-04T16:38:31 Z parsabahrami Schools (IZhO13_school) C++17
100 / 100
 312 ms 19064 KB 
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 3e5 + 10, MOD = 1e9 + 7;
int A[N], B[N], ord[N], M[N], m, s, n; set<pii, greater<pii>> st1, st2;

int main() {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= n; i++) 
        scanf("%d%d", &A[i], &B[i]); 
    /* for (int i = 1; i <= n; i++) 
        scanf("%d", &A[i]);
    for (int i = 1; i <= n; i++) 
        scanf("%d", &B[i]);*/ 
    iota(ord + 1, ord + n + 1, 1);
    sort(ord + 1, ord + n + 1, [&] (int a, int b) { return A[a] > A[b]; });
    ll sum = 0;
    for (int i = 1; i <= m; i++) {
        st1.insert({B[ord[i]] - A[ord[i]], ord[i]}); 
        M[ord[i]] = 1;
        sum += A[ord[i]];
    }
    for (int i = m + 1; i <= n; i++) 
        st2.insert({B[ord[i]], ord[i]});
    int ptr = m + 1;
    for (int i = 1; i <= s; i++) {
        while (ptr <= n && M[ord[ptr]]) ptr++;
        int c1 = (SZ(st1) ? st1.begin()->F + A[ord[ptr]] : -MOD),
            c2 = (SZ(st2) ? st2.begin()->F : -MOD);
        if (c2 > c1) {
            //printf("1 %d ", st2.begin()->S);
            M[st2.begin()->S] = 1, sum += c2;
            st2.erase(st2.begin());
        } else {
            M[st1.begin()->S] = 1, sum += c1;
            st1.erase(st1.begin());
            st1.insert({B[ord[ptr]] - A[ord[ptr]], ord[ptr]}); M[ord[ptr]] = 1;
            st2.erase({B[ord[ptr]], ord[ptr]});
        }
        //printf("%lld\n", sum);
    }
    printf("%lld\n", sum);
    return 0;
}

Compilation message

school.cpp: In function 'int main()':
school.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%d%d%d", &n, &m, &s);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
school.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf("%d%d", &A[i], &B[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 4 ms 588 KB Output is correct
11 Correct 3 ms 588 KB Output is correct
12 Correct 3 ms 588 KB Output is correct
13 Correct 28 ms 2468 KB Output is correct
14 Correct 55 ms 5096 KB Output is correct
15 Correct 133 ms 10148 KB Output is correct
16 Correct 175 ms 11496 KB Output is correct
17 Correct 223 ms 13984 KB Output is correct
18 Correct 216 ms 15344 KB Output is correct
19 Correct 257 ms 16448 KB Output is correct
20 Correct 312 ms 19064 KB Output is correct