Submission #138404

#	Time	Username	Problem	Language	Result	Execution time	Memory
138404		Runtime_error_	Aliens (IOI16_aliens)	C++14	60 / 100	1753 ms	355692 KiB

aliens

#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 sqr(ll x){
    return x*x;
}
 
//ll dp[K][inf];
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;
}
 
// this code to get maximum
// to get minimum use -m , -p , -query
 
struct line{
 
    ll m,p;
    ll eval(ll x){
        return m*x+p;
    }
    ld intersectX(line l){
        return (ld) (p - l.p) / (l.m - m);
    }
};
 
struct LineContainer {
 
    deque<line> dq;
    #define last dq.size()-1
 
    void add(ll m,ll p){
        line cur = {m,p};
        while(dq.size() >= 2 && dq[last-1].intersectX(cur) <= dq[last-1].intersectX(dq[last]))
            dq.pop_back();
        dq.push_back(cur);
    }
 
    ll query(ll x){
        while(dq.size() >= 2 && dq[0].eval(x) <= dq[1].eval(x))
            dq.pop_front();
        return dq[0].eval(x);
    }
};
 
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
 
    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 dp[k+2][n+2] = {0};
    memset(dp,61,sizeof(dp));
    dp[0][0] = 0;
 
    for(ll j=1;j<=k;j++){
      	LineContainer lc;
        for(ll i=1;i<=n;i++){
            ll m = -2ll * a[i].first ,
            p = sqr(a[i].first) + dp[j-1][i-1] - sqr(max(0ll,a[i-1].second - a[i].first+1) ) - 2ll*a[i].first;
            lc.add(-m,-p);
 
            ll add = sqr(a[i].second) + 2ll*a[i].second + 1 , x = a[i].second;
            dp[j][i] = add - lc.query(x);
 
            /*for(ll z = 1;z<=i;z++)
                dp[j][i] = min( dp[j][i] , dp[j-1][z-1] +
                            sqr(a[i].second - a[z].first+1) - sqr(max(0ll,a[z-1].second - a[z].first+1) ) );*/
        }
    }
    return dp[k][n];
}

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