PERIODNB - PERIOD

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<algorithm>
#include<iostream>
#include<cassert>
#include<cstdio>
#include<limits>
#include<queue>
using namespace std;

const int N = 5000000;
long long a[2 * N];
int original[N];
int n, p, q, m, delta;

long long brute() {
    long long res = numeric_limits<long long>::max();
    for(int i = 0; i < n; ++i) {
        long long cost = numeric_limits<long long>::min();
        for(int j = 0; j < n; ++j)
            cost = max(cost, original[(i + j) % n] + (j + 1LL) * delta);
        res = min(res, cost);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> delta >> p >> q >> m;
    for(int i = 0; i < n; ++i)
        a[i] = original[i] = p * (i + 1LL) % m + q;
    copy(a, a + n, a + n);
    for(int i = 0; i < 2 * n; ++i)
        a[i] += (i + 1LL) * delta;
    deque<int> q;
    long long res = numeric_limits<long long>::max();
    for(int i = 0; i < 2 * n; ++i) {
        while(!q.empty() && a[i] >= a[q.back()]) q.pop_back();
        while(!q.empty() && q.front() <= i - n) q.pop_front();
        q.push_back(i);
        if(i >= n - 1)
            res = min(res, a[q.front()] - 1LL * (i - n + 1) * delta);
    }
    cout << res << endl;
    return 0;
}

Download