oj.uz

Submission #894623

# Submission time Handle Problem Language Result Execution time Memory
894623 2023-12-28T14:34:26 Z pcc Soccer (JOI17_soccer) C++14
100 / 100
 2554 ms 24336 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> inq[mxn];
queue<pii> q;
int lim = 2.95*CLOCKS_PER_SEC;
int st;

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;
	st = clock();
	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;
	inq[arr[0].fs][arr[0].sc] = true;
	q.push(arr[0]);
	while(!q.empty()&&clock()-st<=lim){
		auto tt = q.front();
		q.pop();
		int r = tt.fs,c = tt.sc;
		inq[r][c] = false;
		//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;
				if(!inq[nr][nc])inq[nr][nc] = true,q.push({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];
					if(!inq[nr][nc])inq[nr][nc] = true,q.push({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:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 | main(){
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 18352 KB Output is correct
2 Correct 4 ms 17240 KB Output is correct
3 Correct 609 ms 21492 KB Output is correct
4 Correct 611 ms 21496 KB Output is correct
5 Correct 159 ms 18780 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1894 ms 21540 KB Output is correct
2 Correct 1783 ms 21764 KB Output is correct
3 Correct 1526 ms 20660 KB Output is correct
4 Correct 636 ms 21500 KB Output is correct
5 Correct 1510 ms 20680 KB Output is correct
6 Correct 722 ms 21336 KB Output is correct
7 Correct 1836 ms 21548 KB Output is correct
8 Correct 2554 ms 21340 KB Output is correct
9 Correct 1104 ms 21776 KB Output is correct
10 Correct 81 ms 18008 KB Output is correct
11 Correct 1495 ms 21772 KB Output is correct
12 Correct 1540 ms 21516 KB Output is correct
13 Correct 598 ms 20668 KB Output is correct
14 Correct 1324 ms 21632 KB Output is correct
15 Correct 891 ms 20996 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 18352 KB Output is correct
2 Correct 4 ms 17240 KB Output is correct
3 Correct 609 ms 21492 KB Output is correct
4 Correct 611 ms 21496 KB Output is correct
5 Correct 159 ms 18780 KB Output is correct
6 Correct 1894 ms 21540 KB Output is correct
7 Correct 1783 ms 21764 KB Output is correct
8 Correct 1526 ms 20660 KB Output is correct
9 Correct 636 ms 21500 KB Output is correct
10 Correct 1510 ms 20680 KB Output is correct
11 Correct 722 ms 21336 KB Output is correct
12 Correct 1836 ms 21548 KB Output is correct
13 Correct 2554 ms 21340 KB Output is correct
14 Correct 1104 ms 21776 KB Output is correct
15 Correct 81 ms 18008 KB Output is correct
16 Correct 1495 ms 21772 KB Output is correct
17 Correct 1540 ms 21516 KB Output is correct
18 Correct 598 ms 20668 KB Output is correct
19 Correct 1324 ms 21632 KB Output is correct
20 Correct 891 ms 20996 KB Output is correct
21 Correct 148 ms 18776 KB Output is correct
22 Correct 1250 ms 21752 KB Output is correct
23 Correct 996 ms 21352 KB Output is correct
24 Correct 894 ms 21776 KB Output is correct
25 Correct 661 ms 21456 KB Output is correct
26 Correct 802 ms 21568 KB Output is correct
27 Correct 597 ms 23892 KB Output is correct
28 Correct 646 ms 24292 KB Output is correct
29 Correct 602 ms 24284 KB Output is correct
30 Correct 593 ms 24284 KB Output is correct
31 Correct 1643 ms 21588 KB Output is correct
32 Correct 1066 ms 24336 KB Output is correct
33 Correct 759 ms 21512 KB Output is correct
34 Correct 1151 ms 21776 KB Output is correct
35 Correct 710 ms 24292 KB Output is correct