oj.uz

Submission #1069511

# Submission time Handle Problem Language Result Execution time Memory
1069511 2024-08-22T04:13:55 Z Luvidi Palembang Bridges (APIO15_bridge) C++17
17 / 100
 2000 ms 3288 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back

void solve() {
    int br,n;
    cin>>br>>n;
    vector<pll> seg;
    ll sum=0;
    while(n--){
        char x,y;
        ll a,b;
        cin>>x>>a>>y>>b;
        if(a>b)swap(a,b);
        if(x==y)sum+=b-a;
        else{
            seg.pb({a,b});
            sum++;
        }
    }
    n=seg.size();
    if(!n){
        cout<<sum;
        return;
    }
    if(br==1){
        ll ans=1e18;
        for(int i=0;i<n;i++){
            ll s=0;
            for(int j=0;j<n;j++){
                s+=abs(seg[j].fs-seg[i].fs)+abs(seg[i].fs-seg[j].sc);
            }
            ans=min(ans,s);
        }
        cout<<sum+ans;
    }else{
        ll ans=1e18;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                ll s=0;
                for(int k=0;k<n;k++){
                    s+=min(abs(seg[k].fs-seg[i].fs)+abs(seg[i].fs-seg[k].sc),abs(seg[k].fs-seg[j].fs)+abs(seg[j].fs-seg[k].sc));
                }
                ans=min(ans,s);
            }
        }
        cout<<sum+ans;
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();
}

Subtask #1
8.0 / 8.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 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 508 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 2 ms 348 KB Output is correct

Subtask #2
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 2 ms 348 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Execution timed out 2098 ms 3288 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
9.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 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 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 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 452 KB Output is correct
12 Correct 1 ms 348 KB Output is correct

Subtask #4
0 / 32.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 1 ms 344 KB Output is correct
5 Correct 1 ms 348 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 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1073 ms 472 KB Output is correct
14 Correct 1073 ms 348 KB Output is correct
15 Correct 1037 ms 348 KB Output is correct
16 Correct 34 ms 348 KB Output is correct
17 Correct 167 ms 344 KB Output is correct
18 Incorrect 59 ms 348 KB Output isn't correct
19 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 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1065 ms 348 KB Output is correct
14 Correct 1072 ms 348 KB Output is correct
15 Correct 1074 ms 348 KB Output is correct
16 Correct 36 ms 344 KB Output is correct
17 Correct 172 ms 348 KB Output is correct
18 Incorrect 58 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -