Submission #891632

#	Time	Username	Problem	Language	Result	Execution time	Memory
891632		vjudge1	Building Bridges (CEOI17_building)	C++14	100 / 100	120 ms	11008 KiB

building

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 100000;

LL h[MAXN + 10], prew[MAXN + 10];
LL dp[MAXN + 10];

void mineq(LL &dst, LL val) 
{
	dst = min(dst, val);
}

struct Point
{
	LL x, y;
	int ndx;
	
	Point(LL x1 = 0, LL y1 = 0, int n1 = 0)
		: x(x1)
		, y(y1)
		, ndx(n1)
	{
	}
	
	bool operator<(const Point &p) const
	{
		if(x == p.x) return y < p.y;
		return x < p.x;
	}
} point[MAXN + 10], tmp[MAXN + 10];

class Deque
{
	Point q[MAXN + 10];
	int front, rear;
	
public:
	void clear()
	{
		front = rear = 0;
	}
	
	int size()
	{
		return rear - front;
	}
	
	Point& back()
	{
		return q[rear - 1];
	}
	
	void popfront()
	{
		front++;
	}
	
	void popback()
	{
		rear--;
	}
	
	void pushback(Point p)
	{
		q[rear++] = p;
	}
	
	void pushback(LL x = 0, LL y = 0, int ndx = 0)
	{
		q[rear++] = Point(x, y, ndx);
	}
	
	Point& operator[](int ndx)
	{
		return q[ndx + front];
	}
	
	Point& bsslope(int k)
	{
		int l = front, r = rear - 1, m;
		
		while(l < r)
		{
			m = (l + r) / 2;
			if(q[m + 1].y - q[m].y <= k * (q[m + 1].x - q[m].x)) l = m + 1;
			else r = m;
		}
		
		return q[l];
	}
} dq;

void cdq(int l, int r)
{
	if(l == r)
	{
		int ni = point[l].ndx;
		point[l].y = dp[l] - prew[ni] + h[ni] * h[ni];
		return;
	}
	
	int m = (l + r) / 2;
	int lb = l, rb = m + 1;
	int i;
	
	for(i = l; i <= r; i++)
	{
		if(point[i].ndx <= m) tmp[lb++] = point[i];
		else tmp[rb++] = point[i];
	}
	memcpy(point + l, tmp + l, sizeof(Point) * (r - l + 1));
	
	cdq(l, m);
	
	dq.clear();
	//dq.pushback();
	for(i = l; i <= m; i++)
	{
        if(i > l && dq.back().x == point[i].x) continue;
		while(dq.size() > 1 && (dq.back().y - dq[dq.size() - 2].y) * (point[i].x - dq.back().x) >= (point[i].y - dq.back().y) * (dq.back().x - dq[dq.size() - 2].x)) dq.popback();
		dq.pushback(point[i]);
	}
	
	for(i = m + 1; i <= r; i++)
	{
		LL k = h[point[i].ndx] * 2;
		while(dq.size() > 1 && dq[1].y - dq[0].y <= k * (dq[1].x - dq[0].x)) dq.popfront();
		
		int ni = point[i].ndx, nj = dq[0].ndx;
		mineq(dp[ni], dp[nj] + prew[ni - 1] - prew[nj] + (h[ni] - h[nj]) * (h[ni] - h[nj]));
	}
	
	cdq(m + 1, r);
	
	sort(point + l, point + r + 1);
}

int main()
{
	int n;
	int i, w;
	
	scanf("%d", &n);
	for(i = 1; i <= n; i++)
	{
		scanf("%lld", h + i);
		point[i].x = h[i];
		point[i].ndx = i;
		dp[i] = 1e18;
	}
	for(i = 1; i <= n; i++)
	{
		scanf("%d", &w);
		prew[i] = prew[i - 1] + w;
	}
	dp[1] = 0;
	
	sort(point + 1, point + n + 1);
	cdq(1, n);
	
	printf("%lld\n", dp[n]);
	
	return 0;
}

Compilation message (stderr)

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

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