oj.uz

Submission #632615

# Submission time Handle Problem Language Result Execution time Memory
632615 2022-08-20T12:40:10 Z VasLemmy Tracks in the Snow (BOI13_tracks) C++17
2.1875 / 100
 633 ms 96228 KB 
#include<bits/stdc++.h>
//#define int long long
#define pii pair<int,ll>
#define fi first
#define se second
/*#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")*/
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ldb = long double;
const ll N = (int)1e6;
const int maxN = (int)3e5 + 5;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const ll infty = 1e18 + 7;
const int base = (int)4e5;
const int Block_size = 350;

void InputFile()
{
    //freopen("threesum.in","r",stdin);
    //freopen("threesum.out","w",stdout);
    //freopen("test.out","r",stdin);
}

void FastInput()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

int n,m;
char a[4005][4005];
int dp[4005][4005];

void Read()
{
    cin >> m >> n;
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cin >> a[i][j];
            //dp[i][j] = mod;
        }
    }

    deque<pii>  q;
    dp[1][1] = 1;
    q.push_back({1,1});
    int res = 0;
    do
    {
        pii u = q.front();
        res = max(res,dp[u.fi][u.se]);
        q.pop_front();
        pii v = {u.fi,u.se+1};
        if(v.fi <= m && v.se <= n && a[v.fi][v.se] != '.')
        {
            if(!dp[v.fi][v.se])
            {
                dp[v.fi][v.se] = dp[u.fi][u.se] + (a[u.fi][u.se] != a[v.fi][v.se]);
                if(a[u.fi][u.se] != a[v.fi][v.se]) q.push_back(v);
                else q.push_front(v);
            }
        }

        v = {u.fi+1,u.se};
        if(v.fi <= m && v.se <= n && a[v.fi][v.se] != '.')
        {
            if(!dp[v.fi][v.se])
            {
                dp[v.fi][v.se] = dp[u.fi][u.se] + (a[u.fi][u.se] != a[v.fi][v.se]);
                if(a[u.fi][u.se] != a[v.fi][v.se]) q.push_back(v);
                else q.push_front(v);
            }
        }
    }
    while(!q.empty());

    cout << res;
    /*for(int i = 1;i <= m;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            cout << dp[i][j] <<' ';
        }
        cout <<'\n';
    }*/
}

void Solve()
{

}

void Debug()
{

}


int32_t main()
{
    FastInput();
    //InputFile();
    //int sub_type;
    //cin >> sub_type;
    //Sieve()
    int test;
    //cin >> test;
    test = 1;
    while(test--)
    {
        Read();
        Solve();
        //Debug();
    }
}
////
/////
//////

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 5336 KB Output isn't correct
2 Incorrect 1 ms 460 KB Output isn't correct
3 Incorrect 1 ms 724 KB Output isn't correct
4 Incorrect 7 ms 5028 KB Output isn't correct
5 Incorrect 3 ms 2772 KB Output isn't correct
6 Incorrect 1 ms 468 KB Output isn't correct
7 Incorrect 1 ms 712 KB Output isn't correct
8 Incorrect 1 ms 716 KB Output isn't correct
9 Incorrect 1 ms 1108 KB Output isn't correct
10 Incorrect 2 ms 2440 KB Output isn't correct
11 Incorrect 3 ms 2132 KB Output isn't correct
12 Incorrect 4 ms 3028 KB Output isn't correct
13 Incorrect 3 ms 2772 KB Output isn't correct
14 Incorrect 3 ms 2772 KB Output isn't correct
15 Incorrect 9 ms 4936 KB Output isn't correct
16 Incorrect 10 ms 5332 KB Output isn't correct
17 Incorrect 8 ms 4948 KB Output isn't correct
18 Incorrect 7 ms 4948 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 30724 KB Output isn't correct
2 Incorrect 30 ms 13092 KB Output isn't correct
3 Incorrect 211 ms 47720 KB Output isn't correct
4 Incorrect 71 ms 29856 KB Output isn't correct
5 Incorrect 129 ms 32852 KB Output isn't correct
6 Incorrect 565 ms 96020 KB Output isn't correct
7 Incorrect 21 ms 32096 KB Output isn't correct
8 Incorrect 15 ms 30676 KB Output isn't correct
9 Incorrect 2 ms 596 KB Output isn't correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Incorrect 18 ms 31444 KB Output isn't correct
12 Incorrect 2 ms 1492 KB Output isn't correct
13 Incorrect 30 ms 13060 KB Output isn't correct
14 Incorrect 20 ms 9240 KB Output isn't correct
15 Incorrect 21 ms 9156 KB Output isn't correct
16 Incorrect 14 ms 4820 KB Output isn't correct
17 Incorrect 75 ms 23936 KB Output isn't correct
18 Incorrect 77 ms 20140 KB Output isn't correct
19 Incorrect 87 ms 29820 KB Output isn't correct
20 Incorrect 51 ms 17552 KB Output isn't correct
21 Incorrect 126 ms 34036 KB Output isn't correct
22 Incorrect 121 ms 32956 KB Output isn't correct
23 Incorrect 147 ms 34140 KB Output isn't correct
24 Incorrect 166 ms 33976 KB Output isn't correct
25 Incorrect 213 ms 47748 KB Output isn't correct
26 Correct 404 ms 80852 KB Output is correct
27 Incorrect 532 ms 95892 KB Output isn't correct
28 Incorrect 633 ms 96008 KB Output isn't correct
29 Incorrect 620 ms 96228 KB Output isn't correct
30 Incorrect 545 ms 94324 KB Output isn't correct
31 Incorrect 436 ms 73264 KB Output isn't correct
32 Incorrect 395 ms 89652 KB Output isn't correct