結果
問題 |
No.705 ゴミ拾い Hard
|
ユーザー |
![]() |
提出日時 | 2019-10-19 11:03:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 358 ms / 1,500 ms |
コード長 | 1,621 bytes |
コンパイル時間 | 1,365 ms |
コンパイル使用メモリ | 119,996 KB |
実行使用メモリ | 17,516 KB |
最終ジャッジ日時 | 2024-06-26 22:29:37 |
合計ジャッジ時間 | 8,591 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
コンパイルメッセージ
In lambda function, inlined from 'monotone_minima(int, int, const std::function<long long int(int, int)>&)::<lambda(auto:1, int, int, int, int)> [with auto:1 = monotone_minima(int, int, const std::function<long long int(int, int)>&)::<lambda(auto:1, int, int, int, int)>]' at main.cpp:47:8, inlined from 'monotone_minima(int, int, const std::function<long long int(int, int)>&)::<lambda(auto:1, int, int, int, int)> [with auto:1 = monotone_minima(int, int, const std::function<long long int(int, int)>&)::<lambda(auto:1, int, int, int, int)>]' at main.cpp:47:8: main.cpp:47:22: warning: 'k' may be used uninitialized [-Wmaybe-uninitialized] 47 | solve(solve, m+1, u, k, r); | ~~~~~^~~~~~~~~~~~~~~~~~~~~ main.cpp: In lambda function: main.cpp:37:21: note: 'k' was declared here 37 | int k; | ^ In lambda function, inlined from 'monotone_minima(int, int, const std::function<long long int(int, int)>&)::<lambda(auto:1, int, int, int, int)> [with auto:1 = monotone_minima(int, int, const std::function<long long int(int, int)>&)::<lambda(auto:1, int, int, int, int)>]' at main.cpp:46:8, inlined from 'monotone_minima(int, int, const std::function<long long int(int, int)>&)::<lambda(auto:1, int, int, int, int)> [with auto:1 = monotone_minima(int, int, const std::function<long long int(int, int)>&)::<lambda(auto:1, int, int, int, int)>]' at main.cpp:46:8, inlined from 'monotone_minima(int, int, const std::function<long long int(int, int)>&)::<lambda(auto:1, int, int, int, int)> [with auto:1 = monotone_minima(int, int, const std::function<long long int(int, int)>&)::<lambda(auto:1, int, int, int, int)>]' at main.cpp:47:8: main.cpp:47:22: warning: 'k' may be used uninitialized [-Wmaybe-uninitialized] 47 | solve(solve, m+1, u, k, r); | ~~~~~^~~~~~~~~~~~~~~~~~~~~ main.cpp: In lambda function: main.cpp:37:21: note: 'k' was declared here 37 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, ll> P; int n; ll a[300030], x[300030], y[300030]; ll dp[300030]; vector<P> monotone_minima(int h, int w, const function<ll(int, int)> &f){ vector<P> dp(h); const ll INF=1e18; auto solve=[&](auto solve, int d, int u, int l, int r)->void{ if(d>u) return; int m=(d+u)/2; ll mn=INF; int k; for(int i=l; i<=r; i++){ ll v=f(m, i); if(mn>v){ mn=v; k=i; } } dp[m]=P(k, mn); solve(solve, d, m-1, l, k); solve(solve, m+1, u, k, r); }; solve(solve, 0, h-1, 0, w-1); return dp; } void solve(int l, int r){ if(l>r) return; int m=(l+r)/2; solve(l, m-1); vector<P> dp1=monotone_minima(r-m+1, m-l+1, [&](int i, int j){ return dp[j+l-1]+y[j+l]*y[j+l]*y[j+l]+abs(x[j+l]-a[i+m])*abs(x[j+l]-a[i+m])*abs(x[j+l]-a[i+m]);}); for(int i=m; i<=r; i++) dp[i]=min(dp[i], dp1[i-m].second); solve(m+1, r); } int main() { scanf("%d", &n); const ll INF=1e18; fill(dp, dp+n+1, INF); dp[0]=0; 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]); solve(1, n); printf("%lld\n", dp[n]); return 0; }