제출 #873255

#제출 시각아이디문제언어결과실행 시간메모리
873255TurkhuuAliens (IOI16_aliens)C++17
12 / 100
59 ms4188 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; using ll = long long; ll sq(int x) { return (ll)x * x; } ll take_photos(int M, int N, int K, vector<int> R, vector<int> C) { vector<vector<int>> v(N); for (int i = 0; i < M; i++) { v[max(R[i], C[i])].push_back(min(R[i], C[i])); } vector<pair<int, int>> h; vector dp(N, vector<ll>(K + 1, 1e9)); for (int i = 0; i < N; i++) { if (v[i].empty()) { dp[i] = !i ? vector<ll>(K + 1, 0) : dp[i - 1]; continue; } for (int j : v[i]) h.emplace_back(j, i); sort(h.begin(), h.end()); int t = -1; for (auto [y, x] : h) { for (int k = 1; k <= K; k++) { if (t == -1) { dp[i][k] = min(dp[i][k], sq(i - y + 1)); } else { dp[i][k] = min(dp[i][k], dp[t][k - 1] + sq(i - y + 1) + (t < y ? 0 : sq(t - y + 1))); } } t = max(t, x); if (x == i) break; } } return *min_element(dp[N - 1].begin(), dp[N - 1].end()); }
#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...