Submission #241506

#	Time	Username	Problem	Language	Result	Execution time	Memory
241506		Hehehe	Aliens (IOI16_aliens)	C++14	100 / 100	357 ms	7364 KiB

aliens

#include<bits/stdc++.h>
#include "aliens.h"
using namespace std;
typedef long long ll;
#define pi pair <int, int>
#define sz(x) (int)((x).size())

const int N = 100010 + 11;
const ll INF64 = 2e18;

struct interval{
    long long l,r;
};

interval a[N];
long long dp[N], cnt[N], n, m, k;

struct line{
    long long a,b, cnt;
    long long val(int x){
        return a*x + b;
    }
};

double cross(line a, line b){
    return (a.b - b.b)/(b.a - a.a);
}

bool cmp(interval x, interval y){
    if(x.l != y.l)return (x.l < y.l);
    return (x.r > y.r);
}

long long P(long long x){
    return x * x;
}

void solve(long long lambda){

    deque<line>dq;

    for(int i = 1; i <= n; i++){

        line cur = {-2*a[i].l, P(a[i].l) + dp[i - 1] - P(max(0ll, a[i - 1].r - a[i].l + 1ll)), cnt[i - 1] + 1ll};

        while(sz(dq) >= 2 && cross(cur,dq[sz(dq) - 1]) < cross(dq[sz(dq) - 1],dq[sz(dq) - 2]))dq.pop_back();

        dq.push_back(cur);

        while(sz(dq) >= 2 && cross(dq[0],dq[1]) < (a[i].r + 1))dq.pop_front();

        cnt[i] = dq.front().cnt;

        dp[i] = dq.front().val(a[i].r + 1) + P(a[i].r + 1) + lambda;

    }

}

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(int i = 0; i < n; i++){
        a[i + 1].l = min(r[i], c[i]);
        a[i + 1].r = max(r[i], c[i]);
    }

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

    a[0].l = a[0].r = -1;

    long long L = -1, R = -1, cur = 0;
    for(int i = 1; i <= n; i++){
        if(!(L <= a[i].l && a[i].r <= R)){
            a[++cur] = a[i];
            L = a[i].l;
            R = a[i].r;
        }
    }

    n = cur;

    k = min(k, n);

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

    solve(st);

    return dp[n] - st*k;
}

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