oj.uz

Submission #229650

# Submission time Handle Problem Language Result Execution time Memory
229650 2020-05-05T16:32:38 Z nvmdava Palembang Bridges (APIO15_bridge) C++17
100 / 100
 309 ms 14504 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 100005
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;

vector<pair<int, int> > v;
ll tmp;

multiset<int>::iterator it;
multiset<int> in;
ll sum, all;
ll pr[N], su[N];

int n;

void wtf(ll* ans){
    all = sum = 0;
    in.clear();
    in.insert(-1);
    it = in.begin();
    int i = 1;
    for(auto& x : v){
        all += x.ff;
        in.insert(x.ff);
        in.insert(x.ss);
        if(x.ss < *it){
            sum += x.ff + x.ss - (*it);
            --it;
        } else if(x.ff >= *it){
            ++it;
            sum += *it;
        } else {
            sum += x.ff;
        }
        ans[i] = all - sum;
        ++i;
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int k;
    cin>>k>>n;

    while(n--){
        char c, d;
        int a, b;
        cin>>c>>a>>d>>b;
        tmp += abs(a - b);
        if(c == d) continue;
        ++tmp;
        if(a > b) swap(a, b);
        v.push_back({a, b});
    }
    sort(v.begin(), v.end(), [](const pair<int, int>& lhs, const pair<int, int>& rhs){
        return lhs.ff + lhs.ss < rhs.ff + rhs.ss;
    });

    n = v.size();
    
    wtf(pr);
    reverse(v.begin(), v.end());
    wtf(su);


    if(k == 1){
        cout<<pr[n] * 2 + tmp;
    } else {
        ll mn = pr[n];
        for(int i = 0; i <= n; ++i){
            mn = min(pr[i] + su[n - i], mn);
        }
        cout<<mn * 2 + tmp;
    }
}

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 108 ms 12908 KB Output is correct
13 Correct 254 ms 14448 KB Output is correct
14 Correct 224 ms 12140 KB Output is correct
15 Correct 113 ms 8692 KB Output is correct
16 Correct 122 ms 13808 KB Output is correct
17 Correct 127 ms 14504 KB Output is correct
18 Correct 119 ms 14064 KB Output is correct
19 Correct 121 ms 14448 KB Output is correct
20 Correct 117 ms 13936 KB Output is correct
21 Correct 134 ms 14188 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Correct 6 ms 512 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 6 ms 512 KB Output is correct
20 Correct 5 ms 512 KB Output is correct
21 Correct 6 ms 512 KB Output is correct
22 Correct 6 ms 512 KB Output is correct
23 Correct 5 ms 512 KB Output is correct
24 Correct 5 ms 512 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 6 ms 512 KB Output is correct
14 Correct 6 ms 512 KB Output is correct
15 Correct 6 ms 512 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 512 KB Output is correct
20 Correct 5 ms 512 KB Output is correct
21 Correct 6 ms 512 KB Output is correct
22 Correct 5 ms 512 KB Output is correct
23 Correct 5 ms 512 KB Output is correct
24 Correct 5 ms 512 KB Output is correct
25 Correct 114 ms 12908 KB Output is correct
26 Correct 214 ms 13164 KB Output is correct
27 Correct 261 ms 13808 KB Output is correct
28 Correct 309 ms 14444 KB Output is correct
29 Correct 280 ms 14448 KB Output is correct
30 Correct 106 ms 7796 KB Output is correct
31 Correct 119 ms 13800 KB Output is correct
32 Correct 128 ms 14448 KB Output is correct
33 Correct 111 ms 14060 KB Output is correct
34 Correct 129 ms 14448 KB Output is correct
35 Correct 119 ms 13936 KB Output is correct
36 Correct 130 ms 14188 KB Output is correct
37 Correct 108 ms 13188 KB Output is correct