Submission #1222337

#TimeUsernameProblemLanguageResultExecution timeMemory
1222337justAliens (IOI16_aliens)C++20
0 / 100
1 ms328 KiB
#include "aliens.h" #include "bits/stdc++.h" using namespace std; using ll = long long; template<typename T> using vec = vector<T>; using pii = pair<int, int>; #define all(x) x.begin(), x.end() int sq(int x) { return x * x; } vec<pii> a; #define L first #define R second const int STEP = 2; int memo[505][505] = {0}; bool done[505][505] = {false}; int calc(int i, int k) { if (i == -1) return 0; if (k == 0) return INT_MAX; if (k == 1) return sq(abs(a[0].L - a[i].R) + STEP); if (done[i][k]) return memo[i][k]; done[i][k] = true; int ans = sq(abs(a[0].L - a[i].R) + STEP); for (int j = 1; j <= i; j++) { ans = min(ans, calc(j - 1, k - 1) + sq(abs(a[j].L - a[i].R) + STEP) - sq(abs(a[j - 1].R - a[j].L) + STEP)); } return memo[i][k] = ans; } ll take_photos(int n, int m, int k, vec<int> r, vec<int> c) { a.resize(n); for (int i = 0; i < n; i++) { if (r[i] > c[i]) swap(r[i], c[i]); a[i] = {r[i] * STEP, c[i] * STEP}; } sort(all(a)); vec<bool> del(n, false); int mx = -1; for (int i = 0; i < n; i++) { auto [l, r] = a[i]; if (r <= mx) del[i] = true; mx = max(mx, r); } vec<pii> tmp; tmp.reserve(n); for (int i = 0; i < n; i++) { if (!del[i]) tmp.push_back(a[i]); } a = tmp; n = a.size(); return calc(n - 1, k) / (STEP * STEP); }

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#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...