Submission #69935

#	Time	Username	Problem	Language	Result	Execution time	Memory
69935		Just_Solve_The_Problem	Sparklers (JOI17_sparklers)	C++11	0 / 100	4 ms	376 KiB

sparklers

#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 (stderr)

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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50