Editorial for PERIOD
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của happyboy99x
#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; }
Code mẫu của ladpro98
program periodnb; uses math; const fi=''; maxN=10000007; type e=record val:int64; pos,carry:longint; end; var a,timer:array[-1..maxN] of int64; stack:array[-1..maxN] of e; n,head,tail:longint; p,q,m,time,res:int64; procedure input; var f:text; i:longint; begin assign(f,fi); reset(f); readln(f,n,time); readln(f,p,q,m); close(f); end; procedure init; var i:longint; t,pp:int64; begin pp:=0; p:=p mod m; for i:=1 to n do begin pp:=pp+p; while pp>=m do pp:=pp-m; a[i]:=pp + q; end; for i:=n+1 to n shl 1 do a[i]:=a[i-n]; timer[0]:=0; for i:=1 to n shl 1 do timer[i]:=timer[i-1]+time; for i:=1 to n do a[i]:=a[i]+timer[i]; head:=1;tail:=0; res:=high(int64); end; procedure process; var i:longint; begin for i:=1 to n do begin while (head<=tail) and (stack[tail].val<=a[i]) do dec(tail); inc(tail); stack[tail].val:=a[i]; stack[tail].pos:=i; stack[tail].carry:=0; end; for i:=n+1 to n shl 1 do begin inc(stack[tail].carry); if head<>tail then inc(stack[head].carry); while (head<=tail) and (stack[head].pos<=(i-n)) do begin inc(Head); if head<>tail then inc(stack[head].carry,stack[head-1].carry); end; a[i]:=a[i]+timer[n]; while (head<=tail) and ((stack[tail].val-timer[stack[Tail].carry])<=a[i]) do begin dec(tail); if head<tail then inc(stack[tail].carry,stack[tail+1].carry); end; inc(tail); stack[tail].val:=a[i]; stack[tail].pos:=i; stack[tail].carry:=0; res:=min(res,stack[head].val-timer[stack[Head].carry]); end; end; begin input; init; process; write(res); end.
Code mẫu của skyvn97
#include<algorithm> #include<cstdio> #include<iostream> #define MAX 5000500 #define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1) #define FORD(i,b,a) for (int i=(b);i>=(a);i=i-1) using namespace std; typedef long long ll; ll a[MAX]; ll maxleft[MAX]; ll maxright[MAX]; int n; ll d; void init(void) { ll p,m,q; cin >> n; cin >> d; cin >> p >> q >> m; FOR(i,1,n) a[i]=(p*i)%m+q+d*i; FOR(i,1,n) maxleft[i]=max(maxleft[i-1],a[i]); FORD(i,n,1) maxright[i]=max(maxright[i+1],a[i]); } void process(void) { ll res; ll tmp=0; FOR(i,1,n) tmp=max(tmp,a[i]); res=tmp; FOR(i,1,n-1) { tmp=max(maxleft[i]+d*(n-i),maxright[i+1]-d*i); res=min(res,tmp); } cout << res; } int main(void) { //freopen("PERIOD.INP","r",stdin); //freopen("PERIOD.OUT","w",stdout); init(); process(); return 0; }
Comments