Submission #482992

#	Time	Username	Problem	Language	Result	Execution time	Memory
482992		deuslovelt	Schools (IZhO13_school)	C++17	95 / 100	103 ms	14188 KiB

school

//================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 (stderr)

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 / 100