結果

問題 No.914 Omiyage
ユーザー yamate11
提出日時 2019-11-02 09:33:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 8 ms / 2,000 ms
コード長 1,480 bytes
コンパイル時間 2,760 ms
コンパイル使用メモリ 199,468 KB
最終ジャッジ日時 2025-01-08 02:14:03
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <cassert>
typedef long long int ll;
using namespace std;

#if defined(DEBUG)

#include <unistd.h>
#include <sys/fcntl.h>
#define DLOG(...)        cerr << dbgFormat(__VA_ARGS__) << endl
#define DCALL(func, ...) func(__VA_ARGS__)

template <class... Args>
string dbgFormat(const char* fmt, Args... args) {
  size_t len = snprintf(nullptr, 0, fmt, args...);
  char buf[len + 1];
  snprintf(buf, len + 1, fmt, args...);
  return string(buf);
}

#else  // defined(DEBUG)

#define DLOG(...)
#define DCALL(func, ...)

#endif // defined(DEBUG)
// ----------------------------------------------------------------------

// ----------------------------------------------------------------------
int main(int argc, char *argv[]) {
#if defined(DEBUG)
  // GDB on Cygwin ignores redirection at run command.
  if (argc == 2) dup2(open(argv[1], 0), 0);
#else
  // For performance.  We should not use C-style stdio functions
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cout << setprecision(20);

  int N, M, K; cin >> N >> M >> K;
  vector<vector<bool>> rec(N+1, vector<bool>(K+1));
  rec.at(0).at(0) = true;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      int a; cin >> a;
      for (int k = 0; k+a <= K; k++) {
        if (rec.at(i).at(k)) rec.at(i+1).at(k+a) = true;
      }
    }
  }
  int i = K;
  while (i >= 0 && !rec.at(N).at(i)) i--;
  if (i < 0) cout << "-1\n";
  else cout << K - i << "\n";

  return 0;
}
0