oj.uz

Submission #42935

# Submission time Handle Problem Language Result Execution time Memory
42935 2018-03-06T10:58:23 Z Extazy Schools (IZhO13_school) C++14
100 / 100
 478 ms 34524 KB 
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 300007;

int n,m,s;
pair < int, int > a[N];
long long curr,ans;

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

struct cmpm {
    bool operator () (const int &x, const int &y) const {
        return a[x].second-a[x].first==a[y].second-a[y].first ? x<y : a[x].second-a[x].first>a[y].second-a[y].first;
    }
};

struct cmps {
    bool operator () (const int &x, const int &y) const {
        return a[x].second==a[y].second ? x<y : a[x].second<a[y].second;
    }
};

set < int, cmpm > setm;
set < int, cmps > sets;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int i;

    scanf("%d %d %d", &n, &m, &s);
    for(i=1;i<=n;i++) {
        scanf("%d %d", &a[i].first, &a[i].second);
    }
    sort(a+1,a+1+n);
   
    for(i=n;i>=n-m+1;i--) {
        setm.insert(i);
        curr+=a[i].first;
    }

    for(i=1;i<n-m+1;i++) {
        sets.insert(i);
        curr+=a[i].second;
    }

    while((int)sets.size()>s) {
        curr-=a[*sets.begin()].second;
        sets.erase(sets.begin());
    }

    ans=curr;

    for(i=n-m;i>=1;i--) {
        if(sets.find(i)!=sets.end()) {
            curr-=a[i].second;
            sets.erase(i);
        }
        setm.insert(i);
        curr+=a[i].first;

        while((int)setm.size()>m) {
            curr-=a[*setm.begin()].first;
            curr+=a[*setm.begin()].second;
            sets.insert(*setm.begin());
            setm.erase(setm.begin());
        }

        while((int)sets.size()>s) {
            curr-=a[*sets.begin()].second;
            sets.erase(sets.begin());
        }

        ans=max(ans,curr);
    }

    printf("%lld\n", ans);
    
    return 0;
}

Compilation message

school.cpp: In function 'int main()':
school.cpp:36:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &s);
                                  ^
school.cpp:38:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a[i].first, &a[i].second);
                                                  ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 1 ms 412 KB Output is correct
4 Correct 2 ms 416 KB Output is correct
5 Correct 1 ms 508 KB Output is correct
6 Correct 2 ms 528 KB Output is correct
7 Correct 5 ms 788 KB Output is correct
8 Correct 4 ms 840 KB Output is correct
9 Correct 4 ms 908 KB Output is correct
10 Correct 5 ms 1104 KB Output is correct
11 Correct 6 ms 1204 KB Output is correct
12 Correct 6 ms 1256 KB Output is correct
13 Correct 35 ms 3356 KB Output is correct
14 Correct 111 ms 6572 KB Output is correct
15 Correct 212 ms 12736 KB Output is correct
16 Correct 444 ms 16000 KB Output is correct
17 Correct 355 ms 20536 KB Output is correct
18 Correct 345 ms 24660 KB Output is correct
19 Correct 390 ms 28880 KB Output is correct
20 Correct 478 ms 34524 KB Output is correct