Untitled

 avatar
unknown
plain_text
5 months ago
1.8 kB
4
Indexable
#include <bits/stdc++.h>

using namespace std;

#define Chris "test"
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORD(i, a, b) for(int i = (a); i <= (b); ++i)
#define REP(i, a, b) for(int i = (a); i > (b); --i)
#define REPD(i, a, b) for(int i = (a); i >= (b); --i)
#define FORE(i, v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define All(v) (v).begin(), (v).end()
#define rAll(v) (v).rbegin(), (v).rend()
#define MARK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define fi first
#define se second
#define el "\n"

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vii;
typedef set<int> sii;
typedef map<int, int> mii;
typedef stack<int> sti;
typedef deque<int> dqi;
typedef queue<int> quei;
typedef unordered_map<int, int> umii;

const int mod = (int) 1e5;
const int INF = (int) 1e9;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int n;

void solve()
{
cin >> n;
vii t(n + 1), r(n), dp(n + 1, 0), prev(n + 1, 0);
FORD(i, 1, n) cin >> t[i];
FOR(i, 1, n) cin >> r[i];
dp[1] = t[1];
FORD(i, 2, n)
{
    dp[i] = dp[i - 1] + t[i];
    prev[i] = i - 1;
    if(i > 1 && dp[i] > dp[i - 2] + r[i - 1])
    {
        dp[i] = dp[i - 2] + r[i - 1];
        prev[i] = i - 2;
    }
}
cout << dp[n] << el;

vii removed;
for(int i = n; i >= 1; i = prev[i])
{
    if(prev[i] == i - 2)
    {
        removed.pb(i);
    }
}
s
if(removed.empty())
{
    cout << 0 << el;
}
else
{
    reverse(All(removed));
    for(int i : removed)
    {
        cout << i << " ";
    }
    cout << el;
}
}

int main()
{

solve();

return 0;
}
Editor is loading...
Leave a Comment