답안 #997378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
997378	2024-06-12T08:05:44 Z	onbert	Copy and Paste 3 (JOI22_copypaste3)	C++17	6 / 100	719 ms	98504 KB

copypaste3

//bruhed
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, A, B, C;
    string s;
    cin >> n >> s >> A >> B >> C;
    s = '.' + s;
    int id[n+1][n+2], cost[n+1][n+2];
    for (int i=0;i<=n;i++) for (int j=1;j<=n+1;j++) id[i][j] = -1, cost[i][j] = INF;
    for (int i=1;i<=n;i++) cost[1][i] = A;

    for (int sz=1;sz<=n;sz++) {
        // cout << sz << endl;
        if (sz!=1) {
            for (int i=1;i<=n-sz+1;i++) {
                cost[sz][i] = min(cost[sz-1][i] + A, cost[sz][i]);
                cost[sz][i] = min(cost[sz-1][i+1] + A, cost[sz][i]);
                // cout << cost[sz][i] << " ";
            }
        }
        // cout << endl;
        vector<pair<char,int>> v = {{' ', -1}};
        for (int i=1;i<=n-sz+1;i++) v.push_back({s[i], id[sz-1][i+1]});
        sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
        // for (auto [x, y]:v) cout << x << " " << y << endl;
        int m = v.size() - 1;
        vector<int> mem[m+1];
        for (int i=1;i<=n-sz+1;i++) {
            id[sz][i] = lower_bound(v.begin(), v.end(), make_pair(s[i], id[sz-1][i+1])) - v.begin();
            mem[id[sz][i]].push_back(i);
        }
        for (int i=1;i<=m;i++) mem[i].push_back(INF);
        for (int i=1;i<=m;i++) {
            for (int J=0;J<(int)mem[i].size()-1;J++) {
                int j = mem[i][J];
                for (int cnt = 2; ;cnt++) {
                    if (J+cnt-1 > (int)mem[i].size()-1) break;
                    int nxt = max(*lower_bound(mem[i].begin(), mem[i].end(), j + (cnt-1)*sz), mem[i][J+cnt-1]);
                    if (nxt==INF) break;
                    int SZ = nxt + sz - j;
                    int val = (SZ - cnt*sz)*A + C*cnt + cost[sz][j] + B;
                    // if (SZ == 3 && j == 4) cout << "test " << cnt << " " << val << endl;
                    cost[SZ][j] = min(val, cost[SZ][j]);
                }
            }
        }
    }
    cout << cost[n][1] << endl;
}

Subtask #1
1.0 / 1.0

#	결과	메모리	Grader output
1	Correct	600 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	456 KB	Output is correct
9	Correct	348 KB	Output is correct
10	Correct	348 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	308 ms	52668 KB	Output is correct
4	Correct	363 ms	61780 KB	Output is correct
5	Correct	452 ms	71992 KB	Output is correct
6	Correct	565 ms	84048 KB	Output is correct
7	Correct	694 ms	98504 KB	Output is correct
8	Correct	719 ms	98464 KB	Output is correct
9	Correct	706 ms	98404 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	456 KB	Output is correct
16	Correct	1 ms	344 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct

Subtask #3
0 / 14.0

#	결과	메모리	Grader output
1	Correct	600 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	456 KB	Output is correct
9	Correct	348 KB	Output is correct
10	Correct	348 KB	Output is correct
11	Correct	348 KB	Output is correct
12	Correct	604 KB	Output is correct
13	Incorrect	348 KB	Output isn't correct
14	Halted	0 KB	-

Subtask #4
0 / 10.0

#	결과	메모리	Grader output
1	Correct	600 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	456 KB	Output is correct
9	Correct	348 KB	Output is correct
10	Correct	348 KB	Output is correct
11	Correct	348 KB	Output is correct
12	Correct	604 KB	Output is correct
13	Incorrect	348 KB	Output isn't correct
14	Halted	0 KB	-

Subtask #5
0 / 32.0

#	결과	메모리	Grader output
1	Correct	600 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	456 KB	Output is correct
9	Correct	348 KB	Output is correct
10	Correct	348 KB	Output is correct
11	Correct	348 KB	Output is correct
12	Correct	604 KB	Output is correct
13	Incorrect	348 KB	Output isn't correct
14	Halted	0 KB	-

Subtask #6
0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	456 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	308 ms	52668 KB	Output is correct
14	Correct	363 ms	61780 KB	Output is correct
15	Correct	452 ms	71992 KB	Output is correct
16	Correct	565 ms	84048 KB	Output is correct
17	Correct	694 ms	98504 KB	Output is correct
18	Correct	719 ms	98464 KB	Output is correct
19	Correct	706 ms	98404 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	456 KB	Output is correct
26	Correct	1 ms	344 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Correct	0 ms	604 KB	Output is correct
30	Incorrect	0 ms	348 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

답안 #997378

Compilation message

Subtask #1 1.0 / 1.0

Subtask #2 5.0 / 5.0

Subtask #3 0 / 14.0

Subtask #4 0 / 10.0

Subtask #5 0 / 32.0

Subtask #6 0 / 38.0

Subtask #1
1.0 / 1.0

Subtask #2
5.0 / 5.0

Subtask #3
0 / 14.0

Subtask #4
0 / 10.0

Subtask #5
0 / 32.0

Subtask #6
0 / 38.0