oj.uz

Submission #936035

# Submission time Handle Problem Language Result Execution time Memory
936035 2024-03-01T03:14:29 Z 12345678 Schools (IZhO13_school) C++17
95 / 100
 2000 ms 18608 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.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

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 2059 ms 2396 KB Time limit exceeded
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 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 4696 KB Output is correct
8 Correct 2 ms 4696 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 2 ms 4908 KB Output is correct
11 Correct 2 ms 4652 KB Output is correct
12 Correct 2 ms 4700 KB Output is correct
13 Correct 14 ms 8824 KB Output is correct
14 Correct 29 ms 9184 KB Output is correct
15 Correct 34 ms 9920 KB Output is correct
16 Correct 83 ms 17564 KB Output is correct
17 Correct 97 ms 16108 KB Output is correct
18 Correct 105 ms 15848 KB Output is correct
19 Correct 117 ms 16960 KB Output is correct
20 Correct 126 ms 18608 KB Output is correct