# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
937388 | 2024-03-04T01:54:20 Z | duckindog | Palembang Bridges (APIO15_bridge) | C++17 | 2000 ms | 2616 KB |
//from duckindog wth depression #include<bits/stdc++.h> using namespace std; const int N = 100'000 + 10; int k, n; int a[N], b[N]; long long da[N], db[N]; int32_t main() { cin.tie(0)->sync_with_stdio(0); if (fopen("duck.inp", "r")) { freopen("duck.inp", "r", stdin); freopen("duck.out", "w", stdout); } cin >> k >> n; long long answer = 0; for (int i = 1; i <= n; ++i) { char A, B; cin >> A >> a[i] >> B >> b[i]; if (A != B) continue; answer += abs(b[i] - a[i]); i -= 1; n -= 1; } sort(a + 1, a + n + 1); sort(b + 1, b + n + 1); set<int> pos; for (int i = 1; i <= n; ++i) { pos.insert(a[i]); pos.insert(b[i]); da[i] = da[i - 1] + a[i]; db[i] = db[i - 1] + b[i]; } auto cal = [&](int i) { auto itA = upper_bound(a + 1, a + n + 1, i) - a - 1, itB = upper_bound(b + 1, b + n + 1, i) - b - 1; long long ret = 0; ret += 1ll * itA * i - da[itA] + da[n] - da[itA] - 1ll * i * (n - itA); ret += 1ll * itB * i - db[itB] + db[n] - db[itB] - 1ll * i * (n - itB); return ret; }; long long ret = 1'000'000'000'000'000; int mi = min(*min_element(a + 1, a + n + 1), *min_element(b + 1, b + n + 1)), ma = min(*max_element(a + 1, a + n + 1), *max_element(b + 1, b + n + 1)); for (int i = mi; i <= ma; ++i) ret = min(ret, cal(i)); cout << answer + ret + n << "\n"; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Correct | 1 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 23 ms | 2616 KB | Output is correct |
5 | Execution timed out | 2045 ms | 2396 KB | Time limit exceeded |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Correct | 0 ms | 2392 KB | Output is correct |
3 | Correct | 1 ms | 2596 KB | Output is correct |
4 | Correct | 23 ms | 2512 KB | Output is correct |
5 | Execution timed out | 2077 ms | 2396 KB | Time limit exceeded |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
2 | Correct | 1 ms | 2392 KB | Output is correct |
3 | Incorrect | 1 ms | 2396 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
2 | Correct | 1 ms | 2396 KB | Output is correct |
3 | Incorrect | 1 ms | 2392 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Correct | 1 ms | 2396 KB | Output is correct |
3 | Incorrect | 1 ms | 2396 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |