oj.uz

Submission #522005

# Submission time Handle Problem Language Result Execution time Memory
522005 2022-02-03T15:13:56 Z MateGiorbelidze K blocks (IZhO14_blocks) C++14
0 / 100
 4 ms 5008 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sc second
#define vc vector

ll n , k , mx , mn = 1000001 , ans;

vc <ll> t(400001) , a(100001) , d(100001);

void build (ll v, ll tl, ll tr) {
	
	if (tl == tr) t[v] = a[tl];
	else {
		
		ll m = (tl + tr) / 2;
		
		build (2 * v, tl , m) ;
		
		build (2 * v + 1, m + 1 , tr) ;
		
		t[v] = max ( t[2 * v] , t[2 * v + 1] );
		
	}
	
}

ll find_max (ll v, ll tl, ll tr, ll l, ll r) {
	
	if (l > r) return 0;
	
	if (tl == l && tr == r) {
		
		return t[v] ;
		
	}
	
	ll m = (tl + tr) / 2;
		
	ll x = find_max (2 * v, tl , m , l , min (m , r)) ;
	
	ll y = find_max (2 * v + 1, m + 1 , tr , max(l , m + 1) , r) ;
	
	return max ( x , y );
	
}

int main () {
	
	cin>>n>>k;
	
	for (int i = 1; i <= n; i++){
		cin>>a[i];
		mx = max (mx , a[i]) ;
	}
		
	build (1 , 1 , n) ;
		
	for (int i = 1; i <= n; i++) {
		
		if (a[i] == mx) {
			
			d[i] = 1;
			
			break;
			
		}
		
	}
	
	
	for (int o = 2; o <= k; o++) {
		
		ans = 0; mn = 1000001 ; ll cnt = 0 , l = 1;
	
		for (int i = 1; i <= n; i++) {
			
			if (d[i] == 1) {
				
				cnt++;
				
				l = i + 1;
				
				continue;
				
			}
			
			if (cnt != o - 1) {
			
				while (d[i] != 1) {
					
					ll x = find_max(1 , 1 , n , l , i);
					
					if (x < mn) {
						
						ans = i; mn = x;
						
					}
					
					i++;
					
				}
			
			}
			else {
				
				while (i <= n) {
					
					ll x = find_max(1 , 1 , n , i , n);
					
					if (x < mn) {
						
						ans = i; mn = x;
						
					}
					
					i++;
					
				}
				
			}
			
			i--;
			
		}
		
		d[ans] = 1;
	
	}
	
	ll s = 0;
	
	for (int i = 1; i <= n; i++) {
		
		if (d[i] == 1) s += a[i];
		
	}
	
	cout<<s;
	
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 2 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 2 ms 5008 KB Output is correct
6 Correct 2 ms 4940 KB Output is correct
7 Incorrect 2 ms 4960 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

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

Subtask #4
0 / 47.0

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