Submission #330573

#	Time	Username	Problem	Language	Result	Execution time	Memory
330573		IgorI	Aliens (IOI16_aliens)	C++17	4 / 100	6 ms	384 KiB

aliens

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

using namespace std;

long long take_photos(int n, int m, int k, vector<int> l, vector<int> r)
{
    vector<int> cv(m);
    for (int i = 0; i < m; i++)
    {
        cv[i] = i + 1;
    }
    for (int i = 0; i < n; i++)
    {
        int x = min(l[i], r[i]);
        int y = max(l[i], r[i]);
        cv[y] = min(cv[y], x);
    }
    l.clear();
    r.clear();
    for (int i = 0; i < m; i++)
    {
        if (cv[i] <= i)
        {
            while (l.size() && l.back() >= cv[i])
                l.pop_back(), r.pop_back();
            l.push_back(cv[i]), r.push_back(i);
        }
    }
    n = l.size();
    //for (int i = 0; i < l.size(); i++)
    //    cout << l[i] << " " << r[i] << endl;
    const long long INFLL = 1e18;
    long long L = -1, R = m * m + 222;
    long long ans = INFLL;
    while (L + 1 < R)
    {
        long long M = (L + R) / 2;
        vector<long long> dp(n, INFLL);
        vector<long long> bl(n, INFLL);
        for (int i = 0; i < n; i++)
            dp[i] = M + (r[i] - l[0] + 1) * (r[i] - l[0] + 1), bl[i] = 1;
        struct line{
            long long k, b, id;
        };
        vector<line> convex;
        for (int i = 0; i < n; i++)
        {
            long long res = 1ll * r[i] * r[i];
            long long d = INFLL, used = 0;
            for (auto e : convex)
            {
                if (e.b + e.k * r[i] < d)
                    d = e.b + e.k * r[i], used = INFLL;
                if (e.b + e.k * r[i] == d && bl[e.id] < used)
                    used = bl[e.id];
            }
            res += d;
            if (res < dp[i])
                dp[i] = res, bl[i] = used + 1;
            if (i + 1 < n)
            {
                long long b = dp[i] + 1ll * l[i + 1] * l[i + 1] + 1 - 2 * l[i + 1] + M - 1ll * max(0, r[i] - l[i + 1] + 1) * max(0, r[i] - l[i + 1] + 1);
                long long k = 2 * (1 - l[i + 1]);
                convex.push_back({k, b, i});
            }
        }
        //cout << M << " " << dp[0] << " " << dp[1] << " " << dp[n - 1] << " " << bl[n - 1] << endl;
        if (bl[n - 1] <= k)
            ans = min(ans, dp[n - 1] - bl[n - 1] * M);
        if (bl[n - 1] >= k)
            L = M;
        else
            R = M;
    }
    L = -1, R = m * m + 222;
    while (L + 1 < R)
    {
        long long M = (L + R) / 2;
        vector<long long> dp(n, INFLL);
        vector<long long> bl(n, INFLL);
        for (int i = 0; i < n; i++)
            dp[i] = M + (r[i] - l[0] + 1) * (r[i] - l[0] + 1), bl[i] = 1;
        struct line{
            long long k, b, id;
        };
        vector<line> convex;
        for (int i = 0; i < n; i++)
        {
            long long res = 1ll * r[i] * r[i];
            long long d = INFLL, used = 0;
            for (auto e : convex)
            {
                if (e.b + e.k * r[i] < d)
                    d = e.b + e.k * r[i], used = INFLL;
                if (e.b + e.k * r[i] == d && bl[e.id] < used)
                    used = bl[e.id];
            }
            res += d;
            if (res < dp[i])
                dp[i] = res, bl[i] = used + 1;
            if (i + 1 < n)
            {
                long long b = dp[i] + 1ll * l[i + 1] * l[i + 1] + 1 - 2 * l[i + 1] + M - 1ll * max(0, r[i] - l[i + 1] + 1) * max(0, r[i] - l[i + 1] + 1);
                long long k = 2 * (1 - l[i + 1]);
                convex.push_back({k, b, i});
            }
        }
        //cout << M << " " << dp[n - 1] << " " << bl[n - 1] << endl;
        if (bl[n - 1] <= k)
            ans = min(ans, dp[n - 1] - bl[n - 1] * M);
        if (bl[n - 1] > k)
            L = M;
        else
            R = M;
    }
    return ans;
}

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