제출 #158527

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
158527		dennisstar	Aliens (IOI16_aliens)	C++11	0 / 100	2 ms	376 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<ll,ll> pl;

vector<pl> pii, ar; 
pl lines[100010]; int Sv[100010];
int fr, bk;
ll Dp[100010]; int Cn[100010];

ld cr(pl a, pl b) { return (ld)(a.se-b.se)/(b.fi-a.fi); }

void insert(ll p, ll q)
{
	lines[bk]={p,q};
	while (bk>1 && cr(lines[bk-1], lines[bk-2])>cr(lines[bk-1], lines[bk])) {
		lines[bk-1]=lines[bk]; bk--;
	}
	bk++;
}

ll f(ll x) {
	while (fr+1<bk&&cr(lines[fr], lines[fr+1])<=(ld)x) fr++;
	return x*x+lines[fr].fi*x+lines[fr].se;
}

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
	int i, j;
	for (i=0; i<n; i++) if (r[i]<c[i]) swap(r[i], c[i]);
	for (i=0; i<n; i++) pii.push_back({(ll)r[i],(ll)c[i]});
	sort(pii.begin(), pii.end());
	for (i=0; i<n; i++) {
		while (ar.size()&&ar.back().se>=pii[i].se) ar.pop_back();
		ar.push_back(pii[i]);
	}
	ll st=-1, re=(ll)m*m;
	ll ans=(ll)m*m;
	while (st+1<re)
	{
		fr=bk=0;
		for (i=0; i<ar.size(); i++) Sv[i]=Cn[i]=0;
		insert(-2*(ar[0].se-1), (ar[0].se-1)*(ar[0].se-1));
		ll md=(st+re)/2;
		for (i=0; i<ar.size(); i++) {
			Dp[i]=f(ar[i].fi)+md;
			Cn[i]=Cn[Sv[fr]]+1;
			if (i==n-1) continue;
			if (ar[i].fi<ar[i+1].se) insert(-2*(ar[i+1].se-1), Dp[i]+(ar[i+1].se-1)*(ar[i+1].se-1));
			else insert(-2*(ar[i+1].se-1), Dp[i]+(ar[i+1].se-1)*(ar[i+1].se-1)-(ar[i].fi-ar[i+1].se+1)*(ar[i].fi-ar[i+1].se+1));
			Sv[bk-1]=i;
		}
		if (Cn[ar.size()-1]<=k) re=md;
		else st=md;
		if (Cn[ar.size()-1]<=k) ans=min(ans, Dp[ar.size()-1]-Cn[ar.size()-1]*md);
	}
	return ans;
}

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

aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:45:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (i=0; i<ar.size(); i++) Sv[i]=Cn[i]=0;
             ~^~~~~~~~~~
aliens.cpp:48:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (i=0; i<ar.size(); i++) {
             ~^~~~~~~~~~
aliens.cpp:32:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^

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