Submission #733499

#	Time	Username	Problem	Language	Result	Execution time	Memory
733499		PenguinsAreCute	Aliens (IOI16_aliens)	C++17	100 / 100	242 ms	7472 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
typedef vector<ii> vii;
#define REP(i, a, b) for(int i = a; i < b; i++)
#define float long double
deque<iii> dq;
ii dp[100005];
int f(iii line, int x) {
    return line.fi.fi * x + line.fi.se;
}
ii query(int x) {
    while(dq.size() > 1) {
        if(f(dq[0], x) < f(dq[1], x)) dq.pop_front();
        else break;
    }
    return mp(f(dq[0], x),dq[0].se);
}
float intersect(int a, int b, int c, int d) {
    return (float)(d - b) / (a - c);
}
float intersect(iii p1, iii p2) {
    return intersect(p1.fi.fi, p1.fi.se, p2.fi.fi, p2.fi.se);
}
void ins(int m, int c, int idx) {
    iii line = mp(ii(m, c),idx);
    while(dq.size() > 1) {
        int s = dq.size();
        if(intersect(dq[s - 1], line) < intersect(dq[s - 2], line)) dq.pop_back();
        else break;
    }
    dq.push_back(line);
}
ii getCst(int n, vii &pts, int cst) {
	dq.clear();
	int prvCst = 0, prvSz = 0;
	REP(i,0,n){
		int m = 2*pts[i].fi, c = 2*pts[i].fi-pts[i].fi*pts[i].fi-prvCst;
		if(i){
			c+=max((int)0,pts[i-1].se-pts[i].fi+1)*max((int)0,pts[i-1].se-pts[i].fi+1);
		}
		ins(m,c,prvSz);
		prvCst=(pts[i].se+1)*(pts[i].se+1)-query(pts[i].se).fi+cst;
		prvSz=query(pts[i].se).se+1;
	}
	return mp(prvCst,prvSz);
}
bool comp(ii a, ii b) {
	if(a.fi==b.fi) return a.se>b.se;
	return a.fi<b.fi;
}
long long take_photos(int32_t n, int32_t m, int32_t k, std::vector<int32_t> r, std::vector<int32_t> c) {
	ii pts[n];
	REP(i,0,n)if(r[i]>c[i])swap(r[i],c[i]);
	REP(i,0,n) pts[i]=mp(r[i],c[i]);
	sort(pts,pts+n,comp);
	vector<ii> imptPts;
	REP(i,0,n) if(imptPts.empty()||pts[i].se>imptPts.back().se) imptPts.pb(pts[i]);
	int relN = imptPts.size();
	int l=-1,h=(int)m*(int)m;
	while(h-l>1){
		int lambda=(l+h)/2;
		if(getCst(relN,imptPts,lambda).se<=(int)k)h=lambda;
		else l=lambda;
	}
	return (long long)getCst(relN,imptPts,h).fi-(int)k*h;
}

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