Submission #165196

#	Time	Username	Problem	Language	Result	Execution time	Memory
165196		cbertram	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	4 ms	520 KiB

semiexpress

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
#define all(x) x.begin(), x.end()
#define rep(i,a,b) for(int i = a; i < b; i++)

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll N, M, K;
  cin >> N;
  cin >> M;
  cin >> K;
  ll A, B, C;
  cin >> A;
  cin >> B;
  cin >> C;
  ll T;
  cin >> T;
  vll S(M+1);
  rep(m,0,M) cin >> S[m];
  rep(m,0,M+1) S[m]--;
  S[M] = S[M-1]+1;

  ll sum = 0;
  priority_queue<pair<ll, pll>> pq;
  rep(m,0,M) {
    if(T < B*S[m]) break;
    ll reach = (T-B*S[m])/A;
    sum += min(S[m+1]-S[m], 1+reach);
    ll nextpos = S[m]+reach+1;
    if(nextpos < S[m+1] && T >= B*S[m]+C*(reach+1))
      pq.push(make_pair(min(S[m+1]-nextpos, 1+(T-B*S[m]-C*(reach+1))/A) , make_pair(nextpos, m)));
  }
  ll k = K-M;
  while(!pq.empty() && k > 0) {
    auto top = pq.top();
    pq.pop();
    sum += top.first;
    //cout << "S: " << top.second.first << '\n';
    k--;
    ll m = top.second.second;
    ll nextpos = top.second.first+top.first;
    ll timeToNextpos = B*S[m]+C*(nextpos-S[m]);
    if(nextpos < S[m+1] && T >= timeToNextpos)
      pq.push(make_pair(min(S[m+1]-nextpos, 1+(T-timeToNextpos)/A), make_pair(nextpos, m)));
  }

  cout << sum-1 << '\n';
}

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