제출 #1136327

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136327		raspy	Aliens (IOI16_aliens)	C++20	4 / 100	1 ms	328 KiB

aliens

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

using namespace std;

const long long inf = 10e10;

struct line
{
	long long c, m;
	line(long long _c, long long _m) {c = _c;m=_m;}
	long long operator()(long long x)
	{
		return c+m*x;
	}
	long long inter(line l)
	{
		if ((l.m-m) == 0)
		{
			return inf;
		}
		return (c-l.c)/(l.m-m);
	}
};

struct CHT
{
	deque<line> dq;
	deque<long long> pr;
	CHT() {dq = deque<line>();pr=deque<long long>();}
	void add(line l, long long k)
	{
		while (dq.size() > 1 && dq[dq.size()-2].inter(l) > dq[dq.size()-2].inter(dq.back()))
		{
			dq.pop_back();
			pr.pop_back();
		}
		dq.push_back(l);
		pr.push_back(k);
	}
	pair<long long, long long> get_best(long long x)
	{
		while (dq.size() > 1 && dq[1](x) < dq[0](x))
		{
			dq.pop_front();
			pr.pop_front();
		}
		return {dq[0](x), pr[0]};
	}
};

long long sq(long long x)
{
	return x*x;
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
	// get rid of unimportant points
	vector<pair<long long, long long>> pnts; // array of points only below the line x=y
	for (long long i = 0; i < n; i++)
	{
		if (r[i] > c[i]) swap(r[i], c[i]);
		pnts.push_back({r[i], c[i]});
	}
	sort((pnts).begin(), pnts.end(), [](pair<long long, long long> pr, pair<long long, long long> dr){
		if (pr.first != dr.first) return pr < dr;
		return pr > dr;
	}); // sort them by increasing row and decreasing column nummber
	vector<pair<long long, long long>> a; // save only important points
	a.push_back(pnts[0]);
	for (long long i = 1; i < n; i++)
	{
		if (a.back().second < pnts[i].second)
			a.push_back(pnts[i]);
	}
	//lambda optimization
	long long l = -1, d = m*m*10;
	CHT ch;
	vector<pair<long long, long long>> dp;
	while (l+1 < d)
	{
		long long lamb = (l+d)/2;
		ch = CHT();
		dp = vector<pair<long long, long long>>(a.size());
		ch.add(line(sq(a[0].first)-2*a[0].first+1+lamb, -2*a[0].first), 0);
		for (long long i = 0; i < a.size(); i++)
		{
			auto [x, tk] = ch.get_best(a[i].second);
			x+=sq(a[i].second)+2*a[i].second;
			dp[i] = {x, tk+1};
			if (i==n-1) break;
			ch.add(line(x-sq(max(0ll, a[i].second-a[i+1].first+1))+sq(a[i+1].first) -2*a[i+1].first+1+lamb, -2*a[i+1].first), tk+1);
		}
		if (dp.back().second <= k)
			d = lamb;
		else
			l = lamb;
	}
	return dp.back().first-d*k;
}

컴파일 시 표준 에러 (stderr) 메시지

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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