This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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++)
{
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];
dpleft[i][t] = min(dpleft[i][t], dp1[j][t]);
}
}
}
for(int j = 0; j <= mass3.size(); j++)
{
for(int t= 0; t <= k; t++)
{
dp1[j][t] = 0;
dp2[j][t] = 0;
}
}
for(int i = mass2.size() - 1; i >= 0; i--)
{
for(int t = 0; t <= k; t++)
{
dp0[t] = 0;
}
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];
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 (stderr)
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:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j <= mass1.size(); j++)
~~^~~~~~~~~~~~~~~
holding.cpp:72:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j <= mass3.size(); j++)
~~^~~~~~~~~~~~~~~
holding.cpp:102:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j <= mass3.size(); j++)
~~^~~~~~~~~~~~~~~
holding.cpp:116:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < mass2.size() - 1; i++)
~~^~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |