Submission #550746

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
550746	2022-04-19 01:52:26	lkh3happy	Copy and Paste 3 (JOI22_copypaste3)	C++14	62 / 100	1485 ms	57748 KiB

copypaste3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
char S[2501];
long long dp[2501][2501], mod=1e9+7, h[2501], mul=1000003, nex[2501][2501];
int main(){
    h[0]=1;
    for(int i=1;i<2501;i++) h[i]=h[i-1]*mul%mod;
    int n;
    long long a, b, c;
    scanf("%d%s%lld%lld%lld", &n, S, &a, &b, &c);
    for(int i=0;i<=n;i++) for(int j=i;j<=n;j++) dp[i][j]=(j-i+1)*a+b;
    for(int l=1;l<=n;l++){
        map<long long, long long> m;
        queue<long long> q[2501];
        long long hc=0, cnt=0;
        for(int i=0;i<l;i++) hc=(hc*mul+(S[i]-'a'))%mod;
        m[hc]=++cnt;
        q[cnt].push(0);
        for(int i=l;i<n;i++){
            hc=(hc*mul-h[l]*(S[i-l]-'a')+(S[i]-'a'))%mod;
            if(m.find(hc)==m.end()) m[hc]=++cnt;
            long long x=m[hc];
            while(!q[x].empty() && q[x].front()+l-1<i-l+1) nex[q[x].front()][q[x].front()+l-1]=i-l-q[x].front()+1, q[x].pop();
            q[x].push(i-l+1);
        }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%d%s%lld%lld%lld", &n, S, &a, &b, &c);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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