Submission #291985

#	Time	Username	Problem	Language	Result	Execution time	Memory
291985		TAMREF	Acrobat (balkan16_acrobat)	C++11	0 / 100	1 ms	384 KiB

main

#include <bits/stdc++.h>
using namespace std;

int n,m,X[2],arr[5001],dp[5001][5001][2];

int DP(int idx,int rem,int pre) {
    if(idx == n) return rem==0 ? 0 : n+1;
    
    int &ret = dp[idx][rem][pre];
    if(ret!=-1) return ret;

    ret = n+1;

    int f = 2;
    if(arr[idx] == X[0]) f = 0;
    else if(arr[idx] == X[1]) f = 1;
    
    // Change Segs
    if(rem) {
        if(f==2) ret = min(ret, DP(idx+1, rem-1, pre^1));
        else if(pre == f) ret = min(ret, DP(idx+1, rem-1, pre^1) + 2);
        else ret = min(ret, DP(idx+1, rem-1, pre^1) + 1);
    }

    // Step
    if(f==2 || f==pre) ret = min(ret, DP(idx+1, rem, pre));
    else ret = min(ret, DP(idx+1, rem, pre)+1);

    return ret;
}

int main() {
    scanf("%d%d%d",&n,&X[0],&X[1]);
    for(int i=0;i<n;i++) scanf("%d",arr+i);

    int cnt = 0, t1=0, t2=0;
    for(int i=0;i<n;i++) {
        if(arr[i] != X[0] && arr[i] != X[1]) cnt++;
        else if(arr[i] == X[0]) t1++;
        else t2++;
    }

    if(t1 && t2 && !cnt) puts("-1");
    else if(!t1 || !t2) puts("0");
    else {
        memset(dp,-1,sizeof(dp));
        
        int ans = n;
        for(int i=2;i<=cnt+1;i++) ans = min(ans, min(DP(0,i-1,0), DP(0,i-1,1)));
        printf("%d\n",ans);
    }
    
    return 0;
}

Compilation message (stderr)

main.cpp: In function 'int main()':
main.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |     scanf("%d%d%d",&n,&X[0],&X[1]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:34:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |     for(int i=0;i<n;i++) scanf("%d",arr+i);
      |                          ~~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 35
• Subtask 3: 0 / 35