Submission #863765

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
863765	2023-10-21T02:48:48 Z	noobcodur	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	613 ms	143652 KB

tracks

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define ld long double
#define forn(i,j) for(ll i = 0; i < j; i++)
#define forrange(i,j,k) for(int i = j; i < k; ++i)
#define rof(i,j) rof(int i = j; i >= 0; --i)
#define pii pair<int,int>
#define vll vector<ll>
#define vi vector<int>
#define vvll vector<vll>
#define vvi vector<vi>
#define pb push_back
#define p push
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define debug(x) cerr << #x << " is " << x << endl;

#define MOD 1000000007

const int N = 4e3;

string grid[N];

int cost(pii a, pii b){
	if(grid[a.f][a.s] != grid[b.f][b.s]){
		return 1;
	}

	else{
		return 0;
	}
}

int main(){

	int dx[] = {1,0,-1,0};
	int dy[] = {0,1,0,-1};
	int h,w;
	cin >> h >> w;

	vvi dp(h, vi(w, 0));

	forn(i,h){
		cin >> grid[i];
	}

	deque<pii> s;
	dp[0][0] = 1;
	s.push_back({0,0});
	int mx = 0;

	while(!s.empty()){
		pii k = s.front();
		s.pop_front();
		mx = max(dp[k.f][k.s], mx);

		forn(i,4){
			int m = k.f + dx[i];
			int n = k.s + dy[i];
			pii g = {m,n};

			if((m < 0 || n < 0 || m >= h || n >= w) || grid[m][n] == '.' || dp[m][n] != 0){
				continue;
			}

			else{
				if(cost(g,k) == 1){
					dp[m][n] = dp[k.f][k.s] + 1;
					s.push_back(g);
				}

				else{
					dp[m][n] = dp[k.f][k.s];
					s.push_front(g);
				}
			}
		}
	}

	cout << mx << endl;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	2136 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	560 KB	Output is correct
4	Correct	9 ms	1628 KB	Output is correct
5	Correct	4 ms	1116 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	2 ms	860 KB	Output is correct
11	Correct	2 ms	860 KB	Output is correct
12	Correct	4 ms	1112 KB	Output is correct
13	Correct	4 ms	1116 KB	Output is correct
14	Correct	4 ms	1116 KB	Output is correct
15	Correct	14 ms	2084 KB	Output is correct
16	Correct	10 ms	2140 KB	Output is correct
17	Correct	8 ms	2140 KB	Output is correct
18	Correct	8 ms	1596 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	860 KB	Output is correct
2	Correct	44 ms	10604 KB	Output is correct
3	Correct	350 ms	109036 KB	Output is correct
4	Correct	85 ms	26072 KB	Output is correct
5	Correct	189 ms	56240 KB	Output is correct
6	Correct	613 ms	122932 KB	Output is correct
7	Correct	2 ms	856 KB	Output is correct
8	Correct	2 ms	860 KB	Output is correct
9	Correct	2 ms	968 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	2 ms	860 KB	Output is correct
12	Correct	1 ms	712 KB	Output is correct
13	Correct	45 ms	10580 KB	Output is correct
14	Correct	26 ms	6492 KB	Output is correct
15	Correct	21 ms	7260 KB	Output is correct
16	Correct	20 ms	4440 KB	Output is correct
17	Correct	114 ms	27860 KB	Output is correct
18	Correct	89 ms	27488 KB	Output is correct
19	Correct	88 ms	26308 KB	Output is correct
20	Correct	103 ms	23888 KB	Output is correct
21	Correct	189 ms	57812 KB	Output is correct
22	Correct	187 ms	56144 KB	Output is correct
23	Correct	217 ms	47780 KB	Output is correct
24	Correct	185 ms	56660 KB	Output is correct
25	Correct	474 ms	109072 KB	Output is correct
26	Correct	366 ms	123740 KB	Output is correct
27	Correct	517 ms	143652 KB	Output is correct
28	Correct	595 ms	123364 KB	Output is correct
29	Correct	598 ms	120624 KB	Output is correct
30	Correct	539 ms	125900 KB	Output is correct
31	Correct	428 ms	63516 KB	Output is correct
32	Correct	467 ms	133384 KB	Output is correct