| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1224759 | _rain_ | Arranging Tickets (JOI17_arranging_tickets) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
const int N = 200200;
int n, m, pos = 0;
long long a[N], s[N];
vector<pair<int, int>> upd[N];
bool check (long long take, long long lim){
fill(s, s + n + 1, 0ll);
priority_queue<pair<int, int>> pq;
long long cur = 0;
for (int i = 1; i <= pos; ++i){
long long need = max(0,a[i]-lim);
assert(a[i]-need<=lim);
for (auto [x, y] : upd[i]){
if (x > pos){
pq.push({x, y});
}
}
while (cur < need){
if (pq.empty()){
return false;
}
auto [x, y] = pq.top(); pq.pop();
if (cur + 1ll * y <= need){
cur += 1ll * y;
s[x] += 1ll * y;
} else {
long long add = need - cur;
cur += add;
s[x] += add;
y -= (int)(add);
pq.push({x, y});
}
}
}
for (int i = pos + 1; i <= n; ++i){
cur -= s[i];
if (1ll * a[i] + take - 2ll * cur > lim){
return false;
}
}
return true;
}
int32_t main (){
ios::sync_with_stdio(false); cin.tie(nullptr);
if (fopen ("main.inp", "r")){
freopen ("main.inp", "r", stdin);
freopen ("main.out", "w", stdout);
}
cin >> n >> m;
for (int i = 1; i <= m; ++i){
int x, y, z; cin >> x >> y >> z;
if (x > y){
swap(x, y);
}
a[x] += 1ll * z;
a[y] -= 1ll * z;
upd[x].push_back({y, z});
}
for (int i = 1; i <= n; ++i){
a[i] += a[i - 1];
if (a[pos] < a[i]){
pos = i;
}
}
long long l = 0, r = 1ll * m * (int)(1e9), ans = r;
while (l <= r){
long long mid = l + r >> 1;
bool possible = (check(a[pos] - mid, mid) || check(a[pos] - mid + 1, mid));
if (possible){
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << ans << "\n";
}