| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 399794 | Dremix10 | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#ifdef dremix
#define p(x) cerr<<#x<<" = "<<x<<endl;
#define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
#define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl;
#define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
#define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl;
#else
#define p(x) {}
#define p2(x,y) {}
#define pp(x) {}
#define pv(x) {}
#define ppv(x) {}
#endif
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);
const int maxp = 22;
const ld EPS = 1e-18;
const ll INF = 2e18;
const int MOD = 1e9+7;
const int N = 3e5+1;
int cnt;
int shuld;
int maxi;
int m;
bool cells[100][100] = {};
int pts[100][100] = {};
int solve(int k){
//p2(cnt,k)
if(shuld == cnt)
return 0;
if(k == maxi)
return MOD;
int i,j,ii,jj;
int best = MOD;
for(i=0;i<m;i++){
/// point i,i start
for(j=i;j<m;j++){
/// point j,j end
int cost = 0;
vector<pi> used;
for(ii=i;ii<=j;ii++){
for(jj=i;jj<=j;jj++){
if(!cells[ii][jj]){
cost++;
cells[ii][jj] = true;
used.push_back({ii,jj});
if(pts[ii][jj]){
cnt++;
}
}
}
}
best = min(best,solve(k+1) + cost);
for(auto x : used){
cells[x.F][x.S] = false;
if(pts[x.F][x.S])
cnt--;
}
}
}
return best;
}
long long take_photos(int n, int mm, int k, vector<int> r, vector<int> c) {
int i,j;
maxi = k;
m = mm;
shuld = n;
for(i=0;i<n;i++){
p2(r[i],c[i])
pts[r[i]][c[i]] = 1;
}
return solve(0);
}
int main() {
int n, m, k;
assert(3 == scanf("%d %d %d", &n, &m, &k));
std::vector<int> r(n), c(n);
for (int i = 0; i < n; i++) {
assert(2 == scanf("%d %d", &r[i], &c[i]));
}
long long ans = take_photos(n, m, k, r, c);
printf("%lld\n", ans);
return 0;
}