結果
問題 | No.951 【本日限定】1枚頼むともう1枚無料! |
ユーザー |
|
提出日時 | 2019-12-15 01:38:18 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,177 ms / 2,000 ms |
コード長 | 2,030 bytes |
コンパイル時間 | 2,338 ms |
コンパイル使用メモリ | 79,512 KB |
実行使用メモリ | 347,880 KB |
最終ジャッジ日時 | 2024-06-28 10:23:00 |
合計ジャッジ時間 | 39,253 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 52 |
ソースコード
import java.io.*; import java.util.*; class Main { public static void main(String[] args) { new Main().run(); } class SegTree{ int n; int[] v; public SegTree(int n){ this.n=1; while(this.n<n)this.n=2*this.n; v=new int[2*this.n-1]; Arrays.fill(v,0); } void update(int k,int val){ k+=n-1; v[k]=Math.max(v[k],val); while(k>0){ k=(k-1)/2; v[k]=Math.max(v[2*k+1],v[2*k+2]); } } int query(int a,int b){ return query(0,n,a,b,0); } int query(int l,int r,int a,int b,int k){ if(a<=l&&r<=b) return v[k]; else if(r<=a||b<=l) return 0; else{ int vl=query(l,(l+r)/2,a,b,2*k+1); int vr=query((l+r)/2,r,a,b,2*k+2); return Math.max(vl,vr); } } } void run() { Scanner sc=new Scanner(System.in); int N=sc.nextInt(); int K=sc.nextInt(); int[] P=new int[N+1]; int[] D=new int[N+1]; int[][] a=new int[N+1][2]; for(int i=0;i<N;++i){ P[i]=sc.nextInt(); D[i]=sc.nextInt(); } P[N]=0; D[N]=0; for(int i=0;i<=N;++i){ a[i][0]=P[i]; a[i][1]=D[i]; } Arrays.sort(a,new Comparator<int[]>(){ public int compare(int[] a,int[] b){ if(a[0]!=b[0]) return Integer.compare(a[0],b[0]); else return Integer.compare(a[1],b[1]); } }); ++N; int[][] dp=new int[K+1][N]; int[][] ma=new int[K+1][N]; for(int i=0;i<=K;++i){ for(int j=0;j<N;++j){ dp[i][j]=-Integer.MAX_VALUE/3; ma[i][j]=-Integer.MAX_VALUE/3; } } int[][] seg=new int[K+1][N+10]; for(int i=0;i<=K;++i){ for(int j=0;j<N;++j){ dp[i][j]=Math.max((i>0?dp[i-1][j]:0),(j>0?dp[i][j-1]:0)); ma[i][j]=Math.max((i>0?ma[i-1][j]:0),(j>0?ma[i][j-1]:0)); if(i-a[j][0]>=0){ dp[i][j]=Math.max(dp[i][j],a[j][1]+(j>0?seg[i-a[j][0]][j-1]:0)); } if(j+1<N) seg[i][j+1]=Math.max(seg[i][j+1],dp[i][j]+a[j+1][1]); seg[i][j+1]=Math.max(seg[i][j+1],seg[i][j]); } } System.out.println(dp[K][N-1]); } void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }