Submission #593955

#	Time	Username	Problem	Language	Result	Execution time	Memory
593955		VasLemmy	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	8 ms	408 KiB

semiexpress

/// slava sovet·skomu soyuzu
#include <bits/stdc++.h>
using namespace std;
using db = long double;

#define int long long
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back

const int mod =  1000000007;
const int maxN = 200005;
const int base = 31;
const ll infty = 1000000000000000000;

int n,m,k;
int a,b,c;
int t;
int s[maxN];
int lst[3003];


void read()
{
    cin >> n >> m >> k;
    cin >> a >> b >> c;
    cin >> t;
    for(int i = 1; i <= m; i++)
    {
        cin >> s[i];
    }
    int res = 0;
    s[m+1] = n + 1;
    for(int i = 1; i <= m; i++)
    {
        if(t - (s[i] - 1) * b < 0)
        {
            lst[i] = -1;
            continue;
        }
        int lim = (t - (s[i] - 1) * b) / a + s[i];

        lim = min(lim,s[i+1]-1);
        lst[i] = lim;
        res += lim - s[i] + 1;
    }

    /*for(int i = 1;i <= m;i++)
    {
        cout << lst[i] <<'\n';
    }
    return;*/

    for(int j = 1;j <= k - m;j++)
    {
        int more = 0;
        int id = -1;
        for(int i = 1;i < m;i++)
        {
            if(lst[i] == -1) continue;
            if(lst[i] + 1 == s[i+1]) continue;
            if((s[i] - 1) * b + ((lst[i] + 1) - s[i]) * c > t) continue;
            int nxt_semi = lst[i] + 1;
            int lim = (t - ((s[i] - 1) * b + (nxt_semi - s[i]) * c)) / a + nxt_semi;
            lim = min(lim,s[i+1]-1);
            if(lim - lst[i] > more)
            {
                more = lim - lst[i];
                id = i;
            }
        }
        if(more > 0)
        {
            res += more;
            lst[id] += more;
        }
    }
    cout << res - 1;
}

void sol()
{

}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("test.inp","r",stdin);
    int tests;
    //cin >> tests;
    tests = 1;
    while (tests--)
    {
        read();
        sol();
    }
    return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52