oj.uz

Submission #100813

# Submission time Handle Problem Language Result Execution time Memory
100813 2019-03-14T15:35:29 Z 1Khan K blocks (IZhO14_blocks) C++14
18 / 100
 855 ms 3464 KB 
// In the name of GOD

#include <bits/stdc++.h>

using namespace std;

#define BeGood ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define nl '\n'
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

typedef long long ll;
typedef double db;

const int N = 1e5 + 101;
const int M = 1e9 + 7;
const int d = 20;

int n, k, a[N];
vector<int> ans;
int dp[d][N];
int ANS = M;


void man(int id, int sum){
     if(sum > n){
          return;
     }
     if(id > k){
          if(sum == n){
               int answer = 0;
               int l = 1;
               int r = 0;
               for(int i = 0; i < sz(ans); ++i){
                    int res = 0;
                    r += ans[i];
                    int L = l;
                    int R = r;
                    L--;
                    R--;
                    for(int j = d; j >= 0; --j){
                         if(L + (1 << j) - 1 <= R){
                              res = max(res, dp[j][L]);
                              L += 1 << j;
                         }
                    }
                    answer += res;
                    l = r + 1;
               }
               ANS = min(ANS, answer);
               if(clock() / (double) CLOCKS_PER_SEC > 0.855){
                    cout << ANS;
                    exit(0);
               }
          }
          return;
     }
     for(int i = 1; i <= n - k + 1; ++i){
          ans.pb(i);
          sum += i;
          man(id + 1, sum);
          sum -= i;
          ans.pop_back();
     }
}
int main(){

     BeGood

     cin >> n >> k;
     for(int i = 0; i < n; ++i){
          cin >> a[i];
          dp[0][i] = a[i];
     }
     for(int i = 1; i <= d; ++i){
          for(int j = 0; j <= n - (1 << i); ++j){
               dp[i][j] = max(dp[i - 1][j], dp[i - 1][j + (1 << (i - 1))]);
          }
     }
     man(1, 0);
     cout << ANS;
     return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 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 384 KB Output is correct
13 Incorrect 855 ms 412 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 384 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 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 110 ms 436 KB Output is correct
15 Correct 103 ms 384 KB Output is correct
16 Correct 38 ms 384 KB Output is correct
17 Correct 39 ms 512 KB Output is correct
18 Correct 102 ms 384 KB Output is correct
19 Correct 46 ms 504 KB Output is correct
20 Correct 2 ms 384 KB Output is correct

Subtask #3
0 / 21.0

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

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 855 ms 1016 KB Output is correct
2 Correct 10 ms 3456 KB Output is correct
3 Correct 855 ms 3464 KB Output is correct
4 Incorrect 855 ms 3456 KB Output isn't correct
5 Halted 0 ms 0 KB -