Submission #80365

#	Time	Username	Problem	Language	Result	Execution time	Memory
80365		Bodo171	Aliens (IOI16_aliens)	C++14	0 / 100	2 ms	644 KiB

aliens

#include "aliens.h"
#include <iostream>
#include <algorithm>
#include <utility>
const int nmax=100005;
using namespace std;
struct in
{
    int l,r;
}v[nmax];
bool operator <(in unu,in doi)
{
    if(unu.l==doi.l) return unu.r>doi.r;
    return unu.l<doi.l;
}
struct funct
{
    long double a,b;
    int cate;
    void it(long double A,long double B,int c)
    {
        this->a=A;
        this->b=B;
        this->cate=c;
    }
    long double eval(long double x)
    {
        return a*x+b;
    }
}f,st[nmax];
int p,u,i,N;
long double L,R;
pair<long double,int> dp[nmax];
long double a1,a2,b1,b2;
long double in(funct unu,funct doi)
{
    a1=unu.a;a2=doi.a;b1=unu.b;b2=doi.b;
    return (b2-b1)/(a1-a2);
}
void ins()
{
    while(u>2&&in(f,st[u-1])<in(st[u-1],st[u]))
        u--;
    st[++u]=f;
}
void gt(long double x)
{
   while(p<u&&in(st[p],st[p+1])<x)
       p++;
   dp[i]={st[p].eval(x),st[p].cate};
   dp[i].first+=1LL*x*x;
}
int get(long double C)
{
    p=1,u=0;
    int pp=0;
    long double len;
    for(i=1;i<=N;i++)
    {
        L=v[i].l-1;R=v[i].r;
        while(v[pp].r<v[i].l)
            pp++;
        pp--;
        if(pp)len=v[pp].r-v[i].l+1;
        else len=0;
        if(len<0) len=0;
        f.it(-2*L,L*L+dp[pp].first+C-len*len,dp[pp].second+1);
        ins();
        gt(R);
    }
    return dp[N].second;
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    for(i=0;i<n;i++)
    {
        r[i]++,c[i]++;
        v[i+1].l=min(r[i],c[i]);
        v[i+1].r=max(r[i],c[i]);
    }
    sort(v+1,v+n+1);
    int mx=0,nr=0;
    for(i=1;i<=n;i++)
    {
        if(mx<v[i].r)
        {
            v[++nr]=v[i];
        }
        mx=max(mx,v[i].r);
    }
    N=n=nr;
    if(N<=k)
    {
        int ct=get(0);
        return dp[N].first;
    }
    long double ll,rr,mid,kk=k;
    ll=0;rr=1LL*1e16;
    for(int cnt=1;cnt<=100;cnt++)
    {
        mid=(ll+rr)/2;
        if(get(mid)<=k) rr=mid;
        else ll=mid;
    }
    int ct=get(ll);
    long long ans=(long long)(dp[N].first-kk*ll+0.5);
    return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:93:13: warning: unused variable 'ct' [-Wunused-variable]
         int ct=get(0);
             ^~
aliens.cpp:104:9: warning: unused variable 'ct' [-Wunused-variable]
     int ct=get(ll);
         ^~

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