제출 #1136239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136239		raspy	Aliens (IOI16_aliens)	C++20	0 / 100	0 ms	324 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)
	{
		return (c-l.c)/(l.m-m);
	}
};

struct CHT
{
	deque<line> dq;
	deque<long long> pr;
	CHT() {dq.push_back(line(0, 0));pr.push_back(0);}
	void add(line l, long long k)
	{
		while (dq.size() > 2 && dq[dq.size()-2].inter(l) >= dq.back().inter(l))
		{
			dq.pop_back();
			pr.pop_back();
		}
		dq.push_back(l);
		pr.push_back(k);
	}
	pair<int, int> 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 useless points
	vector<pair<long long, long long>> pnts;
	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<int, int> pr, pair<int, int> dr){
		if (pr.first != dr.first) return pr < dr;
		return pr > dr;
	});
	vector<pair<long long, long long>> a;
	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]);
	// cout << a.size() << "\n";
	// for (auto v:a)
	// 	cout << v.first << " :: " << v.second << "\n";
	// lambda optimization, v a so vse pomembne tocke
	long long l = 0, d = inf, lambda = 0;
	CHT ch;
	vector<pair<long long, long long>> dp;
	while (l <= d)
	{
		long long lamb = (l+d)/2;
		ch = CHT();
		dp = vector<pair<long long, long long>>(a.size());
		for (long long i = 0; i < a.size(); i++)
		{
			auto [r, c] = a[i];
			// if (lamb == 0)
			// 	cout << "-> t: " << sq(r-a[0].second+1)+lamb << " " << r << " " << c << "\n";
			dp[i].first = sq(r-a[0].second+1)+lamb;
			// if (lamb == 0)
			// 	cout << "---> " << dp.back().first << "\n";
			dp[i].second = 1;
			if (i)
			{
				auto [zc, tk] = ch.get_best(r);
				long long t = zc+r*r+lamb;
				dp[i] = min(dp[i], {t, tk+1});
			}
			ch.add(line(-2*(c-1), dp[i].first+sq(c-1)+sq(max(0ll, r-c+1))), dp[i].second);
		}
		// if (lamb == 0)
		// 	cout << "-> " << dp.back().first << "\n";
		// cout << lamb << " " << dp.back().first << " " << dp.back().second << "\n";
		if (dp.back().second <= k)
			d = lamb-1;
		else
			l = lamb+1;
		lambda = lamb;
	}
	return dp.back().first-dp.back().second*lambda;
}

컴파일 시 표준 에러 (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: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40