結果

問題 No.705 ゴミ拾い Hard
ユーザー vwxyzvwxyz
提出日時 2024-08-09 01:07:42
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,284 bytes
コンパイル時間 3,173 ms
コンパイル使用メモリ 254,372 KB
実行使用メモリ 16,952 KB
最終ジャッジ日時 2024-08-09 01:07:52
合計ジャッジ時間 9,956 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'll monotone_minima_limit(long long int, std::function<long long int(long long int, long long int)>, long long int)':
main.cpp:33:1: warning: no return statement in function returning non-void [-Wreturn-type]
   33 | }
      | ^

ソースコード

diff #

#include <bits/stdc++.h>
#define int long long

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

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