Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define len(x) int(x.size())
- #define all(x) x.begin(), x.end()
- typedef long long ll;
- /*
- ll s(ll x){
- if (x == 0) return 0;
- return (((x + 1ll) * x) / 2);
- }
- ll n, a, b, c;
- ll sum(ll x){
- ll s1 = s(n - x) * a;
- ll s2 = s(x - 1) * b;
- ll res = s1 + s2 + x * c;
- //cout << s1 << ' '<< s2 << ' ' << x * c << endl;
- return res;
- }
- ll f(ll x){
- vector <ll> t(n + 1);
- for (ll i = 1; i < x; i++){
- t[i] = min(a * i, x * c + (x - i) * b);
- }
- for (ll i = x; i <= n; i++)
- t[i] = min(a * i, x * c + (i - x) * a);
- ll res = 0;
- for (int i = 1; i <= n; i++)
- res = max(res, t[i]);
- return res;
- }
- int main(){
- #ifdef HOME
- freopen("input.txt", "rt", stdin);
- #endif //HOME
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cin >> n >> a >> b >> c;
- ll l = 0, r = n;
- //cout << sum(3);
- //return 0;
- while(r - l > 1){
- ll len = (r - l + 1) / 3ll;
- ll x1 = l + len;
- ll x2 = r - len;
- ll f1 = f(x1);
- ll f2 = f(x2);
- if (f1 > f2)
- l = x1;
- else
- r = x2;
- }
- ll ans = 1e18;
- ll id;
- for (int i = max(0ll, l - 5); i <= min(n, l + 5ll); i++){
- //cout << i << ' ' << f(i) << endl;
- ll was = ans;
- ans = min(ans, f(i));
- if (was != ans)
- id = i;
- }
- #ifdef HOME
- cout << id << ' ';
- #endif //HOME
- cout << ans;
- return 0;
- }*/
- map <string, int> cost;
- int main(){
- #ifdef HOME
- freopen("input.txt", "rt", stdin);
- #endif //HOME
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- string s;
- cin >> s;
- int n = len(s);
- vector<int> dp(n + 1, 1e9);
- dp[0] = 0;
- cost["I"] = 1;
- cost["IV"] = 4;
- cost["V"] = 5;
- cost["IX"] = 9;
- cost["X"] = 10;
- cost["XL"] = 40;
- cost["L"] = 50;
- cost["XC"] = 90;
- cost["C"] = 100;
- cost["CD"] = 400;
- cost["D"] = 500;
- cost["CM"] = 900;
- cost["M"] = 1000;
- for (int i = 1; i <= n; ++i) {
- for (int j = max(1, i - 4); j <= i; ++j) {
- string p = s.substr(j - 1, i - j + 1);
- if (cost.count(p)) dp[i] = min(dp[i], dp[j - 1] + cost[p]);
- }
- }
- cout << dp[n];
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement