Submission #35104734

---

Source Code Expand

#include <bits/stdc++.h>



using namespace std;


// #pragma gcc optimize("ofast")
// #pragma gcc target("avx,avx2,fma")


#define int long long

#define all(x) (x).begin(), (x).end()


#define pb push_back
#define endl '\n'
#define fi first
#define se second

// const int mod = 1e9 + 7;

const int mod=998'244'353;


const long long INF = 2e18 + 10;
// const int INF=4e9+10;

#define readv(x, n)   \
    vector<int> x(n); \
    for (auto &i : x) \
        cin >> i;



template <typename t>
    using v = vector<t>;

template <typename t>
    using vv = vector<vector<t>>;

template <typename t>
    using vvv = vector<vector<vector<t>>>;

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<vector<vector<vector<int>>>> vvvvi;
typedef vector<vector<double>> vvd;

typedef pair<int, int> pii;



int multiply(int a, int b, int in_mod) { return (int)(1ll * a * b % in_mod); }
int mult_identity(int a) { return 1; }



const double pi = acosl(-1);



auto power(auto a, auto b, const int in_mod)
{

    auto prod = mult_identity(a);
    auto mult = a % in_mod;
    while (b != 0)
    {
        if (b % 2)
        {
            prod = multiply(prod, mult, in_mod);
        }
        if(b/2)
        mult = multiply(mult, mult, in_mod);
        b /= 2;
    }
}
auto mod_inv(auto q, const int in_mod)
{
    return power(q, in_mod - 2, in_mod);
}


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());



#define stp cout << fixed << setprecision(20);

void solv()
{

    int n, k;
    cin>>n>>k;

    readv(a,k);

    vvi dp(n + 1, vi(2, -INF));

    dp[0][0] = 0;
    dp[0][1] = 0;




    for(int i = 1;i<=n;i++){
        for(int j= 0;j<2;j++){
            if(j == 0)
                dp[i][j] = INF;
            else
                dp[i][j] = -INF;
            for(int l = 0;l<k;l++){
                if(a[l] <=i){
                    if(j == 1)
                        dp[i][j] = max(dp[i][j], j * a[l] + dp[i-a[l]][1-j] );
                    else
                        dp[i][j] = min(dp[i][j], j * a[l] + dp[i-a[l]][1-j] );

                }
            }
        }
    }
    cout<<dp[n][1]<<endl;

}

void solve()
{

    int t = 1;
    // cin>>t;
    for(int T=1;T<=t;T++)
    {
        // cout<<"Case #"<<T<<": ";
        solv();
    }
}




signed main()
{

    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);


    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cerr.tie(NULL);

    auto clk = clock();
    // -------------------------------------Code starts here---------------------------------------------------------------------

    signed t = 1;
    // cin >> t;

    for (signed test = 1; test <= t; test++)
    {
        // cout<<"Case #"<<test<<": ";

        solve();
    }

    // -------------------------------------Code ends here------------------------------------------------------------------

    clk = clock() - clk;

    #ifndef ONLINE_JUDGE
    cerr << fixed << setprecision(6) << "\nTime: " << ((float)clk) / CLOCKS_PER_SEC << "\n";
    #endif
    return 0;
}

/*
000100

1000100

1 0 -1 -2 -1 -2 -3
*/

Submission Info

Compile Error

./Main.cpp: In function ‘long long int mult_identity(long long int)’:
./Main.cpp:58:23: warning: unused parameter ‘a’ [-Wunused-parameter]
   58 | int mult_identity(int a) { return 1; }
      |                       ^
./Main.cpp: At global scope:
./Main.cpp:66:12: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts’
   66 | auto power(auto a, auto b, const int in_mod)
      |            ^~~~
./Main.cpp:66:20: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts’
   66 | auto power(auto a, auto b, const int in_mod)
      |                    ^~~~
./Main.cpp:82:14: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts’
   82 | auto mod_inv(auto q, const int in_mod)
      |              ^~~~

Judge Result