oj.uz

Submission #129594

# Submission time Handle Problem Language Result Execution time Memory
129594 2019-07-12T17:11:43 Z miguel Semiexpress (JOI17_semiexpress) C++14
100 / 100
 3 ms 508 KB 
#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define int ll
#define sz size()
#define x first
#define y second
#define pi pair <int, int>
#define pii pair <int, pi>
#define vi vector <int>
const ll mod = 1e9 + 7;
int m, k, a, b, c, s[30005], lst[30005];
ll n, t, ans;
priority_queue<pi> p;

int calc(int i){
    ll cur=1LL*s[i]*b+1LL*c*(lst[i]-s[i]);
    if(cur>t) return 0;
    ll ans1=(t-cur)/a;
    ans1=min(ans1, s[i+1]-lst[i]-1);
    return (ans1+1);
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>m>>k>>a>>b>>c>>t;
    k-=m;
    for(int i=1; i<=m; i++){
        cin>>s[i];
        s[i]--;
        if(s[i] && 1LL*s[i]*b<=t) ans++;
    }
    //cout<<ans<<" ";
    for(int i=1; i<m; i++){
        ll cur=1LL*s[i]*b;
        if(cur>t) break;
        ll tm=(t-cur)/a;
        tm=min(tm, s[i+1]-s[i]-1);
        ans+=tm;
        lst[i]=s[i]+tm+1;
        if(lst[i]!=s[i+1]) p.push({calc(i), i});
    }
    //for(int i=1; i<=m; i++) cout<<lst[i]<<" "; cout<<endl;
    while(k-- && !p.empty()){
        pi tm=p.top();
        p.pop();
        //cout<<ans<<" ";
        ans+=tm.x;
        lst[tm.y]+=tm.x;
        if(lst[tm.y]!=s[tm.y+1]) p.push({calc(tm.y), tm.y});
    }
    cout<<ans;
}

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 508 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 416 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 380 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 508 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 416 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 380 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 504 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 508 KB Output is correct
24 Correct 2 ms 508 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 504 KB Output is correct
28 Correct 2 ms 504 KB Output is correct
29 Correct 2 ms 376 KB Output is correct
30 Correct 2 ms 376 KB Output is correct