Submission #231172

#TimeUsernameProblemLanguageResultExecution timeMemory
231172infinite_iqK blocks (IZhO14_blocks)C++14
53 / 100
1016 ms20856 KiB
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #include <bits/stdc++.h> using namespace std; #define sqr 547 //#define mp make_pair #define mid (l+r)/2 #define pb push_back #define ppb pop_back #define fi first #define se second #define lb lower_bound #define ub upper_bound #define ins insert #define era erase #define C continue #define mem(dp,i) memset(dp,i,sizeof(dp)) #define mset multiset #define all(x) x.begin(), x.end() typedef long long ll; typedef short int si; typedef long double ld; typedef pair<int,int> pi; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll; const ll inf=1e18; const ll mod=1e9+7; const ld pai=acos(-1); int n , k ; int a [100009] , last [100009] , dp [100009][109] ; int tree [400009][2] ; void updRmq ( int node , int l , int r , int id , int val ){ if ( l == r ) { tree [node][0] = tree [node][1] = val ; return ; } if ( id <= mid ) updRmq(node*2,l,mid,id,val); else updRmq(node*2+1,mid+1,r,id,val); tree [node][0] = min ( tree[node*2][0] , tree[node*2+1][0] ) ; tree [node][1] = max ( tree[node*2][1] , tree[node*2+1][1] ) ; } int queryRmq ( int node, int l , int r , int s , int e , int t ) { if ( l > r || s > r || e < l ) { if (!t) return 1e9 ; return 0 ; } if ( s <=l && e >= r ) return tree [node][t] ; if ( !t ) return min ( queryRmq ( node*2 , l , mid , s , e , t ) , queryRmq ( node*2+1 , mid +1 , r , s , e , t ) ) ; if ( t ) return max ( queryRmq ( node*2 , l , mid , s , e , t ) , queryRmq ( node*2+1 , mid +1 , r , s , e , t ) ) ; } int main () { scanf("%d%d",&n,&k); for ( int i = 1 ; i <= n ; i ++ ) scanf("%d",&a[i]) , updRmq ( 1 , 0 , n , i , a[i] ) ; for ( int i = 1 ; i <= n ; i ++ ) { int l = 0 , r = i; while ( r - l > 1 ) { if ( queryRmq ( 1 , 0 , n , mid , i , 1 ) > a[i] ) l = mid ; else r = mid ; } last [i] = l ; } updRmq ( 1 , 0 , n , 0 , 1e9 ) ; for ( int i = 1 ; i <= n ; i ++ ) { dp [i][1] = max ( dp [i-1][1] , a[i] ) ; updRmq ( 1 , 0 , n , i , dp [i][1] ) ; } for ( int i = 0 ; i <= n ; i ++ ) { for ( int j = 2 ; j <= k ; j ++ ) { dp [i][j] = 1e9 ; } } for ( int j = 2 ; j <= k ; j ++ ) { for ( int i = j ; i <= n ; i ++ ) { int val1 = queryRmq ( 1 , 0 , n , last[i] , i-1 , 0 ) + a[i] ; int val2 = dp [last[i]][j] ; dp [i][j] = min (val1 , val2 ); } for ( int i =1 ; i <= n ; i ++ ) { updRmq ( 1 , 0 , n , i , dp[i][j] ) ; } } printf("%d\n",dp[n][k]); }

Compilation message (stderr)

blocks.cpp: In function 'int queryRmq(int, int, int, int, int, int)':
blocks.cpp:52:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
blocks.cpp: In function 'int main()':
blocks.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~
blocks.cpp:55:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for ( int i = 1 ; i <= n ; i ++ ) scanf("%d",&a[i]) , updRmq ( 1 , 0 , n , i , a[i] ) ;
                                       ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...