Submission #786496

#	Time	Username	Problem	Language	Result	Execution time	Memory
786496		hcng	Aliens (IOI16_aliens)	C++14	25 / 100	2069 ms	28756 KiB

aliens

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

#define long long long

struct Point {
    long r;
    long c;
} p[50005], a[50005];

long maxc, plen;
long dp[4005][50005];

long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    
    for (long i = 0; i < n; i++) {
        if (r[i] > c[i]) swap(r[i], c[i]);
        p[i].r = r[i];
        p[i].c = c[i];
    }
    sort(p, p + n,
        [](const Point &a, const Point &b) {
            return a.r < b.r || (a.r == b.r && a.c < b.c);
        }
    );
    
    maxc = -1, plen = 0;
    
    a[0].r = -100, a[0].c = -100;
    for (long i = 0; i < n; i++) {
        if (p[i].c > maxc) {
            maxc = p[i].c;
            a[++plen] = p[i];
        }
    }
    
    n = plen;
    
    for (long i = 0; i <= k; i++)
        for (long j = 0; j <= n; j++)
            dp[i][j] = 1e15;
    dp[0][0] = 0;
    
    long ans = 1e15;
    for (long i = 1; i <= k; i++) {
        for (long j = 1; j <= n; j++) {
            for (long x = 0; x < j; x++) {
                dp[i][j] = min(dp[i][j], dp[i - 1][x] + 
                    (a[j].c - a[x + 1].r + 1) * (a[j].c - a[x + 1].r + 1) - 
                    max(0ll, a[x].c - a[x + 1].r + 1) * max(0ll, a[x].c - a[x + 1].r + 1));
            }
        }
        ans = min(ans, dp[i][n]);
    }
    
    return ans;
}

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