結果
問題 | No.914 Omiyage |
ユーザー | pione |
提出日時 | 2019-10-27 20:15:55 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,923 bytes |
コンパイル時間 | 1,523 ms |
コンパイル使用メモリ | 172,744 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-24 16:31:54 |
合計ジャッジ時間 | 2,161 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 1 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 1 ms
6,940 KB |
testcase_06 | AC | 1 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 1 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 2 ms
6,940 KB |
testcase_12 | AC | 1 ms
6,944 KB |
testcase_13 | AC | 2 ms
6,940 KB |
testcase_14 | AC | 1 ms
6,940 KB |
testcase_15 | AC | 2 ms
6,944 KB |
testcase_16 | AC | 1 ms
6,940 KB |
testcase_17 | AC | 1 ms
6,940 KB |
testcase_18 | AC | 1 ms
6,940 KB |
testcase_19 | AC | 2 ms
6,940 KB |
testcase_20 | AC | 2 ms
6,944 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i) #define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i) #define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--) #define rreps(i, n) for (int i = ((int)(n)); i > 0; i--) #define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i) #define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i) #define FOR(e, c) for (auto &e : c) #define SORT(v, n) sort(v, v + n); #define vsort(v) sort(v.begin(), v.end()); #define rvisort(v) sort(v.begin(), v.end(), greater<int>()); #define all(v) v.begin(), v.end() #define mp(n, m) make_pair(n, m); #define cout(d) cout<<d<<endl; #define coutd(d) cout<<std::setprecision(10)<<d<<endl; #define cinline(n) getline(cin,n); #define replace_all(s, b, a) replace(s.begin(),s.end(), b, a); // #define int long long #define PI (acos(-1)) #define FILL(v, n, x) fill(v, v + n, x); using ll = long long; using vi = vector<int>; using vvi = vector<vi>; using vll = vector<ll>; using vvll = vector<vll>; using pii = pair<int, int>; using ul = unsigned long; const int MOD = 1e9+7; const int INF = 1e9; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } int GCD(int a, int b) { return b ? GCD(b, a%b) : a; } int LCM(int a, int b) { return a * b / GCD(a, b); } signed main() { int n,m,K; cin>>n>>m>>K; vvi A(n,vi(m)); rep(i,n) rep(j,m) cin>>A[i][j]; vi dp(K+1,0); dp[0]=1; rep(i,n){ vi tmp(K+1,0); rep(j,m){ for(int k=0; k+A[i][j]<=K; k++){ if(dp[k]) tmp[k+A[i][j]]=1; // 自国のお土産を買ってtrueになったk円を分けるためにtmpに保存 } } dp=tmp; } for(int i=K; i>=0; i--){ if(dp[i]){ cout<<K-i<<endl; return 0; } } cout<<-1<<endl; }