oj.uz

Submission #243263

# Submission time Handle Problem Language Result Execution time Memory
243263 2020-06-30T16:20:59 Z Lawliet Building Bridges (CEOI17_building) C++17
0 / 100
 91 ms 65272 KB 
#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);
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 62976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 91 ms 65272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 62976 KB Output isn't correct
2 Halted 0 ms 0 KB -