제출 #138396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
138396		Runtime_error_	Aliens (IOI16_aliens)	C++14	25 / 100	2043 ms	56056 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define ll long long
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

bool Q ;
struct Line {
	mutable ll m, p, k;
	bool operator<(const Line& o) const {
		return Q ? k < o.k : m < o.m;
	}
};

struct LineContainer : multiset<Line> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b);
    }

	bool isect(iterator x, iterator y) {
		if (y == end()) {
		     x->k = inf;
		     return false;
        }
		if (x->m == y->m)
            x->k = x->p > y->p ? inf : -inf;
		else
            x->k = div(y->p - x->p, x->m - y->m);
		return x->k >= y->k;
	}
	void add(ll m, ll p) {
		auto z = insert({m, p, 0}), y = z++, x = y;
		while (isect(y, z))
            z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->k >= y->k)
			isect(x, erase(y));
	}
	ll query(ll x) {
        if(empty())
            return -MX;

		assert(!empty());
		Q = 1; auto l = *lower_bound({0,0,x}); Q = 0;
		return l.m * x + l.p;
	}
}lc;

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++){
        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: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40