oj.uz

Submission #897511

# Submission time Handle Problem Language Result Execution time Memory
897511 2024-01-03T10:33:01 Z Phan_Tien_Dung K blocks (IZhO14_blocks) C++17
0 / 100
 1 ms 600 KB 
// #pragma GCC optimize("unroll-loops")
// #pragma gcc optimize("Ofast")
// #pragma GCC optimization("Ofast")
// #pragma optimize(Ofast)
#include <bits/stdc++.h>

using namespace std;

#define f 					first
#define s 					second
#define int 				long long
#define sz(A) 				(int)A.size()
#define m_p(A, B) 			make_pair(A, B)
#define all(A) 				A.begin(), A.end()
#define forcin(A, X, Y) 	for (int i = X; i <= Y; ++i) cin >> A[i]
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

void SetIO(string name) {
    if (fopen((name + ".INP").c_str(), "r")) {
        freopen((name + ".INP").c_str(), "r", stdin);
        freopen((name + ".OUT").c_str(), "w", stdout);
    }
}

template <class T>
bool Minimize(T &a, T b) {
    if (a > b)
        return a = b, true;
    return false;
}

template <class T>
bool Maximize(T &a, T b) {
    if (a < b)
        return a = b, true;
    return false;
}

const int INF = 4557430888798830399;
const int MOD = 998244353;
const int N = 100005;
const int MX = 20;

int n, k, spatab[N][20];
vector<int> cur, nex;

int GetMax(int l, int r) {
	int lg = log2(r - l + 1);
	return max(spatab[l][lg], spatab[r - (1 << lg) + 1][lg]);
}

void Compute(int l, int r, int optl, int optr) {
	if (l > r) return;
	int m = l + r >> 1;
	ii best = m_p(INF, -1);
	for (int i = optl; i <= min(m, optr); ++i) {
		Minimize(best, m_p(cur[i - 1] + GetMax(i, m), i));
	}
	nex[m] = best.f;
	int optm = best.s;
	Compute(l, m - 1, optl, optm);
	Compute(m + 1, r, optm, optr);
}

void Solve() {
	cin >> n >> k;
	cur.resize(n + 1, 0);
	nex.resize(n + 1, 0);
	for (int i = 1; i <= n; ++i) {
		cin >> spatab[i][0];
	}
	for (int i = 1; (1 << i) <= n; ++i) {
		for (int j = 1; j + (1 << i) - 1 <= n; ++j) {
			spatab[j][i] = max(spatab[j][i - 1], spatab[j + (1 << i - 1)][i - 1]);
		}
	}
	cur[0] = INF;
	for (int i = 1; i <= n; ++i) {
		cur[i] = GetMax(1, i);
	}
	for (int i = 1; i < k; ++i) {
		Compute(i, n, i, n);
		cur.swap(nex);
		fill(all(nex), INF);
	}
	cout << cur[n];
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    clock_t tStart = clock();
    SetIO("main");

    int t = 1;
//    cin >> t;
    while (t--) {
        Solve();
    }

    cerr << "\nTime Taken: ";
    cerr << fixed << setprecision(10) << (double)(clock() - tStart) / CLOCKS_PER_SEC;
}

Compilation message

blocks.cpp: In function 'void Compute(long long int, long long int, long long int, long long int)':
blocks.cpp:58:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |  int m = l + r >> 1;
      |          ~~^~~
blocks.cpp: In function 'void Solve()':
blocks.cpp:78:60: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   78 |    spatab[j][i] = max(spatab[j][i - 1], spatab[j + (1 << i - 1)][i - 1]);
      |                                                          ~~^~~
blocks.cpp: In function 'void SetIO(std::string)':
blocks.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen((name + ".INP").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen((name + ".OUT").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -