oj.uz

Submission #482992

# Submission time Handle Problem Language Result Execution time Memory
482992 2021-10-27T09:59:30 Z deuslovelt Schools (IZhO13_school) C++17
95 / 100
 103 ms 14188 KB 
//================code===================//


#include <bits/stdc++.h>

#define ci(t) cin>>t
#define co(t) cout<<t
#define LL long long
#define ld long double
#define fa(i,a,b) for(int i=a;i<b;++i)
#define fd(i,a,b) for(int i=a;i>b;--i)
#define setp tuple<LL,LL,LL>
#define setl pair<LL,LL>
#define seti pair<int,int>
#define VL vector<LL>
#define VI vector<int>
#define eps 0.000000001
#define LLL __int128_t

using namespace std;


LL gcd(LL a, LL b)
{
    if (!(a && b)) return max(a, b);
    return a % b ? gcd(b, a % b) : b;
}

#ifdef OHSOLUTION
#define ce(t) cerr << t
#define AT cout << "\n=================ANS=================\n"
#define AE cout << "\n=====================================\n"
#define DB(a) cout << __LINE__ << ": " << #a << " = " << (a) << endl;
#else
#define AT
#define AE
#define ce(t)
#define DB(a)
#endif

pair <int, int> vu[9] = { {-1,0},{0,-1},{1,0} ,{0,1},{1,1}, {1,-1} , {-1,1},{-1,-1},{0,0} }; //RDLU EWSN
//mt19937 rng((unsigned int)chrono::steady_clock::now().time_since_epoch().count());


template<typename T, typename U> void ckmax(T& a, U b) { a = a < b ? b : a; }
template<typename T, typename U> void ckmin(T& a, U b) { a = a > b ? b : a; }
struct gcmp { bool operator()(LL a, LL b) { return a < b; } bool operator()(setl& a, setl& b) { return a.second < b.second; } };
struct lcmp { bool operator()(LL a, LL b) { return a > b; } bool operator()(setl& a, setl& b) { return a.second > b.second; } };

const int max_v = 3e5 + 7;
const int max_k = 5e1 + 7;
const int bsz = 27;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const LL mod = 20070713;//1e9 + 7;// 998244353;// 
template<typename T, typename U> void MOD(T& a, U b) { a += b; if (a < 0) a += mod; if (a >= mod) a -= mod; };

LL dp[max_v][2];

int main()
{
#ifdef OHSOLUTION
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    int n, a, b; ci(n >> a >> b);

    vector<setl> vi(n);
    for (auto& x : vi) ci(x.first >> x.second);

    sort(vi.begin(), vi.end(), [&](setl& a, setl& b) {return a.first - a.second > b.first - b.second; });

    priority_queue<LL, vector<LL>, lcmp> pq;

    LL t = 0;
    fa(i, 0, n)
    {
        t += vi[i].first; pq.push({ vi[i].first });
        if (pq.size() > a) t -= pq.top(), pq.pop();
        dp[i][0] = t;
    }

    while (pq.size()) pq.pop();
    t = 0;
    fd(i, n - 1, -1)
    {
        t += vi[i].second; pq.push({ vi[i].second });
        if (pq.size() > b) t -= pq.top(), pq.pop();
        dp[i][1] = t;
    }

    LL ans = 0;
    fa(i, 0, n - 1) ckmax(ans, dp[i][0] + dp[i + 1][1]);
    co(ans);

}

Compilation message

school.cpp: In function 'int main()':
school.cpp:80:23: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, lcmp>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |         if (pq.size() > a) t -= pq.top(), pq.pop();
      |             ~~~~~~~~~~^~~
school.cpp:89:23: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, lcmp>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |         if (pq.size() > b) t -= pq.top(), pq.pop();
      |             ~~~~~~~~~~^~~

Subtask #1
95.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 324 KB Output isn't correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 3 ms 576 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 18 ms 2256 KB Output is correct
14 Correct 35 ms 3912 KB Output is correct
15 Correct 43 ms 7148 KB Output is correct
16 Correct 57 ms 10104 KB Output is correct
17 Correct 74 ms 10688 KB Output is correct
18 Correct 85 ms 11508 KB Output is correct
19 Correct 103 ms 12308 KB Output is correct
20 Correct 98 ms 14188 KB Output is correct