Submission #1018069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018069		0npata	Aliens (IOI16_aliens)	C++17	60 / 100	1000 ms	1048576 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>

using namespace std;

#define vec vector
#define int long long

const int INF = 1e18;

int eval(pair<int, int> f, int x) {
	return f.first * x + f.second;
}

// returns true iff f(intersect(g, h)) < g(intersect(g, h))
bool comp_mid(pair<int, int> f, pair<int, int> g, pair<int, int> h) {
	auto [a1, b1] = f; auto [a2, b2] = g; auto [a3, b3] = h;
	return (a1-a2)*(b3-b2) < (a3 - a2)*(b1-b2);
}

int take_photos(int32_t n, int32_t m, int32_t k, std::vector<int32_t> r, std::vector<int32_t> c) {

	vec<pair<int, int>> init_rang(n);
	for(int i = 0; i<n; i++) {
		init_rang[i].first = min(r[i], c[i]);
		init_rang[i].second = max(r[i], c[i]);
	}
	sort(init_rang.begin(), init_rang.end());

	vec<pair<int, int>> rang{init_rang[0]};

	for(int i = 1; i<n; i++) {
		if(init_rang[i].second <= rang.back().second) continue;
		if(init_rang[i].first == rang.back().first) {
			rang.back().second = init_rang[i].second;
		}
		else {
			rang.push_back(init_rang[i]);
		}
	}

	n = rang.size();

	vec<vec<int>> dp(n+1, vec<int>(k+1, INF));

	for(int i = 0; i<=k; i++) dp[n][i] = 0;

	vec<deque<pair<int, int>>> cts(k+1);

	for(int i = 0; i<n; i++) {
		rang[i].second++;
	}

	// calls to here should have parameter x decreasing for any given i
	auto query = [&](int i, int x) {
		while(cts[i].size() >= 2 && eval(cts[i][cts[i].size()-2], x) < eval(cts[i].back(), x)) {
			cts[i].pop_back();
		}
		return eval(cts[i].back(), x);
	};

	// calls to here should have parameter a increasing for any given i
	auto insert = [&](int i, int a, int b) {
		while(cts[i].size() >= 2 && comp_mid({a, b}, cts[i][0], cts[i][1])) cts[i].pop_front();
		cts[i].push_front({a, b});
	};

	for(int i = n-1; i>=0; i--) {
		for(int j = 1; j<=k; j++) {
			// insert a line a = -2r[i] b = r[i]**2 + dp[i+1][j-1]
			insert(j, -2*rang[i].second, pow(rang[i].second, 2) + dp[i+1][j-1]);
		}

		for(int j = 1; j<=k; j++) {
			int mn = query(j, rang[i].first); // minimum value at position l[i] of lines in ct[j]
			dp[i][j] = (i>0 & (rang[i-1].second > rang[i].first) ? (-pow(rang[i-1].second - rang[i].first, 2)) : 0) + pow(rang[i].first, 2) + mn;
		}

	}

	int ans = INF;
	for(int i = 0; i<=k; i++) {
		ans = min(ans, dp[0][i]);
	}

	return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int32_t, int32_t, int32_t, std::vector<int>, std::vector<int>)':
aliens.cpp:76:17: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   76 |    dp[i][j] = (i>0 & (rang[i-1].second > rang[i].first) ? (-pow(rang[i-1].second - rang[i].first, 2)) : 0) + pow(rang[i].first, 2) + mn;
      |                ~^~

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