oj.uz

Submission #1013884

# Submission time Handle Problem Language Result Execution time Memory
1013884 2024-07-04T07:34:51 Z snpmrnhlol Semiexpress (JOI17_semiexpress) C++17
100 / 100
 97 ms 604 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 3e3;
ll v[N];
ll v2[N];
ll n,m,k,a,b,c,t;
ll get(ll pos){
    ll l = 0,r = m - 1;
    while(l != r){
        ll mij = (l + r + 1)/2;
        if(pos < v[mij]){
            r = mij - 1;
        }else{
            l = mij;
        }
    }
    return v[l];
}
int main(){
    cin>>n>>m>>k;
    cin>>a>>b>>c;
    cin>>t;
    k-=m;
    for(ll i = 0;i < m;i++){
        cin>>v[i];
        v2[i] = v[i];
        v[i]--;
        v2[i]--;
    }
    ll k2 = m;
    for(ll i = 0;i < k;i++){
        ll poscand = 0,nrcand = -1;
        for(ll i = 0;i < k2 - 1;i++){
            ///find first bad
            ll pos = get(v2[i]);
            ll nxt = v2[i] + (t - pos*b - (v2[i] - pos)*c)/a;
            if(v2[i + 1] <= nxt - 1 || t - pos*b - (v2[i] - pos)*c < 0 || t - pos*b - (nxt + 1 - pos)*c < 0)continue;
            ll nxt2 = min(nxt + 1 + (t - pos*b - (nxt + 1 - pos)*c)/a,v2[i + 1] - 1);
            ///[nxt + 1,nxt2]
            if(nrcand < nxt2 - nxt){
                nrcand = nxt2 - nxt;
                poscand = nxt + 1;
            }
        }
        if(nrcand == -1)break;
        v2[k2++] = poscand;
        sort(v2,v2 + k2);
    }
    ll ans = 0;
    for(ll i = 0;i < k2 - 1;i++){
        ///find first bad
        ll pos = get(v2[i]);
        ll nxt = v2[i] + (t - pos*b - (v2[i] - pos)*c)/a;
        if(t - pos*b - (v2[i] - pos)*c < 0)continue;
        ans+=min(v2[i + 1] - 1,nxt) - v2[i] + 1;
        //cout<<"segment:"<<v2[i]<<' '<<v2[i + 1] - 1<<' '<<nxt<<'\n';
    }
    if(b*v2[k2 - 1] <= t){
        ans++;
    }
    /*for(ll i = 0;i < k2;i++){
        cout<<v2[i]<<' ';
    }
    cout<<'\n';*/
    cout<<ans - 1<<'\n';
    return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 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 0 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 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 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 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 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 420 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 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 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 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 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 420 KB Output is correct
19 Correct 31 ms 348 KB Output is correct
20 Correct 63 ms 456 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 13 ms 480 KB Output is correct
23 Correct 97 ms 344 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 14 ms 464 KB Output is correct
30 Correct 32 ms 344 KB Output is correct