oj.uz

Submission #99923

# Submission time Handle Problem Language Result Execution time Memory
99923 2019-03-08T19:01:34 Z MohamedAhmed0 K blocks (IZhO14_blocks) C++14
0 / 100
 15 ms 16840 KB 
#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)
            {
                if(arr[i] < max(MAX , arr[i]))
                {
                    dp[i][j].first = dp[i-1][j].first - MAX + max(MAX , arr[i]) ;
                    dp[i][j].second = max(MAX , arr[i]) ;
                }
                else
                {
                    dp[i][j].first = arr[i] + dp[i-1][j-1].first ;
                    dp[i][j].second = 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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Incorrect 3 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Incorrect 2 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 16840 KB Output isn't correct
2 Halted 0 ms 0 KB -