結果
問題 | No.914 Omiyage |
ユーザー |
![]() |
提出日時 | 2019-10-25 21:27:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 45 ms / 2,000 ms |
コード長 | 1,424 bytes |
コンパイル時間 | 2,370 ms |
コンパイル使用メモリ | 192,556 KB |
最終ジャッジ日時 | 2025-01-08 01:02:56 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define INF 100000000#define YJ 1145141919#define INF_INT_MAX 2147483647#define INF_LL 9223372036854775#define INF_LL_MAX 9223372036854775807#define EPS 1e-10#define MOD 1000000007#define MOD9 998244353#define Pi acos(-1)#define LL long long#define ULL unsigned long long#define LD long double#define int long longusing II = pair<int, int>;int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }int lcm(int a, int b) { return a * b / gcd(a, b); }int extgcd(int a, int b, int &x, int &y) { int g = a; x = 1; y = 0; if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x; return g; }#define FOR(i,a,b) for(int i=(a);i<(b);++i)#define REP(i,n) FOR(i,0,n)#define ALL(a) begin((a)), end((a))#define RALL(a) (a).rbegin(), (a).rend()#define PB push_back#define MP make_pair#define SZ(a) int((a).size())const int MAX_N = 11;const int MAX_M = 11;const int MAX_K = 501;int N, M;int A[MAX_N][MAX_M];int K;bool dp[MAX_N][MAX_K];signed main(){cin >> N >> M >> K;REP(n,N) {REP(m,M) {cin >> A[n][m];}}dp[0][K] = true;REP(n,N) {REP(k,K+1) {if(!dp[n][k]) continue;REP(m,M) {if(k-A[n][m] >= 0) {dp[n+1][k-A[n][m]] = true;}}}}REP(k,K+1) {if(dp[N][k]) {cout << k << endl;return 0;}}cout << -1 << endl;return 0;}