oj.uz

Submission #789976

# Submission time Handle Problem Language Result Execution time Memory
789976 2023-07-22T08:35:41 Z winter0101 Semiexpress (JOI17_semiexpress) C++14
100 / 100
 30 ms 8692 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
#define pll pair<long long,long long>
long long a[3009];
map<int,int>type;
struct cus{
int u;
long long val;
bool operator < (const cus &p)const {
return val<p.val;
}
};
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    int n,m,k;
    cin>>n>>m>>k;
    long long x,y,z,t;
    cin>>x>>y>>z>>t;
    for1(i,1,m){
    cin>>a[i];
    type[a[i]]=1;
    }
    priority_queue<cus>t1;
    for1(i,1,m-1){
    long long cost=(a[i]-1)*y;
    if (cost>t)continue;
    int last=a[i];
    int lst=a[i];
    long long tme=(t-cost);
    tme/=x;
    last+=tme;
    //cout<<i<<" "<<last<<'\n';
    for1(j,1,k-m){
    int l=last+1,r=a[i+1]-1,nw=-1;
    while (l<=r){
        int mid=(l+r)/2;
        //cerr<<mid<<'\n';
        long long cc=1ll*(mid-a[i])*z+(a[i]-1)*y;
        cc=max(cc,1ll*(mid-1-lst)*x+(lst-a[i])*z+(a[i]-1)*y);
        if (cc<=t){
            nw=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    //cerr<<i<<" "<<nw<<" "<<last<<" "<<lst<<'\n';
    //cout<<nw<<'\n';
    //cout<<last<<'\n';
    if (nw==-1)break;
    lst=nw;
    long long vcl=(a[i]-1)*y+(lst-a[i])*z;
    tme=t-vcl;
    tme/=x;
    int len=a[i+1]-1-lst+1;
    last=nw+tme;
    t1.push({nw,min(tme+1,1ll*len)});
    }
    }
    int vcl=k-m;
    for1(i,1,vcl){
    if (t1.empty())break;
    int nw=t1.top().u;
    t1.pop();
    a[++m]=nw;
    type[nw]=2;
    //cout<<nw<<'\n';
    }
    sort(a+1,a+1+m);
    int lst=1,ans=0;
    for1(i,1,m){
    if (type[a[i]]==1){
        lst=a[i];
    }
    long long cost=(a[i]-lst)*z+(lst-1)*y;
    if (cost<=t)ans++;
    }
    ans--;
    lst=1;
    //for1(i,1,m)cout<<a[i]<<'\n';
    //cout<<m<<'\n';
    for1(i,1,m-1){
    if (type[a[i]]==1){
        lst=a[i];
    }
    int l=a[i]+1,r=a[i+1]-1;
    if (l>r)continue;
    long long cost=(a[i]-lst)*z+(lst-1)*y;
    if (cost>t)continue;
    //cout<<a[i]<<" "<<a[i+1]<<" "<<cost<<'\n';
    long long tme=t-cost;
    tme/=x;
    tme=min(tme,1ll+r-l);
    ans+=tme;
    }
    cout<<ans;
}

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 328 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 2 ms 724 KB Output is correct
23 Correct 30 ms 8676 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 396 KB Output is correct
27 Correct 1 ms 460 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 22 ms 8692 KB Output is correct
30 Correct 15 ms 4556 KB Output is correct