oj.uz

답안 #891632

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
891632 2023-12-23T11:54:07 Z vjudge1 Building Bridges (CEOI17_building) C++14
100 / 100
 120 ms 11008 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 2 ms 8604 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 120 ms 10844 KB Output is correct
2 Correct 118 ms 10844 KB Output is correct
3 Correct 115 ms 10588 KB Output is correct
4 Correct 115 ms 10732 KB Output is correct
5 Correct 46 ms 10584 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 2 ms 8604 KB Output is correct
6 Correct 120 ms 10844 KB Output is correct
7 Correct 118 ms 10844 KB Output is correct
8 Correct 115 ms 10588 KB Output is correct
9 Correct 115 ms 10732 KB Output is correct
10 Correct 46 ms 10584 KB Output is correct
11 Correct 114 ms 11008 KB Output is correct
12 Correct 112 ms 10820 KB Output is correct
13 Correct 113 ms 10844 KB Output is correct
14 Correct 112 ms 10832 KB Output is correct
15 Correct 49 ms 10688 KB Output is correct
16 Correct 45 ms 10576 KB Output is correct
17 Correct 41 ms 10680 KB Output is correct
18 Correct 42 ms 10844 KB Output is correct