Submission #1247399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247399		ulvix	Feast (NOI19_feast)	C++20	18 / 100	1094 ms	6888 KiB

feast

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ff first
#define ss second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll sz=4e6+100;
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f3f3f3f;
template<class T>
using indexed_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct modll {
    ll val;
    modll(ll v = 0LL) { val = v % mod; if (val < 0LL) val += mod; }
    inline modll operator+(const modll &o) const { return modll(val + o.val); }
    inline modll& operator+=(const modll &o) { val += o.val; if (val >= mod) val -= mod; return *this; }
    inline modll operator-(const modll &o) const { return modll(val - o.val); }
    inline modll& operator-=(const modll &o) { val -= o.val; if (val < 0LL) val += mod; return *this; }
    inline modll operator*(const modll &o) const { return modll((val * o.val) % mod); }
    inline modll& operator*=(const modll &o) { val = (val * o.val) % mod; return *this; }
    modll pow(ll exp) const { modll res(1LL), base(val); while (exp > 0LL) { if (exp & 1LL) res *= base; base *= base; exp >>= 1LL; } return res; }
    inline modll inv() const { return pow(mod - 2LL); }
    inline modll operator/(const modll &o) const { return *this * o.inv(); }
    inline modll& operator/=(const modll &o) { *this *= o.inv(); return *this; }
    inline modll operator-() const { return modll(-val); }
    inline bool operator==(const modll &o) const { return val == o.val; }
    inline bool operator!=(const modll &o) const { return val != o.val; }
    inline bool operator<(const modll &o) const { return val < o.val; }
    inline bool operator>(const modll &o) const { return val > o.val; }
    inline bool operator<=(const modll &o) const { return val <= o.val; }
    inline bool operator>=(const modll &o) const { return val >= o.val; }
    inline modll& operator=(ll v) { val = v % mod; if (val < 0LL) val += mod; return *this; }
    explicit inline operator ll() const { return val; }
    inline modll& operator++() { if (++val == mod) val = 0LL; return *this; }
    inline modll operator++(int) { modll tmp = *this; ++*this; return tmp; }
    inline modll& operator--() { if (val == 0LL) val = mod - 1LL; else --val; return *this; }
    inline modll operator--(int) { modll tmp = *this; --*this; return tmp; }
    friend inline ostream& operator<<(ostream &os, const modll &m) { return os << m.val; }
    friend inline istream& operator>>(istream &is, modll &m) { ll v; is >> v; m = modll(v); return is; }
};

void solve(){
    ll n,k;
    cin>>n>>k;
    vector<ll> v(n+1);
    for(ll i=1;i<=n;i++) cin>>v[i];
    vector<ll> dp1(k+10,-inf),dp2(k+10,-inf);
    dp2[0]=0;
    for(ll i=1;i<=n;i++){
        vector<ll> ndp1(k+10,-inf),ndp2(k+10,-inf);
        ndp2[0]=0;
        for(ll j=1;j<=min(i,k);j++){
            ndp1[j]=max(dp1[j],dp2[j-1])+v[i];
            ndp2[j]=max(dp1[j],dp2[j]);
        }
        swap(ndp1,dp1);
        swap(ndp2,dp2);
    }
    cout<<max(dp1[k],dp2[k]);
}
int main(){
    //freopen("sleepy.in","r",stdin);
    //freopen("sleepy.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t=1;
    //cin>>t;
    while(t--) solve();
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 18 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29