Submission #42702

#	Time	Username	Problem	Language	Result	Execution time	Memory
42702		MatheusLealV	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	139 ms	33876 KiB

semiexpress

#include <bits/stdc++.h>
#define M 3005
#define f first
#define s second
using namespace std;

typedef long long ll;

ll A, B, C, W, n, m, k, S[M], dp[M], ans = -1;

vector<ll> val;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    cin>>n>>m>>k>>A>>B>>C>>W;

    for(int i = 1; i <= m; i++) cin>>S[i];

    for(int i = 1; i < m; i++)
    {
    	ll st = (S[i] - 1)*B, pos = min(S[i + 1] - 1, S[i] + (W - st)/A);

    	if(st > W) continue;

    	ans += (pos - S[i] + 1);

    	for(int cnt = 1; cnt <= k && pos <= S[i + 1] - 2; cnt ++)
    	{
    		ll st_2 = st + (pos + 1 - S[i])*C;

    		if(st_2 > W) continue;

    		ll nxt = min(S[i + 1] - 1, 1 + pos + (W - st_2)/A);

    		val.push_back(nxt - pos);

    		pos = nxt;
    	}
    }

    sort(val.rbegin(), val.rend());

    for(int i = 0; i < min(k - m, (ll)val.size()); i++) ans += val[i];

    if((n - 1)*B <= W) ans ++;

    cout<<ans<<"\n";
}

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