제출 #1228778

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228778		PlayVoltz	Aliens (IOI16_aliens)	C++20	100 / 100	192 ms	9372 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back

int n;
pii ans;
vector<int> r, c;

struct line{
	int m, c, id;
	line (int m, int c, int id): m(m), c(c), id(id){}
	int operator()(int x){return m*x+c;}
};

deque <line> cht;

pii query(int x){
	while (cht.size()>1){
		if (cht[0](x)>cht[1](x))cht.pop_front();
		else break;
	}
	return mp(cht[0](x), cht[0].id);
}

long double intersect(line a, line b){
	return (long double)(b.c-a.c)/(a.m-b.m);
}

void insert(int m, int c, int id){
	line l = line(m, c, id);
	while (!cht.empty()&&cht.back().m==m){
		if (cht.back().c>c)cht.pop_back();
		else return;
	}
	while (cht.size()>1){
		int s = cht.size();
		if (intersect(cht[s-1], l)<=intersect(cht[s-2], l))cht.pop_back();
		else break;
	}
	cht.push_back(l);
}

bool custom(pii a, pii b){
	if (a.first==b.first)return a.second>b.second;
	return a.first<b.first;
}

int sq(int a){
	return a*a;
}

void alien(int pen){
	cht.clear();
	vector<pii> dp(n+1, mp(LLONG_MAX/2, LLONG_MAX/2));
	dp[0]=mp(0, 0);
	for (int i=1; i<=n; ++i){
		insert(-2*r[i], dp[i-1].first+sq(r[i])-2*r[i]-sq(max(0ll, c[i-1]-r[i]+1)), dp[i-1].second);
		pii res = query(c[i]);
		dp[i]=mp(res.first+sq(c[i])+2*c[i]+pen+1, res.second+1);
	}
	ans=dp[n];
}

long long take_photos(signed _n, signed m, signed k, vector<signed> _r, vector<signed> _c){
	vector<pii> temp(_n), vect;
	for (int i=0; i<_n; ++i)temp[i]=mp(min(_r[i], _c[i]), max(_c[i], _r[i]));
	sort(temp.begin(), temp.end(), custom);
	vect.pb(mp(-1, -1));
	for (int i=0; i<_n; ++i)if (vect.back().second<temp[i].second)vect.pb(temp[i]);
	n=vect.size()-1;
	r.resize(n+1);
	c.resize(n+1);
	for (int i=0; i<=n; ++i)r[i]=vect[i].first, c[i]=vect[i].second;
	int low=-1, high=LLONG_MAX/2;
	while (low+1<high){
		int mid=(low+high)/2;
		alien(mid);
		if (ans.second<=k)high=mid;
		else low=mid;
	}
	alien(high);
	return ans.first-k*high;
}

컴파일 시 표준 에러 (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: 40 / 40