oj.uz

Submission #580555

# Submission time Handle Problem Language Result Execution time Memory
580555 2022-06-21T12:33:40 Z CyberSleeper Copy and Paste 3 (JOI22_copypaste3) C++17
0 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>
#define fastio      ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define debug(x)    cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl
#define all(x)      x.begin(), x.end()
#define fi          first
#define se          second
#define mp          make_pair
#define pb          push_back
#define ll          long long
#define ull         unsigned long long
#define pll         pair<ll, ll>
#define pii         pair<ll, ll>
#define ld          long double
#define nl          '\n'
#define tb          '\t'
#define sp          ' '
#define sqr(x)      (x)*(x)
#define arr3        array<ll, 3>
using namespace std;

const ll MX=2502, MOD1=1000000000000027, MOD2=1000000123, BLOCK=160, INF=1e9+7, LG=62, key1=177013, key2=353707;
const ll INFF=1000000000000000004;
const ld ERR=1e-6, pi=3.14159265358979323846;

ll A, B, C, N, hsh[MX][MX], DP[MX][MX];
string S;

int main(){
    fastio;
    cin >> A >> B >> C >> S;
    N=S.size();
    if(N==1){
        cout << A << nl;
        return 0;
    }
    for(ll i=0; i<=N; i++){
        for(ll j=0; j<=N; j++)
            DP[i][j]=INFF;
    }
    for(ll i=0; i<N; i++){
        for(ll j=i; j<N; j++){
            (hsh[i][j]=hsh[i][j-1]*key1+S[j])%=MOD1;
        }
        DP[i][i]=A;
    }
    for(ll len=0; len<N; len++){
        vector<pll> sub;
        for(ll le=0, ri=le+len; ri<N; le++, ri++){
            DP[le][ri]=min({DP[le][ri], DP[le+1][ri]+A, DP[le][ri-1]+A});
        }
        for(ll i=0; i+len<N; i++){
            sub.pb({hsh[i][i+len], i});
        }
        sort(all(sub));
        vector<ll> nxt(N, -1);
        for(ll i=0; i+len<N; i++){
            ll loc=lower_bound(all(sub), mp(hsh[i][i+len], i+len+1))-sub.begin();
            if(loc<sub.size() && sub[loc].fi==hsh[i][i+len])
                nxt[i]=sub[loc].se;
        }
        for(ll le=0; le+len<N; le++){
            ll idx=nxt[le], cnt=2, ri;
            while(idx!=-1){
                ri=idx+len;
                DP[le][ri]=min(DP[le][ri], DP[le][le+len]+B+C*cnt+A*(ri-le+1-cnt*(len+1)));
                cnt++;
                idx=nxt[idx];
            }
        }
    }
    cout << DP[0][N-1] << nl;
}

Compilation message

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:58:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             if(loc<sub.size() && sub[loc].fi==hsh[i][i+len])
      |                ~~~^~~~~~~~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -