oj.uz

Submission #1016293

# Submission time Handle Problem Language Result Execution time Memory
1016293 2024-07-07T17:11:36 Z Muhammet Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 1 ms 1372 KB 
#include <bits/stdc++.h>
using namespace std;

#define N 30005
#define ll long long int
#define sz(x) (int)x.size()
#define ff first
#define ss second

ll T, n, m, b[N], p[N], vis[N];

vector <int> v[N];

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

	cin >> n >> m;

	vector <ll> a(n,1e9);

	for(int i = 0; i < m; i++){
		cin >> b[i] >> p[i];
		v[b[i]].push_back(i);
	}

	set <int> s;
	a[0] = 0;
	s.insert(0);
	ll ans = 1e9;
	while(sz(s) > 0){
		int x = *s.begin();
		s.erase(s.begin());
		for(int i = b[x]-p[x]; i >= 0; i -= p[x]){
			a[i] = (a[i+p[x]] + 1);
			if(vis[i] == 0){
				vis[i] = 1;
				for(auto j : v[i]){
					s.insert(j);
				}
			}
		}
		for(int i = b[x]+p[x]; i < n; i += p[x]){
			a[i] = (a[i-p[x]] + 1);
			if(vis[i] == 0){
				vis[i] = 1;
				for(auto j : v[i]){
					s.insert(j);
				}
			}
		}
		ans = min(ans,a[b[1]]);
	}

	cout << ans;
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 0 ms 1116 KB Output is correct
4 Incorrect 1 ms 1116 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 0 ms 1116 KB Output is correct
3 Correct 0 ms 1116 KB Output is correct
4 Incorrect 1 ms 1116 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Incorrect 0 ms 1116 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Incorrect 1 ms 1116 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 0 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Incorrect 0 ms 1116 KB Output isn't correct
5 Halted 0 ms 0 KB -