제출 #1263646

#제출 시각아이디문제언어결과실행 시간메모리
1263646miniobArranging Tickets (JOI17_arranging_tickets)C++20
0 / 100
2 ms4928 KiB
#include <bits/stdc++.h> using namespace std; vector<pair<pair<long long, long long>, long long>> wyma; long long roz[200007]; long long ile[200007]; long long sumakon[200007]; long long maxseg = -1, gdziemax, n, m; vector<pair<long long, long long>> przechodzace[200007]; long long cof[200007]; bool spr(long long sr, long long ilezw) { priority_queue<pair<long long, long long>> pq; long long suma = 0; for(long long i = 0; i < n + 3; i++) { sumakon[i] = 0; } long long cur = 0; long long usunl = 0; for(long long i = 1; i <= gdziemax; i++) { for(auto x : przechodzace[i]) { pq.push(x); cur += x.second; suma += x.second; sumakon[x.first] += x.second; } while(cur > sr) { auto x = pq.top(); pq.pop(); long long minn = min(cur - sr, x.second); x.second -= minn; cur -= minn; usunl += minn; if(x.second > 0) { pq.push(x); } } } while(!pq.empty()) { pq.pop(); } cur = 0; long long usup = 0; for(long long j = gdziemax; j <= n - 1; j++) { if(sumakon[j] > 0) { long long remain = sumakon[j]; while(remain > 0) { pq.push({j, remain}); cur += remain; remain = 0; } } while(cur > sr) { auto x = pq.top(); pq.pop(); long long minn = min(cur - sr, x.second); x.second -= minn; cur -= minn; usup += minn; if(x.second > 0) { pq.push({x.first, x.second}); } } } if(usunl + usup <= suma) { return true; } else { return false; } } int main() { cin >> n >> m; for(long long i = 0; i < m; i++) { long long a, b, c; cin >> a >> b >> c; if(a > b) { swap(a, b); } wyma.push_back({{a, b - 1}, c}); roz[a] += c; roz[b] -= c; } for(long long i = 1; i <= n; i++) { ile[i] = ile[i - 1] + roz[i]; if(maxseg < ile[i]) { maxseg = ile[i]; gdziemax = i; } } for(auto x : wyma) { if(x.first.first <= gdziemax && gdziemax <= x.first.second) { przechodzace[x.first.first].push_back({x.first.second, x.second}); } } long long l = 0, r = maxseg; while(l < r) { long long sr = (l + r) / 2; if(spr(sr, maxseg - sr) || spr(sr, maxseg - sr + 1)) { r = sr; } else { l = sr + 1; } } cout << l << endl; 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...