Submission #99921

#	Time	Username	Problem	Language	Result	Execution time	Memory
99921		MohamedAhmed0	K blocks (IZhO14_blocks)	C++14	0 / 100	18 ms	16896 KiB

blocks

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5+5 ;
const int MAXK = 1e2+5 ;
pair<long long , long long>dp[MAXN][MAXK] ;
int n , k ;
long long arr[MAXN] ;

int main()
{
    scanf("%d %d" , &n , &k) ;
    for(int i = 1 ; i <= n ; ++i)
        scanf("%lld" , &arr[i]) ;
    for(int i = 0 ; i <= n ; ++i)
    {
        for(int j = 0 ; j <= k ; ++j)
            dp[i][j].first = dp[i][j].second = 1e18 ;
    }
    dp[0][0].first = dp[0][0].second = 0 ;
    for(int i = 1 ; i <= n ; ++i)
    {
        for(int j = 1 ; j <= k ; ++j)
        {
            long long MAX = dp[i-1][j].second ;
            long long a = arr[i] + dp[i-1][j-1].first ;
            long long b = dp[i-1][j].first - MAX + max(MAX , arr[i]) ;
            if(a < b)
            {
                dp[i][j].first = arr[i] + dp[i-1][j-1].first ;
                dp[i][j].second = arr[i] ;
            }
            else
            {
                dp[i][j].first = dp[i-1][j].first - MAX + max(MAX , arr[i]) ;
                dp[i][j].second = max(MAX , arr[i]) ;
            }
        }
    }
    return cout<<dp[n][k].first<<"\n" , 0 ;
}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:13: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:15:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld" , &arr[i]) ;
         ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47