Submission #144397

#	Time	Username	Problem	Language	Result	Execution time	Memory
144397		ChrisT	Aliens (IOI16_aliens)	C++17	25 / 100	2049 ms	17220 KiB

aliens

#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
char _;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template <typename t> void scan (t& x) {do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0);}
template <typename t, typename ...r> void scan (t& x, r&... xs) {scan(x); scan(xs...);}
const int MN = 4e3+2;
vector<pii> points;
vector<pii> fin;
ll dp[MN][MN];
ll o[MN];
ll area (int j, int i) {
    int x = fin[i].second - fin[j].first + 1;
    return (ll)x*x;
}
void overlap (int j) {
    int x = max(0,fin[j-1].second - fin[j].first + 1);
    o[j] = (ll)x*x;
}
ll f (int j, int i) {
    return area(j,i) - (j == 0 ? 0 : o[j]);
}
ll take_photos (int n, int m, int K, vector<int> r, vector<int> c) {
    for (int i = 0; i < n; i++) points.emplace_back(min(r[i],c[i]),max(r[i],c[i]));
    sort(all(points),[](pii a, pii b) {return a.first == b.first ? a.second > b.second : a.first < b.first;});
    for (int i = 0; i < n; i++) {
        if (!fin.empty() && fin.back().first <= points[i].first && fin.back().second >= points[i].second) continue;
        fin.push_back(points[i]);
    }
    //area of smallest photo covering point j & point i (j < i) = (points[i].second - points[j].first + 1)^2
    //area of overlap for left point j is max(0,points[j-1].second - points[j].first + 1)^2
    //f[i][j] = area of photo - area of overlap
    n = fin.size();
    for (int i = 1; i <= n; i++) dp[i][1] = area(0,i-1);
    for (int i = 0; i < n; i++) overlap(i);
    for (int i = 1; i <= n; i++) {
        for (int k = 2; k <= K; k++) {
            dp[i][k] = LLONG_MAX>>1;
            for (int j = i; j >= 1; j--) {
                dp[i][k] = min(dp[i][k],dp[j-1][k-1] + f(j-1,i-1));
            }
        }
    }
    return dp[n][K];
}

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