Submission #47322

#	Time	Username	Problem	Language	Result	Execution time	Memory
47322		rkocharyan	K blocks (IZhO14_blocks)	C++14	100 / 100	150 ms	49824 KiB

blocks

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <map>
#include <unordered_map>
#include <stack>
#include <cstring>
#include <string>
#include <set>
#include <unordered_set>
#include <bitset>
#include <limits>
#include <climits>
#include <queue>
#include <deque>
#include <list>
#include <forward_list>
#include <sstream>
#include <complex>
#include <iterator>
#include <functional>
#include <tuple>
#include <array> 
#include <locale>
#include <memory>
#include <cstdio>
#define fin(x) freopen("input.txt", "r", stdin);
#define fout(x) freopen("output.txt", "w", stdout);
#define speedup ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define cp(x) cout.setf(ios::fixed); cout.precision(x);
#define loop(x, n) for(int i = x; i <= n; ++i)
#define FOR(x, n, y) for(int i = x; i <= n; i += y)
#define FORN(x, n, y) for(int y = x; y <= n; ++y)
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define mem(a,b) memset(a, b, sizeof(a))
#define mcp(a,b,x) memcpy(a, b, sizeof(x))
#define wh(t) while(true)
#define sp system("pause")
#define ST(N) srand(time(NULL))
#define SQ(x) (x)*(x)
#define ppc(x) __popcnt(x)
#define lb lower_bound
#define ub upper_bound
#define tp toupper
#define tl tolower
#define ad push_back
#define em emplace
#define eh empalce_hint
#define mp make_pair
#define nxp next_permutation
#define fr first
#define sc second
#define cl clear
#define vc vector
#define pq priority_queue
#define bs bitset
#define li list<int>
#define vi vector<int>
#define si set<int>
#define vii vector<vector<int> >
#define sti stack<int>
#define dqi deque<int>
#define pqi priority_queue<int>
#define pii pair<int, int>
#define mii map<int, int>
#define bs32 bitset<32>
//#define DEBUG
//#define TEST 1
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
typedef long long ll;
typedef long double ld;
typedef double dbl;
typedef unsigned long long ull;
using namespace std;

const int N = 1000 * 1000 + 100;
const ll MOD = 1e9 + 7;
const ll INC = INT_MAX;
const ll INF = LLONG_MAX;
const ull EPS = ULLONG_MAX;
long long minim = INF;
long long maxim = -INF;

long long cnt = 0, ans = 0;
vector<int> dp(N);
bool u = false, U[N];
int a[N], b[N], c[N];
int A[N / 1000][N / 1000];
string s, t;

vector<int> G[N];
vector<int> parent(N), D(N);
vector<char> color(N, false);

void bfs(int s) {
	queue<int> q;
	color[s] = true;
	q.push(s);
	while (!q.empty()) {
		s = q.front(); q.pop();
		for (int i = 0; i < G[s].size(); ++i) {
			if (G[s][i] > 0 && !color[G[s][i]]) {
				color[G[s][i]] = true;
				q.push(G[s][i]);
			}
		}
	}
}

void dfs(int v) {
	color[v] = true;
	for (int i = 0; i < G[v].size(); ++i) {
		if (G[v][i] > 0 && !color[G[v][i]]) {
			color[G[v][i]] = true;
			dfs(G[v][i]);
		}
	}
}

void dfs(int v, int p)
{
	D[v] = D[p] + 1;
	for (auto to : G[v]) {
		if (to != p) dfs(to, v);
	}
}

void make_set(int v) {
	parent[v] = v;
}

int find_set(int v) {
	if (v == parent[v])	return v;
	return parent[v] = find_set(parent[v]);
}

int pre[N]; pii p[N];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	//#define USACO
#ifdef USACO
#ifndef _MSC_VER 
#define TASK ""
	freopen(TASK".in", "r", stdin);
	freopen(TASK".out", "w", stdout);
#endif
#endif 
	
	int n, k; cin >> n >> k;

	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		pre[i] = max(pre[i - 1], a[i]);
	}
	int cnt = 0;

	for (int j = 2; j <= k; ++j) {
		int size = 0;
		for (int i = 1; i <= n; ++i) {
			if (j <= i) cnt = pre[i - 1];
			else cnt = 1000 * 1000 * 1000;
			pre[i - 1] = dp[i - 1];
			for (; size != 0 && a[i] >= p[size - 1].first;) {
				--size;
				cnt = min(cnt, p[size].second);
			}
			if (!size || cnt + a[i] <p[size - 1].first + p[size - 1].second) {
				p[size] = mp(a[i], cnt);
				++size;
			}
			dp[i] = p[size - 1].fr + p[size - 1].sc;
		}
		pre[n] = dp[n];
	}

	cout << pre[n] << endl;

	return 0;
}

Compilation message (stderr)

blocks.cpp:76:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable:4996)
 
blocks.cpp:77:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK:336777216")
 
blocks.cpp: In function 'void bfs(int)':
blocks.cpp:109:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < G[s].size(); ++i) {
                   ~~^~~~~~~~~~~~~
blocks.cpp: In function 'void dfs(int)':
blocks.cpp:120:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G[v].size(); ++i) {
                  ~~^~~~~~~~~~~~~

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