oj.uz

Submission #894563

# Submission time Handle Problem Language Result Execution time Memory
894563 2023-12-28T12:54:22 Z pcc Soccer (JOI17_soccer) C++14
35 / 100
 666 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;
		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: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 16 ms 18896 KB Output is correct
2 Correct 3 ms 17692 KB Output is correct
3 Correct 57 ms 25284 KB Output is correct
4 Correct 19 ms 21452 KB Output is correct
5 Correct 93 ms 21448 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21452 KB Output is correct
2 Correct 9 ms 18900 KB Output is correct
3 Correct 77 ms 25284 KB Output is correct
4 Correct 472 ms 23740 KB Output is correct
5 Correct 93 ms 24116 KB Output is correct
6 Correct 149 ms 24764 KB Output is correct
7 Correct 15 ms 23500 KB Output is correct
8 Correct 17 ms 25036 KB Output is correct
9 Correct 12 ms 20432 KB Output is correct
10 Correct 12 ms 18972 KB Output is correct
11 Correct 26 ms 24780 KB Output is correct
12 Correct 45 ms 24524 KB Output is correct
13 Correct 96 ms 25192 KB Output is correct
14 Correct 14 ms 23896 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 25284 KB Output is correct
4 Correct 19 ms 21452 KB Output is correct
5 Correct 93 ms 21448 KB Output is correct
6 Correct 14 ms 21452 KB Output is correct
7 Correct 9 ms 18900 KB Output is correct
8 Correct 77 ms 25284 KB Output is correct
9 Correct 472 ms 23740 KB Output is correct
10 Correct 93 ms 24116 KB Output is correct
11 Correct 149 ms 24764 KB Output is correct
12 Correct 15 ms 23500 KB Output is correct
13 Correct 17 ms 25036 KB Output is correct
14 Correct 12 ms 20432 KB Output is correct
15 Correct 12 ms 18972 KB Output is correct
16 Correct 26 ms 24780 KB Output is correct
17 Correct 45 ms 24524 KB Output is correct
18 Correct 96 ms 25192 KB Output is correct
19 Correct 14 ms 23896 KB Output is correct
20 Correct 7 ms 18900 KB Output is correct
21 Correct 187 ms 216004 KB Output is correct
22 Correct 295 ms 30392 KB Output is correct
23 Correct 335 ms 43948 KB Output is correct
24 Correct 212 ms 30284 KB Output is correct
25 Correct 196 ms 24260 KB Output is correct
26 Correct 347 ms 30488 KB Output is correct
27 Runtime error 666 ms 262144 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -