oj.uz

Submission #100812

# Submission time Handle Problem Language Result Execution time Memory
100812 2019-03-14T15:29:17 Z 1Khan K blocks (IZhO14_blocks) C++14
18 / 100
 1000 ms 896 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);
          }
          return;
     }
     for(int i = 1; i <= n; ++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 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 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 Execution timed out 1074 ms 384 KB Time limit exceeded
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 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 2 ms 384 KB Output is correct
8 Correct 2 ms 384 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 76 ms 404 KB Output is correct
15 Correct 89 ms 504 KB Output is correct
16 Correct 109 ms 384 KB Output is correct
17 Correct 132 ms 504 KB Output is correct
18 Correct 81 ms 384 KB Output is correct
19 Correct 103 ms 384 KB Output is correct
20 Correct 110 ms 504 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1065 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 896 KB Time limit exceeded
2 Halted 0 ms 0 KB -