oj.uz

Submission #736140

# Submission time Handle Problem Language Result Execution time Memory
736140 2023-05-05T09:02:24 Z marvinthang Holding (COCI20_holding) C++17
110 / 110
 59 ms 107240 KB 
/*************************************
*    author: marvinthang             *
*    created: 05.08.2022 11:41:13    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                 div  ___div
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define             FULL(i)  (MASK(i) - 1)
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }

template <class T>             scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class T>            print_op(vector <T>)  { out << '{'; for (size_t i = 0; i + 1 < u.size(); ++i) out << u[i] << ", "; if (!u.empty()) out << u.back(); return out << '}'; }
template <class U, class V>   scan_op(pair <U, V>)  { return in >> u.fi >> u.se; }
template <class U, class V>  print_op(pair <U, V>)  { return out << '(' << u.fi << ", " << u.se << ')'; }
template <class A, class B>   inline bool minimize(A &a, B b)  { A eps = 1e-9; if (a > b + eps) { a = b; return true; } return false; }
template <class A, class B>   inline bool maximize(A &a, B b)  { A eps = 1e-9; if (a + eps < b) { a = b; return true; } return false; }

const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int dir[] = {1, 0, -1, 0, 1, 1, -1, -1, 1}; // {2, 1, -2, -1, -2, 1, 2, -1, 2};
const int MAX = 102;

int N, L, R, K, A[MAX];
int F[MAX][MAX][MAX * MAX / 4];
int fL[MAX][MAX * MAX / 4];
int fR[MAX][MAX * MAX / 4];

void init(void) {
	cin >> N >> L >> R >> K;
	minimize(K, N * N / 4);
	for (int i = 1; i <= N; ++i) cin >> A[i];
}

void process(void) {
	for (int i = L; i <= R; ++i) for (int j = 0; j < L; ++j) for (int k = 0; k <= K; ++k) {
		F[i][j][k] = F[i - 1][j][k] + A[i];
		if (j) {
			minimize(F[i][j][k], F[i][j - 1][k]);
			if (k >= i - j) minimize(F[i][j][k], F[i - 1][j - 1][k - (i - j)] + A[j]);
		}
	}
	for (int i = L - 1; i <= R; ++i) {
		fL[i][0] = F[i][L - 1][0];
		for (int k = 1; k <= K; ++k) fL[i][k] = min(fL[i][k - 1], F[i][L - 1][k]);
	}

	memset(F, 0, sizeof(F));
	for (int i = R; i >= L; --i) for (int j = N + 1; j > R; --j) for (int k = 0; k <= K; ++k) {
		F[i][j][k] = F[i + 1][j][k] + A[i];
		if (j <= N) {
			minimize(F[i][j][k], F[i][j + 1][k]);
			if (k >= j - i) minimize(F[i][j][k], F[i + 1][j + 1][k - (j - i)] + A[j]);
		}
	}
	for (int i = R + 1; i >= L; --i) {
		fR[i][0] = F[i][R + 1][0];
		for (int k = 1; k <= K; ++k) fR[i][k] = min(fR[i][k - 1], F[i][R + 1][k]);
	}

	int res = 1e9;
	for (int i = L - 1; i <= R; ++i)
		for (int k = 0; k <= K; ++k)
			minimize(res, fL[i][k] + fR[i + 1][K - k]);
	cout << res << '\n';
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("coci1920_r4_holding");
	init();
	process();
	// cerr << "Time elapsed: " << TIME << " s.\n";
	return (0^0);
}

Compilation message

holding.cpp: In function 'int main()':
holding.cpp:22:69: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
holding.cpp:81:2: note: in expansion of macro 'file'
   81 |  file("coci1920_r4_holding");
      |  ^~~~
holding.cpp:22:103: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                                                               ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
holding.cpp:81:2: note: in expansion of macro 'file'
   81 |  file("coci1920_r4_holding");
      |  ^~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 106224 KB Output is correct
2 Correct 53 ms 106268 KB Output is correct
3 Correct 49 ms 106316 KB Output is correct
4 Correct 46 ms 106216 KB Output is correct
5 Correct 42 ms 106316 KB Output is correct
6 Correct 55 ms 106304 KB Output is correct
7 Correct 56 ms 106188 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 106224 KB Output is correct
2 Correct 53 ms 106268 KB Output is correct
3 Correct 49 ms 106316 KB Output is correct
4 Correct 46 ms 106216 KB Output is correct
5 Correct 42 ms 106316 KB Output is correct
6 Correct 55 ms 106304 KB Output is correct
7 Correct 56 ms 106188 KB Output is correct
8 Correct 49 ms 106280 KB Output is correct
9 Correct 52 ms 106320 KB Output is correct
10 Correct 46 ms 106388 KB Output is correct
11 Correct 59 ms 106516 KB Output is correct
12 Correct 47 ms 106464 KB Output is correct
13 Correct 47 ms 106576 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 106224 KB Output is correct
2 Correct 53 ms 106268 KB Output is correct
3 Correct 49 ms 106316 KB Output is correct
4 Correct 46 ms 106216 KB Output is correct
5 Correct 42 ms 106316 KB Output is correct
6 Correct 55 ms 106304 KB Output is correct
7 Correct 56 ms 106188 KB Output is correct
8 Correct 49 ms 106280 KB Output is correct
9 Correct 52 ms 106320 KB Output is correct
10 Correct 46 ms 106388 KB Output is correct
11 Correct 59 ms 106516 KB Output is correct
12 Correct 47 ms 106464 KB Output is correct
13 Correct 47 ms 106576 KB Output is correct
14 Correct 44 ms 106188 KB Output is correct
15 Correct 43 ms 106228 KB Output is correct
16 Correct 52 ms 106188 KB Output is correct
17 Correct 42 ms 106188 KB Output is correct
18 Correct 46 ms 106364 KB Output is correct
19 Correct 48 ms 106456 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 106224 KB Output is correct
2 Correct 53 ms 106268 KB Output is correct
3 Correct 49 ms 106316 KB Output is correct
4 Correct 46 ms 106216 KB Output is correct
5 Correct 42 ms 106316 KB Output is correct
6 Correct 55 ms 106304 KB Output is correct
7 Correct 56 ms 106188 KB Output is correct
8 Correct 49 ms 106280 KB Output is correct
9 Correct 52 ms 106320 KB Output is correct
10 Correct 46 ms 106388 KB Output is correct
11 Correct 59 ms 106516 KB Output is correct
12 Correct 47 ms 106464 KB Output is correct
13 Correct 47 ms 106576 KB Output is correct
14 Correct 44 ms 106188 KB Output is correct
15 Correct 43 ms 106228 KB Output is correct
16 Correct 52 ms 106188 KB Output is correct
17 Correct 42 ms 106188 KB Output is correct
18 Correct 46 ms 106364 KB Output is correct
19 Correct 48 ms 106456 KB Output is correct
20 Correct 55 ms 106296 KB Output is correct
21 Correct 44 ms 106264 KB Output is correct
22 Correct 42 ms 106212 KB Output is correct
23 Correct 46 ms 106196 KB Output is correct
24 Correct 45 ms 106900 KB Output is correct
25 Correct 54 ms 107240 KB Output is correct