Submission #106975

#	Time	Username	Problem	Language	Result	Execution time	Memory
106975		nxteru	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	3 ms	1152 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 1000000000
#define B 173
#define R 1000000000
int n,m,dn[30005][205],dm[30005][205],d[30005][205],st[30005],ed[30005],p[30005],b[30005],rs[30005],ans=INF;
vector<int>g[30005];
int main(void){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)for(int j=0;j<=B;j++)d[i][j]=INF;
	for(int i=0;i<m;i++){
		scanf("%d%d",b+i,p+i);
		st[i]=b[i]%p[i];
		rs[i]=(b[i]-st[i])/p[i];
		ed[i]=(n-st[i]-1)/p[i]+1;
		if(p[i]<=B)d[b[i]][p[i]]=0;
		else for(int j=st[i];j<n;j+=p[i])g[j].PB(i);
	}
	for(int j=1;j<=B;j++){
		for(int i=0;i<n;i++)if(i-j>=0)d[i][j]=min(d[i][j],d[i][i-j]+1);
		for(int i=n-1;i>=0;i--)if(i+j<n)d[i][j]=min(d[i][j],d[i][i+j]+1);
	}
	for(int i=0;i<n;i++)for(int j=0;j<=B;j++)dn[i][j]=INF;
	for(int i=0;i<m;i++)for(int j=0;j<ed[i];j++)dm[i][j]=INF;
	priority_queue<P,vector<P>,greater<P> >dik;
	dn[b[0]][0]=0;
	dik.push(P(0,b[0]*n));
	while(!dik.empty()){
		int c=dik.top().F,x=dik.top().S;
		dik.pop();
		if(x<R){
			int e=x%n,v=x/n;
			if(dn[v][e]<c)continue;
			if(dn[v][0]>c){
				dn[v][0]=c;
				dik.push(P(c,v*n));
			}
			if(e==0){
				for(int i=1;i<=B;i++){
					if(dn[v][i]>c+d[v][i]){
						dn[v][i]=c+d[v][i];
						dik.push(P(dn[v][i],v*n+i));
					}
				}
				for(int i=0;i<g[v].size();i++){
					int r=g[v][i],w=(v-st[r])/p[r];
					if(dm[r][w]>c+abs(rs[r]-w)){
						dm[r][w]=c+abs(rs[r]-w);
						dik.push(P(dm[r][w],R+r*m+w));
					}
				}
			}else{
				if(v+e<n&&dn[v+e][e]>c+1){
					dn[v+e][e]=c+1;
					dik.push(P(c+1,n*(v+e)+e));
				}
				if(v-e>=0&&dn[v-e][e]>c+1){
					dn[v-e][e]=c+1;
					dik.push(P(c+1,n*(v-e)+e));
				}
			}
		}else{
			x-=R;
			int r=x/m,w=x%m;
			if(w+1<ed[r]&&dm[r][w+1]>c+1){
				dm[r][w+1]=c+1;
				dik.push(P(c+1,R+r*m+w+1));
			}
			if(w-1>=0&&dm[r][w-1]>c+1){
				dm[r][w-1]=c+1;
				dik.push(P(c+1,R+r*m+w-1));
			}
		}
	}
	for(int i=0;i<ed[1];i++)ans=min(ans,dn[st[1]+i*p[1]][0]+abs(b[1]-i));
	printf("%d\n",ans);
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:52:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++){
                 ~^~~~~~~~~~~~
skyscraper.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",b+i,p+i);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43