제출 #89285

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
89285		Mouhanad_Hafez	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	100 / 100	126 ms	20316 KiB

skyscraper

    #include <bits/stdc++.h>
    using namespace std;
    typedef pair<int, int> pii;
    int N, M, S, E;
    int D[30005];
    bool V[30005][200];
    vector <int> doge[30005];
    int main()
    {
    	cin>>N>>M;
    	for (int i=0;i<M;i++){
    		int b, p;
    		cin>>b>>p;
    		if (p > 199 || !V[b][p]) doge[b].push_back(p);
    		if (p < 200) V[b][p] = 1;
    		if (!i) S = b;
    		if (i == 1) E = b;
    	}
    	for (int i=0;i<N;i++) D[i] = 2e9;
    	priority_queue <pii> que;
    	D[S] = 0;
    	que.push(make_pair(0, S));
    	while (!que.empty()){
    		int q = que.top().second, d = -que.top().first; que.pop();
    		if (D[q] != d) continue;
    		for (int p: doge[q]){
    			for (int i=q-p;i>=0;i-=p){
    				if (D[i] > d+(q-i)/p)
    					D[i] = d+(q-i)/p, que.push(make_pair(-D[i], i));
    				if (p < 200 && V[i][p]) break;
    				if (p < 200) V[i][p] = 1;
    			}
    			for (int i=q+p;i<N;i+=p){
    				if (D[i] > d+(i-q)/p)
    					D[i] = d+(i-q)/p, que.push(make_pair(-D[i], i));
    				if (p < 200 && V[i][p]) break;
    				if (p < 200) V[i][p] = 1;
    			}
    		}
    	}
    	if (D[E]<2e9)cout<<D[E];
    	else cout<<-1;
    	return 0;
    }

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