Submission #520958

#	Time	Username	Problem	Language	Result	Execution time	Memory
520958		qwerasdfzxcl	Aliens (IOI16_aliens)	C++14	100 / 100	216 ms	10168 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
struct Line{
    ll a, b;
    int c;
    Line(){}
    Line(ll _a, ll _b, int _c): a(_a), b(_b), c(_c) {}
    ll get(ll x){return a*x+b;}
};

long double cross(Line &f, Line &g){
    return (long double)(f.b-g.b) / (g.a-f.a);
}

struct LineContainer{
    vector<Line> st;
    int pt;
    void init(){
        st.clear(); pt = 0;
    }
    void insert(ll a, ll b, int c){
        Line L(a, b, c);
        while(st.size()>=2){
            int f = (int)st.size()-2, s = (int)st.size()-1;
            if (cross(st[f], st[s]) >= cross(st[s], L)) st.pop_back();
            else break;
        }
        if (pt>=(int)st.size()) pt = max((int)st.size()-1, 0);
        st.push_back(L);
    }
    pair<ll, int> query(ll x){
        while(pt < (int)st.size()-1){
            if (cross(st[pt], st[pt+1]) < x) pt++;
            else break;
        }
        return {st[pt].get(x), st[pt].c};
    }
}LC;
vector<pair<int, int>> a;
vector<int> X, Y;
vector<pair<ll, int>> dp;

int calc(ll w){
    int n = X.size();
    LC.init();
    dp.clear();

    LC.insert(-X[0]*4, (ll)X[0]*X[0]*2, 0);

    for (int i=0;i<n;i++){
        dp.push_back(LC.query(Y[i]+1));
        dp.back().first += (ll)(Y[i]+1) * (Y[i]+1)*2 + w;
        dp.back().second++;
        if (i==n-1) break;

        LC.insert(-X[i+1]*4, dp[i].first+ (ll)X[i+1]*X[i+1]*2 - (ll)max(Y[i]+1-X[i+1], 0) * max(Y[i]+1-X[i+1], 0)*2, dp[i].second);
    }
    return dp.back().second;
}

bool comp(pair<int, int> &x, pair<int, int> &y){
    if (x.first==y.first) return x.second > y.second;
    return x.first < y.first;
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    for (int i=0;i<n;i++){
        if (r[i]<=c[i]) a.emplace_back(r[i], c[i]);
        else a.emplace_back(c[i], r[i]);
    }
    sort(a.begin(), a.end(), comp);
    for (int i=0;i<n;i++){
        if (X.empty() || Y.back() < a[i].second){
            X.emplace_back(a[i].first);
            Y.emplace_back(a[i].second);
        }
    }

    //for (int i=0;i<(int)X.size();i++) printf(" %d %d\n", X[i], Y[i]);

    //return (ll)1e9 * X.size() + calc(0);
    if (calc(0)<=k) return dp.back().first/2;

    ll L = -1, R = 1e12 + 100, ans = 1e12 + 100;
    while(L<=R){
        ll M = (L+R)>>1;
        if (calc(M*2+1)<k) R = M-1, ans = M;
        else L = M+1;
    }
    calc(ans*2);
    //calc(0);
    //printf("%lld\n", dp.back().first);
    return dp.back().first/2 - ans * 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