Submission #1070460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070460		fv3	Aliens (IOI16_aliens)	C++14	4 / 100	1 ms	432 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;
            while (l + 1 != i)
            {
                ll n_sz = nodes[i-1].second - nodes[l+1].first;
                ll n_overlap = max(0ll, nodes[l+1].first + n_sz - nodes[i].first);
                ll n_area = dp[l+1][k-1] + n_sz*n_sz - n_overlap * n_overlap;
                //cout << dp[l+1][k-1] << " + " << n_sz << "^2 - " << n_overlap << "^2 = " << n_area << '\n';
                if (n_area > area) break;
                l++;
                sz = n_sz;
                overlap = n_overlap;
                area = n_area;
            }

            dp[i][k] = area;
        }
    }
    
    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