Cod sursa(job #2991073)

Utilizator razvan.chChelariu Razvan Dumitru razvan.ch Data 8 martie 2023 23:23:29
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <bits/stdc++.h>
#include <vector>

using namespace std;

ifstream f("xormax.in");
ofstream g("xormax.out");

int main() {
    int n;
    f >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        f >> a[i];
    }

    vector<vector<int>> dp(n, vector<int>(n));
    vector<vector<int>> pos(n, vector<int>(n));
    int max_xor = 0, start = 0, stop = 0;

    for (int i = 0; i < n; i++) {
        dp[i][1] = a[i];
        pos[i][1] = i;

        for (int j = 2; j <= i+1; j++) {
            dp[i][j] = max(dp[i-1][j], a[i] xor dp[i-1][j-1]);
            if (dp[i][j] > max_xor) {
                max_xor = dp[i][j];
                start = pos[i][j] = i-j+1;
                stop = i;
            } else if (dp[i][j] == max_xor) {
                int new_stop = i;
                if (new_stop < stop) {
                    stop = pos[i][j] = new_stop;
                    start = pos[i][j] = i-j+1;
                } else if (new_stop == stop) {
                    int len1 = stop - start + 1;
                    int len2 = j;
                    if (len2 < len1) {
                        start = pos[i][j] = i-j+1;
                    }
                }
            } else {
                pos[i][j] = pos[i-1][j];
            }
        }
    }

    g << max_xor << " " << start << " " << stop << endl;

    return 0;
}