Submission #166394

#	Time	Username	Problem	Language	Result	Execution time	Memory
166394		Trickster	K blocks (IZhO14_blocks)	C++14	0 / 100	3 ms	504 KiB

blocks

//Suleyman Atayew

#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>

#define N 100010
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define inf 1000000007
#define pii pair <int, int>

using namespace std;

int n, k;
int v[N];
//int MX[N];
//int T[N*4];
//int L[N*4];
int dp[110][N];

//void init(int l, int r, int node)
//{
//	L[node] = 0;
//	T[node] = 1e9;
//	
//	if(l == r) return;
//	
//	init(l, (l+r)/2, node*2);
//	init((l+r)/2+1, r, node*2+1);
//}
//
//void upd2(int x, int y, int l, int r, int node)
//{
//	if(l == r) {
//		T[node] = dp[x][l];
//		return;
//	}
//	
//	if(y <= (l+r)/2)
//		upd2(x, y, l, (l+r)/2, node*2);
//	else
//		upd2(x, y, (l+r)/2+1, r, node*2+1);
//	
//	T[node] = min(T[node*2], T[node*2+1]);
//	
//	if(T[node*2] < T[node*2+1]) L[node] = L[node*2];
//	else L[node] = L[node*2+1];
//}
//shift(int node, int to)
//{
//	T[to] -= L[to];
//	T[to] += L[node];
//	L[to] = L[node];
//}
//void upd(int a, int b, int x, int l, int r, int node)
//{
//	if(l > b || r < a) return;
//	
//	if(l >= a && r <= b) {
//		if(l == r) {
//			T[node] -= L[node];
//			T[node] += x;
//			L[node] = x;
//			return;
//		}
//		
//		L[node] = x;
//		
//		shift(node, node*2);
//		shift(node, node*2+1);
//		
//		T[node] = min(T[node*2], T[node*2+1]);
//		
//		if(T[node*2] < T[node*2+1]) L[node] = L[node*2];
//		else L[node] = L[node*2+1];
//		
//		return;
//	}
//	
//	shift(node, node*2);
//	shift(node, node*2+1);
//	L[node] = 0;
//	
//	upd(a, b, x, l, (l+r)/2, node*2);
//	upd(a, b, x, (l+r)/2+1, r, node*2+1);
//	
//	T[node] = min(T[node*2], T[node*2+1]);
//	
//	if(T[node*2] < T[node*2+1]) L[node] = L[node*2];
//	else L[node] = L[node*2+1];
//}

int main()
{
	scanf("%d%d", &n, &k);
	
	for(int i = 1; i <= n; i++)
		scanf("%d", &v[i]);
	
//	vector <int> E;
//	for(int i = 1; i <= n; i++) {
//		while(!E.empty() && v[E.back()] < v[i])
//			E.pop_back();
//		
//		if(E.empty()) MX[i] = 0;
//		else {
//			if(v[E.back()] == v[i]) MX[i] = MX[E.back()];
//			else MX[i] = E.back()+1;
//		}
//		
//		E.pb(i);
//	}
	
//	for(int i = 1; i <= n; i++) dp[0][i] = 1e9;
//	
//	for(int i = 1; i <= k; i++) {
//		init(0, n, 1);
//		
//		for(int h = 0; h <= n; h++) {
//			if(h < i) {
//				dp[i][h] = 1e9;
//				
//				upd2(i-1, h, 0, n, 1);
//				
//				continue;
//			}
//			
//			upd(MX[h], h-1, v[h], 0, n, 1);
//			
//			dp[i][h] = T[1];
//			
//			upd2(i-1, h, 0, n, 1);
//		}
//	}
	
	cout << dp[k][n] << "\n";
}

Compilation message (stderr)

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

• Subtask 1: 0 / 14
• Subtask 2: 0 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47