oj.uz

Submission #937819

# Submission time Handle Problem Language Result Execution time Memory
937819 2024-03-04T14:27:25 Z Andrey Group Photo (JOI21_ho_t3) C++14
0 / 100
 1 ms 604 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -