結果
| 問題 | No.1512 作文 |
| ユーザー |
 LayCurse
|
| 提出日時 | 2021-05-21 22:13:41 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 24 ms / 2,000 ms |
| コード長 | 5,520 bytes |
| コンパイル時間 | 2,894 ms |
| コンパイル使用メモリ | 217,684 KB |
| 最終ジャッジ日時 | 2025-01-21 15:29:34 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 38 |
ソースコード
#pragma GCC optimize ("Ofast")#include<bits/stdc++.h>using namespace std;void*wmem;char memarr[96000000];template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};(*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );(*arr)=(T*)(*mem);(*mem)=((*arr)+x);}template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){walloc1d(arr, x2-x1, mem);(*arr) -= x1;}template<class T1, class T2> void sortA_L(int N, T1 a[], T2 b[], void *mem = wmem){int i;pair<T1, T2>*arr;walloc1d(&arr, N, &mem);for(i=(0);i<(N);i++){arr[i].first = a[i];arr[i].second = b[i];}sort(arr, arr+N);for(i=(0);i<(N);i++){a[i] = arr[i].first;b[i] = arr[i].second;}}template<class T1, class T2, class T3> void sortA_L(int N, T1 a[], T2 b[], T3 c[], void *mem = wmem){int i;pair<T1, pair<T2, T3> >*arr;walloc1d(&arr, N, &mem);for(i=(0);i<(N);i++){arr[i].first = a[i];arr[i].second.first = b[i];arr[i].second.second = c[i];}sort(arr, arr+N);for(i=(0);i<(N);i++){a[i] = arr[i].first;b[i] = arr[i].second.first;c[i] = arr[i].second.second;}}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;}}inline void rd(char &c){int i;for(;;){i = my_getchar_unlocked();if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){break;}}c = i;}inline int rd(char c[]){int i;int sz = 0;for(;;){i = my_getchar_unlocked();if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){break;}}c[sz++] = i;for(;;){i = my_getchar_unlocked();if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){break;}c[sz++] = i;}c[sz]='\0';return sz;}inline int rd_int(void){int x;rd(x);return 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');}}template<class S> inline void arrInsert(const int k, int &sz, S a[], const S aval){int i;sz++;for(i=sz-1;i>k;i--){a[i] = a[i-1];}a[k] = aval;}template<class S, class T> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval){int i;sz++;for(i=sz-1;i>k;i--){a[i] = a[i-1];}for(i=sz-1;i>k;i--){b[i] = b[i-1];}a[k] = aval;b[k] = bval;}template<class S, class T, class U> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval){int i;sz++;for(i=sz-1;i>k;i--){a[i] = a[i-1];}for(i=sz-1;i>k;i--){b[i] = b[i-1];}for(i=sz-1;i>k;i--){c[i] = c[i-1];}a[k] = aval;b[k] = bval;c[k] = cval;}template<class S, class T, class U, class V> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const Ucval, V d[], const V dval){int i;sz++;for(i=sz-1;i>k;i--){a[i] = a[i-1];}for(i=sz-1;i>k;i--){b[i] = b[i-1];}for(i=sz-1;i>k;i--){c[i] = c[i-1];}for(i=sz-1;i>k;i--){d[i] = d[i-1];}a[k] = aval;b[k] = bval;c[k] = cval;d[k] = dval;}template<class S, class T> inline S chmax(S &a, T b){if(a<b){a=b;}return a;}int N;char S[200000+2];int sz;int a[200000];int b[200000];int c[200000];int dp[26];int main(){int Lj4PdHRW, i;wmem = memarr;int KL2GvlyY = rd_int();for(Lj4PdHRW=(0);Lj4PdHRW<(KL2GvlyY);Lj4PdHRW++){int i;N = rd(S);for(i=(1);i<(N);i++){if(S[i-1] > S[i]){goto Q5VJL1cS;}}arrInsert(sz, sz, a, S[0]-'a', b, S[N-1]-'a', c, N);Q5VJL1cS:;}sortA_L(sz, a, b, c);for(i=(0);i<(sz);i++){int j;chmax(dp[b[i]], dp[a[i]] + c[i]);for(j=(1);j<(26);j++){chmax(dp[j], dp[j-1]);}}wt_L(dp[25]);wt_L('\n');return 0;}// cLay version 20210508-1 [beta]// --- original code ---// int N; char S[2d5+2];// int sz, a[2d5], b[2d5], c[2d5];// int dp[26];// {// REP(rd_int()){// rd(S@N);// rep(i,1,N) if(S[i-1] > S[i]) break_continue;// arrInsert(sz, sz, a, S[0]-'a', b, S[N-1]-'a', c, N);// }// sortA(sz, a, b, c);// rep(i,sz){// dp[b[i]] >?= dp[a[i]] + c[i];// rep(j,1,26) dp[j] >?= dp[j-1];// }// wt(dp[25]);// }