Submission #485377

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
485377	2021-11-07T13:22:00 Z	Neos	Hotel (CEOI11_hot)	C++14	100 / 100	965 ms	45108 KB

#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define PI acos(-1.0)
#define FF first
#define SS second
#define eps 1e-3
// vector
#define pb push_back
#define sz(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define lb lower_bound
#define ub upper_bound
// bit
#define CNTBIT(x) __builtin_popcount(x)
#define ODDBIT(x) __builtin_parity(x)
#define MASK(i) (1ll<<(i))
#define BIT(x, i) (((x)>>(i))&1)
#define SUBSET(big, small) (((big)&(small))==(small))
#define MINBIT(x) (x)&(-x)
// typedef
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> i3;
/* CODE BELOW */
const int N=3e3+7, M=4e5+7;
const int MOD=998244353;
const int oo=1e9+7;

int n, m, k, t;

multiset<ii> s;

signed main() {
    //fastIO;
    scanf("%d%d%d", &n, &m, &k);
    int u, v, cnt=0;
    for(int i=1;i<=n;i++) {
        scanf("%d%d", &u, &v);
        s.insert(ii(v, u));
    }

    vector<ii> q;
    for(int i=1;i<=m;i++) {
        scanf("%d%d", &u, &v);
        q.pb(ii(-u, v));
    }
    sort(all(q));

    ll ans=0;
    vector<ll> _ans;
    for(ii r:q) {
        tie(u, v)=r;
        auto it=s.lb(ii(v, 0));
        if(it==s.end()) continue;
        if(-u-it->SS<0) continue;
        //ans+=-u-it->SS, cnt++;
        _ans.pb(u+it->SS);
        s.erase(it);
        //if(cnt==k) break;
    }

    sort(all(_ans));
    for(int i=1;i<=min(k, sz(_ans));i++) {
        ans+=-_ans[i-1];
    }
    printf("%lld", ans);

    return 0;
}
/* stuff you should look for
    - int overflow, array bounds
    - special/edge cases (n=1?)
    - do smth instead of nothing and stay organized
    - WRITE STUFF DOWN
    - DONT JUST STICK ON ONE APPROACH
*/

Compilation message

hot.cpp: In function 'int main()':
hot.cpp:39:15: warning: unused variable 'cnt' [-Wunused-variable]
   39 |     int u, v, cnt=0;
      |               ^~~
hot.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d%d%d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
hot.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~
hot.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1100 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	4540 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	7672 KB	Output is correct
2	Correct	68 ms	6012 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	243 ms	19888 KB	Output is correct
2	Correct	114 ms	11512 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	598 ms	38644 KB	Output is correct
2	Correct	648 ms	25940 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	697 ms	45108 KB	Output is correct
2	Correct	775 ms	34176 KB	Output is correct
3	Correct	965 ms	36932 KB	Output is correct