Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
yukicoder No.258
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#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 <typename T>
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<int> A(N);
rep(i, N){
A[i] = input();
}
vector<int> dp(N + 3);
vector<string> 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<int> 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment