Submission #1139947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139947		haya	Bank (IZhO14_bank)	C++20	100 / 100	185 ms	16716 KiB

bank

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ld long double
#define ull unsigned long long
#define endl '\n'
#define NF string::npos
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define FAST ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

/*//! Arithmetic sequence law
    (n * (2*a + (n-1)*d))/2;
    n -> number of terms
    a -> first term
    d -> common difference
*/

using namespace std;

const int N = 1e5 + 5;
const int mod = 998244353;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

int n, m;
vector <int> a, b;
vector <pair <int, int> > dp(1<<20, {-1, -1});

pair <int, int> rec(int mask)
{
    if(__builtin_popcount(mask) == m) return {0, 0};
    pair <int, int> &ret = dp[mask];
    if(~ret.first) return ret;
    ret = {0, 0};
    for(int i = 0; i < m; i++)
    {
        if(mask & (1<<i)) continue;
        pair <int, int> p = rec(mask | (1<<i));
        if(ret.first == n) continue;
        int idx = p.first, sum = p.second;
        if(idx == n)
        {
            ret = p;
            continue;
        }
        idx = p.first, sum = p.second + b[i];
        if(sum == a[idx]) idx++, sum = 0;
        ret = max(ret, {idx, sum});
    }
    return ret;
}

signed main()
{
    FAST;

    cin >> n >> m;
    a.resize(n);
    b.resize(m);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];
    pair <int, int> ans = rec(0);
    cout << (ans.first == n ? "YES" : "NO");
    // cout << ans.first << " " << ans.second;

    return 0;
}

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