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 |
|
|
|
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 |