Submission #518293

#	Time	Username	Problem	Language	Result	Execution time	Memory
518293		Mondeus	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	2 ms	464 KiB

semiexpress

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <sstream>
using namespace std;
const int maxn = 2e5;
long long s[maxn+5];
priority_queue<pair<long long, long long>> q;
long long pre[maxn+5];
long long dist[maxn+5];
long long n,m,k;
long long a,b,c;
long long t;
const long long MOD = 998244353;
long long cnt = 0;
long long calc(long long l, long long r, long long x)
{
    if(l > r || x < 0) return 0;
    long long ans = 0;
    long long initial = l;
    //cout << l << ' ' << r << ' ' << x << '\n';
    while(l <= r)
    {
        long long mid = (l+r)/2;
       // cout << l << ' ' << mid << '\n';
        if(x >= (mid-initial) * a)
        {
            l = mid+1;
           // cout << initial << ' ' <<  mid  << '\n';
            ans = mid - initial+1;
        }
        else r = mid-1;
    }
    //cout <<  l << ' ' << r << ' ' << ans << '\n';
    return ans;
}
void solve()
{
    cin >> n >> m >> k;
    cin >> a >> b >> c;
    cin >> t;
    k -= m;
    for(int i = 1; i <= m; i++)
    {
        cin >> s[i];
        dist[i] = s[i];
        if(i > 1)
        {
            pre[i] += pre[i-1] + b * (s[i]-s[i-1]);
        }
    }
    long long cnt = pre[m] <= t;
    for(int i = 1; i < m; i++)
    {
        int x = calc(dist[i],s[i+1]-1,t-pre[i]);
        cnt += x;
        pre[i] += c * x;
        dist[i] += x;
       // cout << x << ' ' <<  '\n';
        q.push({calc(dist[i],s[i+1]-1,t-pre[i]),i});
    }
    for(int p = 1; p <= k; p++)
    {
        long long x = q.top().first;
        long long pos = q.top().second;
       // cout << x << ' ' << pos << '\n';
        q.pop();
        cnt += x;
        pre[pos] += c * x;
        dist[pos] += x;
        q.push({calc(dist[pos],s[pos+1]-1,t-pre[pos]),pos});
    }
    cout << cnt - 1;



}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

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