Submission #108072

#	Time	Username	Problem	Language	Result	Execution time	Memory
108072		autumn_eel	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	2 ms	384 KiB

skyscraper

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int>P;
typedef long long ll;

int b[50000],t[50000];
int d[2200];
//~ int d[2200][2200];
vector<int>v[2200];

struct st{
	int a,b,c;
};
bool operator<(st a,st b){
	return a.c>b.c;
}
int main(){
	int n,m;cin>>n>>m;
	rep(i,m){
		scanf("%d%d",&b[i],&t[i]);
		v[b[i]].push_back(t[i]);
	}
	memset(d,0x3f,sizeof(d));
	d[0]=0;
	priority_queue<st>que;
	que.push({0,-1,0});
	while(!que.empty()){
		st p=que.top();que.pop();
		int c=d[p.a];
		if(c!=p.c)continue;
		for(int k:v[p.a]){
			for(int i=p.a,j=0;i>=0;i-=k,j++){
				if(d[i]>c+j){
					d[i]=c+j;
					que.push({i,-1,d[i]});
				}
			}
			for(int i=p.a,j=0;i<n;i+=k,j++){
				if(d[i]>c+j){
					d[i]=c+j;
					que.push({i,-1,d[i]});
				}
			}
		}
	}
	int ans=d[1];
	if(ans==INF)puts("-1");
	else cout<<ans<<endl;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&b[i],&t[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

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