1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int N = 100005;
int n,m;
int wi[N],hi[N],t[N];
void attach(int i,int &w,int &h){
    if (w+wi[i] > m)
        h = max(h,(int)ceil(1.0*(m-w)*hi[i]/wi[i]));
    else
        h = max(h, hi[i]);
    w = min(m, w+wi[i]);
}
int calc(int i,int w,int h){
    while(i < n && w < m)
        attach(i++,w,h);
    return h+t[i];
}
void solve(){
    int ans = INF,w,h,preSum;
    w = h = preSum = 0;
    for(int i = 0; i < n; ++i){
        int tmp = calc(i+1,w,h);
        ans = min(ans, preSum+tmp);
        attach(i,w,h);
        if(w == m){
            preSum += h;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX