Submission #239469

#	Time	Username	Problem	Language	Result	Execution time	Memory
239469		nicolaalexandra	Aliens (IOI16_aliens)	C++14	100 / 100	194 ms	8316 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
#define DIMN 100010
#define DIMM 1000010
#define INF 2000000000000000000LL
using namespace std;

int n,k,m,i,j,x,y;
vector <int> r,c;

long long dp[DIMN],cnt[DIMN];
pair <int, int> v[DIMN];
int d[DIMM];

struct dreapta{
    long long a,b,cnt;
};
dreapta w[DIMM];


long long f (long long a, long long b, int x){
    if (a == INF && b == INF)
        return INF;
    return a*x + b;
}

bool intersectie (pair<long long,long long> c, pair<long long,long long> b, pair<long long,long long> a){
    return (a.second-c.second)*(b.first-a.first) < (a.second-b.second)*(c.first-a.first);
}

long long patrat (long long x){
    return x*x;
}
long long modul (long long x){
    return max (x,-x);
}
inline int cmp (pair<int,int> a, pair<int,int> b){
    if (a.first == b.first)
        return a.second > b.second;
    return a.first < b.first;
}

void solve (long long lambda){

    /// dp[i] - costul mimim daca am primele i puncte
    /// cnt[i] - de cate subsecvente am nevoie

    int p = 1, u = 0;

    for (int i=1;i<=n;++i){
        w[i-1].a = -2*v[i].first, w[i-1].b = dp[i-1] + patrat(v[i].first) - patrat(max(0,v[i-1].second - v[i].first + 1));
       // add (,, cnt[i-1]);

        while (u > 1 && intersectie (make_pair(w[i-1].a,w[i-1].b), make_pair(w[d[u]].a,w[d[u]].b), make_pair(w[d[u-1]].a,w[d[u-1]].b) ) )
            u--;
        d[++u] = i-1;

        while (p < u && f(w[d[p]].a,w[d[p]].b,v[i].second+1) > f(w[d[p+1]].a,w[d[p+1]].b,v[i].second+1))
            p++;


        dp[i] = f(w[d[p]].a,w[d[p]].b,v[i].second+1) + patrat (v[i].second+1) + lambda;
        cnt[i] = cnt[d[p]] + 1;
    }

}

long long take_photos (int N, int M, int K, std::vector <int> r, std::vector <int> c){
    n = N, m = M, k = K;
    for (i=0;i<n;++i)
        v[i+1] = make_pair(min(r[i],c[i])+1,max(r[i],c[i])+1);

    sort (v+1,v+n+1,cmp);

    /// elimin intervalele care sunt incluse in altele
    int St = -1, Dr = -1, el = 0;
    for (i=1;i<=n;++i){
        if (!(v[i].first >= St && v[i].second <= Dr)){
            v[++el] = v[i];
            St = v[i].first, Dr = v[i].second;
        }}

    n = el;

    k = min (k,n);

    long long st = 0, dr = INF;
    while (st <= dr){
        long long lambda = (st + dr)>>1;
        solve (lambda);
        if (cnt[n] > k)
            st = lambda + 1;
        else dr = lambda - 1;
    }

    solve (st);
    return dp[n] - k * st;

}

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