oj.uz

Submission #894562

# Submission time Handle Problem Language Result Execution time Memory
894562 2023-12-28T12:52:41 Z pcc Soccer (JOI17_soccer) C++14
35 / 100
 1189 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}};
ll lu[mxn][mxn],rd[mxn][mxn],ru[mxn][mxn],ld[mxn][mxn];

main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	for(auto &i:lu)for(auto &j:i)j = inf;//r+c+lu[r][c]
	for(auto &i:rd)for(auto &j:i)j = inf;
	for(auto &i:ru)for(auto &j:i)j = inf;
	for(auto &i:ld)for(auto &j:i)j = inf;
	for(auto &i:player)for(auto &j:i)j = inf;
	for(auto &i:dp)for(auto &j:i)j = inf;
	cin>>N>>M>>A>>B>>C>>K;
	N++,M++;
	for(int i = 0;i<K;i++){
		int r,c;
		cin>>arr[i].fs>>arr[i].sc;
		arr[i].fs++,arr[i].sc++;
		r = arr[i].fs,c = arr[i].sc;
		lu[r][c] = min(lu[r][c],-r-c);
		ld[r][c] = min(ld[r][c],r-c);
		ru[r][c] = min(ru[r][c],c-r);
		rd[r][c] = min(rd[r][c],r+c);
	}
	for(int i = 1;i<=N;i++)for(int j = 1;j<=M;j++)lu[i][j] = min({lu[i][j],lu[i-1][j],lu[i][j-1]});
	for(int i = N;i>=1;i--)for(int j = M;j>=1;j--)rd[i][j] = min({rd[i][j],rd[i+1][j],rd[i][j+1]});
	for(int i = 1;i<=N;i++)for(int j = M;j>=1;j--)ru[i][j] = min({ru[i][j],ru[i-1][j],ru[i][j+1]});
	for(int i = N;i>=1;i--)for(int j = 1;j<=M;j++)ld[i][j] = min({ld[i][j],ld[i+1][j],ld[i][j-1]});
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=M;j++){
			player[i][j] = min({i+j+lu[i][j],-i-j+rd[i][j],-i+j+ld[i][j],i-j+ru[i][j]});
		}
	}

	dp[arr[0].fs][arr[0].sc] = 0;
	pq.push(make_tuple(0,arr[0].fs,arr[0].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-1].fs][arr[K-1].sc];
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 18900 KB Output is correct
2 Correct 4 ms 17692 KB Output is correct
3 Correct 697 ms 24800 KB Output is correct
4 Correct 1189 ms 68200 KB Output is correct
5 Correct 161 ms 20424 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 688 ms 25292 KB Output is correct
2 Correct 707 ms 23752 KB Output is correct
3 Correct 488 ms 24260 KB Output is correct
4 Correct 637 ms 24768 KB Output is correct
5 Correct 521 ms 25292 KB Output is correct
6 Correct 681 ms 25416 KB Output is correct
7 Correct 776 ms 24524 KB Output is correct
8 Correct 725 ms 25036 KB Output is correct
9 Correct 739 ms 24012 KB Output is correct
10 Correct 69 ms 18900 KB Output is correct
11 Correct 709 ms 25292 KB Output is correct
12 Correct 690 ms 23756 KB Output is correct
13 Correct 460 ms 24840 KB Output is correct
14 Correct 714 ms 24776 KB Output is correct
15 Correct 553 ms 24780 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 18900 KB Output is correct
2 Correct 4 ms 17692 KB Output is correct
3 Correct 697 ms 24800 KB Output is correct
4 Correct 1189 ms 68200 KB Output is correct
5 Correct 161 ms 20424 KB Output is correct
6 Correct 688 ms 25292 KB Output is correct
7 Correct 707 ms 23752 KB Output is correct
8 Correct 488 ms 24260 KB Output is correct
9 Correct 637 ms 24768 KB Output is correct
10 Correct 521 ms 25292 KB Output is correct
11 Correct 681 ms 25416 KB Output is correct
12 Correct 776 ms 24524 KB Output is correct
13 Correct 725 ms 25036 KB Output is correct
14 Correct 739 ms 24012 KB Output is correct
15 Correct 69 ms 18900 KB Output is correct
16 Correct 709 ms 25292 KB Output is correct
17 Correct 690 ms 23756 KB Output is correct
18 Correct 460 ms 24840 KB Output is correct
19 Correct 714 ms 24776 KB Output is correct
20 Correct 553 ms 24780 KB Output is correct
21 Runtime error 293 ms 262144 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -