Submission #39025

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
39025	2018-01-09T05:43:22 Z	RockyB	UFO (IZhO14_ufo)	C++14	0 / 100	2000 ms	46712 KB

ufo

/// In The Name Of God

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)1e5 + 7, inf = (int)1e9 + 7, mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int n, k;
int a[N];
int dp[111][N];

/*int get_min(int o, int l, int r) {
	int res = dp[o][l];
	for (int i = l + 1; i <= r; i++) {
		res = min(res, dp[o][i]);
	}
	return res;
}*/

int t[N << 1];
void build(int o) {
	for (int i = 0; i <= n; i++) {
		t[i + n] = dp[o][i];
	}
	for (int i = n - 1; i >= 0; i--) {
		t[i] = min(t[i << 1], t[i << 1 | 1]);
	}
}
int get_min(int x, int l, int r) {
	int res = inf;
	for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
		if (l & 1) res = min(res, t[l++]);
		if (r & 1) res = min(res, t[--r]);
	}
	return res;
}
int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
	#endif
	Kazakhstan

	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	
	memset(dp, 0x3f3f, sizeof(dp));
	dp[0][0] = 0;
	a[0] = inf;
	for (int o = 1; o <= k; o++) {
		vector <int> c;
		multiset <int> st;
		c.pb(0);
		build(o - 1);
		for (int i = 1; i <= n; i++) {
			while (sz(c) && a[i] >= a[c.back()]) {
				int j = sz(c) - 1;
				st.erase(st.find(get_min(o - 1, c[j - 1], c[j] - 1) + a[c[j]]));
				c.pp();
			}
			c.pb(i);
			{
				int j = sz(c) - 1;
				st.insert(get_min(o - 1, c[j - 1], c[j] - 1) + a[c[j]]);
			}
			/*for (int j = 1; j < sz(c); j++) {
				dp[o][i] = min(dp[o][i], get_min(o - 1, c[j - 1], c[j] - 1) + a[c[j]]);
			}*/
			dp[o][i] = *st.begin();
		}
	}
	cout << dp[k][n];
	ioi
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	6 ms	46712 KB	Output isn't correct
2	Incorrect	3 ms	46712 KB	Output isn't correct
3	Incorrect	9 ms	46712 KB	Output isn't correct
4	Incorrect	0 ms	46712 KB	Output isn't correct
5	Runtime error	3 ms	46712 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	9 ms	46712 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	6 ms	46712 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Execution timed out	2000 ms	46712 KB	Execution timed out
9	Execution timed out	2000 ms	46712 KB	Execution timed out
10	Execution timed out	2000 ms	46712 KB	Execution timed out
11	Execution timed out	2000 ms	46712 KB	Execution timed out
12	Execution timed out	2000 ms	46712 KB	Execution timed out
13	Incorrect	156 ms	46712 KB	Output isn't correct
14	Execution timed out	2000 ms	46712 KB	Execution timed out
15	Execution timed out	2000 ms	46712 KB	Execution timed out
16	Execution timed out	2000 ms	46712 KB	Execution timed out
17	Incorrect	183 ms	46712 KB	Output isn't correct
18	Incorrect	16 ms	46712 KB	Output isn't correct
19	Runtime error	13 ms	46712 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	0 ms	46712 KB	Execution killed with signal 11 (could be triggered by violating memory limits)