QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#226771#5153. Delft DistanceFyind#WA 7ms11808kbC++141.7kb2023-10-26 15:53:552023-10-26 15:53:56

Judging History

你现在查看的是最新测评结果

  • [2023-10-26 15:53:56]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:11808kb
  • [2023-10-26 15:53:55]
  • 提交

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'