Submission #622487

#	Time	Username	Problem	Language	Result	Execution time	Memory
622487		Lucpp	Aliens (IOI16_aliens)	C++17	25 / 100	2090 ms	504 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

ll sq(ll x){return x*x;}

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
    m--; // suppress warning
    vector<pair<int, int>> v;
    for(int i = 0; i < n; i++){
        v.emplace_back(min(r[i], c[i]), -max(r[i], c[i]));
    }
    sort(v.begin(), v.end());
    vector<pair<ll, ll>> a;
    for(int i = 0; i < n; i++){
        if(a.empty() || a.back().second < -v[i].second) a.emplace_back(v[i].first, -v[i].second);
    }
    n = (int)a.size();
    vector<ll> dp(n, INF);
    for(int h = 0; h < k; h++){
        vector<ll> dp2(n);
        for(int i = 0; i < n; i++){
            dp2[i] = sq(a[i].second-a[0].first+1);
            for(int j = 0; j < i; j++){
                ll cost = sq(a[i].second-a[j+1].first+1) - sq(max(0ll, a[j].second-a[j+1].first+1));
                dp2[i] = min(dp2[i], dp[j]+cost);
            }
        }
        dp = dp2;
    }
    return dp[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