提出 #17971476

ソースコード 拡げる

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int n;
vector<int>v;
string s;

int cache[20][200];

int dp(int i, int sum)
{
    if(i == n)
    {
        if(sum%3 == 0)
            return 0;
        else
            return 1e6;
    }
    int &ans = cache[i][sum];
    if(ans != -1)
        return ans;

    ans = 0;
    int add = s[i] - '0';
    ans = min(dp(i+1, sum+add), 1 + dp(i+1, sum));

    return ans;

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    memset(cache, -1, sizeof(cache));

    cin>>s;
    n = s.size();
    int ans = dp(0, 0);
    if(ans == n)
        cout<<-1;
    else
        cout<<ans;
    return 0;
}

提出情報

提出日時
問題 C - To 3
ユーザ ateev_mishra7
言語 C++ (GCC 9.2.1)
得点 300
コード長 908 Byte
結果 AC
実行時間 11 ms
メモリ 3668 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 300 / 300
結果
AC × 4
AC × 27
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All all_00.txt, all_01.txt, all_02.txt, all_03.txt, all_04.txt, all_05.txt, all_06.txt, all_07.txt, all_08.txt, all_09.txt, all_10.txt, all_11.txt, all_12.txt, all_13.txt, all_14.txt, all_15.txt, all_16.txt, handmade_00.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
ケース名 結果 実行時間 メモリ
all_00.txt AC 11 ms 3500 KiB
all_01.txt AC 2 ms 3556 KiB
all_02.txt AC 3 ms 3600 KiB
all_03.txt AC 2 ms 3624 KiB
all_04.txt AC 2 ms 3492 KiB
all_05.txt AC 3 ms 3628 KiB
all_06.txt AC 2 ms 3596 KiB
all_07.txt AC 3 ms 3624 KiB
all_08.txt AC 2 ms 3596 KiB
all_09.txt AC 2 ms 3556 KiB
all_10.txt AC 2 ms 3556 KiB
all_11.txt AC 3 ms 3596 KiB
all_12.txt AC 2 ms 3552 KiB
all_13.txt AC 2 ms 3556 KiB
all_14.txt AC 2 ms 3668 KiB
all_15.txt AC 2 ms 3652 KiB
all_16.txt AC 2 ms 3656 KiB
handmade_00.txt AC 3 ms 3616 KiB
random_00.txt AC 2 ms 3584 KiB
random_01.txt AC 2 ms 3600 KiB
random_02.txt AC 4 ms 3600 KiB
random_03.txt AC 2 ms 3620 KiB
random_04.txt AC 2 ms 3536 KiB
sample_01.txt AC 2 ms 3560 KiB
sample_02.txt AC 2 ms 3556 KiB
sample_03.txt AC 2 ms 3628 KiB
sample_04.txt AC 2 ms 3600 KiB