Submission #863768

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
863768	2023-10-21T02:53:16 Z	noobcodur	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	398 ms	115652 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(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	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	7 ms	1628 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	5 ms	1628 KB	Output is correct
5	Correct	1 ms	860 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	604 KB	Output is correct
9	Correct	0 ms	604 KB	Output is correct
10	Correct	1 ms	860 KB	Output is correct
11	Correct	1 ms	856 KB	Output is correct
12	Correct	3 ms	860 KB	Output is correct
13	Correct	1 ms	860 KB	Output is correct
14	Correct	1 ms	860 KB	Output is correct
15	Correct	6 ms	1864 KB	Output is correct
16	Correct	7 ms	1628 KB	Output is correct
17	Correct	5 ms	1628 KB	Output is correct
18	Correct	4 ms	1372 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	860 KB	Output is correct
2	Correct	24 ms	8384 KB	Output is correct
3	Correct	144 ms	81004 KB	Output is correct
4	Correct	37 ms	19032 KB	Output is correct
5	Correct	81 ms	45400 KB	Output is correct
6	Correct	395 ms	95008 KB	Output is correct
7	Correct	1 ms	856 KB	Output is correct
8	Correct	1 ms	860 KB	Output is correct
9	Correct	1 ms	668 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	860 KB	Output is correct
12	Correct	1 ms	600 KB	Output is correct
13	Correct	24 ms	8388 KB	Output is correct
14	Correct	14 ms	4952 KB	Output is correct
15	Correct	8 ms	5468 KB	Output is correct
16	Correct	14 ms	3796 KB	Output is correct
17	Correct	61 ms	20572 KB	Output is correct
18	Correct	41 ms	20312 KB	Output is correct
19	Correct	42 ms	19292 KB	Output is correct
20	Correct	33 ms	17752 KB	Output is correct
21	Correct	93 ms	47192 KB	Output is correct
22	Correct	81 ms	45644 KB	Output is correct
23	Correct	134 ms	39360 KB	Output is correct
24	Correct	80 ms	45912 KB	Output is correct
25	Correct	280 ms	80808 KB	Output is correct
26	Correct	214 ms	111972 KB	Output is correct
27	Correct	305 ms	115652 KB	Output is correct
28	Correct	394 ms	94924 KB	Output is correct
29	Correct	398 ms	92436 KB	Output is correct
30	Correct	351 ms	98508 KB	Output is correct
31	Correct	309 ms	52304 KB	Output is correct
32	Correct	269 ms	105228 KB	Output is correct