Submission #233126

#	Time	Username	Problem	Language	Result	Execution time	Memory
233126		anubhavdhar	Raisins (IOI09_raisins)	C++14	100 / 100	694 ms	53496 KiB

raisins

#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 / 100