Submission #139689

#	Time	Username	Problem	Language	Result	Execution time	Memory
139689		Runtime_error_	Aliens (IOI16_aliens)	C++14	4 / 100	11 ms	1916 KiB

aliens

// 100 points
#include "aliens.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const ll inf = 1e5+9,K = 509,MX = 1e18+9;
ll n ,k;
pair<ll,ll> dp[inf];

ll sqr(ll x){
    return x*x;
}

pair<ll,ll> a[inf];
vector<pair<ll,ll> > all;

bool cmp(pair<ll,ll>x,pair<ll,ll>y ){
    if(x.first == y.first)
        return x.second > y.second;
    return x.first<y.first;
}

struct line {
    ll m, c,idx;
    ll eval(ll x) { return m * x + c; }
    #define ld long double
    ld intersectX(line l) {
        assert(l.m != m);
         return (ld) (c - l.c) / (l.m - m);
         }
};

struct LineContainer{
    //for maximum
    // m increasing and x increasing
    //to get m is decreasing x is decreasing -m , -x

    deque<line> dq;
    #define last dq.size()-1

    void add(ll m,ll p,ll idx){
        line cur = {m,p,idx};
        while (dq.size() >= 2 && dq[last-1].intersectX(cur) <= dq[last-1].intersectX(dq[last]))
            dq.pop_back();
        dq.push_back(cur);
    }

    pair<ll,ll> query(ll x){
        while (dq.size() >= 2 && dq[0].eval(x) <= dq[1].eval(x))
            dq.pop_front();

        return make_pair(dq[0].eval(x),dq[0].idx);
    }
};

ll solve(ll cost){

    memset(dp,61,sizeof(dp));
    dp[0] = make_pair(0ll,0ll);

    LineContainer lc;
    for(ll i=1; i<=n; i++){
        ll m = -2ll * a[i].first,
        p = sqr(a[i].first) + dp[i-1].first - sqr(max(0ll,a[i-1].second - a[i].first+1) ) - 2ll*a[i].first ;
        lc.add(-m,-p,i);

        ll add = sqr(a[i].second) + 2ll*a[i].second + 1, x = a[i].second;
        dp[i] =  lc.query(x);
        dp[i].first = add - dp[i].first + cost;
    }

    int cur = n,cnt = 0;
    while(cur)
        cnt ++ , cur = dp[cur].second - 1;
    return cnt;
}

ll take_photos(int N, int m, int K, vector<int> R, vector<int> c) {
     n = N;
     k = K;
    for(ll i=0;i<n;i++)
        R[i] ++,c[i]++,
        all.push_back( make_pair(min(R[i],c[i]),max(R[i],c[i]) ) );

    sort(all.begin(),all.end(),cmp);
    n = 1;
    a[1] = all[0];
    for(auto o:all){
        if(o.second <= a[n].second)
           continue;
        a[++n] = make_pair(o.first,o.second);
    }
    k = min(k,n);

    ll l = 0 , r = 1e18+9,mid;
    while(r-l > 1){
        mid = (l+r)/2ll;
        if(solve(mid) > k)
            l = mid;
        else
            r = mid;
    }
    solve(r);
    return dp[n].first - k*r;
}

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