Submission #621436

#	Time	Username	Problem	Language	Result	Execution time	Memory
621436		353cerega	Tracks in the Snow (BOI13_tracks)	C++17	19.79 / 100	1045 ms	180656 KiB

tracks

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>


using namespace std;


using ll = long long;
using ld = long double;

#define X first
#define Y second

//const ll mod = 1000000007;
const ll mod = 998244353;


int dp[4001][4001];

void solve()
{
    ll n, m;
    cin >> n >> m;
    vector<string> s(n);
    for (int i=0;i<n;i++) cin >> s[i];
    deque<int> Q;
    Q.push_back(0);
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<m;j++) dp[i][j] = mod;
    }
    dp[0][0] = 0;
    vector<int> was(n*m);
    vector<int> dx = {1,-1,0,0};
    vector<int> dy = {0,0,1,-1};
    while (Q.size()>0)
    {
        int p = Q.front();
        Q.pop_front();
        if (was[p]==1) continue;
        was[p] = 1;
        int x = p/m;
        int y = p-m*x;
        for (int d=0;d<4;d++)
        {
            int x2 = x+dx[d];
            int y2 = y+dy[d];
            if (x2>=n or x2<0 or y2>=m or y2<0) continue;
            int W = dp[x][y];
            int F = 0;
            if (s[x][y]!=s[x2][y2]) F = 1;
            if (dp[x2][y2]>W+F)
            {
                dp[x2][y2] = W+F;
                if (F==0) Q.push_front(x2*m+y2);
                else Q.push_back(x2*m+y2);
            }
        }
    }
    int A = 0;
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<m;j++)
        {
            if (dp[i][j]<mod) A = max(A,dp[i][j]);
        }
    }
    cout << A+1 << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    ll T;
    T = 1;
    //cin >> T;
    while (T--) solve();
}

• Subtask 1: 6.666666666666667 / 30
• Subtask 2: 13.125 / 70