Submission #96818

#	Time	Username	Problem	Language	Result	Execution time	Memory
96818		ami	Maja (COCI18_maja)	C++14	110 / 110	891 ms	640 KiB

maja

#include <bits/stdc++.h>
#define sz(c)      int(c.size())
#define rep(i,a,b) for (int i=a; i<(b); ++i)
#define per(i,a,b) for (int i=(b)-1; i>=(a); --i)
using namespace std;
using ll = long long;

int const MAXN=110;
int N,M,A,B,K;
int C[MAXN][MAXN];
ll f[2][MAXN][MAXN];

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(10);

	cin>>N>>M>>A>>B>>K;
	A--, B--;
	rep(i,0,N) rep(j,0,M) cin>>C[i][j];

	rep(x,0,N) rep(y,0,M) f[0][x][y]=-1;
	f[0][A][B]=0;

	int L=4*max(N,M)*max(N,M);
	//int L=100000;
	if (L%2!=0) L++;

	ll last=0;
	rep(k,0,min(K,L)) {
		auto curr=f[k%2];
		auto next=f[!(k%2)];

		rep(x,0,N) rep(y,0,M) next[x][y]=-1;

		rep(x,0,N) rep(y,0,M) if (curr[x][y]!=-1) {
			if (x-1>=0) next[x-1][y]=max(next[x-1][y],curr[x][y]+C[x-1][y]);
			if (x+1<N)  next[x+1][y]=max(next[x+1][y],curr[x][y]+C[x+1][y]);
			if (y-1>=0) next[x][y-1]=max(next[x][y-1],curr[x][y]+C[x][y-1]);
			if (y+1<M)  next[x][y+1]=max(next[x][y+1],curr[x][y]+C[x][y+1]);
		}

		if (curr[A][B]!=-1) last=curr[A][B];
	}

	ll res=f[0][A][B];
	if (K>L) {
		res+=(f[0][A][B]-last)*(K-L)/2;
	}

	cout<<res<<"\n";
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11