oj.uz

Submission #206617

# Submission time Handle Problem Language Result Execution time Memory
206617 2020-03-04T08:53:24 Z opukittpceno_hhr Soccer (JOI17_soccer) C++17
30 / 100
 1796 ms 8312 KB 
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <random>

using namespace std;

#define int long long

const int INF = 1e18 + 239;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int h, w, a, b, c, n;
	cin >> h >> w >> a >> b >> c >> n;
	h++;
	w++;
	vector<int> s(n);
	vector<int> t(n);
	for (int i = 0; i < n; i++) {
		cin >> s[i] >> t[i];
	}
	auto cost = [&](int i, int j) {
		if (i == j) return (int)0;
		//move i
		int ans = INF;
		for (int tj = 0; tj < w; tj++) {
			int mi = s[j];
			int mj = tj;
			int cur = c * (abs(s[i] - mi) + abs(t[i] - mj)) + b + a * (abs(mi - s[j]));
			if (mi == s[j] && mj == t[j]) cur -= b;

			ans = min(ans, cur);
		}
		for (int ti = 0; ti < h; ti++) {
			int mi = ti;
			int mj = t[j];
			int cur = c * (abs(s[i] - mi) + abs(t[i] - mj)) + b + a * (abs(mj - t[j]));
			if (mi == s[j] && mj == t[j]) cur -= b;
			ans = min(ans, cur);
		}
		return ans;
	};
	vector<vector<int>> d(n, vector<int> (n, INF));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			d[i][j] = cost(i, j);
		}
	}
	vector<int> used(n);
	vector<int> rd(n, INF);
	rd[0] = 0;
	for (int it = 0; it < n; it++) {
		int who = -1;
		for (int i = 0; i < n; i++) {
			if (used[i]) continue;
			if (who == -1 || rd[who] > rd[i]) who = i;
		}
		used[who] = 1;
		for (int j = 0; j < n; j++) {
			rd[j] = min(rd[j], rd[who] + d[who][j]);
		}
	}
	cout << rd[n - 1] << endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 376 KB Output is correct
2 Correct 16 ms 376 KB Output is correct
3 Correct 20 ms 376 KB Output is correct
4 Correct 22 ms 248 KB Output is correct
5 Correct 69 ms 632 KB Output is correct
6 Correct 1795 ms 8272 KB Output is correct
7 Correct 1791 ms 8312 KB Output is correct
8 Correct 1788 ms 8312 KB Output is correct
9 Correct 1796 ms 8312 KB Output is correct
10 Correct 1049 ms 8312 KB Output is correct
11 Correct 1783 ms 8312 KB Output is correct
12 Correct 44 ms 504 KB Output is correct
13 Correct 1621 ms 8312 KB Output is correct
14 Correct 1790 ms 8312 KB Output is correct
15 Correct 1614 ms 8280 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -