Submission #144415

#	Time	Username	Problem	Language	Result	Execution time	Memory
144415		ChrisT	Aliens (IOI16_aliens)	C++17	25 / 100	172 ms	4388 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];
pll lines[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 0;
}
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[1][i] = area(0,i-1);
    o[0] = 0;
    for (int i = 1; i < n; i++) overlap(i);
    for (int k = 2; k <= K; k++) {
        for (int i = 1; i <= n; i++) {
            dp[k][i] = LLONG_MAX>>1;
            for (int j = i; j >= 1; j--) {
                dp[k][i] = min(dp[k][i],dp[k-1][j-1] + fin[i-1].second * 1LL * fin[i-1].second + fin[j-1].first * 1LL * fin[j-1].first + 1 - 2 * fin[i-1].second * fin[j-1].first - 2 * fin[j-1].first + 2 * fin[i-1].second - o[j-1]);
            }
        }
    }
    return dp[K][n];
}

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