Advertisement
Guest User

Untitled

a guest
Dec 16th, 2018
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.41 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define len(x) int(x.size())
  6. #define all(x) x.begin(), x.end()
  7.  
  8. typedef long long ll;
  9. /*
  10. ll s(ll x){
  11. if (x == 0) return 0;
  12. return (((x + 1ll) * x) / 2);
  13. }
  14.  
  15. ll n, a, b, c;
  16.  
  17. ll sum(ll x){
  18. ll s1 = s(n - x) * a;
  19. ll s2 = s(x - 1) * b;
  20. ll res = s1 + s2 + x * c;
  21. //cout << s1 << ' '<< s2 << ' ' << x * c << endl;
  22. return res;
  23. }
  24.  
  25. ll f(ll x){
  26. vector <ll> t(n + 1);
  27. for (ll i = 1; i < x; i++){
  28. t[i] = min(a * i, x * c + (x - i) * b);
  29. }
  30. for (ll i = x; i <= n; i++)
  31. t[i] = min(a * i, x * c + (i - x) * a);
  32. ll res = 0;
  33. for (int i = 1; i <= n; i++)
  34. res = max(res, t[i]);
  35. return res;
  36. }
  37.  
  38. int main(){
  39. #ifdef HOME
  40. freopen("input.txt", "rt", stdin);
  41. #endif //HOME
  42. ios_base::sync_with_stdio(0);
  43. cin.tie(0);
  44. cout.tie(0);
  45. cin >> n >> a >> b >> c;
  46. ll l = 0, r = n;
  47. //cout << sum(3);
  48. //return 0;
  49. while(r - l > 1){
  50. ll len = (r - l + 1) / 3ll;
  51. ll x1 = l + len;
  52. ll x2 = r - len;
  53. ll f1 = f(x1);
  54. ll f2 = f(x2);
  55. if (f1 > f2)
  56. l = x1;
  57. else
  58. r = x2;
  59. }
  60. ll ans = 1e18;
  61. ll id;
  62. for (int i = max(0ll, l - 5); i <= min(n, l + 5ll); i++){
  63. //cout << i << ' ' << f(i) << endl;
  64. ll was = ans;
  65. ans = min(ans, f(i));
  66. if (was != ans)
  67. id = i;
  68. }
  69. #ifdef HOME
  70. cout << id << ' ';
  71. #endif //HOME
  72. cout << ans;
  73. return 0;
  74. }*/
  75.  
  76. map <string, int> cost;
  77.  
  78. int main(){
  79. #ifdef HOME
  80. freopen("input.txt", "rt", stdin);
  81. #endif //HOME
  82. ios_base::sync_with_stdio(0);
  83. cin.tie(0);
  84. cout.tie(0);
  85. string s;
  86. cin >> s;
  87. int n = len(s);
  88. vector<int> dp(n + 1, 1e9);
  89. dp[0] = 0;
  90.  
  91. cost["I"] = 1;
  92.  
  93. cost["IV"] = 4;
  94. cost["V"] = 5;
  95. cost["IX"] = 9;
  96.  
  97. cost["X"] = 10;
  98. cost["XL"] = 40;
  99. cost["L"] = 50;
  100. cost["XC"] = 90;
  101.  
  102. cost["C"] = 100;
  103. cost["CD"] = 400;
  104. cost["D"] = 500;
  105. cost["CM"] = 900;
  106.  
  107. cost["M"] = 1000;
  108.  
  109. for (int i = 1; i <= n; ++i) {
  110. for (int j = max(1, i - 4); j <= i; ++j) {
  111. string p = s.substr(j - 1, i - j + 1);
  112. if (cost.count(p)) dp[i] = min(dp[i], dp[j - 1] + cost[p]);
  113. }
  114. }
  115. cout << dp[n];
  116. return 0;
  117. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement