Submission #144418

#	Time	Username	Problem	Language	Result	Execution time	Memory
144418		ChrisT	Aliens (IOI16_aliens)	C++17	41 / 100	136 ms	72796 KiB

aliens

#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define m first
#define b second
#define fi fin[i].second
#define fj fin[i].first
char _;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> line;
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];
line 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 area(j,i) - (j == 0 ? 0 : o[j]);
}
double intersect (line f, line s) {
    return f.m == s.m ? -1e18 : double(f.b - s.b)/(s.m - f.m);
}
ll get (line a, ll x) {return a.m * x + a.b;}
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 bb) {return a.first == bb.first ? a.second > bb.second : a.first < bb.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++) {
        int l = 0, r = 0;
        for (int i = 1; i <= n; i++) {
            line nline = {-2LL * fin[i-1].first,dp[k-1][i-1] + fin[i-1].first * 1LL * fin[i-1].first - 2LL * fin[i-1].first - o[i-1]};
            while (r-l>1 && intersect(nline,lines[r-1]) < intersect(lines[r-1],lines[r-2])) r--;
            lines[r++] = nline;
            while (r-l>1 && get(lines[l],fin[i-1].second) >= get(lines[l+1],fin[i-1].second)) l++;
            dp[k][i] = get(lines[l],fin[i-1].second) + fin[i-1].second * 1LL * fin[i-1].second + 2LL * fin[i-1].second + 1;
        }
    }
    return dp[K][n];
}

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