Submission #71383757

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int; using ll = long long; using ull = unsigned long long;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using ld = long double; using i128 = __int128; using u128 = unsigned __int128;
template<typename T, size_t N, size_t M> using matrix = array<array<T, M>, N>;
template<typename T1, typename T2> bool chkmin(T1& a, const T2& b) { return b < a ? (a = b, true) : false; }
template<typename T1, typename T2> bool chkmax(T1& a, const T2& b) { return b > a ? (a = b, true) : false; }
template<class... T> void debug(T&&... x) { cout << "(debug) "; ((cout << x << " "), ...); cout << "\n"; }
void fileIO(const string& x) { freopen((x + ".in").c_str(), "r", stdin), freopen((x + ".out").c_str(), "w", stdout); }
mt19937_64 gen(random_device{}());
int test_num = 1, test_case = 1;
const int int_Inf = 1e9; const ll Inf = 1e18;

const int N = 4e4 + 5, Q = 2e5 + 5, LOGN = 16, T = 500;

using DP = array<ll, T + 1>;

// void convolition(DP &c, const DP &a, const DP &b) {
// 	for(int i = 0; i <= T; i++) for(int j = 0; i + j <= T; j++) {
// 		chkmax(c[i + j], a[i] + b[j]);
// 	}
// }
DP add(const DP &a, int wt, ll val) {
	DP c = a;
	for(int i = T; i >= wt; i--) {
		chkmax(c[i], c[i - wt] + val);
	}
	return c;
}

int n, q, h[N], w[N];
ll ans[Q];
DP a[N], f[N];

void solve(int l, int r, vector<array<int, 4> > qry) {
	if(l == r) {
		for(auto [l, r, t, id] : qry) ans[id] = a[l][t];
		return;
	}
	int mid = (l + r) / 2;
	vector<array<int, 4> > Lq, Rq, Mq;

	for(auto [l, r, t, id] : qry) {
		if(l <= mid && mid + 1 <= r) Mq.push_back({ l, r, t, id });
		else if(r <= mid) Lq.push_back({ l, r, t, id });
		else Rq.push_back({ l, r, t, id });
	}
	solve(l, mid, Lq); solve(mid + 1, r, Rq);

	for(int i = l; i <= r; i++) f[i] = {};
	f[mid] = a[mid], f[mid + 1] = a[mid + 1];
	for(int i = mid - 1; i >= l; i--) f[i] = add(f[i + 1], h[i], w[i]);
	for(int i = mid + 2; i <= r; i++) f[i] = add(f[i - 1], h[i], w[i]);
	for(auto [l, r, t, id] : Mq) {
		for(int k = 0; k <= t; k++) {
			chkmax(ans[id], f[l][k] + f[r][t - k]);
		}
	}
}

void solution() {
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> h[i] >> w[i];
	for(int i = 1; i <= n; i++) {
		a[i] = {};
		for(int j = h[i]; j <= T; j++) a[i][j] = w[i];
	}
	cin >> q;
	vector<array<int, 4> > qry;
	for(int i = 1; i <= q; i++) {
		int l, r, t; cin >> l >> r >> t;
		qry.push_back({ l, r, t, i });
	}
	solve(1, n, qry);
	for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}
void sol_clear() {}
void prework() {}

int main() {
	// fileIO("");
	ios::sync_with_stdio(false), cin.tie(nullptr);
	prework();
	// cin >> test_num;
	for(test_case = 1; test_case <= test_num; test_case++) solution(), sol_clear();
	cerr << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
	return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void fileIO(const std::string&)’:
Main.cpp:10:39: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   10 | void fileIO(const string& x) { freopen((x + ".in").c_str(), "r", stdin), freopen((x + ".out").c_str(), "w", stdout); }
      |                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:10:81: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   10 | void fileIO(const string& x) { freopen((x + ".in").c_str(), "r", stdin), freopen((x + ".out").c_str(), "w", stdout); }
      |                                                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Judge Result