Submission #894567

#	Time	Username	Problem	Language	Result	Execution time	Memory
894567		pcc	Soccer (JOI17_soccer)	C++14	35 / 100	3051 ms	32692 KiB

soccer

#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];
set<tlll> 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;
	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));
	st.insert(make_tuple(0,arr[0].fs,arr[0].sc));
	while(!st.empty()){
		//auto tt = pq.top();
		auto tt = *st.begin();
		st.erase(st.begin());
		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){
				if(st.find(make_tuple(dp[nr][nc],nr,nc))!=st.end())st.erase(st.find(make_tuple(dp[nr][nc],nr,nc)));
				dp[nr][nc] = dp[r][c]+C;
				st.insert(make_tuple(dp[nr][nc],nr,nc));
				//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]){
					if(st.find(make_tuple(dp[nr][nc],nr,nc))!=st.end())st.erase(st.find(make_tuple(dp[nr][nc],nr,nc)));
					dp[nr][nc] = dp[r][c]+A*pt+B+C*player[nr][nc];
					st.insert(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 (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 0 / 65