Submission #998237

#TimeUsernameProblemLanguageResultExecution timeMemory
998237LOLOLOFeast (NOI19_feast)C++17
30 / 100
159 ms17936 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define f first #define s second #define pb push_back #define ep emplace #define eb emplace_back #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define mem(f,x) memset(f , x , sizeof(f)) #define sz(x) (ll)(x).size() #define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b)) #define mxx *max_element #define mnn *min_element #define cntbit(x) __builtin_popcountll(x) #define len(x) (int)(x.length()) const int N = 3e5 + 10; int p[N], sz[N], l[N], r[N], a[N]; ll val[N]; set <pair <ll, ll>> st; int get(int x) { return p[x] ? get(p[x]) : x; } int same(int a, int b) { a = get(a), b = get(b); return a == b; } void unite(int a, int b) { a = get(a), b = get(b); if (a == b) return; if (sz[a] < sz[b]) swap(a, b); sz[a] += sz[b]; p[b] = a; l[a] = min(l[a], l[b]); r[a] = max(r[a], r[b]); val[a] += val[b]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k; cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; sz[i] = 1; l[i] = r[i] = i; } while (a[n] <= 0 && n) n--; if (n == 0) { cout << 0 << '\n'; return 0; } int ft = 1; while (a[ft] <= 0) ft++; for (int j = ft; j <= n; j++) a[j - ft + 1] = a[j]; for (int i = 1; i <= n; i++) { val[i] = a[i]; } for (int i = 1; i < n; i++) { if (bool(a[i] >= 0) == bool(a[i + 1] >= 0)) unite(i, i + 1); } ll cc = 0; for (int i = 1; i <= n; i++) { if (get(i) == i) { cc += val[i] > 0; st.insert({abs(val[i]), i}); } } while (cc > k) { auto it = *st.begin(); st.erase(it); int p = get(it.s); cc -= val[p] > 0; if (l[p] > 1) { int x = get(l[p] - 1); st.erase({abs(val[x]), x}); cc -= val[x] > 0; unite(p, x); } if (r[p] < n) { int x = get(r[p] + 1); st.erase({abs(val[x]), x}); cc -= val[x] > 0; unite(p, x); } p = get(p); if ((same(p, 1) == 0 && same(p, n) == 0) || (val[p] > 0)) { st.insert({abs(val[p]), p}); cc += val[p] > 0; } } ll ans = 0; while (sz(st)) { auto it = *st.begin(); st.erase(it); int p = it.s; ans += max((ll)0, val[p]); } cout << ans << '\n'; 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...