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];  
//given ith image and current w & h, return the h and w after attaching ith image
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]);  
}  
//given ith image and current w & h, calculate total h after insert images from i to n
//t[i] stores the gain in h after insert images from i to n to a new line.
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);  
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX