Submission #676879

#	Time	Username	Problem	Language	Result	Execution time	Memory
676879		Arnch	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	811 ms	26700 KiB

skyscraper

// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

/*
	link:	
*/

#include<iostream>
#include<vector>
#include<set>
#include<queue>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define mak make_pair

//constexpr int PRI = 1000696969;
constexpr int INF = 1e9, N = 1e6 + 10, MOD = 1e9 + 7;

int b[N], x[N];
int d[N];
vector<int> vc[N];

int main() {
	ios :: sync_with_stdio(0), cin.tie(0); cout.tie(0);

	int n, m; cin >>n >>m;
	for(int i = 0; i < m; i++) {
		cin >>b[i] >>x[i];
		vc[b[i]].push_back(i);
	}
	
	for(int i = 0; i < n; i++) d[i] = INF;

	d[b[0]] = 0;
	priority_queue<pair<int, int> > st;
	st.push({0, b[0]});

	while(!st.empty()) {
		int q = -st.top().first, p = st.top().second;
		st.pop();
		if(d[p] != q) continue;

		if(p == b[1]) {
			return cout<<d[p], 0;
		}
		
		for(auto j : vc[p]) {
			for(int cnt = 1; p + cnt * x[j] < n; cnt++) {
				int pq = p + cnt * x[j];
				if(d[p] + cnt < d[pq]) {
					d[pq] = d[p] + cnt;
					st.push({-d[pq], pq});
				}
			}
			for(int cnt = 1; p - cnt * x[j] >= 0; cnt++) {
				int pq = p - cnt * x[j];
				if(d[p] + cnt < d[pq]) {
					d[pq] = d[p] + cnt;
					st.push({-d[pq], pq});
				}
			}
		}
	}

	cout<<-1;
	
	return 0;
}

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