oj.uz

Submission #1096377

# Submission time Handle Problem Language Result Execution time Memory
1096377 2024-10-04T11:12:59 Z VMaksimoski008 Sparklers (JOI17_sparklers) C++17
0 / 100
 1 ms 348 KB 
#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.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 50.0

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