Submission #770385

#	Time	Username	Problem	Language	Result	Execution time	Memory
770385		ttamx	Copy and Paste 3 (JOI22_copypaste3)	C++14	5 / 100	496 ms	120168 KiB

copypaste3

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef tuple<ll,int,int> t3;

const int N=2505;
const int mod=1e9+7;

int n;
ll a,b,c;
string s;
ll dp[N][N];
bool vis[N][N];
ll hsh[N];

ll sub(int l,int r){
    return (hsh[r]-hsh[l-1]+mod)%mod;
}

priority_queue<t3,vector<t3>,greater<t3>> pq;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> s >> a >> b >> c;
    s=" "+s;
    for(int i=1;i<=n;i++)hsh[i]=(hsh[i-1]*29%mod+s[i]-'a')%mod;
    for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)dp[i][j]=1e18;
    dp[0][0]=0;
    pq.emplace(0,0,0);
    while(!pq.empty()){
        auto [d,i,j]=pq.top();
        pq.pop();
        if(vis[i][j])continue;
        vis[i][j]=true;
        if(i==n){
            cout << d;
            return 0;
        }
        if(i+1<=n&&d+a<dp[i+1][j]){
            dp[i+1][j]=d+a;
            pq.emplace(dp[i+1][j],i+1,j);
        }
        if(d+b<dp[0][i]){
            dp[0][i]=d+b;
            pq.emplace(dp[0][i],0,i);
        }
        if(i+j<=n&&sub(1,j)==sub(i+1,i+j)){
            if(d+c<dp[i+j][j]){
                dp[i+j][j]=d+c;
                pq.emplace(dp[i+j][j],i+j,j);
            }
        }
    }
}

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:33:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |         auto [d,i,j]=pq.top();
      |              ^

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