oj.uz

Submission #334906

# Submission time Handle Problem Language Result Execution time Memory
334906 2020-12-10T08:20:50 Z YJU Soccer (JOI17_soccer) C++14
35 / 100
 2284 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<int,int> 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],d;
int n,a,b,c,H,W,sx,sy,ex,ey,x,y;
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(int nx,int 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){
			int 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)));}
			if(a<c){
				for(int j=b/(c-a);;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 147 ms 4716 KB Output is correct
2 Correct 2 ms 2304 KB Output is correct
3 Correct 1495 ms 8496 KB Output is correct
4 Correct 2284 ms 37436 KB Output is correct
5 Correct 15 ms 3692 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1401 ms 8552 KB Output is correct
2 Correct 1388 ms 8560 KB Output is correct
3 Correct 882 ms 8296 KB Output is correct
4 Correct 1172 ms 8676 KB Output is correct
5 Correct 995 ms 8560 KB Output is correct
6 Correct 1334 ms 8548 KB Output is correct
7 Correct 1504 ms 8668 KB Output is correct
8 Correct 1293 ms 8668 KB Output is correct
9 Correct 1485 ms 8668 KB Output is correct
10 Correct 122 ms 5476 KB Output is correct
11 Correct 1466 ms 8668 KB Output is correct
12 Correct 1370 ms 8668 KB Output is correct
13 Correct 794 ms 8164 KB Output is correct
14 Correct 1486 ms 8668 KB Output is correct
15 Correct 1045 ms 8668 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 4716 KB Output is correct
2 Correct 2 ms 2304 KB Output is correct
3 Correct 1495 ms 8496 KB Output is correct
4 Correct 2284 ms 37436 KB Output is correct
5 Correct 15 ms 3692 KB Output is correct
6 Correct 1401 ms 8552 KB Output is correct
7 Correct 1388 ms 8560 KB Output is correct
8 Correct 882 ms 8296 KB Output is correct
9 Correct 1172 ms 8676 KB Output is correct
10 Correct 995 ms 8560 KB Output is correct
11 Correct 1334 ms 8548 KB Output is correct
12 Correct 1504 ms 8668 KB Output is correct
13 Correct 1293 ms 8668 KB Output is correct
14 Correct 1485 ms 8668 KB Output is correct
15 Correct 122 ms 5476 KB Output is correct
16 Correct 1466 ms 8668 KB Output is correct
17 Correct 1370 ms 8668 KB Output is correct
18 Correct 794 ms 8164 KB Output is correct
19 Correct 1486 ms 8668 KB Output is correct
20 Correct 1045 ms 8668 KB Output is correct
21 Correct 14 ms 3564 KB Output is correct
22 Runtime error 548 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -