oj.uz

Submission #257077

# Submission time Handle Problem Language Result Execution time Memory
257077 2020-08-03T15:15:49 Z zoooma13 Necklace (Subtask 1-3) (BOI19_necklace1) C++14
17 / 85
 302 ms 36088 KB 
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 3003

int n ,m;
string s ,t;

int com[MAX_N][MAX_N];
int go(int i ,int j){
    if(i == n || j == m)
        return 0;
    int&ret = com[i][j];
    if(~ret)
        return ret;
    go(i+1 ,j);
    go(i ,j+1);
    if(s[i] == t[j])
        return ret = 1 + go(i+1 ,j+1);
    return ret = 0;
}

int main()
{
    cin >> s >> t; n = s.size() ,m = t.size();
    memset(com ,-1 ,sizeof com);
    go(0 ,0);
    pair<int ,pair <int ,int>> ans;
    for(int i=0; i<n; i++)
    for(int j=0; j<m; j++)
        ans = max(ans ,make_pair(com[i][j] ,make_pair(i ,j)));
    reverse(t.begin() ,t.end());
    memset(com ,-1 ,sizeof com);
    go(0 ,0);
    for(int i=0; i<n; i++)
    for(int j=0; j<m; j++)
        ans = max(ans ,make_pair(com[i][j] ,make_pair(i ,m-j-com[i][j])));
    cout << ans.first << endl;
    cout << ans.second.first << ' ' << ans.second.second << endl;
}

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 27 ms 35584 KB Output is partially correct
2 Partially correct 27 ms 35584 KB Output is partially correct
3 Partially correct 26 ms 35584 KB Output is partially correct
4 Partially correct 27 ms 35584 KB Output is partially correct
5 Partially correct 25 ms 35584 KB Output is partially correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 27 ms 35584 KB Output is partially correct
2 Partially correct 27 ms 35584 KB Output is partially correct
3 Partially correct 26 ms 35584 KB Output is partially correct
4 Partially correct 27 ms 35584 KB Output is partially correct
5 Partially correct 25 ms 35584 KB Output is partially correct
6 Partially correct 29 ms 35712 KB Output is partially correct
7 Partially correct 32 ms 35708 KB Output is partially correct
8 Partially correct 28 ms 35712 KB Output is partially correct
9 Partially correct 32 ms 35712 KB Output is partially correct
10 Partially correct 32 ms 35704 KB Output is partially correct
11 Partially correct 31 ms 35704 KB Output is partially correct
12 Partially correct 27 ms 35712 KB Output is partially correct

Subtask #3
8.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 27 ms 35584 KB Output is partially correct
2 Partially correct 27 ms 35584 KB Output is partially correct
3 Partially correct 26 ms 35584 KB Output is partially correct
4 Partially correct 27 ms 35584 KB Output is partially correct
5 Partially correct 25 ms 35584 KB Output is partially correct
6 Partially correct 29 ms 35712 KB Output is partially correct
7 Partially correct 32 ms 35708 KB Output is partially correct
8 Partially correct 28 ms 35712 KB Output is partially correct
9 Partially correct 32 ms 35712 KB Output is partially correct
10 Partially correct 32 ms 35704 KB Output is partially correct
11 Partially correct 31 ms 35704 KB Output is partially correct
12 Partially correct 27 ms 35712 KB Output is partially correct
13 Partially correct 302 ms 36088 KB Output is partially correct
14 Partially correct 276 ms 36088 KB Output is partially correct
15 Partially correct 299 ms 35968 KB Output is partially correct
16 Partially correct 282 ms 36088 KB Output is partially correct
17 Partially correct 260 ms 36036 KB Output is partially correct
18 Partially correct 272 ms 35968 KB Output is partially correct
19 Partially correct 281 ms 35968 KB Output is partially correct
20 Partially correct 278 ms 36088 KB Output is partially correct
21 Partially correct 278 ms 35968 KB Output is partially correct