Nghé đi cày - LCOJ: Luyen Code Online

DICAY - Nghé đi cày

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hieu Nguyen

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Nghé con hôm nay đi tham gia cuộc thi do làng tổ chức. Bài thi của Nghé là cày ~n~ thửa ruộng (đánh số từ ~1~ đến ~n~). Để cày thửa ruộng thứ ~i~ Nghé cần thời gian là ~t_i~ và nếu cày xong sẽ được số điểm là ~d_i~. Tuy nhiên, Nghé chỉ có tổng thời gian là ~S~ để “làm bài”, do vậy Nghé cần lựa chọn những thửa ruộng để cày cho hợp lý. Bạn hãy lập chương trình giúp Nghé lựa chọn các thửa ruộng để cày trong thời gian ~S~ sao cho đạt điểm tối đa.

Input

Dòng đầu chứa hai số nguyên dương ~n~ và ~S~;
Dòng thứ hai chứa ~n~ số nguyên dương ~t_1, t_2, …, t_n~;
Dòng thứ ba chứa ~n~ số nguyên dương ~d_1, d_2, …, d_n~.

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 ≤ 25; 1 ≤ S ≤ 30000; 1 ≤ t_i, d_i ≤ 10000~

Output

Một số nguyên duy nhất là điểm số lớn nhất Nghé có thể đạt được.

Sample

Input #1

3 10
4 5 7
3 4 8

Output #1

Hint

Chọn cày thửa ruộng số ~3~ thì sẽ cày xong và đạt số điểm là ~8~ (Nếu chọn cày thửa ruộng số ~1~ và ~2~ thì cũng cày xong nhưng chỉ đạt ~7~ điểm).

Problem source: Chuyên Sơn La Online Judge

Bình luận

Hãy đọc nội quy trước khi bình luận.

0

DIEM10CODER đã bình luận lúc 20, Tháng 2, 2024, 13:40

include <bits/stdc++.h>

using namespace std; int dp[50][40010],n,S,W[41],V[41]; vector<int> ans ; int main(){ freopen("DATE20.2.24.INP","r",stdin); freopen("DATE20.2.24.OUT","w",stdout); ios::syncwithstdio(0); cin.tie(); cout.tie(); cin >> n >> S; for(int i=1;i<=n;i++){ cin >> W[i]; } for(int i=1;i<=n;i++){ cin >> V[i]; } for(int i=1;i<=n;i++){ for(int j=0;j<=S;j++){ if(j==0||i==0){ dp[i][j]=0; } if(j<W[i]){ dp[i][j]=dp[i-1][j]; } else{ dp[i][j]=max(dp[i-1][j],V[i]+dp[i-1][j-W[i]]); } ans.push_back(dp[i][j]); } } sort(ans.begin(),ans.end(),greater<int>()); cout << ans[0]; return 0; }

include <iostream>

include <vector>

include <algorithm>

using namespace std;

struct Field { int time; int points; };

bool compareFields(Field a, Field b) { return a.time < b.time; }

int main() { int n, t, totalTime; cin >> n >> t;

vector<Field> fields(n);

for (int i = 0; i < n; ++i) {
    cin >> fields[i].time;
}

for (int i = 0; i < n; ++i) {
    cin >> fields[i].points;
}

sort(fields.begin(), fields.end(), compareFields);

vector<vector<int>> dp(n + 1, vector<int>(t + 1, 0));

for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= t; ++j) {
        dp[i][j] = dp[i - 1][j];
        if (j >= fields[i - 1].time) {
            dp[i][j] = max(dp[i][j], dp[i - 1][j - fields[i - 1].time] + fields[i - 1].points);
        }
    }
}

cout << dp[n][t] << endl;

return 0;

}