Submission #684644

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
684644	2023-01-22T08:53:50 Z	pragmatist	Money (IZhO17_money)	C++17	45 / 100	319 ms	17000 KB

money

/*
#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];
bool ok[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) {
		ok[i][i] = 1;
		for(int j = i + 1; j <= n; ++j) {
			ok[i][j] = (ok[i][j - 1] && a[j - 1] <= a[j]);
			if(!ok[i][j]) break;
		}
	}
	int j = 1;
	for(int i = 1; i <= n; ++i) {
	    dp[i] = inf;
	    while(j <= i) {
	    	if(!ok[j][i]) {
	    	    j++;
	    		continue;
	    	}
        	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] = min(dp[i], dp[j - 1] + 1);
        		break;
        	} else {
        		j++;
        	}
		}				
	}
	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
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct

Subtask #2
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	0 ms	340 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct

Subtask #3
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	0 ms	340 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	1 ms	596 KB	Output is correct
28	Correct	1 ms	468 KB	Output is correct
29	Correct	1 ms	468 KB	Output is correct
30	Correct	1 ms	468 KB	Output is correct
31	Correct	1 ms	468 KB	Output is correct
32	Correct	1 ms	724 KB	Output is correct
33	Correct	1 ms	724 KB	Output is correct
34	Correct	2 ms	724 KB	Output is correct
35	Correct	1 ms	724 KB	Output is correct
36	Correct	1 ms	724 KB	Output is correct
37	Correct	2 ms	724 KB	Output is correct
38	Correct	1 ms	724 KB	Output is correct

Subtask #4
0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	0 ms	340 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	1 ms	596 KB	Output is correct
28	Correct	1 ms	468 KB	Output is correct
29	Correct	1 ms	468 KB	Output is correct
30	Correct	1 ms	468 KB	Output is correct
31	Correct	1 ms	468 KB	Output is correct
32	Correct	1 ms	724 KB	Output is correct
33	Correct	1 ms	724 KB	Output is correct
34	Correct	2 ms	724 KB	Output is correct
35	Correct	1 ms	724 KB	Output is correct
36	Correct	1 ms	724 KB	Output is correct
37	Correct	2 ms	724 KB	Output is correct
38	Correct	1 ms	724 KB	Output is correct
39	Runtime error	319 ms	17000 KB	Execution killed with signal 11
40	Halted	0 ms	0 KB	-

Submission #684644

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 16.0 / 16.0

Subtask #3 20.0 / 20.0

Subtask #4 0 / 55.0

Subtask #1
9.0 / 9.0

Subtask #2
16.0 / 16.0

Subtask #3
20.0 / 20.0

Subtask #4
0 / 55.0