Advertisement
OIQ

Dadaya

OIQ
Oct 13th, 2019
254
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.Scanner;
  2. import java.util.ArrayList;
  3.  
  4. public class task4178 {
  5.    
  6.  
  7.     public static void main(String[] args) {
  8.  
  9.             Scanner in = new Scanner(System.in);
  10.  
  11.                 int n = in.nextInt();
  12.                     long W = in.nextLong();
  13.  
  14.                     long[] value = new long[n];
  15.                     long[] width = new long[n];
  16.    
  17.                     for (int i = 0; i < n; i++) {
  18.                         width[i] = in.nextLong();
  19.                         value[i] = in.nextLong();
  20.                     }
  21.    
  22.                     int k = (int) Math.pow(2, n + 1);
  23.                    
  24.                     int c = 0;
  25.                     long w1 = 0;
  26.                     long v1 = 0;
  27.                     long w2 = 0;
  28.                     long v2 = 0;
  29.                     int count = 0;
  30.                     ArrayList<pairs> t = new ArrayList<>();
  31.    
  32.                     for (int i = 0; i < k; i++) {
  33.                         w2 = 0;
  34.                         v2 = 0;
  35.                         count = 0;
  36.    
  37.                         for (int j = 0; j < n; j++) {
  38.                             if ((i & (1 << j)) != 0) {
  39.                                     w2 += width[j];
  40.                                     v2 += value[j];
  41.                                     count++;
  42.                             }
  43.                         }
  44.    
  45.                         if (w2 <= W && v2 >= v1) {
  46.                             t.add(new pairs(count, i, v2));
  47.                             v1 = v2;
  48.                             w1 = w2;
  49.                             //c = i;
  50.                         }
  51.    
  52.    
  53.                     }
  54.                    
  55.                     if (t.isEmpty()) {
  56.                         System.out.print(0 + " " + 0);
  57.                         System.exit(0);
  58.                     }
  59.                     long curr = t.get(t.size() - 1).z;
  60.                    
  61.                     while (t.get(0).z != curr)
  62.                         t.remove(0);
  63.                    
  64.                     int min = 20;
  65.                     int ind = -1;
  66.                    
  67.                     for (int i = 0; i < t.size(); i++)
  68.                         if (t.get(i).x < min) {
  69.                             min = t.get(i).x;
  70.                             ind = i;
  71.                         }
  72.                    
  73.                    
  74.  
  75.                     System.out.println(t.get(ind).x + " " + t.get(ind).z);
  76.                     int num = t.get(ind).y;
  77.                    
  78.                     for (int i = 0; i <= 20; i++)
  79.                         if ((num & (1 << i)) != 0 )
  80.                                 System.out.print((i +1) + " ");
  81.                    
  82.                    
  83.                    
  84.                    
  85.    
  86.         }
  87.     }
  88.  
  89. class pairs {
  90.     int x;
  91.     int y;
  92.     long z;
  93.    
  94.     public pairs(int a, int b, long c) {
  95.         x = a;
  96.         y = b;
  97.         z = c;
  98.     }
  99. }
Advertisement
RAW Paste Data Copied
Advertisement