Submission #570997

#	Time	Username	Problem	Language	Result	Execution time	Memory
570997		definitelynotmee	Aliens (IOI16_aliens)	C++98	25 / 100	2062 ms	22356 KiB

aliens

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using ll = long long;
using pii = pair<int,int> ;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
const int INF =(1<<30)-1;
const ll INFL = (1ll<<61)-1;

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {

    vector<pll> v(n);
    for(int i = 0; i < n; i++){
        v[i] = {r[i],c[i]};
        if(r[i]-c[i] > 0){
            swap(v[i].ff,v[i].ss);
        }
    }

    vector<pll> pareto{{-1,-1}};
    sort(all(v),[&](pll a, pll b){
        if(a.ff == b.ff)
            return a.ss > b.ss;
        return a.ff < b.ff;
    });

    for(int i = 0; i < n; i++){
        if(pareto.back().ss < v[i].ss)
            pareto.push_back(v[i]);
    }
    n = pareto.size();
    swap(v,pareto);

    matrix<ll> dp(k+1,vector<ll>(n,INFL));

    for(int i = 0; i <= k; i++)
        dp[i][0] = 0;
    
    // cout << "----\n";
    // for(pll i : v)
    //     cout << i.ff << ' ' << i.ss << '\n';

    for(int i = 1; i <= k; i++){
        for(int j = 1; j < n; j++){
            for(int l = 1; l <= j; l++){
                ll newarea = (v[j].ss-v[l].ff+1)*(v[j].ss-v[l].ff+1);
                if(v[l].ff <= v[l-1].ss){
                    newarea-=(v[l-1].ss-v[l].ff+1)*(v[l-1].ss-v[l].ff+1);
                }
                dp[i][j] = min(dp[i][j],dp[i-1][l-1]+newarea);
                //cout << i << ' ' << j << ' ' << l << ' ' << newarea << '\n';
            }
        }
    }
    return dp[k][n-1];
}

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