제출 #591400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
591400		Vanilla	Aliens (IOI16_aliens)	C++17	16 / 100	41 ms	4180 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 a[m + 1][m + 1] = {};
        int rs = 0;
        for (int i = 0; i < n; i++){
            for (int j = min(r[i], c[i]); j <= max(r[i], c[i]); j++){
                for (int k = min(r[i], c[i]); k <= max(r[i], c[i]); k++){
                    if (!a[j][k]) rs++;
                    a[j][k] = 1;
                }
            }
        }
        return rs;
    }
    for (int i = 0; i < maxn; i++){
        for (int j = 0; j < maxn; j++){
            dp[i][j] = 1e8;
        }
    }
    vector <pair <int, int> > v; 
    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)));
            }
        }
    }
    int rs = 1e9;
    for (int i = 1; i <= k; i++){
        rs = min(rs, dp[i][n-1]);
    }
    return rs;
}

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