# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
102647 | 2019-03-26T13:24:10 Z | fanache99 | Arranging Tickets (JOI17_arranging_tickets) | C++14 | 3 ms | 384 KB |
#include <bits/stdc++.h> using namespace std; const int SIZE = 1 << 17; int pointer = SIZE; char buffer[SIZE]; char Advance() { if (pointer == SIZE) { fread(buffer, 1, SIZE, stdin); pointer = 0; } return buffer[pointer++]; } int Read() { int answer = 0; char ch = Advance(); while (!isdigit(ch)) ch = Advance(); while (isdigit(ch)) { answer = answer * 10 + ch - '0'; ch = Advance(); } return answer; } const int MAXN = 200000; const int MAXM = 100000; const long long INF = 1000000000000000000LL; long long sum[1 + MAXN], start[1 + MAXN], finish[1 + MAXN]; bool Check(int n, long long limit) { long long add = 0, active = 0, good = 0; for (int i = 1; i <= n; i++) { good = min(good, active - finish[i]); active += sum[i]; long long need = max(0LL, active + add - limit - 2 * good); if (active - good < need) return false; add += need; good += need; } return add <= limit; } int main() { //ifstream cin("tema.in"); //ofstream cout("tema.out"); int n, m; cin >> n >> m; for (int i = 1; i <= m; i++) { int a, b, c; cin >> a >> b >> c; if (a > b) swap(a, b); sum[a] += c; sum[b] -= c; start[a] += c; finish[b] += c; } long long left = 0, right = INF, answer; while (left <= right) { long long middle = (left + right) / 2; if (Check(n, middle)) { answer = middle; right = middle - 1; } else left = middle + 1; } cout << answer << "\n"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |