Submission #768541

#	Time	Username	Problem	Language	Result	Execution time	Memory
768541		Trumling	Mutating DNA (IOI21_dna)	C++17	0 / 100	1639 ms	1406176 KiB

dna

#include <vector>
#include <string>
using namespace std;

vector<vector<int>> dp;
string a, b;

void init(string a, string b) {
    ::a = a;
    ::b = b;
    
    int n = a.length();
    dp.resize(n, vector<int>(n, 0));
    
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (a[i] != b[j]) {
                dp[i][j] = 1;
                dp[j][i] = 1;
            }
            
            if (i > 0) {
                dp[i][j] += dp[i - 1][j];
                dp[j][i] += dp[j][i - 1];
            }
        }
    }
}

int get_distance(int x, int y) {
    int result = dp[y][y] - (x > 0 ? dp[x - 1][y] : 0);
    
    if (x > 0)
        result -= dp[y][x - 1] - (x > 0 ? dp[x - 1][x - 1] : 0);
    
    return result;
}

• Subtask 1: 0 / 21
• Subtask 2: 0 / 22
• Subtask 3: 0 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16