제출 #952459

#제출 시각아이디문제언어결과실행 시간메모리
952459SN0WM4NCake 3 (JOI19_cake3)C++17
5 / 100
64 ms600 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define bpc __builtin_popcount #define mp make_pair #define ull unsigned long long #define ld double #define ll long long #define F first #define S second using namespace __gnu_pbds; using namespace std; typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> Tree; const ll INF = 9223372036854775807LL; const ll inf = 2147483647; const ll MOD = 1e9 + 7; const ld PI = acos(-1); const ll NROOT = 320; //void FileIO(string in, string out) { //#ifndef LOCAL // freopen(in, "r", stdin); // freopen(out, "w", stdout); //#endif //} ll binpow(ll a, ll b) { ll res = 1; for (; b; b /= 2, a *= a, a %= MOD) if (b & 1) res *= a, res %= MOD; return res; } bool dataOverflow(ll a, ll b) {return (log10(a) + log10(b) >= 18);} ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} ll lcm(ll a, ll b) {return a * b / gcd(a, b);} ll invmod(ll a) {return binpow(a, MOD - 2);} ll ceil(ll a, ll b) {return (a + b - 1) / b;} void print(priority_queue<ll, vector<ll>, greater<ll>> q) { int cnt = 0; while (!q.empty()) { if (cnt > 0) cerr << " "; cerr << q.top(); q.pop(); cnt ++; } } bool cmp(pair<ll, ll> a, pair<ll, ll> b) { if (a.S == b.S) return a.F <= b.F; return a.S <= b.S; } void comp(bool stat) { if (!stat) exit(1); } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; m -= 2; vector<pair<ll, ll>> v(n + 1); for (int i = 1; i <= n; i ++) cin >> v[i].F >> v[i].S; sort(v.begin() + 1, v.end(), cmp); ll ans = -1e16; for (int i = 1; i <= n; i ++) { ll act = v[i].F; priority_queue<ll, vector<ll>, greater<ll>> q; comp((int)q.size() <= m); comp(1 <= i && i <= n); for (int j = i + 1; j <= n; j ++) { comp(1 <= j && j <= n); if ((int)q.size() == m) { ll tmp = act + v[j].F; tmp -= 2LL * (v[j].S - v[i].S); ans = max(ans, tmp); // cerr << i << " " << j << ": {"; // print(q); // cerr << "} => " << tmp << '\n'; q.push(v[j].F); act += v[j].F; act -= q.top(); q.pop(); } else { q.push(v[j].F); act += v[j].F; } } } cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...