제출 #395374

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
395374		blue	Aliens (IOI16_aliens)	C++17	4 / 100	11 ms	456 KiB

aliens

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

vector<int> R, C;

int N, K;
vector<long long> A(1, -1), B(1, -1);

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

const long long INF = 5'000'000'000'000;



long long parametric_search(long long X, long long Y)
{
    long long CT = (X + Y)/2;

    // cerr << "ct = " << CT << '\n';

    long long dp[N+1]; // minimum area+cost to cover first i points
    int photos[N+1];

    dp[0] = photos[0] = 0;

    for(int i = 1; i <= N; i++)
    {
        photos[i] = i;
        dp[i] = INF;

        for(int j = 0; j < i; j++)
        {
            long long val;
            val = CT + dp[j] + sq(B[i] - A[j+1]) - sq(max(0LL, B[j] - A[i]));

            if(val < dp[i])
            {
                dp[i] = val;
                photos[i] = photos[j] + 1;
            }
            else if(val == dp[i])
            {
                photos[i] = min(photos[i], photos[j] + 1);
            }
        }
    }

    // for(int i = 1; i <= N; i++) cerr << dp[i] << ' ';
    // cerr << '\n';
    // for(int i = 1; i <= N; i++) cerr << photos[i] << ' ';
    // cerr << '\n';

    if(X == Y) return dp[N] - CT * photos[N];
    else
    {
        if(photos[N] <= K)
            return parametric_search(X, CT);
        else return parametric_search(CT+1, Y);
    }
}



long long take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
    // cerr << '\n';
    for(int i = 0; i < n; i++)
    {
        if(r[i] > c[i]) swap(r[i], c[i]);
    }

    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(R[x] == R[y])
            return C[x] > C[y];
        return R[x] < R[y];
    });

    int maxb = -1;

    for(int i:I)
    {
        // cerr << i << ' ';
        if(maxb < c[i])
        {
            maxb = c[i];
            A.push_back(r[i]);
            B.push_back(c[i] + 1);
        }
    }

    N = A.size() - 1;
    K = min(k, N);

    cerr << "points: \n";
    for(int i = 1; i <= N; i++) cerr << A[i] << ' ' << B[i] << '\n';

    cerr << "check\n";


    return parametric_search(0LL, INF);
}

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