Instantly share code, notes, and snippets.

# ctylim/yukicoder258.cpp Created Dec 4, 2015

What would you like to do?
yukicoder No.258
 #include #include #include #include #include #include #include #include #include #include #include #include #include #define repd(i,a,b) for (int i=(a);i<(b);i++) #define rep(i,n) repd(i,0,n) #define var auto #define mod 1000000007 #define inf 2147483647 #define nil -1 typedef long long ll; using namespace std; inline int input(){ int a; cin >> a; return a; } template inline void output(T a, int p) { if(p){ cout << fixed << setprecision(p) << a << "\n"; } else{ cout << a << "\n"; } } // end of template int main() { cin.tie(0); // source code int N = input(); vector A(N); rep(i, N){ A[i] = input(); } vector dp(N + 3); vector route(N + 3); dp[0] = -inf; dp[1] = dp[2] = 0; route[0] = route[1] = route[2] = ""; repd(i, 3, N + 3){ if (dp[i - 3] + A[i - 3] >= dp[i - 2] + A[i - 3]){ route[i] = route[i - 3] + "1"; dp[i] = dp[i - 3] + A[i - 3]; } else{ route[i] = route[i - 2] + "0"; dp[i] = dp[i - 2] + A[i - 3]; } } vector ret; int now = -2; string rt = route[N + 2]; rep(i, rt.size()){ if (rt[i] == '0'){ ret.push_back(now + 2); now += 2; } else{ ret.push_back(now + 3); now += 3; } } output(dp[N + 2], 0); rep(i, ret.size()){ if (i) cout << " "; cout << ret[i] + 1; } cout << endl; return 0; }