Submission #670464

#	Time	Username	Problem	Language	Result	Execution time	Memory
670464		fatemetmhr	Semiexpress (JOI17_semiexpress)	C++17	48 / 100	2 ms	400 KiB

semiexpress

// ~ Be Name Khoda ~

#include<bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  1e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;

ll dp[2][maxn5], s[maxn5], have[maxn5];

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n, m, k; cin >> n >> m >> k;
    ll a, b, c, t; cin >> a >> b >> c >> t;

    for(int i = 0; i < m; i++)
        cin >> s[i];
    k -= m;
    ll ans = 0;
    for(int i = 0; i < m - 1; i++){
        ll pos = s[i], tim = (s[i] - 1) * b, done = 0;
        int mx = -1;
        for(int j = 0; j <= k; j++){
            dp[i&1][j] = have[j] = 0;
            if(tim > t || pos == s[i + 1])
                continue;
            have[j] = done + min(s[i + 1] - pos, (t - tim) / a + 1);
            ll tt = tim;
            tim += c * min(s[i + 1] - pos, (t - tim) / a + 1);
            pos = min(s[i + 1], pos + (t - tt) / a + 1);
            mx = j;
            done = have[j];
        }
        if(mx == -1)
            break;

        for(int j = 0; j <= k; j++){
            if(j + mx <= k){
                dp[i&1][j + mx] = max(dp[i&1][j + mx], dp[(i&1)^1][j] + have[mx]);
            }
            if(mx && j + mx - 1 <= k)
                dp[i&1][j + mx - 1] = max(dp[i&1][j + mx - 1], dp[(i&1)^1][j] + have[mx - 1]);
            if(k - j <= mx)
                dp[i&1][k] = max(dp[i&1][k], dp[(i&1)^1][j] + have[k - j]);
        }
        for(int j = 0; j <= k; j++){
            ans = max(ans, dp[i&1][j]);
        }
    }
    if((n - 1) * b <= t)
        ans++;
    cout << ans - 1 << endl;
}

/*
Why so fast...? 
Hold on...
Hold your breath...
Need anything else?

Nein, Kein Problem...
Das Leben war schon immer so grausam :)
*/

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