Cerinta completa
Killgrave wants to use his mind control powers to get money from the Justice League superheroes living in houses in Happy Harbor that are numbered sequentially from to . There are roads, and each road connects two different houses, and . Each superhero house (where ) has dollars stashed away for a rainy day.
As long as a superhero is home at house , Killgrave knows they will hand over all of their saved money, . Once he gets money from them, he moves on to the next house. However, the superheroes are cunning; when Killgrave comes to house , every neighbor immediately connected to house by a single road skips town for a couple of days (making it impossible for Killgrave to get money from them). In other words, after Killgrave visits all the superheroes he wants, there will be no road in which he was able to get money from both houses on either end of the road.
What is the maximum amount of money Killgrave can collect from the superheroes, and how many different ways can Killgrave get that amount of money? Two ways are considered to be different if the sets of visited houses are different.
Note: Killgrave can start at an arbitrary house and doesn’t have to only use the roads.
Input Format
The first line contains two space-separated integers, (the number of houses) and (the number of roads), respectively.
The second line contains space-separated integers, where each integer describes the amount of money, , at house .
Each line of the subsequent lines contains two space-separated integers defining a road connecting houses and . Every road connects a different pair of houses.
Constraints
- , where
- No unordered pair will appear more than once.
Output Format
Print two space-separated integers:
- The first integer must denote the maximum amount of money Killgrave can get out of the Justice League.
- The second integer must denote the number of different ways he can collect that amount of money.
Sample Input
3 2
6 8 2
1 2
3 2
Sample Output
8 2
Explanation
Killgrave has two possible courses of action:
- Visit house and get dollars.
- Visit houses and and get dollars.
Both of these options result in dollars, so we know that this is maximal. Thus, we print the maximum amount of money () followed by the number of ways he can get that amount of money () as two space-separated values on a single line.
Limbajul de programare folosit: java8
Cod:
import java.io.*;
import java.util.*;
public class Solution {
private static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { this.in = is; }
private int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c;
do { c = read(); } while (c <= ' ' && c != -1);
int sign = 1;
if (c == '-') { sign = -1; c = read(); }
int val = 0;
while (c > ' ') {
val = val * 10 + (c - '0');
c = read();
}
return val * sign;
}
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
int n = fs.nextInt();
int m = fs.nextInt();
int[] c = new int[n];
for (int i = 0; i < n; i++) c[i] = fs.nextInt();
long[] adj = new long[n];
for (int i = 0; i < m; i++) {
int u = fs.nextInt() - 1;
int v = fs.nextInt() - 1;
adj[u] |= 1L << v;
adj[v] |= 1L << u;
}
int n1 = n / 2;
int n2 = n - n1;
long[] adj1 = new long[n1];
long[] crossTo2 = new long[n1];
long[] adj2 = new long[n2];
for (int i = 0; i < n1; i++) {
long mask = adj[i];
adj1[i] = mask & ((1L << n1) - 1L);
crossTo2[i] = (mask >>> n1) & ((1L << n2) - 1L);
}
for (int i = 0; i < n2; i++) {
long mask = adj[n1 + i] >>> n1;
adj2[i] = mask & ((1L << n2) - 1L);
}
int size1 = 1 << n1;
int size2 = 1 << n2;
boolean[] indep1 = new boolean[size1];
long[] w1 = new long[size1];
int[] forb2 = new int[size1];
indep1[0] = true;
for (int mask = 1; mask < size1; mask++) {
int bit = Integer.numberOfTrailingZeros(mask);
int prev = mask & (mask - 1);
indep1[mask] = indep1[prev] && (((adj1[bit]) & (long) prev) == 0L);
w1[mask] = w1[prev] + c[bit];
forb2[mask] = forb2[prev] | (int) crossTo2[bit];
}
boolean[] indep2 = new boolean[size2];
long[] w2 = new long[size2];
indep2[0] = true;
for (int mask = 1; mask < size2; mask++) {
int bit = Integer.numberOfTrailingZeros(mask);
int prev = mask & (mask - 1);
indep2[mask] = indep2[prev] && (((adj2[bit]) & (long) prev) == 0L);
w2[mask] = w2[prev] + c[n1 + bit];
}
long NEG = Long.MIN_VALUE / 4;
long[] best = new long[size2];
long[] ways = new long[size2];
for (int mask = 0; mask < size2; mask++) {
if (indep2[mask]) {
best[mask] = w2[mask];
ways[mask] = 1;
} else {
best[mask] = NEG;
ways[mask] = 0;
}
}
for (int b = 0; b < n2; b++) {
for (int mask = 0; mask < size2; mask++) {
if ((mask & (1 << b)) == 0) continue;
int sub = mask ^ (1 << b);
if (best[sub] > best[mask]) {
best[mask] = best[sub];
ways[mask] = ways[sub];
} else if (best[sub] == best[mask]) {
ways[mask] += ways[sub];
}
}
}
int full2 = size2 - 1;
long maxMoney = NEG;
long countWays = 0;
for (int mask = 0; mask < size1; mask++) {
if (!indep1[mask]) continue;
int allowed2 = full2 & (~forb2[mask]);
long total = w1[mask] + best[allowed2];
if (total > maxMoney) {
maxMoney = total;
countWays = ways[allowed2];
} else if (total == maxMoney) {
countWays += ways[allowed2];
}
}
System.out.println(maxMoney + " " + countWays);
}
}
Scor obtinut: 1.0
Submission ID: 464618168
Link challenge: https://www.hackerrank.com/challenges/borrowing-money/problem