Submission #1157848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157848		dnnnda	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	9 ms	2564 KiB

semiexpress

#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define ll long long
//#define int long long
//#pragma GCC optimize("Ofast, unroll-loop")
//#pragma GCC target("avx,avx2")
#pragma GCC optimize("O3")
const int inf=0x3f3f3f3f;
const ll inff=0x3f3f3f3f3f3f3f3f;
//const int X=1000000007;
const int X=998244353;

ll s[3005];
vector<int> val;

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m, k; cin >> n >> m >> k;
    k-=m;
    int A, B, C; cin >> A >> B >> C;
    ll T; cin >> T;
    for(int i=1 ; i<=m ; i++) cin >> s[i];
    s[m+1]=inff;
    ll ans=0;
    for(int i=1 ; i<m ; i++){
        //cout << i << " : \n";
        ll t=1LL*B*(s[i]-1);
        if(t>T) continue;
        int nxt=min(s[i+1],s[i]+(T-t)/A+1);
        //cout << nxt << '\n';
        ans+=nxt-s[i];
        t+=1LL*C*(nxt-s[i]);
        s[i]=nxt;
        int cnt=0;
        while(cnt++<=k&&nxt<s[i+1]&&t<=T){
            nxt=min(s[i+1],s[i]+(T-t)/A+1);
            //cout << nxt << '\n';
            val.push_back(nxt-s[i]);
            t+=1LL*C*(nxt-s[i]);
            s[i]=nxt;
        }
    }
    if(1LL*(s[m]-1)*B<=T) ans++;
    sort(val.begin(),val.end());
    //for(int i:val) cout << i << ' ';
    //cout << '\n' << ans << '\n';
    while(!val.empty()&&k--){
        ans+=val.back();
        val.pop_back();
    }
    cout << ans-1 << '\n';


    return 0;
}

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