Submission #1158169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158169		dosts	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	0 ms	328 KiB

semiexpress

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 2e18,N = 5e5+1,MOD =  1e9+7;


void solve() {
    int n,m,k;
    cin >> n >> m >> k;
    int a,b,c;
    cin >> a >> b >> c;
    int t;
    cin >> t;
    vi x(m+2,inf);
    x[m+1] = n+1;
    vi lst(m+1,-1);
    for (int i=1;i<=m;i++) cin >> x[i];
    int ans = 0;
    priority_queue<pii> pq;
    for (int i=1;i<=m;i++) {
        if ((x[i]-1)*b > t) continue;
        int golast = min(x[i+1]-x[i]-1,(t-b*(x[i]-1))/a);
        lst[i] = x[i]+golast;
        ans+=golast+1;
        int city = i;
        if (lst[city] == -1) continue;
        if (lst[city]+1 == x[city+1]) continue;
        int cost = b*(x[city]-1)+c*(lst[city]+1-x[city]);
        if (t-cost < 0) continue;
        int expand = min(x[city+1]-lst[city]-1,(t-cost)/a+1);
        if (expand) pq.push({expand,city});
    }
    k-=m;
    while (k--) {
        if (pq.empty()) break;
        auto[amt,city] = pq.top();
        pq.pop();
        ans+=amt;
        lst[city]+=amt;
        if (lst[city] == -1) continue;
        if (lst[city]+1 == x[city+1]) continue;
        int cost = b*(x[city]-1)+c*(lst[city]+1-x[city]);
        if (t-cost < 0) continue;
        int expand = min(x[city+1]-lst[city]-1,(t-cost)/a+1);
        if (expand) pq.push({expand,city});
    }
    cout << ans-1 << '\n';
}


int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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