oj.uz

Submission #1057091

# Submission time Handle Problem Language Result Execution time Memory
1057091 2024-08-13T14:04:18 Z nickshen Palembang Bridges (APIO15_bridge) C++17
0 / 100
 1 ms 436 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ss second
#define ff first
typedef vector<pair<int, int>> vpi;
typedef vector<int> vi;
void solve() {
    int k, n;
    cin >> k >> n;
    int ans = 0;
    map<int, int> mp;
    vpi v;
    for (int i = 0; i < n; i++) {
        char a, b;
        int c, d;
        cin >> a >> c >> b >> d;
        if (a == b)
            ans += abs(d - c);
        else {
            if (c > d) swap(c, d);
            mp[c]++;
            mp[d + 1]--;
            v.push_back({c, d});
        }
    }
    vi t;
    int mx = 0, p = 0;
    while (k--) {
        int cur = 0;
        for (auto u : mp) {
            cur += u.ss;
            if (mx <= cur) {
                mx = cur;
                p = u.ff;
            }
        }
        for (auto u : v) {
            if (u.ff <= p && u.ss >= p) {
                mp[u.ff]--;
                mp[u.ss + 1]++;
            }
        }
        t.push_back(p);
        mx = 0;
        p = 0;
    }
    for (auto u : v) {
        int mn = 1e10;
        for (auto j : t) {
            mn = min(mn, abs(j - u.ff) + 1 + abs(j - u.ss));
        }
        ans += mn;
    }
    cout << ans << "\n";
}

/*
Fact 1: add a bridge between office and home and add a bridge at the end of office or home are the same -> just add at the end
Fact 2: if pair a is inside pair b, ignore pair b
Fact 3: ignore pair on the same side
Fact 4: it is optimal to choose a point with maximum pair included
*/

/*
Step:
1. Find the point with maximum number of pair included in each loop
2. erase all pair included in the point
3. Calculate the minimum cost after k point is used

time: O(n*log(n))


*/

signed main() {
    int t = 1;
    // cin>>t;
    while (t--) {
        solve();
    }
}

Subtask #1
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 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

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

Subtask #3
0 / 9.0

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