Submission #144440

#	Time	Username	Problem	Language	Result	Execution time	Memory
144440		ChrisT	Aliens (IOI16_aliens)	C++17	100 / 100	348 ms	11120 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 long double ld;
typedef pair<ld,ld> 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 = 1e5+2;
vector<pii> points;
vector<pii> fin;
ll o[MN];
ld dp[MN];
int cnt[MN];
int which[MN];
line lines[MN];
int n;
void overlap (int j) {
    int x = max(0,fin[j-1].second - fin[j].first + 1);
    o[j] = (ll)x*x;
}
ld intersect (line f, line s) {
    return f.m == s.m ? -1e18 : (f.b - s.b)/(s.m - f.m);
}
ld get (line a, ld x) {return a.m * x + a.b;}
void solve (ld cost) {
    int l = 0, r = 0;
    dp[0] = 0; cnt[0] = 0;
    for (int i = 1; i <= n; i++) {
        line nline = {-2LL * fin[i-1].first,dp[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--;
        which[r] = i-1;
        lines[r++] = nline;
        while (r-l>1 && get(lines[l],fin[i-1].second) >= get(lines[l+1],fin[i-1].second)) l++;
        dp[i] = get(lines[l],fin[i-1].second) + fin[i-1].second * 1LL * fin[i-1].second + 2LL * fin[i-1].second + 1 + cost;
        cnt[i] = cnt[which[l]] + 1;
    }
}
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();
    o[0] = 0;
    for (int i = 1; i < n; i++) overlap(i);
    ld low = 0, high = 1e13, mid;
    while (high - low >= 1e-7) {
        mid = (high+low)/2;
        solve(mid);
        if (cnt[n] <= K) high = mid;
        else low = mid;
    }
    return (ll)round(dp[n] - mid * K);
}

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