oj.uz

Submission #380469

# Submission time Handle Problem Language Result Execution time Memory
380469 2021-03-22T02:53:06 Z LittleCube Palembang Bridges (APIO15_bridge) C++14
31 / 100
 2000 ms 3800 KB 
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#pragma pack(0)
#define int long long
#define ll long long
#define pii pair<ll, ll>
#define pll pair<ll, ll>
#define F first
#define S second
#define MOD 1000000007
#define MOD2 998244353
#define _INFINITY 9223372036854775807
#define fast ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

ll n, k, ans1, ans2 = 1e18;
vector<int> v;
vector<pii> u;
signed main()
{
    fast;
    cin >> k >> n;
    for (int i = 1; i <= n; i++)
    {
        char c1, c2;
        int p1, p2;
        cin >> c1 >> p1 >> c2 >> p2;
        if (c1 == c2)
            ans1 += abs(p1 - p2);
        else
        {
            v.emplace_back(p1);
            v.emplace_back(p2);
            u.emplace_back(make_pair(p1, p2));
        }
    }
    sort(v.begin(), v.end());

    ans2 = v.size() / 2;
    if (!v.empty())
    {
        int mid = v[v.size() / 2];
        for (int i : v)
            ans2 += abs(mid - i);
    }
    if (k == 1)
        cout << ans2 + ans1 << '\n';

    else
    {
        for (int i : v)
            for (int j : v)
            {
                ll res = 0;
                for (pii p : u)
                    res += min(abs(p.F - i) + abs(p.S - i) + 1, abs(p.F - j) + abs(p.S - j) + 1);
                ans2 = min(ans2, res);
            }
        cout << ans1 + ans2 << '\n';
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 396 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 25 ms 3672 KB Output is correct
13 Correct 49 ms 3692 KB Output is correct
14 Correct 36 ms 3800 KB Output is correct
15 Correct 30 ms 2392 KB Output is correct
16 Correct 35 ms 3672 KB Output is correct
17 Correct 34 ms 3672 KB Output is correct
18 Correct 41 ms 3672 KB Output is correct
19 Correct 45 ms 3672 KB Output is correct
20 Correct 33 ms 3672 KB Output is correct
21 Correct 45 ms 3672 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 11 ms 364 KB Output is correct
4 Correct 13 ms 364 KB Output is correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 13 ms 364 KB Output is correct
8 Correct 13 ms 364 KB Output is correct
9 Correct 14 ms 364 KB Output is correct
10 Correct 13 ms 364 KB Output is correct
11 Correct 14 ms 364 KB Output is correct
12 Correct 13 ms 364 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 9 ms 364 KB Output is correct
4 Correct 10 ms 364 KB Output is correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 13 ms 364 KB Output is correct
8 Correct 13 ms 364 KB Output is correct
9 Correct 13 ms 364 KB Output is correct
10 Correct 13 ms 364 KB Output is correct
11 Correct 16 ms 364 KB Output is correct
12 Correct 13 ms 364 KB Output is correct
13 Execution timed out 2086 ms 364 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 13 ms 364 KB Output is correct
4 Correct 10 ms 364 KB Output is correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 14 ms 364 KB Output is correct
8 Correct 13 ms 364 KB Output is correct
9 Correct 13 ms 364 KB Output is correct
10 Correct 14 ms 364 KB Output is correct
11 Correct 16 ms 364 KB Output is correct
12 Correct 13 ms 364 KB Output is correct
13 Execution timed out 2073 ms 364 KB Time limit exceeded
14 Halted 0 ms 0 KB -