oj.uz

Submission #1037750

# Submission time Handle Problem Language Result Execution time Memory
1037750 2024-07-29T07:45:24 Z stdfloat Palembang Bridges (APIO15_bridge) C++17
22 / 100
 24 ms 3664 KB 
#include <bits/stdc++.h>
using namespace std;
    
using ll = long long;
    
#define ff  first
#define ss  second
#define pii pair<int, int>
    
ll f(int x, vector<pii> &v) {
    ll sm = 0;
    for (auto i : v) sm += abs(i.ff - x) + 1 + abs(i.ss - x);
    
    return sm;
}
    
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int k, n;
    cin >> k >> n;
    
    ll sm = 0;
    vector<pii> v;
    for (int i = 0; i < n; i++) {
        char p, q;
        int s, t;
        cin >> p >> s >> q >> t;
    
        if (p == q) sm += abs(t - s);
        else v.push_back({s, t});
    }
    
    int l = 0, r = (int)1e9;
    while (l <= r) {
        int md = (l + r) >> 1;
    
        if (f(md, v) >= f(md + 1, v)) l = md + 1;
        else r = md - 1;
    }
    
    cout << sm + f(l, v);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 472 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 500 KB Output is correct
10 Correct 0 ms 492 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 496 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 20 ms 2268 KB Output is correct
13 Correct 24 ms 3664 KB Output is correct
14 Correct 18 ms 2520 KB Output is correct
15 Correct 14 ms 2268 KB Output is correct
16 Correct 22 ms 3040 KB Output is correct
17 Correct 24 ms 3544 KB Output is correct
18 Correct 23 ms 3288 KB Output is correct
19 Correct 24 ms 3564 KB Output is correct
20 Correct 23 ms 3032 KB Output is correct
21 Correct 23 ms 3284 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 348 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -