oj.uz

Submission #477793

# Submission time Handle Problem Language Result Execution time Memory
477793 2021-10-03T18:18:34 Z __SIGSEGV__ Bank (IZhO14_bank) C++17
25 / 100
 1000 ms 12624 KB 
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <chrono>
#include <algorithm>
#include <stdio.h>
#include <unordered_set>
#include <bitset>
#include <cstring>
#include <cmath>
#include <climits>
#include <cassert>
#include <ctime>
#include <unistd.h>
 
using namespace std;
 
#define rep(x, a, b) for (int x = (int) (a); x < (int) (b); x++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int) (x).size()
#define fi first
#define se second
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
 
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
 
template<typename T> bool ckmin(T& a, T b) { return (a > b ? (a = b, false) : true); }
template<typename T> bool ckmax(T& a, T b) { return (a < b ? (a = b, false) : true); }
 
void solve(const int& test_number) {
    int n, m; cin >> n >> m;
    vector<int> customers(n), notes(m);
    rep(i, 0, n) cin >> customers[i];
    rep(i, 0, m) cin >> notes[i];

    vector<vector<int>> dp(n + 1, vector<int>((1 << m), 0));
    vector<int> can(n + 1, 0);
    dp[0][0] = 1;
    can[0] = 1;
    rep(i, 1, n + 1) {
        rep(mask, 0, (1 << m)) {
            for (int sub = mask; sub; sub = (sub - 1) & mask) {
                // sub is a submask of the bitmask "mask"
                int total = 0;
                rep(j, 0, m) if (sub & (1 << j)) total += notes[j];
                if (total == customers[i-1])
                    dp[i][mask] = dp[i-1][mask ^ sub];
                can[i] |= dp[i][mask];
            }
        }
    }
    cout << (can[n] ? "YES" : "NO") << '\n';
}   
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
 
    int tt = 1;
//    cin >> tt;
 
#ifdef LOCAL_DEFINE
    auto start = std::chrono::high_resolution_clock::now();
#endif    
 
    rep(t, 0, tt) 
        solve(t + 1);
 
#ifdef LOCAL_DEFINE
    auto stop = std::chrono::high_resolution_clock::now();
    auto elapsed_ticks = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);
 
    std::cerr << "Execution Completed in: " << elapsed_ticks.count() << " milliseconds\n";
#endif
    return 0;
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 3 ms 208 KB Output is correct
4 Correct 771 ms 720 KB Output is correct
5 Execution timed out 1087 ms 12624 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 336 KB Output is correct
2 Correct 7 ms 336 KB Output is correct
3 Correct 5 ms 208 KB Output is correct
4 Correct 9 ms 336 KB Output is correct
5 Correct 19 ms 336 KB Output is correct
6 Correct 12 ms 340 KB Output is correct
7 Correct 7 ms 208 KB Output is correct
8 Correct 11 ms 336 KB Output is correct
9 Correct 7 ms 336 KB Output is correct
10 Correct 11 ms 336 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 848 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 3 ms 208 KB Output is correct
4 Correct 771 ms 720 KB Output is correct
5 Execution timed out 1087 ms 12624 KB Time limit exceeded
6 Halted 0 ms 0 KB -