제출 #42702

#제출 시각아이디문제언어결과실행 시간메모리
42702MatheusLealVSemiexpress (JOI17_semiexpress)C++14
100 / 100
139 ms33876 KiB
#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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...