QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#369518	#8515. KMOP	willow^#	WA	34ms	16436kb	C++17	1.8kb	2024-03-28 13:28:27	2024-03-28 13:28:28

Judging History

你现在查看的是最新测评结果

[2024-03-28 13:28:28]
评测

测评结果：WA
用时：34ms
内存：16436kb

查看

[2024-03-28 13:28:27]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5, inf = 0x3f3f3f3f;
char s[maxn];
int n, dp[maxn][3];
int Vowel(char c) {
    return c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U' || c == 'Y';
}
int main() {
    scanf("%d", &n);
    memset(dp, inf, sizeof dp);
    dp[0][0] = 0;
    for(int i = 1; i <= n; ++ i) {
        scanf("%s", s + 1);
        int len = strlen(s + 1);
        len = min(len, 3);
        int pos = 1;
        while(pos <= len && !Vowel(s[pos]))
            ++ pos;
// cerr << "? " << pos << endl;
        if(pos > 3) {
            for(int j = 0; j < 2; ++ j) {
                if(dp[i - 1][j] == inf)
                    continue;
                for(int k = 1; k < 3; ++ k) {
                    if(j + k < 3) {
                        dp[i][j + k] = min(dp[i][j + k], dp[i - 1][j] + k);
                    }
                }
            }
            continue;
        }
        for(int j = 0; j < 2; ++ j) {
            if(dp[i - 1][j] == inf)
                continue;
            for(int k = 1; k < pos; ++ k) {
                if(j + k >= 3)
                    continue;
                dp[i][j + k] = min(dp[i][j + k], dp[i - 1][j] + k);
            }
        }
        int pre = 0;
        for(int j = pos; j <= len; ++ j) {
            if(Vowel(s[j])) {
                pre = 0;
            }
            else {
                ++ pre;
            }
            if(pre == 3)
                break;
            for(int k = 0; k < 2; ++ k) {
                if(dp[i - 1][k] == inf || k + pos > 3)
                    continue;
                dp[i][pre] = min(dp[i][pre], dp[i - 1][k] + j);
            }
        }
    }
    int ans = *min_element(dp[n], dp[n] + 3);
    if(ans == inf)
        puts("*");
    else
        printf("%d\n", ans);
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 15604kb

input:

3
KNUTH
MORRIS
PRATT

output:

result:

ok "4"

Test #2:

score: 0

Accepted

time: 0ms

memory: 15516kb

input:

3
KNUTH
M
PRATT

output:

result:

ok "5"

Test #3:

score: 0

Accepted

time: 0ms

memory: 15900kb

input:

3
K
M
P

output:

result:

ok "*"

Test #4:

score: 0

Accepted

time: 3ms

memory: 15496kb

input:

2
K
M

output:

result:

ok "2"

Test #5:

score: 0

Accepted

time: 0ms

memory: 15520kb

input:

4
YOU
SHOULD
BE
DANCING

output:

result:

ok "5"

Test #6:

score: 0

Accepted

time: 34ms

memory: 16348kb

input:

1000000
Y
E
U
O
I
E
I
E
E
Y
I
I
E
Y
E
U
U
O
A
I
U
O
Y
I
Y
Y
U
A
O
E
U
I
A
U
U
I
A
I
U
A
Y
I
E
U
I
O
Y
U
Y
Y
I
E
O
Y
E
A
U
O
O
I
A
E
I
I
Y
U
A
E
Y
Y
A
O
O
Y
A
U
E
A
O
I
O
Y
A
E
I
U
I
E
Y
O
U
O
I
I
Y
E
I
A
Y
U
I
I
Y
E
E
U
O
O
U
A
I
Y
A
I
I
E
O
O
A
A
I
U
I
U
O
E
U
I
E
A
O
E
A
I
O
O
Y
I
U
U
A
I
A
Y
O
A
...

output:

result:

ok "1000000"

Test #7:

score: 0

Accepted

time: 3ms

memory: 16436kb

input:

1
XAJFUEEIIUOQRUJKBDJUWYSAKPTOCXEUYMYGDOKOAGKXUYPYJYALCCXMPWSAUETUHBAOAIYIGKFLGUJVVNQOANJOYIYTXYNAIKAPEIAHVHQZINSOYPJLEBIJOGNAYWFUEIFDSNLSYEXYYAYZRTEUUEFXBUMOQIYESPKYTACAUXFLYIUYIDOUGOADUHKWOHEIEYUWENJPTOOIXMGAWOYZBMLUAKSIUEUEEECSUAFILCXIOOYIIYNMGYATUAIMZUCHXAKIUVALUMFIEUWUKWFRWALUYIDEQKNAETXEWETEGA...

output:

result:

ok "1"

Test #8:

score: 0

Accepted

time: 15ms

memory: 16192kb

input:

333333
SNE
NGO
NJA
JCE
XMU
WBE
ZZO
LTY
RHY
XZU
XZY
HXI
ZPU
FWE
HLA
BFE
NHY
ZPE
WJO
QVU
KGY
DLA
BDI
CSY
WXU
XGU
GQE
CTY
WQU
FHI
KLY
PCI
VDO
BQA
WCU
KQE
FLA
TCI
PHO
GDU
RCO
PKI
HFU
MVA
SRA
KGO
JTI
NNE
RLU
LDU
DGE
QVI
GXE
BHU
CSA
PMY
LTU
HLE
MXY
QFY
STE
WXI
XPA
PKE
DBI
GTY
XVU
MXO
JRA
RNO
FZI
RFI
NGA
Q...

output:

result:

ok "999995"

Test #9:

score: 0

Accepted

time: 3ms

memory: 15452kb

input:

1
E

output:

result:

ok "1"

Test #10:

score: 0

Accepted

time: 0ms

memory: 15600kb

input:

1
IY

output:

result:

ok "1"

Test #11:

score: 0

Accepted

time: 3ms

memory: 15564kb

input:

1
DIJ

output:

result:

ok "1"

Test #12:

score: 0

Accepted

time: 0ms

memory: 15824kb

input:

1
PJEI

output:

result:

ok "1"

Test #13:

score: 0

Accepted

time: 3ms

memory: 15568kb

input:

1
IAOLG

output:

result:

ok "1"

Test #14:

score: 0

Accepted

time: 3ms

memory: 15632kb

input:

2
V
A

output:

result:

ok "2"

Test #15:

score: 0

Accepted

time: 0ms

memory: 15788kb

input:

2
NI
YV

output:

result:

ok "2"

Test #16:

score: 0

Accepted

time: 0ms

memory: 16384kb

input:

2
GJQ
MIT

output:

result:

ok "2"

Test #17:

score: 0

Accepted

time: 4ms

memory: 16108kb

input:

2
OLOY
UPIE

output:

result:

ok "2"

Test #18:

score: 0

Accepted

time: 0ms

memory: 15612kb

input:

2
XLFIE
AMUFI

output:

result:

ok "2"

Test #19:

score: -100

Wrong Answer

time: 0ms

memory: 15316kb

input:

3
R
F
U

output:

result:

wrong answer 1st words differ - expected: '3', found: '*'