oj.uz

Submission #518293

# Submission time Handle Problem Language Result Execution time Memory
518293 2022-01-23T10:38:12 Z Mondeus Semiexpress (JOI17_semiexpress) C++17
100 / 100
 2 ms 464 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <sstream>
using namespace std;
const int maxn = 2e5;
long long s[maxn+5];
priority_queue<pair<long long, long long>> q;
long long pre[maxn+5];
long long dist[maxn+5];
long long n,m,k;
long long a,b,c;
long long t;
const long long MOD = 998244353;
long long cnt = 0;
long long calc(long long l, long long r, long long x)
{
    if(l > r || x < 0) return 0;
    long long ans = 0;
    long long initial = l;
    //cout << l << ' ' << r << ' ' << x << '\n';
    while(l <= r)
    {
        long long mid = (l+r)/2;
       // cout << l << ' ' << mid << '\n';
        if(x >= (mid-initial) * a)
        {
            l = mid+1;
           // cout << initial << ' ' <<  mid  << '\n';
            ans = mid - initial+1;
        }
        else r = mid-1;
    }
    //cout <<  l << ' ' << r << ' ' << ans << '\n';
    return ans;
}
void solve()
{
    cin >> n >> m >> k;
    cin >> a >> b >> c;
    cin >> t;
    k -= m;
    for(int i = 1; i <= m; i++)
    {
        cin >> s[i];
        dist[i] = s[i];
        if(i > 1)
        {
            pre[i] += pre[i-1] + b * (s[i]-s[i-1]);
        }
    }
    long long cnt = pre[m] <= t;
    for(int i = 1; i < m; i++)
    {
        int x = calc(dist[i],s[i+1]-1,t-pre[i]);
        cnt += x;
        pre[i] += c * x;
        dist[i] += x;
       // cout << x << ' ' <<  '\n';
        q.push({calc(dist[i],s[i+1]-1,t-pre[i]),i});
    }
    for(int p = 1; p <= k; p++)
    {
        long long x = q.top().first;
        long long pos = q.top().second;
       // cout << x << ' ' << pos << '\n';
        q.pop();
        cnt += x;
        pre[pos] += c * x;
        dist[pos] += x;
        q.push({calc(dist[pos],s[pos+1]-1,t-pre[pos]),pos});
    }
    cout << cnt - 1;



}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 336 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

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