Untitled
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