제출 #570975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
570975		definitelynotmee	Aliens (IOI16_aliens)	C++98	0 / 100	1 ms	212 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) {

    for(int& i : r){
        i = m-i-1;
    }
    vector<pll> v(n);
    for(int i = 0; i < n; i++){
        v[i] = {c[i]+1,r[i]+1};
        if(v[i].ff + v[i].ss <= m){
            v[i].ff = m-v[i].ff+1;
            v[i].ss = m-v[i].ss + 1;
        }
        //cout << v[i].ff << ' ' << v[i].ss << '\n';
    }
    ll tot = m*m;

    sort(all(v));

    vector<pll> pareto;
    pareto.push_back({0,INF});

    ll maxx = 0, maxy = 0;
    for(int i = 0; i < n; i++){
        maxx = max(v[i].ff,maxx);
        maxy = max(maxy, v[i].ss);
        while(pareto.size() && pareto.back().ss <= v[i].ss)
            pareto.pop_back();
        pareto.push_back(v[i]);
    }
    n = pareto.size();
    swap(v,pareto);
    // for(pll i : v){
    //     cout << i.ff << ' ' << i.ss << '\n';
    // }
    matrix<ll> dp(k+1,vector<ll>(n,INFL));
    for(int i =0 ; i <= k; i++)
        dp[i][0] = 0;

    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].ff-v[l-1].ff)*v[l].ss;
                //cout << v[j].ff << ' ' << v[l-1].ff << ' ' <<v[l].ss <<' ' << newarea << '\n'; 
                dp[i][j] = min(dp[i][j],dp[i-1][l-1]+newarea);
                //cout << i << ' ' << j << ' ' << l << "=>" << dp[i-1][l-1]+newarea << '\n';
            }
        }
    }
    ll resp = dp[k][n-1]*2-tot+(m-maxx)*(m-maxx)+(m-maxy)*(m-maxy);
    //cout << dp[k][n-1]*2 << ' ' << tot << ' ' << (m-v[1].ss)*(m-v[1].ss+1)/2 << ' ' << (m-v[n-1].ff)*(m-v[n-1].ff+1)/2<< '\n';


    return resp;
}

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