oj.uz

Submission #894612

# Submission time Handle Problem Language Result Execution time Memory
894612 2023-12-28T14:24:23 Z pcc Soccer (JOI17_soccer) C++14
35 / 100
 648 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];
bitset<mxn> done[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(done[r][c])continue;
		done[r][c] = true;
		if(r == arr[K-1].fs&&c == arr[K-1].sc)break;
		//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:23:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   23 | main(){
      | ^~~~
soccer.cpp: In function 'int main()':
soccer.cpp:58:37: warning: unused variable 'ds' [-Wunused-variable]
   58 |   int r = get<1>(tt),c = get<2>(tt),ds = get<0>(tt);
      |                                     ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 18896 KB Output is correct
2 Correct 3 ms 17692 KB Output is correct
3 Correct 57 ms 23808 KB Output is correct
4 Correct 18 ms 20428 KB Output is correct
5 Correct 97 ms 21536 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21628 KB Output is correct
2 Correct 8 ms 18900 KB Output is correct
3 Correct 77 ms 23764 KB Output is correct
4 Correct 458 ms 25024 KB Output is correct
5 Correct 86 ms 24268 KB Output is correct
6 Correct 162 ms 25028 KB Output is correct
7 Correct 14 ms 24008 KB Output is correct
8 Correct 16 ms 24008 KB Output is correct
9 Correct 11 ms 21968 KB Output is correct
10 Correct 13 ms 19016 KB Output is correct
11 Correct 27 ms 24384 KB Output is correct
12 Correct 48 ms 24012 KB Output is correct
13 Correct 97 ms 25284 KB Output is correct
14 Correct 13 ms 24520 KB Output is correct
15 Correct 7 ms 18900 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 18896 KB Output is correct
2 Correct 3 ms 17692 KB Output is correct
3 Correct 57 ms 23808 KB Output is correct
4 Correct 18 ms 20428 KB Output is correct
5 Correct 97 ms 21536 KB Output is correct
6 Correct 13 ms 21628 KB Output is correct
7 Correct 8 ms 18900 KB Output is correct
8 Correct 77 ms 23764 KB Output is correct
9 Correct 458 ms 25024 KB Output is correct
10 Correct 86 ms 24268 KB Output is correct
11 Correct 162 ms 25028 KB Output is correct
12 Correct 14 ms 24008 KB Output is correct
13 Correct 16 ms 24008 KB Output is correct
14 Correct 11 ms 21968 KB Output is correct
15 Correct 13 ms 19016 KB Output is correct
16 Correct 27 ms 24384 KB Output is correct
17 Correct 48 ms 24012 KB Output is correct
18 Correct 97 ms 25284 KB Output is correct
19 Correct 13 ms 24520 KB Output is correct
20 Correct 7 ms 18900 KB Output is correct
21 Correct 221 ms 214520 KB Output is correct
22 Correct 280 ms 30652 KB Output is correct
23 Correct 357 ms 42160 KB Output is correct
24 Correct 224 ms 31156 KB Output is correct
25 Correct 179 ms 23756 KB Output is correct
26 Correct 358 ms 30132 KB Output is correct
27 Runtime error 648 ms 262144 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -