oj.uz

Submission #1042860

# Submission time Handle Problem Language Result Execution time Memory
1042860 2024-08-03T13:17:27 Z kaopj Palembang Bridges (APIO15_bridge) C++17
0 / 100
 2000 ms 432 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=1e9,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 1151 ms 432 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 #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1169 ms 432 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 #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 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 2066 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 2048 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -