oj.uz

Submission #894552

# Submission time Handle Problem Language Result Execution time Memory
894552 2023-12-28T12:39:04 Z pcc Soccer (JOI17_soccer) C++14
0 / 100
 93 ms 7236 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 550;
const ll inf = 1e18;
int N,M,K,A,B,C;
ll dp[mxn][mxn];
ll player[mxn][mxn];
pll arr[mxn*mxn];
priority_queue<tlll,vector<tlll>,greater<tlll>> pq;
pii dir[] = {{0,1},{0,-1},{1,0},{-1,0}};

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M>>A>>B>>C>>K;
	for(int i = 1;i<=K;i++)cin>>arr[i].fs>>arr[i].sc;
	for(auto &i:player)for(auto &j:i)j = inf;
	for(int i = 0;i<=N;i++)for(int j = 0;j<=M;j++){
		for(int k = 1;k<=K;k++){
			player[i][j] = min(player[i][j],abs(arr[k].fs-i)+abs(arr[k].sc-j));
		}
	}
	for(auto &i:dp)for(auto &j:i)j = inf;
	dp[arr[1].fs][arr[1].sc] = 0;
	pq.push(make_tuple(0,arr[1].fs,arr[1].sc));
	while(!pq.empty()){
		auto tt = pq.top();
		pq.pop();
		int r = get<1>(tt),c = get<2>(tt),ds = get<0>(tt);
		if(ds != dp[r][c])continue;
		//cout<<r<<' '<<c<<":"<<ds<<endl;
		for(auto &d:dir){
			int nr = r+d.fs,nc = c+d.sc;
			if(nr<0||nr>N||nc<0||nc>M)continue;
			if(dp[nr][nc]>dp[r][c]+C){
				dp[nr][nc] = dp[r][c]+C;
				pq.push(make_tuple(dp[nr][nc],nr,nc));
			}
			nr = r+d.fs,nc = c+d.sc;
			int pt = 1;
			while(nr>=0&&nr<=N&&nc>=0&&nc<=M){
				if(dp[nr][nc]>dp[r][c]+A*pt+B+C*player[nr][nc]){
					dp[nr][nc] = dp[r][c]+A*pt+B+C*player[nr][nc];
					pq.push(make_tuple(dp[nr][nc],nr,nc));
				}
				pt++;
				nr += d.fs,nc += d.sc;
			}
		}
	}
	/*
	for(int i = 0;i<=N;i++){
		for(int j = 0;j<=M;j++)cout<<setw(3)<<dp[i][j]<<' ';
		cout<<endl;
	}

   */
	cout<<dp[arr[K].fs][arr[K].sc];
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 7132 KB Output is correct
2 Correct 3 ms 5976 KB Output is correct
3 Incorrect 3 ms 5724 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

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

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 7132 KB Output is correct
2 Correct 3 ms 5976 KB Output is correct
3 Incorrect 3 ms 5724 KB Output isn't correct
4 Halted 0 ms 0 KB -