Submission #163162

#	Time	Username	Problem	Language	Result	Execution time	Memory
163162		jhnah917	Aliens (IOI16_aliens)	C++14	12 / 100	439 ms	439372 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> p;
 
int n, m, k;
ll dp[101010][555];
p arr[101010];
 
ll take_photos(int N, int m, int k, vector<int> r, vector<int> c){
    ::m = m; ::k = k;
    vector<p> v;
    for(int i=0; i<N; i++) v.emplace_back(min(r[i], c[i]), max(r[i], c[i]));
    sort(v.begin(), v.end(), [](const p &a, const p &b){
        if(a.y != b.y) return a.y < b.y;
        return a.x > b.x;
    });
    n = 0;
    for(auto &i : v){
        while(n && arr[n].y >= i.y) n--;
        arr[++n] = i;
    }
    int q = min(n, k);
    memset(dp, 0x3f, sizeof dp);
    for(int i=1; i<=n; i++) dp[i][1] = (arr[i].y - arr[1].x + 1) * (arr[i].y - arr[1].x + 1);
    
    for(int j=1; j<q; j++){
        for(int k=j; k<n; k++){
            for(int i=k+1; i<=n; i++){
                ll val = dp[k][j] + (arr[i].y - arr[k+1].x + 1) * (arr[i].y - arr[k+1].x + 1);
                if(arr[k+1].x <= arr[k].y) val -= (arr[k].y - arr[k+1].x + 1) * (arr[k].y - arr[k+1].x + 1);
                dp[i][j+1] = min(dp[i][j+1], val);
            }
        }
    }
 
    return dp[n][q];
}

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