#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> l, vector<int> r){
vector<pair<int, int>> v;
for(int i=0; i<n; i++){
if(l[i] > r[i]) swap(l[i], r[i]);
v.push_back({l[i], r[i]});
}
sort(v.begin(), v.end());
vector<pair<int, int>> c;
int max_r = 0;
for(auto [l, r] : v){
if(max_r < r){
if(max_r >= l){
if(!c.empty()){
inter[c.size()] = (max_r - l + 1) * (max_r - l + 1);
}
}
c.push_back({l, r});
max_r = r;
}
}
n = c.size();
dp[0][0] = 0;
for(int i=1; i<=n; i++) dp[i][0] = 1e9;
for(int i=1; i<=n; i++){
for(int k=1; k<=K; k++){
dp[i][k] = 1e9;
for(int j=0; j<i; j++){
ll cost = (c[i - 1].second - c[j].first + 1) * (c[i - 1].second - c[j].first + 1);
dp[i][k] = min(dp[i][k], dp[j][k - 1] + cost - inter[j]);
}
}
}
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... |