oj.uz

Submission #91396

# Submission time Handle Problem Language Result Execution time Memory
91396 2018-12-27T10:45:26 Z Aydarov03 K blocks (IZhO14_blocks) C++14
53 / 100
 2 ms 868 KB 
    #include <bits/stdc++.h>
    using namespace std;
    int a[101] , dp[101][101];


    main()
    {
        int n , k;
        cin >> n >> k;
        for(int i = 1; i <= n; i++)scanf("%d" , &a[i]);

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


        for(int i = 2; i <= k; i++)
        {

            for(int j = i; j <= n; j++)
            {
                int mx = a[j];
                dp[i][j] = dp[i-1][j-1] + a[j];
                for(int t = j; t >= i; t--)
                {
                    mx = max(mx , a[t]);
                    dp[i][j] = min( dp[i][j] , dp[i-1][t-1] + mx);
                }
            }
        }

        cout << dp[k][n];

    }

Compilation message

blocks.cpp:6:10: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
     main()
          ^
blocks.cpp: In function 'int main()':
blocks.cpp:10:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for(int i = 1; i <= n; i++)scanf("%d" , &a[i]);
                                    ~~~~~^~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 420 KB Output is correct
5 Correct 2 ms 484 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 520 KB Output is correct
10 Correct 1 ms 520 KB Output is correct
11 Correct 2 ms 648 KB Output is correct
12 Correct 2 ms 648 KB Output is correct
13 Correct 2 ms 648 KB Output is correct
14 Correct 2 ms 648 KB Output is correct
15 Correct 2 ms 648 KB Output is correct
16 Correct 2 ms 652 KB Output is correct
17 Correct 2 ms 656 KB Output is correct
18 Correct 2 ms 660 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 664 KB Output is correct
2 Correct 2 ms 700 KB Output is correct
3 Correct 2 ms 700 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 2 ms 720 KB Output is correct
7 Correct 2 ms 720 KB Output is correct
8 Correct 2 ms 720 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 2 ms 724 KB Output is correct
13 Correct 2 ms 728 KB Output is correct
14 Correct 2 ms 732 KB Output is correct
15 Correct 2 ms 736 KB Output is correct
16 Correct 2 ms 740 KB Output is correct
17 Correct 2 ms 744 KB Output is correct
18 Correct 2 ms 744 KB Output is correct
19 Correct 2 ms 752 KB Output is correct
20 Correct 2 ms 752 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 756 KB Output is correct
2 Correct 2 ms 756 KB Output is correct
3 Correct 2 ms 756 KB Output is correct
4 Correct 2 ms 756 KB Output is correct
5 Correct 2 ms 756 KB Output is correct
6 Correct 2 ms 772 KB Output is correct
7 Correct 2 ms 772 KB Output is correct
8 Correct 2 ms 780 KB Output is correct
9 Correct 2 ms 780 KB Output is correct
10 Correct 2 ms 788 KB Output is correct
11 Correct 2 ms 788 KB Output is correct
12 Correct 2 ms 788 KB Output is correct
13 Correct 2 ms 804 KB Output is correct
14 Correct 2 ms 804 KB Output is correct
15 Correct 2 ms 808 KB Output is correct
16 Correct 2 ms 808 KB Output is correct
17 Correct 2 ms 868 KB Output is correct
18 Correct 2 ms 868 KB Output is correct
19 Correct 2 ms 868 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 868 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -