oj.uz

Submission #789967

# Submission time Handle Problem Language Result Execution time Memory
789967 2023-07-22T08:24:19 Z winter0101 Semiexpress (JOI17_semiexpress) C++14
18 / 100
 1 ms 328 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<<nw<<'\n';
    //cout<<nw<<'\n';
    //cout<<last<<'\n';
    if (nw==-1)break;
    lst=nw;
    last=nw;
    t1.push({nw,nw-last});
    }
    }
    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 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Halted 0 ms 0 KB -