Submission #1160515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160515		borisAngelov	Aliens (IOI16_aliens)	C++17	4 / 100	5 ms	328 KiB

aliens

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

using namespace std;

const int maxn = 4005;
const long long inf = (1LL << 62);
const long long MAXLAMBDA = 1e13;

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

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

pair<long long, int> check(long long lambda)
{
    dp[0] = {0, 0};

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

    for (int i = 1; i <= n; ++i)
    {
        for (int j = i; j >= 1; --j)
        {
            long long cost = sq(points[i].second - points[j].first + 1);
            if (j > 1 && points[j - 1].second >= points[j].first) cost -= sq(points[j - 1].second - points[j].first + 1);

            if (dp[i].first > cost + lambda + dp[j - 1].first)
            {
                dp[i].first = cost + lambda + dp[j - 1].first;
                dp[i].second = 1 + dp[j - 1].second;
            }
            else if (dp[i].first == cost + lambda + dp[j - 1].first)
            {
                dp[i].second = min(dp[i].second, 1 + dp[j - 1].second);
            }
        }
    }

    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;
    }

    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 * res.second) * 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: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40