oj.uz

Submission #42695

# Submission time Handle Problem Language Result Execution time Memory
42695 2018-03-02T20:28:55 Z MatheusLealV Semiexpress (JOI17_semiexpress) C++14
18 / 100
 2 ms 624 KB 
#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){

   return (-dp[a.f]) < (-dp[b.f]);
}

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
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 528 KB Output is correct
5 Correct 1 ms 564 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 1 ms 612 KB Output is correct
8 Correct 2 ms 612 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 528 KB Output is correct
5 Correct 1 ms 564 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 1 ms 612 KB Output is correct
8 Correct 2 ms 612 KB Output is correct
9 Correct 2 ms 612 KB Output is correct
10 Correct 1 ms 612 KB Output is correct
11 Correct 2 ms 612 KB Output is correct
12 Correct 1 ms 620 KB Output is correct
13 Correct 1 ms 624 KB Output is correct
14 Correct 2 ms 624 KB Output is correct
15 Incorrect 2 ms 624 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 528 KB Output is correct
5 Correct 1 ms 564 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 1 ms 612 KB Output is correct
8 Correct 2 ms 612 KB Output is correct
9 Correct 2 ms 612 KB Output is correct
10 Correct 1 ms 612 KB Output is correct
11 Correct 2 ms 612 KB Output is correct
12 Correct 1 ms 620 KB Output is correct
13 Correct 1 ms 624 KB Output is correct
14 Correct 2 ms 624 KB Output is correct
15 Incorrect 2 ms 624 KB Output isn't correct
16 Halted 0 ms 0 KB -