Submission #197992

#	Time	Username	Problem	Language	Result	Execution time	Memory
197992		ami	Holding (COCI20_holding)	C++17	110 / 110	141 ms	4600 KiB

holding

#include <bits/stdc++.h>
#define sz(c)       int(c.size())
#define rep(i,a,b)  for (int i=a; i<(b); ++i)
#define per(i,a,b)  for (int i=(b)-1; i>=(a); --i)
#define fore(c,...) for (auto __VA_ARGS__:(c))
using namespace std;
using ll = long long;

template<class T> bool umin(T &x,T y) { if (x<y) return 0; x=y; return 1; }
template<class T> bool umax(T &x,T y) { if (x>y) return 0; x=y; return 1; }

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(10);

	int N,L,R,K;
	cin>>N>>L>>R>>K;
	L--,R--;
	vector<int> A(N);
	fore(A,&i) cin>>i;

	vector<int> a,b;
	rep(i,0,N) if (i>=L && i<=R) b.emplace_back(i); else a.emplace_back(i);
	int na=sz(a),nb=sz(b);

	vector<vector<int>> best(nb+1,vector<int>(K+1,(int)1e9));
	best[0][0]=0;
	rep(j,0,nb) umin(best[j+1][0],best[j][0]+A[b[j]]);

	rep(i,0,na) {
		auto next=best;
		rep(j,0,nb) {
			int d=abs(a[i]-b[j]);
			rep(k,0,K+1) {
				umin(next[j+1][k],next[j][k]+A[b[j]]);
				if (k>=d) umin(next[j+1][k],best[j][k-d]+A[a[i]]);
			}
		}
		best=next;
	}
	cout<<*min_element(best[nb].begin(),best[nb].end())<<'\n';
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 22 / 22