結果

問題 No.914 Omiyage
コンテスト
ユーザー fiore57
提出日時 2019-10-25 22:12:22
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,147 bytes
コンパイル時間 1,669 ms
コンパイル使用メモリ 166,936 KB
実行使用メモリ 16,824 KB
最終ジャッジ日時 2024-09-13 04:06:23
合計ジャッジ時間 8,097 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

#define DUMP(x) std::cout << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP(i, k, n) for (int i = (k); i < (int)(n); ++i)
#define ALL(r) r.begin(), r.end()
#define YES puts("YES")
#define Yes puts("Yes")
#define NO puts("NO")
#define No puts("No")
#define IMP puts("IMPOSSIBLE")
#define Imp puts("Impossible")
#define imp puts("impossible")
#define pb push_back

template <typename T>
T dup(T x, T y)
{
    return (x + y - 1) / y;
};
template <typename A, size_t N, typename T>
inline void arrayFill(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); }
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}

using ll = int64_t;
using vint = vector<int32_t>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pint = pair<int32_t, int32_t>;
using pll = pair<ll, ll>;
using vpint = vector<pint>;
using vpll = vector<pll>;
using sint = set<int32_t>;
using sstr = set<string>;
using qint = queue<int32_t>;

constexpr std::int32_t INF = 1001001001;
constexpr std::int64_t LINF = 1001001001001001001;

int n, m, k;
int ans;
int a[12][12];
void dfs(int x, int sum)
{
    if (x == n)
    {
        if (sum > k)
            return;
        else {

            chmax(ans, sum);
            return;
        }
    }

    if (sum > k)
        return;
    rep(i, m)
    {
        dfs(x + 1, sum + a[x][i]);
    }

    return;
}

void Main()
{
    cin >> n >> m >> k;
    ans = -1;

    rep(i, n) rep(j, m) cin >> a[i][j];
    /*
    n = 10; m = 10; k = 500;
    rep(i, n) rep(j, m) a[i][j] = i * 2 + j;
    */

    dfs(0, 0);

    if (ans == -1)cout << -1 << endl;
    else cout << k - ans << endl;
}

int main()
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}
0