Submission #1835290
Source Code Expand
#include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector> #include <climits> #define rep(i, m, n) for(int i=int(m);i<int(n);i++) #define EACH(i, c) for (auto &(i): c) #define all(c) begin(c),end(c) #define EXIST(s, e) ((s).find(e)!=(s).end()) #define SORT(c) sort(begin(c),end(c)) #define pb emplace_back #define MP make_pair #define SZ(a) int((a).size()) //#define LOCAL 0 //#ifdef LOCAL //#define DEBUG(s) cout << (s) << endl //#define dump(x) cerr << #x << " = " << (x) << endl //#define BR cout << endl; //#else //#define DEBUG(s) do{}while(0) //#define dump(x) do{}while(0) //#define BR //#endif //改造 typedef long long int ll; using namespace std; #define INF (1 << 25) #define INFl (ll)5e15 #define DEBUG 0 //デバッグする時1にしてね #define dump(x) cerr << #x << " = " << (x) << endl //ここから編集する int main() { string s; cin >> s; int N = s.size(); int dp[105][105][105]; rep(i,0,N+1){ rep(j,0,N+1){ rep(k,0,N+1){ dp[i][j][k] = INF; } } } dp[0][0][0] = 0; rep(i,0,N+1){ rep(j,0,i+1){ rep(k,0,i+1){ if(k - 1 >= 0){ if(s[i] == '('){ dp[i+1][i+1][k-1] = min(dp[i][j][k]+1,dp[i+1][i+1][k-1]); }else{ // dp[i+1][i][k-1] = min(dp[i][j][k],dp[i+1][i][k-1]-1); dp[i+1][j][k-1] = min(dp[i][j][k],dp[i+1][i][k-1]); } } // if(k + 1 <= N){ if(s[i] == '('){ dp[i+1][j][k+1] = min(dp[i][j][k],dp[i+1][i][k+1]); }else{ dp[i+1][i+1][k+1] = min(dp[i][j][k]+1,dp[i+1][i+1][k+1]); } // } } } } int ans = 114514; rep(j,1,N+1){ ans = min(ans,j-1 + dp[N][j][0]); } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - 天下一魔力発電 |
User | homesentinel |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2624 Byte |
Status | WA |
Exec Time | 5 ms |
Memory | 4608 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 400 | ||||
Status |
|
Set Name | Test Cases |
---|---|
All | 01_sample_01, 01_sample_02, 01_sample_03, 02_manual_01, 02_manual_02, 02_manual_03, 10_random_00, 10_random_01, 10_random_02, 10_random_03, 10_random_04, 10_random_05, 10_random_06, 10_random_07, 10_random_08, 10_random_09, 10_random_10, 10_random_11, 10_random_12, 10_random_13, 10_random_14, 10_random_15, 10_random_16, 10_random_17, 10_random_18, 10_random_19, 20_max_00, 20_max_01, 20_max_02, 20_max_03, 20_max_04, 20_max_05 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01_sample_01 | AC | 1 ms | 384 KB |
01_sample_02 | AC | 1 ms | 256 KB |
01_sample_03 | AC | 1 ms | 256 KB |
02_manual_01 | AC | 1 ms | 256 KB |
02_manual_02 | AC | 1 ms | 384 KB |
02_manual_03 | AC | 1 ms | 256 KB |
10_random_00 | AC | 2 ms | 2560 KB |
10_random_01 | AC | 1 ms | 384 KB |
10_random_02 | AC | 2 ms | 2816 KB |
10_random_03 | AC | 3 ms | 3712 KB |
10_random_04 | AC | 1 ms | 384 KB |
10_random_05 | AC | 1 ms | 512 KB |
10_random_06 | AC | 2 ms | 3072 KB |
10_random_07 | AC | 4 ms | 4352 KB |
10_random_08 | AC | 2 ms | 3200 KB |
10_random_09 | AC | 2 ms | 2432 KB |
10_random_10 | AC | 2 ms | 2432 KB |
10_random_11 | AC | 1 ms | 256 KB |
10_random_12 | AC | 3 ms | 3712 KB |
10_random_13 | AC | 3 ms | 3840 KB |
10_random_14 | AC | 1 ms | 512 KB |
10_random_15 | AC | 1 ms | 512 KB |
10_random_16 | AC | 4 ms | 4224 KB |
10_random_17 | AC | 3 ms | 4352 KB |
10_random_18 | AC | 4 ms | 4224 KB |
10_random_19 | AC | 3 ms | 4480 KB |
20_max_00 | AC | 5 ms | 4608 KB |
20_max_01 | AC | 4 ms | 4608 KB |
20_max_02 | AC | 5 ms | 4608 KB |
20_max_03 | WA | 4 ms | 4608 KB |
20_max_04 | WA | 5 ms | 4608 KB |
20_max_05 | AC | 5 ms | 4608 KB |