Submission #727237

#	Time	Username	Problem	Language	Result	Execution time	Memory
727237		PenguinsAreCute	Aliens (IOI16_aliens)	C++17	16 / 100	1 ms	340 KiB

aliens

#include "aliens.h"
#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
#define LL_MAX LONG_LONG_MAX
#define LL_MIN LONG_LONG_MIN
//#define INF 314159265358979323
#define speed ios_base::sync_with_stdio(false); cin.tie(0)
#define stMx(a,b) a = max(a,b)
#define stMn(a,b) a = min(a,b)
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
typedef vector<int> vi;
typedef set<int> si;
typedef vector<ii> vii;
typedef set<ii> sii;
#define REP(i, a, b) for(int i = a; i < b; i++)
#define float long double
deque<iii> dq;
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) {
	ii dp[n];dp[0]=mp(0,0);
	dq.clear();
	REP(i,1,n){
		// insert e line 4 i-1
		ins(2*pts[i].fi,max((int)0,pts[i-1].se-pts[i].fi+1)*max((int)0,pts[i-1].se-pts[i].fi+1)+2*pts[i].fi-pts[i].fi*pts[i].fi-dp[i-1].fi,dp[i-1].se);
		dp[i].fi=(pts[i].se+1)*(pts[i].se+1)-query(pts[i].se).fi+cst; dp[i].se=query(pts[i].se).se+1;
		assert(dp[i].se>=dp[i-1].se);
	}
	return dp[n-1];
}
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);
	vector<ii> imptPts; imptPts.pb(mp(-10,-10));
	REP(i,0,n) if(pts[i].se>imptPts.back().se) imptPts.pb(pts[i]);
	int relN = imptPts.size(); //int dp[relN+1];
	// dp[i][k]=min cst to take <=k photos of [1,i]
	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: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40