Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

ENAMINE1's blog

By ENAMINE1, history, 2 months ago, In English

This is the code for finding whehther there exists a subset equal to the given sum or not?

The interesting part is that when i change the oreder of rec() in return dp[idx][left_sum] = rec(v,idx+1,n, left_sum) | rec(v, idx+1, n, left_sum — v[idx]); i get different result.

Thanks for looking into it in advance.❤️

here is the test case i have attached

100 5142

57 68 27 100 69 49 100 51 71 63 77 20 63 4 11 31 21 23 94 5 56 54 15 88 61 89 5 22 83 55 90 39 74 16 38 42 17 37 93 39 52 69 59 14 24 21 96 96 43 89 100 51 95 15 38 7 55 42 28 37 49 69 75 74 36 12 16 52 1 60 43 52 80 53 65 55 73 12 50 68 100 50 18 94 16 7 100 70 1 79 58 49 47 32 74 35 95 89 38 47

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#include "./lib/debug.h"
#else
#define debug(...) 42
#endif

#define endl '\n'
#define F(type, i, s, n, step) for (type i = s; (step) > 0 ? i < (n) : i > (n); i += (step))
#define FN(type, i, s, n, step) for (type i = s; (step) > 0 ? i <= (n) : i >= (n); i += (step))
#define pb push_back
// #define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef pair<char, int> pci;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef vector<vl> vvl;

const ll MAXM = 1e5;
int dirx[8] = {-1, 0, 0, 1, -1, -1, 1, 1};
int diry[8] = {0, 1, -1, 0, -1, 1, -1, 1};
int mod = 1e9 + 7;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double EPS = 1e-9;
double PI = acos(-1);
vl factors[MAXM + 5];

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void init()
{
    for (ll i = 1; i <= MAXM; i++)
    {
        for (ll j = i; j <= MAXM; j += i)
        {
            factors[j].pb(i);
        }
    }
}

int bin_pow(int base, int pow)
{
    int ans = 1;
    while (pow)
    {
        if (pow & 1)
        {
            ans = 1LL * ans * base % mod;
        }
        base = 1LL * base * base % mod;
        pow /= 2;
    }
    return ans;
}

int dp[105][1005];
int rec(vector<int> &v, int idx, int left_sum)
{
    int n = v.size();
    if (left_sum < 0)
        return 0;
    if (idx == n)
    {
        if (left_sum == 0)
            return 1;
        else
            return 0;
    }
    if (left_sum == 0)
    {
        return 1;
    }
    if (dp[idx][left_sum] != -1)
    {
        return dp[idx][left_sum];
    }
    return dp[idx][left_sum] = rec(v, idx + 1,left_sum) | rec(v, idx + 1, left_sum - v[idx]);
}

void solve()
{
    int n, sum;
    cin >> n >> sum;
    vi v(n);
    for (auto &e : v)
        cin >> e;
    int ans = rec(v, 0, sum);
    cout << ans;
}

signed main()

{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    std::cout.tie(NULL);

    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++)
    {
#ifdef LOCAL
        std::cerr
            << "Case # " << i << endl;
        std::cout
            << "Case #" << i << endl;
#endif
        solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
    return 0;
}

~~~~~

Full text and comments »

  • Vote: I like it
  • -3
  • Vote: I do not like it