Submission #80446

#	Time	Username	Problem	Language	Result	Execution time	Memory
80446		Bodo171	Aliens (IOI16_aliens)	C++14	100 / 100	309 ms	37340 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];
typedef long long ld;
bool operator <(in unu,in doi)
{
    if(unu.l==doi.l) return unu.r>doi.r;
    return unu.l<doi.l;
}
struct funct
{
    ld a,b;
    int cate;
    void it(ld A,ld B,int c)
    {
        this->a=A;
        this->b=B;
        this->cate=c;
    }
    ld eval(ld x)
    {
        return a*x+b;
    }
}f,st[nmax];
int p,u,i,N;
ld L,R;
pair<ld,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(p<u&&in(f,st[u-1])<in(st[u-1],st[u]))
        u--;
    st[++u]=f;
}
void gt(ld x)
{
   while(p<u&&in(st[p],st[p+1])<(long double)x)
       p++;
   dp[i]={st[p].eval(x),st[p].cate};
   dp[i].first+=1LL*x*x;
}
int get(ld C)
{
    p=1,u=0;
    long double len=0;
    for(i=1;i<=N;i++)
    {
        L=v[i].l-1;R=v[i].r;
        if(i>1)len=v[i-1].r-v[i].l+1;
        else len=0;
        if(len<0) len=0;
        f.it(-2*L,L*L+dp[i-1].first+C-len*len,dp[i-1].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);
        long long ans=dp[N].first;
        return ans;
    }
    ld ll,rr,mid,kk=k;
    ll=(1LL<<40);
    for(int p=39;p>=0;p--)
        if(get(ll-(1LL<<p))<=k)
          ll-=(1LL<<p);
    int ct=get(ll);
    long long ans=(long long)(dp[N].first-kk*ll);
    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:90:13: warning: unused variable 'ct' [-Wunused-variable]
         int ct=get(0);
             ^~
aliens.cpp:94:11: warning: unused variable 'rr' [-Wunused-variable]
     ld ll,rr,mid,kk=k;
           ^~
aliens.cpp:94:14: warning: unused variable 'mid' [-Wunused-variable]
     ld ll,rr,mid,kk=k;
              ^~~
aliens.cpp:99:9: warning: unused variable 'ct' [-Wunused-variable]
     int ct=get(ll);
         ^~

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