oj.uz

Submission #996271

# Submission time Handle Problem Language Result Execution time Memory
996271 2024-06-10T10:36:39 Z dreamboy Palembang Bridges (APIO15_bridge) C++17
31 / 100
 2000 ms 15156 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define russian setlocale(LC_ALL,"Russian_Russia.20866");
#define file freopen("onlyone.in", "r", stdin), freopen("onlyone.out", "w", stdout);
#define ll long long
#define ull unsigned long long
#define ld long double
#define pll pair<ll, ll>
#define pii pair<int, int>
#define all(s) s.begin(), s.end()
#define pb push_back
#define ins insert
#define mp make_pair
#define sz(x) x.size()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define mem(x) memset(x, 0, sizeof(x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 30010;
const ll M = 600000;
const ll block = 316;
const ll mod = 998244353;
const ll P = 263;
const ld pi = acos(-1);
const ll inf = 1e9;

ll add(ll a, ll b) {
    if(a + b < 0) return a + b + mod;
    if(a + b >= mod) return a + b - mod;
    return a + b;
}

ll sub(ll a, ll b) {
    return (a - b + mod) % mod;
}

ll mul(ll a, ll b) {
    return a * 1LL * b % mod;
}

ll binpow(ll a, ll n) {
    ll res = 1LL;
    while(n) {
        if(n & 1) res = mul(res, a); // if(n % 2 == 1)
        a = mul(a, a);
        n >>= 1; //n / 2
    }
    return res;
}

ll inv(ll x) {//число х в степени -1
    return binpow(x, mod - 2);
}
void solve() {
    ll k, n;
    cin >> k >> n;
    ll delt = 0LL;
    set<ll> s;
    vector<pll> v;
    vector<ll> cords;
    cords.pb(-1);
    for(ll i = 1; i <= n; i++) {
        char a, b;
        ll x, y;
        cin >> a >> x >> b >> y;
        s.insert(x); s.insert(y);
        if(a == b) delt += abs(x - y);
        else {
            v.pb({x, y});
            cords.pb(x); cords.pb(y);
        }
    }
    if(k == 1) {
        ll ans = delt;
        sort(all(cords));
        ll b = cords[(int)sz(cords) / 2];
        for(auto [x, y]: v) {
            ans += (abs(b - x) + abs(b - y) + 1LL);
        }
        cout << ans << '\n';
    }
    else {
        ll ans = LLONG_MAX;
        for(auto k1: s) {
            for(auto k2: s) {
                if(k1 == k2) continue;
                ll cur = 0LL;
                for(auto [x, y]: v) {
                    cur += min((abs(k1 - x) + abs(k1 - y) + 1LL), (abs(k2 - x) + abs(k2 - y) + 1LL));
                }
                ans = min(ans, cur);
            }
        }
        cout << ans + delt << '\n';
    }
}
signed main() {
    speed;
    //file;
    int test = 1;
    //cin >> test;
    while(test--) {
        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 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct

Subtask #2
14.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 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 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 604 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 540 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 16 ms 4544 KB Output is correct
13 Correct 91 ms 15156 KB Output is correct
14 Correct 49 ms 4920 KB Output is correct
15 Correct 57 ms 9016 KB Output is correct
16 Correct 21 ms 5312 KB Output is correct
17 Correct 58 ms 14976 KB Output is correct
18 Correct 61 ms 14636 KB Output is correct
19 Correct 70 ms 14700 KB Output is correct
20 Correct 22 ms 5568 KB Output is correct
21 Correct 81 ms 15044 KB Output is correct

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 0 ms 348 KB Output is correct
4 Correct 9 ms 480 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 10 ms 348 KB Output is correct
9 Correct 10 ms 348 KB Output is correct
10 Correct 9 ms 480 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 10 ms 348 KB Output is correct

Subtask #4
0 / 32.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 Correct 9 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 10 ms 476 KB Output is correct
9 Correct 10 ms 344 KB Output is correct
10 Correct 9 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 10 ms 472 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 25 ms 508 KB Output is correct
15 Execution timed out 2047 ms 348 KB Time limit exceeded
16 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 0 ms 348 KB Output is correct
4 Correct 9 ms 476 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 11 ms 344 KB Output is correct
9 Correct 10 ms 476 KB Output is correct
10 Correct 9 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 10 ms 472 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 25 ms 508 KB Output is correct
15 Execution timed out 2066 ms 348 KB Time limit exceeded
16 Halted 0 ms 0 KB -