Submission #395311

#	Time	Username	Problem	Language	Result	Execution time	Memory
395311		blue	Aliens (IOI16_aliens)	C++17	4 / 100	1 ms	296 KiB

aliens

#include "aliens.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

/*
Cells (r, c) and (c, r) are equivalent.
(a, b) = (min(r, c), max(r, c))

A square (p, q) covers point (a, b) if and only if p <= a and b <= q

If (a1, b1) and (a2, b2) are points and a1 <= a2 and b2 <= b1, then (a2, b2) is irrelevant.
So, for any (a1, b1) and (a2, b2)   a1 < a2 <=> b1 < b2

When checking for overlapping areas, we only have to consider the last square.

Let points be sorted (a[1], b[1]) < (a[2], b[2]) < .... < (a[x], b[x]).

Let dp[i][k] be the minimum area required to cover the first i points using k squares.

dp[0][k] = 0
dp[i][k] = min{dp[j][k-1] + (b[i] - a[j] + 1)^2 - max(0, b[j] - a[j] + 1)^2 | j=1..i-1}

A point (a, b) requires a square of endpoints (a, a) and (b, b)  (side = b-a+1)



dp[j][x-1] + sq(b[i]-a[j+1])
dp[j][x-1] + b[i]^2 + a[j+1]^2 - 2*b[i]*a[j+1]
1*[[dp[j][x-1] + a[j+1]^2]] + (-2*b[i])*[[ a[j+1] ]]
*/
vector<int> R, C;

vector<long long> a(1), b(1);

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

const long long INF = 1'000'000'000'001;

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
    // cerr << '\n';
    R = r;
    C = c;

    int I[n];
    for(int i = 0; i < n; i++)
        I[i] = i;

    sort(I, I+n, [] (int x, int y)
    {
        if(min(R[x], C[x]) == min(R[y], C[y]))
            return max(R[x], C[x]) > max(R[y], C[y]);
        return min(R[x], C[x]) < min(R[y], C[y]);
    });

    int maxb = -1;

    for(int i:I)
    {
        // cerr << i << ' ';
        if(maxb < max(r[i], c[i]))
        {
            maxb = max(r[i], c[i]);
            a.push_back(min(r[i], c[i]));
            b.push_back(max(r[i], c[i]));
        }
    }

    n = a.size() - 1;
    // for(int i = 1; i <= n; i++) cerr << a[i] << ' ' << b[i] << '\n';

    k = min(k, n);

    long long dp[n+1][k+1];

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


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



    for(int i = 1; i <= n; i++) b[i]++;

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

    for(int x = 2; x <= k; x++)
    {
        int j1 = 1, j2 = 1;

        for(int i = 2; i <= n; i++)
        {
            while(j1+1 < i && b[j1+1] - a[i] <= 0 && dp[j1][x-1] + sq(b[i]-a[j1+1]) >= dp[j1+1][x-1] + sq(b[i]-a[j1+2]))
                j1++;

            dp[i][x] = min(dp[i][x], dp[j1][x-1] + sq(b[i]-a[j1+1]));

            while(j2+1 < i && dp[j2][x-1] + sq(b[i]-a[j2+1]) >= dp[j2+1][x-1] + sq(b[i] - a[j2+2]))
                j2++;

            if(b[j2] - a[i] >= 1)
            {
                dp[i][x] = min(dp[i][x], dp[j2][x-1] + sq(b[i]-a[j2+1]) - sq(b[j2]-a[i]));
            }
        }
    }



    /*for(int i = 1; i <= n; i++)
    {
        // cerr << "i = " << i << ": \n";
        dp[i][0] = INF;
        dp[i][1] = sq(b[i] - a[1]);
        // cerr << dp[i][1] << ' ';
        for(int x = 2; x <= k; x++)
        {
            dp[i][x] = INF;
            for(int j = 1; j < i; j++)
            {
                // cerr << i << ' ' << x << ' ' << j << ' ';
                // cerr << dp[j][x-1] << ' ' << sq(b[i] - a[j+1] + 1) << ' ' << sq(max(0LL, b[j] - a[i] + 1)) << '\n';
                if(b[j] - a[i] >= 1)
                    dp[i][x] = min(dp[i][x], dp[j][x-1] + sq(b[i]-a[j+1]) - sq(b[j]-a[i]));
                else
                    dp[i][x] = min(dp[i][x], dp[j][x-1] + sq(b[i]-a[j+1]));
            }
            // cerr << dp[i][x] << ' ';
        }
        // cerr << '\n';
    }*/

    return dp[n][k];
}

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