Bài tập: Cắt thép

Người ta cần cắt một đoạn thép dài l mét tại n vị trí, mỗi vị trí có toạ độ là một số nguyên tính theo khoảng cách bắt đầu từ đầu đoạn thép. Chi phí để cắt là chiều dài của đoạn cần cắt.

Yêu cầu: Hãy tìm chi phí nhỏ nhất để cắt đoạn thép.

Dữ liệu vào: cho trong file văn bản catthep.inp có cấu trúc như sau:

• Dòng đầu ghi 2 số nguyên dương l và n.
• Dòng thứ 2 ghi n số là toạ độ của các vị trí cần cắt, các toạ độ có giá trị lớn hơn 0 và nhỏ hơn l.

Kết quả: ghi ra file văn bản catthep.out chỉ 1 số là kết quả tìm được

Bảng con có tổng lớn nhất

BÀI TOÁN

Cho một bảng hình chữ nhật gồm m dòng và n cột, mỗi phần tử là một số nguyên dương. Hãy tìm một bảng con có tổng các phần tử lớn nhất.
Dữ liệu vào:

• Dòng đầu tiên ghi 2 số nguyên dương m và n
• m dòng tiếp theo, mỗi dòng ghi n số nguyên, mỗi số có trị tuyệt đối không vượt quá 1000

Kết quả: ghi ra 1 số là tổng lớn nhất tìm được
Ví dụ

Input	Output
3 5 -2 6 -1 4 -5 4 2 1 6 3 5 -9 2 1 0	20

Giới hạn:

• 30% số test có m, n ≤ 10
• 30% số test còn lại có m, n ≤ 100
• 40% số test còn lại có m, n ≤ 500

Đề thi HSG TP. Cần Thơ 2015-2016

Bài	Tên bài	File chương trình	File dữ liệu vào	File kết quả
1	Số nguyên tố	primemax.*	primemax.inp	primemax.out
2	Rau sạch	vegetables.*	vegetables.inp	vegetables.out
3	Bình chọn giọng hát hay	song.*	song.inp	song.out
4	Xếp hàng mua vé tàu	queue.*	queue.inp	queue.out