oj.uz

Submission #165196

# Submission time Handle Problem Language Result Execution time Memory
165196 2019-11-25T19:06:35 Z cbertram Semiexpress (JOI17_semiexpress) C++14
100 / 100
 4 ms 520 KB 
#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.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 1 ms 312 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 520 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 4 ms 376 KB Output is correct
23 Correct 3 ms 504 KB Output is correct
24 Correct 2 ms 504 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 504 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 2 ms 504 KB Output is correct
30 Correct 2 ms 376 KB Output is correct