Submission #773408

#	Time	Username	Problem	Language	Result	Execution time	Memory
773408		Jomnoi	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	468 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;

const int MAX_M = 505;
const long long INF = 1e18 + 7;

int N, M, K;
int a[MAX_M][MAX_M];
long long dp[MAX_M][MAX_M][MAX_M];

long long take_photos(int n, int m, int k, vector <int> r, vector <int> c) {
    N = n, M = m, K = k;
    for (int i = 0; i < N; i++) a[r[i] + 1][c[i] + 1]++;
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= M; j++) a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
    }

    for (int i = 0; i <= K; i++) {
        for (int j = 0; j <= M; j++) {
            for (int n = 0; n <= N; n++) dp[i][n][j] = INF;
        }
    }

    for (int i = 0; i <= M; i++) dp[0][0][i] = 0;
    for (int i = 1; i <= K; i++) {
        for (int j = 1; j <= M; j++) {
            for (int n = 1; n <= N; n++) {
                dp[i][n][j] = INF;
                for (int k = j; k >= 1; k--) {
                    int cost = a[j][j] - a[k - 1][j] - a[j][k - 1] + a[k - 1][k - 1];
                    if (cost == 0 or n < cost) continue;
                    dp[i][n][j] = min(dp[i][n][j], dp[i - 1][n - cost][k - 1] + 1ll * (j - k + 1) * (j - k + 1));
                }
                // cout << i << ' ' << n << ' ' << j << " : " << dp[i][n][j] << endl;
            }
        }
    }

    long long ans = INF;
    for (int i = 1; i <= K; i++) {
        for (int j = 1; j <= M; j++) ans = min(ans, dp[i][N][j]);
    }
    return ans;
}

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