이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
const long long INF = 2e18 + 5;
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
if(n <= 50 && m <= 100 && k == n){
vector<vector<bool>> arr(m, vector<bool>(m, false));
for(int x = 0; x < n; x++){
for(int i = min(c[x], r[x]); i <= max(c[x], r[x]); i++){
for(int j = min(c[x], r[x]); j <= max(c[x], r[x]); j++){
arr[i][j] = true;
}
}
}
int ans = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < m; j++){
ans += arr[i][j];
}
}
return ans;
}
else{
vector<vector<long long>> dp(n + 5, vector<long long>(k + 5, INF));
vector<int> v = {-1};
for(auto x : r) v.push_back(x);
sort(v.begin(), v.end());
dp[0][0] = 0;
for(int r = 1; r <= n; r++){
for(int l = r; l >= 1; l--){
for(int i = 1; i <= k; i++){
dp[r][i] = min(dp[r][i], dp[l - 1][i - 1] + 1ll * (v[r] - v[l] + 1) * (v[r] - v[l] + 1));
}
}
}
return *min_element(dp[n].begin(), dp[n].end());
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |