Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- using ll = long long;
- using ld = long double;
- using ull = unsigned long long;
- using pii = pair<int, int>;
- using pll = pair<ll, ll>;
- using pld = pair<ld, ld>;
- #define fi first
- #define se second
- #define pb push_back
- #define pf push_front
- #define mp make_pair
- #define ins insert
- #define btpc __builtin_popcount
- #define btclz __builtin_clz
- #define sz(x) (int)(x.size());
- #define all(x) x.begin(), x.end()
- #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
- int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
- int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
- template<class X, class Y>
- bool minimize(X &x, const Y &y) {
- if (x > y)
- {
- x = y;
- return true;
- }
- return false;
- }
- template<class X, class Y>
- bool maximize(X &x, const Y &y) {
- if (x < y)
- {
- x = y;
- return true;
- }
- return false;
- }
- const int MOD = 1e9 + 7; //998244353
- template<class X, class Y>
- void add(X &x, const Y &y) {
- x = (x + y);
- if(x >= MOD) x -= MOD;
- }
- template<class X, class Y>
- void sub(X &x, const Y &y) {
- x = (x - y);
- if(x < 0) x += MOD;
- }
- /* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/
- const ll INF = 1e18;
- const int N = 4e3 + 10;
- ll dp[N][N];
- int opt[N][N], optL[N][N], optR[N][N];
- ll c[N], w[N], pref[N];
- vector<int> ans;
- ll f(int l, int r) {
- if(l > r) return 0;
- if(l == r) return dp[l][r] = c[l];
- if(dp[l][r] != -1) return dp[l][r];
- dp[l][r] = INF;
- for(int i = r; i >= l; i--) {
- ll cost = c[i] + pref[r] - pref[l - 1] - w[i];
- maximize(cost, f(i + 1, r));
- maximize(cost, f(l, i - 1));
- if(minimize(dp[l][r], cost)) opt[l][r] = i;
- }
- return dp[l][r];
- }
- void dfs(int l, int r) {
- if(l == r) {
- ans.pb(l);
- return;
- }
- int pos = opt[l][r];
- ans.pb(pos);
- if(pos > l) dfs(l, pos - 1);
- if(pos < r) dfs(pos + 1, r);
- }
- void dfs2(int l, int r) {
- if(l == r) {
- ans.pb(l);
- return;
- }
- for(int i = r; i >= l; i--) {
- ll cost = c[i] + pref[r] - pref[l - 1] - w[i];
- if(i < r) maximize(cost, dp[i + 1][r]);
- if(i > l) maximize(cost, dp[l][i - 1]);
- if(cost == dp[l][r]) {
- ans.pb(i);
- if(i > l) dfs2(l, i - 1);
- if(i < r) dfs2(i + 1, r);
- return;
- }
- }
- }
- void solve() {
- int n; cin >> n;
- for(int i = 1; i <= n; i++) cin >> c[i];
- for(int i = 1; i <= n; i++) cin >> w[i];
- for(int i = 1; i <= n; i++) pref[i] = pref[i - 1] + w[i];
- if(n <= 400) {
- for(int i = 1; i <= n; i++) {
- for(int j = 1; j <= n; j++) dp[i][j] = -1;
- }
- cout << f(1, n) << '\n';
- dfs(1, n);
- for(auto x : ans) cout << x << " ";
- return;
- }
- if(n <= 4e3) {
- //Knuth : f[i][j - 1] <= f[i][j] <= f[i + 1][j];
- for(int i = 1; i <= n; i++) {
- for(int j = 1; j <= n; j++) dp[i][j] = INF;
- dp[i][i] = c[i];
- opt[i][i] = optL[i][i] = optR[i][i] = i;
- }
- for(int len = 2; len <= n; len++) {
- for(int l = 1; l + len - 1 <= n; l++) {
- int r = l + len - 1;
- for(int pos = optR[l + 1][r]; pos >= optL[l][r - 1]; pos--) {
- ll cost = c[pos] + pref[r] - pref[l - 1] - w[pos];
- if(pos < r) maximize(cost, dp[pos + 1][r]);
- if(pos > l) maximize(cost, dp[l][pos - 1]);
- if(minimize(dp[l][r], cost)) optR[l][r] = pos;
- if(cost == dp[l][r]) optL[l][r] = pos;
- }
- }
- }
- cout << dp[1][n] << "\n";
- dfs2(1, n);
- for(auto x : ans) cout << x << " ";
- return;
- }
- }
- int main()
- {
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- //online
- freopen("QBST.inp", "r", stdin);
- freopen("QBST.out", "w", stdout);
- #endif
- int tc = 1, ddd = 0;
- // cin >> tc;
- while(tc--) {
- //ddd++;
- //cout << "Case #" << ddd << ": ";
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement