Submission #492125

#	Time	Username	Problem	Language	Result	Execution time	Memory
492125		Lam_lai_cuoc_doi	Aliens (IOI16_aliens)	C++17	25 / 100	74 ms	9292 KiB

aliens

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;

constexpr int N = 1e5 + 5;
constexpr ll Inf = 1e17;
int m, n, k;
pair<int, int> a[N];
ll cnt[N], sum[N], dp[502][502];

long long take_photos(int N, int M, int K, vector<int> r, vector<int> c)
{
    /* Convert */
    m = M;
    n = N;
    k = K;
    for (int i = 1; i <= n; ++i)
    {
        a[i] = make_pair(r[i - 1] + 1, c[i - 1] + 1);
        if (a[i].first > a[i].second)
            swap(a[i].first, a[i].second);
    }

    sort(a + 1, a + n + 1, [&](const pair<int, int> &x, const pair<int, int> &y)
         { return x.second < y.second || (x.second == y.second && x.first > y.first); });

    vector<int> s;

    for (int i = 1; i <= n; ++i)
    {
        while (!s.empty() && a[i].first <= a[s.back()].first)
            s.pop_back();
        s.emplace_back(i);
    }

    n = s.size();

    for (int i = 1; i <= n; ++i)
    {
        a[i] = a[s[i - 1]];
    }

    /* End Convert */

    long long temp(0);

    for (int i = 1, j = 1, now = 0; i <= m; ++i)
    {
        if (j <= n && a[j].first == i)
        {
            now = a[j].second;
            ++j;
        }

        if (now >= i)
            temp += 2 * (now - i + 1) - 1;
    }

    for (int i = 1; i <= n; ++i)
    {
        if (i == n)
        {
            cnt[i] = (a[i].second - a[i].first + 1) * 2;
            sum[i] = -cnt[i] * a[i].second;
        }
        else if (a[i].second < a[i + 1].first)
        {
            cnt[i] = (a[i].second - a[i].first + 1) * 2;
            sum[i] = -cnt[i] * a[i].second;

            sum[i] += -(a[i + 1].first - a[i].second - 1) * (a[i + 1].first + a[i].second) + (a[i + 1].first - a[i].second - 1);
            cnt[i] += 2 * (a[i + 1].first - a[i].second - 1);
        }
        else
        {
            cnt[i] = (a[i + 1].first - a[i].first) * 2;
            sum[i] = -cnt[i] * a[i].second;
        }

        cnt[i] += cnt[i - 1];
        sum[i] += sum[i - 1];
    }
    fill_n(&dp[0][0], 502 * 502, Inf);

    for (int i = 0; i <= k; ++i)
        dp[0][i] = 0;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i && j <= k; ++j)
        {
            dp[i][j] = dp[i][j - 1];
            for (int t = 1; t <= i; ++t)
                dp[i][j] = min(dp[i][j], dp[t - 1][j - 1] + (cnt[i - 1] - cnt[t - 1]) * a[i].second + (sum[i - 1] - sum[t - 1]));
        }
    return dp[n][min(n, k)] + temp;
}

void Read()
{
    int m, n, k;
    cin >> n >> m >> k;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; ++i)
        cin >> x[i] >> y[i];

    cout << take_photos(n, m, k, x, y);
}

void Solve()
{
}

Compilation message (stderr)

aliens.cpp: In function 'void read(T&)':
aliens.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^

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