daily pastebin goal
68%
SHARE
TWEET

Untitled

a guest Dec 16th, 2018 51 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top