oj.uz

답안 #241624

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
241624 2020-06-24T20:45:52 Z panda 건포도 (IOI09_raisins) C++14
100 / 100
 635 ms 36352 KB 
#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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 36096 KB Output is correct
2 Correct 24 ms 36096 KB Output is correct
3 Correct 26 ms 36224 KB Output is correct
4 Correct 24 ms 36096 KB Output is correct
5 Correct 25 ms 36216 KB Output is correct
6 Correct 25 ms 36096 KB Output is correct
7 Correct 26 ms 36224 KB Output is correct
8 Correct 32 ms 36224 KB Output is correct
9 Correct 39 ms 36224 KB Output is correct
10 Correct 44 ms 36224 KB Output is correct
11 Correct 40 ms 36344 KB Output is correct
12 Correct 85 ms 36352 KB Output is correct
13 Correct 121 ms 36216 KB Output is correct
14 Correct 49 ms 36224 KB Output is correct
15 Correct 156 ms 36216 KB Output is correct
16 Correct 34 ms 36224 KB Output is correct
17 Correct 70 ms 36224 KB Output is correct
18 Correct 335 ms 36224 KB Output is correct
19 Correct 538 ms 36216 KB Output is correct
20 Correct 635 ms 36224 KB Output is correct