QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#226771 | #5153. Delft Distance | Fyind# | WA | 7ms | 11808kb | C++14 | 1.7kb | 2023-10-26 15:53:55 | 2023-10-26 15:53:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 705;
const int maxm = 6000005;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define debug(x) cout<<#x<<':'<<x<<endl;
typedef long double ld;
const ld pi=acos(-1.0);
ld dp[maxn][maxn];
const ld inf=1e18;
int main(){
int h,w;
cin>>h>>w;
// cout<<h<<w<<endl;
vector<string>s(h+5);
for(int i=0;i<h;i++) cin>>s[i];
for(int i=0;i<maxn;i++){
for(int j=0;j<maxn;j++){
dp[i][j]=inf;
}
}
dp[0][1]=0;
dp[1][0]=0;
dp[0][0]=0;
for(int j=3;j<2*w+1;j+=2){
dp[0][j]=dp[0][j-2]+1;
// debug(dp[0][j]);
}
for(int i=3;i<2*h+1;i+=2){
dp[i][0]=dp[i-2][0]+1;
// debug(dp[i][0]);
}
for(int i=1;i<2*h+1;i++){
for(int j=1;j<=2*w+1;j++){
if(i%2==1&&j%2==1) {
continue;
}
if(i%2==0&&j%2==0){
continue;
}
if(i==0||j==0) continue;
if(i%2==1) {
if(s[i/2][(j-1)/2]=='O') dp[i][j]=min(dp[i][j],dp[i-1][j-1]+pi/4);
else dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
if(i-2>0)dp[i][j]=min(dp[i][j],dp[i-2][j]+1);
}
if(j%2==1){
if(s[(i-1)/2][j/2]=='O') dp[i][j]=min(dp[i][j],dp[i-1][j-1]+pi/4);
else dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
if(j-2>0)dp[i][j]=min(dp[i][j],dp[i][j-2]+1);
}
// debug(i);debug(j);
// debug(dp[i][j]);
}
}
cout<<fixed<<setprecision(8)<<(1+min(dp[2*h][2*w-1],dp[2*h-1][2*w]))*10<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 11768kb
input:
3 5 XOOXO OXOXO XXXXO
output:
71.41592654
result:
ok found '71.4159265', expected '71.4159265', error '0.0000000'
Test #2:
score: 0
Accepted
time: 3ms
memory: 11524kb
input:
1 4 XOOX
output:
45.70796327
result:
ok found '45.7079633', expected '45.7079633', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 11768kb
input:
1 1 X
output:
20.00000000
result:
ok found '20.0000000', expected '20.0000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 11468kb
input:
1 1 O
output:
17.85398163
result:
ok found '17.8539816', expected '17.8539816', error '0.0000000'
Test #5:
score: 0
Accepted
time: 3ms
memory: 11524kb
input:
1 3 XOO
output:
35.70796327
result:
ok found '35.7079633', expected '35.7079633', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 11756kb
input:
1 5 OXOOO
output:
55.70796327
result:
ok found '55.7079633', expected '55.7079633', error '0.0000000'
Test #7:
score: 0
Accepted
time: 3ms
memory: 11528kb
input:
6 10 XXXXXOOOOX XXOOOOOOOO XXXOXOOXOX OXOXOXXOOX OOXXOXXXXO OXOXXOOXOO
output:
142.83185307
result:
ok found '142.8318531', expected '142.8318531', error '0.0000000'
Test #8:
score: 0
Accepted
time: 2ms
memory: 11596kb
input:
1 2 XX
output:
30.00000000
result:
ok found '30.0000000', expected '30.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 3ms
memory: 11628kb
input:
10 1 X X X O O O X O O X
output:
105.70796327
result:
ok found '105.7079633', expected '105.7079633', error '0.0000000'
Test #10:
score: 0
Accepted
time: 2ms
memory: 11528kb
input:
18 6 OOOOOO OOOOOO XOOOOO OOOOXO OOOXOO OOOOOO OOOOOO OOOOOO OOOOOX OOOOOO OOOXOO OOOOOO OOOOOO OOOOOO OOOOOO OOOOOO OOOOOO OOOOOO
output:
214.24777961
result:
ok found '214.2477796', expected '214.2477796', error '0.0000000'
Test #11:
score: 0
Accepted
time: 2ms
memory: 11600kb
input:
40 9 OOOOXOXXX XOXXXOXXO OXOXXXXXO OXOXXXOXX XXXXOXOXX XXOOXOXXX XOOXOXXXX XOXXOOXOX OXXOOOOXX XXOOOXXOO OXOOXOXXX OOOOOXOOO OXXXXXXXO OOOOOOOXX OOOXXXOOX OXOXXOOOO OOOOXOXOO OXOXOOOXO OXXOOXXXO OXOOXOOXO XXXOXOXOO XXOOOXOOX OOXXOOXOO XOOXXXXOX OXXXXOOOO OXOOOOXOX XXOXXXOOO OOXOOOXXX OXOOOOXOO OXOOO...
output:
453.51768778
result:
ok found '453.5176878', expected '453.5176878', error '0.0000000'
Test #12:
score: 0
Accepted
time: 2ms
memory: 11536kb
input:
41 50 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXO XXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXOXXXXXXXXXXXXXXX XXXXXXXXXXXXXOXXXXXXXXXXXXXXOXXXXXXXXXX...
output:
873.51768778
result:
ok found '873.5176878', expected '873.5176878', error '0.0000000'
Test #13:
score: -100
Wrong Answer
time: 7ms
memory: 11808kb
input:
329 527 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
5040.00000000
result:
wrong answer 1st numbers differ - expected: '8560.0000000', found: '5040.0000000', error = '0.4112150'