Submission #572696

#	Time	Username	Problem	Language	Result	Execution time	Memory
572696		Devigo	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	79 / 100	2066 ms	5460 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair

const int siz = 0;
const int mod = 0;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int r, c, d, k;
	cin >> r >> c >> d >> k;
	vector<string> v(r);
	for(int i=0; i<r; i++) {
		cin >> v[i];
	}
	if(r == 1) {
		vector<int> ps(c+1,0);
		for(int i=1; i<=c; i++) {
			ps[i] = ps[i-1];
			if(v[0][i-1] == 'S') ps[i]++;
		}
		//for(int i=0; i<=c; i++) {
		//	cout << ps[i] << " ";
		//}
		cout << endl;
		int cnt = 0;
		for(int i=0; i<c; i++) {
			if(v[0][i] == 'M') {
				int mi = max(1,(i+1-d));
				int ma = min(c,(i+1+d));
				int cn = (ps[i]-ps[mi-1]) + (ps[ma]-ps[i]);
				if(cn >= k) cnt++;
			}
		}
		cout << cnt << "\n"; return 0;
	}
	//for(int i=0; i<r; i++) {
	//	for(int j=0; j<c; j++) {
	//		cout << v[i][j] << " ";
	//	}
	//	cout << "\n";
	//}
	vector<vector<int>> cnt(r,vector<int>(c,0));
	for(int i=0; i<r; i++) {
		for(int j=0; j<c; j++) {
			if(v[i][j] == 'S') {
				int x,y,z,e; //cout << "c\n";
				x = max(0,i-d);
				y = max(0,j-d);
				z = min(r-1,i+d);
				e = min(c-1,j+d);
				for(int sp=x; sp<=z; sp++) {
					for(int ep=y; ep<=e; ep++) {
						cnt[sp][ep]++;
					}
				}
			}
		}
	}
	//for(int i=0; i<r; i++) {
	//	for(int j=0; j<c; j++) {
	//		cout << cnt[i][j] << " ";
	//	}
	//	cout << endl;
	//}
	int cn = 0;
	for(int i=0; i<r; i++) {
		for(int j=0; j<c; j++) {
			if(v[i][j] == 'M' && cnt[i][j] >= k) cn++;
		}
	}
	cout << cn << "\n";
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 23 / 23
• Subtask 5: 19 / 19
• Subtask 6: 0 / 21