oj.uz

답안 #972044

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
972044 2024-04-29T20:11:54 Z sofija6 학교 설립 (IZhO13_school) C++14
100 / 100
 107 ms 21816 KB 
#include <bits/stdc++.h>
#define ll long long
#define MAXN 300010
using namespace std;
ll a[MAXN],b[MAXN],dppref[MAXN],dpsuff[MAXN];
vector<pair<ll,ll> > d;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,m,s;
    cin >> n >> m >> s;
    for (ll i=1;i<=n;i++)
    {
        cin >> a[i] >> b[i];
        d.push_back({a[i]-b[i],i});
    }
    sort(d.begin(),d.end(),greater<pair<ll,ll> >());
    priority_queue<ll,vector<ll>,greater<ll> > q;
    ll sum=0,cur=0;
    for (auto i : d)
    {
        sum+=a[i.second];
        q.push(a[i.second]);
        while (q.size()>m)
        {
            sum-=q.top();
            q.pop();
        }
        if (q.size()==m)
            dppref[cur]=sum;
        cur++;
    }
    while (!q.empty())
        q.pop();
    reverse(d.begin(),d.end());
    sum=0;
    cur=n-1;
    for (auto i : d)
    {
        sum+=b[i.second];
        q.push(b[i.second]);
        while (q.size()>s)
        {
            sum-=q.top();
            q.pop();
        }
        if (q.size()==s)
            dpsuff[cur]=sum;
        cur--;
    }
    ll ans=0;
    for (ll i=m-1;i<n-s;i++)
        ans=max(ans,dppref[i]+dpsuff[i+1]);
    cout << ans;
    return 0;
}

Compilation message

school.cpp: In function 'int main()':
school.cpp:24:24: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   24 |         while (q.size()>m)
      |                ~~~~~~~~^~
school.cpp:29:21: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   29 |         if (q.size()==m)
      |             ~~~~~~~~^~~
school.cpp:42:24: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   42 |         while (q.size()>s)
      |                ~~~~~~~~^~
school.cpp:47:21: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   47 |         if (q.size()==s)
      |             ~~~~~~~~^~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 3 ms 6748 KB Output is correct
10 Correct 3 ms 6748 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 2 ms 6748 KB Output is correct
13 Correct 13 ms 10200 KB Output is correct
14 Correct 25 ms 11152 KB Output is correct
15 Correct 45 ms 14024 KB Output is correct
16 Correct 60 ms 15056 KB Output is correct
17 Correct 84 ms 17352 KB Output is correct
18 Correct 88 ms 17856 KB Output is correct
19 Correct 97 ms 18212 KB Output is correct
20 Correct 107 ms 21816 KB Output is correct