Submission #712430

#	Time	Username	Problem	Language	Result	Execution time	Memory
712430		SA01	Aliens (IOI16_aliens)	C++14	4 / 100	8 ms	340 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt")

using ll = long long int;
using ull = unsigned long long int;
using vi = vector<ll>;
using ii = pair<ll,ll>;
using vii = vector<ii>;
using ld = long double;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree < T, null_type, less<T>,
rb_tree_tag,
tree_order_statistics_node_update >;

//#ifdef SA_DEBUG
template <class T>
void print(T a) {cerr << a << endl;}
template <class T, class... V> 
void print(T a, V... b) {cerr << a << ", "; print(b...);}
#define dbg(...) cerr << "[" << __LINE__ << "] " << #__VA_ARGS__ << " :: ", print(__VA_ARGS__)
//#else
//#define dbg(...) 7
//#endif

#define eb emplace_back
#define fi first
#define se second

const ll INFL = 1e18;
const int INF = 1e9;
const double PI = acos(-1);
const ll mod = 1e9+7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<class T, class V> 
ostream& operator << (ostream &s, pair<T, V> a){
	s << a.fi << ' ' << a.se; return s;
}

template<class T, class V> 
istream& operator >> (istream &s, pair<T, V> &a){
	s >> a.fi >> a.se; return s;
}

template<class T> 
ostream& operator << (ostream &s, vector<T> a){
	for(int i = 0; i < (int)a.size(); i++){
		if(i > 0)s << ' ' ; 
		s << a[i];
	} return s;
}

template<class T> 
istream& operator >> (istream &s, vector<T> &a){
	for(T &x : a)s >> x; 
	return s;
}

template<class T> 
void input(T a[], int l, int r, istream &s = cin){
	while(l <= r)s >> a[l++];
}

template<class T> 
void output(T a[], int l, int r, bool en = true, ostream &s = cout){
	while(l <= r){ s << a[l++];
		if(l <= r) s << ' ';
	} if(en)s << "\n";
}
const ll K = 1e5;

long long take_photos(int n, int m, int k, std::vector<int> R, std::vector<int> C) {
  vector<ii> v(n);
  for(int i = 0; i < n; i++){
		v[i] = {R[i], C[i]};
		if(v[i].fi > v[i].se)swap(v[i].fi, v[i].se);
		v[i].se = -v[i].se;
	}
	sort(v.begin(), v.end());
	
	vector<ii> V(1, ii(-1, -1));
	for(auto x : v){
		int l, r;
		tie(l, r) = x;
		r = -r;
		if(V.back().se < r){
			V.eb(l, r);
		}
	}
	n = V.size();
	auto cost = [&](int i, int j){
		ll cst = V[j].se - V[i].fi + 1;
		cst = cst * cst;
		if(i > 0 && V[i - 1].se >= V[i].fi){
			ll temp = (V[i - 1].se - V[i].fi + 1);
			cst -= temp * temp;
		}
		return cst * K;
	};
	//dbg(V);
	auto solve = [&](ll extra){
			deque<ii> opt(1, ii(0, 1));
			vi dp(n);
			vector<int> cnt(n);
			auto getVal = [&](int i, int j){
				return dp[i] + cost(i + 1, j);
			};
			auto cmp = [&](int i, int j, int l){
				return getVal(i, l) > getVal(j, l);
			};
			for(int i = 1; i < n; i++){
				dp[i] = INFL;
				for(int j = 0; j < i; j++){
					ll x = getVal(j, i) + extra;
					if(x < dp[i])dp[i] = x, cnt[i] = cnt[j] + 1;
				}
				//dp[i] = getVal(opt[0].fi, i) + extra;
				//cnt[i] = cnt[opt[0].fi] + 1;
				//opt[0].se++;
				//while(opt.size() > 1 && opt[0].se >= opt[1].se)opt.pop_front();
				//while(!opt.empty() && cmp(opt.back().fi, i, opt.back().se))
						//opt.pop_back();
						
				//if(opt.empty()){
					//opt.eb(i, i + 1);
					//continue;
				//}
				
				//int lo = opt.back().se + 1, hi = n - 1;
				//while(lo < hi){
					//int mid = (lo + hi + 1) / 2;
					//if(cmp(opt.back().fi, i, mid))lo = mid;
					//else hi = mid - 1;
				//}
				
				//if(cmp(opt.back().fi, i, lo))opt.eb(i, lo);
				
			}
			return ii(dp[n - 1], cnt[n - 1]);
	};
	
	ll lo = -1e15, hi = 1e15;
	//dbg(solve(0));
	while(lo < hi){
		ll mid = (lo + hi) >> 1;
		
		if(solve(mid).se > k)lo = mid + 1;
		else hi = mid;
	}
	ll a, b, c, d;
	tie(a, b) = solve(lo);
	tie(c, d) = solve(lo + 1);
	if(d < k)k = b;
	return (a - lo * k) / K;
	
}
/*

5 7 2
0 3
4 4
4 6
4 5
4 6

2 6 2
1 4
4 1

*/

Compilation message (stderr)

aliens.cpp: In lambda function:
aliens.cpp:117:9: warning: variable 'cmp' set but not used [-Wunused-but-set-variable]
  117 |    auto cmp = [&](int i, int j, int l){
      |         ^~~

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