Submission #427298

#	Time	Username	Problem	Language	Result	Execution time	Memory
427298		vincentpikachu20	Aliens (IOI16_aliens)	C++17	16 / 100	144 ms	2320 KiB

aliens

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

vector<vector<int>> mem;

int dp(vector<int> &a, int n, int i, int k){
    if(mem[i][k] != -1) return mem[i][k];
    if(i == n) return mem[i][k] = 0;
    if(k == 0) return mem[i][k] = 1e18;
    int ans = 1e18;
    for(int j = i; j < n; j ++){
        ans = min(ans, (a[j]-a[i]+1)*(a[j]-a[i]+1) + dp(a,n,j+1,k-1));
    }
    return mem[i][k] = ans;
}

int take_photos(signed n, signed m, signed k, vector<signed> r, vector<signed> c) {
    if(n <= 50 && m <= 100 && k == n){
        int ans = 0;
        vector<vector<bool>> a(m,vector<bool>(m));
        for(int i = 0; i < n; i ++){
            int mi = min(r[i],c[i]);
            int ma = max(r[i],c[i]);
            for(int j = mi; j <= ma; j ++){
                for(int k = mi; k <= ma; k ++){
                    if(!a[j][k]) ans ++;
                    a[j][k] = true;
                }
            }
        }
        return ans;
    }else{
        r.erase(unique(r.begin(), r.end()), r.end());
        sort(r.begin(), r.end());
        vector<int> rr(r.begin(), r.end());
        n = rr.size();
        mem = vector<vector<int>>(n+1,vector<int>(k+1,-1));
        return dp(rr,n,0,k);
    }
}

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