oj.uz

Submission #362005

# Submission time Handle Problem Language Result Execution time Memory
362005 2021-02-01T14:20:10 Z Lawliet K blocks (IZhO14_blocks) C++17
0 / 100
 1 ms 384 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
typedef long long int lli;

const int MAXK = 110;
const int MAXN = 100010;
const int INF = 1000000010;

int n, k;

int v[MAXN];
int dp[MAXK][MAXN];

vector<int> value;
vector<int> minDp;

void solveTestCase()
{
	scanf("%d %d",&n,&k);

	for(int i = 1 ; i <= n ; i++)
		scanf("%d",&v[i]);

	dp[0][0] = 0;

	for(int i = 1 ; i <= n ; i++)
		dp[0][i] = INF;

	for(int i = 1 ; i <= k ; i++)
	{
		value.clear();
		minDp.clear();

		dp[i][0] = INF;

		for(int j = 1 ; j <= n ; j++)
		{
			int curMn = dp[i - 1][j - 1];

			while( !value.empty() && value.back() <= v[j] )
			{
				curMn = min( curMn , minDp.back() );
				minDp.pop_back(); value.pop_back();
			}

			if( value.empty() || value.back() + minDp.back() > v[j] + curMn )
			{
				value.push_back( v[j] );
				minDp.push_back( curMn );
			}

			if( i > j ) continue;

			dp[i][j] = value.back() + minDp.back();
		}
	}

	printf("%d\n",dp[k][n]);
}

int main()
{
	int t = 1;
	// scanf("%d",&t);

	while( t-- )
		solveTestCase();
}

Compilation message

blocks.cpp: In function 'void solveTestCase()':
blocks.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   21 |  scanf("%d %d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~~
blocks.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |   scanf("%d",&v[i]);
      |   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 47.0

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