oj.uz

Submission #377005

# Submission time Handle Problem Language Result Execution time Memory
377005 2021-03-12T17:05:27 Z astoria Soccer (JOI17_soccer) C++14
35 / 100
 571 ms 35040 KB 
#include "bits/stdc++.h"
using namespace std;

#define int long long

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int h,w,a,b,c,n;
	cin>>h>>w>>a>>b>>c>>n;
	
	int s[n],t[n];
	for(int i=0; i<n; i++) cin>>s[i]>>t[i];
	
	vector<pair<int,int> > adj[n];
	
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			int difs = abs(s[i]-s[j]);
			int dift = abs(t[i]-t[j]);
			
			int optOne = (a*difs) + b + (c*dift);
			if(difs==0) optOne-=b;
			int optTwo = (a*dift) + b + (c*difs);
			if(dift==0) optTwo-=b;
			int optThree = (c*difs) + (c*dift);
			
			int dist = min(min(optOne,optTwo),optThree);
			adj[i].push_back({j,dist});
			adj[j].push_back({i,dist});
		}
	}
	
	int dist[n];
	memset(dist,-1,sizeof(dist));
	dist[0] = 0;
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
	pq.push({0,0});
	while(!pq.empty()){
		int v = pq.top().first, di = pq.top().second; pq.pop();
		if(dist[v] != di) continue;
		for(auto ii : adj[v]){
			int nv = ii.first, nd = ii.second+di;
			if(dist[nv] != -1 && dist[nv] <= nd) continue;
			dist[nv] = nd;
			pq.push({nv,nd});
		}
	}
	cout<<dist[n-1];
	
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 876 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 2 ms 876 KB Output is correct
5 Correct 4 ms 2028 KB Output is correct
6 Correct 571 ms 35040 KB Output is correct
7 Correct 83 ms 33276 KB Output is correct
8 Correct 96 ms 33260 KB Output is correct
9 Correct 57 ms 33132 KB Output is correct
10 Correct 54 ms 33260 KB Output is correct
11 Correct 65 ms 33136 KB Output is correct
12 Correct 2 ms 1644 KB Output is correct
13 Correct 434 ms 35040 KB Output is correct
14 Correct 63 ms 33132 KB Output is correct
15 Correct 63 ms 33152 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 876 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 2 ms 876 KB Output is correct
10 Correct 4 ms 2028 KB Output is correct
11 Correct 571 ms 35040 KB Output is correct
12 Correct 83 ms 33276 KB Output is correct
13 Correct 96 ms 33260 KB Output is correct
14 Correct 57 ms 33132 KB Output is correct
15 Correct 54 ms 33260 KB Output is correct
16 Correct 65 ms 33136 KB Output is correct
17 Correct 2 ms 1644 KB Output is correct
18 Correct 434 ms 35040 KB Output is correct
19 Correct 63 ms 33132 KB Output is correct
20 Correct 63 ms 33152 KB Output is correct
21 Correct 1 ms 640 KB Output is correct
22 Incorrect 2 ms 748 KB Output isn't correct
23 Halted 0 ms 0 KB -