Submission #682691

#	Time	Username	Problem	Language	Result	Execution time	Memory
682691		Ronin13	Schools (IZhO13_school)	C++14	100 / 100	318 ms	19680 KiB

school

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax =5e5 + 1;
const ll linf = 1e18 + 1;

ll DP[nmax], dp[nmax];
ll A[nmax], B[nmax];

int main(){
  //  freopen("school.in", "r", stdin);
 // freopen("school.out", "w", stdout);
    int n; cin >> n;
    int m; cin >> m;
    int s; cin >> s;
    for(int i = 1; i <= n; i++)
        cin >> A[i] >> B[i];
    vector <pll> vec;
    for(int i = 1; i <= n; i++){
        vec.pb({B[i] - A[i], i});
    }
    sort(vec.begin(), vec.end());
    multiset <ll> cur;
    for(int i = 0; i < vec.size(); i++){
        int x = vec[i].s;
        if(cur.size() < m)
            DP[i + 1] = DP[i] + A[x], cur.insert(A[x]);
        else{
            DP[i + 1] = DP[i];
            if(cur.empty()) continue;
            if(A[x] < *cur.begin()) continue;
            DP[i + 1] = DP[i] - *cur.begin() + A[x];
            cur.insert(A[x]);
            cur.erase(cur.begin());
        }
    }
    cur.clear();
    for(int i = vec.size() - 1; i >= 0; i--){
        int x = vec[i].s;
        if(cur.size() < s)
            dp[i + 1] = dp[i + 2] + B[x], cur.insert(B[x]);
        else{
            dp[i + 1] = dp[i + 2];
            if(cur.empty()) continue;
            if(B[x] < *cur.begin()) continue;
            dp[i + 1] = dp[i + 2] - *cur.begin() + B[x];
            cur.insert(B[x]);
            cur.erase(cur.begin());
        }
    }
    ll ans = 0;
    for(int i = 0; i <= n; i++)
        ans = max(ans, DP[i] + dp[i + 1]);
    cout << ans;
    return 0;
}

Compilation message (stderr)

school.cpp: In function 'int main()':
school.cpp:31:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i = 0; i < vec.size(); i++){
      |                    ~~^~~~~~~~~~~~
school.cpp:33:23: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |         if(cur.size() < m)
      |            ~~~~~~~~~~~^~~
school.cpp:47:23: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |         if(cur.size() < s)
      |                       ^

• Subtask 1: 100 / 100