oj.uz

Submission #124121

# Submission time Handle Problem Language Result Execution time Memory
124121 2019-07-02T14:32:41 Z mechfrog88 Safety (NOI18_safety) C++14
24 / 100
 2000 ms 196656 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;	

vector <ll> a;
vector <ll> s;

void build(ll id = 1, ll l = 0, ll r = a.size()){
	if (r - l < 2) {
		s[id] = a[l];
		return;
	}
	ll mid = (l+r)/2;
	build (id*2,l,mid);
	build (id*2+1,mid,r);
	s[id] = min(s[id*2],s[id*2+1]);
}

ll query(ll x,ll y,ll id = 1, ll l = 0, ll r = a.size()){
	if (y <= l || x >= r) return LLONG_MAX;
	if (x <= l && r <= y) return s[id];
	ll mid = (l+r)/2;
	return min(query(x,y,id*2,l,mid),query(x,y,id*2+1,mid,r));
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,d;
	cin >> n >> d;
	vector <ll> arr(n+1);
	ll maxi = 0;
	for (int z=1;z<=n;z++){
		cin >> arr[z];
		maxi = max(maxi,arr[z]);
	}
	vector <vector<ll>> dp(n+1,vector<ll>(maxi+1,0));
	a.resize(maxi+1,0);
	for (int z=1;z<=n;z++){
		s.resize(a.size()*4);
		build();
		for (int h=0;h<=maxi;h++){
			ll temp = query(max(ll(0),h-d),min(maxi+1,h+d+1));
			dp[z][h] = temp+abs(arr[z]-h);
			a[h] = dp[z][h];
		}
	}
	ll mini = LLONG_MAX;
	for(int z=0;z<=maxi;z++){
		mini = min(dp[n][z],mini);
	}
	cout << mini << endl;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 296 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 4088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 296 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 29 ms 1988 KB Output is correct
14 Correct 22 ms 1928 KB Output is correct
15 Correct 6 ms 1912 KB Output is correct
16 Correct 23 ms 1912 KB Output is correct
17 Correct 6 ms 1784 KB Output is correct
18 Correct 14 ms 1528 KB Output is correct
19 Correct 22 ms 1912 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 296 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 29 ms 1988 KB Output is correct
14 Correct 22 ms 1928 KB Output is correct
15 Correct 6 ms 1912 KB Output is correct
16 Correct 23 ms 1912 KB Output is correct
17 Correct 6 ms 1784 KB Output is correct
18 Correct 14 ms 1528 KB Output is correct
19 Correct 22 ms 1912 KB Output is correct
20 Correct 184 ms 18836 KB Output is correct
21 Correct 500 ms 20124 KB Output is correct
22 Correct 313 ms 16932 KB Output is correct
23 Correct 41 ms 15608 KB Output is correct
24 Correct 399 ms 18844 KB Output is correct
25 Correct 220 ms 15864 KB Output is correct
26 Correct 535 ms 20216 KB Output is correct
27 Correct 354 ms 18936 KB Output is correct

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 296 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 29 ms 1988 KB Output is correct
14 Correct 22 ms 1928 KB Output is correct
15 Correct 6 ms 1912 KB Output is correct
16 Correct 23 ms 1912 KB Output is correct
17 Correct 6 ms 1784 KB Output is correct
18 Correct 14 ms 1528 KB Output is correct
19 Correct 22 ms 1912 KB Output is correct
20 Correct 184 ms 18836 KB Output is correct
21 Correct 500 ms 20124 KB Output is correct
22 Correct 313 ms 16932 KB Output is correct
23 Correct 41 ms 15608 KB Output is correct
24 Correct 399 ms 18844 KB Output is correct
25 Correct 220 ms 15864 KB Output is correct
26 Correct 535 ms 20216 KB Output is correct
27 Correct 354 ms 18936 KB Output is correct
28 Execution timed out 2069 ms 196656 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 296 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Runtime error 6 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -

Subtask #9
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 296 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Runtime error 6 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -