oj.uz

Submission #96818

# Submission time Handle Problem Language Result Execution time Memory
96818 2019-02-12T09:07:09 Z ami Maja (COCI18_maja) C++14
110 / 110
 891 ms 640 KB 
#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.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
11.0 / 11.0

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

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 460 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 325 ms 640 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 384 KB Output is correct
2 Correct 445 ms 640 KB Output is correct
3 Correct 319 ms 608 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 608 KB Output is correct
2 Correct 891 ms 632 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 504 KB Output is correct
2 Correct 153 ms 512 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 384 KB Output is correct
2 Correct 13 ms 384 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct