제출 #773801

#제출 시각아이디문제언어결과실행 시간메모리
773801JomnoiAliens (IOI16_aliens)C++17
0 / 100
1 ms212 KiB
#include <bits/stdc++.h> #include "aliens.h" using namespace std; const int MAX_K = 1005; const int MAX_N = 1005; const int MAX_M = 1e6 + 5; const long long INF = 1e18 + 7; int N, M, K; long long dp[MAX_K][MAX_N]; int qs[MAX_N][MAX_N]; bool dead[MAX_N]; int minL[MAX_M]; long long take_photos(int n, int m, int k, vector <int> r, vector <int> c) { N = n, M = m, K = k; for (int i = 0; i < m; i++) minL[i] = M; for (int i = 0; i < N; i++) { int x = min(r[i], c[i]), y = max(r[i], c[i]); minL[y] = min(minL[y], x); } stack <pair <int, int>> stk; for (int i = 0; i < m; i++) { if (minL[i] == M) continue; while (!stk.empty() and stk.top().first >= minL[i]) stk.pop(); stk.emplace(minL[i], i); } vector <pair <int, int>> vec; while (!stk.empty()) { auto [x, y] = stk.top(); stk.pop(); vec.emplace_back(x, y); } N = vec.size(); reverse(vec.begin(), vec.end()); vec.push_back({M, M}); for (int i = 1; i <= N; i++) dp[0][i] = INF; for (int k = 1; k <= K; k++) { for (int i = 1; i <= N; i++) { dp[k][i] = INF; for (int j = i; j >= 1; j--) { long long cost = (vec[i - 1].second - vec[j - 1].first + 1) * (vec[i - 1].second - vec[j - 1].first + 1); long long overlap = max(0ll, 1ll * (vec[i - 1].second - vec[i].first + 1) * (vec[i - 1].second - vec[i].first + 1)); dp[k][i] = min(dp[k][i], cost + dp[k - 1][j - 1] - overlap); } } } long long ans = INF; for (int k = 1; k <= K; k++) ans = min(ans, dp[k][N]); return ans; }
#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...