| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 199041 | Ruxandra985 | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "aliens.h"
#define DIMN 100010
using namespace std;
pair <long long,long long> v[DIMN];
long long dp[DIMN];
long long cnt[DIMN];
int cmp (pair <long long,long long> x , pair <long long,long long> y){
if (x.first != y.first)
return x.first < y.first;
return x.second > y.second;
}
pair <long long,long long> solve (long long x , long long n){ /// cost x , n intervale
long long i , j;
/// nu cred ca bag cu cht azi ca mi e somn
for (i = 1 ; i <= n ; i++){
cnt[i] = 1;
dp[i] = (v[i].second - v[1].first + 1) * (v[i].second - v[1].first + 1) - x;
for (j = 1 ; j <= i ; j ++){
if (-x + dp[j - 1] + (v[i].second - v[j].first + 1) * (v[i].second - v[j].first + 1) + max (0LL , (v[j-1].second - v[j].first + 1)) * max (0LL , (v[j-1].second - v[j].first + 1)) <= dp[i]){
dp[i] = -x + dp[j - 1] + (v[i].second - v[j].first + 1) * (v[i].second - v[j].first + 1) + max (0LL , (v[j-1].second - v[j].first + 1)) * max (0LL , (v[j-1].second - v[j].first + 1));
cnt[i] = 1 + cnt[j - 1];
}
}
}
return make_pair(cnt[n] , dp[n]);
}
long long take_photos (long long n , long long m , long long k , vector <long long> r , vector <long long> c){
long long st , dr , mid;
long long i , n2 , rm;
pair <long long,long long> rez;
for (i=0;i<n;i++){
v[i+1] = make_pair(r[i] + 1 , c[i] + 1);
if (v[i+1].first > v[i+1].second)
swap (v[i+1].first , v[i+1].second);
}
sort (v + 1 , v + n + 1 , cmp);
n2 = 0;
rm = 0;
for (i=1;i<=n;i++){ /// nu iau intervale incluse total unul in altul
if (rm < v[i].second)
v[++n2] = v[i];
rm = max(rm , v[i].second);
}
n = n2;
st = 0;
dr = 1000000000000000000;
while (st <= dr){
mid = (st + dr)/2;
rez = solve(mid , n2);
if (rez.first <= k)
st = mid + 1;
else dr = mid - 1;
}
rez = solve(dr , n2);
return rez.second + dr * rez.first;
}