Submission #405960

#	Time	Username	Problem	Language	Result	Execution time	Memory
405960		cgiosy	Aliens (IOI16_aliens)	C++17	12 / 100	6 ms	304 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

struct lr {
	int l, r;
	bool operator<(lr b) const { return l<b.l; }
};
ll pw(int x) { return ll(x)*x; }
ll take_photos(int N, int M, int K, vector<int> L, vector<int> R) {
	lr A[N];
	for(int i=0; i<N; i++) {
		int x=L[i], y=R[i];
		A[i]={min(x, y)-1, max(x, y)};
	}
	sort(A, A+N);
	int N2=0;
	for(int i=1; i<N; i++) if(A[N2].r<A[i].r)
		A[N2+=A[N2].l<A[i].l]=A[i];
	K=min(K, N=N2+1);

	auto f=[&](ll m, int k=INT_MAX) {
		ll C[N+1];
		int D[N+1];
		C[0]=D[0]=0;
		for(int i=1; i<=N; i++) {
			C[i]=LLONG_MAX;
			for(int j=0; j<i; j++) if(!j || A[j-1].r<=A[j].l) {
				ll x=C[j]+pw(A[i-1].r-A[j].l)-m;
				if(x<C[i]) C[i]=x, D[i]=D[j]+1;
			}
			if(D[i]>k) return ll(-1);
		}
		return C[N];
	};
	ll l=-pw(M), r=pw(M);
	while(l<r) {
		ll m=l+r+1>>1;
		if(~f(m, K)) l=m;
		else r=m-1;
	}
	return f(r)+K*r;
}

Compilation message (stderr)

aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:38:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   ll m=l+r+1>>1;
      |        ~~~^~

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