Submission #501203

#	Time	Username	Problem	Language	Result	Execution time	Memory
501203		radal	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	469 ms	8908 KiB

semiexpress

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
const long long int N = 7e5+20,mod = 1e9+7,inf = 1e9+10,sq = 400;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
inline int poww(int n,int k){
    int c = 1;
    while (k){
        if (k&1) c = (1ll*c*n)%mod;
        n = (1ll*n*n)%mod;
        k >>= 1;
    }
    return c;
}
int dp[N][2],n,m,k,a,b,c,r[N],pre[N],ig[N],nxt[N];
ll t,ti[N];
bitset<inf> st;
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k >> a >> b >> c >> t;
    vector<pair<int,bool>> ve;
    ve.reserve(N);
    vector<int> imp;
    imp.reserve(m);
    int lst = 1;
    ve.pb({0,0});
    rep(i,0,m){
        int x;
        cin >> x;
        ve.pb({x,1});
        imp.pb(x);
    }
    int cnt = 0;
    rep(i,0,m){
        ll tm = 1ll*b*(imp[i]-1),l = imp[i];
        while (tm <= t && (t-tm)/a+l < n && (i < m-1 && (t-tm)/a+l+1 < imp[i+1]) && cnt < k-m+30000){
            int p = (t-tm)/a+l+1;
            if (st[p]) break;
            st[p] = 1;
            ve.pb({p,0});
            tm += 1ll*(p-l)*c;
            l = p;
            cnt++;
        }
        lst = imp[i];
    }
    sort(ve.begin(),ve.end());
    int sz = ve.size()-1;
    lst = 1;
    cnt = 0;
    rep(i,1,sz+1){
        ll tm = 1ll*b*(lst-1);
        if (tm > t){
            pre[i] = pre[i-1]+ve[i].X-ve[i-1].X;
        }
        else{
            int p = (t-tm)/a+lst-ve[i-1].X;
            if (p < 0) p = 0;
            if (p > ve[i].X-ve[i-1].X){
                p = ve[i].X-ve[i-1].X;
            }
            cnt += p;
            pre[i] = pre[i-1]+ve[i].X-ve[i-1].X-p;
            if (1ll*b*(ve[i].X-1) <= t && ve[i].Y && p < ve[i].X-ve[i-1].X){
                cnt++;
                pre[i]--;
            }
        }
        if (ve[i].Y) lst = ve[i].X;
        ti[i] = 1ll*b*(lst-1)+1ll*a*(ve[i].X-lst);
        dp[i][0] = -inf;
    }
    lst = 1;
    rep(i,1,sz+1){
        if (ve[i].Y) lst = ve[i].X;
        ll tm = 1ll*b*(lst-1)+1ll*c*(ve[i].X-lst);
        if (tm > t) r[i] = ve[i].X-1;
        else r[i] = min(1ll*n,(t-tm)/a+ve[i].X);
        if (!ve[i].Y) r[i] = min(r[i],*(lower_bound(imp.begin(),imp.end(),ve[i].X))-1);
        else r[i] = min(r[i],ve[i].X-1);
    }

    repr(i,sz,1){
        ig[i] = lower_bound(r,r+sz+1,ve[i].X)-r-1;
    }
    rep(d,1,k+1){
        int j = (d&1);
        rep(i,1,sz+1){
            if (ve[i].Y) dp[i][j] = dp[i-1][1-j];
            else dp[i][j] = dp[i-1][j];
            if (ti[i] <= t || ve[i].Y || r[i] < ve[i].X){
                if (ve[i].Y) lst = ve[i].X;
                continue;
            }
            int ind = ig[i];
            ll tm = 1ll*b*(lst-1);
            if (tm > t){
                dp[i][j] = max(dp[i][j],dp[ind][1-j]+r[i]-ve[i].X+1);
                continue;
            }
            int p = (t-tm)/a+lst;
            if (p >= ve[i].X) dp[i][j] = max(dp[i][j],dp[ind][1-j]+r[i]-p);
            else dp[i][j] = max(dp[i][j],dp[ind][1-j]+r[i]-ve[i].X+1);
        }
    }
    cout << dp[sz][(k&1)]+cnt-1;
}

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