Submission #1096377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096377		VMaksimoski008	Sparklers (JOI17_sparklers)	C++17	0 / 100	1 ms	348 KiB

sparklers

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

int dp[1005][1005];

signed main() {
    int n, id, t, l=0, r=1e9, ans=1e9; cin >> n >> id >> t;

    vector<ll> v(n+1);
    for(int i=1; i<=n; i++) cin >> v[i];
    while(l <= r) {
        int mid = (l + r) / 2;
        
        // v[j] - 2 * mid * t * j <= v[i] - 2 * mid * t * i
        // valjda aquarelle bi rabotelo
        vector<int> R(n+1, n), L(n+1, 1);
        int i = 1;
        for(int j=1; j<=n; j++) {
            while(i < j && v[j] - 2ll * mid * t * j > v[i] - 2 * mid * t * i) i++;
            L[j] = i;
        }

        int j = n;
        for(int i=n; i>=1; i--) {
            while(j > i && v[j] - 2ll * mid * t * j > v[i] - 2 * mid * t * i) j--;
            R[i] = j;
        }

        vector<int> pref(n+1), suf(n+1);
        pref[1] = n; suf[n] = 1;
        for(int i=2; i<=n; i++) pref[i] = min(pref[i-1], R[i-1]);
        for(int i=n-1; i>=1; i--) suf[i] = max(suf[i+1], L[i+1]);

        if(pref[id] < id || suf[id] > id) { 
            l = mid + 1;
            continue;
        } 

        i = j = id;
        while(i > 1 || j < n) {
            if(i > 1 && suf[j] <= i - 1) i--;
            else if(j < n && pref[i] >= j + 1) j++;
            else break;
        }

        if(i == 1 && j == n) ans = mid, r = mid - 1;
        else l = mid + 1;
    }

    cout << ans << '\n';
    return 0;
}

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