#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>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
class ProposalOptimization { public:
double bestPath(int R, int C, int K, vector <int> roses, vector <int> tulips, vector <int> costs)
{
int S = (R - 1) + (C - 1);
vector<vector<tuple<LL, LL, LL>>> cand1(R*C), cand2(R*C);
dfs1(R, C, K, roses, tulips, costs, 0, 0, S/2, 0LL, 0LL, 0LL, cand1);
dfs2(R, C, K, roses, tulips, costs, R-1, C-1, S-S/2, 0LL, 0LL, 0LL, cand2);
double best = -1;
for (int i = 0; i < cand1.size(); ++i)
if (!cand1[i].empty() && !cand2[i].empty())
best = max(best, calc_best(cand1[i], cand2[i], K));
return best;
}
double calc_best(
vector<tuple<LL, LL, LL>> c1,
vector<tuple<LL, LL, LL>> c2,
int K
) {
sort(c1.begin(), c1.end(), [&](const tuple<LL, LL, LL>& a, const tuple<LL, LL, LL>& b) {
return double(get<0>(a)) / get<1>(a) > double(get<0>(b)) / get<1>(b);
});
sort(c2.begin(), c2.end(), [&](const tuple<LL, LL, LL>& a, const tuple<LL, LL, LL>& b) {
return double(get<0>(a)) / get<1>(a) > double(get<0>(b)) / get<1>(b);
});
double best = -1;
for (auto&& e1 : c1) {
LL r1, t1, co1; tie(r1, t1, co1) = e1;
double rat1 = double(r1) / t1;
for (auto&& e2 : c2) {
LL r2, t2, co2; tie(r2, t2, co2) = e2;
double rat2 = double(r2) / t2;
if (co1 + co2 <= K) {
best = max(best, double(r1 + r2) / (t1 + t2));
}
if (rat1 <= best && rat2 <= best)
break;
}
}
return best;
}
void dfs1(int R, int C, int K, const vector<int> &roses, const vector<int>& tulips, const vector<int>& costs,
int y, int x, int s, LL rr, LL tt, LL cc, vector<vector<tuple<LL, LL, LL>>>& cand) {
if (s == 0) {
cand[y*C+x].emplace_back(rr, tt, cc);
return;
}
s--;
rr += roses[y*C + x];
tt += tulips[y*C + x];
cc += costs[y*C + x];
if (y + 1 < R)
dfs1(R, C, K, roses, tulips, costs, y+1, x, s, rr, tt, cc, cand);
if (x + 1 < C)
dfs1(R, C, K, roses, tulips, costs, y, x+1, s, rr, tt, cc, cand);
}
void dfs2(int R, int C, int K, const vector<int> &roses, const vector<int>& tulips, const vector<int>& costs,
int y, int x, int s, LL rr, LL tt, LL cc, vector<vector<tuple<LL, LL, LL>>>& cand) {
rr += roses[y*C + x];
tt += tulips[y*C + x];
cc += costs[y*C + x];
if (s == 0) {
cand[y*C+x].emplace_back(rr, tt, cc);
return;
}
s--;
if (y - 1 >= 0)
dfs2(R, C, K, roses, tulips, costs, y - 1, x, s, rr, tt, cc, cand);
if (x - 1 >= 0)
dfs2(R, C, K, roses, tulips, costs, y, x - 1, s, rr, tt, cc, cand);
}
};
// 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 double& Expected, const double& Received) {
bool ok = (abs(Expected - Received) < 1e-9);
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(_, ProposalOptimization().bestPath(R, C, K, roses, tulips, costs));}
int main(){
CASE(0)
int R = 2;
int C = 2;
int K = 100;
int roses_[] = {0, 2, 3, 0};
vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_));
int tulips_[] = {0, 3, 5, 0};
vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_));
int costs_[] = {0, 70, 80, 0};
vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
double _ = 0.6666666666666667;
END
CASE(1)
int R = 2;
int C = 2;
int K = 100;
int roses_[] = {0, 2, 3, 0};
vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_));
int tulips_[] = {0, 3, 5, 0};
vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_));
int costs_[] = {0, 170, 100, 0};
vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
double _ = 0.6;
END
CASE(2)
int R = 3;
int C = 3;
int K = 98;
int roses_[] = {0, 1, 1, 1, 1, 1, 1, 1, 0};
vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_));
int tulips_[] = {0, 1, 1, 1, 1, 1, 1, 1, 0};
vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_));
int costs_[] = {0, 33, 33, 33, 33, 33, 33, 33, 0};
vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
double _ = -1.0;
END
CASE(3)
int R = 5;
int C = 9;
int K = 622;
int roses_[] = {0, 2, 12, 1, 6, 10, 10, 24, 3, 1, 7, 4, 4, 1, 37, 4, 6, 8, 2, 20, 5, 20, 6, 7, 22, 3, 2, 8, 31, 18, 5, 28, 11, 1, 34, 1, 4, 2, 6, 1, 6, 9, 5, 7, 0};
vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_));
int tulips_[] = {0, 4, 37, 22, 3, 14, 10, 6, 5, 6, 5, 17, 4, 7, 12, 3, 1, 3, 3, 1, 5, 1, 11, 37, 6, 24, 6, 3, 21, 1, 2, 27, 7, 1, 8, 1, 8, 1, 26, 20, 6, 6, 6, 7, 0};
vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_));
int costs_[] = {0, 19, 70, 79, 18, 43, 49, 65, 16, 38, 61, 69, 43, 12, 62, 11, 44, 35, 7, 62, 40, 88, 60, 57, 65, 38, 46, 18, 69, 87, 28, 80, 47, 5, 64, 1, 15, 3, 86, 41, 86, 21, 56, 28, 0};
vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
double _ = 2.161290322580645;
END
CASE(4)
int R = 2;
int C = 3;
int K = 15;
int roses_[] = {0, 1, 3, 1, 1, 0};
vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_));
int tulips_[] = {0, 1, 2, 6, 1, 0};
vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_));
int costs_[] = {0, 1, 18, 9, 1, 0};
vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
double _ = 1.0;
END
CASE(5)
int R = 17;
int C = 17;
int K = 1000000000;
int roses_[] = { 0,17713,98005,85972,85419,41343,40594,75347,93890,14460,88192,13259,57509,23864,11665,83891,86272,15177,6741,719,45954,28976,17494,69645,85635,41641,83750,72134,25460,59238,79843,19241,42910,82037,76014,94424,87835,60518,81389,71620,22925,99806,96380,13812,53986,64087,72645,71066,59167,81512,79112,79376,94122,68917,6461,20829,58265,20191,49403,72161,75464,63255,68477,94619,60731,90043,25099,9348,78594,23510,42035,21938,33854,25015,56547,55185,92344,41515,90935,19182,66704,83072,21731,64543,17498,5861,13274,10448,80628,36311,10855,57786,99593,82225,36546,63772,74592,3376,16070,89074,46067,27551,2731,66618,89683,62388,9681,48186,61936,80333,21392,27448,15920,92274,51645,40695,32491,39887,41545,90544,85138,57454,91032,69274,60520,68444,22949,54533,19920,96297,93530,71936,23721,16630,97250,26918,4078,31547,22942,98473,21503,96772,55133,79486,13707,14208,42654,61512,38364,6095,13808,11189,64709,1277,99824,76973,48998,19603,12891,7593,89029,66987,44448,83779,85479,16134,23980,33936,85444,98235,21115,41423,58343,86809,12650,80022,11253,96942,2552,63303,61702,93988,12874,19507,47539,10623,80913,93724,6698,78407,84626,19955,94554,18908,17534,7815,49133,86196,14223,59940,49525,52174,83198,81931,90518,73849,48514,1486,64897,16791,73509,83061,41101,24339,40911,52042,41565,12010,16810,91464,72979,42196,21127,75435,19330,42120,12526,24400,35862,46552,68157,65335,75713,17243,95124,96114,15670,25945,29786,68448,18314,92647,57702,87304,15779,38562,33340,40193,39768,37511,65405,37272,43597,16314,57010,37359,11549,53388,39583,49716,95725,15464,20113,10362,9822,88209,44604,54927,20688,17684,13526,36081,30399,35955,10775,80362,56735,69285,87764,8086,96866,64919,41125,50869,39730,85021,23265,7472,0 };
vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_));
int tulips_[] = { 0,9769,3028,85209,31522,29537,15670,9872,74152,90511,30552,85947,48407,63109,8661,78971,98650,11447,16597,52768,57998,62459,97353,46290,99556,65315,29642,65209,5186,6575,13996,78253,85369,27644,20307,85963,42024,7704,13495,97337,23681,6532,51458,63148,74251,17312,94640,37763,51284,93920,20807,52788,54022,73863,26384,57486,95723,63913,4796,7952,10401,57086,94030,60544,83498,3953,33518,64072,50391,65430,22260,97536,8499,95372,56623,15411,40845,31869,22748,40259,11731,34988,5007,16729,10429,7649,25527,57598,90154,52284,32678,51334,23627,28031,24523,17301,28375,56446,24804,97224,7073,42305,36863,58364,89465,22514,64934,51833,69432,15144,4114,19130,58231,56947,10697,89774,27353,4582,98877,16611,4898,36227,69319,10145,8021,91236,78226,68164,24304,38902,99049,55563,15667,89339,53542,55528,56648,83841,34369,83507,10322,54066,2109,38691,54068,4146,34578,10539,39825,53008,38115,76977,82128,36250,79640,62876,60224,82458,20672,74027,13015,17336,40022,9466,16190,95201,1984,71439,31622,86304,21238,77681,42793,58347,64545,8461,61198,61462,17351,11199,76388,88024,7151,64715,43508,86176,16988,12823,60358,65930,19270,93090,76541,35446,81321,33736,78439,55714,15090,40355,26655,49819,94411,44956,87498,42104,16999,70319,25812,44599,52167,68978,67435,19497,57032,15935,12790,87411,12311,28746,24555,72121,86503,11097,82830,32400,67871,33171,31720,2775,31814,29149,48084,47054,29581,58158,16032,53299,55162,42943,93528,34878,86465,34271,17400,3307,35604,20670,87995,92288,10165,7459,76834,64926,66418,15671,55829,76154,59843,15184,83445,28295,94417,56173,60185,44153,35721,15819,23521,61573,46060,73816,47811,98808,2077,98142,64358,16098,70327,52811,84917,81751,65018,81568,30895,98370,73153,60908,0 };
vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_));
int costs_[] = { 0,66626,71469,70328,62092,18516,71453,8941,94840,56510,68091,96708,89072,20847,3714,71081,89790,28668,86537,10174,42756,15676,79596,90914,50966,20774,60749,64722,47682,83245,71339,62762,86168,4467,37556,64067,86974,68222,67580,43199,84847,96631,97379,92419,97088,72353,66088,65870,6299,80307,58086,51789,26660,70308,64938,58409,89127,31537,70188,35122,46821,45966,19772,40138,32629,5610,64958,64710,77776,50851,38811,72706,37105,65281,67607,99603,4055,37124,26717,10987,76334,88961,31961,69553,95339,3225,73746,16227,84040,95606,88934,14394,6224,20213,15690,9967,97156,27312,14112,45814,93837,74937,14588,23671,37173,99909,90322,8992,41632,80695,20971,35245,85613,35347,45680,86559,70987,51767,47354,90383,5099,55635,56545,97614,28933,67589,23677,69586,86774,70573,39509,77282,89564,7817,56970,49503,49734,48415,69528,9866,52165,40974,60469,75270,5606,4070,86249,30553,43234,97015,99573,23569,15832,66396,12179,21426,92167,56115,46838,59105,45361,54968,35141,59292,2262,10035,76893,20331,35900,22459,64940,97162,67481,23505,34746,85004,1951,34258,43323,28625,74448,56702,65510,50921,6365,15538,41141,78509,60953,79442,73331,90601,21192,94533,37991,17125,39320,72663,27302,97902,96791,88361,97223,29252,44615,20549,42367,85876,47270,68176,2764,51818,76763,33526,23387,47643,23350,28166,76490,80377,22181,6301,75316,65836,89813,20908,94777,28441,58911,27900,36109,70611,42438,91477,64770,17579,44088,47482,60394,59538,20487,70009,42539,91762,77637,75959,90292,45316,50083,31783,63713,340,30832,21662,13752,84525,96226,40981,37339,6681,69898,43800,42643,45928,41106,42960,23017,89656,82740,38315,66917,64709,85928,66375,50321,41659,91826,81211,63149,73364,18299,50835,27382,7050,56552,46876,34589,20853,0 };
vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
double _ = -2;
END
/*
CASE(6)
int R = 5;
int C = 60;
int K = 100000000;
int roses_[] = { 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 };
vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_));
int tulips_[] = { 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 };
vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_));
int costs_[] = { 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 };
vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
double _ = -2;
END
*/
}
// END CUT HERE