| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1032483 | nishkarsh | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vt vector
#define pb push_back
const int INF = 2e9;
const ll INFLL = 4e18;
const int N = 1e5+1;
const int mod = 998244353;
struct point{
int x,y;
point() {}
point(int _x, int _y) : x(_x), y(_y) {}
int64_t square_size(){
int64_t ans = y+1-x;
return ans*ans;
}
};
int64_t intersection(const point a, const point b){
int nwx = min(a.x,b.x);
int nwy = max(a.y,b.y);
return point(nwx,nwy).square_size();
}
bool cmp(point a, point b){
if(a.x == b.x) return a.y > b.y;
else return a.x < b.x;
}
void dnc(vector<vector<int64_t>> &dp, int k, vector<point> &p, int lt_l, int lt_r, int rt_l, int rt_r){
if(rt_r < rt_l) return;
int rt_mid = (rt_l + rt_r) / 2;
int lt_mid = lt_l;
for(int i = lt_l; i <= lt_r; i++){
int64_t curr;
if(i) curr = dp[i-1][k-1] + intersection(p[rt_mid], p[i]);
else curr = intersection(p[rt_mid],p[i]);
if(curr <= dp[rt_mid][k]){
dp[rt_mid][k] = curr;
lt_mid = i;
}
}
dnc(dp, k, p, lt_l, lt_mid, rt_l, rt_mid - 1);
dnc(dp, k, p, lt_mid, lt_r, rt_mid + 1, rt_r);
}
int64_t take_photos(int n, int m, int k, int r[], int c[]){
point temp[n];
for(int i = 0; i < n; i++){
if(r[i] <= c[i]) temp[i] = point(r[i],c[i]);
else temp[i] = point(c[i],r[i]);
}
sort(temp,temp+n,cmp);
vector<point> p;
int threshold = -1;
for(int i = 0; i < n; i++){
if(temp[i].y > threshold){
// cout << temp[i].x << " " << temp[i].y << "\n";
p.pb(temp[i]);
threshold = temp[i].y;
}
}
n = p.size();
vector<vector<int64_t>> dp(n, vector<int64_t>(k,int64_t(INFLL)));
for(int i = 0; i < n; i++) dp[i][0] = intersection(p[i],p[0]);
for(int j = 1; j < k; j++) dnc(dp, j, p, 0, n-1, 0, n-1);
// for(int i = 0; i < k; i++){
// for(int j = 0; j < n; j++){
// cout << dp[j][i] << " ";
// }
// cout << "\n";
// }
return dp[n-1][k-1];
}
void solve(){
int n,m,k;
cin >> n >> m >> k;
int r[n],c[n];
for(int i = 0; i < n; i++) cin >> r[i];
for(int i = 0; i < n; i++) cin >> c[i];
cout << take_photos(n,m,k,r,c) << "\n";
}
// int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
// int t = 1;
// // cin >> t;
// while(t--) solve();
// }