oj.uz

Submission #334907

# Submission time Handle Problem Language Result Execution time Memory
334907 2020-12-10T08:24:02 Z YJU Soccer (JOI17_soccer) C++14
35 / 100
 2321 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<short,short> 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,L;
short H,W,sx,sy,ex,ey,x,y;
int 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(short nx,short 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;
	if(a<c)L=b/(c-a);
	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=L;;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 151 ms 4712 KB Output is correct
2 Correct 2 ms 2284 KB Output is correct
3 Correct 1407 ms 8544 KB Output is correct
4 Correct 2321 ms 37308 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 1589 ms 8552 KB Output is correct
2 Correct 1471 ms 8548 KB Output is correct
3 Correct 902 ms 8160 KB Output is correct
4 Correct 1312 ms 8548 KB Output is correct
5 Correct 1016 ms 8552 KB Output is correct
6 Correct 1459 ms 8548 KB Output is correct
7 Correct 1570 ms 8668 KB Output is correct
8 Correct 1371 ms 8560 KB Output is correct
9 Correct 1626 ms 8540 KB Output is correct
10 Correct 135 ms 5496 KB Output is correct
11 Correct 1524 ms 8540 KB Output is correct
12 Correct 1504 ms 8676 KB Output is correct
13 Correct 864 ms 8164 KB Output is correct
14 Correct 1584 ms 8540 KB Output is correct
15 Correct 1091 ms 8668 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 4712 KB Output is correct
2 Correct 2 ms 2284 KB Output is correct
3 Correct 1407 ms 8544 KB Output is correct
4 Correct 2321 ms 37308 KB Output is correct
5 Correct 15 ms 3692 KB Output is correct
6 Correct 1589 ms 8552 KB Output is correct
7 Correct 1471 ms 8548 KB Output is correct
8 Correct 902 ms 8160 KB Output is correct
9 Correct 1312 ms 8548 KB Output is correct
10 Correct 1016 ms 8552 KB Output is correct
11 Correct 1459 ms 8548 KB Output is correct
12 Correct 1570 ms 8668 KB Output is correct
13 Correct 1371 ms 8560 KB Output is correct
14 Correct 1626 ms 8540 KB Output is correct
15 Correct 135 ms 5496 KB Output is correct
16 Correct 1524 ms 8540 KB Output is correct
17 Correct 1504 ms 8676 KB Output is correct
18 Correct 864 ms 8164 KB Output is correct
19 Correct 1584 ms 8540 KB Output is correct
20 Correct 1091 ms 8668 KB Output is correct
21 Correct 15 ms 3564 KB Output is correct
22 Runtime error 568 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -