Submission #82159

#	Time	Username	Problem	Language	Result	Execution time	Memory
82159		heon	Pohlepko (COCI16_pohlepko)	C++11	80 / 80	26 ms	19152 KiB

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 / 80