oj.uz

Submission #155880

# Submission time Handle Problem Language Result Execution time Memory
155880 2019-10-01T14:36:14 Z Breno_XD Maja (COCI18_maja) C++14
110 / 110
 1558 ms 936 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

const int MAXN = 110;
ll n,m,a,b,k;
ll matriz[MAXN][MAXN];

struct maybe{

	ll f;
	ll sf;

	bool operator > (const maybe &t){

		if(f!=t.f) return f > t.f;
		else return sf >= t.sf;

		//XD

	}

}dp[MAXN][MAXN][2];

void solve(){

	//Vamos fazer uma dp iterativa HUEHUE

	int mod = 0;

	for(int p=1; p<=min(k,(ll)10000); p++){ //Atual número de passoa

		mod^=1;	

		for(int i=1; i<=n; i++){

			for(int j=1; j<=m; j++){

				//Para cada elemento da célula, em cada passo, vamos verificar o que vale mais a pena
				//O que eu sei para construir a resposta atual é o passo anterior, ou seja, p-1 ... E pelo
				//fato da DP depender apenas disso eu posso usar memory trick :P

				//O que vale mais a pena pegar?
				//A melhor resposta do dos meus vizinhos em p-1, e a melhor resposa é exatamente a comparação feita com
				//o operator modificado para a struct maybe

				maybe up = dp[i-1][j][mod^1];
				maybe down = dp[i+1][j][mod^1];
				maybe left = dp[i][j-1][mod^1];
				maybe right = dp[i][j+1][mod^1];

				//Caso o meu vizinho de cima seja a minha resposta
				if(up > down && up > left && up > right){
					
					//Atualizo o valor f
					dp[i][j][mod] = up;

					//Se valer a pena atualizo o valor sf
					dp[i][j][mod].sf = max(up.sf, matriz[i][j] + matriz[i-1][j]);

				}

				//Caso o meu vizinho de baixo seja a minha resposta
				if(down > up && down > left && down > right){
					
					//Atualizo o valor f
					dp[i][j][mod] = down;

					//Se valer a pena atualizo o valor sf
					dp[i][j][mod].sf = max(down.sf, matriz[i][j] + matriz[i+1][j]);

				}

				//Caso o meu vizinho da esquerda seja a minha resposta
				if(left > down && left > up && left > right){
					
					//Atualizo o valor f
					dp[i][j][mod] = left;

					//Se valer a pena atualizo o valor sf
					dp[i][j][mod].sf = max(left.sf, matriz[i][j] + matriz[i][j-1]);

				}

				//Caso o meu vizinho da direita seja a minha resposta
				if(right > down && right > left && right > up){
					
					//Atualizo o valor f
					dp[i][j][mod] = right;

					//Se valer a pena atualizo o valor sf
					dp[i][j][mod].sf = max(right.sf, matriz[i][j] + matriz[i][j+1]);

				}

				if(dp[i][j][mod].f != -1)  dp[i][j][mod].f += matriz[i][j];

			}


		}

	}

}

int main(){

	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	for(int i=0; i<MAXN; i++)
		for(int j=0; j<MAXN; j++)
			for(int k=0; k<2; k++)
				dp[i][j][k].f = dp[i][j][k].sf = -1;

	cin >> n >> m >> a >> b >> k;

	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			cin >> matriz[i][j];

	dp[a][b][0].f = 0;

	solve();

	if(k <= 10000) cout << dp[a][b][0].f << "\n";
	else cout << dp[a][b][0].f + (dp[a][b][0].sf * (k - 10000))/2 << "\n";

	return 0;

}

Subtask #1
11.0 / 11.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 772 KB Output is correct
2 Correct 17 ms 760 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 760 KB Output is correct
2 Correct 20 ms 892 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 760 KB Output is correct
2 Correct 9 ms 760 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 760 KB Output is correct
2 Correct 25 ms 760 KB Output is correct
3 Correct 1558 ms 912 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 760 KB Output is correct
2 Correct 1073 ms 892 KB Output is correct
3 Correct 1548 ms 936 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 988 ms 896 KB Output is correct
2 Correct 1362 ms 908 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 760 KB Output is correct
2 Correct 300 ms 844 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 760 KB Output is correct
2 Correct 58 ms 804 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 764 KB Output is correct
2 Correct 101 ms 760 KB Output is correct