oj.uz

Submission #972078

# Submission time Handle Problem Language Result Execution time Memory
972078 2024-04-30T03:51:54 Z 12345678 Semiexpress (JOI17_semiexpress) C++17
100 / 100
 6 ms 5588 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=3e3+5;

ll n, m, k, a, b, c, t, s[nx], res, x;
priority_queue<ll> pq;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>k>>a>>b>>c>>t;
    for (int i=1; i<=m; i++) cin>>s[i];
    res=(((s[m]-1)*b)<=t)-1;
    for (int i=1; i<m; i++) 
    {
        ll cur=(s[i]-1)*b;
        if (cur>t) break;
        ll lst=(t-cur)/a+s[i];
        lst=min(lst, s[i+1]-1);
        res+=lst-s[i]+1;
        //cout<<"express "<<lst<<'\n';
        for (int j=1; j<=k-m; j++)
        {
            ll st=lst+1;
            if (st>=s[i+1]) break;
            ll dist=(st-s[i])*c+cur;
            if (t<dist) break;
            ll cnt=(t-dist)/a;
            ll ed=st+cnt;
            ed=min(ed, s[i+1]-1);
            //cout<<"debug "<<i<<' '<<j<<' '<<' '<<dist<<' '<<st<<' '<<ed<<'\n';
            pq.push(ed-st+1);
            lst=ed;
        }
    }
    x=k-m;
    while (!pq.empty()&&x--) res+=pq.top(), pq.pop();
    cout<<res;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 604 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 6 ms 5588 KB Output is correct
24 Correct 1 ms 464 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 5 ms 5588 KB Output is correct
30 Correct 3 ms 2520 KB Output is correct