class Cut { public: int getMaximum(vector <int> eelLengths, int maxCuts) { sort(ALL(eelLengths)); int result = 0; REP(i, eelLengths.size()) { int l = eelLengths[i]; if (l % 10 != 0) { continue; } int cut = l / 10 - 1; if (cut <= maxCuts) { result += l / 10; maxCuts -= cut; } else { result += maxCuts; maxCuts = 0; } } REP(i, eelLengths.size()) { int l = eelLengths[i]; if (l % 10 == 0) { continue; } int cut = l / 10; result += min(cut, maxCuts); maxCuts -= min(cut, maxCuts); } return result; } };
class SPartition { public: long long getCount(string s) { // ビット, Xの長さ map<pair<int, int>, ll> current; current.insert(MP(MP(0, 0), 1)); int N = s.size(); REP(i, N) { char ch = s[i]; int num = (ch == 'o' ? 0 : 1); map<pair<int, int>, ll> next; for (map<pair<int, int>, ll>::const_iterator it = current.begin(), itEnd = current.end(); it != itEnd; ++it) { int bit = it->first.first; int xLen = it->first.second; int yLen = i - xLen; ll ans = it->second; if (i == xLen * 2) { assert(i == yLen * 2); next[MP(bit | (num << xLen), xLen + 1)] += ans; next[MP(bit | (num << xLen), xLen)] += ans; } else if (i < xLen * 2) { // Xの方が長い if (xLen * 2 < N) { // Xに加える next[MP(bit | (num << xLen), xLen + 1)] += ans; } // チェック後Yに加える if (((bit & (1 << yLen)) != 0) == (num != 0)) { next[MP(bit, xLen)] += ans; } } else { // Yの方が長い if (yLen * 2 < N) { // Yに加える next[MP(bit | (num << yLen), xLen)] += ans; } // チェック後Xに加える if (((bit & (1 << xLen)) != 0) == (num != 0)) { next[MP(bit, xLen + 1)] += ans; } } } swap(current, next); //for (map<pair<int, int>, ll>::iterator it = current.begin(), itEnd = current.end(); it != itEnd; ++it) { // printf("bit:%d xLen:%d yLen:%d -> %d\n", it->first, it->first.second, i + 1 - it->first.second, (int)it->second); //} //printf("\n"); } long long result = 0; for (map<pair<int, int>, ll>::iterator it = current.begin(), itEnd = current.end(); it != itEnd; ++it) { result += it->second; } return result; } }
oox 491.87 97位 1716->1816 久々の1800台を回復しました。この調子を保っていきたいです。