結果
問題 | No.703 ゴミ拾い Easy |
ユーザー |
![]() |
提出日時 | 2019-10-29 10:59:54 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,200 bytes |
コンパイル時間 | 1,519 ms |
コンパイル使用メモリ | 121,156 KB |
実行使用メモリ | 27,180 KB |
最終ジャッジ日時 | 2024-09-14 21:26:09 |
合計ジャッジ時間 | 9,249 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | WA | - |
testcase_04 | AC | 3 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 3 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | WA | - |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | WA | - |
testcase_44 | AC | 2 ms
5,376 KB |
testcase_45 | WA | - |
testcase_46 | WA | - |
testcase_47 | WA | - |
testcase_48 | WA | - |
testcase_49 | WA | - |
ソースコード
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <iostream> #include <complex> #include <string> #include <algorithm> #include <numeric> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <unordered_map> #include <unordered_set> #include <functional> #include <cassert> typedef long long ll; using namespace std; #ifndef LOCAL #define debug(x) ; #else #define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl; template <typename T1, typename T2> ostream &operator<<(ostream &out, const pair<T1, T2> &p) { out << "{" << p.first << ", " << p.second << "}"; return out; } template <typename T> ostream &operator<<(ostream &out, const vector<T> &v) { out << '{'; for (const T &item : v) out << item << ", "; out << "\b\b}"; return out; } #endif #define mod 1000000007 //1e9+7(prime number) #define INF 1000000000 //1e9 #define LLINF 2000000000000000000LL //2e18 #define SIZE 300010 template<typename T> struct LiChaoTree { using Line = pair<T, T>; // first * x + second int segn2; vector<Line> data; vector<T> X; template<typename S> LiChaoTree(vector<S> pos) { int N = pos.size(); for (segn2 = 1; segn2 < N; segn2 *= 2); data.assign(segn2 * 2, {0, INF}); X.assign(segn2, INF); for (int i=0; i<pos.size(); i++) X[i] = pos[i]; } inline T f(Line line, T x) { return line.first * x + line.second; } void addLine(int a, int b, Line line, int l = 0, int r = -1, int k = 0) { if (r == -1) r = segn2; int m = (l + r) / 2; if (r <= a || b <= l) return; if (l < a || b < r) { addLine(a, b, line, l, m, k*2+1); addLine(a, b, line, m, r, k*2+2); return; } if (data[k].second == INF) { //isNull data[k] = line; return; } bool fl = f(line, X[l]) < f(data[k], X[l]); bool fm = f(line, X[m]) < f(data[k], X[m]); bool fr = f(line, X[r-1]) < f(data[k], X[r-1]); if (fl == fr) { if (fl) data[k] = line; return; } if (fm) swap(data[k], line); if (fl ^ fm) addLine(a, b, line, l, m, 2*k+1); else addLine(a, b, line, m, r, 2*k+2); } void addLine(Line line) { addLine(0, segn2, line); } T query(int k) { T x = X[k], res = LLINF; k += segn2-1; while(1){ if (data[k].second != INF) //isNotNull res = min(res, f(data[k], x)); if (!k) break; k = (k - 1) / 2; } return res; } }; int main(){ int N, A[SIZE], X[SIZE], Y[SIZE]; ll dp[SIZE]; scanf("%d", &N); for (int i=0; i<N; i++) scanf("%d", A+i); for (int i=0; i<N; i++) scanf("%d", X+i); for (int i=0; i<N; i++) scanf("%d", Y+i); vector<ll> vec; map<ll, int> dic; for (int i=0; i<N; i++) vec.push_back(X[i]); for (int i=0; i<N; i++) vec.push_back(A[i]); sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end()); LiChaoTree<ll> tree(vec); for (int i=0; i<vec.size(); i++) dic[vec[i]] = i; dp[0] = 0; for (int i=0; i<N; i++) { tree.addLine({-2*X[i], X[i]*X[i] + Y[i]*Y[i] + dp[i]}); dp[i+1] = tree.query(dic[A[i]]) + A[i]*A[i]; } cout << dp[N] << endl; return 0; }