Submission #1233369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233369		Tenis0206	Tricks of the Trade (CEOI23_trade)	C++20	5 / 100	8090 ms	7116 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;
}

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];
    }
    for(int i=1;i+k-1<=n;i++)
    {
        r[i] = -oo;
    }
    for(int i=1;i+k-1<=n;i++)
    {
        for(int j=max(poz[i - 1], i + k - 1);j<=n;j++)
        {
            if(cost(i, j) > r[i])
            {
                poz[i] = j;
                r[i] = cost(i, j);
            }
        }
    }
    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