Submission #80441

#	Time	Username	Problem	Language	Result	Execution time	Memory
80441		Bodo171	Aliens (IOI16_aliens)	C++14	60 / 100	2055 ms	33768 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)
    {
        this->a=A;
        this->b=B;
    }
    ld eval(ld x)
    {
        return a*x+b;
    }
}f,st[nmax];
int p,u,i,N;
ld L,R;
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;
}
int lin,use;
long long dp[2][nmax];
void gt(ld x)
{
   while(p<u&&in(st[p],st[p+1])<(long double)x)
       p++;
   dp[use][i]=1LL*st[p].eval(x)+1LL*x*x;
}
void do_dp(int k)
{
    p=1,u=0;
    long double len=0;
    for(lin=1;lin<=k;lin++)
    {
        p=1,u=0;use=1-use;
        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;
        if(lin>1||i==1) f.it(-2*L,L*L+dp[1-use][i-1]-len*len);
        ins();
        gt(R);
     }
    }
}
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;
    do_dp(k);
    return dp[use][n];
}

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