結果
問題 |
No.703 ゴミ拾い Easy
|
ユーザー |
![]() |
提出日時 | 2025-04-04 09:55:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 128 ms / 1,500 ms |
コード長 | 1,467 bytes |
コンパイル時間 | 1,869 ms |
コンパイル使用メモリ | 167,056 KB |
実行使用メモリ | 20,484 KB |
最終ジャッジ日時 | 2025-04-04 09:55:30 |
合計ジャッジ時間 | 7,374 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 46 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:33:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 33 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:34:37: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 34 | for (int i = 1;i <= n;++i) scanf("%lld", &a[i]); | ~~~~~^~~~~~~~~~~~~~~ main.cpp:35:37: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 35 | for (int i = 1;i <= n;++i) scanf("%lld", &x[i]); | ~~~~~^~~~~~~~~~~~~~~ main.cpp:36:37: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 36 | for (int i = 1;i <= n;++i) scanf("%lld", &y[i]); | ~~~~~^~~~~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 3e5 + 5; const int V = 1e5; struct line { LL k, b; }li[N]; struct LiChaoSegmentTree { #define ls (id << 1) #define rs (id << 1 | 1) #define mid (l + r >> 1) int idl[N << 2]; inline int cmp(int i, int j, int x) { LL y0 = li[i].k * x + li[i].b, y1 = li[j].k * x + li[j].b; return y0 <= y1 ? i : j; } inline void update(int id, int l, int r, int j) { int& i = idl[id]; if (i == j) return; if (cmp(i, j, mid) == j) swap(i, j); if (cmp(i, j, l) == j) update(ls, l, mid, j); if (cmp(i, j, r) == j) update(rs, mid + 1, r, j); } inline int query(int id, int l, int r, int x) { if (l == r) return idl[id]; return cmp(idl[id], x <= mid ? query(ls, l, mid, x) : query(rs, mid + 1, r, x), x); } }LCSGT; int n; LL a[N], x[N], y[N], dp[N]; int main() { scanf("%d", &n); for (int i = 1;i <= n;++i) scanf("%lld", &a[i]); for (int i = 1;i <= n;++i) scanf("%lld", &x[i]); for (int i = 1;i <= n;++i) scanf("%lld", &y[i]); li[0] = { -2 * x[1], dp[0] + x[1] * x[1] + y[1] * y[1] }; for (int i = 1;i <= n;++i) { int j = LCSGT.query(1, 0, V, a[i]); dp[i] = li[j].k * a[i] + li[j].b + a[i] * a[i]; li[i] = { -2 * x[i + 1], dp[i] + x[i + 1] * x[i + 1] + y[i + 1] * y[i + 1] }; LCSGT.update(1, 0, V, i); } printf("%lld", dp[n]); return 0; }