제출 #243263

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
243263		Lawliet	Building Bridges (CEOI17_building)	C++17	0 / 100	91 ms	65272 KiB

building

#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXN = 100010;
const int MAXC = 1000010;
const lli INF = 1000000000000000000LL;

struct line
{
	lli A, B;

	line(lli a = 0, lli b = INF)
		: A(a), B(b) {}

	lli getValue(lli x) { return A*x + B; }
};

class LiChaoTree
{
	public:

		int getLeft(int node) { return 2*node; }
		int getRight(int node) { return 2*node + 1; }

		void update(int node, int l, int r, line v)
		{
			int m = ( l + r )/2;

			bool lessMid = ( v.getValue(m) < opt[node].getValue(m) );
			bool lessLeft = ( v.getValue(l) < opt[node].getValue(l) );

			if( lessMid ) swap( opt[node] , v );

			if( l == r ) return;

			if( lessMid != lessLeft ) update( getLeft(node) , l , m , v );
			else update( getRight(node) , m + 1 , r , v );
		}

		lli query(int node, int l, int r, int x)
		{
			if( x < l || r < x ) return INF;
			if( l == r ) return opt[node].getValue( x );

			int m = ( l + r )/2;

			lli ans = opt[node].getValue( x );
			ans = min( ans , query( getLeft(node) , l , m , x ) );
			ans = min( ans , query( getRight(node) , m + 1 , r , x ) );

			return ans;
		}

	protected:

		line opt[4*MAXC];
};

int n;

lli dp[MAXN];
lli h[MAXN], w[MAXN];

LiChaoTree LiChao;

void add(int i)
{
	line cur( -2*h[i] , dp[i] + h[i]*h[i] - w[i] );
	LiChao.update( 1 , 0 , MAXC , cur );
}

int main()
{
	scanf("%d",&n);

	for(int i = 1 ; i <= n ; i++)
		scanf("%lld",&h[i]);

	for(int i = 1 ; i <= n ; i++)
		scanf("%lld",&w[i]);

	lli sumW = 0;

	for(int i = 1 ; i <= n ; i++)
		sumW += w[i];

	dp[n] = -w[n];
	add( n );

	for(int i = n - 1 ; i > 0 ; i--)
	{
		dp[i] = LiChao.query( 1 , 0 , MAXC , h[i] ) + h[i]*h[i];
		add( i );
	}

	printf("%lld\n",dp[1] + sumW);
}

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

building.cpp: In function 'int main()':
building.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
building.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&h[i]);
   ~~~~~^~~~~~~~~~~~~~
building.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&w[i]);
   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40