oj.uz

Submission #83580

# Submission time Handle Problem Language Result Execution time Memory
83580 2018-11-09T12:14:53 Z ekrem Soccer (JOI17_soccer) C++
0 / 100
 3000 ms 124568 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define inf 1000000007
#define N 5005
using namespace std;

typedef pair < int , int > ii;

int n, m, k, a, b, c, x[N*N], y[N*N], dp[N][N], d[N][N], u[N][N];
int o[] = {1, -1, 0, 0};
int p[] = {0, 0, -1, 1};
queue < pair < int , ii > > q;

inline bool git(int i, int j){return !(i < 1 or j < 1 or i > n or j > m or u[i][j]);}

int f(int i, int j){
	int &r = dp[i][j];
	if(r != -1)
		return r;
	r = inf;
	if(i == x[k] and j == y[k])
		return r = 0;
	for(int ii = 1; ii <= n; ii++)
		r = min(r, c*abs(i - ii) + f(ii, j));
	for(int jj = 1; jj <= m; jj++)
		r = min(r, c*abs(j - jj) + f(i, jj));


	for(int ii = 1; ii <= n; ii++){
		r = min(r, a*abs(i - ii) + b + c*d[ii][j] + f(ii, j));
		// cout << i << " " << j << " = " << r << " -> " << ii << " " << j << " " << d[ii][j] << endl;
	}
	for(int jj = 1; jj <= m; jj++){
		r = min(r, a*abs(j - jj) + b + c*d[i][jj] + f(i, jj));
		// cout << i << " " << j << " = " << r << " -> " << i << " " << jj << " " << d[i][jj] << endl;
	}
	return r;
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("amk.txt", "w", stdout);

	memset(dp, -1, sizeof dp);

	scanf("%d %d %d %d %d %d",&n ,&m ,&a ,&b ,&c ,&k);
	n++;m++;
	for(int i = 1; i <= k; i++){
		scanf("%d %d",x + i ,y + i);
		x[i]++;y[i]++;
		q.push(mp(0, mp(x[i], y[i])));
		u[x[i]][y[i]] = 1;
	}
	while(!q.empty()){
		int xx = q.front().nd.st;
		int yy = q.front().nd.nd;
		int yol = q.front().st;
		q.pop();
		d[xx][yy] = yol;
		for(int k = 0; k < 4; k++)
			if(git(xx + o[k], yy + p[k])){
				q.push(mp(yol + 1, mp(xx + o[k], yy + p[k])));
				u[xx + o[k]][yy + p[k]] = 1;
			}
	}
	printf("%d\n", f(x[1], y[1]));
	return 0;
}

Compilation message

soccer.cpp: In function 'int main()':
soccer.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d %d %d",&n ,&m ,&a ,&b ,&c ,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",x + i ,y + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 105976 KB Output is correct
2 Correct 83 ms 105976 KB Output is correct
3 Execution timed out 3053 ms 124256 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3040 ms 124568 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 105976 KB Output is correct
2 Correct 83 ms 105976 KB Output is correct
3 Execution timed out 3053 ms 124256 KB Time limit exceeded
4 Halted 0 ms 0 KB -