This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
#define db(x) cout<<#x<<" = "<<x<<"\n";
#define fore(i,a,b) for(int i=a,ggdem=b;i<ggdem;i++)
#define FIN ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define SZ(a) ((int)(a).size())
#define ALL(a) a.begin(),a.end()
#define mset(a,b) memset(a,b,sizeof(a));
#define pb push_back
#define fst first
#define snd second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll INF=1e15;
ll sq(ll x){return x*x;}
ll subtask_one(int n,int m,int k,vector<int>r,vector<int>c) {
vector<vector<int>>g(m,vector<int>(m));
if(k<0)assert(0);
fore(i,0,m)fore(j,0,m)assert(g[i][j]==0);
fore(i,0,n) {
fore(j,min(r[i],c[i]),max(r[i],c[i])+1) {
fore(k,min(r[i],c[i]),max(r[i],c[i])+1) {
g[j][k]=1;
}
}
}
// fore(i,0,n){fore(j,0,n)cout<<g[i][j];cout<<endl;}
int res=0;
fore(i,0,m)fore(j,0,m)res+=g[i][j];
return res;
}
ll solve(int i,int j,vector<int> &v,vector<vector<ll>> &dp) {
if(i==SZ(v))return 0;
if(j<0)return INF;
if(dp[i][j]!=-1)return dp[i][j];
ll res=INF;
fore(to,i,SZ(v)) {
res=min(res,sq(v[to]-v[i]+1)+solve(to+1,j-1,v,dp));
}
return dp[i][j]=res;
}
ll subtask_two(int n,int m,int k,vector<int> r,vector<int> c) {
sort(ALL(r));sort(ALL(c));
assert(m>=0);
vector<vector<ll>>dp(n,vector<ll>(k,-1));
return solve(0,k-1,c,dp);
}
ll take_photos(int n,int m,int k,vector<int>r,vector<int> c) {
if(n<=50 && m<=50 && k==n)return subtask_one(n,m,k,r,c);
return subtask_two(n,m,k,r,c);
}
/* 100 100 50 50 100
int main() {FIN;
int n,m,k;
cin>>n>>m>>k;
vector<int>r(n),c(n);
fore(i,0,n)cin>>r[i]>>c[i];
cout<<take_photos(n,m,k,r,c)<<"\n";
}
*/
/*
5 7 2
0 3
4 4
4 6
4 5
4 6
---> 25
2 5 2
1 4
4 1
---> 16
*/
# | 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... |