oj.uz

Submission #624135

# Submission time Handle Problem Language Result Execution time Memory
624135 2022-08-07T10:16:31 Z Hanksburger Semiexpress (JOI17_semiexpress) C++17
100 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
using namespace std;
priority_queue<pair<long long, pair<long long, long long> > > pq;
long long s[3005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, m, k, a, b, c, t, ans=-1;
    cin >> n >> m >> k >> a >> b >> c >> t;
    for (long long i=1; i<=m; i++)
        cin >> s[i];
    for (long long i=1; i<m; i++)
    {
        if (b*(s[i]-1)>t)
            break;
        long long x=min(s[i+1], (t-b*(s[i]-1)+a*(s[i]+1))/a);
        long long y=min(s[i+1], (t-b*(s[i]-1)-c*(x-s[i])+a*(x+1))/a);
//        cout << "i x y " << i << ' ' << x << ' ' << y << '\n';
        ans+=x-s[i];
//        cout << "ans " << ans << '\n';
        if (x<y)
            pq.push({y-x, {i, y}});
    }
    if (b*(n-1)<=t)
        ans++;
    for (long long i=m; i<k; i++)
    {
        if (pq.empty())
            break;
        ans+=pq.top().first;
        long long ind=pq.top().second.first;
        long long x=pq.top().second.second;
        long long y=min(s[ind+1], (t-b*(s[ind]-1)-c*(x-s[ind])+a*(x+1))/a);
//        cout << "ind x y " << ind << ' ' << x << ' ' << y << '\n';
        pq.pop();
        if (x<y)
            pq.push({y-x, {ind, y}});
    }
    cout << ans;
    return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 260 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 324 KB Output is correct
8 Correct 0 ms 328 KB Output is correct

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 260 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 324 KB Output is correct
8 Correct 0 ms 328 KB Output is correct
9 Correct 0 ms 328 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 324 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 328 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 1 ms 336 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 1 ms 212 KB Output is correct