結果
問題 |
No.1736 Princess vs. Dragoness
|
ユーザー |
![]() |
提出日時 | 2021-11-12 22:59:48 |
言語 | Java (openjdk 23) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,196 bytes |
コンパイル時間 | 2,297 ms |
コンパイル使用メモリ | 78,632 KB |
実行使用メモリ | 52,432 KB |
最終ジャッジ日時 | 2024-11-25 21:01:08 |
合計ジャッジ時間 | 6,006 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 WA * 4 |
ソースコード
import java.io.*; import java.util.*; class Main { public static void main(String args[])throws Exception { BufferedReader bu=new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb=new StringBuilder(); String s[]=bu.readLine().split(" "); int n=Integer.parseInt(s[0]),a=Integer.parseInt(s[1]),b=Integer.parseInt(s[2]),x=Integer.parseInt(s[3]),y=Integer.parseInt(s[4]); int i,h[]=new int[n]; s=bu.readLine().split(" "); for(i=0;i<n;i++) h[i]=Integer.parseInt(s[i]); int l=0,r=(int)1e9,mid,ans=r; /*while(l<=r) { mid=(l+r)>>1; if(possible(h,a,b,x,y,mid)) { ans=mid; r=mid-1; } else l=mid+1; }*/ if(possible(h,a,b,x,y,0)) sb.append("Yes\n"); else sb.append("No\n"); System.out.print(sb); } static boolean possible(int h[],int a,int b,int x,int y,int k) { int i,n=h.length; for(i=0;i<n;i++) h[i]-=k; TreeMap<Integer,Integer> tm=new TreeMap<>(); long del=1l*b*y; int sz=0; for(i=0;i<n;i++) if(h[i]>0) { long tem=Math.min(del,h[i]); //use y values here del-=tem; h[i]-=tem; long ti=tem/x; while(ti-->0) { if(sz<a) { sz++; tm.put(x,tm.getOrDefault(x,0)+1); } else if(sz==a) { int lo=tm.higherKey(-1); if(lo<x) { remove(tm,lo); tm.put(x,tm.getOrDefault(x,0)+1); } else break; } else break; } if(tem%x!=0 && a>0) { int val=(int)(tem%x); if(sz<a) { sz++; tm.put(val,tm.getOrDefault(val,0)+1); } else if(sz==a) { int lo=tm.higherKey(-1); if(lo<val) { remove(tm,lo); tm.put(val,tm.getOrDefault(val,0)+1); } } } while(h[i]>del && !tm.isEmpty()) { int key=tm.lowerKey(x+1); del+=key; remove(tm,key); a--; //using a sz--; } tem=Math.min(h[i],del); del-=tem; h[i]-=tem; //still now h[i]>0 ti=h[i]/x; if(h[i]%x!=0) ti++; if(ti>a) return false; a-=ti; while(sz>a) { int lo=tm.higherKey(-1); remove(tm,lo); sz--; } } return true; } static void remove(TreeMap<Integer,Integer> tm,int x) { int v=tm.get(x); if(v==1) tm.remove(x); else tm.put(x,v-1); } }