oj.uz

Submission #291985

# Submission time Handle Problem Language Result Execution time Memory
291985 2020-09-06T06:38:11 Z TAMREF None (balkan16_acrobat) C++11
0 / 100
 1 ms 384 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -