結果
問題 | No.703 ゴミ拾い Easy |
ユーザー |
![]() |
提出日時 | 2019-10-29 11:00:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 274 ms / 1,500 ms |
コード長 | 3,212 bytes |
コンパイル時間 | 1,451 ms |
コンパイル使用メモリ | 115,820 KB |
実行使用メモリ | 27,080 KB |
最終ジャッジ日時 | 2025-01-02 14:23:13 |
合計ジャッジ時間 | 8,060 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 46 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:123:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 123 | scanf("%d", &N); | ~~~~~^~~~~~~~~~ main.cpp:125:32: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 125 | for (int i=0; i<N; i++) scanf("%d", A+i); | ~~~~~^~~~~~~~~~~ main.cpp:126:32: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 126 | for (int i=0; i<N; i++) scanf("%d", X+i); | ~~~~~^~~~~~~~~~~ main.cpp:127:32: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 127 | for (int i=0; i<N; i++) scanf("%d", Y+i); | ~~~~~^~~~~~~~~~~
ソースコード
#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], (ll)X[i]*X[i] + (ll)Y[i]*Y[i] + dp[i]}); dp[i+1] = tree.query(dic[A[i]]) + (ll)A[i]*A[i]; } cout << dp[N] << endl; return 0; }