oj.uz

Submission #978254

# Submission time Handle Problem Language Result Execution time Memory
978254 2024-05-09T04:51:12 Z nnin Palembang Bridges (APIO15_bridge) C++17
0 / 100
 2000 ms 452 KB 
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
using ll = long long;
#define f first
#define s second
 
vector<pii> cross;
int N, K, MN, MX;
 
ll check1(int bridge) {
    ll ret = 0;
    for(auto [st, en]:cross) {
        if(bridge<st) ret += (ll)st-bridge+en-bridge;
        else if(bridge>en) ret += (ll)bridge-st+bridge-en;
        else ret += (ll)en-st;
    }
    return ret;
}
 
ll check2(int br1, int br2) {
    ll ret = 0;
    for(auto [st, en]:cross) {
        if((st<=br1&&br1<=en) || (st<=br2&&br2<=en)) ret += (ll)en-st;
        else if(br2<st) ret += (ll)st-br2+en-br2;
        else if(br1>en) ret += (ll)br1-st+br1-en;
        else ret += min((ll)st-br1+en-br1, (ll)br2-st+br2-en);
    }
    return ret;
}
 
ll one() {
    if(cross.empty()) return 0;
    ll ret = 2e9;
    for(int i=MN;i<=MX;i++) ret = min(ret, check1(i));
    return ret;
}
 
ll two() {
    if(cross.empty()) return 0;
    ll ret = 2e9;
    for(int i=MN;i<=MX;i++) for(int j=i+1;j<=MX;j++) ret = min(ret, check2(i, j));
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>K>>N;
    ll ans = 0;
    MN = 2e9, MX = -2e9;
    for(int i=0;i<N;i++) {
        char z1, z2;
        int b1, b2;
        cin>>z1>>b1>>z2>>b2;
        if(z1==z2) {
            ans += abs(b1-b2);
        } else {
            cross.push_back({min(b1, b2), max(b1, b2)});
            MN = min(MN, min(b1, b2));
            MX = max(MX, max(b1, b2));
        }
    }
    sort(cross.begin(), cross.end());
    ans += cross.size();
    if(K==1) cout<<ans+one();
    else cout<<ans+two();
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1915 ms 448 KB Output is correct
5 Execution timed out 2062 ms 348 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.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 1 ms 348 KB Output is correct
4 Correct 1981 ms 452 KB Output is correct
5 Execution timed out 2062 ms 348 KB Time limit exceeded
6 Halted 0 ms 0 KB -

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 Correct 0 ms 348 KB Output is correct
4 Execution timed out 2045 ms 348 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 2085 ms 348 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 2009 ms 348 KB Time limit exceeded
5 Halted 0 ms 0 KB -