#392931 (C++14) No.914 Omiyage

• 問題: No.914 Omiyage
• ユーザー: 沙耶花
• 提出日時: 2019-10-25 21:24:23
• 言語: C++14 (gcc 13.2.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 687 bytes
• コンパイル時間: 1,887 ms
• コンパイル使用メモリ: 176,452 KB
• 実行使用メモリ: 4,348 KB
• 最終ジャッジ日時: 2023-10-24 21:07:41
• 合計ジャッジ時間: 2,697 ms
• ジャッジサーバーID （参考情報）: judge14 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,348 KB
testcase_01	AC	2 ms; 4,348 KB
testcase_02	AC	2 ms; 4,348 KB
testcase_03	AC	2 ms; 4,348 KB
testcase_04	AC	1 ms; 4,348 KB
testcase_05	AC	1 ms; 4,348 KB
testcase_06	AC	1 ms; 4,348 KB
testcase_07	AC	2 ms; 4,348 KB
testcase_08	AC	2 ms; 4,348 KB
testcase_09	AC	2 ms; 4,348 KB
testcase_10	AC	1 ms; 4,348 KB
testcase_11	AC	1 ms; 4,348 KB
testcase_12	AC	1 ms; 4,348 KB
testcase_13	AC	2 ms; 4,348 KB
testcase_14	AC	2 ms; 4,348 KB
testcase_15	AC	2 ms; 4,348 KB
testcase_16	AC	2 ms; 4,348 KB
testcase_17	AC	2 ms; 4,348 KB
testcase_18	AC	2 ms; 4,348 KB
testcase_19	AC	2 ms; 4,348 KB
testcase_20	AC	2 ms; 4,348 KB

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define modulo 10000000
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 100000000



int main(){
    
	int N,M,K;
	cin>>N>>M>>K;
	
	vector<vector<int>> A(N,vector<int>(M));
	
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			cin>>A[i][j];
		}
	}
	
	vector<vector<bool>> dp(N+1,vector<bool>(K+1,false));
	dp[0][0]=true;
	for(int i=0;i<N;i++){
		for(int j=0;j<=K;j++){
			if(dp[i][j]==false)continue;
			for(int k=0;k<M;k++){
				int x = j+A[i][k];
				if(x>K)continue;
				dp[i+1][x]=true;
			}
		}
	}
	
	for(int i=K;i>=0;i--){
		if(dp[N][i]){
			cout<<K-i<<endl;
			return 0;
		}
	}
	cout<<-1<<endl;
	
	
    return 0;
}