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;
}