oj.uz

Submission #771620

# Submission time Handle Problem Language Result Execution time Memory
771620 2023-07-03T07:28:24 Z PoonYaPat Copy and Paste 3 (JOI22_copypaste3) C++14
5 / 100
 682 ms 49532 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;

int n;
string s;
ll dp[2505][2505],nxt[2505],a,b,c,qs[2505],mul[2505],inv;
const ll mod=1e15+7, hs=5e11;

ll power(ll a, ll n) {
    ll ans=1;
    while (n) {
        if (n%2==1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        n/=2;
    }
    return ans;
}

ll hsh(int l, int r) {
    return ((qs[r]-qs[l-1]+mod)%mod * power(inv,l-1))%mod;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    for (int i=1; i<=2500; ++i) for (int j=1; j<=2500; ++j) dp[i][j]=1e18;
    cin>>n>>s>>a>>b>>c;
    s=" "+s;

    mul[0]=1;
    inv=power(hs,mod-2);
    for (int i=1; i<n; ++i) mul[i]=(mul[i-1]*hs)%mod;
    for (int i=1; i<=n; ++i) qs[i]=(qs[i-1]+mul[i-1]*(s[i]-'a'))%mod;

    for (ll siz=1; siz<=n;  ++siz) {

        //find next
        map<ll,int> bef;
        queue<pii> q;
        memset(nxt,0,sizeof(nxt));

        for (int l=n-siz+1; l>=1; --l) {
            int r=l+siz-1;
            while (q.size()>=siz)  {
                bef[q.front().first]=q.front().second;
                q.pop();
            }
            nxt[l]=bef[hsh(l,r)];
            q.push(pii(hsh(l,r),l));
        }

        //find dp
        for (ll l=1; l+siz-1<=n; ++l) {
            ll r=l+siz-1;
            if (siz==1) dp[l][r]=a;
            else dp[l][r]=min({dp[l][r],dp[l][r-1]+a,dp[l+1][r]+a});

            ll nl=l,nr=r,cnt=0;
            while (nl) {
                ++cnt;
                dp[l][nr]=min(dp[l][nr],dp[l][r]+ ((nr-l+1)-siz*cnt)*a+b+c*cnt);
                nl=nxt[nl];
                nr=nl+siz-1;
            }
        }
    }
    cout<<dp[1][n];
}

Compilation message

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:45:28: warning: comparison of integer expressions of different signedness: 'std::queue<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   45 |             while (q.size()>=siz)  {
      |                    ~~~~~~~~^~~~~

Subtask #1
0 / 1.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 49312 KB Output is correct
2 Correct 17 ms 49292 KB Output is correct
3 Correct 311 ms 49404 KB Output is correct
4 Correct 403 ms 49484 KB Output is correct
5 Correct 448 ms 49408 KB Output is correct
6 Correct 584 ms 49420 KB Output is correct
7 Correct 682 ms 49528 KB Output is correct
8 Correct 678 ms 49420 KB Output is correct
9 Correct 662 ms 49532 KB Output is correct
10 Correct 18 ms 49280 KB Output is correct
11 Correct 21 ms 49252 KB Output is correct
12 Correct 19 ms 49352 KB Output is correct
13 Correct 21 ms 49344 KB Output is correct
14 Correct 19 ms 49368 KB Output is correct
15 Correct 21 ms 49368 KB Output is correct
16 Correct 18 ms 49364 KB Output is correct
17 Correct 18 ms 49340 KB Output is correct

Subtask #3
0 / 14.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 32.0

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

Subtask #6
0 / 38.0

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