Artifact Content
Not logged in

Artifact c50d0a704a3e9f57b3cd14f55f7337bdc4f78b98


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef complex<LD> CMP;

class TheMountain { public:
	int minSum(int H, int W, vector <int> Y, vector <int> X, vector <int> V)
	{
		const int N = Y.size();
		static const int INF = 0x3fffffff;
		int best = INF;

		vector< vector<int> > fixed(H, vector<int>(W, 0));
		for(int i=0; i<N; ++i)
			fixed[Y[i]][X[i]] = V[i];

		for(int x=0; x<W; ++x)
		{
			vector< vector<int> > td(H, vector<int>(W));
			vector<int> td_sum(H);
			int td_end = 0;
			for(int y=0; y<H; ++y)
			{
				for(int a=0; a<x; ++a) {
					int req = 1;
					if(0<=a-1&&a-1<W) req = max(req, td[y][a-1]+1);
					if(0<=y-1&&y-1<H) req = max(req, td[y-1][a]+1);
					if(fixed[y][a]) {
						if(fixed[y][a] < req)
							goto label_td_end;
						td[y][a] = fixed[y][a];
					} else {
						td[y][a] = req;
					}
				}
				for(int a=W-1; a>x; --a) {
					int req = 1;
					if(0<=a+1&&a+1<W) req = max(req, td[y][a+1]+1);
					if(0<=y-1&&y-1<H) req = max(req, td[y-1][a]+1);
					if(fixed[y][a]) {
						if(fixed[y][a] < req)
							goto label_td_end;
						td[y][a] = fixed[y][a];
					} else {
						td[y][a] = req;
					}
				}
				int a = x;
				{
					int req = 1;
					if(0<=a-1&&a-1<W) req = max(req, td[y][a-1]+1);
					if(0<=a+1&&a+1<W) req = max(req, td[y][a+1]+1);
					if(0<=y-1&&y-1<H) req = max(req, td[y-1][a]+1);
					if(fixed[y][a]) {
						if(fixed[y][a] < req)
							goto label_td_end;
						td[y][a] = fixed[y][a];
					} else {
						td[y][a] = req;
					}
				}
				td_sum[y] = accumulate(td[y].begin(), td[y].end(), 0);
				td_end ++;
			}
		label_td_end:;

			vector< vector<int> > bu(H, vector<int>(W));
			vector<int> bu_sum(H);
			int bu_begin = H;
			for(int y=H-1; y>=0; --y)
			{
				for(int a=0; a<x; ++a) {
					int req = 1;
					if(0<=a-1&&a-1<W) req = max(req, bu[y][a-1]+1);
					if(0<=y+1&&y+1<H) req = max(req, bu[y+1][a]+1);
					if(fixed[y][a]) {
						if(fixed[y][a] < req)
							goto label_bu_end;
						bu[y][a] = fixed[y][a];
					} else {
						bu[y][a] = req;
					}
				}
				for(int a=W-1; a>x; --a) {
					int req = 1;
					if(0<=a+1&&a+1<W) req = max(req, bu[y][a+1]+1);
					if(0<=y+1&&y+1<H) req = max(req, bu[y+1][a]+1);
					if(fixed[y][a]) {
						if(fixed[y][a] < req)
							goto label_bu_end;
						bu[y][a] = fixed[y][a];
					} else {
						bu[y][a] = req;
					}
				}
				int a = x;
				{
					int req = 1;
					if(0<=a-1&&a-1<W) req = max(req, bu[y][a-1]+1);
					if(0<=a+1&&a+1<W) req = max(req, bu[y][a+1]+1);
					if(0<=y+1&&y+1<H) req = max(req, bu[y+1][a]+1);
					if(fixed[y][a]) {
						if(fixed[y][a] < req)
							goto label_bu_end;
						bu[y][a] = fixed[y][a];
					} else {
						bu[y][a] = req;
					}
				}
				bu_sum[y] = accumulate(bu[y].begin(), bu[y].end(), 0);
				bu_begin --;
			}
		label_bu_end:;

			if(td_end <= bu_begin)
				continue;

			int baseline = 0;
			for(int Y=0; Y<H; ++Y)
				baseline += (Y<bu_begin ? td_sum[Y] : Y==bu_begin ? 0 : bu_sum[Y]);

			for(int y=bu_begin; y<td_end; ++y)
			{
				int score = baseline;
				for(int x=0; x<W; ++x)
					score += max(td[y][x], bu[y][x]);
				best = min(best, score);
				if(y<H)
					baseline += td_sum[y] - bu_sum[y+1];
			}
		}
		return (best==INF ? -1 : best);
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, TheMountain().minSum(n, m, rowIndex, columnIndex, element));}
int main(){

CASE(0)
	int n = 2; 
	int m = 3; 
	int rowIndex_[] = {0, 0, 0, 1, 1, 1};
	  vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_)); 
	int columnIndex_[] = {0, 1, 2, 0, 1, 2};
	  vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_)); 
	int element_[] = {4, 6, 9, 1, 3, 6};
	  vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_)); 
	int _ = 29; 
END
CASE(1)
	int n = 2; 
	int m = 3; 
	int rowIndex_[] = {1, 0, 1};
	  vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_)); 
	int columnIndex_[] = {2, 2, 0};
	  vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_)); 
	int element_[] = {5, 7, 6};
	  vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_)); 
	int _ = 40; 
END
CASE(2)
	int n = 3; 
	int m = 3; 
	int rowIndex_[] = {0, 0, 2, 2};
	  vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_)); 
	int columnIndex_[] = {0, 2, 2, 0};
	  vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_)); 
	int element_[] = {1, 1, 1, 1};
	  vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_)); 
	int _ = 15; 
END
CASE(3)
	int n = 2; 
	int m = 2; 
	int rowIndex_[] = {0, 0, 1, 1};
	  vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_)); 
	int columnIndex_[] = {0, 1, 1, 0};
	  vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_)); 
	int element_[] = {5, 8, 5, 8};
	  vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_)); 
	int _ = -1; 
END
CASE(4)
	int n = 1; 
	int m = 3; 
	int rowIndex_[] = {0};
	  vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_)); 
	int columnIndex_[] = {1};
	  vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_)); 
	int element_[] = {1};
	  vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_)); 
	int _ = -1; 
END
CASE(5)
	int n = 123; 
	int m = 45; 
	int rowIndex_[] = {2, 3, 5, 7, 11};
	  vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_)); 
	int columnIndex_[] = {13, 17, 19, 23, 29};
	  vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_)); 
	int element_[] = {100, 200, 300, 400, 500};
	  vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_)); 
	int _ = 367047; 
END
CASE(6)
	int n = 200; 
	int m = 200; 
	int rowIndex_[] = {5};
	  vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_)); 
	int columnIndex_[] = {8};
	  vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_)); 
	int element_[] = {666};
	  vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_)); 
	int _ = 5737554; 
END
CASE(7)
	int n = 10; 
	int m = 10; 
	int rowIndex_[] = {0, 8, 7};
	  vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_)); 
	int columnIndex_[] = {3, 1, 9};
	  vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_)); 
	int element_[] = {5, 4, 7};
	  vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_)); 
	int _ = 593; 
END
CASE(8)
	int n = 200; 
	int m = 200; 
	int rowIndex_[] = {129,99,142,33,111,174,169,176,83,143,70,116,193,139,7,35,111,4,189,111,170,29,16,87,115,4,60,71,37,138,128,38,61,176,187,66,64,84,120,104,124,129,91,137,114,187,97,115,151,140};
	  vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_)); 
	int columnIndex_[] = {191,148,194,13,90,17,185,163,17,170,193,165,140,158,85,15,56,91,9,68,153,83,9,97,74,40,160,165,49,151,173,98,123,44,139,164,66,112,141,172,91,147,71,167,123,53,189,86,71,171};
	  vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_)); 
	int element_[] = {953,216,307,197,970,590,659,153,79,262,628,153,106,904,888,249,224,839,29,327,664,619,387,325,865,849,516,313,649,135,713,585,347,279,702,837,682,817,844,981,401,410,982,891,167,102,646,73,784,455};
	  vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_)); 
	int _ = -1; 
END
/*
CASE(9)
	int n = ; 
	int m = ; 
	int rowIndex_[] = ;
	  vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_)); 
	int columnIndex_[] = ;
	  vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_)); 
	int element_[] = ;
	  vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_)); 
	int _ = ; 
END
*/
}
// END CUT HERE