oj.uz

Submission #87310

# Submission time Handle Problem Language Result Execution time Memory
87310 2018-11-30T09:38:12 Z 7Polygonz K blocks (IZhO14_blocks) C++11
0 / 100
 48 ms 42592 KB 
using namespace std ;
#include <bits/stdc++.h> /* #7th-Polygon */
typedef pair < int , int > IntInt ;

const int N = 1e5 + 7 ;
const int K = 1e2 + 7 ;
const int INF = 1e9 + 7 ;

int n , k ;
unsigned int a[N] , dp[N][K] ;

int main()
{
    ios::sync_with_stdio(false) ;
    cout.tie(nullptr) ;
    cin.tie(nullptr) ;

    cin >> n >> k ;
    for (int i = 1 ; i <= n ; ++i)
        cin >> a[i] ;

    memset(dp , -1 , sizeof(dp)) ;

    dp[0][1] = 0 ;
    for (int i = 1 ; i <= n ; ++i)
        dp[i][1] = max(dp[i - 1][1] , a[i]) ;

    for (int b = 2 ; b <= k ; ++b)
    {
        stack < IntInt > my_stack ;
        for (int i = b ; i <= n ; ++i)
        {
            int min_dp = dp[i - 1][b - 1] ;
            for ( ; my_stack.size() ; my_stack.pop())
            {
                if (a[my_stack.top().first] > a[i]) break ;
                min_dp = min(min_dp , my_stack.top().second) ;
            }

            dp[i][b] = min_dp + a[i] ;
            if (my_stack.size() && dp[i][b] > dp[i][my_stack.top().first])
                dp[i][b] = dp[i][my_stack.top().first] ;
            my_stack.emplace(i , min_dp) ;
        }
    }

    cout << dp[n][k] << "\n" ;
    return 0 ;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 42232 KB Output is correct
2 Correct 38 ms 42356 KB Output is correct
3 Correct 38 ms 42356 KB Output is correct
4 Correct 37 ms 42484 KB Output is correct
5 Correct 37 ms 42520 KB Output is correct
6 Correct 36 ms 42520 KB Output is correct
7 Correct 36 ms 42520 KB Output is correct
8 Correct 37 ms 42520 KB Output is correct
9 Correct 36 ms 42520 KB Output is correct
10 Correct 43 ms 42520 KB Output is correct
11 Correct 38 ms 42520 KB Output is correct
12 Correct 38 ms 42520 KB Output is correct
13 Incorrect 43 ms 42520 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 42520 KB Output is correct
2 Correct 36 ms 42520 KB Output is correct
3 Correct 36 ms 42520 KB Output is correct
4 Correct 37 ms 42520 KB Output is correct
5 Correct 37 ms 42520 KB Output is correct
6 Correct 37 ms 42520 KB Output is correct
7 Correct 37 ms 42520 KB Output is correct
8 Correct 41 ms 42592 KB Output is correct
9 Correct 37 ms 42592 KB Output is correct
10 Correct 45 ms 42592 KB Output is correct
11 Correct 36 ms 42592 KB Output is correct
12 Correct 37 ms 42592 KB Output is correct
13 Correct 36 ms 42592 KB Output is correct
14 Incorrect 36 ms 42592 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

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

Subtask #4
0 / 47.0

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