結果

問題 No.914 Omiyage
ユーザー murabito1129
提出日時 2025-04-20 01:17:00
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 738 bytes
コンパイル時間 2,227 ms
コンパイル使用メモリ 193,656 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-20 01:17:03
合計ジャッジ時間 3,321 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n,m,k; cin >> n >> m >> k;
  int a[n][m];
  for(int i=0; n>i; ++i){
    for(int j=0; m>j; ++j){
      cin >> a[i][j];
    }
  }
  bool dp[n+1][k+1];
  for(int i=0; n>=i; ++i) for(int j=0; k>=j; ++j) dp[i][j] = false;
  dp[0][0] = true;
  for(int i=0; n>i; ++i){
    for(int j=0; k>=j; ++j){
      for(int l=0; m>l; ++l){
        if(dp[i][j]){
          if(j+a[i][l]<=k) dp[i+1][j+a[i][l]] = true;
        }
      }
    }
  }
  for(int i=k; i>=0; --i){
    if(dp[n][i] == true){
      cout << k-i << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  /*for(int i=0; n>=i; ++i){
    for(int j=0; k>=j; ++j) cout << dp[i][j] << " ";
    cout << endl;
  }cout << endl;*/
}
0