Submission #1070934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070934		fv3	Aliens (IOI16_aliens)	C++14	4 / 100	1 ms	436 KiB

aliens

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

using namespace std;
typedef long long ll;
ll N, M, K;

const ll INF = 1ll << 60ll;

vector<pair<ll, ll>> nodes;
vector<vector<ll>> dp;

ll get_area(int s, int e, int k)
{
    ll sz = nodes[e-1].second - nodes[s].first;
    ll overlap = max(0ll, nodes[s].first + sz - nodes[e].first);
    ll area = dp[s][k-1] + sz*sz - overlap * overlap;
    return area;
}


ll take_photos(int N_, int M_, int K_, vector<int> X, vector<int> Y)
{
    N = N_; M = M_; K = K_;

    vector<int> dist(M), h(M);
    for (int i = 0; i < N; i++)
    {
        if (X[i] > Y[i])
            swap(X[i], Y[i]);
        
        dist[X[i]] = max(dist[X[i]], Y[i] - X[i] + 1);
        h[X[i]] = max(h[X[i]], Y[i] + 1);
    }

    int mx = 0;
    nodes.clear();
    for (int i = 0; i < M; i++)
    {
        if (h[i] <= mx)
        {
            dist[i] = h[i] = 0;
            continue;
        }
        mx = h[i];
        nodes.push_back({i, mx});
    }

    const int node_cnt = nodes.size();
    nodes.push_back({M+1, M+1});

    dp = vector<vector<ll>>(node_cnt + 1, vector<ll>(K+1, INF));

    for (auto&e : dp[0])
        e = 0;

    for (int k = 1; k <= K; k++)
    {
        int L = 0;
        for (int i = 1; i <= node_cnt; i++)
        {
            int cnt = 1;
            int l = L;
            int r = i - 1;
            ll v1, v2;
            while (r - l > 1)
            {
                cnt++;
                int c1 = l + (r - l) / 3;
                int c2 = l + (r - l) * 2 / 3;

                v1 = get_area(c1, i, k);
                if (v1 == INF)
                {
                    r = c1 - 1;
                    break;
                }
                v2 = get_area(c2, i, k);

                if (v1 == v2)
                {
                    l = c1 + 1;
                    r = c2 - 1;
                }
                else if (v1 < v2)
                {
                    r = c2 - 1;
                }
                else
                {
                    l = c1 + 1;
                }
            }
            L = l;
            v1 = get_area(l, i, k);
            if (r == l)
                dp[i][k] = v1;
            else
            {
                v2 = get_area(l+1, i, k);
                dp[i][k] = min(v1, v2);    
            }
        }
    }

    return dp[node_cnt][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