Submission #1233370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233370		Tenis0206	Tricks of the Trade (CEOI23_trade)	C++20	5 / 100	8090 ms	5180 KiB

trade

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int oo = LLONG_MAX;
const int nmax = 3e5;

int n, k;
int c[nmax + 5], s[nmax + 5];

int r[nmax + 5], poz[nmax + 5];

int cost(int st, int dr)
{
    int rez = 0;
    vector<int> v;
    for(int i=st;i<=dr;i++)
    {
        rez -= c[i];
        v.push_back(s[i]);
    }
    sort(v.begin(), v.end(), greater<int>());
    for(int i=0;i<k;i++)
    {
        rez += v[i];
    }
    return rez;
}

void divide(int st, int dr, int min_chosen, int max_chosen)
{
    if(st > dr)
    {
        return;
    }
    int mij = (st + dr) >> 1;
    r[mij] = -oo;
    poz[mij] = 0;
    for(int j=max(min_chosen, mij + k - 1);j<=max_chosen;j++)
    {
        if(cost(mij, j) > r[mij])
        {
            poz[mij] = j;
            r[mij] = cost(mij, j);
        }
    }
    divide(st, mij - 1, min_chosen, poz[mij]);
    divide(mij + 1, dr, poz[mij], max_chosen);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    #endif // home
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
    }
    divide(1, n - k + 1, k, n);
    int rez = -oo;
    for(int i=1;i+k-1<=n;i++)
    {
        rez = max(rez, r[i]);
    }
    cout<<rez<<'\n';
    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45