Submission #138759

#	Time	Username	Problem	Language	Result	Execution time	Memory
138759		Hassoony	Aliens (IOI16_aliens)	C++17	25 / 100	151 ms	9080 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MX=1009;
const ll inf = (1ll<<60);
ll dp[MX][MX];
vector<pii>v1;
bool cmp(pii a,pii b){
    if(a.second == b.second)
        return a.first > b.first;
    return a.second < b.second;
}
int n,k;
vector<pair<ll,ll> >a;
ll take_photos(int N, int m, int K, vector<int> r, vector<int> c) {
    n=N;k=K;
    for(int i=0;i<n;i++){
        if(r[i] > c[i])swap(c[i],r[i]);
        v1.push_back({c[i],r[i]});
    }
    sort(v1.begin(),v1.end(),cmp);
    a.push_back({-5,-5});
    a.push_back(v1[0]);
    for(int i=1;i<n;i++){
        if(v1[i].first <= a.back().first) continue;
        a.push_back(v1[i]);
    }
    n=a.size() - 1;
    sort(a.begin(),a.end());
//    for(auto pp:a)cout<<pp.first<<" "<<pp.second<<endl;
    for(int i=1;i<=n;i++)dp[0][i]=inf;
    dp[0][0]=0;
    for(int u=1;u<=k;u++){
        for(int i=1;i<=n;i++)dp[u][i]=inf;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                ll Cost = (a[i].first - a[j].second + 1) * (a[i].first - a[j].second + 1);
                ll Inter = (max(0ll,a[j-1].first - a[j].second + 1)) * (max(0ll,a[j-1].first - a[j].second + 1));
                dp[u][i] = min(dp[u][i], dp[u-1][j-1] + Cost - Inter);
            }
        }
    }
    return dp[k][n];
}
/*
5 7 2
0 3
4 4
4 6
4 5
4 6
*/

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