Submission #875472

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
875472	2023-11-19T19:58:10 Z	auslander	K blocks (IZhO14_blocks)	C++17	53 / 100	1000 ms	80588 KB

blocks

#include <iostream>
#include <algorithm>
#include <math.h>
#include <sstream>
#include <string>
#include <iomanip>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <vector>
#include <iterator>
using namespace std;

//defines
#define ll long long
#define usg unsigned
#define kap map
#define print(x, n) for(int for_loop = 0; for_loop < n; for_loop++){cout<<x[for_loop]<<' ';}cout<<endl; 
#define read(x, n) for(int for_loop = 0; for_loop < n; for_loop++){cin>>x[for_loop];} 
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ratdig(x) cout << fixed << setprecision(x);
#define xfixdig(x) cout << setprecision(x);
#define multi int t; cin>>t; presolve(); while(t--) solve()
#define single presolve(); solve(); return 0
#define rev(x) reverse(x.begin(), x.end())
#define all(x) x.begin(), x.end()

//functions
void yn(bool b)
{
	if (b)
	{
		cout << "YES\n";
		return;
	}
	cout << "NO\n";
}

ll gcd(ll a, ll b) {
	if (a == 0)
		return b;
	if (b == 0)
		return a;
	return gcd(b % a, a);
}

ll lcm(ll a, ll b)
{
	return (a * b) / gcd(a, b);
}

string to2(ll a)
{
	string r = "";
	for (ll i = a; i > 0; )
	{
		ll k = i % 2;
		i /= 2;
		char c = k + 48;
		r += c;
	}
	if (a == 0)
	{
		r = "0";
	}
	rev(r);

	return r;
}

ll binpow(ll a, ll b, ll mod = -1)
{
	ll ans = 1;
	while (b)
	{
		if ((b & 1) == 1)
		{
			ans *= a;
			if (mod != -1)
				ans %= mod;
		}
		b >>= 1;
		a *= a;
		if (mod != -1)
			a %= mod;
	}
	return ans;
}

//body

void presolve()
{

}

const int N = 100005;
const int K = 105;

ll arr[N];
ll dp[K][N];
void solve()
{
	ll i, j, k, m, n;
	cin >> n >> m;
	for (i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	k = arr[0];
	dp[0][0] = k;
	for (i = 1; i < n; i++)
	{
		k = max(k, arr[i]);
		dp[0][i] = k;
		//cout << k << ' ';
	}
	ll w = 0;
	//cout << endl;
	for (i = 1; i < m; i++)
	{
		for (j = i; j < n; j++)
		{
			dp[i][j] = 1000000000000000;
			w = arr[j];
			for (k = j - 1; k >= i - 1; k--)
			{
				dp[i][j] = min(dp[i][j], w + dp[i - 1][k]);
				w = max(w, arr[k]);
			}
			/*cout << dp[i][j] << ' ';*/
		}
		/*cout << endl;*/
	}

	cout << dp[m - 1][n - 1] << endl;
}

int main()
{
	speed;
	single;
	multi;

	return 0;
}

Subtask #1
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2392 KB	Output is correct
2	Correct	0 ms	2392 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	0 ms	2396 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	6492 KB	Output is correct
11	Correct	1 ms	6492 KB	Output is correct
12	Correct	1 ms	2392 KB	Output is correct
13	Correct	1 ms	6492 KB	Output is correct
14	Correct	1 ms	6492 KB	Output is correct
15	Correct	0 ms	2396 KB	Output is correct
16	Correct	1 ms	4444 KB	Output is correct
17	Correct	0 ms	2396 KB	Output is correct
18	Correct	1 ms	6492 KB	Output is correct

Subtask #2
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	1 ms	2392 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	6492 KB	Output is correct
11	Correct	1 ms	6492 KB	Output is correct
12	Correct	1 ms	6492 KB	Output is correct
13	Correct	1 ms	8656 KB	Output is correct
14	Correct	2 ms	10588 KB	Output is correct
15	Correct	1 ms	10584 KB	Output is correct
16	Correct	2 ms	14684 KB	Output is correct
17	Correct	2 ms	14684 KB	Output is correct
18	Correct	1 ms	10588 KB	Output is correct
19	Correct	2 ms	14680 KB	Output is correct
20	Correct	2 ms	16728 KB	Output is correct

Subtask #3
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2392 KB	Output is correct
2	Correct	0 ms	2392 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	0 ms	2396 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	6492 KB	Output is correct
11	Correct	1 ms	6492 KB	Output is correct
12	Correct	1 ms	2392 KB	Output is correct
13	Correct	1 ms	6492 KB	Output is correct
14	Correct	1 ms	6492 KB	Output is correct
15	Correct	0 ms	2396 KB	Output is correct
16	Correct	1 ms	4444 KB	Output is correct
17	Correct	0 ms	2396 KB	Output is correct
18	Correct	1 ms	6492 KB	Output is correct
19	Correct	0 ms	2396 KB	Output is correct
20	Correct	0 ms	2396 KB	Output is correct
21	Correct	1 ms	2392 KB	Output is correct
22	Correct	1 ms	4444 KB	Output is correct
23	Correct	1 ms	4444 KB	Output is correct
24	Correct	1 ms	2396 KB	Output is correct
25	Correct	1 ms	4444 KB	Output is correct
26	Correct	1 ms	4444 KB	Output is correct
27	Correct	1 ms	4444 KB	Output is correct
28	Correct	1 ms	6492 KB	Output is correct
29	Correct	1 ms	6492 KB	Output is correct
30	Correct	1 ms	6492 KB	Output is correct
31	Correct	1 ms	8656 KB	Output is correct
32	Correct	2 ms	10588 KB	Output is correct
33	Correct	1 ms	10584 KB	Output is correct
34	Correct	2 ms	14684 KB	Output is correct
35	Correct	2 ms	14684 KB	Output is correct
36	Correct	1 ms	10588 KB	Output is correct
37	Correct	2 ms	14680 KB	Output is correct
38	Correct	2 ms	16728 KB	Output is correct
39	Correct	15 ms	41308 KB	Output is correct
40	Correct	1 ms	2396 KB	Output is correct
41	Correct	1 ms	2396 KB	Output is correct
42	Correct	1 ms	2396 KB	Output is correct
43	Correct	1 ms	4444 KB	Output is correct
44	Correct	1 ms	4564 KB	Output is correct
45	Correct	0 ms	2512 KB	Output is correct
46	Correct	1 ms	4572 KB	Output is correct
47	Correct	1 ms	4444 KB	Output is correct
48	Correct	1 ms	4444 KB	Output is correct
49	Correct	1 ms	6492 KB	Output is correct
50	Correct	1 ms	6612 KB	Output is correct
51	Correct	3 ms	22872 KB	Output is correct
52	Correct	3 ms	22876 KB	Output is correct
53	Correct	13 ms	80588 KB	Output is correct
54	Correct	8 ms	80476 KB	Output is correct
55	Correct	5 ms	43356 KB	Output is correct
56	Correct	8 ms	80432 KB	Output is correct
57	Correct	10 ms	80472 KB	Output is correct

Subtask #4
0 / 47.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2392 KB	Output is correct
2	Correct	0 ms	2392 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	0 ms	2396 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	6492 KB	Output is correct
11	Correct	1 ms	6492 KB	Output is correct
12	Correct	1 ms	2392 KB	Output is correct
13	Correct	1 ms	6492 KB	Output is correct
14	Correct	1 ms	6492 KB	Output is correct
15	Correct	0 ms	2396 KB	Output is correct
16	Correct	1 ms	4444 KB	Output is correct
17	Correct	0 ms	2396 KB	Output is correct
18	Correct	1 ms	6492 KB	Output is correct
19	Correct	0 ms	2396 KB	Output is correct
20	Correct	0 ms	2396 KB	Output is correct
21	Correct	1 ms	2392 KB	Output is correct
22	Correct	1 ms	4444 KB	Output is correct
23	Correct	1 ms	4444 KB	Output is correct
24	Correct	1 ms	2396 KB	Output is correct
25	Correct	1 ms	4444 KB	Output is correct
26	Correct	1 ms	4444 KB	Output is correct
27	Correct	1 ms	4444 KB	Output is correct
28	Correct	1 ms	6492 KB	Output is correct
29	Correct	1 ms	6492 KB	Output is correct
30	Correct	1 ms	6492 KB	Output is correct
31	Correct	1 ms	8656 KB	Output is correct
32	Correct	2 ms	10588 KB	Output is correct
33	Correct	1 ms	10584 KB	Output is correct
34	Correct	2 ms	14684 KB	Output is correct
35	Correct	2 ms	14684 KB	Output is correct
36	Correct	1 ms	10588 KB	Output is correct
37	Correct	2 ms	14680 KB	Output is correct
38	Correct	2 ms	16728 KB	Output is correct
39	Correct	15 ms	41308 KB	Output is correct
40	Correct	1 ms	2396 KB	Output is correct
41	Correct	1 ms	2396 KB	Output is correct
42	Correct	1 ms	2396 KB	Output is correct
43	Correct	1 ms	4444 KB	Output is correct
44	Correct	1 ms	4564 KB	Output is correct
45	Correct	0 ms	2512 KB	Output is correct
46	Correct	1 ms	4572 KB	Output is correct
47	Correct	1 ms	4444 KB	Output is correct
48	Correct	1 ms	4444 KB	Output is correct
49	Correct	1 ms	6492 KB	Output is correct
50	Correct	1 ms	6612 KB	Output is correct
51	Correct	3 ms	22872 KB	Output is correct
52	Correct	3 ms	22876 KB	Output is correct
53	Correct	13 ms	80588 KB	Output is correct
54	Correct	8 ms	80476 KB	Output is correct
55	Correct	5 ms	43356 KB	Output is correct
56	Correct	8 ms	80432 KB	Output is correct
57	Correct	10 ms	80472 KB	Output is correct
58	Execution timed out	1026 ms	17020 KB	Time limit exceeded
59	Halted	0 ms	0 KB	-

Submission #875472

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 18.0 / 18.0

Subtask #3 21.0 / 21.0

Subtask #4 0 / 47.0

Subtask #1
14.0 / 14.0

Subtask #2
18.0 / 18.0

Subtask #3
21.0 / 21.0

Subtask #4
0 / 47.0