Submission #241624

#	Time	Username	Problem	Language	Result	Execution time	Memory
241624		panda	Raisins (IOI09_raisins)	C++14	100 / 100	635 ms	36352 KiB

raisins

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;

const int MX = 55;
const int INF = 1e9;
const int MOD = 1e9 + 7;

#define F0R(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ps(x) cout << x << "\n";
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) begin(x), end(x);
#define sz(x) (int)x.size()
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 

void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
		ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O
		// cin.exceptions(cin.failbit); 
		// throws exception when do smth illegal
		// ex. try to read letter into int
		if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

int N, M, grid[MX][MX];
int dp[MX][MX][MX][MX], cumsum[MX][MX];

int solve(int r, int c, int r1, int c1) {
	if (dp[r][c][r1][c1] != -1) return dp[r][c][r1][c1];

	if (r == r1 && c == c1) return 0;

	int ret = INF;
	FOR(i, r + 1, r1 + 1) {
		ret = min(ret, solve(r, c, i - 1, c1) + solve(i, c, r1, c1));
	}
	FOR(i, c + 1, c1 + 1) {
		ret = min(ret, solve(r, c, r1, i - 1) + solve(r, i, r1, c1));
	}

	int cnt = cumsum[r1][c1];
	if (r) cnt -= cumsum[r - 1][c1];
	if (c) cnt -= cumsum[r1][c - 1];
	if (r && c) cnt += cumsum[r - 1][c - 1];


	return dp[r][c][r1][c1] = ret + cnt;
}

int main() {
	setIO();
	memset(dp, -1, sizeof dp);
	cin >> N >> M;
	F0R(i, N) F0R(j, M) cin >> grid[i][j];

	F0R(i, N) {
		F0R(j, M) {
			if (i) cumsum[i][j] += cumsum[i - 1][j];
			if (j) cumsum[i][j] += cumsum[i][j - 1];
			if (i && j) cumsum[i][j] -= cumsum[i - 1][j - 1];
			cumsum[i][j] += grid[i][j];
		}
	}

	ps(solve(0, 0, N - 1, M - 1));
}

Compilation message (stderr)

raisins.cpp: In function 'void setIn(std::__cxx11::string)':
raisins.cpp:28:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
raisins.cpp: In function 'void setOut(std::__cxx11::string)':
raisins.cpp:29:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100