Submission #739639

#	Time	Username	Problem	Language	Result	Execution time	Memory
739639		Abrar_Al_Samit	Aliens (IOI16_aliens)	C++17	25 / 100	187 ms	5076 KiB

aliens

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

const int nax = 503;
const long long INF = 1e18;

int N, K;
vector<int>col_tag, row_tag;

long long dp[nax][nax];

long long sq(long long x) {
    return x * x;
}
long long solve(int i, int j) {
    if(j>K) return INF;
    if(i==N) return 0LL;

    long long &ret = dp[i][j];
    if(ret!=-1) return ret;

    ret = INF;

    int deepest = 0;
    for(int k=i+1; k<=N; ++k) {
        deepest = max(deepest, row_tag[k-1]);

        long long dimen = deepest - col_tag[i] + 1;
        long long isec = 0;
        if(k<N && col_tag[k]<=deepest) {
            isec = sq((deepest - col_tag[k] + 1));
        }
        if(k==N) {
            ret = min(ret, sq(dimen) + solve(k, j+1));
            break;
        }
        if(row_tag[k]<deepest) continue;

        ret = min(ret, solve(k, j+1) + sq(dimen) - isec);
    }
    return ret;
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    map<int,int>deep;

    for(int i=0; i<n; ++i) {
        if(r[i] < c[i]) swap(r[i], c[i]);
        deep[c[i]] = max(deep[c[i]], r[i]);
    }

    for(auto it : deep) {
        col_tag.push_back(it.first);
        row_tag.push_back(it.second);
    }

    n = col_tag.size();
    N = n;
    K = k;

    memset(dp, -1, sizeof dp);
    return solve(0, 0);
}   

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