提出 #1490914


ソースコード 拡げる

Copy
/// d.cpp
# include <stdio.h>
# include <bits/stdc++.h>
using namespace std;
const pair < int , int > DD[] = {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define IOS ios_base :: sync_with_stdio(0);cin.tie(0)
# define p(v) cerr << #v << " = " << v << '\n'
# define p2(v) cerr << #v << " = " << (complex < decltype(v.x) > (v.x,v.y)) << '\n'
# define vi vector < int >
# define vl vector < ll >
# define pll pair < ll , ll >
# define pii pair < int , int >
# define mp make_pair
# define db long double
# define fail puts("-1")
# define yes puts("YES")
# define no puts("NO")
# define PP puts("Possible")
# define II puts("Impossible")
# define vii vector < pii >
# define vll vector < pll >
# define pb push_back
# define pdd pair < db , db >
# define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int main(void)
{
    #ifdef CF
    freopen("input","r",stdin);
    #endif // CF
    srand(time(0));
    fo << fixed << setprecision(7);
    cerr << fixed << setprecision(7);
    int n;
    fi>>n;
    static int s[1 << 20];
    for (int i = 1;i <= n;++i)
        fi>>s[i];
    static bitset < (1 << 24) > prime;
    const int N = 1e7;
    for (int i = 2;i <= N;++i)
        prime[i] = 1;
    for (int i = 2;i <= N;++i)
        if (prime[i])
            for (int j = i + i;j <= N;j += i)
                prime[j] = 0;
    auto get = [&](int k)
    {
        if (!k)
            return 0;
        if (!(k & 1))
            return 2;
        if (prime[k])
            return 1;
        return 3;
    };
    static int dp[1 << 20];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2;i <= n;++i)
    {
        dp[i] = dp[i - 1] + get(1);
        int offset = 0;
        for (int j = i;j;--j)
        {
            offset += get(s[j] - s[j - 1] - 1);
            smin(dp[i],offset + dp[j - 1] + get(s[i] - s[j - 1]));
            if (j >= 2)
                smin(dp[i],offset + dp[j - 2] + get(s[i] - s[j - 1] + 1));
        }
    }
    fo << dp[n] << '\n';
    cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
    return 0;
}

提出情報

提出日時
問題 F - Prime Flip
ユーザ reality
言語 C++14 (GCC 5.4.1)
得点 0
コード長 2342 Byte
結果 WA
実行時間 88 ms
メモリ 4352 KB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 1200
結果
AC × 3
AC × 20
WA × 55
セット名 テストケース
Sample 0_00.txt, 0_01.txt, 0_02.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt, 1_54.txt, 1_55.txt, 1_56.txt, 1_57.txt, 1_58.txt, 1_59.txt, 1_60.txt, 1_61.txt, 1_62.txt, 1_63.txt, 1_64.txt, 1_65.txt, 1_66.txt, 1_67.txt, 1_68.txt, 1_69.txt, 1_70.txt, 1_71.txt
ケース名 結果 実行時間 メモリ
0_00.txt AC 88 ms 4352 KB
0_01.txt AC 88 ms 4352 KB
0_02.txt AC 88 ms 4352 KB
1_00.txt WA 88 ms 4352 KB
1_01.txt AC 88 ms 4352 KB
1_02.txt AC 88 ms 4352 KB
1_03.txt WA 88 ms 4352 KB
1_04.txt AC 88 ms 4352 KB
1_05.txt AC 88 ms 4352 KB
1_06.txt AC 88 ms 4352 KB
1_07.txt WA 88 ms 4352 KB
1_08.txt WA 88 ms 4352 KB
1_09.txt WA 88 ms 4352 KB
1_10.txt WA 88 ms 4352 KB
1_11.txt WA 88 ms 4352 KB
1_12.txt WA 88 ms 4352 KB
1_13.txt WA 88 ms 4352 KB
1_14.txt WA 88 ms 4352 KB
1_15.txt WA 88 ms 4352 KB
1_16.txt WA 88 ms 4352 KB
1_17.txt WA 88 ms 4352 KB
1_18.txt WA 88 ms 4352 KB
1_19.txt WA 88 ms 4352 KB
1_20.txt WA 88 ms 4352 KB
1_21.txt WA 88 ms 4352 KB
1_22.txt WA 88 ms 4352 KB
1_23.txt WA 88 ms 4352 KB
1_24.txt WA 88 ms 4352 KB
1_25.txt AC 88 ms 4352 KB
1_26.txt AC 88 ms 4352 KB
1_27.txt WA 88 ms 4352 KB
1_28.txt AC 88 ms 4352 KB
1_29.txt WA 88 ms 4352 KB
1_30.txt AC 88 ms 4352 KB
1_31.txt AC 88 ms 4352 KB
1_32.txt AC 88 ms 4352 KB
1_33.txt AC 88 ms 4352 KB
1_34.txt AC 88 ms 4352 KB
1_35.txt AC 88 ms 4352 KB
1_36.txt AC 88 ms 4352 KB
1_37.txt WA 88 ms 4352 KB
1_38.txt AC 88 ms 4352 KB
1_39.txt AC 88 ms 4352 KB
1_40.txt WA 88 ms 4352 KB
1_41.txt WA 88 ms 4352 KB
1_42.txt WA 88 ms 4352 KB
1_43.txt WA 88 ms 4352 KB
1_44.txt WA 88 ms 4352 KB
1_45.txt WA 88 ms 4352 KB
1_46.txt WA 88 ms 4352 KB
1_47.txt WA 88 ms 4352 KB
1_48.txt WA 88 ms 4352 KB
1_49.txt WA 88 ms 4352 KB
1_50.txt WA 88 ms 4352 KB
1_51.txt WA 88 ms 4352 KB
1_52.txt WA 88 ms 4352 KB
1_53.txt WA 88 ms 4352 KB
1_54.txt WA 88 ms 4352 KB
1_55.txt WA 88 ms 4352 KB
1_56.txt WA 88 ms 4352 KB
1_57.txt WA 88 ms 4352 KB
1_58.txt WA 88 ms 4352 KB
1_59.txt WA 88 ms 4352 KB
1_60.txt WA 87 ms 4352 KB
1_61.txt WA 88 ms 4352 KB
1_62.txt WA 88 ms 4352 KB
1_63.txt WA 88 ms 4352 KB
1_64.txt WA 87 ms 4352 KB
1_65.txt WA 88 ms 4352 KB
1_66.txt WA 88 ms 4352 KB
1_67.txt WA 88 ms 4352 KB
1_68.txt WA 88 ms 4352 KB
1_69.txt WA 88 ms 4352 KB
1_70.txt WA 88 ms 4352 KB
1_71.txt WA 88 ms 4352 KB