# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
23775 | 2017-05-25T18:02:48 Z | rubabredwan | Palembang Bridges (APIO15_bridge) | C++14 | 33 ms | 2020 KB |
/* Bismillahir Rahmanir Rahim */ #include <bits/stdc++.h> using namespace std; const int N = 105; const long long oo = 1e18; int k, n; long long pos[N][2]; char fk[N][2]; void solve_big(){ long long ret = oo; for(int i = 1; i <= n; i++){ for(int a = 0; a <= 1; a++){ for(int j = 1; j <= n; j++){ for(int b = 0; b <= 1; b++){ long long ans = 0; for(int f = 1; f <= n; f++){ if(fk[f][0] == fk[f][1]){ ans += abs(pos[f][1] - pos[f][0]); continue; } long long aa = 1LL + abs(pos[f][0] - pos[i][a]) + abs(pos[f][1] - pos[i][a]); long long bb = 1LL + abs(pos[f][0] - pos[j][b]) + abs(pos[f][1] - pos[j][b]); ans += min(aa, bb); } ret = min(ret, ans); } } } } cout << ret << endl; } void solve_small(){ long long ret = oo; long long add = 0; long long pre = 0; long long suf = 0; vector<long long> gg; for(int i = 1; i <= n; ++i){ if(fk[i][0] == fk[i][1]) add += abs(pos[i][1] - pos[i][0]); else{ gg.push_back(pos[i][0]); gg.push_back(pos[i][1]); suf += pos[i][0]; suf += pos[i][1]; add += 1LL; } } sort(gg.begin(), gg.end()); for(long long i = 0; i < gg.size(); ++i){ long long ans = 0; ans += (gg[i] * i) - pre; ans += suf - (gg[i] * 1LL * (gg.size() - i)); pre += gg[i]; suf -= gg[i]; ret = min(ret, ans); } cout << ret + add << endl; } int main(){ cin >> k >> n; for(int i = 1; i <= n; i++){ for(int j = 0; j <= 1; j++){ cin >> fk[i][j] >> pos[i][j]; } } if(k == 1) solve_small(); else solve_big(); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 2020 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 2020 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2020 KB | Output is correct |
2 | Correct | 0 ms | 2020 KB | Output is correct |
3 | Correct | 16 ms | 2020 KB | Output is correct |
4 | Correct | 16 ms | 2020 KB | Output is correct |
5 | Correct | 3 ms | 2020 KB | Output is correct |
6 | Correct | 0 ms | 2020 KB | Output is correct |
7 | Correct | 16 ms | 2020 KB | Output is correct |
8 | Correct | 23 ms | 2020 KB | Output is correct |
9 | Correct | 26 ms | 2020 KB | Output is correct |
10 | Correct | 16 ms | 2020 KB | Output is correct |
11 | Correct | 26 ms | 2020 KB | Output is correct |
12 | Correct | 16 ms | 2020 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2020 KB | Output is correct |
2 | Correct | 0 ms | 2020 KB | Output is correct |
3 | Correct | 16 ms | 2020 KB | Output is correct |
4 | Correct | 16 ms | 2020 KB | Output is correct |
5 | Correct | 3 ms | 2020 KB | Output is correct |
6 | Correct | 0 ms | 2020 KB | Output is correct |
7 | Correct | 16 ms | 2020 KB | Output is correct |
8 | Correct | 29 ms | 2020 KB | Output is correct |
9 | Correct | 16 ms | 2020 KB | Output is correct |
10 | Correct | 19 ms | 2020 KB | Output is correct |
11 | Correct | 16 ms | 2020 KB | Output is correct |
12 | Correct | 23 ms | 2020 KB | Output is correct |
13 | Incorrect | 0 ms | 2020 KB | Output isn't correct |
14 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2020 KB | Output is correct |
2 | Correct | 0 ms | 2020 KB | Output is correct |
3 | Correct | 16 ms | 2020 KB | Output is correct |
4 | Correct | 16 ms | 2020 KB | Output is correct |
5 | Correct | 0 ms | 2020 KB | Output is correct |
6 | Correct | 0 ms | 2020 KB | Output is correct |
7 | Correct | 16 ms | 2020 KB | Output is correct |
8 | Correct | 16 ms | 2020 KB | Output is correct |
9 | Correct | 16 ms | 2020 KB | Output is correct |
10 | Correct | 33 ms | 2020 KB | Output is correct |
11 | Correct | 16 ms | 2020 KB | Output is correct |
12 | Correct | 16 ms | 2020 KB | Output is correct |
13 | Incorrect | 0 ms | 2020 KB | Output isn't correct |
14 | Halted | 0 ms | 0 KB | - |