Submission #1155459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155459		tsengang	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	4 ms	1544 KiB

semiexpress

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define ertunt return
const int MOD = 998244353;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
int main() {
    ll n,m,k;
    cin >> n >> m >> k;
    ll a,b,c;
    cin >> a >> b >> c;
    ll t;
    cin >> t;
    ll s[m];
    for(ll i = 0; i < m; i++)cin >> s[i];
    k-=m;
    ll ans = 0;
    vector<ll>v;
    ll cnt = 0;
    for(ll i = 1; i < m; i++){
        ll x = s[i-1];
        ll cur = s[i-1]*b - b;
        while(x < s[i]){
            if(cur > t)break;
            ll res = x+(t-cur)/a;
            res = min(res,s[i]-1);
            if(x == s[i-1]){
                ans+=res-x+1;
            }
            else v.pb(res-x+1);
            cur+=c*(res-x+1);
            x = res+1;
            cnt++;
            if(cnt >= 1e5)break;
        }
    }
    sort(all(v));
    reverse(all(v));
    for(ll i = 0; i < min(k,(ll)(v.size())); i++)ans+=v[i];
    if((n-1)*b <= t)ans++;
    cout << ans-1;
}

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