oj.uz

Submission #23776

# Submission time Handle Problem Language Result Execution time Memory
23776 2017-05-25T18:12:43 Z rubabredwan Palembang Bridges (APIO15_bridge) C++14
9 / 100
 33 ms 2020 KB 
/*  Bismillahir Rahmanir Rahim  */

#include <bits/stdc++.h>

using namespace std;

const int N = 105;
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;
	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 += 1LL;
		}
	}
	sort(gg.begin(), gg.end());
    if(gg.size() == 0) ret = 0;
	for(long long i = 0; i < gg.size(); ++i){
		long long ans = 0;
		ans += (gg[i] * i) - pre;
		ans += suf - (gg[i] * 1LL * (gg.size() - i));
		pre += gg[i];
		suf -= gg[i];
		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:56:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(long long i = 0; i < gg.size(); ++i){
                         ^

Subtask #1
0 / 8.0

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

Subtask #2
0 / 14.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2020 KB Output is correct
2 Correct 0 ms 2020 KB Output is correct
3 Correct 23 ms 2020 KB Output is correct
4 Correct 16 ms 2020 KB Output is correct
5 Correct 3 ms 2020 KB Output is correct
6 Correct 0 ms 2020 KB Output is correct
7 Correct 16 ms 2020 KB Output is correct
8 Correct 16 ms 2020 KB Output is correct
9 Correct 19 ms 2020 KB Output is correct
10 Correct 16 ms 2020 KB Output is correct
11 Correct 29 ms 2020 KB Output is correct
12 Correct 16 ms 2020 KB Output is correct
13 Incorrect 0 ms 2020 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2020 KB Output is correct
2 Correct 0 ms 2020 KB Output is correct
3 Correct 16 ms 2020 KB Output is correct
4 Correct 19 ms 2020 KB Output is correct
5 Correct 3 ms 2020 KB Output is correct
6 Correct 0 ms 2020 KB Output is correct
7 Correct 19 ms 2020 KB Output is correct
8 Correct 16 ms 2020 KB Output is correct
9 Correct 16 ms 2020 KB Output is correct
10 Correct 16 ms 2020 KB Output is correct
11 Correct 16 ms 2020 KB Output is correct
12 Correct 16 ms 2020 KB Output is correct
13 Incorrect 0 ms 2020 KB Output isn't correct
14 Halted 0 ms 0 KB -