oj.uz

Submission #799622

# Submission time Handle Problem Language Result Execution time Memory
799622 2023-07-31T16:47:25 Z I_Love_EliskaM_ Raisins (IOI09_raisins) C++14
100 / 100
 222 ms 82636 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define forn(i,n) for(int i=0;i<n;++i)
#define pi pair<int,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vii(a,n) vector<int>a(n);forn(i,n)cin>>a[i];

const int inf = 1e15;

const int N=50;
int dp[N][N][N][N];
int mem[N][N][N][N];
int pr[N+1][N+1];

int query(int a, int b, int c, int d) {
	a++, b++, c++, d++;
	return pr[c][d] - pr[c][b-1] - pr[a-1][d] + pr[a-1][b-1];
}

void rec(int a, int b, int c, int d) {
	if (mem[a][b][c][d]) return;
	mem[a][b][c][d]=1;
	for (int m=a; m<c; ++m) {
		rec(a,b,m,d); rec(m+1,b,c,d);
		dp[a][b][c][d]=min(dp[a][b][c][d],dp[a][b][m][d]+dp[m+1][b][c][d]);
	}
	for (int m=b; m<d; ++m) {
		rec(a,b,c,m); rec(a,m+1,c,d);
		dp[a][b][c][d]=min(dp[a][b][c][d],dp[a][b][c][m]+dp[a][m+1][c][d]);
	}
	dp[a][b][c][d]+=query(a,b,c,d);
	//cout<<a<<' '<<b<<' '<<c<<' '<<d<<"  "<<dp[a][b][c][d]<<'\n';
}

void solve() {

	int n,m; cin>>n>>m;
	forn(i,n) forn(j,m) forn(k,n) forn(t,m) dp[i][j][k][t]=inf;
	forn(i,n) forn(j,m) dp[i][j][i][j]=0;
	forn(i,n) forn(j,m) mem[i][j][i][j]=1;
	forn(i,n) {
		forn(j,m) {
			int x; cin>>x;
			pr[i+1][j+1]=pr[i+1][j]+pr[i][j+1]-pr[i][j]+x;
			//cout<<pr[i+1][j+1]<<' ';
		}
		//cout<<'\n';
	}
	rec(0,0,n-1,m-1);
	cout<<dp[0][0][n-1][m-1]<<'\n';

}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	solve();
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 1732 KB Output is correct
7 Correct 1 ms 2260 KB Output is correct
8 Correct 5 ms 7876 KB Output is correct
9 Correct 8 ms 11860 KB Output is correct
10 Correct 11 ms 14292 KB Output is correct
11 Correct 9 ms 11592 KB Output is correct
12 Correct 26 ms 26700 KB Output is correct
13 Correct 44 ms 35072 KB Output is correct
14 Correct 13 ms 14736 KB Output is correct
15 Correct 52 ms 39708 KB Output is correct
16 Correct 8 ms 13524 KB Output is correct
17 Correct 26 ms 28308 KB Output is correct
18 Correct 134 ms 63328 KB Output is correct
19 Correct 193 ms 77356 KB Output is correct
20 Correct 222 ms 82636 KB Output is correct