oj.uz

Submission #581535

# Submission time Handle Problem Language Result Execution time Memory
581535 2022-06-22T17:37:05 Z alexdd Tracks in the Snow (BOI13_tracks) C++17
19.7917 / 100
 1589 ms 137532 KB 
#include<iostream>
#include<deque>
using namespace std;
int n,m;
char mat[4001][4001];
int dirlin[4]={1,-1,0,0};
int dircol[4]={0,0,1,-1};
deque<int> dqlin;
deque<int> dqcol;
int best[4001][4001];
bool good(int lin, int col)
{
    if(lin>=1 && lin<=n && col>=1 && col<=m)
        return 1;
    return 0;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            {cin>>mat[i][j];best[i][j]=4000*4000+100;}
    dqlin.push_back(1);
    dqcol.push_back(1);
    best[1][1]=1;
    int lin,col;
    while(dqlin.empty()==0)
    {
        lin=dqlin.front();
        col=dqcol.front();
        dqlin.pop_front();
        dqcol.pop_front();
        for(int i=0;i<4;i++)
        {
            if(good(lin+dirlin[i], col+dircol[i]) && best[lin][col]+(mat[lin][col]!=mat[lin+dirlin[i]][col+dircol[i]])<best[lin+dirlin[i]][col+dircol[i]])
            {
                best[lin+dirlin[i]][col+dircol[i]]=best[lin][col]+(mat[lin][col]!=mat[lin+dirlin[i]][col+dircol[i]]);
                if(mat[lin][col]!=mat[lin+dirlin[i]][col+dircol[i]])
                {
                    dqlin.push_back(lin+dirlin[i]);
                    dqcol.push_back(col+dircol[i]);
                }
                else
                {
                    dqlin.push_front(lin+dirlin[i]);
                    dqcol.push_front(col+dircol[i]);

                }
            }
        }
    }
    int mxm=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            mxm=max(mxm,best[i][j]);
    }
    cout<<mxm;
}

Subtask #1
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 5436 KB Output isn't correct
2 Incorrect 1 ms 448 KB Output isn't correct
3 Incorrect 1 ms 724 KB Output isn't correct
4 Correct 15 ms 5104 KB Output is correct
5 Incorrect 9 ms 3028 KB Output isn't correct
6 Incorrect 1 ms 444 KB Output isn't correct
7 Incorrect 1 ms 724 KB Output isn't correct
8 Correct 1 ms 724 KB Output is correct
9 Incorrect 2 ms 1108 KB Output isn't correct
10 Incorrect 7 ms 2772 KB Output isn't correct
11 Correct 5 ms 2052 KB Output is correct
12 Incorrect 11 ms 3020 KB Output isn't correct
13 Incorrect 9 ms 3028 KB Output isn't correct
14 Incorrect 8 ms 3032 KB Output isn't correct
15 Incorrect 25 ms 5840 KB Output isn't correct
16 Incorrect 24 ms 5328 KB Output isn't correct
17 Incorrect 24 ms 5228 KB Output isn't correct
18 Correct 16 ms 5080 KB Output is correct

Subtask #2
13.125 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 30944 KB Output isn't correct
2 Incorrect 136 ms 21484 KB Output isn't correct
3 Incorrect 1291 ms 137532 KB Output isn't correct
4 Incorrect 328 ms 34288 KB Output isn't correct
5 Incorrect 816 ms 105184 KB Output isn't correct
6 Correct 1398 ms 107872 KB Output is correct
7 Incorrect 17 ms 32340 KB Output isn't correct
8 Incorrect 18 ms 30932 KB Output isn't correct
9 Incorrect 6 ms 712 KB Output isn't correct
10 Incorrect 3 ms 596 KB Output isn't correct
11 Incorrect 18 ms 31828 KB Output isn't correct
12 Incorrect 3 ms 1620 KB Output isn't correct
13 Incorrect 143 ms 21528 KB Output isn't correct
14 Incorrect 83 ms 14264 KB Output isn't correct
15 Incorrect 99 ms 15452 KB Output isn't correct
16 Incorrect 58 ms 8112 KB Output isn't correct
17 Incorrect 344 ms 45884 KB Output isn't correct
18 Incorrect 405 ms 44904 KB Output isn't correct
19 Incorrect 326 ms 34240 KB Output isn't correct
20 Incorrect 286 ms 40504 KB Output isn't correct
21 Incorrect 774 ms 97592 KB Output isn't correct
22 Incorrect 753 ms 104964 KB Output isn't correct
23 Incorrect 646 ms 75808 KB Output isn't correct
24 Incorrect 747 ms 94392 KB Output isn't correct
25 Incorrect 1589 ms 132032 KB Output isn't correct
26 Correct 1014 ms 130936 KB Output is correct
27 Correct 1273 ms 121036 KB Output is correct
28 Correct 1371 ms 107764 KB Output is correct
29 Correct 1480 ms 106156 KB Output is correct
30 Correct 1461 ms 110304 KB Output is correct
31 Incorrect 1022 ms 73436 KB Output isn't correct
32 Incorrect 1407 ms 109728 KB Output isn't correct