oj.uz

Submission #100510

# Submission time Handle Problem Language Result Execution time Memory
100510 2019-03-11T21:04:59 Z MohamedAhmed0 K blocks (IZhO14_blocks) C++14
0 / 100
 152 ms 40976 KB 
#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

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.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 428 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 356 KB Output is correct
13 Incorrect 2 ms 384 KB Output isn't correct
14 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 252 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Incorrect 2 ms 256 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

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

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1408 KB Output is correct
2 Correct 9 ms 1152 KB Output is correct
3 Correct 13 ms 2304 KB Output is correct
4 Correct 66 ms 14200 KB Output is correct
5 Correct 152 ms 40976 KB Output is correct
6 Correct 20 ms 3072 KB Output is correct
7 Correct 76 ms 19456 KB Output is correct
8 Incorrect 2 ms 256 KB Output isn't correct
9 Halted 0 ms 0 KB -