QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#367779	#8515. KMOP	ucup-team1196^#	WA	91ms	174912kb	C++20	1.8kb	2024-03-26 13:49:02	2024-03-26 13:49:04

Judging History

This is the latest submission verdict.

[2024-03-26 13:49:04]
Judged

Verdict: WA
Time: 91ms
Memory: 174912kb

Show

[2024-03-26 13:49:02]
Submitted

answer

#include <bits/stdc++.h>

using namespace std;
#define int long long

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    std::cin >> n;
    vector<string> s(n + 1);
    map<char, int> mp;

    vector dp(n + 1, vector<int>(5, 1e18)), ans(n + 1, vector<int>(5, 1e18));

    mp['A'] = mp['E'] = mp['I'] = mp['O'] = mp['U'] = mp['Y'] = 1;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        if(mp[s[i][0]]) {
            dp[i][0] = 1;
        } else {
            dp[i][1] = 1;
            if(s[i].size() > 1 && mp[s[i][1]]) {
                dp[i][2] = 2;
            } else if(s[i].size() > 2 && mp[s[i][2]]) {
                dp[i][3] = 3;
            }
        }
        // for(int j = 0; j <= 3; j++) {
        //     cout << dp[i][j] << " \n"[j == 3];
        // }
    }
    ans[0][0] = 0;
    for(int i = 1; i <= n; i++) {
        ans[i][0] = min(ans[i][0], ans[i - 1][0] + dp[i][0]);
        ans[i][0] = min(ans[i][0], ans[i - 1][1] + dp[i][0]);
        ans[i][0] = min(ans[i][0], ans[i - 1][2] + dp[i][0]);

        ans[i][0] = min(ans[i][0], ans[i - 1][0] + dp[i][2]);
        ans[i][0] = min(ans[i][0], ans[i - 1][1] + dp[i][2]);
        ans[i][0] = min(ans[i][0], ans[i - 1][2] + dp[i][2]);

        ans[i][0] = min(ans[i][0], ans[i - 1][0] + dp[i][3]);
        ans[i][0] = min(ans[i][0], ans[i - 1][1] + dp[i][3]);
        ans[i][0] = min(ans[i][0], ans[i - 1][2] + dp[i][3]);

        ans[i][1] = min(ans[i][1], ans[i - 1][0] + dp[i][1]);

        ans[i][2] = min(ans[i][2], ans[i - 1][1] + dp[i][1]);
    }
    int res = 1e18;
    for(int i = 0; i <= 2; i++) {
        res = min(res, ans[n][i]);
    }

    if(res > 1e17) {
        cout << "*\n";
    } else {
        cout << res << '\n';
    }
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3588kb

input:

3
KNUTH
MORRIS
PRATT

output:

result:

ok "4"

Test #2:

score: 0

Accepted

time: 0ms

memory: 3576kb

input:

3
KNUTH
M
PRATT

output:

result:

ok "5"

Test #3:

score: 0

Accepted

time: 1ms

memory: 3760kb

input:

3
K
M
P

output:

result:

ok "*"

Test #4:

score: 0

Accepted

time: 0ms

memory: 3528kb

input:

2
K
M

output:

result:

ok "2"

Test #5:

score: 0

Accepted

time: 0ms

memory: 3836kb

input:

4
YOU
SHOULD
BE
DANCING

output:

result:

ok "5"

Test #6:

score: 0

Accepted

time: 91ms

memory: 174912kb

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

memory: 4100kb

input:

1
XAJFUEEIIUOQRUJKBDJUWYSAKPTOCXEUYMYGDOKOAGKXUYPYJYALCCXMPWSAUETUHBAOAIYIGKFLGUJVVNQOANJOYIYTXYNAIKAPEIAHVHQZINSOYPJLEBIJOGNAYWFUEIFDSNLSYEXYYAYZRTEUUEFXBUMOQIYESPKYTACAUXFLYIUYIDOUGOADUHKWOHEIEYUWENJPTOOIXMGAWOYZBMLUAKSIUEUEEECSUAFILCXIOOYIIYNMGYATUAIMZUCHXAKIUVALUMFIEUWUKWFRWALUYIDEQKNAETXEWETEGA...

output:

result:

ok "1"

Test #8:

score: -100

Wrong Answer

time: 44ms

memory: 60460kb

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:

wrong answer 1st words differ - expected: '999995', found: '555555'