Submission #6825550


Source Code Expand

Copy
/** 
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 */

/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
*/

#include <bits/stdc++.h>
using namespace std;

/* see https://github.com/pllk/cphb/
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,
    tree_order_statistics_node_update> indexed_set;
 **/

typedef long long ll;
#define endl "\n"
#define fori(n) for(ll i=0; i<(n); i++)

#define cins(s) string s; cin>>s;
#define cini(i) int i; cin>>i;
#define cinll(l) ll l; cin>>l;
#define cinai(a, n) vi a(n); fori(n) { cin>>a[i]; }
#define cinall(a, n) vll a(n); fori(n) { cin>>a[i]; }
#define cinas(s, n) vs s(n); fori(n) { cin>>s[i]; }

//typedef __int128 lll;
typedef pair<int, int> pii;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<string> vs;
typedef vector<ll> vll;

int main() {
cin.tie(nullptr);
std::ios::sync_with_stdio(false);
    cini(n);
    cini(m);
    vector<pii> a(n);

    fori(n) {
        cin>>a[i].first>>a[i].second;
    }
    sort(a.begin(), a.end());

    multiset<int> bees;
    int idx=0;
    ll ans=0;
    for(int i=1; i<=m; i++) {
        while(idx<n && a[idx].first<=i) {
            bees.insert(a[idx].second);
            idx++;
        }
        if(bees.size()>0) {
            auto it=bees.end();
            it--;
            int val=*it;
//cout<<"days "<<i<<" job worth="<<val<<endl;
            ans+=val;
            bees.erase(it);
        }
    }

    cout<<ans<<endl;
}

Submission Info

Submission Time
Task D - Summer Vacation
User spookywooky
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1697 Byte
Status AC
Exec Time 41 ms
Memory 5632 KB

Judge Result

Set Name All Sample
Score / Max Score 400 / 400 0 / 0
Status
AC × 21
AC × 3
Set Name Test Cases
All sample_01, sample_02, sample_03, testcase_01, testcase_02, testcase_03, testcase_04, testcase_05, testcase_06, testcase_07, testcase_08, testcase_09, testcase_10, testcase_11, testcase_12, testcase_13, testcase_14, testcase_15, testcase_16, testcase_17, testcase_18
Sample sample_01, sample_02, sample_03
Case Name Status Exec Time Memory
sample_01 AC 1 ms 256 KB
sample_02 AC 1 ms 256 KB
sample_03 AC 1 ms 256 KB
testcase_01 AC 5 ms 384 KB
testcase_02 AC 2 ms 256 KB
testcase_03 AC 20 ms 896 KB
testcase_04 AC 32 ms 1024 KB
testcase_05 AC 32 ms 1024 KB
testcase_06 AC 24 ms 1024 KB
testcase_07 AC 28 ms 1152 KB
testcase_08 AC 12 ms 1920 KB
testcase_09 AC 26 ms 3968 KB
testcase_10 AC 39 ms 5632 KB
testcase_11 AC 36 ms 5120 KB
testcase_12 AC 11 ms 1664 KB
testcase_13 AC 41 ms 5632 KB
testcase_14 AC 38 ms 5248 KB
testcase_15 AC 4 ms 640 KB
testcase_16 AC 41 ms 5632 KB
testcase_17 AC 7 ms 1024 KB
testcase_18 AC 39 ms 5248 KB