Submission #24374813

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

int n;
long long x[200005], y[200005], za[200005], zb[200005], wa[200005], wb[200005], ans = LLONG_MAX;
vector<tuple<long long, long long, long long>> va, vb;

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%lld", x + i);
	for (int i = 0; i < n; i++)
		y[i + 1] = y[i] + x[i];
	zb[0] = x[0];
	for (int i = 1; i < n; i++) {
		za[i] = za[i - 1] + max(0LL, x[i] - x[i - 1]);
		zb[i] = zb[i - 1] + min(0LL, x[i] - x[i - 1]);
	}
	for (int i = 0; i < n; i++) {
		wa[i + 1] = wa[i] + za[i];
		wb[i + 1] = wb[i] + zb[i];
	}
	va.emplace_back(LLONG_MIN, -n, -wa[n]);
	for (int i = n - 1; i >= 0; i--)
		va.emplace_back(-za[i], n - i * 2, wa[n] - wa[i] * 2);
	va.emplace_back(LLONG_MAX, LLONG_MAX, LLONG_MAX);
	vb.emplace_back(LLONG_MIN, -n, wb[n]);
	for (int i = n - 1; i >= 0; i--)
		vb.emplace_back(zb[i], n - i * 2, -wb[n] + wb[i] * 2);
	vb.emplace_back(LLONG_MAX, LLONG_MAX, LLONG_MAX);
	for (int ia = 0, ib = 0; ; ) {
		long long from = max(get<0>(va[ia]), get<0>(vb[ib]));
		if (from == LLONG_MAX)
			break;
		long long to = min(get<0>(va[ia + 1]), get<0>(vb[ib + 1]));
		long long ta = get<1>(va[ia]) + get<1>(vb[ib]);
		long long tb = get<2>(va[ia]) + get<2>(vb[ib]);
		if (from != LLONG_MIN)
			ans = min(ans, ta * from + tb);
		if (to != LLONG_MAX)
			ans = min(ans, ta * to + tb);
		if (to == get<0>(va[ia + 1]))
			ia++;
		else
			ib++;
	}
	printf("%lld\n", ans);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:10:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   10 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
./Main.cpp:12:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   12 |   scanf("%lld", x + i);
      |   ~~~~~^~~~~~~~~~~~~~~

Judge Result