oj.uz

Submission #591896

# Submission time Handle Problem Language Result Execution time Memory
591896 2022-07-08T07:30:40 Z Cross_Ratio Copy and Paste 3 (JOI22_copypaste3) C++14
1 / 100
 3000 ms 33948 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
map<string, int> M;
string S;
int D[2505][2505];
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N;
    cin >> S;
    int A, B, C;
    cin >> A >> B >> C;
    int i, j;
    for(i=0;i<=N;i++) {
        for(j=0;j<=N;j++) D[i][j] = INF;
    }
    M[""] = 0;
    int L = B / A;
    for(int len = 1; len <= N; len++) {
        for(i=0;i+len<=N;i++) {
            //(  Copy  ) AAA
            if(len==1) {
                D[i][i+len] = A;
                string o = "";
                o+=S[i];
                M[o] = D[i][i+len];
                continue;
            }
            string s = "";
            D[i][i+len] = len * A;
            D[i][i+len] = min(D[i][i+len],min(D[i][i+len-1],D[i+1][i+len])+A);
            for(j=1;j<=len;j++) {
                s+=S[i+j-1];
                if(j<=L) continue;
                if(!M.count(s)) continue;
                int cnt = i + j;
                for(cnt = i+j; cnt < i + len&&S[cnt]==s[(cnt-(i+j))%j]; cnt++);
                int sz = (cnt-i)/j;
                int val = M[s];
                D[i][i+len] = min(D[i][i+len],B + val + C * sz + A * (len - j * sz));
            }
            M[s] = D[i][i+len];
            //cout << i << " to " << i + len << " : " << D[i][i+len] << '\n';
        }
    }
    cout << D[0][N];
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 3072 ms 33948 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Execution timed out 3072 ms 33948 KB Time limit exceeded
14 Halted 0 ms 0 KB -