oj.uz

Submission #522044

# Submission time Handle Problem Language Result Execution time Memory
522044 2022-02-03T16:17:45 Z MateGiorbelidze K blocks (IZhO14_blocks) C++14
0 / 100
 6 ms 8144 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define pll pair<ll,ll>
#define sc second
#define vc vector

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

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

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

pll find_max (ll v, ll tl, ll tr, ll l, ll r) {
	
	if (l > r) return {0 , 0};
	
	if (tl == l && tr == r) {
		
		return t[v] ;
		
	}
	
	ll m = (tl + tr) / 2;
		
	pll x = find_max (2 * v, tl , m , l , min (m , r)) ;
	
	pll y = find_max (2 * v + 1, m + 1 , tr , max(l , m + 1) , r) ;
	
	if ( x.ff > y.ff ) {
			
		return x;
		
	}
	else 				{
		
		return 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 = n; i >= 1; i--) {
		
		if (a[i] == mx) {
			
			d[i] = 1;
			
			break;
			
		}
		
	}
	
	
	for (int o = 2; o <= k; o++) {
		
		for (int i = 1; i <= n; i++) 
			if (d[i] == 1) r = i;
		
		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 - 2 && o > 2) {
				
				while (d[i] != 1) {
					
					pll x = find_max(1 , 1 , n , l , i) , y = find_max(1 , 1 , n , i + 1 , r);
					
					if (x.ff + y.ff < mn + a[r]) {
						
						d[r] = 0; d[y.sc] = 1;
						
						r = y.sc;
						
						ans = x.sc; mn = x.ff;
						
					}
					
					i++;
					
				}
				
			}
			
			else if (cnt != o - 1) {
			
				while (d[i] != 1) {
					
					pll x = find_max(1 , 1 , n , l , i);
					
					if (x.ff < mn) {
						
						ans = x.sc; mn = x.ff;
						
					}
					
					i++;
					
				}
			
			}
			else {
				
				while (i <= n) {
					
					pll x = find_max(1 , 1 , n , i , n);
					
					if (x.ff < mn) {
						
						ans = x.sc; mn = x.ff;
						
					}
					
					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 4 ms 8012 KB Output is correct
2 Correct 4 ms 8132 KB Output is correct
3 Correct 6 ms 8140 KB Output is correct
4 Correct 4 ms 8140 KB Output is correct
5 Correct 3 ms 8088 KB Output is correct
6 Correct 5 ms 8140 KB Output is correct
7 Correct 4 ms 8076 KB Output is correct
8 Correct 4 ms 8140 KB Output is correct
9 Correct 4 ms 8144 KB Output is correct
10 Correct 5 ms 8084 KB Output is correct
11 Correct 4 ms 8140 KB Output is correct
12 Correct 5 ms 8012 KB Output is correct
13 Incorrect 4 ms 8140 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8136 KB Output is correct
2 Correct 6 ms 8024 KB Output is correct
3 Correct 4 ms 8140 KB Output is correct
4 Correct 6 ms 8108 KB Output is correct
5 Correct 4 ms 8136 KB Output is correct
6 Correct 4 ms 8140 KB Output is correct
7 Correct 4 ms 8012 KB Output is correct
8 Correct 4 ms 8144 KB Output is correct
9 Correct 4 ms 8136 KB Output is correct
10 Correct 4 ms 8140 KB Output is correct
11 Correct 6 ms 8012 KB Output is correct
12 Incorrect 4 ms 8140 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8012 KB Output is correct
2 Correct 4 ms 8132 KB Output is correct
3 Correct 6 ms 8140 KB Output is correct
4 Correct 4 ms 8140 KB Output is correct
5 Correct 3 ms 8088 KB Output is correct
6 Correct 5 ms 8140 KB Output is correct
7 Correct 4 ms 8076 KB Output is correct
8 Correct 4 ms 8140 KB Output is correct
9 Correct 4 ms 8144 KB Output is correct
10 Correct 5 ms 8084 KB Output is correct
11 Correct 4 ms 8140 KB Output is correct
12 Correct 5 ms 8012 KB Output is correct
13 Incorrect 4 ms 8140 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8012 KB Output is correct
2 Correct 4 ms 8132 KB Output is correct
3 Correct 6 ms 8140 KB Output is correct
4 Correct 4 ms 8140 KB Output is correct
5 Correct 3 ms 8088 KB Output is correct
6 Correct 5 ms 8140 KB Output is correct
7 Correct 4 ms 8076 KB Output is correct
8 Correct 4 ms 8140 KB Output is correct
9 Correct 4 ms 8144 KB Output is correct
10 Correct 5 ms 8084 KB Output is correct
11 Correct 4 ms 8140 KB Output is correct
12 Correct 5 ms 8012 KB Output is correct
13 Incorrect 4 ms 8140 KB Output isn't correct
14 Halted 0 ms 0 KB -