Submission #447722

#	Time	Username	Problem	Language	Result	Execution time	Memory
447722		RaresFelix	Exam (eJOI20_exam)	C++17	0 / 100	8 ms	9292 KiB

exam

#include <bits/stdc++.h>
#define MAXN 107171
#define MAXD 5071
#define INF 1000000000
#define fi cin
#define fo cout
using namespace std;
//ifstream fi("a.in");
//ofstream fo("a.out");
int n, A[MAXN], B[MAXN], rez;
void read_and_norm()
{
    int nr = 0;
    fi >> n;
    map<int, int> NORMAP;
    vector<int> R;
    for(int i = 1; i <= n; ++i)
    {
        fi >> A[i];
        R.push_back(A[i]);
    }
    for(int i = 1; i <= n; ++i)
    {
        fi >> B[i];
        R.push_back(B[i]);
    }
    sort(R.begin(), R.end());
    for(auto it : R)
        if(!NORMAP.count(it))
            NORMAP[it] = ++nr;
    for(int i = 1; i <= n; ++i)
        A[i] = NORMAP[A[i]];
    for(int i = 1; i <= n; ++i)
        B[i] = NORMAP[B[i]];

}

void special()
{
    // va subtask-urile 2 si 4
    int beg = 1;
    for(int i = 1; i < n; ++i)
        if(B[i] != B[i+1]){
            beg = 0;
            break;
        }
    if(beg) // subtask 2
    {
        int lsecv = 0, aparb = 0;
        for(int i = 1; i <= n; ++i){
            if(A[i] > B[1]){
                if(aparb) rez += lsecv;
                lsecv = aparb = 0;
            } else if(A[i] == B[1])
                aparb = 1;
            else
                ++lsecv;
        }
    }
    else ///subtask 4
    {
        //chiar nu am vreo nicio idee acum... revin main tarziu
        rez = -1;
    }
}

    int DP[2][MAXD][2*MAXD]; //tip, poz, valb
void dynamic()
{
    set<int> SVB;
    for(int i = 1; i <= n; ++i)
        SVB.insert(A[i]);
    for(int i = 1; i <= n; ++i)
        SVB.insert(B[i]);
    vector<int> VB;
    for(auto it : SVB)
        VB.push_back(it);
//    unordered_map<int, int> DP[2][MAXD]; //tip, poz, valb
    for(auto it : VB)
        DP[0][0][it] = -INF;
    int maxim_anterior = 0;
    for(int i = 1; i <= n; ++i) { // pozitie
        maxim_anterior = 0;
        for(auto it : VB)
            maxim_anterior = max(maxim_anterior, DP[0][i-1][it]);
        for(auto it : VB) { // ultima valoare
            /// chiar e pus
            DP[0][i][it] = DP[0][i-1][it];
            if(it == A[i]){
                DP[0][i][it] = max(DP[0][i][it], maxim_anterior); ///chiar apare un element
                DP[0][i][it] += DP[1][i-1][it]; /// dispar promisiunile
                if(it == B[i])
                    DP[0][i][it]++;
            } else {
                DP[1][i][it] = DP[1][i-1][it];
                if(it == B[i]) /// mai se adauga ceva la promisiune
                    DP[1][i][it]++;
            }
            if(A[i] > it){
                DP[0][i][it] = -INF;
                DP[1][i][it] = maxim_anterior; /// nu se poate
            }
        }
    }
    for(auto it : VB)
        rez = max(rez, DP[0][n][it]);
}

int main()
{
    read_and_norm();
    if(n > 5000)
        special();
    else
        dynamic();
    fo << rez << "\n";
    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22