Submission #1589068


Source Code Expand

#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

// struct Edge{
// 	ll to, cap, cost, rev;
// };

// const int MAX_V = 256;
// int V;
// vector<Edge> G[MAX_V]; 
// ll dist[MAX_V];
// int prevv[MAX_V], preve[MAX_V];

// void add_edge(ll from, ll to, ll cap, ll cost) {
// 	G[from].push_back({to, cap, cost, (ll)G[to].size()});
// 	G[to].push_back({from, 0LL, -cost, (ll)G[from].size()-1});
// }

// ll min_cost_flow(int s, int t, ll f) {
// 	ll ret = 0LL;
// 	while(f > 0) {
//  		// fill(dist, dist+V, INF);
// 		rep(i, V) dist[i] = INF;
// 		dist[s] = 0LL;
// 		bool update = true;
// 		while(update) {
// 			update = false;
// 			for(int v = 0; v < V; ++v) {
// 				if(dist[v] == INF) continue;
// 				for(int i = 0; i < G[v].size(); ++i) {
// 					auto& e = G[v][i];
// 					if(e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
// 						dist[e.to] = dist[v] + e.cost;
// 						prevv[e.to] = v;
// 						preve[e.to]  = i;
// 						update = true;
// 						cout << e.to << " " << dist[e.to] << endl;
// 					}
// 				}
// 			}
// 		}
// 		if(dist[t] == INF) return ret;
// 		ll d = f;
// 		for(int v = t; v != s; v = prevv[v]) {
// 			d = min(d, G[prevv[v]][preve[v]].cap);
// 		}
// 		f -= d;
// 		ret += d * dist[t];
// 		for(int v = t; v != s; v = prevv[v]) {
// 			auto& e = G[prevv[v]][preve[v]];
// 			e.cap -= d;
// 			G[v][e.rev].cap += d;
// 		}
// 	}
// 	return ret;
// }

const int MAX_N = 60;
vector<int> es[MAX_N];
vector<int> d;

ll dfs(int cur, ll mask) {
	ll ret = 0LL;
	for(auto& to : es[cur]) {
		if(mask & (1<<to)) continue;
		ret = max(ret, dfs(to, mask | (1<<to)));
	}
	ret += d[cur];
	return ret;
}

int main(){
	int n, k;
	cin >> n >> k;
	d.resize(n);
	rep(i, n) cin >> d[i];
	rep(i, k) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		es[a].pb(b);
		es[b].pb(a);
	}
	ll ans = 0LL;
	rep(i, n) ans = max(ans, dfs(i, 1<<i));
	cout << ans << endl;
	// V = n * 2+2;
	// int source = n * 2;
	// int sink = n * 2 +1;
	// rep(i, n) {
	// 	ll d;
	// 	cin >> d;
	// 	add_edge(i*2, i*2+1, 1, -d);
	// }
	// rep(i, k) {
	// 	int x, y;
	// 	cin >> x >> y;
	// 	x--; y--;
	// 	add_edge(x*2+1, y*2, 1, 0);
	// 	add_edge(y*2+1, x*2, 1, 0);
	// }
	// rep(i, n) {
	// 	add_edge(source, i*2, 1, 0);
	// 	add_edge(i*2+1, sink, 1, 0);
	// }
	// cout << -min_cost_flow(source, sink, INF) << endl;
	return 0;
}

Submission Info

Submission Time
Task C - お金の街 (The Money Town)
User T1610
Language C++14 (GCC 5.4.1)
Score 50
Code Size 2935 Byte
Status WA
Exec Time 2 ms
Memory 256 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 50 / 50 0 / 50
Status
AC × 3
AC × 7
AC × 10
WA × 3
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
Subtask1 sample1.txt, sample2.txt, sample3.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt
Subtask2 sample1.txt, sample2.txt, sample3.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub2_1.txt, sub2_2.txt, sub2_3.txt, sub2_4.txt, sub2_5.txt, sub2_6.txt
Case Name Status Exec Time Memory
sample1.txt AC 1 ms 256 KB
sample2.txt AC 1 ms 256 KB
sample3.txt AC 1 ms 256 KB
sub1_1.txt AC 1 ms 256 KB
sub1_2.txt AC 1 ms 256 KB
sub1_3.txt AC 1 ms 256 KB
sub1_4.txt AC 1 ms 256 KB
sub2_1.txt AC 1 ms 256 KB
sub2_2.txt AC 2 ms 256 KB
sub2_3.txt AC 1 ms 256 KB
sub2_4.txt WA 1 ms 256 KB
sub2_5.txt WA 2 ms 256 KB
sub2_6.txt WA 2 ms 256 KB