oj.uz

Submission #396012

# Submission time Handle Problem Language Result Execution time Memory
396012 2021-04-29T11:09:59 Z amunduzbaev Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 74 ms 35012 KB 
/* made by amunduzbaev */
 
#include <bits/stdc++.h>
 
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
//using namespace __gnu_pbds;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vv vector
#define tut(x) array<int, x> 
//#define int long long
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef vector<int> vii;
typedef vector<pii> vpii;
 
template<class T> bool umin(T& a, const T& b) { return a > b? a = b, true:false; }
template<class T> bool umax(T& a, const T& b) { return a < b? a = b, true:false; }
//void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);  
	//freopen((s+".out").c_str(),"w",stdout); }
//template<class T> tree<T, 
//less<T>, null_type, rb_tree_tag, 
//tree_order_statistics_node_update> ordered_set;
 
const int N = 3e4+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
const int M = 2e3+5;
const int B = 500;
 
#define MULTI 0
int n, m, K, s, ans, q, res, a[N];
int b[N], p[N], dd[M][M];
vii cnt[N];
 
void solve(int t_case){
	cin>>m>>n;
	for(int i=0;i<n;i++) cin>>b[i]>>p[i], cnt[b[i]].pb(i);
	memset(dd, 127, sizeof dd);
	
	queue<pii> qq;
	res = mod;
	qq.push({b[0], p[0]}), dd[b[0]][p[0]] = 0;
	while(!qq.empty()){
		pii cur = qq.front(); qq.pop();
		if(cur.ff + cur.ss < m && umin(dd[cur.ff + cur.ss][cur.ss], dd[cur.ff][cur.ss] + 1)) qq.push({cur.ff + cur.ss, cur.ss});
		if(cur.ff - cur.ss >= 0 && umin(dd[cur.ff - cur.ss][cur.ss], dd[cur.ff][cur.ss] + 1)) qq.push({cur.ff - cur.ss, cur.ss});
		for(auto x : cnt[cur.ff]){
			umin(dd[cur.ff][p[x]], dd[cur.ff][cur.ss]);
			if(cur.ff + p[x] < m && umin(dd[cur.ff + p[x]][p[x]], dd[cur.ff][cur.ss] + 1)) qq.push({cur.ff + p[x], p[x]});
			if(cur.ff - p[x] >= 0 && umin(dd[cur.ff - p[x]][p[x]], dd[cur.ff][cur.ss] + 1)) qq.push({cur.ff - p[x], p[x]});
		} 
	} for(int i=0;i<M;i++) umin(res, dd[b[1]][i]);
	if(res != mod) cout<<res<<"\n";
	else cout<<-1<<"\n";
}
 
signed main(){ 
	NeedForSpeed
	if(!MULTI) {
		solve(1);
	} else {
		int t; cin>>t;
		for(int t_case = 1; t_case <= t; t_case++) solve(t_case);
	} return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16716 KB Output is correct
2 Correct 9 ms 16716 KB Output is correct
3 Correct 9 ms 16716 KB Output is correct
4 Correct 9 ms 16716 KB Output is correct
5 Correct 9 ms 16752 KB Output is correct
6 Correct 9 ms 16684 KB Output is correct
7 Correct 9 ms 16716 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16716 KB Output is correct
2 Correct 9 ms 16776 KB Output is correct
3 Correct 9 ms 16716 KB Output is correct
4 Correct 9 ms 16652 KB Output is correct
5 Correct 9 ms 16720 KB Output is correct
6 Correct 9 ms 16676 KB Output is correct
7 Correct 9 ms 16712 KB Output is correct
8 Correct 11 ms 16712 KB Output is correct
9 Correct 9 ms 16776 KB Output is correct
10 Correct 9 ms 16716 KB Output is correct
11 Correct 10 ms 16804 KB Output is correct
12 Correct 9 ms 16788 KB Output is correct
13 Correct 9 ms 16788 KB Output is correct
14 Correct 9 ms 16716 KB Output is correct
15 Correct 10 ms 16788 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16716 KB Output is correct
2 Correct 9 ms 16716 KB Output is correct
3 Correct 9 ms 16716 KB Output is correct
4 Correct 9 ms 16716 KB Output is correct
5 Correct 9 ms 16724 KB Output is correct
6 Correct 9 ms 16716 KB Output is correct
7 Correct 9 ms 16736 KB Output is correct
8 Correct 9 ms 16712 KB Output is correct
9 Correct 9 ms 16716 KB Output is correct
10 Correct 9 ms 16728 KB Output is correct
11 Correct 10 ms 16716 KB Output is correct
12 Correct 10 ms 16716 KB Output is correct
13 Correct 9 ms 16716 KB Output is correct
14 Correct 10 ms 16716 KB Output is correct
15 Correct 10 ms 16716 KB Output is correct
16 Correct 9 ms 16788 KB Output is correct
17 Correct 10 ms 16828 KB Output is correct
18 Correct 10 ms 16776 KB Output is correct
19 Correct 9 ms 16788 KB Output is correct
20 Correct 9 ms 16844 KB Output is correct
21 Correct 10 ms 16788 KB Output is correct
22 Correct 9 ms 16748 KB Output is correct
23 Correct 10 ms 16716 KB Output is correct
24 Correct 11 ms 16844 KB Output is correct
25 Correct 10 ms 16844 KB Output is correct
26 Correct 10 ms 16788 KB Output is correct
27 Correct 10 ms 16796 KB Output is correct
28 Correct 11 ms 16796 KB Output is correct
29 Correct 11 ms 16720 KB Output is correct
30 Correct 10 ms 16776 KB Output is correct
31 Correct 10 ms 16716 KB Output is correct
32 Correct 10 ms 16716 KB Output is correct
33 Correct 14 ms 16756 KB Output is correct
34 Correct 15 ms 16828 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16716 KB Output is correct
2 Correct 9 ms 16716 KB Output is correct
3 Correct 9 ms 16716 KB Output is correct
4 Correct 9 ms 16716 KB Output is correct
5 Correct 10 ms 16716 KB Output is correct
6 Correct 9 ms 16716 KB Output is correct
7 Correct 9 ms 16716 KB Output is correct
8 Correct 9 ms 16716 KB Output is correct
9 Correct 9 ms 16716 KB Output is correct
10 Correct 9 ms 16716 KB Output is correct
11 Correct 10 ms 16832 KB Output is correct
12 Correct 9 ms 16716 KB Output is correct
13 Correct 9 ms 16796 KB Output is correct
14 Correct 10 ms 16716 KB Output is correct
15 Correct 10 ms 16820 KB Output is correct
16 Correct 9 ms 16724 KB Output is correct
17 Correct 11 ms 16776 KB Output is correct
18 Correct 9 ms 16756 KB Output is correct
19 Correct 9 ms 16716 KB Output is correct
20 Correct 10 ms 16856 KB Output is correct
21 Correct 10 ms 16716 KB Output is correct
22 Correct 9 ms 16716 KB Output is correct
23 Correct 11 ms 16716 KB Output is correct
24 Correct 10 ms 16844 KB Output is correct
25 Correct 10 ms 16792 KB Output is correct
26 Correct 10 ms 16768 KB Output is correct
27 Correct 10 ms 16716 KB Output is correct
28 Correct 11 ms 16844 KB Output is correct
29 Correct 11 ms 16716 KB Output is correct
30 Correct 10 ms 16716 KB Output is correct
31 Correct 10 ms 16784 KB Output is correct
32 Correct 10 ms 16716 KB Output is correct
33 Correct 13 ms 16716 KB Output is correct
34 Correct 13 ms 16836 KB Output is correct
35 Correct 45 ms 17476 KB Output is correct
36 Correct 12 ms 16844 KB Output is correct
37 Correct 59 ms 17484 KB Output is correct
38 Correct 72 ms 17604 KB Output is correct
39 Correct 70 ms 17700 KB Output is correct
40 Correct 74 ms 17612 KB Output is correct
41 Correct 68 ms 17644 KB Output is correct
42 Correct 15 ms 17380 KB Output is correct
43 Correct 14 ms 17348 KB Output is correct
44 Correct 14 ms 17432 KB Output is correct
45 Correct 47 ms 17644 KB Output is correct
46 Correct 49 ms 17612 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16716 KB Output is correct
2 Correct 9 ms 16716 KB Output is correct
3 Correct 9 ms 16716 KB Output is correct
4 Correct 10 ms 16716 KB Output is correct
5 Correct 9 ms 16716 KB Output is correct
6 Correct 9 ms 16716 KB Output is correct
7 Correct 9 ms 16756 KB Output is correct
8 Correct 9 ms 16716 KB Output is correct
9 Correct 10 ms 16716 KB Output is correct
10 Correct 9 ms 16716 KB Output is correct
11 Correct 10 ms 16768 KB Output is correct
12 Correct 9 ms 16716 KB Output is correct
13 Correct 9 ms 16716 KB Output is correct
14 Correct 9 ms 16716 KB Output is correct
15 Correct 10 ms 16828 KB Output is correct
16 Correct 9 ms 16672 KB Output is correct
17 Correct 11 ms 16716 KB Output is correct
18 Correct 9 ms 16716 KB Output is correct
19 Correct 9 ms 16716 KB Output is correct
20 Correct 9 ms 16844 KB Output is correct
21 Correct 9 ms 16716 KB Output is correct
22 Correct 9 ms 16748 KB Output is correct
23 Correct 10 ms 16716 KB Output is correct
24 Correct 11 ms 16756 KB Output is correct
25 Correct 10 ms 16844 KB Output is correct
26 Correct 10 ms 16716 KB Output is correct
27 Correct 10 ms 16820 KB Output is correct
28 Correct 11 ms 16844 KB Output is correct
29 Correct 11 ms 16716 KB Output is correct
30 Correct 9 ms 16716 KB Output is correct
31 Correct 10 ms 16772 KB Output is correct
32 Correct 10 ms 16716 KB Output is correct
33 Correct 14 ms 16716 KB Output is correct
34 Correct 13 ms 16832 KB Output is correct
35 Correct 47 ms 17408 KB Output is correct
36 Correct 12 ms 16792 KB Output is correct
37 Correct 57 ms 17356 KB Output is correct
38 Correct 70 ms 17696 KB Output is correct
39 Correct 69 ms 17636 KB Output is correct
40 Correct 67 ms 17692 KB Output is correct
41 Correct 69 ms 17612 KB Output is correct
42 Correct 14 ms 17348 KB Output is correct
43 Correct 14 ms 17372 KB Output is correct
44 Correct 14 ms 17424 KB Output is correct
45 Correct 47 ms 17636 KB Output is correct
46 Correct 47 ms 17640 KB Output is correct
47 Runtime error 34 ms 35012 KB Execution killed with signal 11
48 Halted 0 ms 0 KB -