oj.uz

Submission #23777

# Submission time Handle Problem Language Result Execution time Memory
23777 2017-05-25T18:24:02 Z rubabredwan Palembang Bridges (APIO15_bridge) C++14
31 / 100
 2000 ms 15204 KB 
/*  Bismillahir Rahmanir Rahim  */

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;
const long long oo = 1e18;

int k, n; 
long long pos[N][2];
char fk[N][2];

void solve_big(){
    long long ret = oo;
    for(int i = 1; i <= n; i++){
        for(int a = 0; a <= 1; a++){
            for(int j = 1; j <= n; j++){
                for(int b = 0; b <= 1; b++){
                    long long ans = 0;
                    for(int f = 1; f <= n; f++){
                        if(fk[f][0] == fk[f][1]){
                            ans += abs(pos[f][1] - pos[f][0]);
                            continue;
                        }
                        long long aa = 1LL + abs(pos[f][0] - pos[i][a]) + abs(pos[f][1] - pos[i][a]);
                        long long bb = 1LL + abs(pos[f][0] - pos[j][b]) + abs(pos[f][1] - pos[j][b]);
                        ans += min(aa, bb);
                    }
                    ret = min(ret, ans);
                }
            }
        }
    }
    cout << ret << endl;
}

void solve_small(){
	long long ret = oo;
	long long add = 0;
	long long pre = 0;
	long long suf = 0;
    vector<long long> gg;
    set<long long>ds;
	for(int i = 1; i <= n; ++i){
		if(fk[i][0] == fk[i][1]) add += abs(pos[i][1] - pos[i][0]);
		else{
			gg.push_back(pos[i][0]);
			gg.push_back(pos[i][1]);
            suf += pos[i][0];
            suf += pos[i][1];
            ++add;
        }
        ds.insert(pos[i][0]);
        ds.insert(pos[i][1]);
	}
	sort(gg.begin(), gg.end());
    if(gg.size() == 0) ret = 0;
    int ptr = 0;
    long long aa = 0, bb = gg.size();
    for(auto u : ds){

        while(ptr < gg.size() && gg[ptr] <= u){
            pre += gg[ptr];
            suf -= gg[ptr];
            ++aa;
            --bb;
            ++ptr;
        }

		long long ans = 0;

        ans += (u * aa) - pre;
        ans += suf - (u * bb);

        ret = min(ret, ans);
	}
	cout << ret + add << endl;
}

int main(){
    cin >> k >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= 1; j++){
            cin >> fk[i][j] >> pos[i][j];
        }
    }
    if(k == 1) solve_small();
    else solve_big();
    return 0;
}

Compilation message

bridge.cpp: In function 'void solve_small()':
bridge.cpp:63:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(ptr < gg.size() && gg[ptr] <= u){
                   ^

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3780 KB Output is correct
2 Correct 0 ms 3780 KB Output is correct
3 Correct 0 ms 3780 KB Output is correct
4 Correct 0 ms 3912 KB Output is correct
5 Correct 0 ms 3912 KB Output is correct
6 Correct 0 ms 3780 KB Output is correct
7 Correct 0 ms 3912 KB Output is correct
8 Correct 0 ms 3912 KB Output is correct
9 Correct 0 ms 3912 KB Output is correct
10 Correct 0 ms 3780 KB Output is correct
11 Correct 0 ms 3912 KB Output is correct
12 Correct 83 ms 6936 KB Output is correct
13 Correct 339 ms 15204 KB Output is correct
14 Correct 113 ms 7388 KB Output is correct
15 Correct 176 ms 10352 KB Output is correct
16 Correct 93 ms 6936 KB Output is correct
17 Correct 179 ms 15204 KB Output is correct
18 Correct 183 ms 15204 KB Output is correct
19 Correct 283 ms 14820 KB Output is correct
20 Correct 119 ms 6936 KB Output is correct
21 Correct 216 ms 15204 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3780 KB Output is correct
2 Correct 0 ms 3780 KB Output is correct
3 Correct 16 ms 3780 KB Output is correct
4 Correct 19 ms 3780 KB Output is correct
5 Correct 3 ms 3780 KB Output is correct
6 Correct 0 ms 3780 KB Output is correct
7 Correct 16 ms 3780 KB Output is correct
8 Correct 16 ms 3780 KB Output is correct
9 Correct 16 ms 3780 KB Output is correct
10 Correct 23 ms 3780 KB Output is correct
11 Correct 23 ms 3780 KB Output is correct
12 Correct 16 ms 3780 KB Output is correct
13 Execution timed out 2000 ms 3780 KB Execution timed out
14 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3780 KB Output is correct
2 Correct 0 ms 3780 KB Output is correct
3 Correct 16 ms 3780 KB Output is correct
4 Correct 16 ms 3780 KB Output is correct
5 Correct 3 ms 3780 KB Output is correct
6 Correct 0 ms 3780 KB Output is correct
7 Correct 33 ms 3780 KB Output is correct
8 Correct 29 ms 3780 KB Output is correct
9 Correct 19 ms 3780 KB Output is correct
10 Correct 23 ms 3780 KB Output is correct
11 Correct 19 ms 3780 KB Output is correct
12 Correct 16 ms 3780 KB Output is correct
13 Execution timed out 2000 ms 3780 KB Execution timed out
14 Halted 0 ms 0 KB -