Submission #100510

#	Time	Username	Problem	Language	Result	Execution time	Memory
100510		MohamedAhmed0	K blocks (IZhO14_blocks)	C++14	0 / 100	152 ms	40976 KiB

blocks

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n , k ;
    scanf("%d %d" , &n , &k) ;
    int arr[n+1] ;
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d" , &arr[i]);
    int dp[k+1][n+1] ;
    memset(dp , 0x3f3f3f , sizeof(dp));
    dp[1][0] = -1e9 ;
    for(int j = 1 ; j <= n ; ++j)
        dp[1][j] = max(arr[j] , dp[1][j-1]) ;
    for(int i = 2 ; i <= k ; ++i)
    {
        vector< pair<int , int> >v ;
        for(int j = i ; j <= n ; ++j)
        {
            int now = dp[i-1][j-1] ;
            int MAX = arr[j] ;
            while(v.size() > 0)
            {
                pair<int , int>p = v.back();
                if(p.first + p.second >= now + MAX)
                    break;
                if(p.first + max(p.second , MAX) < now+MAX )
                    now = p.first , MAX = max(MAX , p.second) ;
                v.pop_back();
            }
            if(v.size() == 0)
                v.push_back({now , MAX}) ;
            else if(v.back().second < MAX)
                v.push_back({now , MAX}) ;
            dp[i][j] = now + MAX ;
         }
    }
    return printf("%d\n" , dp[k][n]) , 0 ;
}

Compilation message (stderr)

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

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