結果
問題 | No.1413 Dynamic Sushi |
ユーザー |
![]() |
提出日時 | 2021-02-28 21:28:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 575 ms / 4,000 ms |
コード長 | 5,996 bytes |
コンパイル時間 | 2,478 ms |
コンパイル使用メモリ | 218,104 KB |
最終ジャッジ日時 | 2025-01-19 08:25:19 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
#pragma GCC optimize ("Ofast")#include<bits/stdc++.h>using namespace std;#define PI 3.14159265358979323846inline int my_getchar_unlocked(){static char buf[1048576];static int s = 1048576;static int e = 1048576;if(s == e && e == 1048576){e = fread_unlocked(buf, 1, 1048576, stdin);s = 0;}if(s == e){return EOF;}return buf[s++];}inline void rd(int &x){int k;int m=0;x=0;for(;;){k = my_getchar_unlocked();if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){k = my_getchar_unlocked();if(k<'0'||k>'9'){break;}x=x*10+k-'0';}if(m){x=-x;}}inline void rd(double &x){int k;int m=0;int p=0;double r = 1;x = 0;for(;;){k = my_getchar_unlocked();if(k=='-'){m = 1;break;}if(k=='.'){p = 1;break;}if('0'<=k&&k<='9'){x = k - '0';break;}}for(;;){k = my_getchar_unlocked();if(k=='.'){p = 1;continue;}if(k<'0'||k>'9'){break;}if(p){r *= 0.1;x += r * (k - '0');}else{x = x * 10 + k - '0';}}if(m){x = -x;}}struct MY_WRITER{char buf[1048576];int s;int e;MY_WRITER(){s = 0;e = 1048576;}~MY_WRITER(){if(s){fwrite_unlocked(buf, 1, s, stdout);}}};MY_WRITER MY_WRITER_VAR;void my_putchar_unlocked(int a){if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);MY_WRITER_VAR.s = 0;}MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;}inline void wt_L(char a){my_putchar_unlocked(a);}int WRITER_DOUBLE_DIGIT = 15;inline int writerDigit_double(){return WRITER_DOUBLE_DIGIT;}inline void writerDigit_double(int d){WRITER_DOUBLE_DIGIT = d;}inline void wt_L(double x){const int d = WRITER_DOUBLE_DIGIT;int k;int r;double v;if(x!=x || (x==x+1 && x==2*x)){my_putchar_unlocked('E');my_putchar_unlocked('r');my_putchar_unlocked('r');return;}if(x < 0){my_putchar_unlocked('-');x = -x;}x += 0.5 * pow(0.1, d);r = 0;v = 1;while(x >= 10*v){v *= 10;r++;}while(r >= 0){r--;k = floor(x / v);if(k >= 10){k = 9;}if(k <= -1){k = 0;}x -= k * v;v *= 0.1;my_putchar_unlocked(k + '0');}if(d > 0){my_putchar_unlocked('.');v = 1;for(r=(0);r<(d);r++){v *= 0.1;k = floor(x / v);if(k >= 10){k = 9;}if(k <= -1){k = 0;}x -= k * v;my_putchar_unlocked(k + '0');}}}template<class T> inline T pow2_L(T a){return a*a;}template<class S, class T> inline S chmin(S &a, T b){if(a>b){a=b;}return a;}int N;double W;double X[13];double Y[13];double R[13];double V[13];double A[13];double dp[13][10000];int main(){int i, mask;double res = 1e150;double tmp;double dx;double dy;double d;rd(N);rd(W);{int Lj4PdHRW;for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){rd(X[Lj4PdHRW]);rd(Y[Lj4PdHRW]);rd(R[Lj4PdHRW]);rd(V[Lj4PdHRW]);rd(A[Lj4PdHRW]);}}N++;for(i=(0);i<(N);i++){int j;for(j=(0);j<(1<<N);j++){dp[i][j] = 1e150;}}dp[N-1][1<<(N-1)] = 0;for(mask=(0);mask<(1<<N);mask++){for(i=(0);i<(N);i++){if(dp[i][mask] < 1e150){int j;for(j=(0);j<(N);j++){if(!((mask) &(1<<(j)))){double a2conNHc;double hCmBdyQB;double V9aVTaxx;a2conNHc = 0;hCmBdyQB = 1e8;for(;;){V9aVTaxx = (a2conNHc + hCmBdyQB) / 2;if(hCmBdyQB - a2conNHc < 1e-9){break;}if(a2conNHc > 0 && hCmBdyQB - a2conNHc < a2conNHc * 1e-9){break;}if(hCmBdyQB < 0 && hCmBdyQB - a2conNHc < (-hCmBdyQB) * 1e-9){break;}if(V9aVTaxx == a2conNHc || V9aVTaxx == hCmBdyQB){break;}dx = X[i] + R[i] * cos((V[i] * dp[i][mask] + A[i]) * PI / 180);dy = Y[i] + R[i] * sin((V[i] * dp[i][mask] + A[i]) * PI / 180);dx -= X[j] + R[j] * cos((V[j] * (dp[i][mask]+V9aVTaxx) + A[j]) * PI / 180);dy -= Y[j] + R[j] * sin((V[j] * (dp[i][mask]+V9aVTaxx) + A[j]) * PI / 180);d = sqrt((pow2_L(dx))+(pow2_L(dy)));if(d <= W * V9aVTaxx){hCmBdyQB = V9aVTaxx;}else{a2conNHc = V9aVTaxx;}}tmp =((a2conNHc + hCmBdyQB) / 2);chmin(dp[j][mask|(1<<j)], dp[i][mask] + tmp);}}}}}for(i=(0);i<(N);i++){chmin(res, dp[i][(1<<N)-1]);}wt_L(res);wt_L('\n');return 0;}// cLay version 20210227-1// --- original code ---// int N; double W, X[13], Y[], R[], V[], A[];// double dp[13][1d4];// {// double res = double_inf, tmp, dx, dy, d;// rd(N,W,(X,Y,R,V,A)(N));// N++;// rep(i,N) rep(j,1<<N) dp[i][j] = double_inf;// dp[N-1][1<<(N-1)] = 0;// rep(mask,1<<N) rep(i,N) if(dp[i][mask] < double_inf){// rep(j,N) if(!BIT_ith(mask,j)){// tmp = bsearch_min[double,t,0,1e8,E=1e-9][// dx = X[i] + R[i] * cos((V[i] * dp[i][mask] + A[i]) * PI / 180);// dy = Y[i] + R[i] * sin((V[i] * dp[i][mask] + A[i]) * PI / 180);// dx -= X[j] + R[j] * cos((V[j] * (dp[i][mask]+t) + A[j]) * PI / 180);// dy -= Y[j] + R[j] * sin((V[j] * (dp[i][mask]+t) + A[j]) * PI / 180);// d = sqrt(dx ** 2 + dy ** 2);// ](d <= W * t);// dp[j][mask|(1<<j)] <?= dp[i][mask] + tmp;// }// }// rep(i,N) res <?= dp[i][(1<<N)-1];// wt(res);// }