oj.uz

Submission #165129

# Submission time Handle Problem Language Result Execution time Memory
165129 2019-11-25T08:51:32 Z cbertram Semiexpress (JOI17_semiexpress) C++14
18 / 100
 2 ms 504 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) {
    ll reach = (T-B*S[m])/A;
    if(T < B*S[m]) break;
    sum += min(S[m+1]-S[m], 1+reach);
    if(S[m]+reach+1 < S[m+1] && T >= B*S[m]+C*(reach+1))
      pq.push(make_pair(1+(T-B*S[m]-C*(reach+1))/A , make_pair(S[m]+reach+1, m)));
  }
  ll k = K-M;
  while(!pq.empty() && k > 0) {
    auto top = pq.top();
    pq.pop();
    sum += min(S[top.second.second+1]-top.second.first, top.first);
    //cout << "S: " << top.second.first << '\n';
    k--;
    ll nextpos = top.second.first+top.first;
    if(nextpos < S[top.second.second+1] && T >= B*S[top.second.second]+C*(nextpos-S[top.second.second])) {
      pq.push(make_pair(min(S[top.second.second+1]-nextpos, 1+(T-B*S[top.second.second]-C*(nextpos-S[top.second.second]))/A),
			make_pair(nextpos, top.second.second)));
    }
  }

  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 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 372 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 420 KB Output is correct

Subtask #2
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 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 372 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 420 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 420 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Incorrect 2 ms 376 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
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 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 372 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 420 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 420 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Incorrect 2 ms 376 KB Output isn't correct
16 Halted 0 ms 0 KB -