제출 #562774

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
562774		elazarkoren	Aliens (IOI16_aliens)	C++17	12 / 100	179 ms	4332 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_N = 5001;
const ll infinity = 1e18;

ll dp[MAX_N][MAX_N];
int ind[MAX_N];

//bool grid[MAX_N][MAX_N];

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
//    for (int i = 0; i < n; i++) {
//        if (r[i] > c[i]) swap(r[i], c[i]);
//        for (int x = r[i]; x <= c[i]; x++) {
//            for (int y = r[i]; y <= c[i]; y++) {
//                grid[x][y] = true;
//            }
//        }
//    }
//    ll ans = 0;
//    for (int i = 0; i < m; i++) {
//        for (int j = 0; j < m; j++) {
//            ans += grid[i][j];
//        }
//    }
//    return ans;
    iota(ind, ind + n, 0);
    sort(ind, ind + n, [&] (int i, int j) {
        return r[i] + c[i] < r[j] + c[j];
    });
    fill(dp[0], dp[0] + n, infinity);
    for (int j = 1; j <= k; j++) {
        for (int i = 0; i < n; i++) {
            dp[j][i] = infinity;
            int left = m, right = 0;
            for (int l = i; l >= 0; l--) {
                chkmin(left, r[ind[l]]);
                chkmax(right, c[ind[l]] + 1);
                ll x = (l ? dp[j - 1][l - 1] : 0) + ll(right - left) * (right - left);
                chkmin(dp[j][i], x);
            }
        }
    }
    return dp[k][n - 1];
}

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