| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 241624 |
2020-06-24T20:45:52 Z |
panda |
Raisins (IOI09_raisins) |
C++14 |
|
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); }
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
