oj.uz

답안 #87310

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
87310 2018-11-30T09:38:12 Z 7Polygonz K개의 묶음 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 42592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 42592 KB Output isn't correct
2 Halted 0 ms 0 KB -