Submission #676876

#	Time	Username	Problem	Language	Result	Execution time	Memory
676876		Arnch	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1040 ms	27324 KiB

skyscraper

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

/*
	link:	
*/

#include<bits/stdc++.h>
//#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 ll INF = 1e18, N = 1e6 + 10, MOD = 1e9 + 7;

int b[N], x[N];
ll 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;
	set<pair<ll, int> > st;
	st.insert({0, b[0]});

	while(!st.empty()) {
		int p = st.begin() -> second; st.erase(st.begin());

		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]) {
					st.erase({d[pq], pq});
					d[pq] = d[p] + cnt;
					st.insert({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]) {
					st.erase({d[pq], pq});
					d[pq] = d[p] + cnt;
					st.insert({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: 0 / 43