Submission #5279

#	Time	Username	Problem	Language	Result	Execution time	Memory
5279		ainta	Orchard (NOI14_orchard)	C++98	25 / 25	248 ms	19688 KiB

orchard

#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 / 4
• Subtask 2: 4 / 4
• Subtask 3: 5 / 5
• Subtask 4: 3 / 3
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5