oj.uz

Submission #69935

# Submission time Handle Problem Language Result Execution time Memory
69935 2018-08-22T05:30:10 Z Just_Solve_The_Problem Sparklers (JOI17_sparklers) C++11
0 / 100
 4 ms 376 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 int long long

const int 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 < int > x, vector < int > y) {
  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 < int > x, y;
  for (int i = k; i >= 0; i--)
    x.pb(X[i] - 2 * s * t * i);
  for (int i = k; i < n; i++)
    y.pb(X[i] - 2 * s * t * i);
  if (make(x, y)) return 1;
  return 0;
}

main() {
  scanf("%lld %lld %lld", &n, &k, &t);
  for (int i = 0; i < n; i++) {
    scanf("%lld", &X[i]);
  }
  int l = 0;
  int r = 1e9;
  while (r - l > 1) {
    int mid = (l + r) >> 1;
    if (check(mid)) {
      r = mid;
    } else {
      l = mid;
    }
  }
  cout << r;
}

Compilation message

sparklers.cpp:54:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
sparklers.cpp: In function 'int main()':
sparklers.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld", &n, &k, &t);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &X[i]);
     ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -