Submission #226068

#	Time	Username	Problem	Language	Result	Execution time	Memory
226068		VEGAnn	Aliens (IOI16_aliens)	C++14	60 / 100	2092 ms	356712 KiB

aliens

# include "aliens.h"
#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define L first
#define R second
#define M make_pair
#define sz(x) (int)x.size()
using namespace std;
typedef long long ll;
typedef std::vector<int> V;
vector<pll> seg,Seg;
ll oo=1e18,cur;
vector<vector<ll> > f;

ll sqr(ll x) { if (x>=0ll) return x*x; else return 0ll; }

bool cmp(pll x,pll y){
    if (x.L==y.L)
        return x.R>y.R;
    else return x.L<y.L;
}

void Calc(int j,int li,int ri,int l,int r){
    if (li>ri) return;
    int i=(li+ri)>>1,opt;
    for (int I=l;I<=r;I++)
        if (f[I][j-1]!=oo){
            cur=f[I][j-1]+sqr(Seg[i].R-Seg[I+1].L+1ll)-sqr(Seg[I].R-Seg[I+1].L+1ll);
            if (f[i][j]>cur){
                f[i][j]=cur; opt=I;
            }
        }
    Calc(j,li,i-1,l,opt);
    Calc(j,i+1,ri,opt,r);
}

long long take_photos (int n, int m, int k, V r, V c) {
    m+=m; seg.clear(); Seg.clear();
    for (int i=0;i<n;i++) seg.push_back(M(min(r[i],c[i]),max(r[i],c[i])));
    seg.push_back(M(-1,-1));
    sort(seg.begin(),seg.end(),cmp);
    Seg.push_back(seg[0]);
    for (int i=1;i<sz(seg);i++)
        if (Seg.back().R<seg[i].R)
            Seg.push_back(seg[i]);
    n=sz(Seg)-1; f.clear(); f.resize(n+1);
    for (int i=0;i<=n;i++){
        f[i].resize(k+1);
        for (int j=0;j<=k;j++) f[i][j]=oo;
    }
    for (int j=0;j<=k;j++) f[0][j]=0ll;
    for (int j=1;j<=k;j++) Calc(j,1,n,0,n-1);
    return f[n][k];
}

Compilation message (stderr)

aliens.cpp: In function 'void Calc(int, int, int, int, int)':
aliens.cpp:33:9: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
     Calc(j,li,i-1,l,opt);
     ~~~~^~~~~~~~~~~~~~~~

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