Submission #1196286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196286		h1440	Raisins (IOI09_raisins)	C++20	100 / 100	650 ms	34744 KiB

raisins

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fore(i,a,b) for(lli i = (a), abcdxd = (b); i < abcdxd; i++)
#define f first
#define s second
#define ENDL '\n'
#define pb push_back
#define sz(s) lli((s).size())
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
using namespace std;
typedef long long lli;
// typedef long long LLI;
typedef pair<lli,lli> ii;
typedef vector<lli> vi;
typedef vector<ii> vii;
typedef long double ld;
#define deb(x) cout << #x << ": " << x << endl;
#define BIGLLI __int128
typedef vector<vi> mtrx;

const lli N = 55;
const lli INF = 1e18 + 12;

lli n, m;

lli v[N][N];

lli dp[N][N][N][N];
bool vis[N][N][N][N];

lli calc(lli lx, lli rx, lli ly, lli ry){
  if (lx > rx or ly > ry) return 0;
  if (lx == rx and ly == ry) return 0;
  auto &ans = dp[lx][rx][ly][ry];
  auto &mem = vis[lx][rx][ly][ry];
  if (!mem){
    mem = true;
    ans = INF;
    lli sum = 0; fore(i,lx,rx+1) fore(j,ly,ry+1) sum += v[i][j];
    fore(i,lx,rx) ans = min(ans, sum + calc(lx, i, ly, ry) + calc(i+1, rx, ly, ry));
    fore(j,ly,ry) ans = min(ans, sum + calc(lx, rx, ly, j) + calc(lx, rx, j+1, ry));
  }
  return ans;
}

void solve(){
  cin >> n >> m;
  fore(i,0,n) fore(j,0,m) cin >> v[i][j];
  cout << calc(0, n-1, 0, m-1) << endl;
}

int main(){
  // lli t; cin >> t;
  // while (t--)
    solve();
  return 0;
}

• Subtask 1: 100 / 100