oj.uz

Submission #233126

# Submission time Handle Problem Language Result Execution time Memory
233126 2020-05-19T12:21:20 Z anubhavdhar Raisins (IOI09_raisins) C++14
100 / 100
 694 ms 53496 KB 
#include<bits/stdc++.h>

#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i,n) for(i=0;i<(n);++i)
#define FORe(i,n) for(i=1;i<=(n);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,n) for(i=(n);i>=0;--i)
#define F0R(i,n) for(int i=0;i<(n);++i)
#define F0Re(i,n) for(int i=1;i<=(n);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,n) for(int i=(n);i>=0;--i)
#define ii pair<ll,ll>
#define vi vector<ll>
#define vii vector<ii>
#define ff first 
#define ss second
#define cd complex<double>
#define vcd vector<cd>
#define ldd long double
#define dbgLine cout<<"Line : "<<__LINE__<<'\n'
#define all(x) (x).begin(),(x).end()

using namespace std;

const short int __PRECISION = 10;

const ll MOD = 1e9+7;
const ll INF = 1e17 + 1101;
const ll LOGN = 17;
const ll MAXN = 2e5+5;
const ll ROOTN = 320;

const ldd PI = acos(-1);
const ldd EPS = 1e-7;

int N, M;
ll A[51][51], pre[51][51], dp[51][51][51][51];

ll DP(int x1, int y1, int x2, int y2)
{
	if (x1 == x2 and y1 == y2)
		return 0;
	ll& t = dp[x1][y1][x2][y2];
	if (t != -1)
		return t;
	t = INF;
	F0Rr(i, x1, x2)
		t = min(t, DP(x1,y1,i,y2) + DP(i+1,y1,x2,y2));
	F0Rr(j, y1, y2)
		t = min(t, DP(x1,y1,x2,j) + DP(x1,j+1,x2,y2));
	t += pre[x2][y2] - pre[x2][y1-1] - pre[x1-1][y2] + pre[x1-1][y1-1];
	// assert(t == dp[x1][y1][x2][y2]);
	// cout<<"dp["<<x1<<"]["<<y1<<"]["<<x2<<"]["<<y2<<"] = "<<t<<'\n';
	return t;
}

int main()
{
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int i, j;
	FOR(i, 51)
		FOR(j, 51)
			A[i][j] = pre[i][j] = 0;

	FOR(i, 51)
		FOR(j, 51)
			F0R(k, 51)
				F0R(l , 51)
					dp[i][j][k][l] = -1;

	cin>>N>>M;

	FORe(i, N)
		FORe(j, M)
			cin>>A[i][j], pre[i][j] = A[i][j] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];

	cout<<DP(1, 1, N, M);


	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 53376 KB Output is correct
2 Correct 32 ms 53376 KB Output is correct
3 Correct 33 ms 53376 KB Output is correct
4 Correct 33 ms 53376 KB Output is correct
5 Correct 33 ms 53368 KB Output is correct
6 Correct 33 ms 53376 KB Output is correct
7 Correct 34 ms 53376 KB Output is correct
8 Correct 40 ms 53496 KB Output is correct
9 Correct 48 ms 53368 KB Output is correct
10 Correct 56 ms 53376 KB Output is correct
11 Correct 50 ms 53376 KB Output is correct
12 Correct 96 ms 53368 KB Output is correct
13 Correct 144 ms 53368 KB Output is correct
14 Correct 62 ms 53368 KB Output is correct
15 Correct 177 ms 53368 KB Output is correct
16 Correct 44 ms 53376 KB Output is correct
17 Correct 90 ms 53376 KB Output is correct
18 Correct 398 ms 53496 KB Output is correct
19 Correct 625 ms 53368 KB Output is correct
20 Correct 694 ms 53368 KB Output is correct