Submission #693150

#TimeUsernameProblemLanguageResultExecution timeMemory
693150nhphucqtFeast (NOI19_feast)C++17
100 / 100
261 ms18520 KiB
#include <bits/stdc++.h> using namespace std; template<typename T> inline void maximize(T&x, T y) { if (x < y) x = y; } const int N = 3e5+7; int n, k, a[N]; vector<long long> v; int fa[N]; long long sum[N]; pair<int,int> range[N]; int cnt, lef, rig; set<pair<long long,int>> comp; long long res; int root(int x) { return fa[x] < 0 ? x : fa[x] = root(fa[x]); } void unite(int u, int v) { if (fa[u] > fa[v]) swap(u,v); comp.erase(make_pair(abs(sum[u]), u)); comp.erase(make_pair(abs(sum[v]), v)); fa[u] += fa[v]; fa[v] = u; sum[u] += sum[v]; range[u].first = min(range[u].first, range[v].first); range[u].second = max(range[u].second, range[v].second); } int main() { cin.tie(nullptr)->sync_with_stdio(false); //freopen("PHATQUA.inp", "r", stdin); //freopen("PHATQUA.out", "w", stdout); cin >> n >> k; for (int i = 1; i <= n; ++i) { cin >> a[i]; } long long s = 0; for (int i = 1; i <= n; ++i) { s += a[i]; if (i==n || ((a[i]>0)^(a[i+1]>0))) { v.push_back(s); s = 0; } } memset(fa, -1, sizeof fa); for (int i = 0; i < (int)v.size(); ++i) { sum[i] = v[i]; range[i] = make_pair(i,i); } for (int i = 0; i < (int)v.size(); ++i) { if (v[i] > 0 || (i>0&&i+1<(int)v.size())) { comp.emplace(abs(v[i]), i); } cnt += v[i] > 0; } lef = v[0] <= 0 ? 1 : 0; rig = v.back() <= 0 ? (int)v.size()-2 : (int)v.size()-1; while (cnt > k) { int u = comp.begin()->second; assert(u == root(u)); cnt -= sum[u] > 0; if (range[u].first > lef) { int v = root(range[u].first-1); cnt -= sum[v] > 0; unite(u, v); } u = root(u); if (range[u].second < rig) { int v = root(range[u].second+1); cnt -= sum[v] > 0; unite(u, v); } u = root(u); if (sum[u] < 0 && (range[u].first == lef || range[u].second == rig)) { if (range[u].first == lef) { lef = range[u].second+1; } else { rig = range[u].first-1; } } else { comp.emplace(abs(sum[u]), u); cnt += sum[u] > 0; } } for (auto p : comp) { if (sum[p.second] > 0) { res += sum[p.second]; } } cout << res; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...