Submission #593168

#	Time	Username	Problem	Language	Result	Execution time	Memory
593168		alirezasamimi100	Aliens (IOI16_aliens)	C++17	0 / 100	4 ms	6612 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using pll = pair<ll, ll>;
using ld = long double;
using pld = pair<ld, int>;
using pdd = pair<ld, ld>;
#define pb push_back
#define F first
#define S second
const ld eps = 1e-7;
const int N = 1e5 + 10;

vector<pll> vec;
pld dp[N];
int n;
struct CHT{
    const ld INF=1e18;
    pair<ld, pair<pdd,int>> A[N];
    int L, R;
    CHT(){
        L=R=0;
    }
    inline ld Intersect(pdd a, pdd b){
        if (a.first==b.first) return (a.second>=b.second?-INF:INF);
        return (a.second-b.second)/(b.first-a.first);
    }
    inline void Add(pair<pdd,int> X){
        while (L<R && Intersect(A[R-1].second.first, X.first)<=A[R-1].first) R--;
        if (L==R) A[R++]={-INF, X};
        else A[R]={Intersect(A[R-1].second.first, X.first), X}, R++;
    }
    inline pld GetMin(ld x){
        while (L+1<R && A[L+1].first<=x) L++;
        return {A[L].second.first.first*x + A[L].second.first.second,A[L].second.second};
    }
} cht;
void solve(ld cs){
    cht.L=cht.R=0;
    for(int i=1; i<=n; i++){
        ld x=vec[i-1].S-vec[i].F+1;
        if(x>=0) x*=x;
        else x=0;
        cht.Add({{(ld)-vec[i].F,cs+dp[i-1].F+vec[i].F*vec[i].F-x},dp[i-1].S+1});
        dp[i]=cht.GetMin(2*(vec[i].S+1));
        dp[i].F+=(vec[i].S+1)*(vec[i].S+1);
    }
}
ll take_photos(int n, int m, int k, vector<int> R, vector<int> C) {
    ::n=n;
    vector<pll> tp={{-1,-1}};
    for(int i=0; i<n; i++) tp.pb({R[i],C[i]});
    sort(tp.begin(),tp.end());
    for(auto [x,y] : tp){
        while(!vec.empty() && vec.back().F==x) vec.pop_back();
        if(vec.empty() || vec.back().S<y) vec.pb({x,y});
    }
    n=(int)vec.size()-1;
    ld l=0,r=1e9;
    while(r-l>eps){
        ld m=(l+r)/2;
        solve(m);
        if(dp[n].S<=k) r=m;
        else l=m;
    }
    solve(r);
    return (ll)(dp[n].F-dp[n].S*r);
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40