Submission #1190364

#TimeUsernameProblemLanguageResultExecution timeMemory
1190364lopkusCake 3 (JOI19_cake3)C++20
0 / 100
1 ms328 KiB
#include <bits/stdc++.h> void solve() { int n, m; std::cin >> n >> m; std::vector<std::array<int64_t, 2>> a(n + 1); for(int i = 1; i <= n; i++) { std::cin >> a[i][0] >> a[i][1]; std::swap(a[i][0], a[i][1]); } std::sort(a.begin() + 1, a.end()); int64_t ans = 0; std::multiset<int64_t> ms; std::vector<int64_t> x(n + 1); for(int i = 1; i <= n; i++) { x[i] = a[i][1] - 2 * a[i][0]; } for(int i = 1; i < n; i++) { ms.clear(); ms.insert(a[i + 1][1]); int64_t sum = a[i + 1][1] + 2 * a[i][0] + a[i][1]; for(int j = i + 2; j <= n; j++) { if(j - i + 1 >= m) { ans = std::max(ans, sum + x[j]); } ms.insert(a[j][1]); sum += a[j][1]; if(ms.size() > m - 2) { auto small = ms.begin(); sum -= *small; ms.erase(ms.find(*small)); } } } std::cout << ans; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int t = 1; //std::cin >> t; while (t--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...