結果
問題 | No.914 Omiyage |
ユーザー |
![]() |
提出日時 | 2019-10-25 21:40:24 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,005 bytes |
コンパイル時間 | 1,346 ms |
コンパイル使用メモリ | 163,404 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-24 16:26:50 |
合計ジャッジ時間 | 1,970 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define REP(i,m,n) for(int i=(m);i<(n);i++)#define rep(i,n) REP(i,0,n)#define pb push_back#define mp make_pair#define all(c) (c).begin(),(c).end()#define rall(c) (c).rbegin(),(c).rend()typedef long long ll;typedef pair<int,int> pii;typedef pair<ll,ll> pll;const ll inf=1e9+7;const ll mod=998244353;int main(){ll n,m,k;cin>>n>>m>>k;vector<vector<ll> >a(n+1,vector<ll>(m));rep(i,n)rep(j,m)cin>>a[i+1][j];ll mi=k;vector<vector<ll> >dp(n+1,vector<ll>(k+1));dp[0][k]=1;bool ff=1;REP(i,1,n+1){bool f=0;rep(j,k+1){rep(s,m){if(j+a[i][s]<=k&&dp[i-1][j+a[i][s]]){dp[i][j]=dp[i-1][j+a[i][s]];f=1;}}}if(f==0){ff=0;break;}}rep(i,k+1){if(dp[n][i]){mi=i;break;}}cout<<(ff?mi:-1)<<endl;}