oj.uz

Submission #684642

# Submission time Handle Problem Language Result Execution time Memory
684642 2023-01-22T08:48:08 Z pragmatist Money (IZhO17_money) C++17
0 / 100
 0 ms 340 KB 
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/

#include<bits/stdc++.h>
 
#define sz(v) (int)v.size()
#define ll long long
#define pb push_back
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define nl "\n"

using namespace std;

const int N = (int)1e6 + 7; // make sure this is right
const int M = (int)1e3 + 7;
const int inf = (int)2e9 + 7;
const ll INF = (ll)3e18 + 7; 
const ll MOD = (ll)1e9 + 7; // make sure this is right

bool bit(int x, int i) {
	return x >> i & 1;
}

int sum(int x, int y) {
	x += y;
	if(x >= MOD) x -= MOD;
	return x;
}

int n, a[N], dp[N];
int b[301][301];

void solve() {
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		for(int j = 1; j <= i; ++j) b[i][j] = a[j];
		sort(b[i] + 1, b[i] + 1 + i);
	}
	for(int i = 1; i <= n; ++i) {
		bool ok = 1;
		int j = -1;
		for(int l = i; l >= 1; --l) {
			if(l < i) ok &= (a[l] <= a[l + 1]);
			if(ok) j = l;
			if(!ok) break;
		}
		assert(j != -1);
		bool can = (a[j] >= b[j - 1][j - 1] || a[i] <= b[j - 1][1]);
		
		int l = 1, r = j - 2, k = -1;
		while(l <= r) {
			int mid = (l + r) >> 1;
			if(a[i] <= b[j - 1][mid + 1]) {
				k = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		if(k != -1) {
			can |= (a[j] >= b[j - 1][k] && a[i] <= b[j - 1][k + 1]);
		}
		if(can) dp[i] = dp[j - 1] + 1;				
	}
	cout << dp[n];
}

signed main() {	
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	int test = 1;
	//cin >> test;
	for(int i = 1; i <= test; ++i) {
	 	//cout << "Case #" << i << ": ";
		solve();
	}
	return 0;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 55.0

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