fork download
copy 
  1. #include <cmath>
  2. #include <ctime>
  3. #include <iostream>
  4. #include <string>
  5. #include <vector>
  6. #include<cstdio>
  7. #include<sstream>
  8. #include<algorithm>
  9. #include<cstdlib>
  10. #include<cstring>
  11. #include<map>
  12. #include<set>
  13. #include<queue>
  14. #include<cctype>
  15. #include <iomanip>
  16. #include <string>
  17. #include <sstream>
  18. #include <functional>
  19. #include <numeric>
  20. #include <stack>
  21. #include <climits>
  22. #include <float.h>
  23. #include<unordered_map>
  24. #include <bitset>
  25.  
  26. using namespace std;
  27.  
  28. #define pb push_back
  29. #define mp make_pair
  30. #define ff first
  31. #define ss second
  32. #define rep(i, n) for(int i = 0; i < (n); ++i)
  33. #define f(i,a,b) for(int i=a;i<b;i++)
  34. #define F(i,a,b) for(int i=a;i>=    b;i--)
  35. #define sz(a) ((int)a.size())
  36. #define all(c) c.begin(), c.end()
  37. #define fast ios_base::sync_with_stdio(0);cin.tie(0);
  38. #define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
  39. #define dbg(x) cerr << (#x) << " --> " << (x) << endl
  40.  
  41.  
  42. typedef long long ll;
  43. typedef unsigned long long ull;
  44. typedef pair <ll, ll> pll;
  45. typedef vector<ll> vll;
  46. typedef vector<int> vi;
  47. typedef vector<string> vs;
  48. typedef vector<pair<int, int> > vpii;
  49. typedef map<int, int> mii;
  50. typedef map<ll, ll> mll;
  51. typedef pair<int, int> pii;
  52. typedef pair<string, int> psi;
  53. typedef long double ld;
  54.  
  55.  
  56. template <class T> const T& max(const T& a, const T&b, const T&c) { return max(a, max(b, c)); }
  57.  
  58. template <class T> const T& min(const T& a, const T&b, const T&c) { return min(a, min(b, c)); }
  59.  
  60.  
  61.  
  62. ll gcd(ll a, ll b){ if (b == 0) return a; return gcd(b, a % b); }
  63.  
  64. ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
  65.  
  66. ll poww(ll a, ll b) {
  67.  
  68. 	if (b == 0) return 1;
  69.  
  70. 	ll tmp = poww(a, b / 2);
  71.  
  72. 	return (b & 1 ? a * tmp * tmp : tmp * tmp);
  73.  
  74. }
  75.  
  76.  
  77.  
  78. ll sumOfDigs(string s) { ll sum = 0; for (int i = 0; i < s.length(); i++) sum += s[i] - '0'; return sum; }
  79.  
  80. ll sumOfDigs(ll n) { return (n < 10 ? n : n % 10 + sumOfDigs(n / 10)); }
  81.  
  82. string itos(ll i) { string s = ""; 	while (i) { s += char(i % 10 + '0'); i /= 10; } reverse(all(s));  return s; }
  83.  
  84. ll stoi(string &s) { ll tot = 0; for (int i = (int)s.length() - 1, j = 1; i >= 0; i--, j *= 10) { tot += j * (s[i] + '0'); }  return tot; }
  85.  
  86.  
  87. int months[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
  88.  
  89.  
  90. using namespace std;
  91.  
  92. #define PI acos((ld)-1.0) 
  93.  
  94.  
  95.  
  96. void t(){
  97.  
  98. #ifndef online_judge
  99. 	freopen("test.txt", "r", stdin);
  100. #endif
  101. }
  102.  
  103.  
  104. ll fact[1000 * 1000];
  105.  
  106. ll mod = 1e9 + 7;
  107.  
  108. ll modpower(ll x, ll y, ll p)
  109. {
  110.  
  111. 	x %= mod;
  112.  
  113. 	if (!y) return 1;
  114.  
  115. 	ll res = 1;
  116.  
  117. 	if (y & 1) { res *= x;  res %= p; }
  118.  
  119. 	ll z = modpower(x, y / 2, p);
  120.  
  121. 	z %= p;
  122.  
  123. 	z *= z;
  124.  
  125. 	z %= mod;
  126.  
  127. 	res *= z;
  128.  
  129. 	res %= p;
  130.  
  131. 	return res;
  132.  
  133. }
  134.  
  135.  
  136. int n, m;
  137.  
  138. int c[1000], conn[1000][1000], val[1 << 18], dp[1 << 18], cnt[1 << 18];
  139.  
  140.  
  141. int main(){
  142.  
  143. 	cin >> n >> m;
  144.  
  145. 	for (int i = 0; i < n; i++) cin >> c[i];
  146.  
  147. 	for (int i = 1; i <= m; i++) {
  148.  
  149. 		int a, b;
  150. 		cin >> a >> b;
  151. 		a--, b--;
  152. 		conn[a][b] = conn[b][a] = 1;
  153.  
  154. 	}
  155.  
  156. 	int N = n / 2;
  157.  
  158.  
  159. 	for (int i = 0; i < (1 << N); i++) {
  160.  
  161. 		int cost = 0;
  162.  
  163. 		vi v;
  164.  
  165. 		for (int j = 0; j < N; j++) if (i & (1 << j)) { cost += c[j];  v.pb(j); }
  166.  
  167. 		int poss = 1;
  168.  
  169. 		for (int j = 0; j < v.size(); j++) for (int k = j + 1; k < v.size(); k++) if (conn[v[j]][v[k]]) { poss = 0; break; }
  170.  
  171. 		if (poss) val[i] = cost;
  172.  
  173. 	}
  174.  
  175.  
  176. 	for (int i = 0; i < (1 << N); i++) {
  177.  
  178. 		for (int submask = i;; submask = (submask - 1) & i) {
  179.  
  180. 			if (dp[i] < val[submask]) { dp[i] = val[submask]; cnt[i] = 1; }
  181.  
  182. 			else if (dp[i] == val[submask]) { cnt[i]++; }
  183.  
  184. 			if (!submask) break;
  185. 		}
  186.  
  187.  
  188. 	}
  189.  
  190.  
  191. 	int mxCost = 0, mxCnt = 0;
  192.  
  193. 	for (ll i = 0; i < (1ll << n); i += (1 << N)) {
  194.  
  195. 		int cost = 0;
  196. 		vi v;
  197.  
  198. 		for (int j = N; j < n; j++) if (i & (1 << j)) { v.pb(j); cost += c[j]; }
  199.  
  200. 		int poss = 1;
  201.  
  202. 		for (int j = 0; j < v.size(); j++) for (int k = j + 1; k < v.size(); k++) if (conn[v[j]][v[k]]) { poss = 0; break; }
  203.  
  204. 		if (poss){
  205.  
  206. 			int mask = (1 << N) - 1;
  207. 			for (int j = 0; j < v.size(); j++) {
  208.  
  209. 				for (int k = 0; k < N; k++) if (conn[k][v[j]]) mask = mask & ~(1 << k);
  210.  
  211.  
  212. 			}
  213.  
  214.  
  215. 			cost += dp[mask];
  216.  
  217. 			if (cost > mxCost) { mxCost = cost; mxCnt = cnt[mask]; }
  218.  
  219. 			else if (cost == mxCost) { mxCnt += cnt[mask]; }
  220.  
  221. 		}
  222.  
  223.  
  224. 	}
  225.  
  226.  
  227. 	cout << mxCost << " " << mxCnt << endl;
  228.  
  229. 	return 0;
  230. }
  231.  
  232.  
  233.  
Success #stdin #stdout 0s 18256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 1
https://ideone.com/ipaB6s
language:
C++14 (gcc 8.3)
created:
8 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!