oj.uz

답안 #211919

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
211919 2020-03-21T17:58:26 Z mode149256 건포도 (IOI09_raisins) C++14
100 / 100
 323 ms 33784 KB 
/*input
2 3
2 7 5
1 9 5
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}

ll dp[50][50][50][50];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N, M;
	cin >> N >> M;
	vii sk(N, vi(M));
	vii sm(N, vi(M, 0));

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			cin >> sk[i][j];
			sm[i][j] = sk[i][j];
			if (i) sm[i][j] += sm[i - 1][j];
			if (j) sm[i][j] += sm[i][j - 1];
			if (i and j) sm[i][j] -= sm[i - 1][j - 1];
		}
	}

	auto sum = [&](int ln, int lm, int hn, int hm) {
		return sm[hn][hm]
		       - (lm ? sm[hn][lm - 1] : 0)
		       - (ln ? sm[ln - 1][hm] : 0)
		       + (lm and ln ? sm[ln - 1][lm - 1] : 0);
	};



	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			for (int n = 0; n + i < N; ++n)
			{
				for (int m = 0; m + j < M; ++m)
				{
					if (!i and !j) {
						dp[n][m][n + i][m + j] = 0;
						continue;
					}
					dp[n][m][n + i][m + j] = (ll)1e16;
					for (int ki = 0; ki < i; ++ki)
					{
						ll nauja = dp[n][m][n + ki][m + j]
						           + dp[n + ki + 1][m][n + i][m + j];

						dp[n][m][n + i][m + j] = min(dp[n][m][n + i][m + j], nauja);
					}

					for (int kj = 0; kj < j; ++kj)
					{
						ll nauja = dp[n][m][n + i][m + kj]
						           + dp[n][m + kj + 1][n + i][m + j];

						dp[n][m][n + i][m + j] = min(dp[n][m][n + i][m + j], nauja);
					}
					dp[n][m][n + i][m + j] += sum(n, m, n + i, m + j);
				}
			}
		}
	}
	printf("%lld\n", dp[0][0][N - 1][M - 1]);
}

/* Look for:
* special cases (n=1?)
* overflow (ll vs int?)
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* array bounds
*/

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 5 ms 1024 KB Output is correct
7 Correct 5 ms 1152 KB Output is correct
8 Correct 7 ms 3456 KB Output is correct
9 Correct 9 ms 4864 KB Output is correct
10 Correct 12 ms 5888 KB Output is correct
11 Correct 9 ms 4864 KB Output is correct
12 Correct 26 ms 10488 KB Output is correct
13 Correct 47 ms 13560 KB Output is correct
14 Correct 12 ms 6144 KB Output is correct
15 Correct 57 ms 15224 KB Output is correct
16 Correct 9 ms 5376 KB Output is correct
17 Correct 30 ms 11128 KB Output is correct
18 Correct 177 ms 25336 KB Output is correct
19 Correct 276 ms 31224 KB Output is correct
20 Correct 323 ms 33784 KB Output is correct