#include <bits/stdc++.h> #include <unordered_set> using namespace std; #define st first #define nd second #define pb push_back #define mp make_pair #define klar(v) memset(v, 0, sizeof(v)) #define bust ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define gcd(a, b) __gcd(a, b); #define debug(x) cout << #x << " " << x << endl; #define endl "\n" typedef vector<int> vi; typedef vector<pair<int, int> > vpii; typedef vector<long long> vll; typedef pair<int, int> pii; typedef pair<long long, long long> pll; typedef long long ll; const int maxn = 2e3+100; int h[maxn][maxn]; ll dp[maxn][maxn]; int main(){ int n, k; cin >> n >> k; for(int i = 1; i <= n; i++){ for(int j = 1; j <= i; j++){ cin >> h[i][j]; } } dp[1][1] = 1; for(int i = 2; i <= n; i++){ for(int j = 1; j <= i; j++){ dp[i][j] = dp[i-1][j] + dp[i-1][j-1] - dp[i-2][j-1] + 1; } } int ans = h[1][1]; for(int i = 1; i <= n; i++){ for(int j = 1; j <= i; j++){ if(dp[i][j] <= k) ans = min(ans, h[i][j]); } } cout << ans << endl; }
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 | #include <bits/stdc++.h> #include <unordered_set> using namespace std; #define st first #define nd second #define pb push_back #define mp make_pair #define klar(v) memset(v, 0, sizeof(v)) #define bust ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define gcd(a, b) __gcd(a, b); #define debug(x) cout << #x << " " << x << endl; #define endl "\n" typedef vector<int> vi; typedef vector<pair<int, int> > vpii; typedef vector<long long> vll; typedef pair<int, int> pii; typedef pair<long long, long long> pll; typedef long long ll; const int maxn = 2e3+100; int h[maxn][maxn]; ll dp[maxn][maxn]; int main(){ int n, k; cin >> n >> k; for(int i = 1; i <= n; i++){ for(int j = 1; j <= i; j++){ cin >> h[i][j]; } } dp[1][1] = 1; for(int i = 2; i <= n; i++){ for(int j = 1; j <= i; j++){ dp[i][j] = dp[i-1][j] + dp[i-1][j-1] - dp[i-2][j-1] + 1; } } int ans = h[1][1]; for(int i = 1; i <= n; i++){ for(int j = 1; j <= i; j++){ if(dp[i][j] <= k) ans = min(ans, h[i][j]); } } cout << ans << endl; } |