CHUNGCAKE - Bánh chưng
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Nhân dịp Tết nguyên đán năm nay, Nhà trường tổ chức cho các lớp gói bánh Chưng. Có nhiều lớp tham gia, các lớp đã gói được ~n~ cái bánh Chưng, cái thứ ~i~ có thể tích là sô nguyên dương ~v_i~ ~(cm^3)~. Tuy nhiên để luộc những cái bánh này thì lại chỉ có duy nhất một cái nồi với thể tích là ~V~ ~(cm^3)~ và số củi chỉ đủ để luộc duy nhất một nồi. Bạn hãy tính xem có thể luộc được số bánh Chưng với tổng thể tích lớn nhất là bao nhiêu (số bánh Chưng luộc được phải có tổng thể tích không vượt quá thể tích của nồi)?
Input
- Dòng đầu chứa hai số nguyên dương ~n~ và ~V~;
- Dòng thứ hai chứa ~n~ số nguyên dương ~v_i~.
Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.
Giới hạn:
- ~1 ≤ n ≤ 30; 1 ≤ V ≤ 2000; 1 ≤ v_i ≤ 100~
Output
- Một số nguyên duy nhất là tổng thể tích lớn nhất của số bánh Chưng luộc được.
Sample
Input #1
3 8
2 3 4
Output #1
7
Input #2
4 10
1 2 3 4
Output #2
10
Problem source: Chuyên Sơn La Online Judge
Bình luận
include <bits/stdc++.h>
using namespace std;
int main() { int n, V; cin >> n >> V; vector<int> v(n); for(int i = 0; i < n; i++) cin >> v[i];
}
test 4 là gì v anh em. code đúng qhd mà ac hết mỗi tét 4 WA:)))))))))
Code của thu hoạch được tối ưu case 9
test 9 là gì vậy ạ=((
bài này sd quy hoạch động, test 9 là trường hợp những cái bánh chưng đều có thể tích lớn hơn cái nồi, tức là v[i] vs i từ 1 - n đều > V thì kq là 0; vậy chỉ cần sd quy hoạch động và thêm đk check xem nếu ko có dãy con nào có thể tạo thành thì mik cout 0;
lô ae
xin test 5 vs test 10 với ạ
bài này tớ dùng đệ quy có nhớ là ac được, dùng đệ quy không ac được tét cuối
ac la gi vay ban
AC LÀ ĐÚNG Á FEND (ACCEPTED)
xin test 5 vs test cuối đc ko admin :v