Overview
| SHA1 Hash: | 06a6ad17f5f7f8a888d27cfc501f53c87618c212 |
|---|---|
| Date: | 2020-09-10 16:54:39 |
| User: | kinaba |
| Comment: | 790 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/790-U/1A.cpp version [5858693d18cedfa3]
1 +#include <iostream> 2 +#include <sstream> 3 +#include <iomanip> 4 +#include <vector> 5 +#include <string> 6 +#include <map> 7 +#include <set> 8 +#include <algorithm> 9 +#include <numeric> 10 +#include <iterator> 11 +#include <functional> 12 +#include <complex> 13 +#include <queue> 14 +#include <stack> 15 +#include <cmath> 16 +#include <cassert> 17 +#include <tuple> 18 +using namespace std; 19 +typedef long long LL; 20 +typedef complex<double> CMP; 21 + 22 +struct UnionFind 23 +{ 24 + vector<int> uf, sz; 25 + int nc; 26 + 27 + UnionFind(int N) : uf(N), sz(N, 1), nc(N) 28 + { 29 + for (int i = 0; i<N; ++i) uf[i] = i; 30 + } 31 + int size() 32 + { 33 + return nc; 34 + } 35 + int size(int a) 36 + { 37 + return sz[Find(a)]; 38 + } 39 + int Find(int a) 40 + { 41 + return uf[a] == a ? a : uf[a] = Find(uf[a]); 42 + } 43 + // Semi-compression w.o. recursion. 44 + //{ while(uf[a] != a) a=uf[a]=uf[uf[a]]; return a; } 45 + bool Union(int a, int b) 46 + { 47 + a = Find(a); 48 + b = Find(b); 49 + if (a != b) 50 + { 51 + if (sz[a] >= sz[b]) swap(a, b); 52 + uf[a] = b; 53 + sz[b] += sz[a]; 54 + --nc; 55 + } 56 + return (a != b); 57 + } 58 +}; 59 + 60 +static const unsigned MODVAL = 1000000007; 61 +struct mint 62 +{ 63 + unsigned val; 64 + mint() :val(0) {} 65 + mint(int x) :val(x%MODVAL) {} 66 + mint(unsigned x) :val(x%MODVAL) {} 67 + mint(LL x) :val(x%MODVAL) {} 68 +}; 69 +mint& operator+=(mint& x, mint y) { return x = x.val + y.val; } 70 +mint& operator-=(mint& x, mint y) { return x = x.val - y.val + MODVAL; } 71 +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } 72 +mint operator+(mint x, mint y) { return x += y; } 73 +mint operator-(mint x, mint y) { return x -= y; } 74 +mint operator*(mint x, mint y) { return x *= y; } 75 + 76 +mint POW(mint x, LL e) { mint v = 1; for (; e; x *= x, e >>= 1) if (e & 1) v *= x; return v; } 77 + 78 +class TheSocialNetwork { public: 79 + int minimumCut(int n, int m, vector <int> u, vector <int> v, vector <int> l) 80 + { 81 + vector<tuple<int, int, int>> e; 82 + for (int i = 0; i < m; ++i) 83 + e.emplace_back(l[i], u[i]-1, v[i]-1); 84 + sort(e.begin(), e.end()); 85 + 86 + vector<bool> use(m, false); 87 + for (int k = e.size() - 1; k >= 0; --k) { 88 + use[k] = true; 89 + if (is_connected(n, m, use, e)) 90 + use[k] = false; 91 + } 92 + 93 + mint ans = 0; 94 + for (int i = 0; i < m; ++i) if (!use[i]) 95 + ans += POW(2, get<0>(e[i])); 96 + return ans.val; 97 + } 98 + 99 + bool is_connected(int n, int m, const vector<bool>& use, const vector<tuple<int, int, int>>& e) { 100 + UnionFind uf(n); 101 + for (int i = 0; i < m; ++i) if (use[i]) 102 + uf.Union(get<1>(e[i]), get<2>(e[i])); 103 + return uf.size() == 1; 104 + 105 + } 106 +}; 107 + 108 +// BEGIN CUT HERE 109 +#include <ctime> 110 +double start_time; string timer() 111 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 112 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 113 + { os << "{ "; 114 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 115 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 116 +void verify_case(const int& Expected, const int& Received) { 117 + bool ok = (Expected == Received); 118 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 119 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 120 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 121 +#define END verify_case(_, TheSocialNetwork().minimumCut(n, m, u, v, l));} 122 +int main(){ 123 + 124 +CASE(0) 125 + int n = 6; 126 + int m = 6; 127 + int u_[] = {1, 2, 3, 4, 5, 6} ; 128 + vector <int> u(u_, u_+sizeof(u_)/sizeof(*u_)); 129 + int v_[] = {2, 3, 4, 5, 6, 1}; 130 + vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 131 + int l_[] = {1, 7, 3, 4, 6, 12}; 132 + vector <int> l(l_, l_+sizeof(l_)/sizeof(*l_)); 133 + int _ = 10; 134 +END 135 +CASE(1) 136 + int n = 5; 137 + int m = 7; 138 + int u_[] = {1, 1, 1, 2, 2, 3, 3}; 139 + vector <int> u(u_, u_+sizeof(u_)/sizeof(*u_)); 140 + int v_[] = {5, 3, 2, 5, 3, 5, 4}; 141 + vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 142 + int l_[] = {1, 8, 2, 3, 4, 6, 9}; 143 + vector <int> l(l_, l_+sizeof(l_)/sizeof(*l_)); 144 + int _ = 28; 145 +END 146 +CASE(2) 147 + int n = 7; 148 + int m = 6; 149 + int u_[] = {1, 1, 2, 2, 3, 3}; 150 + vector <int> u(u_, u_+sizeof(u_)/sizeof(*u_)); 151 + int v_[] = {2, 3, 4, 5, 6, 7}; 152 + vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 153 + int l_[] = {7, 11, 6, 9, 20, 15}; 154 + vector <int> l(l_, l_+sizeof(l_)/sizeof(*l_)); 155 + int _ = 64; 156 +END 157 +CASE(3) 158 + int n = 8; 159 + int m = 11; 160 + int u_[] = {1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 7}; 161 + vector <int> u(u_, u_+sizeof(u_)/sizeof(*u_)); 162 + int v_[] = {2, 8, 3, 5, 4, 6, 7, 5, 6, 8, 8}; 163 + vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 164 + int l_[] = {2, 3, 1, 6, 11, 8, 9, 10, 7, 4, 5}; 165 + vector <int> l(l_, l_+sizeof(l_)/sizeof(*l_)); 166 + int _ = 12; 167 +END 168 +CASE(4) 169 + int n = 13; 170 + int m = 56; 171 + int u_[] = {1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 11, 11, 12}; 172 + vector <int> u(u_, u_+sizeof(u_)/sizeof(*u_)); 173 + int v_[] = {3, 4, 5, 7, 9, 12, 13, 3, 5, 8, 9, 10, 12, 13, 5, 6, 8, 9, 10, 11, 12, 5, 6, 7, 9, 11, 13, 7, 8, 9, 11, 12, 7, 8, 9, 10, 13, 8, 9, 10, 11, 12, 13, 9, 11, 12, 10, 11, 12, 13, 11, 12, 13, 12, 13, 13}; 174 + vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 175 + int l_[] = {82, 240, 395, 1041, 1165, 1274, 1540, 1650, 1904, 2306, 2508, 3162, 3380, 3637, 3778, 3913, 3971, 4101, 4148, 4218, 4394, 4434, 5107, 6147, 6280, 6337, 6461, 6490, 7056, 8024, 8373, 8924, 8961, 9058, 9304, 9359, 10899, 11049, 11090, 11174, 11269, 11356, 11547, 11808, 12566, 12591, 13322, 13447, 13667, 13672, 15013, 15319, 16153, 16447, 16454, 16470}; 176 + vector <int> l(l_, l_+sizeof(l_)/sizeof(*l_)); 177 + int _ = 504663883; 178 +END 179 +/* 180 +CASE(5) 181 + int n = ; 182 + int m = ; 183 + int u_[] = ; 184 + vector <int> u(u_, u_+sizeof(u_)/sizeof(*u_)); 185 + int v_[] = ; 186 + vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 187 + int l_[] = ; 188 + vector <int> l(l_, l_+sizeof(l_)/sizeof(*l_)); 189 + int _ = ; 190 +END 191 +CASE(6) 192 + int n = ; 193 + int m = ; 194 + int u_[] = ; 195 + vector <int> u(u_, u_+sizeof(u_)/sizeof(*u_)); 196 + int v_[] = ; 197 + vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 198 + int l_[] = ; 199 + vector <int> l(l_, l_+sizeof(l_)/sizeof(*l_)); 200 + int _ = ; 201 +END 202 +*/ 203 +} 204 +// END CUT HERE
Added SRM/790-U/1B.cpp version [f1a66c485fe2d09f]
1 +#include <iostream> 2 +#include <sstream> 3 +#include <iomanip> 4 +#include <vector> 5 +#include <string> 6 +#include <map> 7 +#include <set> 8 +#include <algorithm> 9 +#include <numeric> 10 +#include <iterator> 11 +#include <functional> 12 +#include <complex> 13 +#include <queue> 14 +#include <stack> 15 +#include <cmath> 16 +#include <cassert> 17 +#include <tuple> 18 +using namespace std; 19 +typedef long long LL; 20 +typedef complex<double> CMP; 21 + 22 +class ProposalOptimization { public: 23 + double bestPath(int R, int C, int K, vector <int> roses, vector <int> tulips, vector <int> costs) 24 + { 25 + int S = (R - 1) + (C - 1); 26 + 27 + vector<vector<tuple<LL, LL, LL>>> cand1(R*C), cand2(R*C); 28 + dfs1(R, C, K, roses, tulips, costs, 0, 0, S/2, 0LL, 0LL, 0LL, cand1); 29 + dfs2(R, C, K, roses, tulips, costs, R-1, C-1, S-S/2, 0LL, 0LL, 0LL, cand2); 30 + 31 + double best = -1; 32 + for (int i = 0; i < cand1.size(); ++i) 33 + if (!cand1[i].empty() && !cand2[i].empty()) 34 + best = max(best, calc_best(cand1[i], cand2[i], K)); 35 + return best; 36 + } 37 + 38 + double calc_best( 39 + vector<tuple<LL, LL, LL>> c1, 40 + vector<tuple<LL, LL, LL>> c2, 41 + int K 42 + ) { 43 + sort(c1.begin(), c1.end(), [&](const tuple<LL, LL, LL>& a, const tuple<LL, LL, LL>& b) { 44 + return double(get<0>(a)) / get<1>(a) > double(get<0>(b)) / get<1>(b); 45 + }); 46 + sort(c2.begin(), c2.end(), [&](const tuple<LL, LL, LL>& a, const tuple<LL, LL, LL>& b) { 47 + return double(get<0>(a)) / get<1>(a) > double(get<0>(b)) / get<1>(b); 48 + }); 49 + double best = -1; 50 + for (auto&& e1 : c1) { 51 + LL r1, t1, co1; tie(r1, t1, co1) = e1; 52 + double rat1 = double(r1) / t1; 53 + for (auto&& e2 : c2) { 54 + LL r2, t2, co2; tie(r2, t2, co2) = e2; 55 + double rat2 = double(r2) / t2; 56 + if (co1 + co2 <= K) { 57 + best = max(best, double(r1 + r2) / (t1 + t2)); 58 + } 59 + if (rat1 <= best && rat2 <= best) 60 + break; 61 + } 62 + } 63 + return best; 64 + } 65 + 66 + void dfs1(int R, int C, int K, const vector<int> &roses, const vector<int>& tulips, const vector<int>& costs, 67 + int y, int x, int s, LL rr, LL tt, LL cc, vector<vector<tuple<LL, LL, LL>>>& cand) { 68 + if (s == 0) { 69 + cand[y*C+x].emplace_back(rr, tt, cc); 70 + return; 71 + } 72 + s--; 73 + rr += roses[y*C + x]; 74 + tt += tulips[y*C + x]; 75 + cc += costs[y*C + x]; 76 + if (y + 1 < R) 77 + dfs1(R, C, K, roses, tulips, costs, y+1, x, s, rr, tt, cc, cand); 78 + if (x + 1 < C) 79 + dfs1(R, C, K, roses, tulips, costs, y, x+1, s, rr, tt, cc, cand); 80 + } 81 + void dfs2(int R, int C, int K, const vector<int> &roses, const vector<int>& tulips, const vector<int>& costs, 82 + int y, int x, int s, LL rr, LL tt, LL cc, vector<vector<tuple<LL, LL, LL>>>& cand) { 83 + rr += roses[y*C + x]; 84 + tt += tulips[y*C + x]; 85 + cc += costs[y*C + x]; 86 + if (s == 0) { 87 + cand[y*C+x].emplace_back(rr, tt, cc); 88 + return; 89 + } 90 + s--; 91 + if (y - 1 >= 0) 92 + dfs2(R, C, K, roses, tulips, costs, y - 1, x, s, rr, tt, cc, cand); 93 + if (x - 1 >= 0) 94 + dfs2(R, C, K, roses, tulips, costs, y, x - 1, s, rr, tt, cc, cand); 95 + } 96 +}; 97 + 98 +// BEGIN CUT HERE 99 +#include <ctime> 100 +double start_time; string timer() 101 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 102 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 103 + { os << "{ "; 104 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 105 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 106 +void verify_case(const double& Expected, const double& Received) { 107 + bool ok = (abs(Expected - Received) < 1e-9); 108 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 109 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 110 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 111 +#define END verify_case(_, ProposalOptimization().bestPath(R, C, K, roses, tulips, costs));} 112 +int main(){ 113 + 114 +CASE(0) 115 + int R = 2; 116 + int C = 2; 117 + int K = 100; 118 + int roses_[] = {0, 2, 3, 0}; 119 + vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_)); 120 + int tulips_[] = {0, 3, 5, 0}; 121 + vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_)); 122 + int costs_[] = {0, 70, 80, 0}; 123 + vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 124 + double _ = 0.6666666666666667; 125 +END 126 +CASE(1) 127 + int R = 2; 128 + int C = 2; 129 + int K = 100; 130 + int roses_[] = {0, 2, 3, 0}; 131 + vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_)); 132 + int tulips_[] = {0, 3, 5, 0}; 133 + vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_)); 134 + int costs_[] = {0, 170, 100, 0}; 135 + vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 136 + double _ = 0.6; 137 +END 138 +CASE(2) 139 + int R = 3; 140 + int C = 3; 141 + int K = 98; 142 + int roses_[] = {0, 1, 1, 1, 1, 1, 1, 1, 0}; 143 + vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_)); 144 + int tulips_[] = {0, 1, 1, 1, 1, 1, 1, 1, 0}; 145 + vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_)); 146 + int costs_[] = {0, 33, 33, 33, 33, 33, 33, 33, 0}; 147 + vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 148 + double _ = -1.0; 149 +END 150 +CASE(3) 151 + int R = 5; 152 + int C = 9; 153 + int K = 622; 154 + 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}; 155 + vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_)); 156 + 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}; 157 + vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_)); 158 + 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}; 159 + vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 160 + double _ = 2.161290322580645; 161 +END 162 +CASE(4) 163 + int R = 2; 164 + int C = 3; 165 + int K = 15; 166 + int roses_[] = {0, 1, 3, 1, 1, 0}; 167 + vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_)); 168 + int tulips_[] = {0, 1, 2, 6, 1, 0}; 169 + vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_)); 170 + int costs_[] = {0, 1, 18, 9, 1, 0}; 171 + vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 172 + double _ = 1.0; 173 +END 174 +CASE(5) 175 + int R = 17; 176 + int C = 17; 177 + int K = 1000000000; 178 + 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 }; 179 + vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_)); 180 + 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 }; 181 + vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_)); 182 + 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 }; 183 + vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 184 + double _ = -2; 185 +END 186 +/* 187 +CASE(6) 188 + int R = 5; 189 + int C = 60; 190 + int K = 100000000; 191 + 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 }; 192 + vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_)); 193 + 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 }; 194 + vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_)); 195 + 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 }; 196 + vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 197 + double _ = -2; 198 +END 199 +*/ 200 +} 201 +// END CUT HERE