oj.uz

Submission #197992

# Submission time Handle Problem Language Result Execution time Memory
197992 2020-01-24T12:43:04 Z ami Holding (COCI20_holding) C++17
110 / 110
 141 ms 4600 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 4 ms 1032 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 4 ms 1032 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 36 ms 2552 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 4 ms 1032 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 36 ms 2552 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 380 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 3 ms 376 KB Output is correct
19 Correct 36 ms 2552 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 4 ms 1032 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 36 ms 2552 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 380 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 3 ms 376 KB Output is correct
19 Correct 36 ms 2552 KB Output is correct
20 Correct 4 ms 376 KB Output is correct
21 Correct 3 ms 380 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 504 KB Output is correct
25 Correct 141 ms 4600 KB Output is correct