fork download
copy 
  1. /*
  2. written by- Piyush Golani
  3. language- c++
  4. country- India
  5. College- N.I.T Jamshedpur
  6. */
  7. #include <cmath>
  8. #include <ctime>
  9. #include <iostream>
  10. #include <string>
  11. #include <vector>
  12. #include<cstdio>
  13. #include<sstream>
  14. #include<algorithm>
  15. #include<cstdlib>
  16. #include<cstring>
  17. #include<map>
  18. #include<set>
  19. #include<queue>
  20. #include<cctype>
  21. using namespace std;
  22. #define pb push_back
  23. #define all(s) s.begin(),s.end()
  24. #define f(i,a,b) for(int i=a;i<b;i++)
  25. #define F(i,a,b) for(int i=a;i>=b;i--)
  26. #define PI 3.1415926535897932384626433832795
  27. #define INF 2000000000
  28. #define BIG_INF 7000000000000000000LL
  29. #define mp make_pair
  30. #define eps 1e-9
  31. #define si(n) scanf("%d",&n)
  32. #define sll(n) scanf("%lld",&n)
  33. #define mod 1000000007
  34. #define mm 10000000
  35.  
  36. typedef long long LL;
  37.  
  38.  
  39. string inttostring(int n)
  40. {
  41.     stringstream a;
  42.     a<<n;
  43.     return a.str();
  44. }
  45.  
  46. int stringtoint(string A)
  47. {
  48.     istringstream a(A);
  49.     int p;
  50.     a>>p;
  51.     return p;
  52. }
  53.  
  54. //////////////////////////////////////////////////////
  55.  
  56.  
  57. class MagicMoleculeEasy {
  58. public:
  59.     vector<int> mp;
  60.     int a[1225],b[1225];
  61.     int e;
  62.     int n,best;
  63.     bool used[1225];
  64.     int rec(int p,int k)
  65.     {
  66.         if(p==e)
  67.         {
  68.             int res=0;
  69.             vector<int> x;
  70.             f(i,0,n)
  71.             {
  72.                 if(used[i])
  73.                 {
  74.                     res+=mp[i];
  75.                 }
  76.                 else
  77.                 {
  78.                     x.pb(mp[i]);
  79.                 }
  80.             }
  81.             sort(all(x),greater<int>() );
  82.             f(i,0,k) res+=x[i];
  83.             best=max(best,res);
  84.             return 0;
  85.         }
  86.         else
  87.         {
  88.             if(used[a[p]] || used[b[p]])
  89.             {
  90.                 rec(p+1,k);
  91.             }
  92.             else if(k>0)
  93.             {
  94.                 used[a[p]]=true;
  95.                 rec(p+1,k-1);
  96.                 used[a[p]]=false;
  97.                 used[b[p]]=true;
  98.                 rec(p+1,k-1);
  99.                 used[b[p]]=false;
  100.             }
  101.             return 0;
  102.         }
  103.     }
  104.    int maxMagicPower( vector <int> magicPower, vector <string> magicBond, int k ) {
  105.     this->mp=magicPower;
  106.     n=magicPower.size();
  107.     e=0;
  108.     f(i,0,n)
  109.     {
  110.         f(j,0,n)
  111.         {
  112.             if(magicBond[i][j]=='Y')
  113.             {
  114.                 a[e]=i;
  115.                 b[e++]=j;
  116.             }
  117.         }
  118.     }
  119.     fill(used,used+n,false);
  120.     best=-1;
  121.     rec(0,k);
  122.     return best;
  123.    }
  124. };
  125.  
  126. // BEGIN CUT HERE
  127. namespace moj_harness {
  128.     int run_test_case(int);
  129. 	void run_test(int casenum = -1, bool quiet = false) {
  130. 		if (casenum != -1) {
  131. 			if (run_test_case(casenum) == -1 && !quiet) {
  132. 				cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
  133. 			}
  134. 			return;
  135. 		}
  136.  
  137. 		int correct = 0, total = 0;
  138. 		for (int i=0;; ++i) {
  139. 			int x = run_test_case(i);
  140. 			if (x == -1) {
  141. 				if (i >= 100) break;
  142. 				continue;
  143. 			}
  144. 			correct += x;
  145. 			++total;
  146. 		}
  147.  
  148. 		if (total == 0) {
  149. 			cerr << "No test cases run." << endl;
  150. 		} else if (correct < total) {
  151. 			cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
  152. 		} else {
  153. 			cerr << "All " << total << " tests passed!" << endl;
  154. 		}
  155. 	}
  156.  
  157. 	int verify_case(int casenum, const int &expected, const int &received, clock_t elapsed) {
  158. 		cerr << "Example " << casenum << "... ";
  159.  
  160. 		string verdict;
  161. 		vector<string> info;
  162. 		char buf[100];
  163.  
  164. 		if (elapsed > CLOCKS_PER_SEC / 200) {
  165. 			sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
  166. 			info.push_back(buf);
  167. 		}
  168.  
  169. 		if (expected == received) {
  170. 			verdict = "PASSED";
  171. 		} else {
  172. 			verdict = "FAILED";
  173. 		}
  174.  
  175. 		cerr << verdict;
  176. 		if (!info.empty()) {
  177. 			cerr << " (";
  178. 			for (int i=0; i<(int)info.size(); ++i) {
  179. 				if (i > 0) cerr << ", ";
  180. 				cerr << info[i];
  181. 			}
  182. 			cerr << ")";
  183. 		}
  184. 		cerr << endl;
  185.  
  186. 		if (verdict == "FAILED") {
  187. 			cerr << "    Expected: " << expected << endl;
  188. 			cerr << "    Received: " << received << endl;
  189. 		}
  190.  
  191. 		return verdict == "PASSED";
  192. 	}
  193.  
  194. 	int run_test_case(int casenum__) {
  195. 		switch (casenum__) {
  196. 		case 0: {
  197. 			int magicPower[]          = {1, 2};
  198. 			string magicBond[]        = {"NY",
  199.  "YN"};
  200. 			int k                     = 1;
  201. 			int expected__            = 2;
  202.  
  203. 			clock_t start__           = clock();
  204. 			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
  205. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  206. 		}
  207. 		case 1: {
  208. 			int magicPower[]          = {100, 1, 100};
  209. 			string magicBond[]        = {"NYN",
  210.  "YNY",
  211.  "NYN"};
  212. 			int k                     = 1;
  213. 			int expected__            = 1;
  214.  
  215. 			clock_t start__           = clock();
  216. 			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
  217. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  218. 		}
  219. 		case 2: {
  220. 			int magicPower[]          = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
  221.  
  222. 			string magicBond[]        = {"NYYYYYYYYYYYYYYYYYYYYNYYNYYYYYYYYYYYYYYYYY", "YNYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYY", "YYNYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYY", "YYYNYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYN", "YYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYNYYYYNYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYY", "YYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYNYYYYYYYYYYNYYYYYYYYYYYYNYYYYYYYYYY", "YYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYNYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYY", "YYYYYNYYYYNYYNYYYYYYYYYYYYYYYYYYYNYYYYYYYY", "YYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYNYYYNYYYYYYYYYYYYNYYNYYYYYYYYY", "YYYNYYYYYYNYYNYYYYYYYYYYYYYYYYYYYYYYYYYYNY", "YYYYYYYYYYYYYYNYYYYYYYYYYYYYYYNYYYYYYYYYYY", "YYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYNYYYNYYYYYYYYYNNYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYNYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYNYYYYYYYYNNYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYY", "NYYYYNYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYNYYYYYNY", "YYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYY", "NYNYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYNYYYYYYYYYNYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYNYYYYYYYYYYNYYYYYYYYYYYYYY", "YNYYYYYYYNYYYYYYYYYNYYYYYYYYNYYYYYYYYYYNYY", "YYYYYYYYYYYYNYYYYYYNYYYYYYYYYNYYYYNYYYYYYY", "YYYYYYYYYYYYYYNYYYYYYYYYYYYYYYNYYYYYYYYYYY", "YYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYY", "YYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYNYYYYYYYNY", "YYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYNYYYYYNYY", "YYYYYYYYYYYYYYYYYYYYYYNYYYYYYNYYYYNYYYNYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYNYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNNYYNYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYNYYYYYNNY", "YYYYYYYYYYYYYNYYYYYYYYNYYYYYYYYYNYYYYYYNNY", "YYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYN"};
  223. 			int k                     = 13;
  224. 			int expected__            = -1;
  225.  
  226. 			clock_t start__           = clock();
  227. 			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
  228. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  229. 		}
  230. 		case 3: {
  231. 			int magicPower[]          = {4, 7, 5, 8};
  232. 			string magicBond[]        = {"NYNY",
  233.  "YNYN",
  234.  "NYNY",
  235.  "YNYN"};
  236. 			int k                     = 2;
  237. 			int expected__            = 15;
  238.  
  239. 			clock_t start__           = clock();
  240. 			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
  241. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  242. 		}
  243. 		case 4: {
  244. 			int magicPower[]          = {46474, 60848, 98282, 58073, 42670, 50373};
  245. 			string magicBond[]        = {"NYNNNY", "YNNYNY", "NNNYYY", "NYYNNN", "NNYNNN", "YYYNNN"};
  246. 			int k                     = 3;
  247. 			int expected__            = 209503;
  248.  
  249. 			clock_t start__           = clock();
  250. 			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
  251. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  252. 		}
  253. 		case 5: {
  254. 			int magicPower[]          = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
  255. 			string magicBond[]        = {"NNYYYNYYNYNNY", "NNYNYYYYYYYNY", "YYNYYNYYYYYYY", "YNYNYYNYYYYYY",
  256.  "YYYYNNYYYYYNY", "NYNYNNYYYYYNN", "YYYNYYNYYYYYY", "YYYYYYYNYNYYY",
  257.  "NYYYYYYYNYYYY", "YYYYYYYNYNNNN", "NYYYYYYYYNNYN", "NNYYNNYYYNYNN", "YYYYYNYYYNNNN"};
  258. 			int k                     = 9;
  259. 			int expected__            = -1;
  260.  
  261. 			clock_t start__           = clock();
  262. 			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
  263. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  264. 		}
  265. 		case 6: {
  266. 			int magicPower[]          = {1, 1};
  267. 			string magicBond[]        = {"NN", "NN"};
  268. 			int k                     = 1;
  269. 			int expected__            = 1;
  270.  
  271. 			clock_t start__           = clock();
  272. 			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
  273. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  274. 		}
  275. 		case 7: {
  276. 			int magicPower[]          = {1,1,2,5,2,4,2};
  277. 			string magicBond[]        = {"NNNNNNN","NNYNNNN","NYNNNYN","NNNNNNY","NNNNNNN","NNYNNNN","NNNYNNN"};
  278. 			int k                     = 3;
  279. 			int expected__            = 11;
  280.  
  281. 			clock_t start__           = clock();
  282. 			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
  283. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  284. 		}
  285.  
  286. 		// custom cases
  287.  
  288. /*      case 8: {
  289. 			int magicPower[]          = ;
  290. 			string magicBond[]        = ;
  291. 			int k                     = ;
  292. 			int expected__            = ;
  293.  
  294. 			clock_t start__           = clock();
  295. 			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
  296. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  297. 		}*/
  298. /*      case 9: {
  299. 			int magicPower[]          = ;
  300. 			string magicBond[]        = ;
  301. 			int k                     = ;
  302. 			int expected__            = ;
  303.  
  304. 			clock_t start__           = clock();
  305. 			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
  306. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  307. 		}*/
  308. /*      case 10: {
  309. 			int magicPower[]          = ;
  310. 			string magicBond[]        = ;
  311. 			int k                     = ;
  312. 			int expected__            = ;
  313.  
  314. 			clock_t start__           = clock();
  315. 			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
  316. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  317. 		}*/
  318. 		default:
  319. 			return -1;
  320. 		}
  321. 	}
  322. }
  323.  
  324.  
  325. int main(int argc, char *argv[]) {
  326. 	if (argc == 1) {
  327. 		moj_harness::run_test();
  328. 	} else {
  329. 		for (int i=1; i<argc; ++i)
  330. 			moj_harness::run_test(atoi(argv[i]));
  331. 	}
  332. }
  333. // END CUT HERE
  334.  
  335.  
  336.  
Runtime error #stdin #stdout 0s 3056KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uD8Tjy
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!