Submission #309561

#	Time	Username	Problem	Language	Result	Execution time	Memory
309561		Kenzo_1114	Building Bridges (CEOI17_building)	C++17	0 / 100	44 ms	3692 KiB

building

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
const long long int INF = 1e13 + 19;

int n, sz;
long long int w[MAXN], h[MAXN], dp[MAXN];
vector<long long int> A, B;

/*

y = A * x + B
y = y2
A * x + B = A2 * x + B2
A * x - A2 * x = B2 - B
x = (B2 - B) / (A - A2)

*/

bool useless(int l1, int l2, int l3)
{
//	x12 = (B2 - B1) / (A1 - A2)
//	x13 = (B3 - B1) / (A1 - A3)
//	x12 >= x13	
	return (B[l2] - B[l1]) * (A[l1] - A[l3]) >= (B[l3] - B[l1]) * (A[l1] - A[l2]);
}

void add(int a, int b)
{
	A.push_back(a);
	B.push_back(b);
	sz++;

	while(sz >= 3 && useless(sz - 3, sz - 2, sz - 1))
	{
		A.erase(A.end() - 2);
		B.erase(B.end() - 2);
		sz--;
	}
}

//	bgx = (B2 - B1) / (A1 - A2)
//	bgx <= x
//	B2 - B1 <= x * (A1 - A2)
bool before(int id, long long int x)
{
	if(!id)	return true;
	return B[id] - B[id - 1] <= x * (A[id - 1] - A[id]);
}

long long int qry(long long int x)
{
	int bg = 0, ed = sz - 1;
	while(bg < ed)
	{
		int mid = (bg == ed - 1) ? ed : ((bg + ed) >> 1);

		if(before(mid, x))	bg = mid;
		else	ed = mid - 1;
	}

	return A[ed] * x + B[ed];
}

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]);
		w[i] += w[i - 1];
	}
	

	add(-2 * h[1], h[1] * h[1] - w[1]);
	for(int i = 2; i <= n; i++)
	{	
		dp[i] = qry(h[i]) + h[i] * h[i] + w[i - 1];
		add(-2 * h[i], dp[i] + h[i] * h[i] - w[i]);
//		printf("dp[%d] = %lld\n", i, dp[i]);
	}

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

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
building.cpp:69:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |  for(int i = 1; i <= n; i++) scanf("%lld", &h[i]);
      |                              ~~~~~^~~~~~~~~~~~~~~
building.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |   scanf("%lld", &w[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

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