제출 #1326656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326656		Jawad_Akbar_JJ	Aliens (IOI16_aliens)	C++20	60 / 100	2094 ms	11080 KiB

aliens

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

using namespace std;
#define ll long long
const ll N = 1<<17;
ll dp[N][2], r[N], c[N], b[N], m[N];

ll intersection(ll i, ll j){
	ll A = b[j] - b[i], B = m[i] - m[j], pnt = A / B;
	pnt += (A % B != 0);
	return max(pnt, 1LL);
}

long long take_photos(int n, int am, int k, vector<int> x, vector<int> y){
	vector<pair<ll, ll>> vc;
	for (ll i=0;i<n;i++){
		if (x[i] > y[i])
			swap(x[i], y[i]);
		vc.push_back({x[i] + 1, y[i] + 1});
	}
	sort(begin(vc), end(vc));
	n = 0;
	for (ll i=0, mxC = 0;i<vc.size();i++){
		if (vc[i].second <= mxC)
			continue;

		while (r[n] == vc[i].first)
			n--;
		n++;
		mxC = max(mxC, vc[i].second);
		r[n] = vc[i].first, c[n] = vc[i].second;
	}
	r[n+1] = r[n] + 1;

	for (ll i=0;i<=n;i++){
		m[i] = -2 * r[i + 1];
		for (ll j=0;j<2;j++)
			dp[i][j] = 1e16 * (i + j != 0);
	}

	ll Ans = 1LL * am * am;
	while (k--){
		vector<ll> v = {0}, st = {0};
		b[0] = dp[0][0];
		for (ll i=1;i<=n;i++){
			ll L = 0, R = v.size();
			while (L + 1 < R){
				ll mid = (L + R) / 2;
				if (st[mid] > c[i])
					R = mid;
				else
					L = mid;
			}

			ll lst = v[L];
			dp[i][1] = dp[lst][0] + (c[i] - r[lst + 1] + 1) * (c[i] - r[lst + 1] + 1);

			if (i + 1 <= n and c[i] >= r[i + 1])
				dp[i][1] -= (c[i] - r[i+1] + 1) * (c[i] - r[i+1] + 1);

			b[i] = dp[i][0] + r[i + 1] * (r[i + 1] - 2) + 1;

			while (v.size() > 1 and intersection(v.back(), i) <= st.back())
				v.pop_back(), st.pop_back();

			st.push_back(intersection(v.back(), i));
			v.push_back(i);
		}
		Ans = min(Ans, dp[n][1]);
		for (int i=0;i<=n;i++)
			dp[i][0] = dp[i][1], dp[i][1] = 1e16;
	}
	return Ans;
}

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