The problem can be found here

My Thought Process

  1. We are asked to maximize something, perhaps binary search will be useful?
  2. We want to maximize the number of soldiers so to do so, we should maximize the number of soldiers in each row using binary search.
  3. The soldiers with height $1$ can only be paired up with soldiers of height 2. If we can form entire rows with soldiers of height $1$, it makes sense to do that since we would be wasting soldiers of height $2$ otherwise.
  4. The leftovers should be paired with soldiers of height $2$ if possible. After a bit of thinking and thinking about worst cases, this seems optimal?

Implementation

#include <bits/stdc++.h>

using ll = long long;
#define pb push_back

using namespace std;

const int MOD = 1e9+7;
const int MAXN = 2e6+1;
const int INF = 2e9;    
const long long IINF = 2e18;

#define int long long

void solve() { 
    int n, k;
    cin >> n >> k;

    vector<int> v(n);
    for(int i = 0; i < n; ++i){cin >> v[i];}

    int l = 1;
    int r = 2e18;
    int ans = 0;

    while(l <= r){
        int m = (l + r)/2;
        vector<int> a = v;
        int teams = 0;
        for(int i = 0; i < n-1; ++i){
            int c = (a[i] + a[i+1])/m;
            if(c > 0){
                a[i+1] -= (c * m - min(c * m, a[i]));
            }
            teams += c;
        }

        teams += (a[n-1] / m);

        if(teams >= k){
            ans = max(ans, m);
            l = m + 1;
        }
        else{
            r = m - 1;
        }
    }

    cout << ans * k << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

See here for the solution and another implementation.