Submission #1070372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070372		fv3	Aliens (IOI16_aliens)	C++14	25 / 100	2031 ms	22360 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;

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;
    vector<pair<ll, ll>> nodes;
    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});
    vector<vector<ll>> dp(node_cnt + 1, vector<ll>(K+1, INF));

    dp[0][0] = 0;
    for (int i = 0; i < node_cnt; i++)
    {
        for (int k = 0; k < K; k++)
        {
            for (int j = i; j < node_cnt; j++)
            {
                ll sz = nodes[j].second - nodes[i].first;
                ll overlap = max(0ll, nodes[i].first + sz - nodes[j+1].first);
                dp[j+1][k+1] = min(dp[j+1][k+1], dp[i][k] + sz * sz - overlap * overlap);
            }
        }
    }

    while (dp.back().back() == INF)
        dp.back().pop_back();
    ll res = dp.back().back();

    // DP[i][k] = min number of cells up to i with k photos
    // (Provided that you still need to take a photo there)
    // Remember to subtract overlapping area

    return res;
}

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