oj.uz

Submission #107010

# Submission time Handle Problem Language Result Execution time Memory
107010 2019-04-21T12:50:06 Z someone_aa Palembang Bridges (APIO15_bridge) C++17
22 / 100
 177 ms 3972 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
ll s[maxn], f[maxn], n, k;
char szone[maxn], fzone[maxn];

int main() {
    cin>>k>>n;
    ll result = 0LL;

    vector<ll>v;
    vector<pair<ll,ll> > vv;
    for(int i=1;i<=n;i++) {
        cin>>szone[i]>>s[i];
        cin>>fzone[i]>>f[i];
        if(szone[i] == fzone[i]) result += abs(f[i] - s[i]);
        if(szone[i] != fzone[i]) {
            v.pb(s[i]);
            v.pb(f[i]);
        }

        if(s[i] > f[i]) swap(s[i], f[i]);
    }

    if(v.size() == 0) {
        cout<<result;
        return 0;
    }

    if(k == 1) {
        ll mintemp = LLONG_MAX;
        sort(v.begin(), v.end());

        // 0 1 2 3

        int half = v[0];
        if(v.size() > 1)
            half = v[v.size()/2-1];
        else half = v.back();
        for(int d=half-1;d<=half+1;d++) {
            ll temp = 0LL;
            for(int i=1;i<=n;i++) {
                if(szone[i] != fzone[i]) {
                    temp += abs(f[i] - d) + abs(s[i] - d) + 1;
                }
            }
            //cout<<d<<": "<<temp<<"\n";
            mintemp = min(mintemp, temp);
        }

        result += mintemp;
        cout<<result<<"\n";
        return 0;
    }
    else if(k == 2) {
        sort(v.begin(), v.end());
        ll mintemp = LLONG_MAX;
        for(int i:v) {
            vector<int>v2;
            ll temp = 0LL;
            for(int j=1;j<=n;j++) {
                if(fzone[j] == szone[j]) continue;

                if(!(s[j] <= i && i <= f[j])) {
                    v2.pb(s[j]);
                    v2.pb(f[j]);
                }
                else {
                    temp += abs(s[j] - i) + abs(f[j] - i);
                }
            }

            /*cout<<i<<": \n";
            for(int i:v2) {
                cout<<i<<" ";
            } cout<<" - "<<temp<<" -> ";*/

            sort(v2.begin(), v2.end());

            if(v2.size() == 0) continue;
            int half = v2[0];
            if(v2.size() > 1)
                half = v2[v2.size()/2-1] ;
            else half = v2.back();

            for(int j:v2) {
                temp += abs(j - half);
            }

            temp += v.size() / 2;

            //cout<<temp<<"\n";

            mintemp = min(mintemp, temp);
        }
        cout<<result+mintemp;
    }

    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 63 ms 3944 KB Output is correct
13 Correct 131 ms 3940 KB Output is correct
14 Correct 78 ms 3832 KB Output is correct
15 Correct 92 ms 2536 KB Output is correct
16 Correct 135 ms 3904 KB Output is correct
17 Correct 177 ms 3940 KB Output is correct
18 Correct 133 ms 3856 KB Output is correct
19 Correct 131 ms 3852 KB Output is correct
20 Correct 125 ms 3940 KB Output is correct
21 Correct 143 ms 3972 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Incorrect 3 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Incorrect 4 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Incorrect 3 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -