oj.uz

Submission #386435

# Submission time Handle Problem Language Result Execution time Memory
386435 2021-04-06T14:19:59 Z Trunkty Orchard (NOI14_orchard) C++14
25 / 25
 190 ms 14060 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 14060 KB Output is correct
2 Correct 86 ms 14060 KB Output is correct
3 Correct 78 ms 14060 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2668 KB Output is correct
2 Correct 16 ms 2668 KB Output is correct
3 Correct 16 ms 2668 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 364 KB Output is correct
2 Correct 7 ms 492 KB Output is correct
3 Correct 7 ms 492 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 7660 KB Output is correct
2 Correct 185 ms 7788 KB Output is correct
3 Correct 190 ms 7788 KB Output is correct