oj.uz

Submission #894567

# Submission time Handle Problem Language Result Execution time Memory
894567 2023-12-28T12:58:23 Z pcc Soccer (JOI17_soccer) C++14
35 / 100
 3000 ms 32692 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];
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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 19632 KB Output is correct
2 Correct 4 ms 17244 KB Output is correct
3 Correct 118 ms 26316 KB Output is correct
4 Correct 38 ms 22416 KB Output is correct
5 Correct 132 ms 21236 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 22860 KB Output is correct
2 Correct 18 ms 20572 KB Output is correct
3 Correct 134 ms 27032 KB Output is correct
4 Correct 559 ms 25684 KB Output is correct
5 Correct 232 ms 27060 KB Output is correct
6 Correct 208 ms 29556 KB Output is correct
7 Correct 62 ms 29652 KB Output is correct
8 Correct 78 ms 31316 KB Output is correct
9 Correct 36 ms 24464 KB Output is correct
10 Correct 20 ms 19548 KB Output is correct
11 Correct 105 ms 32692 KB Output is correct
12 Correct 113 ms 31824 KB Output is correct
13 Correct 154 ms 27988 KB Output is correct
14 Correct 51 ms 27732 KB Output is correct
15 Correct 12 ms 19292 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 19632 KB Output is correct
2 Correct 4 ms 17244 KB Output is correct
3 Correct 118 ms 26316 KB Output is correct
4 Correct 38 ms 22416 KB Output is correct
5 Correct 132 ms 21236 KB Output is correct
6 Correct 31 ms 22860 KB Output is correct
7 Correct 18 ms 20572 KB Output is correct
8 Correct 134 ms 27032 KB Output is correct
9 Correct 559 ms 25684 KB Output is correct
10 Correct 232 ms 27060 KB Output is correct
11 Correct 208 ms 29556 KB Output is correct
12 Correct 62 ms 29652 KB Output is correct
13 Correct 78 ms 31316 KB Output is correct
14 Correct 36 ms 24464 KB Output is correct
15 Correct 20 ms 19548 KB Output is correct
16 Correct 105 ms 32692 KB Output is correct
17 Correct 113 ms 31824 KB Output is correct
18 Correct 154 ms 27988 KB Output is correct
19 Correct 51 ms 27732 KB Output is correct
20 Correct 12 ms 19292 KB Output is correct
21 Execution timed out 3051 ms 20696 KB Time limit exceeded
22 Halted 0 ms 0 KB -