답안 #45014 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
45014	2018-04-10T14:47:43 Z	RezwanArefin01	Palembang Bridges (APIO15_bridge)	C++17	31 / 100	2000 ms	2440 KB

bridge

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

vector<int> pos; vector<ii> v;
ll get(int x) { ll ret = 0;
	for(ii a : v) ret += abs(a.first - x) + abs(a.second - x) + 1; 
	return ret;
}
int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
	freopen("in", "r", stdin);
#endif
	int n, k; scanf("%d %d", &k, &n); 
	ll pre = 0; 
	for(int i = 0; i < n; i++) {
		char p, q; int s, t;
		scanf(" %c %d %c %d", &p, &s, &q, &t);
		if(p == q) pre += abs(s - t); 
		else v.emplace_back(s, t), pos.push_back(s), pos.push_back(t); 
	}
	sort(pos.begin(), pos.end()); 
	if(k == 1) {
		int sz = pos.size(); ll mn = 0;
		if(v.size()) {
			mn = get(pos[sz / 2]);
			if(sz / 2 + 1 < sz) mn = min(mn, get(pos[sz / 2 + 1])); 
		} printf("%lld\n", mn + pre);
	} else {
		pos.erase(unique(pos.begin(), pos.end()), pos.end());
		ll ans = 1e18;
		if(!pos.size()) ans = 0; else
		for(int i = 0; i < pos.size(); i++) {
			for(int j = i + 1; j < pos.size(); j++) {
				ll tot = 0;
				int x = pos[i], y = pos[j]; 
				for(ii a : v) {
					tot += min(abs(a.first - x) + abs(a.second - x),
							   abs(a.first - y) + abs(a.second - y)) + 1;
				} ans = min(ans, tot);
			}
		} printf("%lld\n", ans + pre);
	}
}

Compilation message

bridge.cpp: In function 'int main(int, const char**)':
bridge.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < pos.size(); i++) {
                  ~~^~~~~~~~~~~~
bridge.cpp:39:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = i + 1; j < pos.size(); j++) {
                       ~~^~~~~~~~~~~~
bridge.cpp:19:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, k; scanf("%d %d", &k, &n); 
            ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %d %c %d", &p, &s, &q, &t);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	536 KB	Output is correct
4	Correct	2 ms	556 KB	Output is correct
5	Correct	3 ms	640 KB	Output is correct
6	Correct	2 ms	640 KB	Output is correct
7	Correct	2 ms	640 KB	Output is correct
8	Correct	2 ms	640 KB	Output is correct
9	Correct	3 ms	640 KB	Output is correct
10	Correct	3 ms	640 KB	Output is correct
11	Correct	2 ms	640 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	640 KB	Output is correct
2	Correct	2 ms	640 KB	Output is correct
3	Correct	2 ms	640 KB	Output is correct
4	Correct	3 ms	640 KB	Output is correct
5	Correct	2 ms	640 KB	Output is correct
6	Correct	2 ms	640 KB	Output is correct
7	Correct	3 ms	640 KB	Output is correct
8	Correct	2 ms	640 KB	Output is correct
9	Correct	2 ms	640 KB	Output is correct
10	Correct	3 ms	640 KB	Output is correct
11	Correct	2 ms	640 KB	Output is correct
12	Correct	46 ms	2380 KB	Output is correct
13	Correct	75 ms	2380 KB	Output is correct
14	Correct	55 ms	2420 KB	Output is correct
15	Correct	44 ms	2420 KB	Output is correct
16	Correct	51 ms	2420 KB	Output is correct
17	Correct	53 ms	2420 KB	Output is correct
18	Correct	68 ms	2420 KB	Output is correct
19	Correct	71 ms	2440 KB	Output is correct
20	Correct	52 ms	2440 KB	Output is correct
21	Correct	65 ms	2440 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2440 KB	Output is correct
2	Correct	2 ms	2440 KB	Output is correct
3	Correct	2 ms	2440 KB	Output is correct
4	Correct	3 ms	2440 KB	Output is correct
5	Correct	2 ms	2440 KB	Output is correct
6	Correct	2 ms	2440 KB	Output is correct
7	Correct	2 ms	2440 KB	Output is correct
8	Correct	4 ms	2440 KB	Output is correct
9	Correct	4 ms	2440 KB	Output is correct
10	Correct	4 ms	2440 KB	Output is correct
11	Correct	2 ms	2440 KB	Output is correct
12	Correct	5 ms	2440 KB	Output is correct

Subtask #4
0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2440 KB	Output is correct
2	Correct	2 ms	2440 KB	Output is correct
3	Correct	2 ms	2440 KB	Output is correct
4	Correct	4 ms	2440 KB	Output is correct
5	Correct	2 ms	2440 KB	Output is correct
6	Correct	2 ms	2440 KB	Output is correct
7	Correct	2 ms	2440 KB	Output is correct
8	Correct	5 ms	2440 KB	Output is correct
9	Correct	4 ms	2440 KB	Output is correct
10	Correct	4 ms	2440 KB	Output is correct
11	Correct	2 ms	2440 KB	Output is correct
12	Correct	4 ms	2440 KB	Output is correct
13	Correct	2 ms	2440 KB	Output is correct
14	Correct	11 ms	2440 KB	Output is correct
15	Execution timed out	2056 ms	2440 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-

Subtask #5
0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2440 KB	Output is correct
2	Correct	2 ms	2440 KB	Output is correct
3	Correct	2 ms	2440 KB	Output is correct
4	Correct	4 ms	2440 KB	Output is correct
5	Correct	2 ms	2440 KB	Output is correct
6	Correct	2 ms	2440 KB	Output is correct
7	Correct	2 ms	2440 KB	Output is correct
8	Correct	4 ms	2440 KB	Output is correct
9	Correct	4 ms	2440 KB	Output is correct
10	Correct	5 ms	2440 KB	Output is correct
11	Correct	2 ms	2440 KB	Output is correct
12	Correct	4 ms	2440 KB	Output is correct
13	Correct	2 ms	2440 KB	Output is correct
14	Correct	8 ms	2440 KB	Output is correct
15	Execution timed out	2061 ms	2440 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-

답안 #45014

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 14.0 / 14.0

Subtask #3 9.0 / 9.0

Subtask #4 0 / 32.0

Subtask #5 0 / 37.0

Subtask #1
8.0 / 8.0

Subtask #2
14.0 / 14.0

Subtask #3
9.0 / 9.0

Subtask #4
0 / 32.0

Subtask #5
0 / 37.0