Submission #830507

#	Time	Username	Problem	Language	Result	Execution time	Memory
830507		RaresFelix	Group Photo (JOI21_ho_t3)	C++17	100 / 100	817 ms	468 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MN = 5001;
const int INF = 1e9;

struct BIT {
    vector<int> S;
    BIT(int n) : S(n) {}
    void update(int p, int v) {
        while(p < S.size()) {
            S[p] += v;
            p += p & -p;
        }
    }
    int query(int p) {
        int re = 0;
        while(p) {
            re += S[p];
            p -= p & -p;
        }
        return re;
    }
    int query(int st, int dr) {
        return (st <= 0 ? query(dr) : (query(dr) - query(st - 1)));
    }
    void clear() {
        fill(S.begin(), S.end(), 0);
    }
    void afis(int n, string mes) {
        cout << mes;
        for(int i = 1; i <= n; ++i)
            cout << query(i, i) << " ";
        cout << "\n";
    }
};

BIT Activ(MN), Inv(MN), InSol(MN);
int n, A[MN], DP[MN], Rank[MN];

int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
         cin >> A[i];
         Rank[A[i]] = i;
    }
    DP[0] = 0;
    for(int i = 1; i <= n; ++i) {
        DP[i] = INF;
    }
    for(int i = 0; i <= n; ++i) {
        ///adaug asupra solutiei de lungime i
        for(int j = 1; j <= n; ++j) {
            Activ.update(j, 1);
        }
        for(int j = 1; j <= i; ++j)
            Activ.update(Rank[j], -1); /// luate  
        int cost = 0;
        for(int j = i + 1; j <= n; ++j) {
            cost += Activ.query(Rank[j] - 1) - InSol.query(Rank[j], n);
            cost += Inv.query(Rank[j] - 1);
            InSol.update(Rank[j], 1);
        //    printf("Din %d in %d\n", i, j);
        //    Inv.afis(n, "Inv: ");
        //    Activ.afis(n, "Activ: ");
        //    InSol.afis(n, "InSol: ");
        //    printf("costul e %d\n\n", cost);
            Inv.update(Rank[j], 1); 
            Activ.update(Rank[j], -1);
            DP[j] = min(DP[j], DP[i] + cost);
        
        }
        Activ.clear();
        Inv.clear();
        InSol.clear();
    }
    cout << DP[n] << "\n";
    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void BIT::update(int, int)':
Main.cpp:12:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |         while(p < S.size()) {
      |               ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 32 / 32
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36