Submission #1221799


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
 
#ifdef WIN32
    #define lld "%I64d"
#else
    #define lld "%lld"
#endif
 
#define mp make_pair
#define pb push_back
#define put(x) { cout << #x << " = "; cout << (x) << endl; }
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef double db;
 
const int M = 1e6 + 15;
const int Q = 1e9 + 7;
 
int a[M];
 
int dp[M][2];
int main() {
    srand(time(NULL));
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
	cin.tie(0);
	ios_base::sync_with_stdio(0);
 
	int n;
	cin >> n;
	if (n <= 2) {
		cout << 1;
		return 0;
	}	
	int ans = 1;
	for (int i = 0; i < n; i++) cin >> a[i];
	dp[n - 1][0] = dp[n - 1][1] = 1;
    for (int i = n - 2; i >= 0; i--) {
    	for (int it = 0; it < 2; it++) {
    		if (a[i] <= a[i + 1]) 
    			dp[i][0] = dp[i + 1][0];
    		else 
    			dp[i][0] = 1 + min(dp[i + 1][0], dp[i + 1][1]);

			if (a[i]>= a[i + 1]) 
    			dp[i][1] = dp[i + 1][1];
    		else 
    			dp[i][1] = 1 + min(dp[i + 1][0], dp[i + 1][1]);
    	}
    }
    cout << min(dp[0][0], dp[0][1]) << endl;
 
    return 0;
}   

Submission Info

Submission Time
Task A - Sorted Arrays
User ZhNV
Language C++14 (GCC 5.4.1)
Score 300
Code Size 1201 Byte
Status AC
Exec Time 13 ms
Memory 5120 KB

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 2 ms 2304 KB
sample_02.txt AC 2 ms 2304 KB
sample_03.txt AC 2 ms 2304 KB
subtask_1_01.txt AC 8 ms 2816 KB
subtask_1_02.txt AC 7 ms 2688 KB
subtask_1_03.txt AC 5 ms 2560 KB
subtask_1_04.txt AC 13 ms 5120 KB
subtask_1_05.txt AC 13 ms 5120 KB
subtask_1_06.txt AC 13 ms 5120 KB
subtask_1_07.txt AC 13 ms 5120 KB
subtask_1_08.txt AC 13 ms 5120 KB
subtask_1_09.txt AC 13 ms 5120 KB
subtask_1_10.txt AC 1 ms 256 KB
subtask_1_11.txt AC 1 ms 256 KB