結果

問題 No.2684 折々の色
ユーザー MM
提出日時 2024-03-22 22:20:26
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1 RE * 1
other AC * 3 WA * 4 RE * 2 TLE * 1 -- * 46
権限があれば一括ダウンロードができます

ソースコード

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