# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
936035 | 12345678 | Schools (IZhO13_school) | C++17 | 2059 ms | 18608 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>
using namespace std;
#define ll long long
const int nx=3e5+5;
int n, m, s;
ll dp[2][nx],res;
vector<int> a, b;
struct value
{
int a, b;
bool operator< (const value &o) const {return (a-b)<(o.a-o.b);}
} d[nx];
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>m>>s;
for (int i=1; i<=n; i++) cin>>d[i].a>>d[i].b;
sort(d+1, d+n+1);
//for (int i=1; i<=n; i++) cout<<"value "<<i<<' '<<d[i].a<<' '<<d[i].b<<'\n';
for (int i=1; i<=n; i++) a.push_back(d[i].a), b.push_back(d[i].b);
multiset<int> ms;
ll sm=0;
for (int i=n-1; i>=0; i--)
{
if (ms.size()<m) ms.insert(a[i]), sm+=a[i];
else if (a[i]>*ms.begin()) sm+=a[i]-*ms.begin(), ms.erase(ms.begin()), ms.insert(a[i]);
dp[0][i]=(ms.size()>=m)?sm:-1e18;
}
ms.clear();
sm=0;
for (int i=0; i<n; i++)
{
if (ms.size()<s) ms.insert(b[i]), sm+=b[i];
else if (b[i]>*ms.begin()) sm+=b[i]-*ms.begin(), ms.erase(ms.begin()), ms.insert(b[i]);
dp[1][i]=(ms.size()>=s)?sm:-1e18;
}
//for (int i=0; i<n; i++) cout<<i<<' '<<dp[0][i]<<' '<<dp[1][i]<<'\n';
if (s==0) return cout<<dp[0][0], 0;
if (m==0) return cout<<dp[1][n-1], 0;
for (int i=0; i<n-1; i++) res=max(res, dp[0][i+1]+dp[1][i]);
cout<<res;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |