Submission #937819

#	Time	Username	Problem	Language	Result	Execution time	Memory
937819		Andrey	Group Photo (JOI21_ho_t3)	C++14	0 / 100	1 ms	604 KiB

Main

#include <bits/stdc++.h>
using namespace std;

vector<int> dp(5001,INT_MAX);
vector<int> idk(5001);
int n;

void upd(int a, int x) {
    while(a <= n) {
        idk[a]+=x;
        a+=(a&(-a));
    }
}

int calc(int a) {
    int c = 0,sb = 0;
    for(int i = 12; i >= 0; i--) {
        if(c+(1 << i) <= a) {
            c+=(1 << i);
            sb+=idk[c];
        }
    }
    return sb;
}

int dude(vector<int> haha) {
    int n = haha.size()-1;
    vector<int> p(n+1);
    for(int i = 1; i <= n; i++) {
        p[haha[i]] = i;
    }
    int br = 0;
    for(int i = 0; i <= n; i++) {
        idk[i] = 0;
    }
    for(int i = n; i >= 1; i--) {
        br+=n-p[i];
        br-=calc(p[i]);
        upd(p[i],1);
        dp[n] = min(dp[n],dp[i-1]+br);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    dp[0] = 0;
    vector<int> haha(n+1);
    for(int i = 1; i <= n; i++) {
        cin >> haha[i];
    }
    for(int i = 1; i <= n; i++) {
        vector<int> bruh(1);
        for(int j = 1; j <= n; j++) {
            if(haha[j] <= i) {
                bruh.push_back(haha[j]);
            }
        }
        dude(bruh);
    }
    cout << dp[n];
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int dude(std::vector<int>)':
Main.cpp:42:1: warning: no return statement in function returning non-void [-Wreturn-type]
   42 | }
      | ^

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