Submission #33786

#	Time	Username	Problem	Language	Result	Execution time	Memory
33786		leejseo	Aliens (IOI16_aliens)	C++11	0 / 100	0 ms	394212 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long lld;
#define append push_back
#define MAXN 100001
#define all(v) (v).begin(), (v).end()

long long D[MAXN][501];

struct Point{
    int r, c;
} A[MAXN];

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    // n : interesting place
    // m : row
    // k : max image
    vector <Point> arr;
    for (int i = 0; i < n; i ++) arr.append({min(r[i], c[i]), max(r[i], c[i])});
    sort(all(arr), [](const Point &a, const Point &b){
        if (a.c != b.c) return a.c < b.c;
        return a.r > b.r;
    });
    int K = min(k, n);
    for (int i=1; i <= n; i++) for(int j=1; j<=K; j++) D[i][j] = 1e18;
    for (int i=1; i<=n; i++) D[i][1] = (long long )(A[i].c - A[1].r+1 )*(A[i].c - A[1].r+1);
    for (int i=2; i<K; i++){
        for(int j=1; j<n; j++) for (int k=j+1; k<=n; k++){
            long long v = D[j][i] + (long long)(A[k].c - A[j+1].r+1)*(A[k].c - A[j+1].r+1);
            if (A[j+1].r <= A[j].c)
                v -= (long long)(A[j].c - A[j+1].r+1)*(A[k].c-A[j+1].r+1);
            D[k][i+1] = min(D[k][i+1], v);
        }
    }
    return D[n][K];
}

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