Submission #256706

#TimeUsernameProblemLanguageResultExecution timeMemory
256706MrRobot_28Holding (COCI20_holding)C++17
88 / 110
2088 ms24320 KiB
#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 + abs(mass2[i].second - mass1[j].second) <= k; t++) { 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 + abs(mass2[i].second - mass3[j - 1].second) <= k; t++) { 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:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j <= mass1.size(); j++)
                  ~~^~~~~~~~~~~~~~~
holding.cpp:68:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0; j <= mass3.size(); j++)
                 ~~^~~~~~~~~~~~~~~
holding.cpp:94:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j <= mass3.size(); j++)
                  ~~^~~~~~~~~~~~~~~
holding.cpp:108:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < mass2.size() - 1; i++)
                 ~~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...