#include <stdio.h>

//VSTUP:
#define M 4
#define N 4
int dobre[M][N], spatne[M][N];

// nultý sloupec je vždy 0 (pro usnadnění)
int d[M][N+1]; // rozdíly počtu dobrých a špatných
int s[M][N+1]; // částečné součty
int o[M][N+1]; // optima

int k[M][N+1]; // pro zjištění tvaru výsledné dělící cesty si pamatuji, 
               // kde pokračovala o řádek výše pro všechna její pokračování tady
int nazapad[M+1]; // kolik cest nakonec kde vede na Z

int main() {
	int i,j,max;
	//VSTUP - neřeším
	for(i=0;i<M;i++) {                        	//spočtu rozdíly a částečné součty
		d[i][0]=s[i][0]=o[i][0]=k[i][0]=0;
		for(j=1;j<=N;j++) {
			d[i][j]=dobre[i][j-1]-spatne[i][j-1];
			s[i][j]=s[i][j-1]+d[i][j];
		}
	}

	for(j=0;j<=N;j++) o[0][j]=s[0][j]; 	        // první řádek
	for(i=1;i<M;i++) {                             	// a ty další
		max=0;                                  // pozice maxima
		for(j=1;j<=N;j++) {
			if(o[i-1][max]<o[i-1][j]) max=j;
			o[i][j]=s[i][j]+o[i-1][max];
			k[i][j]=max;
		}
	}

	max=0;
	for(j=1;j<=N;j++) if(o[M-1][max]<o[M-1][j]) max=j;
	// nyní mám v max optimální konec cesty, z něj, zpětně zjistím, kudy optimálně vedla
	nazapad[M-1]=max;
	for(i=M-2;i>=0;i--) nazapad[i]=k[i+1][nazapad[i+1]];

	max=0;                                         	// a ještě výpis
	for(i=0;i<M;i++) {
		for(j=0;j<nazapad[i];j++) {
			max+=dobre[i][j];
			printf("-");
		}
		for(;j<N;j++){
			max+=spatne[i][j];
			printf("|");
		}
		printf("\n");
	}
	printf("Vydoluje se %d zpráv\n",max);
	return 0;
}