oj.uz

Submission #114566

# Submission time Handle Problem Language Result Execution time Memory
114566 2019-06-01T19:25:55 Z ioilolcom K blocks (IZhO14_blocks) C++14
53 / 100
 1000 ms 158592 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long int ll;
const int N=1e5+7;
const int K=200;
int a[N];
int n;
const int m=20;
ll dp[N][K];
int st[N][m];
int v;
int query(int L,int R){
	int j = log2(R - L + 1);
	int ans = max(st[L][j], st[R - (1 << j)+1][j]);
	//cout<<L<<" "<<R<<" "<<j<<endl;
	return ans;
}
/*
   int query(int l,int r){
        int ans=0;
        for(int i=l; i<=r; i++) {
                ans=max(ans,a[i]);
        }
        return ans;
   }
 */
int  solve(int idx,int k){

	if(idx==n+1) {
		if(k==v+1) {
			return 0;
		}
		return 1e9;
	}
	if(dp[idx][k]!=-1) {
		return dp[idx][k];
	}
	int ans=1e9;
	for(int j=idx; j<=n; j++) {
		ans=min(ans,query(idx,j)+solve(j+1,k+1));
	}
	return dp[idx][k]=ans;
}
int main()
{

	ios_base:: sync_with_stdio(false); cin.tie(0);
	cin>>n>>v;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		st[i][0]=a[i];
	}
	for (int j = 1; j < m; j++) {
		for (int i = 1; i + (1 << j) <=n+1; i++) {
			st[i][j] = max(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
		}
	}
/*
        for (int j = 1; j < m; j++) {
                for (int i = 1; i + (1 << j) <=n; i++) {
                        cout<<" starting at i "<<i<<" of length 2^"<<j<<" "<<st[i][j]<<endl;
                }
        }
 */
	//cout<<st[4][1]<<endl;
	memset(dp,-1,sizeof dp);
	ll ans=solve(1,1);

	cout<<ans<<endl;
	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 157020 KB Output is correct
2 Correct 111 ms 156920 KB Output is correct
3 Correct 115 ms 156956 KB Output is correct
4 Correct 113 ms 156920 KB Output is correct
5 Correct 115 ms 156920 KB Output is correct
6 Correct 113 ms 156892 KB Output is correct
7 Correct 114 ms 156920 KB Output is correct
8 Correct 114 ms 156892 KB Output is correct
9 Correct 115 ms 156892 KB Output is correct
10 Correct 115 ms 156932 KB Output is correct
11 Correct 129 ms 156936 KB Output is correct
12 Correct 119 ms 157048 KB Output is correct
13 Correct 118 ms 156920 KB Output is correct
14 Correct 120 ms 156920 KB Output is correct
15 Correct 115 ms 156904 KB Output is correct
16 Correct 114 ms 156920 KB Output is correct
17 Correct 118 ms 156920 KB Output is correct
18 Correct 126 ms 156920 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 156920 KB Output is correct
2 Correct 119 ms 157016 KB Output is correct
3 Correct 112 ms 156912 KB Output is correct
4 Correct 112 ms 156896 KB Output is correct
5 Correct 112 ms 156920 KB Output is correct
6 Correct 111 ms 156920 KB Output is correct
7 Correct 110 ms 156860 KB Output is correct
8 Correct 111 ms 156892 KB Output is correct
9 Correct 111 ms 156920 KB Output is correct
10 Correct 113 ms 156896 KB Output is correct
11 Correct 111 ms 156892 KB Output is correct
12 Correct 110 ms 156920 KB Output is correct
13 Correct 153 ms 156920 KB Output is correct
14 Correct 112 ms 156920 KB Output is correct
15 Correct 113 ms 156892 KB Output is correct
16 Correct 115 ms 156896 KB Output is correct
17 Correct 116 ms 156920 KB Output is correct
18 Correct 114 ms 156936 KB Output is correct
19 Correct 114 ms 156868 KB Output is correct
20 Correct 114 ms 156920 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 156924 KB Output is correct
2 Correct 116 ms 156832 KB Output is correct
3 Correct 114 ms 156880 KB Output is correct
4 Correct 114 ms 156920 KB Output is correct
5 Correct 115 ms 156920 KB Output is correct
6 Correct 115 ms 156912 KB Output is correct
7 Correct 112 ms 156900 KB Output is correct
8 Correct 114 ms 156940 KB Output is correct
9 Correct 111 ms 156932 KB Output is correct
10 Correct 111 ms 156920 KB Output is correct
11 Correct 113 ms 156920 KB Output is correct
12 Correct 113 ms 156968 KB Output is correct
13 Correct 115 ms 156920 KB Output is correct
14 Correct 115 ms 156920 KB Output is correct
15 Correct 114 ms 156892 KB Output is correct
16 Correct 117 ms 157020 KB Output is correct
17 Correct 119 ms 156932 KB Output is correct
18 Correct 115 ms 156920 KB Output is correct
19 Correct 114 ms 156920 KB Output is correct

Subtask #4
0 / 47.0

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