Submission #467502

#	Time	Username	Problem	Language	Result	Execution time	Memory
467502		alextodoran	Aliens (IOI16_aliens)	C++17	100 / 100	665 ms	9412 KiB

aliens

#include <bits/stdc++.h>

#define double long double

#include "aliens.h"

using namespace std;

const int N_MAX = 100002;

const double E = 0.000001;

typedef long long ll;

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

int n, m, k;

struct Point
{
    int x, y;
};

bool operator < (const Point &a, const Point &b)
{
    return make_pair(a.y, -a.x) > make_pair(b.y, -b.x);
}

Point v[N_MAX];

ll X[N_MAX], Y[N_MAX];

struct Line
{
    double a, b;
    int index;
    double eval (double x)
    {
        return a * x + b;
    }
};

bool ftest (const Line &l1, const Line &l2, const Line &l3)
{
    return (l2.b - l1.b) * (l2.a - l3.a) < (l3.b - l2.b) * (l1.a - l2.a);
}

deque <Line> dq;

void update (Line l)
{
    while(dq.size() >= 2 && ftest(dq.end()[-2], dq.end()[-1], l) == false)
        dq.pop_back();
    dq.push_back(l);
}

void query (double x, double &answer, int &index)
{
    while(dq.size() >= 2 && dq[0].eval(x) >= dq[1].eval(x))
        dq.pop_front();
    answer = dq.front().eval(x);
    index = dq.front().index;
}

double dp[N_MAX];
int steps[N_MAX];

void push (int i)
{
    double a = -2 * X[i + 1];
    double b = dp[i] + sq(X[i + 1]) - 2 * X[i + 1] - sq(max(0LL, Y[i] - X[i + 1] + 1));
    update(Line{a, b, i});
}

void compute (double C)
{
    while(!dq.empty())
        dq.pop_back();
    Y[0] = X[1] - 1;
    push(0);
    for(int i = 1; i <= n; i++)
    {
        double q;
        int index;
        query(Y[i], q, index);
        dp[i] = sq(Y[i]) + 2 * Y[i] + 1 + C + q;
        steps[i] = steps[index] + 1;
        if(i == n)
            break;
        push(i);
    }
}

ll take_photos(int _n, int _m, int _k, vector <int> _r, vector <int> _c)
{
    n = _n;
    m = _m;
    k = _k;
    for(int i = 1; i <= n; i++)
    {
        v[i].x = _r[i - 1];
        v[i].y = _c[i - 1];
        if(v[i].x > v[i].y)
            swap(v[i].x, v[i].y);
    }
    sort(v + 1, v + n + 1);
    int posy = 1;
    Y[1] = v[1].y;
    X[1] = v[1].x;
    for(int i = 1; i <= n; i++)
        if(i > 1 && v[i].y < v[i - 1].y && v[i].x < X[posy])
        {
            posy++;
            Y[posy] = v[i].y;
            X[posy] = v[i].x;
        }
    n = posy;
    reverse(X + 1, X + n + 1);
    reverse(Y + 1, Y + n + 1);
    double l = 0, r = 1000000000000;
    int cnt = 64;
    while(cnt--)
    {
        double mid = (l + r) / 2;
        compute(mid);
        if(steps[n] > k)
            l = mid + E;
        else
            r = mid;
    }
    compute(l);
    return (ll) round(dp[n] - l * 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