#include<bits/stdc++.h> using namespace std; #define PII pair<int,int> #define st first #define nd second #define LL long long #define pushb push_back #define popb pop_back #define cerr if(1) cout #define sz(x) (int)x.size() #define _upgrade ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) const int MXN=2e3, INF=1e9; int n, k; int tab[MXN+5][MXN+5], dp[MXN+5][MXN+5]; int safe( int i, int j ) { if( i<0 || j<0 || j>i ) return 0; return dp[i][j]+1; } void countt( ) { for( int i=0; i<n; i++ ) for( int j=0; j<=i; j++ ) dp[i][j]=safe(i-1,j-1) + safe(i-1,j) - safe(i-2,j-1); } int main( ) { _upgrade; cin>>n>>k; for( int i=0; i<n; i++ ) for( int j=0; j<=i; j++ ) cin>>tab[i][j]; countt(); int ans=INF; for( int i=0; i<n; i++ ){ for( int j=0; j<=i; j++ ) if( dp[i][j]<k ) ans=min(tab[i][j],ans); } cout<<ans<<'\n'; }
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 | #include<bits/stdc++.h> using namespace std; #define PII pair<int,int> #define st first #define nd second #define LL long long #define pushb push_back #define popb pop_back #define cerr if(1) cout #define sz(x) (int)x.size() #define _upgrade ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) const int MXN=2e3, INF=1e9; int n, k; int tab[MXN+5][MXN+5], dp[MXN+5][MXN+5]; int safe( int i, int j ) { if( i<0 || j<0 || j>i ) return 0; return dp[i][j]+1; } void countt( ) { for( int i=0; i<n; i++ ) for( int j=0; j<=i; j++ ) dp[i][j]=safe(i-1,j-1) + safe(i-1,j) - safe(i-2,j-1); } int main( ) { _upgrade; cin>>n>>k; for( int i=0; i<n; i++ ) for( int j=0; j<=i; j++ ) cin>>tab[i][j]; countt(); int ans=INF; for( int i=0; i<n; i++ ){ for( int j=0; j<=i; j++ ) if( dp[i][j]<k ) ans=min(tab[i][j],ans); } cout<<ans<<'\n'; } |