Submission #795225

#	Time	Username	Problem	Language	Result	Execution time	Memory
795225		vjudge1	Copy and Paste 3 (JOI22_copypaste3)	C++11	15 / 100	3082 ms	280264 KiB

copypaste3

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std ;
const ll N = 3e5 ;
ll n, a, b, c, ans = 1e18 ;
string s ;
set<char> st ;
map<string, bool> mp ;
map<pair<string, string>, ll> dist ;
void deikstra()
{
    for(ll ln = 1 ; ln <= n ; ln++)
        for(ll j = 0 ; j <= s.size() - ln ; j++)
            mp[s.substr(j, ln)] = 1 ;
    set<pair<ll, pair<string, string>>> dxy ;
    dxy.insert({1, {"", ""}}) ;
    dist[{"", ""}] = 1 ;
    while(dxy.size())
    {
        auto abu = *dxy.begin() ;
        ll ds = abu.fi ;
        string x = abu.se.fi, y = abu.se.se ;
        dxy.erase(abu) ;
        if(x == s)
            ans = min(ans, ds) ;
        if(ds > dist[{x, y}])
            continue ;
        for(char i = 'a' ; i <= 'z' ; i++)
            if(mp[x + i] && (!dist[{x + i, y}] || dist[{x + i, y}] > ds + a))
            {
                dist[{x + i, y}] = ds + a ;
                dxy.insert({ds + a, {x + i, y}}) ;
            }
        if(mp[x + y] && (!dist[{x + y, y}] || dist[{x + y, y}] > ds + c))
        {
            dist[{x + y, y}] = ds + c ;
            dxy.insert({ds + c, {x + y, y}}) ;
        }
        if(mp[x] && (!dist[{"", x}] || dist[{"", x}] > ds + b))
        {
            dist[{"", x}] = ds + b ;
            dxy.insert({ds + b, {"", x}}) ;
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n >> s >> a >> b >> c ;
    if(n == 3)
    {
        for(char i : s)
            st.insert(i) ;
        cout << min(a * 3ll, (ll)st.size() * a + b + (3 - (ll)st.size() + 1) * c) ;
        return 0 ;
    }
    deikstra() ;
    cout << ans - 1 ;
    return 0 ;
}
//30
//qazwsxedcrfvtgbyhnujmikolpaaaa
//1
//1
//1

Compilation message (stderr)

copypaste3.cpp: In function 'void deikstra()':
copypaste3.cpp:15:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   15 |         for(ll j = 0 ; j <= s.size() - ln ; j++)
      |                        ~~^~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 0 / 5
• Subtask 3: 14 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 32
• Subtask 6: 0 / 38