Submission #1490914


Source Code Expand

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;
}

Submission Info

Submission Time
Task F - Prime Flip
User reality
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2342 Byte
Status
Exec Time 88 ms
Memory 4352 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1200
Status
× 3
× 20
× 55
Set Name Test Cases
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
Case Name Status Exec Time Memory
0_00.txt 88 ms 4352 KB
0_01.txt 88 ms 4352 KB
0_02.txt 88 ms 4352 KB
1_00.txt 88 ms 4352 KB
1_01.txt 88 ms 4352 KB
1_02.txt 88 ms 4352 KB
1_03.txt 88 ms 4352 KB
1_04.txt 88 ms 4352 KB
1_05.txt 88 ms 4352 KB
1_06.txt 88 ms 4352 KB
1_07.txt 88 ms 4352 KB
1_08.txt 88 ms 4352 KB
1_09.txt 88 ms 4352 KB
1_10.txt 88 ms 4352 KB
1_11.txt 88 ms 4352 KB
1_12.txt 88 ms 4352 KB
1_13.txt 88 ms 4352 KB
1_14.txt 88 ms 4352 KB
1_15.txt 88 ms 4352 KB
1_16.txt 88 ms 4352 KB
1_17.txt 88 ms 4352 KB
1_18.txt 88 ms 4352 KB
1_19.txt 88 ms 4352 KB
1_20.txt 88 ms 4352 KB
1_21.txt 88 ms 4352 KB
1_22.txt 88 ms 4352 KB
1_23.txt 88 ms 4352 KB
1_24.txt 88 ms 4352 KB
1_25.txt 88 ms 4352 KB
1_26.txt 88 ms 4352 KB
1_27.txt 88 ms 4352 KB
1_28.txt 88 ms 4352 KB
1_29.txt 88 ms 4352 KB
1_30.txt 88 ms 4352 KB
1_31.txt 88 ms 4352 KB
1_32.txt 88 ms 4352 KB
1_33.txt 88 ms 4352 KB
1_34.txt 88 ms 4352 KB
1_35.txt 88 ms 4352 KB
1_36.txt 88 ms 4352 KB
1_37.txt 88 ms 4352 KB
1_38.txt 88 ms 4352 KB
1_39.txt 88 ms 4352 KB
1_40.txt 88 ms 4352 KB
1_41.txt 88 ms 4352 KB
1_42.txt 88 ms 4352 KB
1_43.txt 88 ms 4352 KB
1_44.txt 88 ms 4352 KB
1_45.txt 88 ms 4352 KB
1_46.txt 88 ms 4352 KB
1_47.txt 88 ms 4352 KB
1_48.txt 88 ms 4352 KB
1_49.txt 88 ms 4352 KB
1_50.txt 88 ms 4352 KB
1_51.txt 88 ms 4352 KB
1_52.txt 88 ms 4352 KB
1_53.txt 88 ms 4352 KB
1_54.txt 88 ms 4352 KB
1_55.txt 88 ms 4352 KB
1_56.txt 88 ms 4352 KB
1_57.txt 88 ms 4352 KB
1_58.txt 88 ms 4352 KB
1_59.txt 88 ms 4352 KB
1_60.txt 87 ms 4352 KB
1_61.txt 88 ms 4352 KB
1_62.txt 88 ms 4352 KB
1_63.txt 88 ms 4352 KB
1_64.txt 87 ms 4352 KB
1_65.txt 88 ms 4352 KB
1_66.txt 88 ms 4352 KB
1_67.txt 88 ms 4352 KB
1_68.txt 88 ms 4352 KB
1_69.txt 88 ms 4352 KB
1_70.txt 88 ms 4352 KB
1_71.txt 88 ms 4352 KB