Submission #124109

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
124109	2019-07-02T14:25:01 Z	mechfrog88	Safety (NOI18_safety)	C++14	24 / 100	2000 ms	262144 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(22222,LLONG_MAX);

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 <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	3 ms	1016 KB	Output is correct
4	Correct	3 ms	1144 KB	Output is correct
5	Correct	3 ms	1144 KB	Output is correct
6	Correct	3 ms	1016 KB	Output is correct
7	Correct	3 ms	1144 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	1272 KB	Output is correct
4	Correct	4 ms	1192 KB	Output is correct
5	Correct	4 ms	1240 KB	Output is correct

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	5 ms	2040 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	230 ms	262144 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	3 ms	1016 KB	Output is correct
4	Correct	3 ms	1144 KB	Output is correct
5	Correct	3 ms	1144 KB	Output is correct
6	Correct	3 ms	1016 KB	Output is correct
7	Correct	3 ms	1144 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	1272 KB	Output is correct
11	Correct	4 ms	1192 KB	Output is correct
12	Correct	4 ms	1240 KB	Output is correct
13	Correct	76 ms	22392 KB	Output is correct
14	Correct	67 ms	21752 KB	Output is correct
15	Correct	63 ms	21736 KB	Output is correct
16	Correct	75 ms	22392 KB	Output is correct
17	Correct	54 ms	19968 KB	Output is correct
18	Correct	55 ms	16552 KB	Output is correct
19	Correct	68 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	3 ms	1016 KB	Output is correct
4	Correct	3 ms	1144 KB	Output is correct
5	Correct	3 ms	1144 KB	Output is correct
6	Correct	3 ms	1016 KB	Output is correct
7	Correct	3 ms	1144 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	1272 KB	Output is correct
11	Correct	4 ms	1192 KB	Output is correct
12	Correct	4 ms	1240 KB	Output is correct
13	Correct	76 ms	22392 KB	Output is correct
14	Correct	67 ms	21752 KB	Output is correct
15	Correct	63 ms	21736 KB	Output is correct
16	Correct	75 ms	22392 KB	Output is correct
17	Correct	54 ms	19968 KB	Output is correct
18	Correct	55 ms	16552 KB	Output is correct
19	Correct	68 ms	21404 KB	Output is correct
20	Correct	289 ms	20956 KB	Output is correct
21	Correct	485 ms	22520 KB	Output is correct
22	Correct	282 ms	18812 KB	Output is correct
23	Correct	190 ms	17528 KB	Output is correct
24	Correct	417 ms	20828 KB	Output is correct
25	Correct	294 ms	17708 KB	Output is correct
26	Correct	509 ms	22540 KB	Output is correct
27	Correct	325 ms	20856 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	3 ms	1016 KB	Output is correct
4	Correct	3 ms	1144 KB	Output is correct
5	Correct	3 ms	1144 KB	Output is correct
6	Correct	3 ms	1016 KB	Output is correct
7	Correct	3 ms	1144 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	1272 KB	Output is correct
11	Correct	4 ms	1192 KB	Output is correct
12	Correct	4 ms	1240 KB	Output is correct
13	Correct	76 ms	22392 KB	Output is correct
14	Correct	67 ms	21752 KB	Output is correct
15	Correct	63 ms	21736 KB	Output is correct
16	Correct	75 ms	22392 KB	Output is correct
17	Correct	54 ms	19968 KB	Output is correct
18	Correct	55 ms	16552 KB	Output is correct
19	Correct	68 ms	21404 KB	Output is correct
20	Correct	289 ms	20956 KB	Output is correct
21	Correct	485 ms	22520 KB	Output is correct
22	Correct	282 ms	18812 KB	Output is correct
23	Correct	190 ms	17528 KB	Output is correct
24	Correct	417 ms	20828 KB	Output is correct
25	Correct	294 ms	17708 KB	Output is correct
26	Correct	509 ms	22540 KB	Output is correct
27	Correct	325 ms	20856 KB	Output is correct
28	Execution timed out	2069 ms	218280 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	3 ms	1016 KB	Output is correct
4	Correct	3 ms	1144 KB	Output is correct
5	Correct	3 ms	1144 KB	Output is correct
6	Correct	3 ms	1016 KB	Output is correct
7	Correct	3 ms	1144 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	1272 KB	Output is correct
11	Correct	4 ms	1192 KB	Output is correct
12	Correct	4 ms	1240 KB	Output is correct
13	Runtime error	5 ms	2040 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	3 ms	1016 KB	Output is correct
4	Correct	3 ms	1144 KB	Output is correct
5	Correct	3 ms	1144 KB	Output is correct
6	Correct	3 ms	1016 KB	Output is correct
7	Correct	3 ms	1144 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	1272 KB	Output is correct
11	Correct	4 ms	1192 KB	Output is correct
12	Correct	4 ms	1240 KB	Output is correct
13	Runtime error	5 ms	2040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Halted	0 ms	0 KB	-

Submission #124109

Compilation message