Submission #42697

#	Time	Username	Problem	Language	Result	Execution time	Memory
42697		MatheusLealV	Semiexpress (JOI17_semiexpress)	C++14	0 / 100	2 ms	352 KiB

semiexpress

#include <bits/stdc++.h>
#define M 3005
#define int long long
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

typedef long long ll;

int A, B, C, W, n, m, k, S[M], marca[M], dp[M], cnt, ans;

vector<pii> val;

bool comp (pii a, pii b){

   int l1 = a.f, r1 = a.s;

   int best = max(r1 - 1, (W - dp[l1])/A + l1);

   dp[best] = dp[l1] + (best - l1)*A;

   int p = max(r1 - 1, best + (W - dp[best])/A);


   int l2 = b.f, r2 = b.s;

   int best2 = max(r2 - 1, (W - dp[l2])/A + l1);

   dp[best2] = dp[l2] + (best2 - l2)*A;

   int p2= best2 + (W - dp[best2])/A; 

   return (p - l1 > p2 - l2);

}

priority_queue<pii, std::vector<pii>, std::function<bool(pii, pii)>> pq(comp);

int32_t 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], marca[S[i]] = 1;

    sort(S + 1, S + m + 1);

    for(int i = 1; i <= m; i++)
    {
        if(i == 1) dp[S[i]] = (S[i] - 1)*A;

        else dp[S[i]] = dp[S[1]] + (S[i] - S[1])*B;

        if(i < m) pq.push({S[i], S[i + 1]});
    }

    while(!pq.empty() && cnt < k - m)
    {
    	int l = pq.top().f, r = pq.top().s;

    	pq.pop();

    	if(dp[l] >= W) continue;

    	int best = (W - dp[l])/A + l + 1;

    	if(!(l < best && best < r)) continue;

    	dp[best] = dp[l] + (best - l)*C;

    	cnt ++;

    	//cout<<"ADD "<<best<<"\n";

    	pq.push({l, best});

    	pq.push({best, r});
    }

    for(int i = 1; i <= n; i++)
    {
    	for(int j = 1; j < i; j++)
    	{
    		if(dp[i]) dp[i] = min(dp[i], dp[j] + (i - j)*A);

    		else dp[i] = dp[j] + (i - j)*A;
    	}

    	if(i > 1 && dp[i] <= W) ans ++;

    	//if(dp[i])cout<<i<<" "<<dp[i]<<"\n";
    }

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

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