Submission #1296685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296685		Dreamy_lovesper	Feast (NOI19_feast)	C++20	71 / 100	33 ms	53500 KiB

feast

// I also thought that there was a small chance that she likes me back.
#include <bits/stdc++.h>

using namespace std;

// Do you think you'll ever remember me someday, or will I just fade away from your memory?
#define LIFESUCK ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define str string
#define mll map<ll, ll>
#define vll vector<ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define all(c) c.begin(), c.end()
#define pb push_back
#define sz(s) s.size()
#define debug cout << "I Love You\n";
#define fu(i, a, b) for (ll i = a; i <= b; i++)
#define fd(i, b, a) for (ll i = b; i >= a; i--)
#define Bisave(msk, j) ((msk >> j) & 1)
#define _log(x) 31 - __builtin_clz(x)
#define LoveTime chrono::steady_clock::now().time_since_epoch().count()

const ll Mod = 998244353;
const ll inf = (1ll << 30);
const ll lnf = (1ll << 60);

// When time passes and things change... will you still remember someone like me?
int64_t add(ll& a, ll b) {
    a += b;
    if (a >= Mod) a %= Mod;
    while (a < 0) a += Mod;
    return a;
}

int64_t mul(ll a, ll b) {
    a = 1ll * a * b % Mod;
    return a;
}

template <class X, class Y>
bool minimize(X& x, Y y) {
    X eps = 1e-9;
    if (x > y + eps) {
        x = y;
        return 1;
    }
    return 0;
}

template <class X, class Y>
bool maximize(X& x, Y y) {
    X eps = 1e-9;
    if (x + eps < y) {
        x = y;
        return 1;
    }
    return 0;
}

// I wonder… will I just become a distant memory to you one day?
#define mxn 300'007
ll n, k, g[mxn];

namespace Love1 {
    bool check() {
        fu(i, 1, n) if(g[i] < 0) return 0;
        return 1;
    }

    void DreamyLove () {
        ll sad = 0;
        fu(i, 1, n) sad += g[i];

        cout << sad;

        //
    }
}

namespace Love2 {
    bool check() {
        bool ok = 0;
        fu(i, 1, n) {
            if(g[i] < 0) {
                if(ok) return 0;
                ok = 1;
            }
        }
        return 1;
    }

    void DreamyLove() {

        ll sad = 0;
        fu(i, 1, n) {
            if(g[i] < 0) continue;
            sad += g[i];
        }

        cout << sad;

        //
    }
}

namespace Love3 {
    bool check() {
        return (k == 1);
    }

    void DreamyLove () {

        ll sad = 0, cr = 0;

        fu(i, 1, n) {
            cr += g[i];
            maximize(sad, cr);
            if(cr < 0) cr = 0;
        }

        cout << sad;

        //
    }
}

namespace Love4 {
    bool check() {
        return (n <= 80);
    }

    ll f[87][87], pref[87];

    void DreamyLove () {
        
        fu(i, 1, n) pref[i] = pref[i - 1] + g[i];

        ll sad = 0;
        // f[1][1] = g[1];
        fu(i, 1, n) {
            fu(l, 1, i) {
                ll val = pref[i] - pref[l - 1];
                fu(pos, 0, l - 1) fu(j, 1, k) {
                    maximize(f[j][i], f[j - 1][pos] + val);
                    maximize(sad, f[j][i]);
                    // cerr << i << ' ' << l << "  " << pos << ' ' << j << "  =>   " << f[j][i] << ' ' << val << '\n';
                }
            }
        }

        cout << sad;

        //
    }
}

namespace Love56 {
    bool check() {
        return (n <= 2007);
    }

    ll f[2007][2007], pref[2007];
    ll d[2007][2007];

    void DreamyLove () {
        
        fu(i, 1, n) pref[i] = pref[i - 1] + g[i];

        ll sad = 0;

        fu(j, 1, k) {
            fu(i, 1, n) {
                d[j][i] = max(d[j][i - 1], f[j - 1][i - 1] - pref[i - 1]);
                maximize(f[j][i], f[j][i - 1]);
                maximize(f[j][i], d[j][i] + pref[i]);
            }
        }
        
        cout << f[k][n];
        //
    }
}

// The world is still beautiful, only it’s a pity that you are no longer among the living.
void lovesper(const ll& Tessavease) {
    cin >> n >> k;
    fu(i, 1, n) cin >> g[i];

    if(Love1::check()) {
        Love1::DreamyLove();
        return;
    }
    
    if(Love3::check()) {
        Love3::DreamyLove();
        return;
    }
    
    if(Love2::check()) {
        Love2::DreamyLove();
        return;
    }

    if(Love4::check()) {
        Love4::DreamyLove();
        return;
    }

    if(Love56::check()) {
        Love56::DreamyLove();
        return;
    }

}

//    In the future, each of us will have our own path..
// ...But no matter where we go, we will always be a beautiful part of each other’s memories.
signed main() {
    LIFESUCK

#define name "lovesper"
    // freopen(name".inp", "r", stdin);
    // freopen(name".out", "w", stdout);

    ll Test = 1;
    // cin >> Test;

    fu(i, 1, Test) {
        lovesper(i);
        if (i < Test) cout << '\n';
    }

    return 0;
}

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