oj.uz

Submission #243267

# Submission time Handle Problem Language Result Execution time Memory
243267 2020-06-30T16:32:02 Z Lawliet Building Bridges (CEOI17_building) C++17
100 / 100
 113 ms 66552 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 = 2 ; i <= n ; i++)
		sumW += w[i];

	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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62968 KB Output is correct
2 Correct 36 ms 62968 KB Output is correct
3 Correct 40 ms 62968 KB Output is correct
4 Correct 37 ms 62968 KB Output is correct
5 Correct 39 ms 63104 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 65332 KB Output is correct
2 Correct 90 ms 66296 KB Output is correct
3 Correct 97 ms 66336 KB Output is correct
4 Correct 93 ms 66296 KB Output is correct
5 Correct 86 ms 66216 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62968 KB Output is correct
2 Correct 36 ms 62968 KB Output is correct
3 Correct 40 ms 62968 KB Output is correct
4 Correct 37 ms 62968 KB Output is correct
5 Correct 39 ms 63104 KB Output is correct
6 Correct 91 ms 65332 KB Output is correct
7 Correct 90 ms 66296 KB Output is correct
8 Correct 97 ms 66336 KB Output is correct
9 Correct 93 ms 66296 KB Output is correct
10 Correct 86 ms 66216 KB Output is correct
11 Correct 101 ms 66552 KB Output is correct
12 Correct 113 ms 66296 KB Output is correct
13 Correct 95 ms 66424 KB Output is correct
14 Correct 101 ms 66424 KB Output is correct
15 Correct 84 ms 66168 KB Output is correct
16 Correct 90 ms 66296 KB Output is correct
17 Correct 80 ms 66296 KB Output is correct
18 Correct 82 ms 66424 KB Output is correct