oj.uz

Submission #206616

# Submission time Handle Problem Language Result Execution time Memory
206616 2020-03-04T08:50:25 Z opukittpceno_hhr Soccer (JOI17_soccer) C++17
0 / 100
 3000 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);
		}
	}

	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	cout << d[0][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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 376 KB Output is correct
2 Correct 21 ms 376 KB Output is correct
3 Correct 22 ms 376 KB Output is correct
4 Correct 24 ms 376 KB Output is correct
5 Correct 79 ms 712 KB Output is correct
6 Execution timed out 3037 ms 8312 KB Time limit exceeded
7 Halted 0 ms 0 KB -

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 -