Submission #146578

#TimeUsernameProblemLanguageResultExecution timeMemory
146578jwvg0425Safety (NOI18_safety)C++17
18 / 100
132 ms3704 KiB
#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; } for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); if (n > 500) { 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 (stderr)

safety.cpp: In function 'void h0()':
safety.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &s[i]);
   ~~~~~^~~~~~~~~~~~~
safety.cpp: In function 'int main()':
safety.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &h);
  ~~~~~^~~~~~~~~~~~~~~~~
safety.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &arr[i]);
   ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...