oj.uz

Submission #875909

# Submission time Handle Problem Language Result Execution time Memory
875909 2023-11-20T18:01:38 Z auslander K blocks (IZhO14_blocks) C++17
0 / 100
 1 ms 8540 KB 
#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], sum[N], mx[N];
pair<ll, ll> dp[K][N];//dp, max
void solve()
{
	ll i, j, k, m, n;
	cin >> n >> m;
	k = 0;
	for (i = 0; i < n; i++)
	{
		cin >> arr[i];
		k += arr[i];
		sum[i] = k;
	}
	dp[0][0] = { arr[0], arr[0]};
	for (i = 1; i < n; i++)
	{
		k = max(arr[i], dp[0][i - 1].first);
		dp[0][i] = { k, k };
	}
	ll w;
	for (i = 1; i < m; i++)
	{
		dp[i][i] = { sum[i],  arr[i]};
		for (j = i + 1; j < n; j++)
		{
			//arandzin axb
			dp[i][j] = { dp[i - 1][j - 1].first + arr[j], arr[j] };
			
			//kpcnel naxordin
			if (dp[i][j - 1].second >= arr[j])
			{
				k = dp[i][j - 1].first;
				w = dp[i][j - 1].second;
			}
			else
			{
				k = dp[i][j - 1].first + arr[j] - dp[i][j - 1].second;
				w = arr[j];
			}
			if (k < dp[i][j].first)
			{
				dp[i][j] = { k, w };
			}
			else if (k == dp[i][j].first)
			{
				if (dp[i][j].second < w)
				{
					dp[i][j] = { k, w };
				}
			}
		}
	}
	cout << dp[m - 1][n - 1].first;
}

int main()
{
	speed;
	single;
	multi;

	return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2648 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 4440 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Incorrect 1 ms 8540 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2512 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 6492 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Incorrect 1 ms 8540 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2648 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 4440 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Incorrect 1 ms 8540 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2648 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 4440 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Incorrect 1 ms 8540 KB Output isn't correct
12 Halted 0 ms 0 KB -