#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4005;
const long long inf = (1LL << 62);
int n, m, k;
pair<int, int> points[maxn];
vector<pair<int, int>> v;
long long dp[maxn][maxn];
long long sq(long long x)
{
return x * x;
}
long long take_photos(int N, int M, int K, std::vector<int> r, std::vector<int> c)
{
m = M;
k = K;
for (int i = 1; i <= N; ++i)
{
int x = r[i - 1] + 1;
int y = c[i - 1] + 1;
if (x > y)
{
swap(x, y);
}
v.push_back({x, y});
//cout << "add " << x << " " << y << endl;
}
sort(v.begin(), v.end());
n = 0;
for (int i = 0; i < N; ++i)
{
if (i == 0 || v[i] != v[i - 1])
{
points[++n] = v[i];
//cout << "now " << points[i].first << " " << points[i].second << endl;
}
}
for (int i = 0; i <= n; ++i)
{
for (int j = 0; j <= k; ++j)
{
dp[i][j] = inf;
}
}
dp[0][0] = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= min(i, k); ++j)
{
for (int prv = j; prv <= i; ++prv)
{
long long cost = sq(points[i].second - points[prv].first + 1);
if (prv > 1 && points[prv - 1].second >= points[prv].first) cost -= sq(points[prv - 1].second - points[prv].first + 1);
dp[i][j] = min(dp[i][j], dp[prv - 1][j - 1] + cost);
}
//cout << i << " " << j << " :: " << dp[i][j] << endl;
}
}
long long ans = inf;
for (int i = 1; i <= k; ++i)
{
ans = min(ans, dp[n][i]);
}
return ans;
}
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... |