Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize ("O3")
- #pragma GCC target ("sse4")
- #include <bits/stdc++.h>
- #include <ext/pb_ds/tree_policy.hpp>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/rope>
- using namespace std;
- using namespace __gnu_pbds;
- using namespace __gnu_cxx;
- typedef long long ll;
- typedef long double ld;
- typedef complex<ld> cd;
- typedef pair<int, int> pi;
- typedef pair<ll,ll> pl;
- typedef pair<ld,ld> pd;
- typedef vector<int> vi;
- typedef vector<ld> vd;
- typedef vector<ll> vl;
- typedef vector<pi> vpi;
- typedef vector<pl> vpl;
- typedef vector<cd> vcd;
- template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
- #define FOR(i, a, b) for (int i = (a); i < (b); i++)
- #define F0R(i, a) for (int i = 0; i < (a); i++)
- #define FORd(i,a,b) for (int i = (b)-1; i >= (a); i--)
- #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
- #define trav(a, x) for (auto& a : x)
- #define mp make_pair
- #define pb push_back
- #define f first
- #define s second
- #define lb lower_bound
- #define ub upper_bound
- #define sz(x) (int)x.size()
- #define beg(x) x.begin()
- #define en(x) x.end()
- #define all(x) beg(x), en(x)
- #define resz resize
- const int MOD = 1000000007;
- const ll INF = 1e18;
- const int MX = 100001;
- const ld PI = 4*atan((ld)1);
- template<class T> void ckmin(T &a, T b) { a = min(a, b); }
- template<class T> void ckmax(T &a, T b) { a = max(a, b); }
- int N, M, perm [10];
- ll arr [100010], groups [10], lo = 0, hi = INF/10000ll, ret;
- bool checkLess(ll p, ll q, ll r){
- return p/q < r || (p/q == r && p%q == 0);
- }
- bool checkIt(ll mini){
- for(int i = 0; i < M; i++) perm[i] = i;
- map<pair<int, int>, int> nexts;
- do{
- int idx = 0;
- for(int i = 0; i < M; i++){
- int curr = perm[i];
- if(nexts.find(mp(idx, curr)) == nexts.end()){
- int a = idx, b = N, best;
- while(a <= b){
- int mid = (a+b)/2;
- if(checkLess(arr[mid]-arr[idx], groups[curr], mini)){ a = mid+1; best = mid; }
- else b = mid-1;
- }
- nexts[mp(idx, curr)] = best;
- }
- idx = nexts[mp(idx, curr)];
- if(idx == N) break;
- }
- if(idx == N) return true;
- }while(next_permutation(perm, perm+M));
- return false;
- }
- int main() {
- // you should actually read the stuff at the bottom
- ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10);
- cin >> N >> M;
- for(int i = 1; i <= N; i++){
- cin >> arr[i];
- arr[i] += arr[i-1];
- }
- for(int i = 0; i < M; i++) cin >> groups[i];
- while(lo <= hi){
- ll mid = (lo+hi)/2;
- if(checkIt(mid)){ hi = mid-1; ret = mid; }
- else lo = mid+1;
- }
- cout << ret << '\n';
- //cout << "HI" << endl;
- // you should actually read the stuff at the bottom
- }
- /* stuff you should look for
- * int overflow, array bounds
- * special cases (n=1?), set tle
- * do smth instead of nothing and stay organized
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement