oj.uz

Submission #1042863

# Submission time Handle Problem Language Result Execution time Memory
1042863 2024-08-03T13:21:11 Z kaopj Palembang Bridges (APIO15_bridge) C++17
0 / 100
 2000 ms 600 KB 
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define int long long
#define lgm cin.tie(0)->sync_with_stdio(0);
#define be(x) x.begin(),x.end()
#define v vector
#define f first
#define s second
const int mod = 1e9+7;
signed main() {
    lgm;
    int n,k;
    cin >> k>>n;
    v<pair<int,int>> a(n),b(n);
    int mx=0;
    for (int i=0;i<n;i++) {
        int p;
        char c;
        cin >> c >> p;
        mx=max(mx,p);
        a[i]={p,c-'A'};
        cin >> c >> p;
        mx=max(mx,p);
        b[i]={p,c-'A'};
    }
    int ans=1e18,cur;
    if (k == 1) {
        for (int i=0;i<=mx;i++) {
            cur=0;
            for (int j=0;j<n;j++) {
                if (a[j].s==b[j].s) {
                    cur+=abs(a[j].f-b[j].f);
                } else {
                    cur+=1+abs(a[j].f-i)+abs(b[j].f-i);
                }
            }
            ans=min(ans,cur);
        }
    } else {
        for (int i=0;i<=mx;i++) {
            for (int j=i+1;j<=mx;j++) {
                cur=0;
                for (int k=0;k<n;k++) {
                    if (a[k].s==b[k].s) {
                        cur+=abs(a[k].f-b[k].f);
                    } else {
                        cur+=1+min(abs(a[k].f-i)+abs(b[k].f-i),abs(a[k].f-j)+abs(b[k].f-j));
                    }
                }
                ans=min(ans,cur);
            }
        }
    }
    cout << ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1102 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1187 ms 484 KB Output is correct
5 Execution timed out 2072 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 1108 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 1204 ms 484 KB Output is correct
5 Execution timed out 2025 ms 600 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2049 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2047 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2075 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -