結果

問題 No.914 Omiyage
コンテスト
ユーザー minato
提出日時 2019-12-07 23:26:07
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 14 ms / 2,000 ms
コード長 1,043 bytes
コンパイル時間 2,036 ms
コンパイル使用メモリ 180,536 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-24 16:32:46
合計ジャッジ時間 2,538 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const double PI = acos(-1);
const ll MOD = 1000000007;
using Graph = vector<vector<int>>;

int N,M,K;
vector<vector<int>> A;
vector<int> AL,AR;

void dfs(int k,int O,int n, int x, vector<int> &ALR) {
  if (O + k == n) {
    ALR.push_back(x);
    return;
  }
  rep(i,M) {
    dfs(k+1,O,n,x+A[O+k][i],ALR);
  }
  return;
}

int main() {
  cin >> N >> M >> K;
  A.resize(N, vector<int>(M));
  rep(i,N) {
    rep(j,M) cin >> A[i][j];
  }

  dfs(0,0,N/2,0,AL);
  dfs(0,N/2,N,0,AR);

  sort(all(AL)); sort(all(AR));
  int p = AL.size();
  int q = AR.size();
  
  int ans = -1;
  rep(i,p) {
    if (AL[i] + AR[0] > K) continue;
    else if (AL[i] + AR[q-1] <= K) ans = max(ans,AL[i] + AR[q-1]);
    else {
      int j = upper_bound(all(AR),K - AL[i]) - AR.begin();
      j--;
      ans = max(ans,AL[i] + AR[j]);
    }
  }

  if (ans != -1) cout << K - ans << endl;
  else cout << -1 << endl;
}
0