Submission #1224211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224211		Dreamy_lovesper	Holding (COCI20_holding)	C++20	55 / 110	118 ms	254944 KiB

holding

#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 debug cout << "I Love You\n";
#define fu(i, a, b) for (int i = a; i <= b; i++)
#define fd(i, b, a) for (int i = b; i >= a; i--)
#define Bitc(msk, j) ((msk >> j) & 1)
#define _log(x) 31 - __builtin_clz(x)

const ll Mod = 1e9 + 7;
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 10'007
ll n, l, r, k;
ll g[107];

struct Edge{
    ll u, v;
} edge[mxn];

namespace Love1 {
    bool check () {
        return (n <= 13 && r == n);
    }

    void DreamyLove() {
        
        ll bad = 0;
        fu(i, l, r) bad += g[i];
        ll sad = bad;

        fu(msk1, 0, (1 << (l - 1)) - 1) {
            ll cr = 0, sum1 = 0;
            fu(j, 0, l - 2) if(Bitc(msk1, j)) cr += j + 1, sum1 += g[j + 1];
            fu(msk2, 0, (1 << (r - l + 1))) {
                if(__builtin_popcount(msk1) != __builtin_popcount(msk2)) continue;
                ll gf = 0, sum2 = 0;
                fu(j, 0, r - l) if(Bitc(msk2, j)) gf += l + j, sum2 += g[l + j];
                if((gf - cr) > k) continue;
                minimize(sad, bad - sum2 + sum1);
            }
        }

        cout << sad;

        //
    }
}

namespace Love2 {
    bool check () {
        return (n <= 50 && r == n);
    }

    ll f[57][57][mxn];
    void DreamyLove () {

        memset(f, 0, sizeof(f));
        ll bad = 0;

        fu(i, 1, l - 1) fu(j, l, n)
            fd(c, k, 0) {
                maximize(f[i][j][c], f[i - 1][j][c]);
                maximize(f[i][j][c], f[i][j - 1][c]);
                if(j - i <= c) maximize(f[i][j][c], f[i - 1][j - 1][c - (j - i)] + (g[j] - g[i]));
                maximize(bad, f[i][j][c]);
            }

            ll sad = 0;
            fu(i, l, r) sad += g[i];
            
            cout << sad - bad;

        //
    }
}

void lovesper(const ll &TestCase) {
    
    cin >> n >> l >> r >> k;
    fu(i, 1, n) cin >> g[i];

    // if(Love1::check()) {
    //     Love1::DreamyLove();
    //     return;
    // }

    // if(Love2::check()) {
        Love2::DreamyLove();
    //     return;
    // }

}

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: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 0 / 33
• Subtask 4: 0 / 22