# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
146579 | 2019-08-24T13:27:31 Z | jwvg0425 | Safety (NOI18_safety) | C++17 | 143 ms | 1968 KB |
#include <stdio.h> #include <vector> #include <queue> #include <algorithm> #include <iostream> #include <string> #include <bitset> #include <map> #include <set> #include <tuple> #include <string.h> #include <math.h> #include <random> #include <functional> #include <assert.h> #include <math.h> #define all(x) (x).begin(), (x).end() #define xx first #define yy second #define MOD 998244353 #define BUCKET 700 using namespace std; using i64 = long long int; using ii = pair<int, int>; using ii64 = pair<i64, i64>; int n, h; void h0() { vector<int> s(n); for (int i = 0; i < n; i++) scanf("%d", &s[i]); sort(all(s)); int m = s[n / 2]; i64 ans = 0; for (int i = 0; i < n; i++) ans += abs(m - s[i]); printf("%lld\n", ans); } int arr[200005]; i64 table[505][405]; int main() { scanf("%d %d", &n, &h); if (h == 0) { h0(); return 0; } if (n > 500) { printf("-1\n"); return 0; } for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); if (arr[i] > 400) { printf("-1\n"); return 0; } } memset(table, -1, sizeof(table)); for (int v = 0; v <= 400; v++) table[n - 1][v] = 0; for (int idx = n - 2; idx >= 0; idx--) { for (int v = 0; v <= 400; v++) { for (int s = max(0, v - h); s <= min(400, v + h); s++) { auto now = abs(arr[idx + 1] - s) + table[idx + 1][s]; if (table[idx][v] == -1 || now < table[idx][v]) table[idx][v] = now; } } } i64 ans = table[0][arr[0]]; for (int i = 0; i <= 400; i++) ans = min(ans, abs(i - arr[0]) + table[0][i]); printf("%lld\n", ans); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1912 KB | Output is correct |
2 | Correct | 4 ms | 1912 KB | Output is correct |
3 | Correct | 2 ms | 380 KB | Output is correct |
4 | Correct | 6 ms | 1912 KB | Output is correct |
5 | Correct | 3 ms | 1912 KB | Output is correct |
6 | Correct | 3 ms | 1912 KB | Output is correct |
7 | Correct | 3 ms | 1912 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 1912 KB | Output is correct |
3 | Correct | 3 ms | 1912 KB | Output is correct |
4 | Correct | 4 ms | 1912 KB | Output is correct |
5 | Correct | 3 ms | 1912 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 256 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 38 ms | 888 KB | Output is correct |
2 | Correct | 55 ms | 1144 KB | Output is correct |
3 | Correct | 56 ms | 1144 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1912 KB | Output is correct |
2 | Correct | 4 ms | 1912 KB | Output is correct |
3 | Correct | 2 ms | 380 KB | Output is correct |
4 | Correct | 6 ms | 1912 KB | Output is correct |
5 | Correct | 3 ms | 1912 KB | Output is correct |
6 | Correct | 3 ms | 1912 KB | Output is correct |
7 | Correct | 3 ms | 1912 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 3 ms | 1912 KB | Output is correct |
10 | Correct | 3 ms | 1912 KB | Output is correct |
11 | Correct | 4 ms | 1912 KB | Output is correct |
12 | Correct | 3 ms | 1912 KB | Output is correct |
13 | Correct | 12 ms | 1912 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 143 ms | 1968 KB | Output is correct |
16 | Correct | 95 ms | 1912 KB | Output is correct |
17 | Correct | 132 ms | 1912 KB | Output is correct |
18 | Correct | 92 ms | 1912 KB | Output is correct |
19 | Correct | 5 ms | 1912 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1912 KB | Output is correct |
2 | Correct | 4 ms | 1912 KB | Output is correct |
3 | Correct | 2 ms | 380 KB | Output is correct |
4 | Correct | 6 ms | 1912 KB | Output is correct |
5 | Correct | 3 ms | 1912 KB | Output is correct |
6 | Correct | 3 ms | 1912 KB | Output is correct |
7 | Correct | 3 ms | 1912 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 3 ms | 1912 KB | Output is correct |
10 | Correct | 3 ms | 1912 KB | Output is correct |
11 | Correct | 4 ms | 1912 KB | Output is correct |
12 | Correct | 3 ms | 1912 KB | Output is correct |
13 | Correct | 12 ms | 1912 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 143 ms | 1968 KB | Output is correct |
16 | Correct | 95 ms | 1912 KB | Output is correct |
17 | Correct | 132 ms | 1912 KB | Output is correct |
18 | Correct | 92 ms | 1912 KB | Output is correct |
19 | Correct | 5 ms | 1912 KB | Output is correct |
20 | Incorrect | 2 ms | 256 KB | Output isn't correct |
21 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1912 KB | Output is correct |
2 | Correct | 4 ms | 1912 KB | Output is correct |
3 | Correct | 2 ms | 380 KB | Output is correct |
4 | Correct | 6 ms | 1912 KB | Output is correct |
5 | Correct | 3 ms | 1912 KB | Output is correct |
6 | Correct | 3 ms | 1912 KB | Output is correct |
7 | Correct | 3 ms | 1912 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 3 ms | 1912 KB | Output is correct |
10 | Correct | 3 ms | 1912 KB | Output is correct |
11 | Correct | 4 ms | 1912 KB | Output is correct |
12 | Correct | 3 ms | 1912 KB | Output is correct |
13 | Correct | 12 ms | 1912 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 143 ms | 1968 KB | Output is correct |
16 | Correct | 95 ms | 1912 KB | Output is correct |
17 | Correct | 132 ms | 1912 KB | Output is correct |
18 | Correct | 92 ms | 1912 KB | Output is correct |
19 | Correct | 5 ms | 1912 KB | Output is correct |
20 | Incorrect | 2 ms | 256 KB | Output isn't correct |
21 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1912 KB | Output is correct |
2 | Correct | 4 ms | 1912 KB | Output is correct |
3 | Correct | 2 ms | 380 KB | Output is correct |
4 | Correct | 6 ms | 1912 KB | Output is correct |
5 | Correct | 3 ms | 1912 KB | Output is correct |
6 | Correct | 3 ms | 1912 KB | Output is correct |
7 | Correct | 3 ms | 1912 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 3 ms | 1912 KB | Output is correct |
10 | Correct | 3 ms | 1912 KB | Output is correct |
11 | Correct | 4 ms | 1912 KB | Output is correct |
12 | Correct | 3 ms | 1912 KB | Output is correct |
13 | Incorrect | 2 ms | 256 KB | Output isn't correct |
14 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1912 KB | Output is correct |
2 | Correct | 4 ms | 1912 KB | Output is correct |
3 | Correct | 2 ms | 380 KB | Output is correct |
4 | Correct | 6 ms | 1912 KB | Output is correct |
5 | Correct | 3 ms | 1912 KB | Output is correct |
6 | Correct | 3 ms | 1912 KB | Output is correct |
7 | Correct | 3 ms | 1912 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 3 ms | 1912 KB | Output is correct |
10 | Correct | 3 ms | 1912 KB | Output is correct |
11 | Correct | 4 ms | 1912 KB | Output is correct |
12 | Correct | 3 ms | 1912 KB | Output is correct |
13 | Incorrect | 2 ms | 256 KB | Output isn't correct |
14 | Halted | 0 ms | 0 KB | - |