AOJ-ICPC埋め

国内予選出るので精進します。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2743&lang=jp

4隅を必ず含む解が存在することが言える。それを元に丁寧に場合分けすればできる。面倒だけど一発AC。

int H, W, N;
ll A[210][210];
ll S[210][210];

ll get(int x1, int y1, int x2, int y2) { //[x1 x2)*[y1 y2)
	return S[x2][y2] - S[x1][y2] - S[x2][y1] + S[x1][y1];
}

bool divide1(int x1, int y1, int x2, int y2, ll m) { //O(1)
	return get(x1, y1, x2, y2) >= m;
}

bool divide2(int x1, int y1, int x2, int y2, ll m) { //O(N)
	bool ok = false;
	rep(i, x1, x2) {
		ok |= (divide1(x1, y1, i, y2, m) & divide1(i, y1, x2, y2, m));
	}
	rep(i, y1, y2) {
		ok |= (divide1(x1, y1, x2, i, m) & divide1(x1, i, x2, y2, m));
	}
	return ok;
}

bool divide3(int x1, int y1, int x2, int y2, ll m) { //O(N)
	bool ok = false;
	rep(i, x1, x2) {
		if(divide1(x1, y1, i, y2, m)) {
			ok |= divide2(i, y1, x2, y2, m);
			break;
		}
	}
	rer(i, x2, x1) {
		if(divide1(i, y1, x2, y2, m)) {
			ok |= divide2(x1, y1, i, y2, m);
			break;
		}
	}
	rep(i, y1, y2) {
		if(divide1(x1, y1, x2, i, m)) {
			ok |= divide2(x1, i, x2, y2, m);
			break;
		}
	}
	rer(i, y2, y1) {
		if(divide1(x1, i, x2, y2, m)) {
			ok |= divide2(x1, y1, x2, i, m);
			break;
		}
	}
	return ok;
}

bool divide4(ll x1, ll y1, ll x2, ll y2, ll m) {
	bool ok = false;
	rep(i, x1, x2) {
		if(divide1(x1, y1, i, y2, m)) {
			ok |= divide3(i, y1, x2, y2, m);
			break;
		}
	}
	rer(i, x2, x1) {
		if(divide1(i, y1, x2, y2, m)) {
			ok |= divide3(x1, y1, i, y2, m);
			break;
		}
	}
	rep(i, y1, y2) {
		if(divide1(x1, y1, x2, i, m)) {
			ok |= divide3(x1, i, x2, y2, m);
			break;
		}
	}
	rer(i, y2, y1) {
		if(divide1(x1, i, x2, y2, m)) {
			ok |= divide3(x1, y1, x2, i, m);
			break;
		}
	}
	rep(i, 0, H) {
		rep(j, 0, W) {
			if(divide1(0, 0, i, j, m)) {
				int x = 0, y = 0;
				while(x <= H && !divide1(0, j, x, W, m)) {
					x++;
				}
				while(y <= W && !divide1(i, 0, H, y, m)) {
					y++;
				}
				if(x <= H && y <= W) {
					if((x <= i && y >= j) || (x >= i && y <= j)) {
						ok |= divide1(x, y, H, W, m);
					}
				}
			}
		}
	}
	return ok;
}

void solve() {
	cin >> H >> W >> N;
	rep(i, 0, H) {
		rep(j, 0, W) {
			ll a; cin >> a;
			S[i + 1][j + 1] += a + S[i + 1][j] + S[i][j + 1] - S[i][j];
		}
	}
	ll lv = -1, rv = inf;
	while(rv - lv > 1) {
		ll m = (lv + rv) / 2;
		if(N == 2) {
			if(divide2(0, 0, H, W, m)) lv = m;
			else rv = m;
		}
		else if(N == 3) {
			if(divide3(0, 0, H, W, m)) lv = m;
			else rv = m;
		}
		else {
			if(divide4(0, 0, H, W, m)) lv = m;
			else rv = m;
		}
	}
	cout << lv << "\n";
}

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2646&lang=jp

dp(l, r, k):=区間[l, r)内でトーナメント表を作るとして2^kが優勝するときの最小変更回数
とすれば区間はたかだかO(M*N)個しかないのでO(M*N^2)で計算できて間に合います。1回dp tableがでかくしすぎてMLEした。
こういうの制約が大きいから貪欲的に考えがちだけど、DPにも頭を働かせられるようになるといいですね。

int N, M, K; //K:=num of interval
pl I[MAX_N];
pi nex[MAX_N];
int D[MAX_N]; //depth
int S[MAX_N]; //-1 or else
ll A[10010], B[10010];

ll dp[MAX_N][31];

void init(ll l, ll r, int k, int d) {
	I[k] = pl(l, r);
	D[k]= d;
	int at = upper_bound(A, A + M + 1, l) - A;
	ll m = (l + r) / 2;
	if(A[at] >= r) {
		S[k] = B[at - 1];
	}
	else {
		S[k] = -1;
		nex[k] = pi(K + 1, K + 2);
		K += 2;
		init(l, m, nex[k].fst, d + 1);
		init(m, r, nex[k].sec, d + 1);
	}
}

ll loop(int at, int s) {
	if(dp[at][s] != -1) return dp[at][s];
	else if(S[at] != -1) {
		ll l = I[at].sec - I[at].fst;
		ll sub = 0;
		if(S[at] > D[at]) {
			sub = (1LL << (S[at] - (D[at] + 1)));
		}
		else if(S[at] <= D[at]) {
			sub = (s == S[at]);
		}
		return l - sub;
	}
	else {
		ll lv = loop(nex[at].fst, s) + loop(nex[at].sec, D[at] + 1);
		ll rv = loop(nex[at].fst, D[at] + 1) + loop(nex[at].sec, s);
		return dp[at][s] = min(lv, rv);
	}
}

void solve() {
	cin >> N >> M;
	rep(i, 0, M + 1) cin >> A[i];
	rep(i, 0, M) cin >> B[i];
	K = 0;
	init(0, (1LL << N), 0, 0);
	memset(dp, -1, sizeof(dp));
	cout << loop(0, 0) << "\n";
}