Submission #292613

#	Time	Username	Problem	Language	Result	Execution time	Memory
292613		VodkaInTheJar	Aliens (IOI16_aliens)	C++14	Compilation error	0 ms	0 KiB

aliens

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

using namespace std;

const int maxn = 100003; 
const double inf = 1/.0;

struct line
{
	long long k, m, delta;  
    double p; 
    bool operator < (const long long &t) {return p < t;}
};

double intersection_point(line a, line b)
{
	if (a.k == b.k)
	return (a.m >= b.m ? -inf: inf);
	
	else
	return (double)(b.m - a.m) / (double)(a.k - b.k);
}

struct line_container
{
	vector <line> lines;
	void insert_line(long long a, long long b, long long delta)
	{
		line curr = {a, b, delta, 0};
		while (!lines.empty() && intersection_point(curr, lines.back()) <= lines.back().p)
		lines.pop_back();
		
		if (!lines.empty())
		curr.p = intersection_point(curr, lines.back());
		
		else 
		curr.p = -inf;
		
		lines.push_back(curr);
	}
	
	pair <long long, long long> query(long long pos)
	{
		auto it = lower_bound(lines.begin(), lines.end(), pos);
		it--;
		
		return {it->delta, it->k * pos + it->m};
	}
};

vector <pair <long long, long long> > v; 
line_container convex_hull;
double dp[maxn];
long long delta[maxn];

void calc(long long x)
{
	convex_hull.lines.clear();
	dp[0] = 0; 
	delta[0] = 0; 
	convex_hull.insert_line(2 * v[0].first, -dp[0] - 1ll * v[0].first * v[0].first, 0);
	
	for (int i = 1; i <= (int)v.size(); i++)
	{
		auto curr = convex_hull.query(v[i-1].second + 1);
		dp[i] = -curr.second + (v[i-1].second + 1) * (v[i-1].second + 1) + x;
		delta[i] = curr.first + 1; 
		 
		if (i != (int)v.size())
		{
			long long curr_c = -dp[i] - v[i].first * v[i].first;
		    if (v[i-1].second >= v[i].first)
		    curr_c += (v[i-1].second - v[i].first + 1) * (v[i-1].second - v[i].first + 1); 
			convex_hull.insert_line(2 * v[i].first, curr_c, delta[i]);
		}
		
		/*
		dp[i] = inf1; 
		for (int j = i; j >= 1; j--)
		{
			double curr = 1ll * (v[i-1].second - v[j-1].first + 1) * (v[i-1].second - v[j-1].first + 1) + dp[j-1];
			if (j != 1 && v[j-2].second >= v[j-1].first)
			curr += 1ll * (v[j-2].second - v[j-1].first + 1) * (v[j-2].second - v[j-1].first + 1);
		    
		    if (curr + x < dp[i])
		    dp[i] = curr + x, delta[i] = delta[j-1] + 1; 
		}
		*/
	}
}

long long take_photos(int n, int m, int k, vector <int> r, vector <int> c)
{
	map <int, int> mp;
	for (int i = 0; i < n; i++)
	{
		r[i]++;
		c[i]++; 
		
		int ll = min(r[i], c[i]);
		int rr = max(r[i], c[i]);

		if (!mp.count(rr) || ll < mp[rr])
		mp[rr] = ll; 
	}
	
	for (auto i: mp)
	{ 
		while (!v.empty() && v.back().first >= i.second)
		v.pop_back();
		
		v.push_back({i.second, i.first});
	}
	
	
	long long low = -1e9, high = 1e9;
	while (low < high)
	{ 
		//cout << low << " " << high << endl; 
		long long mid = (low + high) / 2; 
		calc(mid);
		
		if (delta[(int)v.size()] <= k)
		high
		
		else 
		low = mid + 1; 
	}
	
	calc(low);
	assert(delta[(int)v.size()] <= k);
	return dp[(int)v.size()] - 1ll * delta[(int)v.size()] * low;
}


/*
int n, k, m; 
vector <int> r, c;
int main()
{
	cin >> n >> k >> m;
	r.resize(n), c.resize(n);
	for (int i = 0; i < n; i++)
	cin >> r[i] >> c[i];
	
	cout << take_photos(n, m, k, r, c) << endl; 
}
*/

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:125:7: error: expected ';' before 'else'
  125 |   high
      |       ^
      |       ;
  126 | 
  127 |   else
      |   ~~~~ 
aliens.cpp:125:3: warning: statement has no effect [-Wunused-value]
  125 |   high
      |   ^~~~