oj.uz

Submission #23774

# Submission time Handle Problem Language Result Execution time Memory
23774 2017-05-25T17:52:56 Z rubabredwan Palembang Bridges (APIO15_bridge) C++14
17 / 100
 2000 ms 3776 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;
	for(int i = 1; i <= n; ++i){
		for(int a = 0; a <= 1; a++){
	        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]);
                ans += aa;
            }
            ret = min(ret, ans);
        }
	}
	cout << ret << 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;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
0 / 14.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3776 KB Output is correct
2 Correct 0 ms 3776 KB Output is correct
3 Correct 16 ms 3776 KB Output is correct
4 Correct 16 ms 3776 KB Output is correct
5 Correct 3 ms 3776 KB Output is correct
6 Correct 0 ms 3776 KB Output is correct
7 Correct 16 ms 3776 KB Output is correct
8 Correct 16 ms 3776 KB Output is correct
9 Correct 16 ms 3776 KB Output is correct
10 Correct 16 ms 3776 KB Output is correct
11 Correct 16 ms 3776 KB Output is correct
12 Correct 16 ms 3776 KB Output is correct
13 Execution timed out 2000 ms 3776 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 3776 KB Output is correct
2 Correct 0 ms 3776 KB Output is correct
3 Correct 16 ms 3776 KB Output is correct
4 Correct 16 ms 3776 KB Output is correct
5 Correct 3 ms 3776 KB Output is correct
6 Correct 0 ms 3776 KB Output is correct
7 Correct 16 ms 3776 KB Output is correct
8 Correct 23 ms 3776 KB Output is correct
9 Correct 29 ms 3776 KB Output is correct
10 Correct 23 ms 3776 KB Output is correct
11 Correct 16 ms 3776 KB Output is correct
12 Correct 16 ms 3776 KB Output is correct
13 Execution timed out 2000 ms 3776 KB Execution timed out
14 Halted 0 ms 0 KB -