Submission #124082

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
124082	2019-07-02T13:42:53 Z	mechfrog88	Safety (NOI18_safety)	C++14	24 / 100	2000 ms	262148 KB

safety

#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(5555*4);

void build(ll id = 1, ll l = 0, ll r = 5555){
	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 = 5555){
	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 <vector<ll>> dp(n+1,vector<ll>(5555,0));
	vector <ll> arr(n+1);
	ll maxi = 0;
	for (int z=1;z<=n;z++){
		cin >> arr[z];
		maxi = max(maxi,arr[z]);
	}
	for (int z=1;z<=n;z++){
		a = dp[z-1];
		build();
		for (int h=0;h<=maxi;h++){
			ll temp = query(h-d,min(maxi+1,h+d+1));
			dp[z][h] = temp+abs(arr[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	4 ms	1016 KB	Output is correct
2	Correct	3 ms	1144 KB	Output is correct
3	Correct	2 ms	888 KB	Output is correct
4	Correct	3 ms	1016 KB	Output is correct
5	Correct	3 ms	1016 KB	Output is correct
6	Correct	3 ms	1016 KB	Output is correct
7	Correct	3 ms	1016 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1272 KB	Output is correct
2	Correct	4 ms	1272 KB	Output is correct
3	Correct	3 ms	1144 KB	Output is correct
4	Correct	4 ms	1240 KB	Output is correct
5	Correct	5 ms	1272 KB	Output is correct

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	5 ms	1912 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	267 ms	262148 KB	Execution killed with signal 9 (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	4 ms	1016 KB	Output is correct
2	Correct	3 ms	1144 KB	Output is correct
3	Correct	2 ms	888 KB	Output is correct
4	Correct	3 ms	1016 KB	Output is correct
5	Correct	3 ms	1016 KB	Output is correct
6	Correct	3 ms	1016 KB	Output is correct
7	Correct	3 ms	1016 KB	Output is correct
8	Correct	4 ms	1272 KB	Output is correct
9	Correct	4 ms	1272 KB	Output is correct
10	Correct	3 ms	1144 KB	Output is correct
11	Correct	4 ms	1240 KB	Output is correct
12	Correct	5 ms	1272 KB	Output is correct
13	Correct	105 ms	22520 KB	Output is correct
14	Correct	78 ms	21752 KB	Output is correct
15	Correct	81 ms	21808 KB	Output is correct
16	Correct	90 ms	22364 KB	Output is correct
17	Correct	68 ms	19836 KB	Output is correct
18	Correct	57 ms	16632 KB	Output is correct
19	Correct	78 ms	21404 KB	Output is correct

Subtask #6
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1016 KB	Output is correct
2	Correct	3 ms	1144 KB	Output is correct
3	Correct	2 ms	888 KB	Output is correct
4	Correct	3 ms	1016 KB	Output is correct
5	Correct	3 ms	1016 KB	Output is correct
6	Correct	3 ms	1016 KB	Output is correct
7	Correct	3 ms	1016 KB	Output is correct
8	Correct	4 ms	1272 KB	Output is correct
9	Correct	4 ms	1272 KB	Output is correct
10	Correct	3 ms	1144 KB	Output is correct
11	Correct	4 ms	1240 KB	Output is correct
12	Correct	5 ms	1272 KB	Output is correct
13	Correct	105 ms	22520 KB	Output is correct
14	Correct	78 ms	21752 KB	Output is correct
15	Correct	81 ms	21808 KB	Output is correct
16	Correct	90 ms	22364 KB	Output is correct
17	Correct	68 ms	19836 KB	Output is correct
18	Correct	57 ms	16632 KB	Output is correct
19	Correct	78 ms	21404 KB	Output is correct
20	Correct	344 ms	20936 KB	Output is correct
21	Correct	542 ms	22460 KB	Output is correct
22	Correct	312 ms	18936 KB	Output is correct
23	Correct	221 ms	17400 KB	Output is correct
24	Correct	470 ms	20984 KB	Output is correct
25	Correct	345 ms	17656 KB	Output is correct
26	Correct	634 ms	22520 KB	Output is correct
27	Correct	369 ms	20936 KB	Output is correct

Subtask #7
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1016 KB	Output is correct
2	Correct	3 ms	1144 KB	Output is correct
3	Correct	2 ms	888 KB	Output is correct
4	Correct	3 ms	1016 KB	Output is correct
5	Correct	3 ms	1016 KB	Output is correct
6	Correct	3 ms	1016 KB	Output is correct
7	Correct	3 ms	1016 KB	Output is correct
8	Correct	4 ms	1272 KB	Output is correct
9	Correct	4 ms	1272 KB	Output is correct
10	Correct	3 ms	1144 KB	Output is correct
11	Correct	4 ms	1240 KB	Output is correct
12	Correct	5 ms	1272 KB	Output is correct
13	Correct	105 ms	22520 KB	Output is correct
14	Correct	78 ms	21752 KB	Output is correct
15	Correct	81 ms	21808 KB	Output is correct
16	Correct	90 ms	22364 KB	Output is correct
17	Correct	68 ms	19836 KB	Output is correct
18	Correct	57 ms	16632 KB	Output is correct
19	Correct	78 ms	21404 KB	Output is correct
20	Correct	344 ms	20936 KB	Output is correct
21	Correct	542 ms	22460 KB	Output is correct
22	Correct	312 ms	18936 KB	Output is correct
23	Correct	221 ms	17400 KB	Output is correct
24	Correct	470 ms	20984 KB	Output is correct
25	Correct	345 ms	17656 KB	Output is correct
26	Correct	634 ms	22520 KB	Output is correct
27	Correct	369 ms	20936 KB	Output is correct
28	Execution timed out	2048 ms	218256 KB	Time limit exceeded
29	Halted	0 ms	0 KB	-

Subtask #8
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1016 KB	Output is correct
2	Correct	3 ms	1144 KB	Output is correct
3	Correct	2 ms	888 KB	Output is correct
4	Correct	3 ms	1016 KB	Output is correct
5	Correct	3 ms	1016 KB	Output is correct
6	Correct	3 ms	1016 KB	Output is correct
7	Correct	3 ms	1016 KB	Output is correct
8	Correct	4 ms	1272 KB	Output is correct
9	Correct	4 ms	1272 KB	Output is correct
10	Correct	3 ms	1144 KB	Output is correct
11	Correct	4 ms	1240 KB	Output is correct
12	Correct	5 ms	1272 KB	Output is correct
13	Runtime error	5 ms	1912 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	4 ms	1016 KB	Output is correct
2	Correct	3 ms	1144 KB	Output is correct
3	Correct	2 ms	888 KB	Output is correct
4	Correct	3 ms	1016 KB	Output is correct
5	Correct	3 ms	1016 KB	Output is correct
6	Correct	3 ms	1016 KB	Output is correct
7	Correct	3 ms	1016 KB	Output is correct
8	Correct	4 ms	1272 KB	Output is correct
9	Correct	4 ms	1272 KB	Output is correct
10	Correct	3 ms	1144 KB	Output is correct
11	Correct	4 ms	1240 KB	Output is correct
12	Correct	5 ms	1272 KB	Output is correct
13	Runtime error	5 ms	1912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Halted	0 ms	0 KB	-

Submission #124082

Compilation message