DengklekMakingChains
方針
やるだけ
ソース
#include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #include <iostream> #include <utility> #include <set> #include <cctype> #include <queue> #include <stack> #include <cstdio> #include <cstdlib> #include <cmath> #include <iterator> using namespace std; class DengklekMakingChains{ int n_chain; vector<vector<int> > chains_; int ret; vector<bool> in_center; public: int maxBeauty(vector <string> chains){ n_chain = chains.size(); chains_.resize(n_chain, vector<int>(3)); char temp[2]; temp[1] = 0; for(int i = 0; i < n_chain; i++){ for(int j = 0; j < 3; j++){ temp[0] = chains[i][j]; chains_[i][j] = chains[i][j] == '.' ? -1 : atoi(temp); } } ret = 0; in_center = vector<bool>(n_chain, true); find_center(); find_side(); find_ex(); return ret; } void find_center(){ for(int i = 0; i < n_chain; i++){ int s = 0; for(int j = 0; j < 3; j++){ if(chains_[i][j] == -1){ s = 0; in_center[i] = false; break; } s += chains_[i][j]; } ret += s; } } void find_side(){ int s = 0; for(int l = 0; l < n_chain; l++){ for(int r = 0; r < n_chain; r++){ if(l == r){ s = max(s, max(left_value(l), right_value(r))); } else{ s = max(s, left_value(l) + right_value(r)); } } } ret += s; } void find_ex(){ for(int i = 0; i < n_chain; i++){ if(chains_[i][0] == -1 && chains_[i][1] != -1 && chains_[i][2] == -1){ ret = max(ret, chains_[i][1]); } } } int left_value(int l){ if(in_center[l]) return 0; vector<int> v = chains_[l]; int val = 0; for(int i = 2; i >= 0 && v[i] >= 0; i--){ val += v[i]; } return val; } int right_value(int r){ if(in_center[r]) return 0; vector<int> v = chains_[r]; int val = 0; for(int i = 0; i < 3 && v[i] >= 0; i++){ val += v[i]; } return val; } };