結果

問題 No.705 ゴミ拾い Hard
ユーザー vwxyz
提出日時 2024-08-09 01:11:12
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 380 ms / 1,500 ms
コード長 2,337 bytes
コンパイル時間 2,956 ms
コンパイル使用メモリ 256,116 KB
実行使用メモリ 16,188 KB
最終ジャッジ日時 2024-08-09 01:11:23
合計ジャッジ時間 10,523 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using ll=long long;

//f(i,j)はiからjに移動するコスト、Cは移動回数
ll monotone_minima_limit(int N, function<ll(int, int)> f, int C) {
  ll INF = 1ll<<60;
  vector<ll> D(N + 1, INF);
  D[0] = 0ll;
  for (int _ = 0; _ < C; ++_){
    vector<ll> P = D;
    D.assign(N + 1, INF);
    vector<int> I(N + 1, 0);
    D[0] = 0ll;
    for (int n = 0; n <= N; ++n) {
      if (P[n] + f(n, N) < D[N]) {D[N] = P[n] + f(n, N); I[N] = n;}
    }
    while (find(D.begin(), D.end(), INF) != D.end()) {
      int l=-1;
      for(int r=0;r<N;r++){
        if (D[r]==INF) continue;
        if (l==-1) {l=r; continue;}
        int m = (l + r) / 2;
        for (int n = I[l]; n <= min(I[r], m); ++n) {
          if (P[n] + f(n, m) < D[m]) {D[m] = P[n] + f(n, m); I[m] = n;}
        }
        l=r;
      }
    }
  }
  return D[N];
}

//f(i,j)はiからjに移動するコスト、移動回数に制限なし
ll monotone_minima_unlimit(int N, function<ll(int, int)> f) {
  ll INF = 1ll<<60;
  vector<ll> D(N + 1, INF);
  D[0] = 0ll;
  function<void(int, int)> solve = [&](int L, int R) {
    if (R - L <= 1) return;
    int M = (L + R) / 2;
    solve(L, M);
    vector<ll> U(R - M, INF);
    vector<int> I(R - M, INF);
    for (int n = L; n < M; ++n) {
      if (D[n] + f(n, M) < U[0]) {U[0] = D[n] + f(n, M); I[0] = n;}
      if (D[n] + f(n, R - 1) < U[R - M - 1]) {U[R - M - 1] = D[n] + f(n, R - 1); I[R - M - 1] = n;}
    }
    while (find(U.begin(), U.end(), INF) != U.end()) {
      int l=-1;
      for (int r = M; r < R; ++r) {
        if (U[r - M] == INF) continue;
        if (l==-1){l=r; continue;}
        int m = (l + r) / 2;
        for (int n = I[l - M]; n <= I[r - M]; ++n) {
          if (D[n] + f(n, m) < U[m - M]) {U[m - M] = D[n] + f(n, m); I[m - M] = n;}
        }
        l=r;
      }
    }
    for (int n = M; n < R; ++n) D[n] = min(D[n], U[n - M]);
    solve(M, R);
  };
  solve(0, N + 1);
  return D[N];
}

signed main(){
  int N;cin>>N;
  vector<ll> A(N),X(N),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];
  }
  function<ll(int,int)> f=[&](int i,int j){
    ll d0=abs(X[i]-A[j-1]),d1=abs(Y[i]);
    return d0*d0*d0+d1*d1*d1;
  };
  ll ans=monotone_minima_unlimit(N,f);
  cout<<ans<<endl;
}
0