結果

問題 No.705 ゴミ拾い Hard
コンテスト
ユーザー hiikunZ
提出日時 2025-03-19 13:32:43
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 314 ms / 1,500 ms
コード長 876 bytes
コンパイル時間 2,006 ms
コンパイル使用メモリ 195,524 KB
実行使用メモリ 19,032 KB
最終ジャッジ日時 2025-03-19 13:32:54
合計ジャッジ時間 10,101 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N;
vector<ll> A(400000),X(400000),Y(400000);
vector<ll> DP(400000,1e18),IDX(400000);
ll f(ll a,ll b){
    ll x = abs(A[a] - X[b - 1]);
    ll y = abs(0 - Y[b - 1]);
    return x * x * x + y * y * y;
}
void check(ll a,ll b){
    if(DP[a] + f(a,b) < DP[b]){
        DP[b] = DP[a] + f(a,b);
        IDX[b] = a;
    }
}
void solve(ll l,ll r){
    if(r - l == 1) return;
    ll m = (l + r) / 2;
    for(ll i = IDX[l];i <= IDX[r];i++) check(i,m);
    solve(l,m);
    for(ll i = l + 1;i <= m;i++) check(i,r);
    solve(m,r);
}
int main(){
    cin >> N;
    for(ll i = 0;i < N;i++) cin >> A[N - 1 - i];
    for(ll i = 0;i < N;i++) cin >> X[N - 1 - i];
    for(ll i = 0;i < N;i++) cin >> Y[N - 1 - i];
    DP[0] = 0;
    IDX[0] = 0;
    DP[N] = f(0,N);
    IDX[N] = 0;
    solve(0,N);
    cout << DP[N] << endl;
}
0