Submission #386435

#TimeUsernameProblemLanguageResultExecution timeMemory
386435TrunktyOrchard (NOI14_orchard)C++14
25 / 25
190 ms14060 KiB
#include <iostream>
#include <vector>
using namespace std;
int r,c,maxi=-1e9,x1,x2,y1,y2;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> r >> c;
	int arr[r+1][c+1];
    int prearr[r+1][c+1];
    for(int j=1;j<=c;j++){
    	prearr[0][j] = 0;
	}
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin >> arr[i][j];
			if(arr[i][j]==0){
				arr[i][j] = -1;
			}
			prearr[i][j] = prearr[i-1][j]+arr[i][j];
		}
	}
	for(int i=1;i<=r;i++){
		for(int j=i;j<=r;j++){
			int mini=0,totsum=0,pos=-1;
			for(int k=1;k<=c;k++){
				totsum += prearr[j][k]-prearr[i-1][k];
				if(totsum-mini>maxi){
					maxi = totsum-mini;
					x1 = i;
					x2 = j;
					y1 = pos+1;
					y2 = k;
				}
				if(totsum<mini){
					mini = totsum;
					pos = k;
				}
			}
		}
	}
	int cnt=0;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			if(i>=x1 and i<=x2 and j>=y1 and j<=y2){
				if(arr[i][j]==-1){
					cnt++;
				}
			}
			else{
				if(arr[i][j]==1){
					cnt++;
				}
			}
		}
	}
	cout << cnt;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...