# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
682687 | Ronin13 | Schools (IZhO13_school) | C++14 | 1 ms | 212 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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(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(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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |