結果
問題 | No.37 遊園地のアトラクション |
ユーザー |
|
提出日時 | 2019-07-31 01:12:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 28 ms / 5,000 ms |
コード長 | 1,660 bytes |
コンパイル時間 | 801 ms |
コンパイル使用メモリ | 72,944 KB |
最終ジャッジ日時 | 2025-01-07 10:13:32 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
ソースコード
/** 037_sample.cpp** No.37 �V���n�̃A�g���N�V����* ��Փx3*/#include <iostream>#include <vector>#include <cstdio>using VEC = std::vector<int>;int main () {// �W������int T = 0; // �؍ݎ���int N = 0; // �A�g���N�V�����̐�std::cin >> T >> N;VEC c(N*9+1); // �A�g���N�V�����̑҂�����(+��蕨�̎���)VEC v(N*9+1); // �����xfor (int i = 0; i < N; i++) {std::cin >> c[i];}for (int i = 0; i < N; i++) {std::cin >> v[i];}// ������int dp[N+1][T+1];for (int i = 0; i < N+1; i++) {for (int j = 0; j < T+1; j++) {dp[i][j] = -1;}}// dp[�A�g���N�V������][�҂����Ԃ̍��v]=�����x// 0�Ԗڂ��·���0��1�·��A�g���N�V�����ɏ���Ă��Ȃ���Ԃ̈ז����x0dp[0][0] = 0;for (int i = 0; i < N; ++i) {for (int j = 0; j <= T; ++j) {int sum = 0;dp[i+1][j] = dp[i][j];for (int k = v[i], count = 1; 0 <= k; k /= 2, count++ ) {// �J��Ԃ������A�g���N�V�����ɏ�邽�і����x������// 0�ƂȂ�Ƃ���ȏ�͏���Ă��Ӗ����Ȃ��בł���if (k == 0) {break;}// i�Ԗڂ̖����x���vsum += k;if (j - c[i] * count >= 0) {// i�Ԗڂ̃A�g���N�V������count������Ƃ��̍��v���Ԃ�// �؍ݎ��Ԃ��Ă��Ȃ��ꍇif (dp[i][j - c[i] * count] != -1) {dp[i+1][j] = std::max(dp[i+1][j], dp[i][j - c[i] * count] + sum);}}}}}// �ŏI�I�ɍŌ�̊X�ł����������Ԃň�ԏ��������̂��Ƃ���int ans = 0;for (int i = 0; i <= T; ++i) {ans = std::max(ans, dp[N][i]);}// �Ō�̊X�܂ł��ǂ蒅���Ă��Ȃ��ꍇ��-1�Ƃ���std::cout << ans << std::endl;return 0;}