# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
124071 |
2019-07-02T13:23:12 Z |
mechfrog88 |
Safety (NOI18_safety) |
C++14 |
|
892 ms |
262148 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 <vector<ll>> sparse(15,vector<ll>(5001));
void build(vector <ll> arr){
for (ll z=0;z<15;z++){
for (ll x=0;x<5001;x++){
sparse[z][x] = LLONG_MAX;
if (x + (1 << z) - 1 < 5000){
if (z == 0) sparse[z][x] = arr[x];
else sparse[z][x] = min(sparse[z-1][x],sparse[z-1][x+(1<<(z-1))]);
}
}
}
}
ll query (ll l ,ll r){
int k = 31-__builtin_clz(r-l);
if (l == r) k = 0;
return min(sparse[k][l],sparse[k][r - (1 << k)+1]);
}
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>(5001,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++){
build(dp[z-1]);
for (int h=0;h<=maxi;h++){
ll temp = query(max(ll(0),h-d),min(ll(maxi),h+d));
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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1400 KB |
Output is correct |
2 |
Correct |
4 ms |
1400 KB |
Output is correct |
3 |
Correct |
4 ms |
1272 KB |
Output is correct |
4 |
Correct |
4 ms |
1400 KB |
Output is correct |
5 |
Correct |
4 ms |
1400 KB |
Output is correct |
6 |
Correct |
4 ms |
1400 KB |
Output is correct |
7 |
Correct |
4 ms |
1400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
1528 KB |
Output is correct |
2 |
Correct |
3 ms |
1656 KB |
Output is correct |
3 |
Correct |
5 ms |
1528 KB |
Output is correct |
4 |
Correct |
5 ms |
1532 KB |
Output is correct |
5 |
Correct |
5 ms |
1528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
5 ms |
2552 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
231 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1400 KB |
Output is correct |
2 |
Correct |
4 ms |
1400 KB |
Output is correct |
3 |
Correct |
4 ms |
1272 KB |
Output is correct |
4 |
Correct |
4 ms |
1400 KB |
Output is correct |
5 |
Correct |
4 ms |
1400 KB |
Output is correct |
6 |
Correct |
4 ms |
1400 KB |
Output is correct |
7 |
Correct |
4 ms |
1400 KB |
Output is correct |
8 |
Correct |
5 ms |
1528 KB |
Output is correct |
9 |
Correct |
3 ms |
1656 KB |
Output is correct |
10 |
Correct |
5 ms |
1528 KB |
Output is correct |
11 |
Correct |
5 ms |
1532 KB |
Output is correct |
12 |
Correct |
5 ms |
1528 KB |
Output is correct |
13 |
Correct |
86 ms |
20892 KB |
Output is correct |
14 |
Correct |
78 ms |
19960 KB |
Output is correct |
15 |
Correct |
79 ms |
20088 KB |
Output is correct |
16 |
Correct |
81 ms |
20728 KB |
Output is correct |
17 |
Correct |
73 ms |
18296 KB |
Output is correct |
18 |
Correct |
57 ms |
15480 KB |
Output is correct |
19 |
Correct |
78 ms |
19704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1400 KB |
Output is correct |
2 |
Correct |
4 ms |
1400 KB |
Output is correct |
3 |
Correct |
4 ms |
1272 KB |
Output is correct |
4 |
Correct |
4 ms |
1400 KB |
Output is correct |
5 |
Correct |
4 ms |
1400 KB |
Output is correct |
6 |
Correct |
4 ms |
1400 KB |
Output is correct |
7 |
Correct |
4 ms |
1400 KB |
Output is correct |
8 |
Correct |
5 ms |
1528 KB |
Output is correct |
9 |
Correct |
3 ms |
1656 KB |
Output is correct |
10 |
Correct |
5 ms |
1528 KB |
Output is correct |
11 |
Correct |
5 ms |
1532 KB |
Output is correct |
12 |
Correct |
5 ms |
1528 KB |
Output is correct |
13 |
Correct |
86 ms |
20892 KB |
Output is correct |
14 |
Correct |
78 ms |
19960 KB |
Output is correct |
15 |
Correct |
79 ms |
20088 KB |
Output is correct |
16 |
Correct |
81 ms |
20728 KB |
Output is correct |
17 |
Correct |
73 ms |
18296 KB |
Output is correct |
18 |
Correct |
57 ms |
15480 KB |
Output is correct |
19 |
Correct |
78 ms |
19704 KB |
Output is correct |
20 |
Correct |
85 ms |
19312 KB |
Output is correct |
21 |
Correct |
99 ms |
20692 KB |
Output is correct |
22 |
Correct |
80 ms |
17656 KB |
Output is correct |
23 |
Correct |
72 ms |
16064 KB |
Output is correct |
24 |
Correct |
85 ms |
19192 KB |
Output is correct |
25 |
Correct |
72 ms |
16424 KB |
Output is correct |
26 |
Correct |
92 ms |
20840 KB |
Output is correct |
27 |
Correct |
85 ms |
19192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1400 KB |
Output is correct |
2 |
Correct |
4 ms |
1400 KB |
Output is correct |
3 |
Correct |
4 ms |
1272 KB |
Output is correct |
4 |
Correct |
4 ms |
1400 KB |
Output is correct |
5 |
Correct |
4 ms |
1400 KB |
Output is correct |
6 |
Correct |
4 ms |
1400 KB |
Output is correct |
7 |
Correct |
4 ms |
1400 KB |
Output is correct |
8 |
Correct |
5 ms |
1528 KB |
Output is correct |
9 |
Correct |
3 ms |
1656 KB |
Output is correct |
10 |
Correct |
5 ms |
1528 KB |
Output is correct |
11 |
Correct |
5 ms |
1532 KB |
Output is correct |
12 |
Correct |
5 ms |
1528 KB |
Output is correct |
13 |
Correct |
86 ms |
20892 KB |
Output is correct |
14 |
Correct |
78 ms |
19960 KB |
Output is correct |
15 |
Correct |
79 ms |
20088 KB |
Output is correct |
16 |
Correct |
81 ms |
20728 KB |
Output is correct |
17 |
Correct |
73 ms |
18296 KB |
Output is correct |
18 |
Correct |
57 ms |
15480 KB |
Output is correct |
19 |
Correct |
78 ms |
19704 KB |
Output is correct |
20 |
Correct |
85 ms |
19312 KB |
Output is correct |
21 |
Correct |
99 ms |
20692 KB |
Output is correct |
22 |
Correct |
80 ms |
17656 KB |
Output is correct |
23 |
Correct |
72 ms |
16064 KB |
Output is correct |
24 |
Correct |
85 ms |
19192 KB |
Output is correct |
25 |
Correct |
72 ms |
16424 KB |
Output is correct |
26 |
Correct |
92 ms |
20840 KB |
Output is correct |
27 |
Correct |
85 ms |
19192 KB |
Output is correct |
28 |
Correct |
892 ms |
197000 KB |
Output is correct |
29 |
Correct |
726 ms |
166400 KB |
Output is correct |
30 |
Incorrect |
884 ms |
193752 KB |
Output isn't correct |
31 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1400 KB |
Output is correct |
2 |
Correct |
4 ms |
1400 KB |
Output is correct |
3 |
Correct |
4 ms |
1272 KB |
Output is correct |
4 |
Correct |
4 ms |
1400 KB |
Output is correct |
5 |
Correct |
4 ms |
1400 KB |
Output is correct |
6 |
Correct |
4 ms |
1400 KB |
Output is correct |
7 |
Correct |
4 ms |
1400 KB |
Output is correct |
8 |
Correct |
5 ms |
1528 KB |
Output is correct |
9 |
Correct |
3 ms |
1656 KB |
Output is correct |
10 |
Correct |
5 ms |
1528 KB |
Output is correct |
11 |
Correct |
5 ms |
1532 KB |
Output is correct |
12 |
Correct |
5 ms |
1528 KB |
Output is correct |
13 |
Runtime error |
5 ms |
2552 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1400 KB |
Output is correct |
2 |
Correct |
4 ms |
1400 KB |
Output is correct |
3 |
Correct |
4 ms |
1272 KB |
Output is correct |
4 |
Correct |
4 ms |
1400 KB |
Output is correct |
5 |
Correct |
4 ms |
1400 KB |
Output is correct |
6 |
Correct |
4 ms |
1400 KB |
Output is correct |
7 |
Correct |
4 ms |
1400 KB |
Output is correct |
8 |
Correct |
5 ms |
1528 KB |
Output is correct |
9 |
Correct |
3 ms |
1656 KB |
Output is correct |
10 |
Correct |
5 ms |
1528 KB |
Output is correct |
11 |
Correct |
5 ms |
1532 KB |
Output is correct |
12 |
Correct |
5 ms |
1528 KB |
Output is correct |
13 |
Runtime error |
5 ms |
2552 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
14 |
Halted |
0 ms |
0 KB |
- |