結果

問題 No.704 ゴミ拾い Medium
コンテスト
ユーザー vjudge1
提出日時 2025-10-22 16:15:11
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 57 ms / 1,500 ms
コード長 1,266 bytes
コンパイル時間 1,584 ms
コンパイル使用メモリ 162,612 KB
実行使用メモリ 38,904 KB
最終ジャッジ日時 2025-10-22 16:15:18
合計ジャッジ時間 7,017 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int ll

const int N = 1000000;
const int inf = 1e18;
using namespace std;

inline int read () {
	int x = 0, k = 1; char c = getchar();
	while (c < '0' || c > '9') { if (c == '-') k = -1; c = getchar(); }
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return x * k;
}

int n;
int a[N + 100], x[N + 100], y[N + 100], f[N + 100];

int val[3][N + 100];
void update (int o, int k, int x) { ++k; for (int i = k; i <= N; i += (i & -i)) val[o][i] = min(val[o][i], x); }
int query (int o, int k, int ret = inf) { ++k; for (int i = k; i >= 1; i -= (i & -i)) ret = min(ret, val[o][i]); return ret; }


signed main() {
	n = read();
	for (int i = 0; i <= N + 10; ++i) val[0][i] = val[1][i] = inf;
	for (int i = 1; i <= n; ++i) a[i] = read();
	for (int i = 1; i <= n; ++i) x[i] = read();
	for (int i = 1; i <= n; ++i) y[i] = read();

	update(0, x[1], y[1] - x[1]), update(1, N - x[1], x[1] + y[1]);

	for (int i = 1; i <= n; ++i) {
		f[i] = min(a[i] + query(0, a[i]), query(1, N - a[i]) - a[i]);
		if (i != n) update(0, x[i + 1], f[i] - x[i + 1] + y[i + 1]), update(1, N - x[i + 1], f[i] + x[i + 1] + y[i + 1]);
	}

	cout << f[n] << endl;
	return 0;
}

/*

*/
0