fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <utility>
  4. #include <algorithm>
  5. #pragma GCC diagnostic ignored "-Wlong-long"
  6. using namespace std;
  7. int n;
  8. char s[500001];
  9. int lval[500000];
  10. int rval[500000];
  11.  
  12. long long dp[2][500001];
  13.  
  14. const long long impossible = 500000LL * 2147483647LL + 1;
  15.  
  16. long long solve() {
  17.     dp[1][0] = 0;
  18.     fill_n(dp[1] + 1, n, impossible * 2);
  19.     for(int i = 0; i < n; i++) {
  20.         int t = i % 2, f = 1 - t;
  21.         switch(s[i]) {
  22.         case '(':
  23.             dp[t][0] = impossible * 2;
  24.             copy(dp[f], dp[f] + n, dp[t] + 1);
  25.             break;
  26.         case ')':
  27.             copy(dp[f] + 1, dp[f] + n + 1, dp[t]);
  28.             dp[t][n] = impossible * 2;
  29.             break;
  30.         case '?':
  31.             dp[t][0] = dp[f][1] + rval[i];
  32.             for(int j = 1; j < n; j++)
  33.                 dp[t][j] = min(dp[f][j - 1] + lval[i], dp[f][j + 1] + rval[i]);
  34.             dp[t][n] = dp[f][n - 1] + lval[i];
  35.             break;
  36.         }
  37.     }
  38.     return dp[(n - 1) % 2][0];
  39. }
  40.  
  41.  
  42. int main(){
  43.     int t;
  44.     scanf("%d", &t);
  45.     while(t--) {
  46.         scanf("%s", s);
  47.         n = strlen(s);
  48.         for(int i = 0; i < n; i++)
  49.             if(s[i] == '?')
  50.                 scanf("%d %d", lval + i, rval + i);
  51.         long long x = solve();
  52.         if(x >= impossible) {
  53.             puts("IMBA");
  54.         } else {
  55.             #pragma GCC diagnostic push
  56.             #pragma GCC diagnostic ignored "-Wformat"
  57.             printf("%lld\n", x);
  58.             #pragma GCC diagnostic pop
  59.         }
  60.     }
  61. }
  62.  
Success #stdin #stdout 0s 15504KB
comments (?)
stdin
copy 
4
(())
(??)
1 10
10 100
?????)))))
2 1
2 1
2 1
2 1
2 1
(((((?
2147483647 -2147483648
stdout
copy 
0
20
10
IMBA
https://ideone.com/pSjcyH
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!