結果
| 問題 | No.2161 Black Market |
| ユーザー |
 fgwiebfaoish
|
| 提出日時 | 2022-12-12 23:50:02 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 610 ms / 7,000 ms |
| コード長 | 11,646 bytes |
| コンパイル時間 | 1,283 ms |
| コンパイル使用メモリ | 115,200 KB |
| 実行使用メモリ | 76,396 KB |
| 最終ジャッジ日時 | 2024-11-06 21:26:08 |
| 合計ジャッジ時間 | 7,828 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 37 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
using System.Threading;
using System.Runtime.CompilerServices;
using System.Diagnostics;
using nint=System.Int64;
static class Program{
const long inf=long.MaxValue>>1;
const int mod=998244353;
static Sc sc=new Sc();
static void Main(){
Pt pt=new Pt(Solve);
pt.Sm();
}
static void Solve(Pt pt) {
var (n,k,l,p)=sc.Tp4<int>();
int f = n>>1;
int g = n-f;
var a = new int[f][];
var b = new int[g][];
for(int i = 0;i<f;i++) { a[i]=sc.Ia; }
for(int i = 0;i<g;i++) { b[i]=sc.Ia; }
int m = 1<<f;
var dp1 = new long[m];
var dp2 = new long[m];
var li = new List<(long c, long p)>[f+1];
for(int i = 0;i<=f;i++) { li[i]=new List<(long c, long p)>(); }
li[0].Add((0, 0));
for(int i = 1, j = 0;i<m;i++) {
if((1<<(j+1))<=i) { j++; }
dp1[i]=dp1[i-(1<<j)]+a[j][0];
dp2[i]=dp2[i-(1<<j)]+a[j][1];
li[Pc(i)].Add((dp1[i], dp2[i]));
}
var wm = new Wm[f+1];
for(int i = 0;i<=f;i++) {
li[i].Sort((u,v) => u.c.CompareTo(v.c));
var arr = li[i].Select(e => e.p).ToArray();
wm[i]=new Wm(arr);
}
m=1<<g;
dp1 = new long[m];
dp2 = new long[m];
long ans = 0;
Fu(0,0,0);
for(int i = 1, j = 0;i<m;i++) {
if((1<<(j+1))<=i) { j++; }
dp1[i]=dp1[i-(1<<j)]+b[j][0];
dp2[i]=dp2[i-(1<<j)]+b[j][1];
Fu(Pc(i),dp1[i],dp2[i]);
}
void Fu(int bn,long cn,long pn) {
if(l-cn<0) return;
for(int i = 0;bn+i<=k&&i<=f;i++) {
int lb = -1, ub = li[i].Count, mid = 0;
while(lb+1!=ub) {
mid=(ub+lb)/2;
if(li[i][mid].c>l-cn) { ub=mid; }
else { lb=mid; }
}
if(p-pn<=0) {
ans+=ub;
continue;
}
else if(lb>=0){
ans+=wm[i].Rm(0,lb,p-pn-1);
}
}
}
pt.Wl(ans);
}
static int Pc(int n) {
n-=(n>>1)&0x55555555;
n=(n&0x33333333)+((n>>2)&0x33333333);
return ((n+(n>>4)&0xF0F0F0F)*0x1010101)>>24;
}
}
static class Ex1 {
public static int Bs(this int[] a,int x,bool b) { return Bs2(a,x,b,a.Length); }
public static int Bs(this int[] a,int x,bool b,int ub) { return Bs2(a,x,b,ub+1); }
private static int Bs2(int[] a,int x,bool b,int ub) {
int lb = -1, mid = 0;
while(ub-lb>1) {
mid=(ub+lb)/2;
if(a[mid]>=x) { ub=mid; }
else { lb=mid; }
}
return b ? lb : ub;
}
}
public class Wm {
private int[][] ra;
private int[] za;
private const int b = 60;
private int n;
public Wm(nint[] a) {
n=a.Length;
var d = new int[b+1][];
ra=new int[b+1][];
for(int i = 0;i<=b;i++) {
d[i]=new int[n];
ra[i]=new int[n+1];
}
var d0 = new nint[2][] { new nint[n],new nint[n] };
var d1 = new nint[2][] { new nint[n],new nint[n] };
var h0 = new int[] { 0,0 };
var h1 = new int[] { 0,0 };
za=new int[b+1];
for(int i = 0;i<n;i++) {
if((a[i]&(1L<<b))==0) {
d0[1][h0[1]]=a[i];
h0[1]++;
za[b]++;
}
else {
d1[1][h1[1]]=a[i];
h1[1]++;
d[b][i]=ra[b][i+1]=1;
}
ra[b][i+1]+=ra[b][i];
}
for(int i = 1;i<=b;i++) {
nint g = 1L<<(b-i), p = i&1;
h0[p^1]=h1[p^1]=0;
for(int j = 0;j<h0[p];j++) {
if((d0[p][j]&g)==0) {
d0[p^1][h0[p^1]]=d0[p][j];
h0[p^1]++;
za[b-i]++;
}
else {
d1[p^1][h1[p^1]]=d0[p][j];
h1[p^1]++;
d[b-i][j]=ra[b-i][j+1]=1;
}
ra[b-i][j+1]+=ra[b-i][j];
}
for(int j = 0;j<h1[p];j++) {
if((d1[p][j]&g)==0) {
d0[p^1][h0[p^1]]=d1[p][j];
h0[p^1]++;
za[b-i]++;
}
else {
d1[p^1][h1[p^1]]=d1[p][j];
h1[p^1]++;
d[b-i][h0[p]+j]=ra[b-i][h0[p]+j+1]=1;
}
ra[b-i][h0[p]+j+1]+=ra[b-i][h0[p]+j];
}
}
}
public int Rk(int l,int r,long k) {
l--;
for(int i = b;i>=0;i--) {
if(((k>>i)&1)==1) {
r=ra[i][r+1]+za[i]-1;
l=ra[i][l+1]+za[i]-1;
}
else {
r=r-ra[i][r+1];
l=l-ra[i][l+1];
}
}
return r-l;
}
public int Rl(int l,int r,long k) {
l--;
int p = 0;
for(int i = b;i>=0;i--) {
if(((k>>i)&1)==1) {
p+=r-l;
r=ra[i][r+1]+za[i]-1;
l=ra[i][l+1]+za[i]-1;
p-=r-l;
}
else {
r=r-ra[i][r+1];
l=l-ra[i][l+1];
}
}
return p;
}
public int Rm(int l,int r,long k) {
l--;
int p = 0;
for(int i = b;i>=0;i--) {
if(((k>>i)&1)==1) {
r=ra[i][r+1]+za[i]-1;
l=ra[i][l+1]+za[i]-1;
}
else {
p+=r-l;
r=r-ra[i][r+1];
l=l-ra[i][l+1];
p-=r-l;
}
}
return p;
}
public nint Qt(int l,int r,int k) {
l--;
nint p = 0;
for(int i = b;i>=0;i--) {
if((r-ra[i][r+1])-(l-ra[i][l+1])<k) {
k-=(r-ra[i][r+1])-(l-ra[i][l+1]);
r=ra[i][r+1]+za[i]-1;
l=ra[i][l+1]+za[i]-1;
p|=1L<<i;
}
else {
r=r-ra[i][r+1];
l=l-ra[i][l+1];
}
}
return p;
}
public nint Pv(int l,int r,int k) {
int p = Rl(l,r,k);
return p!=0 ? Qt(l,r,p) : -1;
}
public nint Nv(int l,int r,int k) {
int p = Rm(l,r,k);
return p!=0 ? Qt(l,r,r-l+1-p+1) : -1;
}
}
public class Pt{
private StringBuilder sb=new StringBuilder();
public Pt(Action<Pt> f){f(this);}
public void W(int s){sb.Append(s);}
public void W(long s){sb.Append(s);}
public void W(double s){sb.Append(s);}
public void W(decimal s){sb.Append(s);}
public void W(char s){sb.Append(s);}
public void W(string s){sb.Append(s);}
public void W(object s){sb.Append(s);}
public void W(params object[] s){sb.Append(string.Join(" ",s));}
public void Wl(int s){sb.Append(s).AppendLine();}
public void Wl(long s){sb.Append(s).AppendLine();}
public void Wl(double s){sb.Append(s).AppendLine();}
public void Wl(decimal s){sb.Append(s).AppendLine();}
public void Wl(char s){sb.Append(s).AppendLine();}
public void Wl(string s){sb.AppendLine(s);}
public void Wl(object s){sb.Append(s).AppendLine();}
public void Wl(int[] s){sb.AppendLine(string.Join(" ",s));}
public void Wl(long[] s){sb.AppendLine(string.Join(" ",s));}
public void Wl(double[] s){sb.AppendLine(string.Join(" ",s));}
public void Wl(string[] s){sb.AppendLine(string.Join(" ",s));}
public void Wl(params object[] s){sb.AppendLine(string.Join(" ",s));}
public void Wl(){sb.AppendLine();}
public void Sm(){Console.Write(sb);}
public void Op(StreamWriter sw){
sw.Write(sb);
sw.Close();
}
public static bool operator ==(Pt a,Pt b){return a.sb.ToString()==b.sb.ToString();}
public static bool operator !=(Pt a,Pt b){return a.sb.ToString()!=b.sb.ToString();}
public override bool Equals(object obj){return false;}
public override int GetHashCode(){return 0;}
}
public class Sc{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
protected virtual string Rl(){return Console.ReadLine();}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
protected virtual string[] Sp(string st){return st.Split();}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private T Ct<T>(string s){return (T)Convert.ChangeType(s,typeof(T));}
public virtual int I{get{return int.Parse(Rl());}}
public virtual long L{get{return long.Parse(Rl());}}
public virtual double D{get{return double.Parse(Rl());}}
public virtual string S{get{return Rl();}}
public int[] Ia{get{return Array.ConvertAll(Sp(Rl()),int.Parse);}}
public long[] La{get{return Array.ConvertAll(Sp(Rl()),long.Parse);}}
public double[] Da{get{return Array.ConvertAll(Sp(Rl()),double.Parse);}}
public string[] Sa{get{return Sp(Rl());}}
public object[] Oa{get{return Sp(Rl());}}
public int[] Ia2{get{return Array.ConvertAll(Sp("0 "+Rl()+" 0"),int.Parse);}}
public int[] Ia3(string a,string b){return Array.ConvertAll(Sp(a+Rl()+b),int.Parse);}
public int[] Ia3(int a){return Array.ConvertAll(Sp(Rl()+" "+a.ToString()),int.Parse);}
public long[] La2{get{return Array.ConvertAll(Sp("0 "+Rl()+" 0"),long.Parse);}}
public long[] La3(string a,string b){return Array.ConvertAll(Sp(a+Rl()+b),long.Parse);}
public long[] La3(int a){return Array.ConvertAll(Sp(Rl()+" "+a.ToString()),long.Parse);}
public double[] Da2{get{return Array.ConvertAll(Sp("0 "+Rl()+" 0"),double.Parse);}}
public double[] Da3(string a,string b){return Array.ConvertAll(Sp(a+Rl()+b),double.Parse);}
public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Sp(Rl()));}return a;}
public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Sp(Rl()));}return a;}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public (T,T) Tp2<T>(){var s=Sp(Rl());return (Ct<T>(s[0]),Ct<T>(s[1]));}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public (T,T,T) Tp3<T>(){var s=Sp(Rl());return (Ct<T>(s[0]),Ct<T>(s[1]),Ct<T>(s[2]));}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public (T,T,T,T) Tp4<T>(){var s=Sp(Rl());return (Ct<T>(s[0]),Ct<T>(s[1]),Ct<T>(s[2]),Ct<T>(s[3]));}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public (T,T,T,T,T) Tp5<T>(){var s=Sp(Rl());return (Ct<T>(s[0]),Ct<T>(s[1]),Ct<T>(s[2]),Ct<T>(s[3]),Ct<T>(s[4]));}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public (T,T,T,T,T,T) Tp6<T>(){var s=Sp(Rl());return (Ct<T>(s[0]),Ct<T>(s[1]),Ct<T>(s[2]),Ct<T>(s[3]),Ct<T>(s[4]),Ct<T>(s[5]));}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public (T1,T2) Tp2<T1,T2>(){var s=Sp(Rl());return (Ct<T1>(s[0]),Ct<T2>(s[1]));}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public (T1,T1,T2) Tp3<T1,T2>(){var s=Sp(Rl());return (Ct<T1>(s[0]),Ct<T1>(s[1]),Ct<T2>(s[2]));}
}
public class Scr:Sc{
private List<string> li=new List<string>();
private int l=0;
private bool bo=false;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
protected override string Rl(){
if(bo){return li[l++%li.Count];}
li.Add(Console.ReadLine());
return li[li.Count-1];
}
public void Again(){bo=true;}
}
public class Scs:Sc{
private StreamReader sr;
public Scs(string t){sr=new StreamReader(t);}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
protected override string Rl(){return sr.ReadLine();}
public void Close(){sr.Close();}
}
public class Sc2:Sc{
private string[] sps=new string[]{" "," ","\t"};
[MethodImpl(MethodImplOptions.AggressiveInlining)]
protected override string[] Sp(string st){return st.Split(sps,StringSplitOptions.RemoveEmptyEntries);}
public override int I{get{return int.Parse(Sp(Rl())[0]);}}
public override long L{get{return long.Parse(Sp(Rl())[0]);}}
public override double D{get{return double.Parse(Sp(Rl())[0]);}}
public override string S{get{return Sp(Rl())[0];}}
}
public class Scs2:Sc2{
private StreamReader sr;
public Scs2(string t){sr=new StreamReader(t);}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
protected override string Rl(){return sr.ReadLine();}
public void Close(){sr.Close();}
}
public class Sct:Sc{
private List<string> li=new List<string>();
private int l=0;
public void Add(int s){li.Add(s.ToString());}
public void Add(long s){li.Add(s.ToString());}
public void Add(double s){li.Add(s.ToString());}
public void Add(string s){li.Add(s.ToString());}
public void Add(object s){li.Add(s.ToString());}
public void Add(int[] s){li.Add(string.Join(" ",s));}
public void Add(long[] s){li.Add(string.Join(" ",s));}
public void Add(double[] s){li.Add(string.Join(" ",s));}
public void Add(string[] s){li.Add(string.Join(" ",s));}
public void Add(params object[] s){li.Add(string.Join(" ",s));}
protected override string Rl(){return li[l++];}
public void Clear(){li.Clear();l=0;}
public void Again(){l=0;}
public void Pf(){Console.WriteLine(string.Join("\n",li));}
}