#include <iostream> #include <cstring> #include <unordered_map> #include <climits> using namespace std; int take(int i, int j, bool** c) { int r = 0; if(!c[i][j]) { r++; c[i][j] = 1; } if(j != 0) { r += take(i - 1, j - 1, c); } if(j != i) { r += take(i - 1, j, c); } return r; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, k, i, j, x; cin >> n >> k; int** p = new int*[n]; bool** c = new bool*[n]; unordered_map <int, int> um; unordered_map <int, int>::iterator it; for(i = 0; i < n; i++) { p[i] = new int[i + 1]; c[i] = new bool[i + 1]; for(j = 0; j <= i; j++) { cin >> p[i][j]; um[p[i][j]] = INT_MAX; } } for(i = 0; i < n; i++) { for(j = 0; j <= i; j++) { for(x = 0; x < n; x++) { memset(c[x], 0, (x + 1) * sizeof(bool)); } um[p[i][j]] = min(um[p[i][j]], take(i, j, c)); } } x = INT_MAX; for(it = um.begin(); it != um.end(); it++) { if(((it -> second) <= k) && ((it -> first) < x)) { x = (it -> first); } } cout << x << "\n"; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | #include <iostream> #include <cstring> #include <unordered_map> #include <climits> using namespace std; int take(int i, int j, bool** c) { int r = 0; if(!c[i][j]) { r++; c[i][j] = 1; } if(j != 0) { r += take(i - 1, j - 1, c); } if(j != i) { r += take(i - 1, j, c); } return r; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, k, i, j, x; cin >> n >> k; int** p = new int*[n]; bool** c = new bool*[n]; unordered_map <int, int> um; unordered_map <int, int>::iterator it; for(i = 0; i < n; i++) { p[i] = new int[i + 1]; c[i] = new bool[i + 1]; for(j = 0; j <= i; j++) { cin >> p[i][j]; um[p[i][j]] = INT_MAX; } } for(i = 0; i < n; i++) { for(j = 0; j <= i; j++) { for(x = 0; x < n; x++) { memset(c[x], 0, (x + 1) * sizeof(bool)); } um[p[i][j]] = min(um[p[i][j]], take(i, j, c)); } } x = INT_MAX; for(it = um.begin(); it != um.end(); it++) { if(((it -> second) <= k) && ((it -> first) < x)) { x = (it -> first); } } cout << x << "\n"; return 0; } |