oj.uz

Submission #69947

# Submission time Handle Problem Language Result Execution time Memory
69947 2018-08-22T05:57:50 Z Just_Solve_The_Problem Sparklers (JOI17_sparklers) C++11
0 / 100
 3 ms 576 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define eb emplace_back
#define ll long long
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define OK puts("ok");
#define whatis(x) cerr << #x << " = " << x << endl;
#define pause system("pause");
#define ld long double

const ll N = (int)1e5 + 7;
const int inf = (int)1e9 + 7;
int mod = (int)1e9 + 7;
int n, k, t;
int X[N];

bool make(vector < ld > x, vector < ld > y) {
  if (x[0] < y[0]) return 0;
  int ok = 1;
  pii L, R;
  L = mk(0, 0);
  R = mk(0, 0);
  while (ok) {
    ok = 0;
    while (L.fr + 1 < sz(x) && x[L.fr + 1] >= y[R.sc]) {
      ok = 1;
      if (x[++L.fr] > x[L.sc]) L.sc = L.fr;
    }
    while (R.fr + 1 < sz(y) && y[R.fr + 1] <= x[L.sc]) {
      ok = 1;
      if (y[++R.fr] < y[R.sc]) R.sc = R.fr;
    }
  }
  return L.fr + 1 == sz(x) && R.fr + 1 == sz(y);
}

bool check(int s) {
  vector < ld > x, y;
  for (ll i = k; i >= 0; i--)
    x.pb(X[i] - (ld)2 * s * t * i);
  for (ll i = k; i < n; i++)
    y.pb(X[i] - (ld)2 * s * t * i);
  if (!make(x, y)) return 0;
  return 1;
}

main() {
  cin >> n >> k >> t;
  k--;
  for (ll i = 0; i < n; i++) {
    cin >> X[i];
  }
  int l = 0;
  int r = 1e9;
  while (l < r) {
    ll mid = (l + r) / 2;
    if (check(mid)) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  cout << l;
}

Compilation message

sparklers.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 3 ms 424 KB Output is correct
5 Correct 3 ms 576 KB Output is correct
6 Correct 2 ms 576 KB Output is correct
7 Correct 3 ms 576 KB Output is correct
8 Correct 3 ms 576 KB Output is correct
9 Correct 2 ms 576 KB Output is correct
10 Correct 2 ms 576 KB Output is correct
11 Correct 3 ms 576 KB Output is correct
12 Incorrect 3 ms 576 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 3 ms 424 KB Output is correct
5 Correct 3 ms 576 KB Output is correct
6 Correct 2 ms 576 KB Output is correct
7 Correct 3 ms 576 KB Output is correct
8 Correct 3 ms 576 KB Output is correct
9 Correct 2 ms 576 KB Output is correct
10 Correct 2 ms 576 KB Output is correct
11 Correct 3 ms 576 KB Output is correct
12 Incorrect 3 ms 576 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 3 ms 424 KB Output is correct
5 Correct 3 ms 576 KB Output is correct
6 Correct 2 ms 576 KB Output is correct
7 Correct 3 ms 576 KB Output is correct
8 Correct 3 ms 576 KB Output is correct
9 Correct 2 ms 576 KB Output is correct
10 Correct 2 ms 576 KB Output is correct
11 Correct 3 ms 576 KB Output is correct
12 Incorrect 3 ms 576 KB Output isn't correct
13 Halted 0 ms 0 KB -