| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 239207 | nicolaalexandra | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "aliens.h"
#define DIMN 100010
#define DIMM 1000010
using namespace std;
int n,k,i,j;
long long dp[DIMN][2];
pair <int, int> v[DIMN];
struct dreapta{
long long a,b;
} aint[DIMM*4];
long long f (long long a, long long b, int x){
return a*x + b;
}
void add (int nod, int st, int dr, long long a, long long b){
if (st == dr){
if (f(a,b,st) < f(aint[nod].a,aint[nod].b,st))
aint[nod] = {a,b};
return;
}
int mid = (st+dr)>>1;
int ok_mid = 0, ok_dr = 0;
if (f(a,b,mid) <= f(aint[nod].a,aint[nod].b,mid))
ok_mid = 1;
if (f(a,b,dr) <= f(aint[nod].a,aint[nod].b,dr))
ok_dr = 1;
if (!ok_mid && !ok_dr)
add (nod<<1,st,mid,a,b);
else {
if (!ok_mid && ok_dr)
add ((nod<<1)|1,mid+1,dr,a,b);
else {
swap (aint[nod].a,a);
swap (aint[nod].b,b);
if (ok_dr)
add (nod<<1,st,mid,a,b);
else add ((nod<<1)|1,mid+1,dr,a,b);
}}}
long long query (int nod, int st, int dr, int x){
if (st == dr)
return f(aint[nod].a,aint[nod].b,x);
int mid = (st+dr)>>1;
long long sol = 0;
if (x <= mid)
sol = query (nod<<1,st,mid,x);
else sol = query ((nod<<1)|1,mid+1,dr,x);
return max (sol,f(aint[nod].a,aint[nod].b,x));
}
long long patrat (long long x){
return x*x;
}
long long modul (long long x){
return max (x,-x);
}
long long take_photos (int N, int m, int K, std::vector <int> R, std::vector <int> C){
n = N, k = K;
for (i=0;i<n;i++)
v[i+1] = make_pair(min(r[i],c[i])+1,max(r[i],c[i])+1);
sort (v+1,v+n+1);
int el = 1;
for (i=2;i<=n;i++)
if (v[i] != v[i-1])
v[++el] = v[i];
n = el;
/// dp[i][j] - costul minim sa parcurg primele i puncte si sa am j subsecvente
for (i=1;i<=n;i++)
dp[i][1] = patrat (v[i].first - v[1].second + 1);
int t = 0;
for (j=2;j<=k;j++){
for (i=1;i<=4*m+4;i++)
aint[i] = {0,0};
for (i=j;i<=n;i++){
add (1,1,n,-2*v[i].second,dp[i-1][1-t] + patrat(v[i].second));
dp[i][t] = patrat(v[i].first + 1) + query (1,1,n,v[i].first+1);
}
t = 1-t;
}
return dp[n][1-t];
}