oj.uz

Submission #330182

# Submission time Handle Problem Language Result Execution time Memory
330182 2020-11-24T06:07:41 Z oak Collecting Mushrooms (NOI18_collectmushrooms) C++14
0 / 100
 2000 ms 219756 KB 
#include<bits/stdc++.h>
using namespace std;
int fw[500002];
void upd(int po,int val){
	for(;po<=500000;po+=(po&-po)){
		fw[po]+=val;
	}
}
int qry(int po){
	int ret = 0;
	for(;po>0;po-=(po&-po)){
		ret += fw[po];
	}
	return ret;
}
int main(){
	int n,m,i,j,d,k;
	scanf("%d %d %d %d",&n,&m,&d,&k);
	char inp[m+1];
	int sum[n+2][m+2];
	memset(sum,0,sizeof sum);
	vector<int> mr[n+1];
	for(i=1;i<=n;i++){
		scanf("%s",inp+1);
		for(j=1;j<=m;j++){
			if(inp[j] == 'S'){
				sum[max(1,i-d)][max(1,j-d)] += 1;
				sum[max(1,i-d)][min(m,j+d)+1] -= 1;
				sum[min(n,i+d)+1][max(1,j+d)] -= 1;
				sum[min(n,i+d)+1][min(m,j+d)+1] += 1;
			}else if(inp[j] == 'M'){
				mr[i].push_back(j);
			}
		}
	}
	int ans = 0;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(sum[i][j]){
				//printf("Upd (%d,%d) : %d\n",i,j,sum[i][j]);
				upd(j,sum[i][j]);
			}
		}
		for(auto x: mr[i]){
			int test = qry(x);
			//printf("test (%d,%d) : %d\n",i,x,test);
			if(test >= k)ans++;
		}
	}
	printf("%d",ans);
}

Compilation message

mushrooms.cpp: In function 'int main()':
mushrooms.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |  scanf("%d %d %d %d",&n,&m,&d,&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
mushrooms.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |   scanf("%s",inp+1);
      |   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2231 ms 219756 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2231 ms 219756 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 2284 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 15200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2231 ms 219756 KB Time limit exceeded
2 Halted 0 ms 0 KB -