Submission #386435

#	Time	Username	Problem	Language	Result	Execution time	Memory
386435		Trunkty	Orchard (NOI14_orchard)	C++14	25 / 25	190 ms	14060 KiB

orchard

#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;
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 5 / 5
• Subtask 4: 3 / 3
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5