Created
January 17, 2016 18:31
-
-
Save iray-tno/2226b3ff9f9dcf0603f9 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <queue> | |
#include <bitset> | |
#include <algorithm> | |
#include <iostream> | |
#include <set> | |
#include <map> | |
#include <iterator> | |
#include <cmath> | |
#include <tuple> | |
#include <stack> | |
#include <iomanip> | |
#include <string> | |
#include <vector> | |
#include <limits> | |
using namespace std; | |
template<class T = int,T divided_by = 10> | |
constexpr T PINF(){ return std::numeric_limits<T>::max()/divided_by; } | |
template<class T = int,T divided_by = 10> | |
constexpr T MINF(){ return std::numeric_limits<T>::lowest()/divided_by; } | |
long long solve(){ | |
long long l,n,m,d; | |
cin >> l >> n >> m >> d; | |
vector<long long> w(n); | |
for(long long i = 0; i < n; ++i){ | |
cin >> w[i]; | |
} | |
//にぶたんすにぺっと | |
long long invalid_X,valid_X,middle_X; | |
//↓書き換える | |
invalid_X = 0; //にぶたん開始点1 : invalidなX | |
valid_X = PINF<long long>(); //にぶたん開始点2 : validなX | |
bool check_invalid_flag = true; //invalid_Xがvalidかつそれが答えになる可能性 | |
auto is_valid = [&](long long times){ //validのときtrueを返す関数 | |
long long washed = 0; | |
for(long long i = 0; i < n; ++i){ | |
washed += times/w[i]; | |
} | |
if(l<=washed) return true; | |
return false; | |
}; | |
//↑終わり | |
if(check_invalid_flag&&is_valid(invalid_X)){ | |
valid_X=invalid_X; | |
}else{ | |
while(1<abs(valid_X-invalid_X)){ | |
middle_X = (valid_X+invalid_X)/2; | |
if(is_valid(middle_X)){ | |
valid_X=middle_X; | |
}else{ | |
invalid_X=middle_X; | |
} | |
} | |
} | |
//にぶたんすにぺっとおわり | |
long long wash_t = valid_X; | |
multiset<long long> launds_t; | |
for(long long i = 0; i < n; ++i){ | |
long long loop = wash_t/w[i]; | |
for(long long j = 0; j < loop; ++j){ | |
launds_t.insert(w[i]*(j+1)); | |
} | |
} | |
priority_queue<long long,vector<long long>,greater<long long>> pq; | |
long long done = 0,last = 0; | |
for(auto t : launds_t){ | |
if(pq.size()<m){ | |
last = t+d; | |
pq.push(last); | |
}else{ | |
long long p = pq.top(); pq.pop(); | |
if(p<t){ | |
last = t+d; | |
}else{ | |
last = p+d; | |
} | |
pq.push(last); | |
} | |
done++; | |
if(done==l) break; | |
} | |
return last; | |
} | |
int main() { | |
cin.tie(nullptr); ios::sync_with_stdio(false); | |
//cout << fixed << setprecision(10); | |
int t; | |
cin >> t; | |
for(int i = 0; i < t; ++i){ | |
cout << "Case #" << i+1 << ": " << solve() << endl; | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment