oj.uz

Submission #744600

# Submission time Handle Problem Language Result Execution time Memory
744600 2023-05-18T19:16:33 Z Desh03 Palembang Bridges (APIO15_bridge) C++17
22 / 100
 172 ms 26032 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    long long k, n, ans = 1e18, ss = 0, S = 0, S2 = 0;
    cin >> k >> n;
    vector<long long> a, b;
    for (int i = 0; i < n; i++) {
        char x, y;
        int s, t;
        cin >> x >> s >> y >> t;
        if (x == y) {
            ss += abs(s - t);
            continue;
        }
        if (x == 'A') a.push_back(s), b.push_back(t);
        else a.push_back(t), b.push_back(s);
    }
    if (a.size()) {
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        n = a.size();
        vector<long long> pre1(n + 1), pre2(n + 1), v;
        for (int i = 0; i < n; i++) pre1[i + 1] = pre1[i] + a[i], S += a[i];
        for (int i = 0; i < n; i++) pre2[i + 1] = pre2[i] + b[i], S2 += b[i];
        set<long long> to;
        for (auto x : a) v.push_back(x);
        for (auto y : b) v.push_back(y);
        to.insert(v[0]);
        for (int i = 0; i < v.size() - 1; i++) {
            to.insert(v[i + 1]);
            to.insert(v[i] + v[i + 1] >> 1);
        }
        for (auto x : to) {
            long long k = upper_bound(a.begin(), a.end(), x) - a.begin();
            long long k2 = upper_bound(b.begin(), b.end(), x) - b.begin();
            ans = min(ans, 2 * (x * (k + k2 - n) - pre1[k] - pre2[k2]));
        }
        cout << ans + S + S2 + ss + n << '\n';
    } else {
        cout << ss << '\n';
    }
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:32:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (int i = 0; i < v.size() - 1; i++) {
      |                         ~~^~~~~~~~~~~~~~
bridge.cpp:34:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |             to.insert(v[i] + v[i + 1] >> 1);

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 456 KB Output is correct
5 Correct 2 ms 568 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 1 ms 352 KB Output is correct
11 Correct 1 ms 480 KB Output is correct
12 Correct 27 ms 6368 KB Output is correct
13 Correct 147 ms 26020 KB Output is correct
14 Correct 56 ms 6444 KB Output is correct
15 Correct 94 ms 15492 KB Output is correct
16 Correct 34 ms 7244 KB Output is correct
17 Correct 172 ms 26032 KB Output is correct
18 Correct 119 ms 16292 KB Output is correct
19 Correct 137 ms 25200 KB Output is correct
20 Correct 35 ms 7476 KB Output is correct
21 Correct 119 ms 17580 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -