Submission #290261

#	Time	Username	Problem	Language	Result	Execution time	Memory
290261		Kastanda	Aliens (IOI16_aliens)	C++11	100 / 100	1367 ms	13892 KiB

aliens

// M
#include<bits/stdc++.h>
#include "aliens.h"
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double ld;
struct CHT
{
        typedef pair < ld , ld > Line;
        deque < pair < ld , pair < Line , int > > > A;
        ld INF = 1e18;
        inline void Add(Line X, int i)
        {
                while (A.size() && Intersection(A.back().second.first, X) <= A.back().first)
                        A.pop_back();
                if (A.size())
                        A.push_back({Intersection(A.back().second.first, X), {X, i}});
                else
                        A.push_back({-INF, {X, i}});
        }
        inline int GetMax(ld X)
        {
                while (A.size() > 1 && A[1].first <= X)
                        A.pop_front();
                return A[0].second.second;
        }
        inline ld Intersection(Line X, Line Y)
        {
                if (X.first == Y.first)
                        return X.second <= Y.second ? -INF : INF;
                return (X.second - Y.second) / (Y.first - X.first);
        }
};
const int N = 100005;
int n, m, k, Cnt[N];
ll CutOff[N];
ld dp[N];
pair < int , int > A[N];
inline int Solve(ld md)
{
        CHT C;
        auto Add = [&](int i){
                C.Add(make_pair(2LL * (A[i + 1].y - 1), - dp[i] + CutOff[i] - (ll)(A[i + 1].y - 1) * (A[i + 1].y - 1)), i);
        };

        auto GetValue = [&](int i, int j){
                return (dp[j] - CutOff[j] + (ll)(A[i].x - A[j + 1].y + 1) * (A[i].x - A[j + 1].y + 1));
        };

        Add(0);
        for (int i = 1; i <= n; i ++)
        {
                int j = C.GetMax(A[i].x);
                Cnt[i] = Cnt[j] + 1;
                dp[i] = GetValue(i, j) + md;
                Add(i);
                /*dp[i] = 1e18; Cnt[i] = 0;
                for (int j = 0; j < i; j ++)
                        if (dp[i] >= GetValue(i, j) + md)
                                dp[i] = GetValue(i, j) + md, Cnt[i] = Cnt[j] + 1;*/
        }
        return Cnt[n];
}

long long take_photos(int _n, int _m, int _k, vector < int > _R, vector < int > _C)
{
        n = _n; m = _m; k = _k;
        for (int i = 0; i < n; i ++)
                A[i] = {_C[i], _R[i]};

        for (int i = 0; i < n; i ++)
                if (A[i].x < A[i].y)
                        swap(A[i].x, A[i].y);
        vector < int > MN(m, m);
        for (int i = 0; i < n; i ++)
                MN[A[i].x] = min(MN[A[i].x], A[i].y);
        n = 0;
        for (int i = m - 1; i >= 0; i --)
                if (MN[i] != m)
                        if (!n || A[n].y > MN[i])
                                A[++ n] = make_pair(i, MN[i]);
        reverse(A + 1, A + n + 1);
        k = min(k, n);

        for (int i = 1; i < n; i ++)
                if (A[i].x >= A[i + 1].y)
                        CutOff[i] = (ll)(A[i].x - A[i + 1].y + 1) * (A[i].x - A[i + 1].y + 1);

        // Phew ..
        ld le = 0, ri = 1e13, md;
        for (int __ = 0; __ <= 170; __ ++)
        {
                md = (le + ri) * 0.5;
                if (Solve(md) >= k)
                        le = md;
                else
                        ri = md;
        }
        Solve(le);
        return (ll)(dp[n] - k * le + 0.5);
}

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