oj.uz

Submission #810820

# Submission time Handle Problem Language Result Execution time Memory
810820 2023-08-06T15:50:42 Z AkibAzmain K blocks (IZhO14_blocks) C++17
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template < class key, class compare = less < key > >
using indexed_set = tree < key, null_type, compare, rb_tree_tag,
                           tree_order_statistics_node_update >;

int
main ()
{
  ios::sync_with_stdio (false);
  cin.tie (nullptr);
  int n, k;
  cin >> n >> k;
  vector < int > a (n);
  for (auto &x : a) cin >> x;
  vector < vector < pair < int, int > > > dp (n, vector < pair < int, int > > (k, { -1, -1 }));
  dp[0][0] = { 0, a[0] };
  for (int i = 1; i < n; ++i)
    for (int j = 0; j < k; ++j)
      {
        if (dp[i - 1][j].first != -1)
          {
            dp[i][j] = dp[i - 1][j];
            dp[i][j].second = max (dp[i][j].second, a[i]);
          }
        if (j > 0)
          {
            auto x = dp[i - 1][j - 1];
            x.first += x.second;
            x.second = a[i];
            if (dp[i][j].first == -1 || x.first + x.second < dp[i][j].first + dp[i][j].second)
              dp[i][j] = x;
          }
      };
  cout << dp[n - 1][k - 1].first + dp[n - 1][k - 1].second << '\n';
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 320 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 320 KB Output is correct
8 Correct 0 ms 324 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 320 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 320 KB Output is correct
8 Correct 0 ms 324 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 320 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 320 KB Output is correct
8 Correct 0 ms 324 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -