oj.uz

답안 #758982

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
758982 2023-06-15T16:17:40 Z scrge 은행 (IZhO14_bank) C++17
52 / 100
 67 ms 18752 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 20;

int n, m;
int salary[N], notes[N], pref[N+1];
int dp[1 << N], sum[1 << N];

signed main(){
  cin >> n >> m;
  int cur_pref = 0;
  pref[0] = 0;
  for(int i = 0; i < n; i++){
    cin >> salary[i];
    //cur_pref += salary[i];
    pref[i+1] = pref[i] + salary[i];
  }
  for(int i = 0; i < m; i++){
    cin >> notes[i];
  }

  for(int i = 0; i < (1 << m); i++){
    int cur = 0;
    for(int j = 0; j < m; j++){
      if(i & (1 << j)) cur += notes[j];
    }
    sum[i] = cur;
  }

  vector<int> masks[N];
  for(int i = 0; i < (1 << m); i++)
    masks[__builtin_popcount(i)].push_back(i);

  memset(dp, 0, sizeof dp);
  dp[0] = true;
  for(int i = 0; i < m; i++){
    for(int mask: masks[i]){
      for(int j = 0; j < m; j++){
        if((mask & (1 << j)) || !dp[mask]) continue;
        int nmask = mask | (1 << j);

        auto lb1 = upper_bound(pref, pref+n, sum[mask]);
        auto lb2 = upper_bound(pref, pref+n, sum[nmask]);
        lb1--, lb2--;
        if(lb1 != lb2){
          if(lb2 == next(lb1) && *lb2 == sum[nmask])
            dp[nmask] = true;
        } else{
          dp[nmask] = true;
        }
      }
      //cout << bitset<6>(mask) << " " << dp[mask] << endl;
    }
  }

  bool ans = false;
  for(int mask = 0; mask < (1 << m); mask++){
    if(sum[mask] == pref[n]){
      //printf("mask %d has sum equals %d, dp = %d\n", mask, pref[n], dp[mask]);
    } 
    if(sum[mask] == pref[n] && dp[mask])
      ans = true;
  }
  if(ans)
    cout << "YES";
  else
    cout << "NO";
}

Compilation message

bank.cpp: In function 'int main()':
bank.cpp:11:7: warning: unused variable 'cur_pref' [-Wunused-variable]
   11 |   int cur_pref = 0;
      |       ^~~~~~~~

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4308 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Correct 2 ms 4308 KB Output is correct
4 Correct 6 ms 4692 KB Output is correct
5 Runtime error 67 ms 18752 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4308 KB Output is correct
2 Correct 3 ms 4308 KB Output is correct
3 Correct 2 ms 4308 KB Output is correct
4 Correct 2 ms 4308 KB Output is correct
5 Correct 2 ms 4308 KB Output is correct
6 Correct 2 ms 4308 KB Output is correct
7 Correct 2 ms 4308 KB Output is correct
8 Correct 2 ms 4308 KB Output is correct
9 Correct 2 ms 4308 KB Output is correct
10 Correct 2 ms 4308 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4564 KB Output is correct
2 Correct 4 ms 4564 KB Output is correct
3 Correct 3 ms 4564 KB Output is correct
4 Correct 3 ms 4436 KB Output is correct
5 Correct 3 ms 4564 KB Output is correct
6 Correct 3 ms 4564 KB Output is correct
7 Correct 4 ms 4564 KB Output is correct
8 Correct 4 ms 4436 KB Output is correct
9 Correct 5 ms 4564 KB Output is correct
10 Correct 3 ms 4564 KB Output is correct
11 Correct 4 ms 4436 KB Output is correct

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4308 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Correct 2 ms 4308 KB Output is correct
4 Correct 6 ms 4692 KB Output is correct
5 Runtime error 67 ms 18752 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -