結果
問題 | No.703 ゴミ拾い Easy |
ユーザー |
![]() |
提出日時 | 2024-12-04 16:26:32 |
言語 | C++23(gcc13) (gcc 13.2.0 + boost 1.83.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 1 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 1 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 2 ms
5,248 KB |
testcase_13 | AC | 1 ms
5,248 KB |
testcase_14 | AC | 3 ms
5,248 KB |
testcase_15 | AC | 3 ms
5,248 KB |
testcase_16 | AC | 2 ms
5,248 KB |
testcase_17 | AC | 3 ms
5,248 KB |
testcase_18 | AC | 3 ms
5,248 KB |
testcase_19 | AC | 2 ms
5,248 KB |
testcase_20 | AC | 3 ms
5,248 KB |
testcase_21 | AC | 3 ms
5,248 KB |
testcase_22 | AC | 3 ms
5,248 KB |
testcase_23 | AC | 3 ms
5,248 KB |
testcase_24 | AC | 274 ms
10,240 KB |
testcase_25 | AC | 290 ms
10,240 KB |
testcase_26 | AC | 272 ms
10,240 KB |
testcase_27 | AC | 271 ms
10,368 KB |
testcase_28 | AC | 268 ms
10,240 KB |
testcase_29 | AC | 265 ms
10,240 KB |
testcase_30 | AC | 291 ms
10,368 KB |
testcase_31 | AC | 263 ms
10,240 KB |
testcase_32 | AC | 258 ms
10,240 KB |
testcase_33 | AC | 270 ms
10,240 KB |
testcase_34 | AC | 223 ms
10,240 KB |
testcase_35 | AC | 215 ms
10,240 KB |
testcase_36 | AC | 214 ms
10,240 KB |
testcase_37 | AC | 234 ms
10,240 KB |
testcase_38 | AC | 221 ms
10,240 KB |
testcase_39 | AC | 213 ms
10,368 KB |
testcase_40 | AC | 212 ms
10,240 KB |
testcase_41 | AC | 211 ms
10,240 KB |
testcase_42 | AC | 215 ms
10,240 KB |
testcase_43 | AC | 218 ms
10,368 KB |
testcase_44 | AC | 2 ms
5,248 KB |
testcase_45 | AC | 2 ms
5,248 KB |
testcase_46 | AC | 278 ms
10,240 KB |
testcase_47 | AC | 293 ms
10,240 KB |
testcase_48 | AC | 2 ms
5,248 KB |
testcase_49 | AC | 2 ms
5,248 KB |
ソースコード
#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"; }