oj.uz

Submission #894553

# Submission time Handle Problem Language Result Execution time Memory
894553 2023-12-28T12:39:52 Z pcc Soccer (JOI17_soccer) C++14
35 / 100
 1232 ms 262144 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>
#define int ll

const int mxn = 550;
const ll inf = 4e18;
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}};

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];
}

Compilation message

soccer.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main(){
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 7124 KB Output is correct
2 Correct 3 ms 6172 KB Output is correct
3 Correct 660 ms 12992 KB Output is correct
4 Correct 1232 ms 56484 KB Output is correct
5 Correct 147 ms 10192 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 12140 KB Output is correct
2 Correct 724 ms 12608 KB Output is correct
3 Correct 504 ms 12444 KB Output is correct
4 Correct 596 ms 12344 KB Output is correct
5 Correct 526 ms 12612 KB Output is correct
6 Correct 948 ms 13760 KB Output is correct
7 Correct 961 ms 12364 KB Output is correct
8 Correct 963 ms 12484 KB Output is correct
9 Correct 1027 ms 12744 KB Output is correct
10 Correct 122 ms 7116 KB Output is correct
11 Correct 959 ms 13388 KB Output is correct
12 Correct 737 ms 13108 KB Output is correct
13 Correct 661 ms 13648 KB Output is correct
14 Correct 1037 ms 11848 KB Output is correct
15 Correct 773 ms 13976 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 7124 KB Output is correct
2 Correct 3 ms 6172 KB Output is correct
3 Correct 660 ms 12992 KB Output is correct
4 Correct 1232 ms 56484 KB Output is correct
5 Correct 147 ms 10192 KB Output is correct
6 Correct 698 ms 12140 KB Output is correct
7 Correct 724 ms 12608 KB Output is correct
8 Correct 504 ms 12444 KB Output is correct
9 Correct 596 ms 12344 KB Output is correct
10 Correct 526 ms 12612 KB Output is correct
11 Correct 948 ms 13760 KB Output is correct
12 Correct 961 ms 12364 KB Output is correct
13 Correct 963 ms 12484 KB Output is correct
14 Correct 1027 ms 12744 KB Output is correct
15 Correct 122 ms 7116 KB Output is correct
16 Correct 959 ms 13388 KB Output is correct
17 Correct 737 ms 13108 KB Output is correct
18 Correct 661 ms 13648 KB Output is correct
19 Correct 1037 ms 11848 KB Output is correct
20 Correct 773 ms 13976 KB Output is correct
21 Runtime error 284 ms 262144 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -