提出 #67007185

---

ソースコード 拡げる

import static java.lang.Math.*;
import static java.util.Arrays.*;

import java.io.*;
import java.lang.reflect.*;
import java.util.*;
import java.util.ArrayList;
import java.util.concurrent.*;
import java.util.function.*;

public class Main{
  public static void main(String[] args) throws Exception{
    MyReader in = new MyReader(System.in);
    MyWriter out = new MyWriter(System.out,false),log = new MyWriter(System.err,true);
    int T = Solver.multi ? in.it() : 1;
    while (T-- > 0)
      Optional.ofNullable(new Solver(in,out,log).solve()).ifPresent(out::println);
    out.flush();
  }
}

class Solver extends BaseSolver{
  public Solver(MyReader in,MyWriter out,MyWriter log){ super(in,out,log); }

  public static boolean multi = true;

  public Object solve(){
    int N = in.it();
    long W = in.lg();
    int[][] T = in.it(N,2);

    List<List<Long>> list = new ArrayList<>();
    for (int k = 0;k < 60;k++)
      list.add(new ArrayList<>());

    for (var t:T)
      list.get(t[0]).add(1L *t[1]);

    for (var lis:list)
      Collections.sort(lis);

    long ans = 0;
    while (true) {
      int k = -1;
      long sum = 0;

      for (int kk = 0;kk < 60;kk++) {
        if (1L <<kk > W)
          break;

        var q = list.get(kk);
        if (q.isEmpty())
          continue;
        long cur = q.get(q.size() -1);

        boolean ok = true;

        for (int j = 0;j < kk;j++) {
          var lis = list.get(j);
          if (lis.size() > 1 && sum +lis.get(lis.size() -2) >= cur) {
            ok = false;
            break;
          }
        }

        if (sum < cur && ok)
          k = kk;

        sum += cur;
      }

      if (k == -1)
        break;

      var lis = list.get(k);
      ans += lis.get(lis.size() -1);
      lis.remove(lis.size() -1);
      W -= 1L <<k;
    }

    return ans;

    //    long[] dp = new long[1 <<N];
    //    for (int bit = 0;bit < 1 <<N;bit++) {
    //      for (int i = 0;i < N;i++)
    //        if ((bit >>i &1) == 1)
    //          dp[bit] += T[i][1];
    //
    //      if (dp[bit] == 3102936938L)
    //        for (int i = 0;i < N;i++)
    //          if ((bit >>i &1) == 1)
    //            out.println(i);
    //    }
    //
    //    List<Queue<Integer>> list = new ArrayList<>();
    //    for (int k = 0;k < 60;k++)
    //      list.add(new ArrayDeque<>());
    //
    //    for (int i = 0;i < N;i++) {
    //      var t = T[i];
    //      list.get(t[0]).add(i);
    //    }
    //
    //    Set<Integer> used = new HashSet<>();
    //    long ans = 0;
    //    for (int k = 0;k < 60;k--) {
    //      if (1L <<k > W)
    //        continue;
    //      Queue<X> q = new PriorityQueue<>(Comparator.comparing(x -> -x.num));
    //      for (var i:list.get(0)) {
    //        var x = new X();
    //        x.id = i;
    //        x.num = T[i][1];
    //        q.add(x);
    //      }
    //
    //      for (int kk = 1;kk <= k;kk++) {
    //        Queue<X> nq = new PriorityQueue<>(Comparator.comparing(x -> -x.num));
    //        while (q.size() > 1) {
    //          var x = new X();
    //          var a = q.poll();
    //          var b = q.poll();
    //          x.id = -1;
    //          x.num = a.num +b.num;
    //          x.sub = new X[]{a, b};
    //          nq.add(x);
    //        }
    //        nq.addAll(q);
    //
    //        for (var i:list.get(kk)) {
    //          var x = new X();
    //          x.id = i;
    //          x.num = T[i][1];
    //          nq.add(x);
    //        }
    //        q = nq;
    //      }
    //
    //      if (q.isEmpty())
    //        break;
    //      var x = q.poll();
    //      long w = 0;
    //      long y = x.num;
    //
    //      Queue<X> que = new ArrayDeque<>();
    //      que.add(x);
    //      while (!que.isEmpty()) {
    //        var xx = que.poll();
    //        used.add(xx.id);
    //        if (xx.id != -1)
    //          w += 1L <<T[xx.id][0];
    //        else
    //          Collections.addAll(que,xx.sub);
    //      }
    //      ans += y;
    //      W -= w;
    //
    //      for (int kk = 0;kk < 60;kk++) {
    //        var qq = list.get(kk);
    //        int n = qq.size();
    //        while (n-- > 0) {
    //          var i = qq.poll();
    //          if (!used.contains(i))
    //            qq.add(i);
    //        }
    //
    //      }
    //
    //    }

  }

  private boolean calc(long[][] T,long x){

    return false;
  }
}

class X{
  int id;
  long num;
  X[] sub;
}

class Data extends BaseV{
  long v;

  public Data(long v){ this.v = v; }

  @Override
  public String toString(){ return String.valueOf(v); }
}

class PrefixSum{
  private long[] sum;
  private int i;

  public PrefixSum(int n){ sum = new long[n +1]; }

  public PrefixSum(long[] a){
    this(a.length);
    for (int i = 0;i < a.length;i++)
      sum[i +1] = sum[i] +a[i];
  }

  public void add(long a){ sum[i +1] = sum[i++] +a; }

  public long get(int l,int r){ return sum[r] -sum[l]; }

  public long get(int i){ return get(i,i +1); }
}

class UnionFind{
  int num;
  protected int[] dat;
  protected int[] nxt;

  public UnionFind(int n){
    dat = new int[n];
    nxt = new int[n];
    setAll(nxt,i -> i);
    fill(dat,-1);
    num = n;
  }

  public int root(int x){ return dat[x] < 0 ? x : (dat[x] = root(dat[x])); }

  public boolean same(int u,int v){ return root(u) == root(v); }

  public boolean unite(int u,int v){
    if ((u = root(u)) == (v = root(v)))
      return false;

    if (dat[u] > dat[v]) {
      u ^= v;
      v ^= u;
      u ^= v;
    }
    dat[u] += dat[v];
    dat[v] = u;
    num--;
    nxt[u] ^= nxt[v];
    nxt[v] ^= nxt[u];
    nxt[u] ^= nxt[v];
    return true;
  }

  public int size(int x){ return -dat[root(x)]; }

  public int[] getGroup(int x){
    int[] ret = new int[size(x)];
    for (int i = 0,c = root(x);i < ret.length;i++)
      ret[i] = c = nxt[c];
    return ret;
  }
}

abstract class SquareLong{
  private int b;
  private long[] val0,val1;

  public SquareLong(int n){ this(n,(int) sqrt(n) +1); }

  public SquareLong(int n,int b){
    this.b = b;
    int bn = (n +b -1) /b;
    val0 = new long[n];
    val1 = new long[bn];
    fill(val0,e());
    fill(val1,e());
  }

  protected abstract long e();
  protected abstract long agg(long a,long b);
  protected abstract long map(long v,long f);

  public void upd(int i,long f){
    val0[i] = map(val0[i],f);
    int bi = i /b;
    val1[bi] = agg(val1[bi],val0[i]);
  }

  public long get(int i){ return val0[i]; }

  public long get(int l,int r){
    long ret = e();

    if (r -l < b) {
      for (int i = l;i < r;i++)
        ret = agg(ret,val0[i]);
      return ret;
    }

    int lb = (l +b -1) /b;
    int rb = r /b;

    for (int i = l;i < lb *b;i++)
      ret = agg(ret,val0[i]);

    for (int i = lb;i < rb;i++)
      ret = agg(ret,val1[i]);

    for (int i = rb *b;i < r;i++)
      ret = agg(ret,val0[i]);
    return ret;
  }
}

class Edge<L> {
  public int id,u,v;
  public L val;
  public Edge<L> re;

  public Edge(int id,int u,int v,L val){
    this.id = id;
    this.u = u;
    this.v = v;
    this.val = val;
  }
}

class Graph<L> {
  protected int n;
  protected MyList<Edge<L>> es;
  private Edge<L>[][] go,bk;
  private int[] cntgo,cntbk;
  private boolean built;

  public Graph(int n,boolean dir){
    this.n = n;
    go = Util.cast(new Edge[n][]);
    bk = dir ? Util.cast(new Edge[n][]) : go;
    fill(go,new Edge[0]);
    fill(bk,new Edge[0]);
    es = new MyList<>();
    cntgo = new int[n];
    cntbk = dir ? new int[n] : cntgo;
  }

  public int size(){ return n; }

  protected L inv(L l){ return l; }

  public void addEdge(int u,int v){ addEdge(u,v,null); }

  public void addEdge(int u,int v,L l){
    var e = new Edge<>(es.size(),u,v,l);
    var re = new Edge<>(e.id,e.v,e.u,inv(e.val));
    es.add(e);
    re.re = e;
    e.re = re;
  }

  public Edge<L>[] go(int u){
    if (!built)
      build();
    return go[u];
  }

  public Edge<L>[] bk(int u){
    if (!built)
      build();
    return bk[u];
  }

  private void build(){
    for (var e:es) {
      cntgo[e.u]++;
      cntbk[e.v]++;
    }
    for (var e:es) {
      if (go[e.u].length == 0)
        go[e.u] = Util.cast(new Edge[cntgo[e.u]]);
      if (bk[e.v].length == 0)
        bk[e.v] = Util.cast(new Edge[cntbk[e.v]]);
    }
    for (var e:es) {
      go[e.u][--cntgo[e.u]] = e;
      bk[e.v][--cntbk[e.v]] = e.re;
    }
    built = true;
  }

  public void clear(){
    Edge<L>[] empty = Util.cast(new Edge[0]);
    for (var e:es)
      go[e.u] = bk[e.v] = empty;
    es.clear();
    built = false;
  }
}

abstract class BaseV{
  public int sz;
  public boolean fail;
}

class MyList<E> implements Iterable<E>{
  private E[] arr;
  private int hd,tl;

  public MyList(){ this(16); }

  public MyList(int n){ arr = Util.cast(new Object[Integer.highestOneBit(max(16,n) -1) <<1]); }

  public MyList(MyList<E> org){
    this(org.size() +1);
    System.arraycopy(org.arr,0,arr,0,tl = org.size());
  }

  public MyList(Collection<E> col){
    this(col.size() +1);
    col.forEach(this::add);
  }

  public void add(E t){ addLast(t); }

  public void addFirst(E e){
    hd = hd -1 &arr.length -1;
    arr[hd] = e;
    if (hd == tl)
      grow();
  }

  public void addLast(E e){
    arr[tl] = e;
    tl = tl +1 &arr.length -1;
    if (hd == tl)
      grow();
  }

  public E peek(){ return peekFirst(); }

  public E peekFirst(){ return arr[hd]; }

  public E peekLast(){ return arr[tl -1 &arr.length -1]; }

  public E poll(){ return pollFirst(); }

  public E pollFirst(){
    E ret = arr[hd];
    hd = hd +1 &arr.length -1;
    return ret;
  }

  public E pollLast(){
    tl = tl -1 &arr.length -1;
    return arr[tl];
  }

  public E get(int i){ return arr[hd +i &arr.length -1]; }

  public E remove(int i){
    i = hd +i &arr.length -1;
    E ret = arr[i];
    tl = tl -1 &arr.length -1;
    while (i != tl) {
      arr[i] = arr[i +1 &arr.length -1];
      i = i +1 &arr.length -1;
    }
    return ret;
  }

  public E removeFast(int i){
    swap(i,size() -1);
    return pollLast();
  }

  public void swap(int i,int j){
    i = hd +i &arr.length -1;
    j = hd +j &arr.length -1;
    Util.swap(arr,i,j);
  }

  public void set(int i,E t){ arr[hd +i &arr.length -1] = t; }

  public void clear(){ tl = hd; }

  public int size(){ return tl -hd &arr.length -1; }

  public boolean isEmpty(){ return tl == hd; }

  public void sort(){ sort(Util.cast(Comparator.naturalOrder())); }

  public void sort(Comparator<E> cmp){
    if (hd > tl)
      System.arraycopy(arr,hd,arr,tl,arr.length -hd);
    else
      System.arraycopy(arr,hd,arr,0,tl -hd);

    Arrays.sort(arr,hd = 0,tl = size(),cmp);
  }

  public <U> MyList<U> map(Function<E, U> func){
    MyList<U> ret = new MyList<>(size());
    forEach(t -> ret.add(func.apply(t)));
    return ret;
  }

  public MyList<E> rev(){
    MyList<E> ret = new MyList<>(size());
    for (int i = size();i-- > 0;)
      ret.add(get(i));
    return ret;
  }

  public int[] toIntArray(ToIntFunction<E> f){ return Util.arrI(size(),i -> f.applyAsInt(get(i))); }

  public E[] toArray(){
    if (hd == tl)
      return Util.cast(new Object[0]);
    E[] ret = Util.cast(Array.newInstance(arr[0].getClass(),size()));
    if (hd < tl)
      System.arraycopy(arr,hd,ret,0,tl -hd);
    else {
      System.arraycopy(arr,hd,ret,0,arr.length -hd);
      System.arraycopy(arr,0,ret,arr.length -hd,tl);
    }
    return ret;
  }

  private void grow(){
    E[] newarr = Util.cast(new Object[arr.length <<1]);
    System.arraycopy(arr,hd,newarr,0,arr.length -hd);
    System.arraycopy(arr,0,newarr,arr.length -hd,tl);
    hd = 0;
    tl = arr.length;
    arr = newarr;
  }

  @Override
  public Iterator<E> iterator(){
    return new Iterator<>(){
      int i = 0;

      @Override
      public boolean hasNext(){ return i < size(); }

      @Override
      public E next(){ return get(i++); }
    };
  }
}

class BaseSolver extends Util{
  public MyReader in;
  public MyWriter out,log;

  public BaseSolver(MyReader in,MyWriter out,MyWriter log){
    this.in = in;
    this.out = out;
    this.log = log;
  }

  public int[][] addId(int[][] T){
    return arr(new int[T.length][],i -> {
      int[] t = copyOf(T[i],T[i].length +1);
      t[t.length -1] = i;
      return t;
    });
  }

  public long inv(long x){ return pow(x,mod -2); }

  public long inv(long x,long mod){ return (extendGcd(x,mod)[0] +mod) %mod; }

  public long pow(long x,long n){ return pow(x,n,mod); }

  public long pow(long x,long n,long mod){
    long ret = 1;
    for (x %= mod;0 < n;x = x *x %mod,n >>= 1)
      if ((n &1) == 1)
        ret = ret *x %mod;
    return ret;
  }

  public int bSearchI(int o,int n,IntPredicate judge){
    for (int m = 0;1 < abs(n -o);)
      m = judge.test(m = o +n >>1) ? (o = m) : (n = m);
    return o;
  }

  public long bSearchL(long o,long n,LongPredicate judge){
    for (long m = 0;1 < abs(n -o);)
      m = judge.test(m = o +n >>1) ? (o = m) : (n = m);
    return o;
  }

  public double bSearchD(double o,double n,DoublePredicate judge){
    for (double m,c = 0;c < 100;c++)
      m = judge.test(m = (o +n) /2) ? (o = m) : (n = m);
    return o;
  }

  public long gcd(long a,long b){
    while (0 < b) {
      long t = a;
      a = b;
      b = t %b;
    }
    return a;
  }

  public long[] extendGcd(long a,long b){
    long x0 = 1,y0 = 0,x1 = 0,y1 = 1;
    while (b != 0) {
      long q = a /b,t = a %b,tx = x1,ty = y1;
      a = b;
      b = t;
      x1 = x0 -q *x1;
      y1 = y0 -q *y1;
      x0 = tx;
      y0 = ty;
    }
    return new long[]{x0, y0, a};
  }

  public long lcm(long a,long b){ return b /gcd(a,b) *a; }

  public long ceil(long a,long b){ return (a +b -1) /b; }

  public int[] lis(int[] arr){
    int n = arr.length;
    int[] lis = new int[n],idx = new int[n],par = new int[n];
    fill(lis,infI);

    int l = 0;
    for (int i = 0;i < n;i++) {
      int a = arr[i];
      int pos = bSearchI(n -1,-1,ii -> lis[ii] >= a);
      lis[pos] = a;
      idx[pos] = i;
      if (pos > 0)
        par[i] = idx[pos -1];
      l = max(l,pos +1);
    }

    int[] result = new int[l];
    for (int i = l -1,cur = idx[l -1];i >= 0;i--) {
      result[i] = arr[cur];
      cur = par[cur];
    }
    return result;
  }

  public void shift(char[][] S,char offset){
    for (var s:S)
      shift(s,offset);
  }

  public void shift(char[] s,char offset){
    for (int i = 0;i < s.length;i++)
      s[i] -= offset;
  }
}

class Util{
  public static String yes = "Yes",no = "No";
  public static int infI = (1 <<30) -1,mod = 998244353;
  public static long infL = (1L <<61 |1 <<30) -1;
  public static Random rd = ThreadLocalRandom.current();
  private long st = System.currentTimeMillis();

  protected long elapsed(){ return System.currentTimeMillis() -st; }

  protected void reset(){ st = System.currentTimeMillis(); }

  public static int[] arrI(int N,IntUnaryOperator f){
    int[] ret = new int[N];
    setAll(ret,f);
    return ret;
  }

  public static long[] arrL(int N,IntToLongFunction f){
    long[] ret = new long[N];
    setAll(ret,f);
    return ret;
  }

  public static double[] arrD(int N,IntToDoubleFunction f){
    double[] ret = new double[N];
    setAll(ret,f);
    return ret;
  }

  public static <T> T[] arr(T[] arr,IntFunction<T> f){
    setAll(arr,f);
    return arr;
  }

  @SuppressWarnings("unchecked")
  public static <T> T cast(Object obj){ return (T) obj; }

  public static <T> void swap(T[] arr,int i,int j){
    T t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
  }

  public static int min(int... arr){
    int ret = arr[0];
    for (int i = 1;i < arr.length;i++)
      ret = Math.min(ret,arr[i]);
    return ret;
  }

  public static long min(long... arr){
    long ret = arr[0];
    for (int i = 1;i < arr.length;i++)
      ret = Math.min(ret,arr[i]);
    return ret;
  }

  public static double min(double... arr){
    double ret = arr[0];
    for (int i = 1;i < arr.length;i++)
      ret = Math.min(ret,arr[i]);
    return ret;
  }

  public static int max(int... arr){
    int ret = arr[0];
    for (int i = 1;i < arr.length;i++)
      ret = Math.max(ret,arr[i]);
    return ret;
  }

  public static long max(long... arr){
    long ret = arr[0];
    for (int i = 1;i < arr.length;i++)
      ret = Math.max(ret,arr[i]);
    return ret;
  }

  public static double max(double... arr){
    double ret = arr[0];
    for (int i = 1;i < arr.length;i++)
      ret = Math.max(ret,arr[i]);
    return ret;
  }

  public static double sum(double... A){
    double ret = 0;
    for (var a:A)
      ret += a;
    return ret;
  }

  public static long sum(int... A){
    long ret = 0;
    for (var a:A)
      ret += a;
    return ret;
  }

  public static long sum(long... A){
    long ret = 0;
    for (var a:A)
      ret += a;
    return ret;
  }
}

class MyReader{
  private byte[] buf = new byte[1 <<16];
  private int ptr,tail;
  private InputStream in;

  public MyReader(InputStream in){ this.in = in; }

  private byte read(){
    if (ptr == tail)
      try {
        tail = in.read(buf);
        ptr = 0;
      } catch (IOException e) {}
    return buf[ptr++];
  }

  private boolean isPrintable(byte c){ return 32 < c && c < 127; }

  private byte nextPrintable(){
    byte ret = read();
    while (!isPrintable(ret))
      ret = read();
    return ret;
  }

  public int it(){ return toIntExact(lg()); }

  public int[] it(int N){ return Util.arrI(N,i -> it()); }

  public int[][] it(int H,int W){ return Util.arr(new int[H][],i -> it(W)); }

  public int idx(){ return it() -1; }

  public int[] idx(int N){ return Util.arrI(N,i -> idx()); }

  public int[][] idx(int H,int W){ return Util.arr(new int[H][],i -> idx(W)); }

  public long lg(){
    byte i = nextPrintable();
    boolean negative = i == 45;
    long n = negative ? 0 : i -'0';
    while (isPrintable(i = read()))
      n = 10 *n +i -'0';
    return negative ? -n : n;
  }

  public long[] lg(int N){ return Util.arrL(N,i -> lg()); }

  public long[][] lg(int H,int W){ return Util.arr(new long[H][],i -> lg(W)); }

  public double dbl(){
    String str = str();
    return Double.parseDouble(str);
  }

  public double[] dbl(int N){ return Util.arrD(N,i -> dbl()); }

  public double[][] dbl(int H,int W){ return Util.arr(new double[H][],i -> dbl(W)); }

  public char[] ch(){ return str().toCharArray(); }

  public char[][] ch(int H){ return Util.arr(new char[H][],i -> ch()); }

  public String line(){
    StringBuilder sb = new StringBuilder();
    for (byte c;(c = read()) != '\n';)
      sb.append((char) c);
    return sb.toString();
  }

  public String str(){
    StringBuilder sb = new StringBuilder();
    sb.append((char) nextPrintable());
    for (byte c;isPrintable(c = read());)
      sb.append((char) c);
    return sb.toString();
  }

  public String[] str(int N){ return Util.arr(new String[N],i -> str()); }

  public String[][] str(int H,int W){ return Util.arr(new String[H][],i -> str(W)); }
}

class MyWriter{
  private OutputStream out;
  private byte[] buf = new byte[1 <<16],ibuf = new byte[20];
  private int tail;
  private boolean autoflush;

  public MyWriter(OutputStream out,boolean autoflush){
    this.out = out;
    this.autoflush = autoflush;
  }

  public void flush(){
    try {
      out.write(buf,0,tail);
      tail = 0;
    } catch (IOException e) {
      e.printStackTrace();
    }
  }

  private void write(byte b){
    buf[tail++] = b;
    if (tail == buf.length)
      flush();
  }

  private void write(long n){
    if (n < 0) {
      n = -n;
      write((byte) '-');
    }
    int i = ibuf.length;
    do {
      ibuf[--i] = (byte) (n %10 +'0');
      n /= 10;
    } while (n > 0);
    while (i < ibuf.length)
      write(ibuf[i++]);
  }

  private void print(Object obj){
    if (obj instanceof Boolean)
      print((boolean) obj ? Util.yes : Util.no);
    else if (obj instanceof Integer)
      write((int) obj);
    else if (obj instanceof Long)
      write((long) obj);
    else if (obj instanceof char[])
      for (char b:(char[]) obj)
        write((byte) b);
    else if (obj.getClass().isArray()) {
      int l = Array.getLength(obj);
      for (int i = 0;i < l;i++) {
        print(Array.get(obj,i));
        if (i +1 < l)
          write((byte) ' ');
      }
    } else
      print(Objects.toString(obj).toCharArray());
  }

  public void println(Object obj){
    if (obj == null)
      obj = "null";
    if (obj instanceof Iterable<?>)
      for (Object e:(Iterable<?>) obj)
        println(e);
    else if (obj.getClass().isArray() && Array.getLength(obj) > 0 && Array.get(obj,0).getClass().isArray()) {
      int l = Array.getLength(obj);
      for (int i = 0;i < l;i++)
        println(Array.get(obj,i));
    } else {
      print(obj);
      write((byte) '\n');
      if (autoflush)
        flush();
    }
  }

  public void printlns(Object... obj){
    print(obj);
    write((byte) '\n');
    if (autoflush)
      flush();
  }
}

提出情報

ジャッジ結果