oj.uz

Submission #936039

# Submission time Handle Problem Language Result Execution time Memory
936039 2024-03-01T03:22:13 Z 12345678 Schools (IZhO13_school) C++17
100 / 100
 124 ms 15548 KB 
#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 (!ms.empty()&&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 (!ms.empty()&&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

school.cpp: In function 'int main()':
school.cpp:30:22: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |         if (ms.size()<m) ms.insert(a[i]), sm+=a[i];
      |             ~~~~~~~~~^~
school.cpp:32:28: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |         dp[0][i]=(ms.size()>=m)?sm:-1e18;
      |                   ~~~~~~~~~^~~
school.cpp:38:22: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |         if (ms.size()<s) ms.insert(b[i]), sm+=b[i];
      |             ~~~~~~~~~^~
school.cpp:40:28: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |         dp[1][i]=(ms.size()>=s)?sm:-1e18;
      |                   ~~~~~~~~~^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 3 ms 4700 KB Output is correct
8 Correct 3 ms 4700 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 2 ms 4700 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 2 ms 4700 KB Output is correct
13 Correct 13 ms 8408 KB Output is correct
14 Correct 23 ms 8392 KB Output is correct
15 Correct 32 ms 8136 KB Output is correct
16 Correct 81 ms 15548 KB Output is correct
17 Correct 113 ms 13796 KB Output is correct
18 Correct 96 ms 13036 KB Output is correct
19 Correct 108 ms 13916 KB Output is correct
20 Correct 124 ms 15048 KB Output is correct