結果

問題 No.2684 折々の色
ユーザー MMMM
提出日時 2024-03-22 22:20:26
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,973 bytes
コンパイル時間 3,872 ms
コンパイル使用メモリ 241,168 KB
実行使用メモリ 243,972 KB
最終ジャッジ日時 2024-09-30 11:49:49
合計ジャッジ時間 11,061 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 RE -
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 3 ms
6,816 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 WA -
testcase_07 RE -
testcase_08 RE -
testcase_09 WA -
testcase_10 AC 3 ms
6,816 KB
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
testcase_50 -- -
testcase_51 -- -
testcase_52 -- -
testcase_53 -- -
testcase_54 -- -
testcase_55 -- -
testcase_56 -- -
testcase_57 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all>
#define chmin(x,y) (x) = min((x),(y))
#define chmax(x,y) (x) = max((x),(y))
#define ld long double
using namespace std;
using namespace atcoder;
using ll = long long;
const ll mod = 998244353;
using mint = modint998244353;
//using Graph = vector<vector<pair<int,int>>>;
using Graph = vector<vector<int>>;
const vector<int> dx = {1,0,-1,0}, dy = {0,1,0,-1};

ll sqrtll(ll x) {
  assert(x >= 0);
  ll hi(x), lo(0);
  while (hi != lo) {
    ll y = (hi + lo + 1) / 2;
    if (y <= x/y) lo = y;
    else hi = y - 1;
  }
  return lo;
}


int main(){
  // input + prep
  int N,M; cin >> N >> M;
  vector<ll> X(M),T(N);
  vector<vector<ll>> C(N,vector<ll>(M));
  vector<set<vector<ll>>> st(1<<M);
  for(int i = 0; i < M; i++) cin >> X[i];
  for(int i = 0; i < N; i++){
    for(int j = 0; j < M; j++)
      cin >> C[i][j];
    
    cin >> T[i];
    
    for(int j = 0; j < M; j++)
      C[i][j] *= T[i];
    
    for(int k = 1; k < (1<<M); k++){
      vector<ll> v;
      for(int j = 0; j < M; j++){
        if(k&(1<<j)) v.push_back(C[i][j]);
      }
      st[k].insert(v);
    }
  }
  
  bool can = 0;
  for(int i = 0; i < N; i++){
    // st.erase(C[i]);
    
    bool exist = 1;
    vector<ll> tgt;
    int bits = (1<<M)-1;
    for(int j = 0; j < M; i++){
      if(T[i] == 100){
        if(C[i][j] == X[j]) bits ^= (1<<j);
        else exist = 0;
      }
      else{
        ll bns = 100 * (100 * X[j] - C[i][j]);
        if(bns % (100-T[i]) != 0) exist = 0;
        else tgt.push_back(bns / (100-T[i]));
      }
      
      if(!exist) break;
    }
    
    if(exist && bits == 0) can = 1;
    else if(exist){
      vector<ll> org;
      for(int j = 0; j < M; j++)
        if(bits & (1<<j)){
          org.push_back(C[i][j]);
        }
      
      st[bits].erase(org);
      if(st[bits].count(tgt))
        can = 1;
      st[bits].insert(org);
    }
    
    if(can) break;
  }
  
  // output
  cout << (can ? "Yes":"No") << endl;
}
0