oj.uz

Submission #334905

# Submission time Handle Problem Language Result Execution time Memory
334905 2020-12-10T08:13:00 Z YJU Soccer (JOI17_soccer) C++14
35 / 100
 2477 ms 262148 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=5e2+5;
const ll K=350;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

queue<pll> q;
ll cost[N][N],dis[N][N],n,a,b,c,H,W,sx,sy,ex,ey,x,y,d;
ll dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
priority_queue<pair<ll,pll>,vector<pair<ll,pll> >,greater<pair<ll,pll> > > pq;

bool ck(ll nx,ll ny){
	return (nx>=0&&nx<=H&&ny>=0&&ny<=W);
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>H>>W;
	cin>>a>>b>>c;
	cin>>n;
	memset(dis,-1,sizeof(dis));
	REP1(i,n)cin>>x>>y,q.push(mp(x,y)),cost[x][y]=0,dis[x][y]=INF,sx=(i==1?x:sx),sy=(i==1?y:sy);
	ex=x;ey=y;
	while(SZ(q)){
		x=q.front().X;y=q.front().Y;q.pop();
		REP(i,4){
			if(ck(x+dx[i],y+dy[i])&&dis[x+dx[i]][y+dy[i]]==-1){
				dis[x+dx[i]][y+dy[i]]=INF;
				cost[x+dx[i]][y+dy[i]]=cost[x][y]+c;
				q.push(mp(x+dx[i],y+dy[i]));
			}
		}
	}
	pq.push(mp(dis[sx][sy]=0,mp(sx,sy)));
	while(SZ(pq)){
		d=pq.top().X,x=pq.top().Y.X,y=pq.top().Y.Y;pq.pop();
		if(d!=dis[x][y])continue;
		REP(i,4){
			ll nx=x+dx[i],ny=y+dy[i];
			if(ck(nx,ny)&&dis[nx][ny]>d+c){pq.push(mp(dis[nx][ny]=d+c,mp(nx,ny)));}
			for(int j=1;;j++){
				nx=x+dx[i]*j,ny=y+dy[i]*j;
				if(!ck(nx,ny))break;
				if(dis[nx][ny]>d+b+a*j+cost[nx][ny]){
					pq.push(mp(dis[nx][ny]=d+b+a*j+cost[nx][ny],mp(nx,ny)));
				}
			}
		}
	}
	cout<<dis[ex][ey]<<"\n";
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 5240 KB Output is correct
2 Correct 4 ms 2864 KB Output is correct
3 Correct 1415 ms 10596 KB Output is correct
4 Correct 2477 ms 53804 KB Output is correct
5 Correct 282 ms 7012 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1473 ms 10740 KB Output is correct
2 Correct 1445 ms 10764 KB Output is correct
3 Correct 891 ms 10256 KB Output is correct
4 Correct 1213 ms 10724 KB Output is correct
5 Correct 993 ms 10764 KB Output is correct
6 Correct 1381 ms 10592 KB Output is correct
7 Correct 1556 ms 10908 KB Output is correct
8 Correct 1350 ms 10764 KB Output is correct
9 Correct 1576 ms 10908 KB Output is correct
10 Correct 135 ms 6140 KB Output is correct
11 Correct 1514 ms 10892 KB Output is correct
12 Correct 1457 ms 10764 KB Output is correct
13 Correct 867 ms 10208 KB Output is correct
14 Correct 1599 ms 10780 KB Output is correct
15 Correct 1091 ms 10892 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 5240 KB Output is correct
2 Correct 4 ms 2864 KB Output is correct
3 Correct 1415 ms 10596 KB Output is correct
4 Correct 2477 ms 53804 KB Output is correct
5 Correct 282 ms 7012 KB Output is correct
6 Correct 1473 ms 10740 KB Output is correct
7 Correct 1445 ms 10764 KB Output is correct
8 Correct 891 ms 10256 KB Output is correct
9 Correct 1213 ms 10724 KB Output is correct
10 Correct 993 ms 10764 KB Output is correct
11 Correct 1381 ms 10592 KB Output is correct
12 Correct 1556 ms 10908 KB Output is correct
13 Correct 1350 ms 10764 KB Output is correct
14 Correct 1576 ms 10908 KB Output is correct
15 Correct 135 ms 6140 KB Output is correct
16 Correct 1514 ms 10892 KB Output is correct
17 Correct 1457 ms 10764 KB Output is correct
18 Correct 867 ms 10208 KB Output is correct
19 Correct 1599 ms 10780 KB Output is correct
20 Correct 1091 ms 10892 KB Output is correct
21 Runtime error 647 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -