Submission #69211

#	Time	Username	Problem	Language	Result	Execution time	Memory
69211		Talant	Sparklers (JOI17_sparklers)	C++17	0 / 100	2 ms	248 KiB

sparklers

#include <bits/stdc++.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define Scan(a) scanf ("%I64d", &a)
#define scan(a) scanf ("%d", &a)
#define int long long

using namespace std;

const int inf = (int)1e9 + 7;
const int N = (int)2e6 + 7;

int n,k,t;
int a[N];
int cn;

bool check (int x) {
      int cur = a[k];
      cn = 0;
      for (int i = k + 1; i <= n; i ++) {
            int dst = x * t;
            int o = max(a[i] - dst,cur);
            if ((o - cur) > dst) return false;
            cur = o;
            cn ++;
      }
      for (int i = k - 1; i >= 1; i --) {
            int pos = min(cur,a[i] + x * cn * t);
            int dst = x * t;
            int o = max(cur - dst,pos);
            if ((o - pos) > dst) return false;
            cur = o;
      }
      return true;
}
main () {
      cin >> n >> k >> t;

      for (int i = 1; i <= n; i ++)
            cin >> a[i];


      int l = 0,r = 1e9;

      while (r - l > 1) {
            int m = (r + l) >> 1;

            if (check(m)) r = m;
            else l = m;
      }
      if (check(l)) r = l;
      cout << r << endl;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50