oj.uz

Submission #108287

# Submission time Handle Problem Language Result Execution time Memory
108287 2019-04-28T12:51:39 Z maksim_gaponov Palembang Bridges (APIO15_bridge) C++14
8 / 100
 2000 ms 4444 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define pb push_back
typedef pair<int, int> pii;
#define F first
#define S second
#define len(x) (int)(x).size()
const int INF = 1e18;

bool cmin(int &a, const int &b) {
	if (a > b) {
		a = b;
		return 1;
	}
	return 0;
}

void run() {
	int k, n;
	cin >> k >> n;
	int ans = 0;
	vector<pii> v;
	vector<int> vals;
	for (int i = 0; i < n; ++i) {
		char a, c;
		int b, d;
		cin >> a >> b >> c >> d;
		a -= 'A';
		c -= 'A';
		if (a == c) {
			ans += abs(b - d);
		} else {
			if (a)
				swap(b, d);
			v.pb({b, d});
			vals.pb(b);
			vals.pb(d);
		}
	}
	int ans2 = INF;
	if (len(vals) == 0)
		ans2 = 0;
	for (auto x : vals) {
		int cur_ans2 = 0;
		for (auto f : v) {
			cur_ans2 += abs(f.F - x) + abs(f.S - x) + 1;
		}
		cmin(ans2, cur_ans2);
	}
	// cout << ans << ' ' << ans2 << '\n';
	cout << ans + ans2 << '\n';
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
}

Subtask #1
8.0 / 8.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 7 ms 384 KB Output is correct
4 Correct 7 ms 428 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 8 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 7 ms 384 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 9 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Execution timed out 2041 ms 4444 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 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 Incorrect 3 ms 384 KB Output isn't correct
4 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 256 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -