oj.uz

Submission #256691

# Submission time Handle Problem Language Result Execution time Memory
256691 2020-08-03T06:44:14 Z MrRobot_28 Holding (COCI20_holding) C++17
55 / 110
 1484 ms 12608 KB 
#include<bits/stdc++.h>
 
using namespace std;
#define int long long
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, l, r, k;
	cin >> n >> l >> r >> k;
	vector <int> a(n);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	l--;
	r--;
	int sum = 0, ans = 0;
	vector <pair <int, int> > mass1, mass2, mass3;
	for(int i = 0; i < n; i++)
	{
		if(i < l)
		{
			mass1.push_back({a[i], i});
		}
		else if(i <= r){
			sum += a[i];
			ans += a[i];
			mass2.push_back({a[i], i});
		}
		else
		{
			mass3.push_back({a[i], i});
		}
	}
	vector <vector <int> > dp1(n + 1, vector <int> (k + 1, 0));
	vector <vector <int> > dp2(n + 1, vector <int> (k + 1, 0));
	vector <int> dp0(k + 1, 0);
	vector <vector <int> > dpleft(mass2.size(), vector <int> (k + 1, 0));
	vector <vector <int> > dpright(mass2.size(), vector <int> (k + 1, 0));
	for(int i = 0; i < mass2.size(); i++)
	{
		for(int t = 0; t <= k; t++)
		{
			dp0[t] = 0;
		}
		for(int j = 0; j <= mass1.size(); j++)
		{
			for(int t = 0; t <= k; t++)
			{
				dp2[j][t] = dp1[j][t];
			}
		}
		for(int j = 0; j < mass1.size(); j++)
		{
			for(int t = 0; t <= k; t++)
			{
				dp0[t] = min(dp0[t], dp1[j][t]);
			}
			for(int t = 0; t <= k; t++)
			{
				if(t + abs(mass2[i].second - mass1[j].second) > k)
				{
					continue;
				}
				dp2[j + 1][t + abs(mass2[i].second - mass1[j].second)] = 
				min(dp2[j + 1][t + abs(mass2[i].second - mass1[j].second)], dp0[t] + mass1[j].first - mass2[i].first);
			}
		}
		for(int j = 0; j <= mass1.size(); j++)
		{
			for(int t = 0; t <= k; t++)
			{
				dp1[j][t] = dp2[j][t];
				dp2[j][t] = 0;
				dpleft[i][t] = min(dpleft[i][t], dp1[j][t]);
			}
		}
	}
	for(int i = mass2.size() - 1; i >= 0; i--)
	{
		for(int t = 0; t <= k; t++)
		{
			dp0[t] = 0;
		}
		for(int j = 0; j <= mass3.size(); j++)
		{
			for(int t = 0; t <= k; t++)
			{
				dp2[j][t] = dp1[j][t];
			}
		}
		for(int j = mass3.size(); j > 0; j--)
		{
			for(int t = 0; t <= k; t++)
			{
				dp0[t] = min(dp0[t], dp1[j][t]);	
			}
			for(int t = 0; t <= k; t++)
			{
				if(t + abs(mass2[i].second - mass3[j - 1].second) > k)
				{
					continue;
				}
				dp2[j - 1][t + abs(mass2[i].second - mass3[j - 1].second)] = 
				min(dp2[j - 1][t + abs(mass2[i].second - mass3[j - 1].second)], dp0[t] + mass3[j - 1].first - mass2[i].first);
			}
		}
		for(int j = 0; j <= mass3.size(); j++)
		{
			for(int t = 0; t <= k; t++)
			{
				dp1[j][t] = dp2[j][t];
				dp2[j][t] = 0;
				dpright[i][t] = min(dpright[i][t], dp1[j][t]);
			}
		}
	}
	for(int j = 0; j <= k; j++)
	{
		ans = min(ans, sum + dpleft[mass2.size() - 1][j]);
		ans = min(ans, sum + dpright[0][j]);
	}
	for(int i = 0; i < mass2.size() - 1; i++)
	{
		for(int j = 0; j <= k; j++)
		{
			for(int t = 0; t + j <= k; t++)
			{
				ans = min(ans, sum + dpleft[i][j] + dpright[i + 1][t]);
			}
		}
	}
	cout << ans;
	return 0;
}

Compilation message

holding.cpp: In function 'int main()':
holding.cpp:41:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < mass2.size(); i++)
                 ~~^~~~~~~~~~~~~~
holding.cpp:47:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j <= mass1.size(); j++)
                  ~~^~~~~~~~~~~~~~~
holding.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < mass1.size(); j++)
                  ~~^~~~~~~~~~~~~~
holding.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j <= mass1.size(); j++)
                  ~~^~~~~~~~~~~~~~~
holding.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j <= mass3.size(); j++)
                  ~~^~~~~~~~~~~~~~~
holding.cpp:109:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j <= mass3.size(); j++)
                  ~~^~~~~~~~~~~~~~~
holding.cpp:124:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < mass2.size() - 1; i++)
                 ~~^~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 372 ms 3704 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 372 ms 3704 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 3 ms 516 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1484 ms 12608 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 372 ms 3704 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 3 ms 516 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1484 ms 12608 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Incorrect 1 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 372 ms 3704 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 3 ms 516 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1484 ms 12608 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Incorrect 1 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -