Contest Duration: - (local time) (100 minutes) Back to Home

## F - Treasure Hunting Editorial by en_translator

Assume that the $$K$$-th largest integer is some fixed $$X$$.

Use DP (Dynamic Programming) to find for each square the minimum sum of integers greater than or equal to $$X$$ if he passes through exactly $$k$$ squares when traveling from the initial square to that square.

A set of DP requires an $$O(HWK)$$ time, so the overall time complexity is $$O(H^2W^2K)$$.

Be careful of the case where there are multiple squares written $$X$$.

Sample code (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < n; i++)
void chmin(ll&a,ll b){if(a>b)a=b;}
const ll inf = 1001001001001001001;

int main(){
int h, w, K; cin >> h >> w >> K;
vector<vector<int>> grid(h, vector<int>(w));
rep(i, h) rep(j, w) cin >> grid[i][j];
ll ans = inf;
for(auto y : grid) for(auto x : y) {
vector<vector<vector<ll>>> dp(K + 1, vector<vector<ll>>(h, vector<ll>(w, inf)));
if(grid[0][0] >= x) dp[1][0][0] = grid[0][0];
if(grid[0][0] <= x) dp[0][0][0] = 0;
rep(i, K + 1) rep(j, h) rep(k, w) {
if(j != h - 1){
if(i != K && grid[j + 1][k] >= x) chmin(dp[i + 1][j + 1][k], dp[i][j][k] + grid[j + 1][k]);
if(grid[j + 1][k] <= x) chmin(dp[i][j + 1][k], dp[i][j][k]);
}
if(k != w - 1){
if(i != K && grid[j][k + 1] >= x) chmin(dp[i + 1][j][k + 1], dp[i][j][k] + grid[j][k + 1]);
if(grid[j][k + 1] <= x) chmin(dp[i][j][k + 1], dp[i][j][k]);
}
}
chmin(ans, dp[K][h - 1][w - 1]);
}
cout << ans << endl;
}


bonus: $$O(H^2W^2)$$

posted:
last update: