oj.uz

Submission #936037

# Submission time Handle Problem Language Result Execution time Memory
936037 2024-03-01T03:18:30 Z 12345678 Schools (IZhO13_school) C++17
95 / 100
 2000 ms 15552 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 (a[i]>*ms.begin()) sm+=a[i]-*ms.begin(), ms.erase(ms.find(*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.find(*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
95.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Execution timed out 2094 ms 2396 KB Time limit exceeded
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 3 ms 4700 KB Output is correct
10 Correct 3 ms 4700 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 3 ms 4700 KB Output is correct
13 Correct 14 ms 8408 KB Output is correct
14 Correct 24 ms 8180 KB Output is correct
15 Correct 33 ms 8124 KB Output is correct
16 Correct 81 ms 15552 KB Output is correct
17 Correct 97 ms 13536 KB Output is correct
18 Correct 100 ms 13032 KB Output is correct
19 Correct 111 ms 13756 KB Output is correct
20 Correct 136 ms 15144 KB Output is correct