Submission #1613138
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; //太特么厉害了,逆天了 //这个也能二分,太巧妙了, #define MS(a) memset(a,0,sizeof(a)) #define MP make_pair #define PB push_back const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } ////////////////////////////////////////////////////////////////////////// const int maxn = 1e5+10; ll x[maxn],k[maxn]; ll n,a,b; bool check(ll t) { memcpy(k,x,sizeof(x)); for(ll i=1; i<=n; i++) { k[i] -= t*b; } ll more = (a-b),cnt=0; for(ll i=1; i<=n; i++) { if(k[i]>0) cnt += (k[i]%more==0) ? (k[i]/more) : (k[i]/more+1); } return cnt <= t; } int main() { cin >> n >> a >> b; for(int i=1; i<=n; i++) { x[i] = read(); } ll ans,L=1,R=1e9; while(L<=R) { ll mid = (L+R)/2; if(check(mid)) ans=mid,R=mid-1; else L=mid+1; } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Widespread |
User | yuxiaokang |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 1276 Byte |
Status | AC |
Exec Time | 43 ms |
Memory | 1792 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | a01, a02, a03 |
All | a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
a01 | AC | 3 ms | 1024 KB |
a02 | AC | 3 ms | 1024 KB |
a03 | AC | 3 ms | 1024 KB |
b04 | AC | 3 ms | 1024 KB |
b05 | AC | 17 ms | 1792 KB |
b06 | AC | 43 ms | 1792 KB |
b07 | AC | 27 ms | 1792 KB |
b08 | AC | 23 ms | 1792 KB |
b09 | AC | 17 ms | 1792 KB |
b10 | AC | 15 ms | 1792 KB |
b11 | AC | 17 ms | 1792 KB |
b12 | AC | 18 ms | 1792 KB |
b13 | AC | 35 ms | 1792 KB |