Submission #7608712
Source Code Expand
#include <bits/stdc++.h> using namespace std; using Int = long long; template <class T> void chmin(T& x, T y) { if (x > y) x = y; } int main() { int N, L; cin >> N >> L; vector<int> A(N), B(N), C(N); for (int i = 0; i < N; i++) cin >> A[i] >> B[i] >> C[i]; vector<pair<int, int>> human, goal; Int M = 0; for (int i = 0; i < N; i++) { int t = abs(B[i] - C[i]); auto& to = B[i] > C[i] ? human : goal; to.emplace_back(A[i], t); if (B[i] > C[i]) M += t; } auto calc = [&](Int offset) { if (!(0 <= offset && offset < M)) return (Int)1e18; Int ans = 0; int g0 = 0, g1 = 0; for (int i = 0; i < goal.size(); i++) { if (goal[i].second <= offset) { offset -= goal[i].second; } else { g0 = i, g1 = offset; break; } } for (int i = 0; i < human.size(); i++) { int h = human[i].first; int rest = human[i].second; while (goal[g0 % goal.size()].second - g1 < rest) { Int k = goal[g0 % goal.size()].second - g1; int g = goal[g0 % goal.size()].first; ans += k * min({ abs(h - g), abs(h - g - L), abs(h - g + L) }); rest -= k; g0 += 1, g1 = 0; } int g = goal[g0 % goal.size()].first; ans += rest * min({ abs(h - g), abs(h - g - L), abs(h - g + L) }); g1 += rest; } return ans; }; Int left = 0, right = M - 1; while (right - left > 2) { Int mid1 = left + (right - left) / 3; Int mid2 = right - (right - left) / 3; if (calc(mid1) <= calc(mid2)) { right = mid2; } else { left = mid1; } } Int ans = 1e18; chmin(ans, calc(0)); chmin(ans, calc(left)); chmin(ans, calc(left + 1)); chmin(ans, calc(right)); chmin(ans, calc(M - 1)); cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - タクシー |
User | ha15 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2087 Byte |
Status | WA |
Exec Time | 286 ms |
Memory | 2680 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 15 | 0 / 30 | 0 / 55 | ||||||||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0-sample-01.txt, subtask0-sample-02.txt |
Subtask1 | subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt |
Subtask2 | subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt |
Subtask3 | subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask3-01.txt, subtask3-02.txt, subtask3-03.txt, subtask3-04.txt, subtask3-05.txt, subtask3-06.txt, subtask3-07.txt, subtask3-08.txt, subtask3-09.txt, subtask3-10.txt, subtask3-11.txt, subtask3-12.txt, subtask3-13.txt, subtask3-14.txt, subtask3-15.txt, subtask3-16.txt, subtask3-17.txt, subtask3-18.txt, subtask3-19.txt, subtask3-20.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0-sample-01.txt | AC | 1 ms | 256 KB |
subtask0-sample-02.txt | AC | 1 ms | 256 KB |
subtask1-01.txt | AC | 1 ms | 256 KB |
subtask1-02.txt | AC | 1 ms | 256 KB |
subtask1-03.txt | AC | 8 ms | 384 KB |
subtask1-04.txt | AC | 8 ms | 384 KB |
subtask1-05.txt | AC | 8 ms | 384 KB |
subtask1-06.txt | AC | 5 ms | 384 KB |
subtask1-07.txt | AC | 8 ms | 384 KB |
subtask1-08.txt | WA | 8 ms | 384 KB |
subtask1-09.txt | AC | 8 ms | 384 KB |
subtask1-10.txt | AC | 8 ms | 384 KB |
subtask1-11.txt | AC | 7 ms | 384 KB |
subtask1-12.txt | AC | 8 ms | 384 KB |
subtask1-13.txt | AC | 7 ms | 384 KB |
subtask1-14.txt | AC | 8 ms | 384 KB |
subtask1-15.txt | AC | 8 ms | 384 KB |
subtask1-16.txt | AC | 8 ms | 384 KB |
subtask1-17.txt | AC | 8 ms | 384 KB |
subtask1-18.txt | AC | 7 ms | 384 KB |
subtask1-19.txt | AC | 8 ms | 384 KB |
subtask1-20.txt | AC | 8 ms | 384 KB |
subtask2-01.txt | WA | 13 ms | 384 KB |
subtask2-02.txt | WA | 13 ms | 384 KB |
subtask2-03.txt | WA | 10 ms | 384 KB |
subtask2-04.txt | WA | 13 ms | 384 KB |
subtask2-05.txt | AC | 9 ms | 384 KB |
subtask2-06.txt | WA | 10 ms | 384 KB |
subtask2-07.txt | WA | 14 ms | 384 KB |
subtask2-08.txt | WA | 14 ms | 384 KB |
subtask2-09.txt | WA | 13 ms | 384 KB |
subtask2-10.txt | WA | 13 ms | 384 KB |
subtask2-11.txt | WA | 13 ms | 384 KB |
subtask2-12.txt | WA | 13 ms | 384 KB |
subtask2-13.txt | WA | 13 ms | 384 KB |
subtask2-14.txt | AC | 9 ms | 384 KB |
subtask2-15.txt | WA | 13 ms | 384 KB |
subtask2-16.txt | WA | 14 ms | 384 KB |
subtask2-17.txt | WA | 13 ms | 384 KB |
subtask2-18.txt | AC | 9 ms | 384 KB |
subtask2-19.txt | WA | 13 ms | 384 KB |
subtask2-20.txt | WA | 14 ms | 384 KB |
subtask3-01.txt | WA | 55 ms | 768 KB |
subtask3-02.txt | WA | 139 ms | 1408 KB |
subtask3-03.txt | WA | 278 ms | 2380 KB |
subtask3-04.txt | WA | 228 ms | 2680 KB |
subtask3-05.txt | WA | 278 ms | 2372 KB |
subtask3-06.txt | WA | 284 ms | 2372 KB |
subtask3-07.txt | WA | 279 ms | 2396 KB |
subtask3-08.txt | WA | 284 ms | 2428 KB |
subtask3-09.txt | AC | 167 ms | 2680 KB |
subtask3-10.txt | WA | 278 ms | 2428 KB |
subtask3-11.txt | AC | 93 ms | 2552 KB |
subtask3-12.txt | WA | 282 ms | 2340 KB |
subtask3-13.txt | WA | 277 ms | 2372 KB |
subtask3-14.txt | WA | 279 ms | 2340 KB |
subtask3-15.txt | WA | 286 ms | 2428 KB |
subtask3-16.txt | WA | 283 ms | 2428 KB |
subtask3-17.txt | WA | 278 ms | 2380 KB |
subtask3-18.txt | WA | 274 ms | 2380 KB |
subtask3-19.txt | WA | 281 ms | 2428 KB |
subtask3-20.txt | WA | 279 ms | 2372 KB |