Submission #632193

#	Time	Username	Problem	Language	Result	Execution time	Memory
632193		Ooops_sorry	Group Photo (JOI21_ho_t3)	C++14	100 / 100	420 ms	420 KiB

Main

#include<bits/stdc++.h>

using namespace std;

mt19937 rnd(51);

#define ll long long
#define pb push_back
#define ld long double

const int INF = 1e9;

struct Fenwick {
    vector<int> t;
    Fenwick(int n) {
        t.resize(n);
    }
    void inc(int i, int d) {
        for (; i < t.size(); i = (i | (i + 1))) {
            t[i] += d;
        }
    }
    int get(int r) {
        int ans = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1) {
            ans += t[r];
        }
        return ans;
    }
};

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n), dp(n + 1, INF), pos(n);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    //dp[i] - answer for the prefix
    for (int i = 0; i < n; i++) {
        int ind = 0;
        Fenwick t(n - i);
        for (int j = 0; j < n; j++) {
            if (a[j] < i) continue;
            pos[a[j] - i] = ind++;
        }
        int add = 0;
        for (int j = 0; j < n - i; j++) {
            add += pos[j] - j;
            add += t.get(pos[j]);
            dp[j + i + 1] = min(dp[j + i + 1], dp[i] + add);
            t.inc(pos[j], 1);
        }
    }
    cout << dp[n] << endl;
    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void Fenwick::inc(int, int)':
Main.cpp:19:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         for (; i < t.size(); i = (i | (i + 1))) {
      |                ~~^~~~~~~~~~

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