#include <bits/stdc++.h>
#include "aliens.h"
using ll = long long;
using namespace std;
const int MAXN = 510;
ll dp[MAXN][MAXN], inter[MAXN];
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
vector<pair<int, int>> v;
for(int i=0; i<n; i++){
if(r[i] > c[i]) swap(r[i], c[i]);
v.push_back({r[i], c[i]});
}
vector<pair<int, int>> cells;
int max_r = 0;
for(auto [r, c] : v){
if(max_r < c){
cells.push_back({r, c});
max_r = c;
}
}
n = cells.size();
for(int i=1; i<n; i++){
if(cells[i].first <= cells[i - 1].second){
inter[i] = (cells[i - 1].second - cells[i].first + 1) * (cells[i - 1].second - cells[i].first + 1);
}
}
dp[0][0] = 0;
for(int i=1; i<=n; i++) dp[i][0] = 1e9;
for(int i=1; i<=n; i++){
for(int j=1; j<=k; j++){
dp[i][j] = 1e9;
for(int l=0; l<i; l++){
ll cost = (cells[i - 1].second - cells[l].first + 1) * (cells[i - 1].second - cells[l].first + 1);
dp[i][j] = min(dp[i][j], dp[l][j - 1] + cost - inter[l]);
}
}
}
return dp[n][k];
}
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 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... |