結果
| 問題 | No.1294 マウンテン数列 |
| ユーザー |
 LayCurse
|
| 提出日時 | 2020-11-20 23:19:30 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 31 ms / 2,000 ms |
| コード長 | 6,747 bytes |
| コンパイル時間 | 2,361 ms |
| コンパイル使用メモリ | 214,216 KB |
| 最終ジャッジ日時 | 2025-01-16 03:21:54 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 17 |
ソースコード
#pragma GCC optimize ("Ofast")#include<bits/stdc++.h>using namespace std;#define MD (998244353U)template<class S, class T> inline S max_L(S a,T b){return a>=b?a:b;}struct Modint{unsigned val;Modint(){val=0;}Modint(int a){val = ord(a);}Modint(unsigned a){val = ord(a);}Modint(long long a){val = ord(a);}Modint(unsigned long long a){val = ord(a);}inline unsigned ord(unsigned a){return a%MD;}inline unsigned ord(int a){a %= (int)MD;if(a < 0){a += MD;}return a;}inline unsigned ord(unsigned long long a){return a%MD;}inline unsigned ord(long long a){a %= (int)MD;if(a < 0){a += MD;}return a;}inline unsigned get(){return val;}inline Modint &operator+=(Modint a){val += a.val;if(val >= MD){val -= MD;}return *this;}inline Modint &operator-=(Modint a){if(val < a.val){val = val + MD - a.val;}else{val -= a.val;}return *this;}inline Modint &operator*=(Modint a){val = ((unsigned long long)val*a.val)%MD;return *this;}inline Modint &operator/=(Modint a){return *this *= a.inverse();}inline Modint operator+(Modint a){return Modint(*this)+=a;}inline Modint operator-(Modint a){return Modint(*this)-=a;}inline Modint operator*(Modint a){return Modint(*this)*=a;}inline Modint operator/(Modint a){return Modint(*this)/=a;}inline Modint operator+(int a){return Modint(*this)+=Modint(a);}inline Modint operator-(int a){return Modint(*this)-=Modint(a);}inline Modint operator*(int a){return Modint(*this)*=Modint(a);}inline Modint operator/(int a){return Modint(*this)/=Modint(a);}inline Modint operator+(long long a){return Modint(*this)+=Modint(a);}inline Modint operator-(long long a){return Modint(*this)-=Modint(a);}inline Modint operator*(long long a){return Modint(*this)*=Modint(a);}inline Modint operator/(long long a){return Modint(*this)/=Modint(a);}inline Modint operator-(void){Modint res;if(val){res.val=MD-val;}else{res.val=0;}return res;}inline operator bool(void){return val!=0;}inline operator int(void){return get();}inline operator long long(void){return get();}inline Modint inverse(){int a = val;int b = MD;int u = 1;int v = 0;int t;Modint res;while(b){t = a / b;a -= t * b;swap(a, b);u -= t * v;swap(u, v);}if(u < 0){u += MD;}res.val = u;return res;}inline Modint pw(unsigned long long b){Modint a(*this);Modint res;res.val = 1;while(b){if(b&1){res *= a;}b >>= 1;a *= a;}return res;}inline bool operator==(int a){return ord(a)==val;}inline bool operator!=(int a){return ord(a)!=val;}};inline Modint operator+(int a, Modint b){return Modint(a)+=b;}inline Modint operator-(int a, Modint b){return Modint(a)-=b;}inline Modint operator*(int a, Modint b){return Modint(a)*=b;}inline Modint operator/(int a, Modint b){return Modint(a)/=b;}inline Modint operator+(long long a, Modint b){return Modint(a)+=b;}inline Modint operator-(long long a, Modint b){return Modint(a)-=b;}inline Modint operator*(long long a, Modint b){return Modint(a)*=b;}inline Modint operator/(long long a, Modint b){return Modint(a)/=b;}inline int my_getchar_unlocked(){static char buf[1048576];static int s = 1048576;static int e = 1048576;if(s == e && e == 1048576){e = fread_unlocked(buf, 1, 1048576, stdin);s = 0;}if(s == e){return EOF;}return buf[s++];}inline void rd(int &x){int k;int m=0;x=0;for(;;){k = my_getchar_unlocked();if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){k = my_getchar_unlocked();if(k<'0'||k>'9'){break;}x=x*10+k-'0';}if(m){x=-x;}}struct MY_WRITER{char buf[1048576];int s;int e;MY_WRITER(){s = 0;e = 1048576;}~MY_WRITER(){if(s){fwrite_unlocked(buf, 1, s, stdout);}}};MY_WRITER MY_WRITER_VAR;void my_putchar_unlocked(int a){if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);MY_WRITER_VAR.s = 0;}MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;}inline void wt_L(char a){my_putchar_unlocked(a);}inline void wt_L(int x){int s=0;int m=0;char f[10];if(x<0){m=1;x=-x;}while(x){f[s++]=x%10;x/=10;}if(!s){f[s++]=0;}if(m){my_putchar_unlocked('-');}while(s--){my_putchar_unlocked(f[s]+'0');}}inline void wt_L(Modint x){int i;i = (int)x;wt_L(i);}int N;int A[2501];int samx[2501];int go[2501];Modint dp[2501];Modint dps[2501];Modint cnt[2501];int main(){int h, i;Modint res = 0;rd(N);{int Lj4PdHRW;for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){rd(A[Lj4PdHRW]);}}for(i=(1);i<(N);i++){samx[i] =max_L(samx[i-1], A[i] - A[i-1]);}for(i=(0);i<(N);i++){go[i] = i;}for(h=(1);h<(2501);h++){if(A[N-1]-A[N-2] <= h){dp[0] = 0;dps[0] = 0;for(i=(0);i<(N-1);i++){dp[i+1] = 0;while(go[i+1] > 1 && A[i+1] - A[go[i+1]-2] <= h){go[i+1]--;}dp[i+1] += dps[i] - dps[go[i+1]-1];if(samx[i] <= h){dp[i+1] += 1;}dps[i+1] = dps[i] + dp[i+1];}cnt[h] = dp[N-1];}}for(i=(1);i<(2501);i++){res += i * (cnt[i] - cnt[i-1]);}wt_L(res * 2);wt_L('\n');return 0;}// cLay version 20201120-1 [beta]// --- original code ---// #define MD 998244353// int N, A[2501], samx[2501], go[2501];// Modint dp[2501], dps[2501], cnt[2501];// {// Modint res = 0;// rd(N,A(N));//// rep(i,1,N) samx[i] = max(samx[i-1], A[i] - A[i-1]);// rep(i,N) go[i] = i;//// rep(h,1,2501) if(A[N-1]-A[N-2] <= h){// dp[0] = 0;// dps[0] = 0;// rep(i,N-1){// dp[i+1] = 0;// while(go[i+1] > 1 && A[i+1] - A[go[i+1]-2] <= h) go[i+1]--;// dp[i+1] += dps[i] - dps[go[i+1]-1];// // rrep(j,1,i+1) if(A[i+1] - A[j-1] <= h) dp[i+1] += dp[j];// if(samx[i] <= h) dp[i+1] += 1;// dps[i+1] = dps[i] + dp[i+1];// }// cnt[h] = dp[N-1];// }// rep(i,1,2501) res += i * (cnt[i] - cnt[i-1]);// wt(res * 2);// }