QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #797046 | #1369. Longest Common Subsequence | debian | AC ✓ | 1ms | 3720kb | C++14 | 482b | 2024-12-02 14:55:25 | 2024-12-02 14:55:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m;
int nxt[26];
char S[27];
int f[26];
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
memset(nxt,-1,sizeof nxt);
cin>>n>>m;
for(int i=1;i<=n;++i){
cin>>S;
for(int msk=0,j=m;~--j;){
nxt[S[j]-'A']&=msk;
msk|=1<<(S[j]-'A');
}
}
for(int i=m;~--i;){
int a=0;
for(int j=nxt[S[i]-'A'];j;j&=(j-1))
a=max(a,f[__builtin_ctz(j)]);
f[S[i]-'A']=a+1;
}
cout<<*max_element(f,end(f));
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3656kb
input:
6113 13 DALIBKGHEMJFC DAHLIBKGEMJFC DALIBKGEMJFHC DAHLIBKGEMJFC DALIBHKGEMJFC DALHIBKGEMJFC DHALIBKGEMJFC DALIBKGEHMJFC DAHLIBKGEMJFC DALIHBKGEMJFC DALIBKHGEMJFC DALIHBKGEMJFC DALHIBKGEMJFC DALIBKGEMJFCH DALIBKGEMJHFC DAHLIBKGEMJFC DALIBKGEMJFHC DALIBKGEMHJFC DALIBHKGEMJFC DALIBKHGEMJFC DALIBKGEMHJF...
output:
12
result:
ok single line: '12'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
3041 4 DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DACB DAC...
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
2958 22 NSRIBATQJPGELDKFVCHMUO MHNSDRUKBAFTCQJPIGELVO NSRKIUBATMQJCPHGLFVEOD NSREUBATQKJFHPGLMDVOCI UFNSRBEDATCQKJPGHMLVIO NSRBAKEMCITHQJUPGLFVDO NSKCRBUATFDQHJPMGLIVEO MNSKFRHBAETQJPDIGUCLVO NMSRBHACTDEKUQJFPIGLVO KNSRBMACTQUIJPFGDLVEHO NSMDRBACTKHIQJPFGLEVOU NSCRBEATQDJPGLKVOMUFHI UINSRCBEFKATDQJP...
output:
13
result:
ok single line: '13'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
4135 23 VBHFGJNLEDPKCTIWQUORSMA VJBHFGNLEDPKCTIWQUORSMA VBHFGNLEDJPKCTIWQUORSMA VBHFGNLEDPKCTIWQUORSMAJ VBHFGNLEDPKCTIJWQUORSMA VBHFGNLEDPJKCTIWQUORSMA VBHFGNLEDPKCTIWQUJORSMA VBHFGNLEDPKCTIWQUJORSMA VBHFGNLEDPKCTIWQUORSJMA VBHFGNLEDPKCTIWQUORSMAJ VJBHFGNLEDPKCTIWQUORSMA VBHFGNLEDPKCTIWQUOJRSMA VBHF...
output:
22
result:
ok single line: '22'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
1204 22 HKOETNMUFJSLGVRABIDCQP RIKUNMLJAFVHPEGOSBDCQT KSBRCTEJUNOIMHLPFAGDVQ KBNOMLVACUGTFRSDEPJQIH HKGJNVMLFSOTIARPEDBCQU VRBSFKNOCGMTHILJPAEDUQ JCKSERGNFPBOMIHVLAUDQT THKECNGIMPRLUFOSABDJQV FKCSNTGPEVBMLJIOHRAUDQ KNHSFCTVBORIMEGLUAJDQP KNIFHGMROLUSPECABVTDJQ IBKFUEJNHVSOCPGMLADRQT KHNRUMBIGELATSDC...
output:
7
result:
ok single line: '7'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
8807 13 CBFJLDIKAEMHG CFJLDIBAEKMHG CFBJLDKIAMHEG KCFJLDIABEMHG CBKFJLDIAMHGE ECBFJKLDIAMHG CFJLDIAMBKHGE CFJKLDIBAMEHG CFBJLEDIAMHGK CFJLEDBIAMKHG CBFJLDIAMKHEG CFJLDEIAKMBHG BCFJLEDIKAMHG CEFBKJLDIAMHG ECKFJLDBIAMHG CFKJELDBIAMHG CFJBLDKIEAMHG ECFJLDIBAMHKG KCFEBJLDIAMHG CFKJLDEBIAMHG CBFJLDIKAMHE...
output:
10
result:
ok single line: '10'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
9495 2 BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA BA...
output:
2
result:
ok single line: '2'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
9360 26 YTUSFHBJZRQWKNCLDMAPVXEGOI YUEFHJSMZRQKCWLDAPTVXGOBNI BYUFHSTJZRNWQKCLDAPVXGOIEM YUSFBHJZNWRQKCMLDEAPTVXGOI YUFHJZERBQTKCLDMAWNPVXSGOI YUNTMFHJZRQKCLDSBAPEWVXGOI YUFNEHJZWRSQKCMLDTAPBVXGOI MYUFHBJZRQTKCLDWSAPVXGONIE YWUFHJZNERQKMCLDBSAPVXGOTI SYUFHJNZRQKCLDAPVXMWGEOITB YUTFHJZRQKCLDBEAPVXGWO...
output:
19
result:
ok single line: '19'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
1869 24 CUPLKEBMFTNWVSJHAIRXGODQ ODEUPXCKBWSTMNVLIFQJHRAG UPEBTLIONWDQAXVKJSFHCMRG AUXKPOBTNVIWSLJMHEQRCDFG FUOPDBQTNCLVJHMEXKAISRGW WCMULIAPBTNESOQFKVXJDHRG UAWPFMKBSXTNEVLJCHRQGDOI IEUXSCPWABTNMVJFQKOHDRGL WXCUPBMTKNVJFOEHQLRADGIS UPABTNMVWSIKCDXFJHREOLQG IUPQEFBSXWTMNKDCOAVJLHRG OUPDBXATCNWIFVKLJ...
output:
10
result:
ok single line: '10'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
6641 25 NBDJWKSGTYVECRXILAHMPUOQF MNLFDRJQYKXWHOIEVCAPSTBGU DICTHLGSBWOMQRNEUXFKVAYJP TUKOSJCEIMDLBRXGWYANVHPQF LDMBHRVJCWXQUYESTAPFINGOK DBSUOQJRHYWXFNMAVGCPILEKT DROFXAGYSVHKMEPIJNBLQUCWT VLOGDNRCBIKSJWTXQEUYFAHMP ODJTRFQLIVWBXGEAHYPUNSKCM VIOGFUDNKBTRYHCSEXMLAJWPQ GHFLDMIJOYVUQNKBTRXAWCSEP HKDBRV...
output:
5
result:
ok single line: '5'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
9529 2 AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB AB...
output:
2
result:
ok single line: '2'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
7625 20 DSMPGROAEIFBCTQLHNKJ DTKAPBLGREQIMCJNHOSF FIAGMHLQJRBTEDNPKOSC SAQLKCGBJTNEFMODIPHR HIKNRDQJGBPTEAFLSMCO NDACRFPKSGLIQHOETBJM IHLBONDQCSFAKTGEJRPM PCKTARIOENDMJGQSHFLB RNGJTKSPMBEOFLAQICDH KIBPASJFHTCQRNGMLDOE MJGDBOQRTNHKFSIALCEP CAIGLKNBFHEOPQMRTSDJ QTJFBGNISCADOPHMKLER TKSJCIBOQMNLREPGHAD...
output:
1
result:
ok single line: '1'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
300 26 ABCDTFGHIJKLMNOPQRSEUVWXYZ ABCDEFGNIJKLMHOPQRSTUVWXYZ ABCDEFIHGJKLMNOPQRSTUVWXYZ IBCDEFGHAJKLMNOPQRSTUVWXYZ ABCDEFGHIJKLTNOPQRSMUVWXYZ ABCDEFGKIJHLMNOPQRSTUVWXYZ ABCDEFGKIJHLMNOPQRSTUVWXYZ ABCDEFGHIJLKMNOPQRSTUVWXYZ ABCDEFGHIJKLMNOPQRTSUVWXYZ ABRDEFGHIJKLMNOPQCSTUVWXYZ ABVDEFGHIJKLMNOPQRSTUCW...
output:
1
result:
ok single line: '1'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
300 26 ABCDEFGHIJTLMNOPQRSKUVWXYZ ABCDEFGHIJKLMNSPQROTUVWXYZ ABCDEFGHIJKLMYOPQRSTUVWXNZ MBCDEFGHIJKLANOPQRSTUVWXYZ ABCDEFGHIZKLMNOPQRSTUVWXYJ ABCDEFGHIJLKMNOPQRSTUVWXYZ ABCDEKGHIJFLMNOPQRSTUVWXYZ AFCDEBGHIJKLMNOPQRSTUVWXYZ ABCDEFGHIJKLMNOPQRSVUTWXYZ ABCDEFGHIJKLMNOQPRSTUVWXYZ AHCDEFGBIJKLMNOPQRSTUVW...
output:
2
result:
ok single line: '2'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
30 26 ABCDEFGHIJPLMNOKQRSTUVWXYZ ABCDEFGHSJKLMNOPQRITUVWXYZ ABCDEFGHIJKLMNOPQRSTUVXWYZ ABCDEFGHIJKLMNOPQRSTUVWXZY LBCDEFGHIJKAMNOPQRSTUVWXYZ ASCDEFGHIJKLMNOPQRBTUVWXYZ ABCNEFGHIJKLMDOPQRSTUVWXYZ ABCDEFGHIJNLMKOPQRSTUVWXYZ WBCDEFGHIJKLMNOPQRSTUVAXYZ APCDEFGHIJKLMNOBQRSTUVWXYZ ABJDEFGHICKLMNOPQRSTUVWX...
output:
8
result:
ok single line: '8'