oj.uz

Submission #888042

# Submission time Handle Problem Language Result Execution time Memory
888042 2023-12-15T20:28:27 Z Maite_Morale Semiexpress (JOI17_semiexpress) C++14
100 / 100
 1 ms 2548 KB 
#include<bits/stdc++.h>
#define F first
#define S second
#define MAX 500005
#define oo 1e18
#define mod 1000000007
#define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
using namespace std;
typedef long long ll;
#define pll pair<ll , ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vpll vector<pll>
 
ll m,n,a[MAX],b[MAX],r,t,t1,t2,t3,k;
ll cost(ll x,ll y){
    if(a[y]*t3+x*t2>t)return 0;
    return min(b[y]-x,max((ll)0,(t-(a[y]*t3+x*t2))/t1)+1);
}
int main(){
    fast_in
    cin>>n>>m>>k>>t1>>t3>>t2>>t;
    t2=min(t2,t1);t3=min(t3,t2);
    priority_queue<pair<ll,pll>> q;
    for(int i=0;i<m;i++){
        cin>>a[i];a[i]--;if(i>0)b[i-1]=a[i]-a[i-1];
    }b[m-1]=n-a[m-1]; 
    for(int i=0;i<m;i++){
        if(a[i]*t3<=t){
            ll p=cost(0,i);
            r+=p;//cout<<p<<" "<<i<<" "<<0<<"\n";
            q.push({cost(p,i),{p,i}});
        }
    }k-=m;
    while(!q.empty()){
        pair<ll,pll> u=q.top();q.pop();
        if(u.F==0 || k==0)break;
        k--;r+=u.F;//cout<<u.F<<" "<<u.S.S<<" "<<u.S.F<<"\n";
        q.push({cost(u.S.F+u.F,u.S.S),{u.S.F+u.F,u.S.S}});
    }
    cout<<r-1;
return 0;
}/*
1 2  3  4  5  6  7  8  9  10
1          1  1  1  1     1
0 10 20 30 25 15 25 25    27

*/

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2548 KB Output is correct
13 Correct 1 ms 2508 KB Output is correct
14 Correct 1 ms 2512 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 1 ms 2392 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 1 ms 2524 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Correct 1 ms 2532 KB Output is correct
25 Correct 1 ms 2396 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 1 ms 2396 KB Output is correct
28 Correct 1 ms 2396 KB Output is correct
29 Correct 1 ms 2396 KB Output is correct
30 Correct 1 ms 2396 KB Output is correct