Submission #124356

#	Time	Username	Problem	Language	Result	Execution time	Memory
124356		baluteshih	Aliens (IOI16_aliens)	C++14	100 / 100	230 ms	9060 KiB

aliens

#include "aliens.h"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define pb push_back
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define F first
#define S second
#define ET cout << "\n"
#define MP make_pair
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

bool yee(pll a,pll b)
{
	if(a.F==b.F) return a.S>b.S;
	return a.F<b.F;
}

bool challenge(pll a,pll b,pll c)
{
	return (__int128)(b.S-a.S)*(a.F-c.F)>=(__int128)(c.S-a.S)*(a.F-b.F);
}

pll cal(ll p,vector<pll> &arr)
{
	int n=arr.size();
	vector<pll> dp(n,MP(0,0));
	deque<pair<pll,ll>> dq;
	for(int i=1;i<n;++i)
	{
		pll dt=MP(-2*arr[i].F,arr[i].F*arr[i].F+dp[i-1].F);
		if(arr[i-1].S>arr[i].F) dt.S-=(arr[i-1].S-arr[i].F)*(arr[i-1].S-arr[i].F);
		while(dq.size()>1&&challenge(dq[dq.size()-2].F,dq.back().F,dt))
			dq.pop_back();
		dq.pb(MP(dt,dp[i-1].S+1));
		while(dq.size()>1&&dq[1].F.F*arr[i].S+dq[1].F.S<dq[0].F.F*arr[i].S+dq[0].F.S)
			dq.pop_front();
		while(dq.size()>1&&dq[1].F.F*arr[i].S+dq[1].F.S==dq[0].F.F*arr[i].S+dq[0].F.S&&dq[1].S<=dq[0].S)
			dq.pop_front();
		dp[i]=MP(dq[0].F.F*arr[i].S+dq[0].F.S+arr[i].S*arr[i].S+p,dq[0].S);
	}
	return dp[n-1];
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c)
{
    const ll INF=1e18;
	ll mx=-1,L=0,R=(ll)m*m;
	vector<pll> v,arr;
	for(int i=0;i<n;++i)
		if(r[i]<=c[i]) v.pb(MP(r[i],c[i]+1));
		else v.pb(MP(c[i],r[i]+1));
	sort(ALL(v),yee),arr.pb(MP(-1,-1));
	for(auto i:v)
		if(i.S>mx)
			mx=i.S,arr.pb(i);
	while(L<R)
	{
		ll mid=L+R>>1;
		if(cal(mid,arr).S<=k) R=mid;
		else L=mid+1;
	}
	return cal(L,arr).F-L*k;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:64:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll mid=L+R>>1;
          ~^~
aliens.cpp:52:14: warning: unused variable 'INF' [-Wunused-variable]
     const ll INF=1e18;
              ^~~

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