結果
問題 | No.703 ゴミ拾い Easy |
ユーザー |
![]() |
提出日時 | 2024-12-04 16:26:32 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 293 ms / 1,500 ms |
コード長 | 2,337 bytes |
コンパイル時間 | 4,276 ms |
コンパイル使用メモリ | 279,720 KB |
実行使用メモリ | 10,368 KB |
最終ジャッジ日時 | 2024-12-04 16:26:44 |
合計ジャッジ時間 | 12,003 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 46 |
ソースコード
#include <bits/stdc++.h> using namespace std; using uint = unsigned int; using ll = long long; using ull = unsigned long long; template<class T> using V = vector<T>; template<class T> using VV = V<V<T>>; constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); } #define FOR(i, a, b) for(int i=(int)(a);i<(int)(b);i++) #define rep(i,N) for(int i=0;i<(int)(N);i++) #define rep1(i,N) for(int i=1;i<=(int)(N);i++) #define fs first #define sc second #define eb emplace_back #define pb eb #define all(x) x.begin(),x.end() template<class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; } template<class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; } // bit op int popcnt(uint x) { return __builtin_popcount(x); } int popcnt(ull x) { return __builtin_popcountll(x); } int bsr(uint x) { return 31 - __builtin_clz(x); } int bsr(ull x) { return 63 - __builtin_clzll(x); } int bsf(uint x) { return __builtin_ctz(x); } int bsf(ull x) { return __builtin_ctzll(x); } struct Line { mutable ll k, m, p; bool operator<(const Line& o) const { return k < o.k; } bool operator<(ll x) const { return p < x; } }; struct LineContainer : multiset<Line, less<>> { // (for doubles, use inf = 1/.0, div(a,b) = a/b) const ll inf = LLONG_MAX; ll div(ll a, ll b) { // floored division return a / b - ((a ^ b) < 0 && a % b); } bool isect(iterator x, iterator y) { if (y == end()) { x->p = inf; return false; } if (x->k == y->k) x->p = x->m > y->m ? inf : -inf; else x->p = div(y->m - x->m, x->k - y->k); return x->p >= y->p; } void add(ll k, ll m) { auto z = insert({k, m, 0}), y = z++, x = y; while (isect(y, z)) z = erase(z); if (x != begin() && isect(--x, y)) isect(x, y = erase(y)); while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y)); } ll query(ll x) {//gives max value assert(!empty()); auto l = *lower_bound(x); return l.k * x + l.m; } }; int main(){ int N;cin>>N; vector<ll> A(N); vector<ll> X(N); vector<ll> Y(N); for(int i=0;i<N;i++){ cin>>A[i]; } for(int i=0;i<N;i++){ cin>>X[i]; } for(int i=0;i<N;i++){ cin>>Y[i]; } LineContainer dp; ll cost=0; for(int i=0;i<N;i++){ dp.add(2*X[i],-cost-X[i]*X[i]-Y[i]*Y[i]); cost=-dp.query(A[i])+A[i]*A[i]; } ll ans=cost; cout<<ans<<"\n"; }