Submission #382890

#	Time	Username	Problem	Language	Result	Execution time	Memory
382890		yoavL	Aliens (IOI16_aliens)	C++14	0 / 100	1 ms	364 KiB

aliens

#include <iostream>
#include <vector>
#include <algorithm>

#define rep(s, e) for(ll i = s; i < e; i++)
#define rep(e) for(ll i = 0; i < e; i++)
#define what(x) cout << #x << ": " << x << endl;
#define upmin(a, b) a = min(a, b)
#define pr(v) cout << #v << ": " << endl; for(auto it = v.begin(); it != v.end(); it++) cout << *it << " "; cout << endl;


using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vi = vector<int>;

const ll inf = 1e18;

/*

Solution:

dp[i][j] = min cost to do first i cells with jj squares

do each layer with D&C

Complexity:
O(k*nlogn)

Should get 60

*/




struct seg {
	ll s, e;

	seg() {}
	seg(ll s, ll e) : s(s), e(e) {};

	void print() {
		cout << "(" << this->s << ", " << this->e << ")" << endl;
	}

	inline bool operator<(const seg& other) {
		if (this->s < other.s) return true;
		if (this->s > other.s) return false;
		return (this->e > other.e);
	}
};


ll get_size(ll s, ll e)
{
	if (e < s) return 0;
	ll len = e - s + (ll)1;
	return len * len;
}


bool comp_seg(const seg& s1, const  seg& s2) {
	if (s1.s < s2.s) return true;
	if (s1.s > s2.s) return false;
	return (s1.e > s2.e);
}
using vs = vector<seg>;


seg to_seg(ll x, ll y) {
	seg tans = seg(min(x, y), max(x, y));
	return tans;
}


ll n, m, k;
vs arr;
vvll dp;


void D_C(ll layer, ll l, ll r, ll optl, ll optr)
{
	ll i = (l + r) / 2;
	//what(l);
	//what(r);
	ll opt = 0;
	ll optval = inf;
	for (ll j = optl; j <= min(optr, i); j++) {
		
		ll lastlen = get_size(arr[j].s, arr[i].e);
		ll inter = get_size(arr[j].e, arr[i].s);
		ll curcost = lastlen - inter;
		//what(i);
		//what(j);
		if (j > 0) curcost += dp[layer - 1][j - 1];
		if (optval > curcost) {
			optval = curcost;
			opt = j;
		}
	}

	dp[layer][i] = optval;

	if (l +1 >= r) return;

	D_C(layer, l, i, optl, opt);
	D_C(layer, i, r, opt, optr);
}


ll take_photos(int N, int M, int K, vi r, vi c)
{
	n = N, m = M, k = K;
	vs segs(n);
	rep(n) {
		segs[i] = to_seg(r[i], c[i]);
	}

	sort(segs.begin(), segs.end(), comp_seg);
	
	/*
	for (auto it : segs) {
		it.print();
	}
	*/
	arr.push_back(segs[0]);
	for (ll i = 1; i < n; i++) {
		seg cur = segs[i];
		if (arr[arr.size() - 1].e >= cur.e) continue;
		arr.push_back(cur);
	}

	n = arr.size();
	
	/*
	what(n);
	for (auto it : arr) {
		it.print();
	}
	*/

	dp.resize(k+1, vll(n, inf));

	for (ll layer = 1; layer <= k; layer++) {
		D_C(layer, 0, n, 0, n);
	}

	ll ans = inf;

	for (ll layer = 0; layer <= k; layer++) {
		upmin(ans, dp[layer][n - 1]);
	}

	/*
	for (ll layer = 0; layer <= k; layer++) {
		pr(dp[layer]);
	}
	*/
	return ans;
}

/*

(5, 7, 2, [0, 4, 4, 4, 4], [3, 4, 6, 5, 6])

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

*/

Compilation message (stderr)

aliens.cpp:6: warning: "rep" redefined
    6 | #define rep(e) for(ll i = 0; i < e; i++)
      | 
aliens.cpp:5: note: this is the location of the previous definition
    5 | #define rep(s, e) for(ll i = s; i < e; i++)
      |

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