Submission #824651

#	Time	Username	Problem	Language	Result	Execution time	Memory
824651		andecaandeci	Bank (IZhO14_bank)	C++17	19 / 100	5 ms	332 KiB

bank

// Remember to do easier subtasks for ALL problmes in IO when stuck for too long
// Always be doing something useful, like mapping the problem
// Try a different approach or view problem in a different perspective
// Don't overthink, have a clear mind, don't panic if not getting the easy problems

#include<bits/stdc++.h>
#define fastcincout ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fi first
#define se second
#define pq priority_queue
#define mp make_pair
#define str string
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define bop pop_back
#define MOD 1000000007

using namespace std;
const int maxn=25;
bool debug=1;

int a[maxn], b[maxn], c[maxn], n, m; // c is to keep track of a aka a tmp copy array of a

int d[maxn][maxn];

int dp(int idx, int rem) { // we are on b[idx] with rem many customers unsatisfied
//     cout << "dp " << idx << " " << rem << "\n";
     if (rem == 0) return 1;
  if (rem > m-idx) return 0;
//  if (d[idx][rem] != -1) return d[idx][rem];
  int ret=0;
  for (int i=1; i<=n; i++) {
    if (c[i]-b[idx] < 0) continue;
    c[i]-=b[idx];
//    cout << a[i] << " - " << b[idx] << " = " << c[i] << "\n";
    ret |= dp(idx+1, rem-(c[i] == 0));
    c[i]+=b[idx];
  }
  ret |= dp(idx+1, rem);
  return d[idx][rem]=max(ret, d[idx][rem]);
}

void solve() {
  str ans[] = {"NO", "YES"};
  memset(d, -1, sizeof(d));
  cin >> n >> m;
  for (int i=1; i<=n; i++) {
    cin >> a[i];
    c[i]=a[i];
  }
  for (int i=1; i<=m; i++) {
    cin >> b[i]; 
  }
  sort(a+1, a+n+1); sort(b+1, b+m+1); sort(c+1, c+n+1);
  cout << ans[dp(1, n)] << "\n";
}

int main() {
  fastcincout;
  int t=1;
  // cin >> t;
  while(t--)
  {
      solve();
   }
  return 0;
}

• Subtask 1: 19 / 19
• Subtask 2: 0 / 25
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29