QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#369515	#8515. KMOP	willow^#	WA	38ms	16608kb	C++17	2.0kb	2024-03-28 13:22:37	2024-03-28 13:22:39

Judging History

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

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

测评结果：WA
用时：38ms
内存：16608kb

查看

[2024-03-28 13:22:37]
提交

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);
        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;
// cerr << "! " << j << " " << k << " " << dp[i][j + k] << " " << dp[i - 1][j] << " " << k << endl;
                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;
            }
            for(int k = 0; k < 2; ++ k) {
                if(dp[i - 1][k] == inf || k + pos > 3)
                    continue;
// cerr << j << " " << k << " " << dp[i - 1][k] << " " << endl;
                dp[i][pre] = min(dp[i][pre], dp[i - 1][k] + j);
// cerr << "Fu" << i << " " << pre << " " << dp[i - 1][k] + j << endl;
            }
        }
// cerr << dp[i][0] << " " << dp[i][1] << " " << dp[i][2] << endl;
    }
    int ans = *min_element(dp[n], dp[n] + 3);
    if(ans == inf)
        puts("*");
    else
        printf("%d\n", ans);
}

源文件, 语言: C++17

詳細信息

Test #1:

score: 100

Accepted

time: 3ms

memory: 15844kb

input:

3
KNUTH
MORRIS
PRATT

output:

result:

ok "4"

Test #2:

score: 0

Accepted

time: 3ms

memory: 15640kb

input:

3
KNUTH
M
PRATT

output:

result:

ok "5"

Test #3:

score: 0

Accepted

time: 3ms

memory: 15508kb

input:

3
K
M
P

output:

result:

ok "*"

Test #4:

score: 0

Accepted

time: 0ms

memory: 15492kb

input:

2
K
M

output:

result:

ok "2"

Test #5:

score: 0

Accepted

time: 0ms

memory: 15628kb

input:

4
YOU
SHOULD
BE
DANCING

output:

result:

ok "5"

Test #6:

score: 0

Accepted

time: 38ms

memory: 16576kb

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: 9ms

memory: 16608kb

input:

1
XAJFUEEIIUOQRUJKBDJUWYSAKPTOCXEUYMYGDOKOAGKXUYPYJYALCCXMPWSAUETUHBAOAIYIGKFLGUJVVNQOANJOYIYTXYNAIKAPEIAHVHQZINSOYPJLEBIJOGNAYWFUEIFDSNLSYEXYYAYZRTEUUEFXBUMOQIYESPKYTACAUXFLYIUYIDOUGOADUHKWOHEIEYUWENJPTOOIXMGAWOYZBMLUAKSIUEUEEECSUAFILCXIOOYIIYNMGYATUAIMZUCHXAKIUVALUMFIEUWUKWFRWALUYIDEQKNAETXEWETEGA...

output:

result:

ok "1"

Test #8:

score: 0

Accepted

time: 19ms

memory: 15496kb

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: 0ms

memory: 15568kb

input:

1
E

output:

result:

ok "1"

Test #10:

score: 0

Accepted

time: 0ms

memory: 15564kb

input:

1
IY

output:

result:

ok "1"

Test #11:

score: 0

Accepted

time: 0ms

memory: 15452kb

input:

1
DIJ

output:

result:

ok "1"

Test #12:

score: 0

Accepted

time: 0ms

memory: 15632kb

input:

1
PJEI

output:

result:

ok "1"

Test #13:

score: 0

Accepted

time: 0ms

memory: 15612kb

input:

1
IAOLG

output:

result:

ok "1"

Test #14:

score: 0

Accepted

time: 0ms

memory: 16376kb

input:

2
V
A

output:

result:

ok "2"

Test #15:

score: 0

Accepted

time: 2ms

memory: 15452kb

input:

2
NI
YV

output:

result:

ok "2"

Test #16:

score: 0

Accepted

time: 3ms

memory: 15600kb

input:

2
GJQ
MIT

output:

result:

ok "2"

Test #17:

score: 0

Accepted

time: 0ms

memory: 15460kb

input:

2
OLOY
UPIE

output:

result:

ok "2"

Test #18:

score: 0

Accepted

time: 0ms

memory: 15744kb

input:

2
XLFIE
AMUFI

output:

result:

ok "2"

Test #19:

score: -100

Wrong Answer

time: 2ms

memory: 15480kb

input:

3
R
F
U

output:

result:

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