#364211 (C++17) No.37 遊園地のアトラクション

• 問題: No.37 遊園地のアトラクション
• ユーザー: takana-sky07
• 提出日時: 2019-07-31 01:12:00
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 4 ms / 5,000 ms
• コード長: 1,660 bytes
• コンパイル時間: 808 ms
• コンパイル使用メモリ: 74,368 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-10-10 13:35:01
• 合計ジャッジ時間: 1,656 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	3 ms; 5,248 KB
testcase_03	AC	3 ms; 5,248 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	4 ms; 5,248 KB
testcase_08	AC	2 ms; 5,248 KB
testcase_09	AC	2 ms; 5,248 KB
testcase_10	AC	3 ms; 5,248 KB
testcase_11	AC	3 ms; 5,248 KB
testcase_12	AC	2 ms; 5,248 KB
testcase_13	AC	3 ms; 5,248 KB
testcase_14	AC	2 ms; 5,248 KB
testcase_15	AC	2 ms; 5,248 KB
testcase_16	AC	3 ms; 5,248 KB
testcase_17	AC	3 ms; 5,248 KB
testcase_18	AC	4 ms; 5,248 KB
testcase_19	AC	2 ms; 5,248 KB
testcase_20	AC	2 ms; 5,248 KB
testcase_21	AC	2 ms; 5,248 KB
testcase_22	AC	4 ms; 5,248 KB
testcase_23	AC	2 ms; 5,248 KB
testcase_24	AC	2 ms; 5,248 KB
testcase_25	AC	2 ms; 5,248 KB
testcase_26	AC	2 ms; 5,248 KB
testcase_27	AC	2 ms; 5,248 KB
testcase_28	AC	2 ms; 5,248 KB
testcase_29	AC	2 ms; 5,248 KB
testcase_30	AC	2 ms; 5,248 KB

ソースコード

/*
* 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);		// �����x
	for (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�����ɏ���Ă��Ȃ���Ԃ̈ז����x0
	dp[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���v
				sum += 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;
	
}