Submission #923615

#TimeUsernameProblemLanguageResultExecution timeMemory
923615danikoynovCake 3 (JOI19_cake3)C++14
0 / 100
2 ms6492 KiB
/** ____ ____ ____ ____ ____ ____ ||l |||e |||i |||n |||a |||d || ||__|||__|||__|||__|||__|||__|| |/__\|/__\|/__\|/__\|/__\|/__\| **/ #include<bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } const int maxn = 2e5 + 10; struct element { ll v, s, idx; element(ll _v = 0, ll _s = 0, ll _idx = 0) { v = _v; s = _s; idx = _idx; } }e[maxn]; int n, m; void input() { cin >> n >> m; for (int i = 1; i <= n; i ++) { cin >> e[i].v >> e[i].s; e[i].s *= 2; e[i].idx = i; } } bool cmp_second(element e1, element e2) { return e1.s < e2.s; } ll inf = 1e18; ll result; ll dp[maxn]; ll cost(int left, int right) { //cout << "cost " << left << " " << right << endl; vector < ll > values; for (int i = left; i <= right; i ++) values.push_back(e[i].v); sort(values.begin(), values.end()); ll res = 0; for (int i = (int)(values.size()) - 1; i >= (int)(values.size()) - m; i --) res += values[i]; //exit(0); return res; } void divide(int l, int r, int optl, int optr) { if (l > r) return; ///cout << l << " " << r << " " << optl << " " << optr << endl; int mid = (l + r) / 2, opt = -1; if (mid < m) return; dp[mid] = -inf; for (int i = optl; i <= min(optr, mid); i ++) { ///cout << "check " << mid << " " << i << endl; if (mid - i + 1 >= m) { ll sum = - e[mid].s + e[i].s + cost(i, mid); ///cout << "alive " << " " << sum << endl; if (sum > dp[mid]) { dp[mid ] = sum; opt = i; } } } //cout << "pos " << mid << " " << opt << endl; divide(l, mid - 1, optl, opt); divide(mid + 1, r, opt, optr); } void print() { ll best = -inf; for (int i = 1; i <= n; i ++) best = max(best, dp[i]); cout << best << endl; } void solve() { input(); sort(e + 1, e + n + 1, cmp_second); for (int i = 1; i <= n; i ++) dp[i] = -inf; divide(1, n, 1, n); print(); } int main() { solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...