Untitled

mail@pastecode.io avatar
unknown
plain_text
17 days ago
1.1 kB
7
Indexable
Never
#include <iostream>
#include <cmath>

using namespace std;

typedef long long ll;

int a[100002];

ll lamtron(ll a, ll b){ // lam tron len
    int c = a / b;
    if(c < 1.0 * a / b) c++;
    return c;
}

int main() {
    // input
    int n, k; cin >> n >> k;
    // tinh tong
    ll sum = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        sum += a[i];
    }
    ll res = 1, s = sum;
    //1 ngay n toa tang
    ll t, can, tang = 1ll * n * k; t = tang;
    
    // max toa_n
    ll toa_n = lamtron(1ll*a[n], 1ll*k);
    
    a[0] = a[n+1] = 0; 
    // duyet cac doan i -> n -> xu li toa n
    for(int i = 1; i <= n; i++){
        sum -= a[i-1]; // tong doan
        can = lamtron(sum, tang);
        toa_n = min(toa_n, can); 
        tang -= k;
    }
    
    // duyet cac doan 1 -> i -> xu li tong so ngay tat ca day
    for(int i = n; i >= 1; i--){
        s -= a[i+1]; // tong doan
        can = lamtron(s, t);
        res = max(res, can);
        t -= k;
    }

    cout << toa_n << " " << res;

    return 0;
}
/*
4 2 = 8
1 2 4 6 = 13

-> 13/8 = 1,... -> 2

vay toa 6 day trong toi da 2 ngay

it nhat trong min(min, ?);

*/
Leave a Comment