Submission #1220981


Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

#define maxN 100011

int n, i;
int a[maxN];
int dp_inc[maxN], dp_dec[maxN], dp[maxN];

int main()
{
   // freopen("test.in","r",stdin);

    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        scanf("%d", &a[i]);

        dp_inc[i] = dp_dec[i] = 1;
        if (a[i - 1] <= a[i] && i > 1) dp_inc[i] = 1 + dp_inc[i - 1];
        if (a[i - 1] >= a[i] && i > 1) dp_dec[i] = 1 + dp_dec[i - 1];

        dp[i] = 1 + min(dp[i - dp_inc[i]], dp[i - dp_dec[i]]);
    }

    printf("%d", dp[n]);




    return 0;
}

Submission Info

Submission Time
Task A - Sorted Arrays
User atatomir
Language C++14 (GCC 5.4.1)
Score 300
Code Size 750 Byte
Status AC
Exec Time 14 ms
Memory 1792 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:24:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
./Main.cpp:26:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
                           ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 3
AC × 17
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt
Case Name Status Exec Time Memory
sample_01.txt AC 5 ms 764 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask_1_01.txt AC 9 ms 1152 KB
subtask_1_02.txt AC 7 ms 1024 KB
subtask_1_03.txt AC 5 ms 768 KB
subtask_1_04.txt AC 14 ms 1792 KB
subtask_1_05.txt AC 14 ms 1792 KB
subtask_1_06.txt AC 13 ms 1792 KB
subtask_1_07.txt AC 14 ms 1792 KB
subtask_1_08.txt AC 14 ms 1792 KB
subtask_1_09.txt AC 14 ms 1792 KB
subtask_1_10.txt AC 1 ms 256 KB
subtask_1_11.txt AC 1 ms 256 KB