Submission #670736

#	Time	Username	Problem	Language	Result	Execution time	Memory
670736		MohammadAghil	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	1 ms	340 KiB

semiexpress

      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
 using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
     #define per(i,r,l) for(int i = (r); i >= (l); i--)
       #define rep(i,l,r) for(int i = (l); i < (r); i++)
          #define all(x) begin(x), end(x)
             #define sz(x) (int)(x).size()
                 #define pb push_back
                     #define ss second
                          #define ff first
                                  void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     #ifndef ONLINE_JUDGE
          #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
     #else
          #define er(args ...) 0
     #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 2e5 + 5, lg = 22, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll,md);return k*k%md*(b&1ll?a:1)%md;}

int main(){ IOS();
     ll n, m, k; cin >> n >> m >> k;
     ll a, b, c; cin >> a >> b >> c;
     ll t; cin >> t;
     if(a <= min(b, c)){
          b = c = a;
     } else if(c <= b){
          b = c;
     } else if(c > a){
          c = a;
     }
     assert(b <= c && c <= a);
     vector<ll> s(m);
     rep(i,0,m) cin >> s[i];
     priority_queue<pair<ll, pp>> q;
     ll ans = (n-1)*b <= t;
     auto nxt = [&](ll p, int i){
          ll rem = t - (s[i]-1)*b - (p - s[i])*c;
          if(rem >= 0){
               return min(s[i+1]-1, p + rem/a);
          }
          return p-1;
     };
     rep(i,0,m-1){
          ll rem = t - (s[i]-1)*b;
          if(rem >= 0){
               ll to = nxt(s[i], i);
               ans += to - s[i] + 1;
               // er(s[i], to);
               to++;
               if(to - s[i+1]){
                    ll v = nxt(to, i);
                    if(v >= to){
                         q.push({v-to+1, {to, i}});
                    }
               }
          }
     }
     k -= m;
     while(k-- && sz(q)){
          auto[w, tmp] = q.top();
          q.pop();
          auto[p, i] = tmp;
          ans += w;
          p += w;
          int to = nxt(p, i);
          // er(p, i, to);
          if(to >= p){
               q.push({to-p+1, {p, i}});
          }          
     }
     cout << --ans << '\n';
}

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52