結果

問題 No.705 ゴミ拾い Hard
ユーザー vwxyzvwxyz
提出日時 2024-08-09 01:11:47
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 377 ms / 1,500 ms
コード長 2,334 bytes
コンパイル時間 3,019 ms
コンパイル使用メモリ 255,372 KB
実行使用メモリ 16,252 KB
最終ジャッジ日時 2024-08-09 01:11:59
合計ジャッジ時間 10,639 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 3 ms
5,376 KB
testcase_15 AC 3 ms
5,376 KB
testcase_16 AC 3 ms
5,376 KB
testcase_17 AC 3 ms
5,376 KB
testcase_18 AC 3 ms
5,376 KB
testcase_19 AC 3 ms
5,376 KB
testcase_20 AC 3 ms
5,376 KB
testcase_21 AC 3 ms
5,376 KB
testcase_22 AC 3 ms
5,376 KB
testcase_23 AC 3 ms
5,376 KB
testcase_24 AC 359 ms
16,120 KB
testcase_25 AC 359 ms
16,120 KB
testcase_26 AC 376 ms
16,244 KB
testcase_27 AC 350 ms
16,116 KB
testcase_28 AC 356 ms
16,120 KB
testcase_29 AC 377 ms
16,116 KB
testcase_30 AC 361 ms
16,116 KB
testcase_31 AC 320 ms
16,120 KB
testcase_32 AC 337 ms
16,244 KB
testcase_33 AC 265 ms
16,120 KB
testcase_34 AC 245 ms
16,252 KB
testcase_35 AC 299 ms
16,116 KB
testcase_36 AC 315 ms
16,120 KB
testcase_37 AC 306 ms
16,244 KB
testcase_38 AC 317 ms
16,120 KB
testcase_39 AC 363 ms
16,116 KB
testcase_40 AC 2 ms
5,376 KB
testcase_41 AC 1 ms
5,376 KB
testcase_42 AC 2 ms
5,376 KB
testcase_43 AC 356 ms
16,120 KB
権限があれば一括ダウンロードができます

ソースコード

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];
}

int 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