Submission #552612

#	Time	Username	Problem	Language	Result	Execution time	Memory
552612		QwertyPi	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1088 ms	67400 KiB

skyscraper

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

int dp[30001];
vector<int> G[30001];
int A[30001][2];
int main(){
	int n, k;
	cin >> n >> k;
	for(int i = 0; i < k; i++){
		cin >> A[i][0] >> A[i][1];
		G[A[i][0]].push_back(A[i][1]);
	}
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
	q.push({0, A[0][0]});
	fill(dp, dp + n, (1 << 30));
	while(q.size()){
		pair<int, int> qe = q.top(); q.pop();
		int v = qe.se, w = qe.fi;
		if(dp[v] != (1 << 30)) continue;
		dp[v] = w;
		// cout << v << ' ' << w << endl;
		for(auto i : G[v]){
			for(int j = v % i; j < n; j += i){
				int d = abs(v - j) / i;
				if(dp[j] > w + d) q.push({w + d, j});
			}
		}
	}
	cout << (dp[A[1][0]] == (1 << 30) ? -1 : dp[A[1][0]]) << endl;
}

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