Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.InputStreamReader;
- import java.util.*;
- public class Solution {
- static Scanner in;
- public static void main(String[] args) {
- in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
- int t = Integer.parseInt(in.nextLine()); // Scanner has functions to read ints, longs, strings, chars, etc.
- for (int i = 1; i <= t; ++i) {
- solve(i);
- System.out.flush();
- }
- }
- public static void solve(int caseid) {
- int antCount = Integer.parseInt(in.nextLine());
- Iterator<Long> antWeights = Arrays.stream(in.nextLine().split(" ")).map(Long::parseLong).iterator();
- //Store length of stack and best weight
- HashMap<Integer, Long> records = new HashMap<>();
- records.put(0, 0L);
- //Loop through ants
- while(antWeights.hasNext()) {
- long antWeight = antWeights.next();
- //Check against all current records
- for(Map.Entry<Integer, Long> record : clone(records).entrySet()) {
- //Check if ant can be put below stack
- if(record.getValue() <= 6 * antWeight) {
- //Check if putting ant below stack improves solution
- long oldWeight = records.getOrDefault(record.getKey() + 1, Long.MAX_VALUE);
- long newWeight = record.getValue() + antWeight;
- if(newWeight < oldWeight) {
- //Save new record
- records.put(record.getKey() + 1, newWeight);
- }
- }
- }
- }
- //Find optimal solution
- int best = 0;
- for(Map.Entry<Integer, Long> record : records.entrySet()) {
- if(record.getKey() > best) {
- best = record.getKey();
- }
- }
- System.out.println("Case #" + caseid + ": " + best);
- }
- public static<K,V> Map<K,V> clone(Map<K,V> original) {
- Map<K,V> copy = new HashMap<>();
- copy.putAll(original);
- return copy;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement