이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
#define INT int64_t
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
const INT MXN=4e3+5, INF=1e9;
INT N,M,K;
array<INT,2> arr[MXN];
INT dp[MXN][MXN];
bool cc1(const array<INT,2> &a, const array<INT,2> &b) {
if (a[0]==b[0]) {
return a[1]>b[1];
}
return a[0]<b[0];
}
bool cc2(const array<INT,2> &a, const array<INT,2> &b) {
return a[1]<b[1];
}
INT take_photos(int32_t n, int m, int k, vector<int> r, vector<int> c) {
N = n, M = m, K = k;
for (int i=1; i<=N; i++) {
arr[i] = {min(r[i-1],c[i-1]),max(r[i-1],c[i-1])};
}
arr[0] = {-INF,-INF};
sort(arr,arr+N+1,cc1);
INT pv = 0,sub = 0;
for (int i=1; i<=N; i++) {
if (arr[pv][1] >= arr[i][1]) {
sub++; arr[i] = {INF,INF};
} else pv = i;
}
sort(arr,arr+1+N,cc2);
N -= sub; K = min(K,N);
memset(dp,0x3f,sizeof(dp));
dp[0][0] = 0;
for (int i=1; i<=N; i++) {
for (int j=1; j<=K; j++) {
for (int p=0; p<i; p++) {
INT area = (arr[i][1]-arr[p+1][0]+1)*(arr[i][1]-arr[p+1][0]+1);
INT dif = 1ll*max(0ll,arr[p][1]-arr[p+1][0]+1ll)*max(0ll,arr[p][1]-arr[p+1][0]+1ll);
area -= dif;
dp[i][j] = min(dp[i][j],dp[p][j-1]+area);
}
}
}
return dp[N][K];
}
/*
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int a,b,c; cin>>a>>b>>c;
vector<int> x(a),y(a);
for (int i=0; i<a; i++) {
cin>>x[i]>>y[i];
}
cout<<take_photos(a,b,c,x,y);
return 0;
}
*/
# | 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... |