Submission #591392

#	Time	Username	Problem	Language	Result	Execution time	Memory
591392		Vanilla	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	1264 KiB

aliens

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

const int maxn = 5e2 + 2;
int dp[maxn][maxn]; // dp[i][j] -> numarul minim de celule pentru a putea fotografia primele j puncte de interes folosind i fotografii

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    // if (k == n) {
    //     int rs = 0;
    //     for (int i = 0; i < n; i++){

    //     }
    // }
    for (int i = 0; i < maxn; i++){
        for (int j = 0; j < maxn; j++){
            dp[i][j] = 1e8;
        }
    }
    sort(r.begin(), r.end());
    for (int i = 0; i < n; i++) dp[1][i] = (r[i] - r[0] + 1) * (r[i] - r[0] + 1);
    for (int i = 2; i <= k; i++){
        for (int j = 1; j < n; j++){
            for (int k = j; k > 0; k--){
                dp[i][j] = min(dp[i][j], dp[i-1][k-1] + ((r[j] - r[k] + 1) * (r[j] - r[k] + 1)));
            }
        }
    }
    return dp[k][n-1];
}

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