Submission #1160569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160569		borisAngelov	Aliens (IOI16_aliens)	C++17	25 / 100	1 ms	580 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const long long inf = (1LL << 62);
const long long MAXLAMBDA = 1e12 + 5;

int n, m, k;
pair<int, int> points[maxn];
vector<pair<int, int>> v, v2;
pair<long long, int> dp[maxn];
long long rem[maxn];

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

struct Line
{
    long long a, b;
    int dpSecond;

    long long calc(long long x)
    {
        return a * x + b;
    }
};

double intersect(Line l1, Line l2)
{
    return (1.0 * (l2.b - l1.b)) / (1.0 * (l1.a - l2.a));
}

struct ConvexHullTrickMin
{
    vector<pair<Line, double>> envelope;

    void reset()
    {
        envelope.clear();
    }

    bool toRemove(Line prv2, Line prv1, Line& newLine)
    {
        double p1 = intersect(prv2, prv1);
        double p2 = intersect(prv2, newLine);

        if (p2 > p1) return false;
        //newLine.dpSecond = min(newLine.dpSecond, prv1.dpSecond);
        if (p2 < p1) return true;
        return true;
    }

    void addLine(Line newLine)
    {
        int curr = newLine.dpSecond;

        while (envelope.size() >= 2 && toRemove(envelope[envelope.size() - 2].first, envelope.back().first, newLine) == true)
        {
            envelope.pop_back();
        }

        if (envelope.size() >= 1) envelope.push_back({newLine, intersect(newLine, envelope.back().first)});
        else envelope.push_back({newLine, -inf});
    }

    Line query(double x)
    {
        int l = 0;
        int r = envelope.size() - 1;

        while (l <= r)
        {
            int mid = (l + r) / 2;

            if (x == envelope[mid].second)
            {
                if (mid == 0) return envelope[mid].first;
                if (envelope[mid].first.dpSecond > envelope[mid - 1].first.dpSecond) return envelope[mid - 1].first;
                else return envelope[mid].first;
            }

            if (envelope[mid].second > x)
            {
                r = mid - 1;
            }
            else
            {
                l = mid + 1;
            }
        }

        return envelope[r].first;
    }
};

ConvexHullTrickMin cht;

pair<long long, int> check(long long lambda)
{
    cht.reset();

    dp[0] = {0, 0};

    for (int i = 1; i <= n; ++i)
    {
        dp[i] = {inf, 0};
    }

    for (int i = 1; i <= n; ++i)
    {
        cht.addLine({-2 * points[i].first + 2, dp[i - 1].first - rem[i] - 2 * points[i].first + points[i].first * points[i].first + 1, dp[i - 1].second});
        Line bestLine = cht.query(points[i].second);
        dp[i] = {bestLine.calc(points[i].second) + points[i].second * points[i].second + lambda, 1 + bestLine.dpSecond};
    }

    return dp[n];
}

long long take_photos(int N, int M, int K, std::vector<int> rr, std::vector<int> c)
{
    m = M;
    k = K;

    for (int i = 1; i <= N; ++i)
    {
        int x = rr[i - 1] + 1;
        int y = c[i - 1] + 1;

        if (x > y)
        {
            swap(x, y);
        }

        v.push_back({x, y});
    }

    sort(v.begin(), v.end());
    n = 0;

    for (int i = 0; i < N; ++i)
    {
        if (i == N - 1 || v[i].first != v[i + 1].first)
        {
            v2.push_back(v[i]);
        }
    }

    int maxEnd = 0;

    for (int i = 0; i < v2.size(); ++i)
    {
        if (v2[i].second <= maxEnd) continue;
        points[++n] = v2[i];
        maxEnd = points[n].second;
    }

    for (int i = 2; i <= n; ++i)
    {
        if (points[i - 1].second >= points[i].first) rem[i] = sq(points[i - 1].second - points[i].first + 1);
    }

    long long l = 0;
    long long r = MAXLAMBDA;

    while (l <= r)
    {
        long long mid = (l + r) / 2;

        pair<long long, int> res = check(mid);
        //cout << l << " " << r << " " << mid << " :: " << res.first << " " << res.second << endl;

        if (res.second > k)
        {
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }

    pair<long long, int> res = check(l);
    return res.first - (1LL * k) * l;
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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