Submission #1235908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235908		nasjes	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	32 ms	16796 KiB

semiexpress

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 5*1e6+7;
//const ll mod = 1e9 + 7;
const ll inf = 1e18 + 77;
#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>

ll n, m;
ll a[dim], dp[dim];
ll nw[dim], nwp[dim];
int main() {
    ll d, k, q, s, t, l, e, sm;
    cin>>n>>m>>k;
    cin>>l>>e>>sm;
    cin>>t;
    for(int i=1; i<=m; i++){
        cin>>a[i];
    }
    k-=m;
    for(int i=1; i<=k; i++){
        dp[i]=0;
    }
    vll opt;
    ll tm=0;
    ll ans=0;
    for(int i=1; i<=m-1; i++){
        tm=t-e*(a[i]-1);
        if(tm>=0)ans++;
        else break;
        if(i==1)ans--;
        ll cnt1=min(tm/l, a[i+1]-a[i]-1);
        ans+=cnt1;
        if(cnt1==a[i+1]-a[i]-1)continue;
        nw[0]=0;
        for(int j=1; j<=k; j++){
            if(tm<(nw[j-1]+cnt1+1)*sm)break;
            nw[j]=min<ll>(nw[j-1]+1+(tm-(nw[j-1]+cnt1+1)*sm)/l, a[i+1]-a[i]-cnt1-1);
            opt.pb(nw[j]-nw[j-1]);
            //  cout<<nw[j]<<" ";
        }

    }
    if((n-1)*e<=t)ans++;
    sort(opt.begin(), opt.end());
    reverse(opt.begin(), opt.end());
    for(auto x:opt){
        if(k==0)break;
        ans+=x;
        k--;
    }
    cout<<ans<<endl;


    return 0;
}

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