#2357388

Solution for 1176: Planning Rolling Blackouts by gazelle

Source Code Status Test Cases
    Policy: public     Reviewed: 26    
00.43 sec    18096 KB    103 lines     2617 bytes    2017-06-07 11:15
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#define REP(i, N) for(ll i = 0; i < N; ++i)
#define FOR(i, a, b) for(ll i = a; i < b; ++i)
#define ALL(a) (a).begin(),(a).end()
#define pb push_back
#define INF (long long)1000000000
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
vector<vector<int> > u;
vector<vector<int> > sums;
vector<vector<vector<vector<i_i> > > > memo;
int h, w, s;
int sum;

i_i rec(i_i lu, i_i rd) {
	if(memo[lu.first][lu.second][rd.first][rd.second].first != INF) return memo[lu.first][lu.second][rd.first][rd.second];
	else {
		int sub = s - (sum - (sums[rd.first + 1][rd.second + 1] - sums[(lu.first + 1) - 1][rd.second + 1]
						 - sums[rd.first + 1][(lu.second + 1) - 1] + sums[(lu.first + 1) - 1][(lu.second + 1) - 1]));
		if(sub < 0) {
			return memo[lu.first][lu.second][rd.first][rd.second] = i_i(-1, -1);
		}
		i_i res = i_i(-1, -1);
		REP(i, rd.first - lu.first) {
			i_i lset = rec(lu, i_i(lu.first + i, rd.second));
			i_i rset = rec(i_i(lu.first + 1 + i, lu.second), rd);
			if(lset.first != -1 && rset.first != -1) {
				res = max(res, i_i(lset.first + rset.first, min(lset.second, rset.second)));
			}
		}
		REP(i, rd.second - lu.second) {
			i_i lset = rec(lu, i_i(rd.first, lu.second + i));
			i_i rset = rec(i_i(lu.first, lu.second + 1 + i), rd);
			if(lset.first != -1 && rset.first != -1) {
				res = max(res, i_i(lset.first + rset.first, min(lset.second, rset.second)));
			}
		}
		if(res.first != -1) return memo[lu.first][lu.second][rd.first][rd.second] = res;
		else {
			return memo[lu.first][lu.second][rd.first][rd.second] = i_i(1, sub);
		}
	}
}

int main(void) {
	while(true) {
		cin>>h>>w>>s;
		if(h == 0 && w == 0 && s == 0) break;
		sum = 0;
		u.resize(h);
		REP(i, h) u[i].resize(w);
		REP(i, h) {
			REP(j, w) {
				cin>>u[i][j];
				sum += u[i][j];
			}
		}
		sums.resize(h + 1);
		REP(i, h + 1) sums[i].resize(w + 1);
		REP(i, h + 1) {
			REP(j, w + 1) {
				if(i == 0 || j == 0) sums[i][j] = 0;
				else {
					sums[i][j] = u[i - 1][j - 1];
				}
			}
		}
		REP(i, h + 1) {
			REP(j, w + 1) {
				if(j == 0) continue;
				sums[i][j] += sums[i][j - 1];
			}
		}
		REP(j, w + 1) {
			REP(i, h + 1) {
				if(i == 0) continue;
				sums[i][j] += sums[i - 1][j];
			}
		}
		memo.resize(h);
		REP(i, h) {
			memo[i].resize(w);
			REP(j, w) {
				memo[i][j].resize(h);
				REP(k, h) {
					memo[i][j][k].resize(w);
					REP(l, w) {
						memo[i][j][k][l] = i_i(INF, INF);
					}
				}
			}
		}
		i_i ans = rec(i_i(0, 0), i_i(h - 1, w - 1));
		cout<<ans.first<<" "<<ans.second<<endl;
	}
}


Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 2/2 C++ CPU: 00.43 sec Memory: 18096 KB Length: 2617 B 2017-06-07 11:15 2017-06-07 11:15
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 00.35 sec 14484 KB
Case #2: : Accepted 00.43 sec 18096 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags