oj.uz

Submission #5279

# Submission time Handle Problem Language Result Execution time Memory
5279 2014-03-15T11:16:24 Z ainta Orchard (NOI14_orchard) C++
25 / 25
 248 ms 19688 KB 
#pragma warning(disable:4996)
#include<stdio.h>
int w[3][1000010], P[1000010];
int p[152][5010];
int n, m, M, C;
void Do()
{
	int i, Mn = 999999999;
	for (i = 0; i <= m; i++){
		if (M < P[i] - Mn)M = P[i] - Mn;
		if (Mn > P[i])Mn = P[i];
	}
}
void Do1(){
	int i, j, k;
	for (i = 1; i <= n; i++){
		for (j = 1; j <= m; j++){
			scanf("%d", &w[i][j]);
			if (!w[i][j])w[i][j] = -1;
			else C++;
			w[i][j] += w[i - 1][j] + w[i][j - 1] - w[i - 1][j - 1];
		}
	}
	for (i = 0; i < n; i++){
		for (j = i + 1; j <= n; j++){
			for (k = 0; k <= m; k++)P[k] = w[j][k] - w[i][k];
			Do();
		}
	}
}
void Do2(){
	int i, j, k;
	for (i = 1; i <= n; i++){
		for (j = 1; j <= m; j++){
			scanf("%d", &p[i][j]);
			if (!p[i][j])p[i][j] = -1;
			else C++;
			p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
		}
	}
	for (i = 0; i < n; i++){
		for (j = i + 1; j <= n; j++){
			for (k = 0; k <= m; k++)P[k] = p[j][k] - p[i][k];
			Do();
		}
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	if (n <= 2)Do1();
	else Do2();
	printf("%d\n", C - M);
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 19688 KB Output is correct
2 Correct 108 ms 19688 KB Output is correct
3 Correct 116 ms 19688 KB Output is correct

Subtask #4
3.0 / 3.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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