oj.uz

답안 #344199

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
344199 2021-01-05T09:00:48 Z ak2006 Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 930 ms 110844 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
const ll mod = 1e9 + 7,inf = 1e18;
const vi dx = {1,-1,0,0},dy = {0,0,1,-1};
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int main()
{
    fast;
    int w,h;
    cin>>w>>h;
    vvc g(w,vc(h));
    for (int i = 0;i<w;i++)for (int j = 0;j<h;j++)cin>>g[i][j];
    vvi dp(w,vi(h,1e9));
    dp[0][0] = 0;
    deque<pair<int,int>>q;
    q.push_back({0,0});
    int ans = 0;
    while (!q.empty()){
        int ci = q.front().first,cj = q.front().second;
        q.pop_front();
        for (int x = 0;x<4;x++){
            int ni = ci + dx[x],nj = cj + dy[x];
            if (ni < 0 || nj < 0 || ni >= w || nj >= h || g[ni][nj] == '.')continue;
            int cost = (g[ci][cj] == g[ni][nj] ? 0 : 1);
            if (dp[ni][nj] <= dp[ci][cj] + cost)continue;
            dp[ni][nj] = dp[ci][cj] + cost;
            if (cost == 0)q.push_front({ni,nj});
            else q.push_back({ni,nj});
            ans = max(ans,dp[ni][nj]);
        }
    }
    cout<<ans + 1;
    return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 1644 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 9 ms 1388 KB Output is correct
5 Correct 3 ms 748 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 3 ms 620 KB Output is correct
11 Correct 3 ms 620 KB Output is correct
12 Correct 7 ms 876 KB Output is correct
13 Correct 3 ms 748 KB Output is correct
14 Correct 3 ms 748 KB Output is correct
15 Correct 14 ms 1644 KB Output is correct
16 Correct 15 ms 1676 KB Output is correct
17 Correct 11 ms 1516 KB Output is correct
18 Correct 9 ms 1388 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 876 KB Output is correct
2 Correct 61 ms 8044 KB Output is correct
3 Correct 442 ms 78956 KB Output is correct
4 Correct 116 ms 18796 KB Output is correct
5 Correct 360 ms 44524 KB Output is correct
6 Correct 928 ms 92536 KB Output is correct
7 Correct 2 ms 876 KB Output is correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 3 ms 620 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 2 ms 876 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 62 ms 8044 KB Output is correct
14 Correct 35 ms 4844 KB Output is correct
15 Correct 31 ms 5228 KB Output is correct
16 Correct 28 ms 3692 KB Output is correct
17 Correct 164 ms 20332 KB Output is correct
18 Correct 132 ms 20076 KB Output is correct
19 Correct 129 ms 18892 KB Output is correct
20 Correct 99 ms 17260 KB Output is correct
21 Correct 255 ms 46188 KB Output is correct
22 Correct 298 ms 44524 KB Output is correct
23 Correct 325 ms 38552 KB Output is correct
24 Correct 251 ms 45036 KB Output is correct
25 Correct 655 ms 79084 KB Output is correct
26 Correct 661 ms 110844 KB Output is correct
27 Correct 836 ms 105500 KB Output is correct
28 Correct 926 ms 92664 KB Output is correct
29 Correct 930 ms 91108 KB Output is correct
30 Correct 854 ms 95124 KB Output is correct
31 Correct 729 ms 51308 KB Output is correct
32 Correct 720 ms 94372 KB Output is correct