Submission #792011

#	Time	Username	Problem	Language	Result	Execution time	Memory
792011		I_Love_EliskaM_	Aliens (IOI16_aliens)	C++14	25 / 100	1445 ms	1048580 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second
using ll = long long;
#define int ll 
const int inf=1e18;

int sq(int x) {
    return x*x;
}

struct line {
    int a,b;
    int f(int x) {
        return a*x+b;
    }
    line() {
        a=0, b=inf;
    }
    line(int x, int y) {
        a=x, b=y;
    }
};
const int sz=1<<20;
struct sgt {
    sgt *L, *R;
    line ln;
    sgt() {
        L=R=NULL; ln=line();
    }
    sgt(line n) {
        L=R=NULL; ln=n;
    }
    void add(int l, int r, line n) {
        if (n.f(l)<=ln.f(l) && n.f(r)<=ln.f(r)) {
            ln=n; return;
        }
        if (n.f(l)>=ln.f(l) && n.f(r)>=ln.f(r)) {
            return;
        }
        if (r-l==1) return;
        int m=(l+r)>>1;
        if (!L) L=new sgt(ln);
        if (!R) R=new sgt(ln);
        L->add(l,m,n);
        R->add(m,r,n);
    }
    void add(line n) {
        add(0,sz,n);
    }
    int query(int l, int r, int x) {
        if (r<=x || l>x) return inf;
        int m=(l+r)>>1;
        int f=ln.f(x);
        int s=L?L->query(l,m,x):inf;
        int t=R?R->query(m,r,x):inf;
        return min({f,s,t});
    }
    int query(int x) {
        return query(0,sz,x);
    }
};

int take_photos(int32_t n, int32_t m, int32_t k, vector<int32_t> r, vector<int32_t> c) {


    vector<int> a(m,0);
    forn(i,n) {
        int x=r[i], y=c[i];
        if (x<y) {
            a[x]=max(a[x],y-x+1);
        } else {
            a[y]=max(a[y],x-y+1);
        }
    }
    int x=-inf;
    forn(i,m) {
        if (!a[i]) continue;
        if (a[i]+i<=x) a[i]=0;
        else x=a[i]+i;
    }
    int z=0;
    forn(i,m) z+=!!a[i];
    if (z<=k) {
        int ans=0;
        int last=-1;
        forn(i,m) {
            if (!a[i]) continue;
            if (last==-1) {
                ans+=a[i]*a[i];
                last=i;
                continue;
            }
            if (last + a[last] >= i) {
                ans += sq(a[i]) - sq(last+a[last]-i);
                last=i;
            } else {
                ans+=a[i]*a[i];
                last=i;
            }
        }
        return ans;
    }

    if (n*k > 1e7) return -1;
    vector<sgt> st(k+1);
    vector<pi> v;
    forn(i,m) if (a[i]) v.pb({i,i+a[i]});
    n=v.size();
    st[1].add({-2*v[0].f,sq(v[0].f)});

    vector<int> dp(k+1,inf);
    dp[1]=sq(v[0].s - v[0].f);

    for (int i=1; i<n; ++i) {
        for (int j=min(1ll*k,i+1); j>0; --j) {
            int f=st[j].query(v[i].s) + sq(v[i].s);
            int s=dp[j-1] + sq(v[i].s-v[i].f);
            if (v[i-1].s > v[i].f) s-=sq(v[i-1].s-v[i].f);
            dp[j]=min(f,s);
            st[j].add({-2*v[i].f,sq(v[i].f)+s-sq(v[i].s-v[i].f)});
        }
    }
    return dp[k];
    
}
#undef int

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