Submission #19735515

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll dp[3001][3001][4];
ll values[3000][3000];
int main()
{
  int r, c, k;
  cin >> r >> c >> k;
  for (int i=0; i<k; i++){
    int r, c, v;
    cin >> r >> c >> v; r--; c--;
    values[r][c] = v;
  }
  for (int y=1; y<=r; y++){
    for (int x=1; x<=c; x++){
      ll val=values[y-1][x-1];
      ll upv = 0;
      for (int j=0; j<=3; j++){
	upv = max(upv, dp[y-1][x][j]);
      }
      // get an item here
      if (val > 0){
	for (int j=1; j<=3; j++){
	  dp[y][x][j] = val + max(upv, dp[y][x-1][j-1]);
	}
      }
      // don't get an item here
      for (int j=0; j<=3; j++){
	ll t = max(upv, dp[y][x-1][j]);
	dp[y][x][j] = max(dp[y][x][j], t);
      }
    }
  }
  ll ans = 0;
  for (int i=0; i<=3; i++){
    ans = max(ans, dp[r][c][i]);
  }
  cout << ans << endl;
  return 0;
}

Submission Info

Judge Result