oj.uz

Submission #1042864

# Submission time Handle Problem Language Result Execution time Memory
1042864 2024-08-03T13:26:45 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,b;
    int mx=0,r=0;
    for (int i=0;i<n;i++) {
        int p;
        char c;
        cin >> c >> p;
        mx=max(mx,p);
        a.push_back({p,c-'A'});
        cin >> c >> p;
        mx=max(mx,p);
        if (a.back().s == c-'A') {
            r+=abs(p-a.back().f);
            a.pop_back();
        } else b.push_back({p,c-'A'});
    }
    int ans=1e18,cur;
    n=a.size();
    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 << r+ans;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1168 ms 504 KB Output is correct
5 Execution timed out 2080 ms 348 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 2024 ms 344 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 2025 ms 344 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 2035 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -