Tetrooj Box

Tetrooj Box

• 比赛主页
• 我的提交

时间限制：C/C++ 5秒，其他语言10秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

Dr. Orooji’s children have played Tetris but are not willing to help Dr. O with a related problem.
Dr. O’s children don’t realize that Dr. O is lucky to have access to 100+ great problem solvers and

great programmers today!

Dr. O knows the length of the base for a 2D box and wants to figure out the needed height for the
box. Dr. O will drop some 2D blocks (rectangles) on the base. A block will go down until it lands
on the base or is stopped by an already-dropped block (i.e., it lands on that block). After all the
blocks have been dropped, we can determine the needed height for the box – the tallest column is
the needed height (please see pictures on the next page corresponding to Sample Input/Output).

输入描述:

The first input line contains two integers:b(1 ≤b≤ 100), indicating the length of the base andr
(1 ≤r≤50), indicating the number of blocks (rectangular pieces) to be dropped. Each of the next
rinput lines contains three integers: a block’shorizontal lengthh(1 ≤h≤100), the block’svertical
lengthv(1 ≤v≤100), andc(c≥1), the leftmost column the block is dropped into. Assume that
thehandcvalues will be such that the block will not go beyond the box base, i.e., (c+h–1)≤b.

输出描述:

Print the needed height for the box (the tallest column is the height).

示例1

输入

复制

10 4
2 3 1
4 2 2
1 7 6
1 3 4

输出

复制

8

说明

示例2

输入

复制

10 3
3 4 8
8 2 1
1 1 3

输出

复制

7

说明

#include<iostream>
#include<set>
#include<cstring>

using namespace std;
int main(){
    int d,n;
    cin>>d>>n;
    int a[110][11000];
    memset(a, 0, sizeof(a));
    int c,k,cc;
    int max=0;
    for(int i=0;i<n;i++){
        cin>>c>>k>>cc;
        int maxh=1;
        for(int j=cc+1;j<cc+c;j++){
            for(int h=0;h<110;h++){
                if(a[j][h]==1&&h>maxh)
                    maxh=h;
            }
        }
        for(int j=cc;j<=cc+c;j++){
            for(int h=maxh;h<=maxh+k;h++){
                a[j][h]=1;
            }
        }
    }
    for(int i=0;i<110;i++){
        for(int j=0;j<110;j++){
            if(a[i][j]==1&&j>max){
                max=j;
            }
        }
    }
    cout<<max;
}