Submission #82159

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
82159	2018-10-29T10:11:31 Z	heon	Pohlepko (COCI16_pohlepko)	C++11	80 / 80	26 ms	19152 KB

pohlepko

#include<bits/stdc++.h>

using namespace std;

const int dx[] = {1, 0};
const int dy[] = {0, 1};

bool bio[2002][2002];

int main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
  
	int n,m;
	cin >> n >> m;
	vector <string> s(n);
	for(int i = 0; i < n; i++) cin >> s[i];
	vector <pair<int,int>> q;
	q.push_back(make_pair(0,0));
	bio[0][0] = 1;
	string sol;
	while(!q.empty()){
		cout << s[q.back().first][q.back().second];
		vector <pair<int,int>> next;
		char mn = 'z';
		for(auto x : q){
			for(int i = 0; i < 2; i++){
				int nx = dx[i] + x.first;
				int ny = dy[i] + x.second;
				if(nx >= n || ny >= m) continue;
				mn = min(mn, s[nx][ny]);
			}
		}
		for(auto x : q){
			for(int i = 0; i < 2; i++){
				int nx = dx[i] + x.first;
				int ny = dy[i] + x.second;
				if(nx >= n || ny >= m || s[nx][ny] != mn || bio[nx][ny]) continue;
				next.push_back(make_pair(nx,ny));
				bio[nx][ny] = 1;
			}
		}
		q = next;
	}
}

Subtask #1

80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	1492 KB	Output is correct
3	Correct	2 ms	1492 KB	Output is correct
4	Correct	2 ms	1492 KB	Output is correct
5	Correct	3 ms	1492 KB	Output is correct
6	Correct	4 ms	1712 KB	Output is correct
7	Correct	9 ms	6232 KB	Output is correct
8	Correct	16 ms	14328 KB	Output is correct
9	Correct	2 ms	14328 KB	Output is correct
10	Correct	3 ms	14328 KB	Output is correct
11	Correct	3 ms	14328 KB	Output is correct
12	Correct	6 ms	14328 KB	Output is correct
13	Correct	9 ms	14328 KB	Output is correct
14	Correct	17 ms	19152 KB	Output is correct
15	Correct	3 ms	19152 KB	Output is correct
16	Correct	26 ms	19152 KB	Output is correct