oj.uz

Submission #93127

# Submission time Handle Problem Language Result Execution time Memory
93127 2019-01-06T14:47:20 Z Nodir_Bobiev K blocks (IZhO14_blocks) C++14
0 / 100
 6 ms 888 KB 
# include <iostream>
# include <set>

using namespace std;
	
const int N = 1e5 + 100;

set < pair < int, int > > blocks[111];
int n, k;
int a[N];
int l[111], r[111];
long long ans;

int getMax(int i)
{
	return  -(blocks[i].begin() -> first);
}

int PgetMax(int i)
{
	auto it = blocks[i].begin();
	it++;
	return - (it -> first);
}

int main()
{
	cin >> n >> k;
	
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	
	for (int i = 1; i <= k; i++){
		blocks[i].insert({-a[i], i});
		l[i] = i;
		r[i] = i;
	}
	for (int i = k + 1; i <= n; i++){
		r[k]++;
		blocks[k].insert({-a[i], i});
		for (int j = k - 1; j >= 1; j--){
			if(r[j + 1] == l[j + 1])
				continue;
			
			if(a[l[j + 1]] <= getMax(j) || a[l[j + 1]] == getMax(j + 1)){
				blocks[j + 1].erase({-a[l[j + 1]], l[j + 1]});
				blocks[j].insert({-a[l[j + 1]], l[j + 1]});
				l[j + 1]++;
				r[j]++;
			}
		}
	}
	for (int i = 1; i <= k; i++){
		ans += getMax(i);
	}
	cout << ans;
}

/*

5 2
5 4 3 1 2

5 2
4 3 5 2 1

*/

Subtask #1
0 / 14.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 47.0

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