Submission #1070535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070535		fv3	Aliens (IOI16_aliens)	C++14	41 / 100	2099 ms	70992 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));

    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++)
        {
            ll sz = nodes[i-1].second - nodes[l].first;
            ll overlap = max(0ll, nodes[l].first + sz - nodes[i].first);

            ll area = dp[l][k-1] + sz * sz - overlap * overlap;

            for (int j = l; j < i; j++)
            {
                ll n_sz = nodes[i-1].second - nodes[j].first;
                ll n_overlap = max(0ll, nodes[j].first + n_sz - nodes[i].first);
                ll n_area = dp[j][k-1] + n_sz*n_sz - n_overlap * n_overlap;
                if (n_area > area) continue;
                l = j;
                sz = n_sz;
                overlap = n_overlap;
                area = n_area;
            }
          
            dp[i][k] = area;
        }
    }
    
    return dp[node_cnt][K];
}

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