oj.uz

Submission #342891

# Submission time Handle Problem Language Result Execution time Memory
342891 2021-01-03T07:14:48 Z maskoff Money (IZhO17_money) C++17
45 / 100
 11 ms 1516 KB 
#include <bits/stdc++.h>
 
#define file ""
 
#define all(x) x.begin(), x.end()
 
#define sc second
#define fr first
 
#define pb push_back
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
 
const ll inf = 1e18 + 5;
const ll mod = 1e9 + 7;
 
const int N = 1e5 + 5;
 
int dx[] = {+1, 0, -1, 0};
int dy[] = {0, +1, 0, -1};
 
int n;
int a[N];
void solve1() {
	int res = 40;
 	for (int mask = 1; mask < (1 << n); mask += 2) {
 		//cerr << mask << endl;
 		vector<int> v[20];
 		int cur = 0;
 		for (int i = 0; i < n; i++) {
 		 	if (mask & (1 << i)) v[++cur].pb(a[i + 1]);
 		 	else v[cur].pb(a[i + 1]);
 		}
 		vector<int> ans;
 		for (int to : v[1]) ans.pb(to);
 		if (!is_sorted(all(ans))) continue;
 			
 		for (int i = 2; i <= cur; i++) {
 			//cerr << "i : " << i << endl;
 		 	for (int p = 0; p <= ans.size(); p++) {
 		 		vector<int> d = ans;
 		 		//cerr << "p : " << p << endl;
      	for (int j = 0; j < v[i].size(); j++)
      		d.insert(d.begin() + p + j, v[i][j]);
      	//for (int to : d) cerr << to << " ";
      	//cerr << endl;
      	if (is_sorted(all(d))) {
      	 	ans = d;
      	 	goto pos;
      	}
      }
      goto here;
     	pos:;
 		}
 		res = min(res, cur);
 		here:;
 	}
 	cout << res;
}
 
bool check(int l, int r) {
 	for (int i = l + 1; i <= r; i++)
 		if (a[i] < a[i - 1]) return false;
 	return true;
}
 
void solve2() {
	vector<int> dp(n + 5, 1e9);
	vector<int> all[n + 5];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++)
			all[i].pb(a[j]);
		sort(all(all[i]));
	}
	dp[0] = 0;
	for (int i = 1; i <= n; i++) {
	 	for (int j = 0; j < i; j++) {
	 		if (check(j + 1, i)) {
	 			if (j == 0) {
	 				dp[i] = 1;
	 				continue;
	 			}     /*
	 			cerr << "val : " << j + 1 << " " << i << endl;
	 			for (int p = j + 1; p <= i; p++)
	 				cerr << a[p] << " ";
	 			cerr << endl;  */   
	 			if (a[j + 1] >= all[j].back()) dp[i] = min(dp[j] + 1, dp[i]);
	 			if (a[i] <= all[j][0]) dp[i] = min(dp[j] + 1, dp[i]);
	 		 	for (int p = 0; p < all[j].size() - 1; p++) {
	 		 	 	if (a[j + 1] >= all[j][p] && a[i] <= all[j][p + 1]) {
	 		 	 	 	dp[i] = min(dp[j] + 1, dp[i]);
	 		 	 	 	goto there;
	 		 	 	}
	 			}
	 			there:;
	 		}
	 	}
	}
	//for (int i = 1; i <= n; i++) cout << i << " " << dp[i] << endl;
	cout << dp[n];
}
 
int main() {  
	ios_base :: sync_with_stdio(false);               
	cin.tie(nullptr);
	srand(time(nullptr));
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	//if (n <= 8) solve1();
	if (n <= 300) solve2();
  return 0;
}

Compilation message

money.cpp: In function 'void solve1()':
money.cpp:44:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |      for (int p = 0; p <= ans.size(); p++) {
      |                      ~~^~~~~~~~~~~~~
money.cpp:47:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |        for (int j = 0; j < v[i].size(); j++)
      |                        ~~^~~~~~~~~~~~~
money.cpp: In function 'void solve2()':
money.cpp:93:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |       for (int p = 0; p < all[j].size() - 1; p++) {
      |                       ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 0 ms 364 KB Output is correct
16 Correct 0 ms 364 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 364 KB Output is correct
20 Correct 0 ms 364 KB Output is correct
21 Correct 0 ms 364 KB Output is correct
22 Correct 0 ms 364 KB Output is correct
23 Correct 0 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 2 ms 492 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Correct 2 ms 620 KB Output is correct
33 Correct 2 ms 628 KB Output is correct
34 Correct 2 ms 620 KB Output is correct
35 Correct 2 ms 620 KB Output is correct
36 Correct 2 ms 620 KB Output is correct
37 Correct 3 ms 620 KB Output is correct
38 Correct 2 ms 620 KB Output is correct
39 Runtime error 11 ms 1516 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -