oj.uz

Submission #47322

# Submission time Handle Problem Language Result Execution time Memory
47322 2018-04-30T17:43:21 Z rkocharyan K blocks (IZhO14_blocks) C++14
100 / 100
 150 ms 49824 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 36600 KB Output is correct
2 Correct 28 ms 36600 KB Output is correct
3 Correct 29 ms 36640 KB Output is correct
4 Correct 29 ms 36780 KB Output is correct
5 Correct 30 ms 36876 KB Output is correct
6 Correct 30 ms 36876 KB Output is correct
7 Correct 28 ms 36944 KB Output is correct
8 Correct 30 ms 37092 KB Output is correct
9 Correct 33 ms 37092 KB Output is correct
10 Correct 29 ms 37092 KB Output is correct
11 Correct 29 ms 37092 KB Output is correct
12 Correct 32 ms 37092 KB Output is correct
13 Correct 29 ms 37092 KB Output is correct
14 Correct 28 ms 37092 KB Output is correct
15 Correct 29 ms 37092 KB Output is correct
16 Correct 29 ms 37092 KB Output is correct
17 Correct 28 ms 37092 KB Output is correct
18 Correct 29 ms 37092 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 37092 KB Output is correct
2 Correct 29 ms 37092 KB Output is correct
3 Correct 30 ms 37092 KB Output is correct
4 Correct 30 ms 37092 KB Output is correct
5 Correct 30 ms 37092 KB Output is correct
6 Correct 30 ms 37092 KB Output is correct
7 Correct 29 ms 37092 KB Output is correct
8 Correct 29 ms 37092 KB Output is correct
9 Correct 29 ms 37092 KB Output is correct
10 Correct 28 ms 37092 KB Output is correct
11 Correct 29 ms 37092 KB Output is correct
12 Correct 29 ms 37092 KB Output is correct
13 Correct 28 ms 37092 KB Output is correct
14 Correct 29 ms 37092 KB Output is correct
15 Correct 30 ms 37092 KB Output is correct
16 Correct 29 ms 37092 KB Output is correct
17 Correct 29 ms 37096 KB Output is correct
18 Correct 29 ms 37096 KB Output is correct
19 Correct 30 ms 37104 KB Output is correct
20 Correct 35 ms 37108 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 37108 KB Output is correct
2 Correct 29 ms 37116 KB Output is correct
3 Correct 29 ms 37204 KB Output is correct
4 Correct 29 ms 37204 KB Output is correct
5 Correct 30 ms 37204 KB Output is correct
6 Correct 33 ms 37204 KB Output is correct
7 Correct 36 ms 37204 KB Output is correct
8 Correct 29 ms 37204 KB Output is correct
9 Correct 51 ms 37204 KB Output is correct
10 Correct 31 ms 37204 KB Output is correct
11 Correct 30 ms 37204 KB Output is correct
12 Correct 28 ms 37204 KB Output is correct
13 Correct 30 ms 37204 KB Output is correct
14 Correct 29 ms 37204 KB Output is correct
15 Correct 28 ms 37204 KB Output is correct
16 Correct 29 ms 37204 KB Output is correct
17 Correct 28 ms 37204 KB Output is correct
18 Correct 29 ms 37308 KB Output is correct
19 Correct 31 ms 37308 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 37320 KB Output is correct
2 Correct 34 ms 37904 KB Output is correct
3 Correct 38 ms 38280 KB Output is correct
4 Correct 65 ms 38572 KB Output is correct
5 Correct 124 ms 39720 KB Output is correct
6 Correct 45 ms 40316 KB Output is correct
7 Correct 80 ms 40992 KB Output is correct
8 Correct 29 ms 40992 KB Output is correct
9 Correct 44 ms 40992 KB Output is correct
10 Correct 29 ms 40992 KB Output is correct
11 Correct 29 ms 40992 KB Output is correct
12 Correct 30 ms 40992 KB Output is correct
13 Correct 31 ms 40992 KB Output is correct
14 Correct 48 ms 40992 KB Output is correct
15 Correct 30 ms 40992 KB Output is correct
16 Correct 32 ms 40992 KB Output is correct
17 Correct 35 ms 41168 KB Output is correct
18 Correct 37 ms 41472 KB Output is correct
19 Correct 61 ms 41768 KB Output is correct
20 Correct 110 ms 42856 KB Output is correct
21 Correct 43 ms 43564 KB Output is correct
22 Correct 75 ms 44212 KB Output is correct
23 Correct 42 ms 44864 KB Output is correct
24 Correct 48 ms 45548 KB Output is correct
25 Correct 122 ms 46384 KB Output is correct
26 Correct 30 ms 46384 KB Output is correct
27 Correct 35 ms 46384 KB Output is correct
28 Correct 49 ms 46384 KB Output is correct
29 Correct 30 ms 46384 KB Output is correct
30 Correct 33 ms 46384 KB Output is correct
31 Correct 35 ms 46412 KB Output is correct
32 Correct 38 ms 46816 KB Output is correct
33 Correct 72 ms 47248 KB Output is correct
34 Correct 150 ms 48400 KB Output is correct
35 Correct 43 ms 49132 KB Output is correct
36 Correct 89 ms 49824 KB Output is correct
37 Correct 30 ms 49824 KB Output is correct
38 Correct 44 ms 49824 KB Output is correct
39 Correct 30 ms 49824 KB Output is correct
40 Correct 29 ms 49824 KB Output is correct
41 Correct 37 ms 49824 KB Output is correct
42 Correct 28 ms 49824 KB Output is correct