Submission #6442093


Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using SB = System.Text.StringBuilder;
//using System.Threading.Tasks;
//using System.Text.RegularExpressions;
//using System.Globalization;
//using System.Diagnostics;
using static System.Console;
using System.Numerics;
using static System.Math;
using pair = Pair<int, int>;

class Program
{
    static void Main()
    {
        //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    readonly Scanner cin = new Scanner();
    readonly int[] dd = { 0, 1, 0, -1, 0 }; //→↓←↑
    readonly int mod = 1000000007;
    readonly int dom = 998244353;
    bool chmax<T>(ref T a, T b) where T : IComparable<T> { if (a.CompareTo(b) < 0) { a = b; return true; } return false; }
    bool chmin<T>(ref T a, T b) where T : IComparable<T> { if (b.CompareTo(a) < 0) { a = b; return true; } return false; }

    void solve()
    {
        var S = ReadLine();
        int N = S.Length;
        int W = N / 3 + 2;
        var last = new bool[N, N, W, 7];
        var first = new bool[N, N, W, 7];

        for (int i = 0; i < N; i++)
        {
            first[i, i, 0, 0] = true;
            last[i, i, 0, 0] = true;
            if (S[i] == 'i')
            {
                first[i, i, 0, 1] = true;
                last[i, i, 0, 1] = true;

            }
            else
            {
                first[i, i, 0, 4] = true;
                last[i, i, 0, 4] = true;
            }
        }

        var add_i = new[] { 1, 2, 2, 10, 5, 2, 5 };
        var add_w = new[] { 4, 3, 3, 6, 6, 3, 6 };
        int ans = 0;
        for (int L = 1; L < N; L++)
        {
            for (int i = 0; i + L < N; i++)
            {
                int j = i + L;
                for (int k = 0; k < W; k++)
                {
                    //左から足す
                    for (int l = 0; l < 7; l++)
                    {
                        if (!first[i + 1, j, k, l]) continue;
                        int to = S[i] == 'w' ? add_w[l] : add_i[l];
                        if (S[i] == 'i')
                        {
                            first[i, j, k, 1] = true;
                        }
                        else
                        {
                            first[i, j, k, 4] = true;
                        }
                        if (to == 10)
                        {
                            first[i, j, k, 5] = true;
                            first[i, j, k + 1, 0] = true;
                            if (i + 3 <= j)
                            {
                                for (int p = 0; p < 7; p++)
                                {
                                    first[i, j, k + 1, p] |= first[i + 3, j, k, p];
                                }
                            }
                            chmax(ref ans, k + 1);

                        }
                        else
                        {
                            first[i, j, k, to] = true;
                        }
                    }
                    //右から足す
                    for (int l = 0; l < 7; l++)
                    {
                        if (!last[i, j - 1, k, l]) continue;
                        int to = S[j] == 'w' ? add_w[l] : add_i[l];
                        if (S[j] == 'i')
                        {
                            last[i, j, k, 1] = true;
                        }
                        else
                        {
                            last[i, j, k, 4] = true;
                        }
                        if (to == 10)
                        {
                            last[i, j, k, 5] = true;

                            last[i, j, k + 1, 0] = true;
                            if (i <= j - 3)
                            {
                                for (int p = 0; p < 7; p++)
                                {
                                    last[i, j, k + 1, p] |= last[i, j - 3, k, p];
                                }
                            }


                            chmax(ref ans, k + 1);
                        }
                        else
                        {
                            last[i, j, k, to] = true;
                        }
                    }
                    for (int l = 0; l < 7; l++)
                    {
                        if (first[i, j - 1, k, l])
                        {
                            first[i, j, k, l] = true;
                        }
                        if (last[i + 1, j, k, l])
                        {
                            last[i, j, k, l] = true;
                        }
                    }
                }
            }
        }

        WriteLine(ans);
    }



}


static class Ex
{
    public static void join<T>(this IEnumerable<T> values, string sep = " ") => WriteLine(string.Join(sep, values));
    public static string concat<T>(this IEnumerable<T> values) => string.Concat(values);
    public static string reverse(this string s) { var t = s.ToCharArray(); Array.Reverse(t); return t.concat(); }

    public static int lower_bound<T>(this IList<T> arr, T val) where T : IComparable<T>
    {
        int low = 0, high = arr.Count;
        int mid;
        while (low < high)
        {
            mid = ((high - low) >> 1) + low;
            if (arr[mid].CompareTo(val) < 0) low = mid + 1;
            else high = mid;
        }
        return low;
    }
    public static int upper_bound<T>(this IList<T> arr, T val) where T : IComparable<T>
    {
        int low = 0, high = arr.Count;
        int mid;
        while (low < high)
        {
            mid = ((high - low) >> 1) + low;
            if (arr[mid].CompareTo(val) <= 0) low = mid + 1;
            else high = mid;
        }
        return low;
    }
}

class Pair<T, U> : IComparable<Pair<T, U>> where T : IComparable<T> where U : IComparable<U>
{
    public T f; public U s;
    public Pair(T f, U s) { this.f = f; this.s = s; }
    public int CompareTo(Pair<T, U> a) => f.CompareTo(a.f) != 0 ? f.CompareTo(a.f) : s.CompareTo(a.s);
    public override string ToString() => $"{f} {s}";
}

class Scanner
{
    string[] s; int i;
    readonly char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan => ReadLine().Split();
    public int[] scanint => Array.ConvertAll(scan, int.Parse);
    public long[] scanlong => Array.ConvertAll(scan, long.Parse);
    public double[] scandouble => Array.ConvertAll(scan, double.Parse);
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint => int.Parse(next);
    public long nextlong => long.Parse(next);
    public double nextdouble => double.Parse(next);
}

Submission Info

Submission Time
Task I - イウィ
User claw88
Language C# (Mono 4.6.2.0)
Score 0
Code Size 7289 Byte
Status WA
Exec Time 1454 ms
Memory 135640 KB

Judge Result

Set Name All
Score / Max Score 0 / 5
Status
AC × 4
WA × 3
Set Name Test Cases
All 00, 01, 02, 03, 04, 90, 91
Case Name Status Exec Time Memory
00 AC 1299 ms 135640 KB
01 AC 1210 ms 133720 KB
02 WA 1454 ms 133720 KB
03 WA 1343 ms 130648 KB
04 WA 1398 ms 109272 KB
90 AC 21 ms 9172 KB
91 AC 21 ms 9124 KB