Submission #421813

#	Time	Username	Problem	Language	Result	Execution time	Memory
421813		Harry464	Group Photo (JOI21_ho_t3)	C++14	100 / 100	665 ms	492 KiB

Main

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long ll;

class fenw{

   vector <ll> bit;
   ll vel;

   public:

   fenw(ll a){

     vel = a;
     bit.resize(a+1);

   }

   void upd(ll x, ll val){

      while (x <= vel){

        bit[x] += val;
        x += x&-x;

      }

   }

   ll sum(ll x){

     ll s = 0;

     while (x > 0){

        s += bit[x];
        x -= x&-x;

     }

     return s;

   }


};

int main()
{
    ll n;
    cin >> n;

    vector <ll> a(n);

    for (int i = 0; i < n; i++)
        cin >> a[i];

    fenw bit1(n);

    vector <ll> poz(n+1);

    for (int i = 0; i < n; i++)
        poz[a[i]] = i + 1;

    vector <ll> dp(n+1, 1000000000000000000);
    dp[0] = 0;

    for (int i = 0; i < n; i++){

        fenw inv(n);

        ll brin = 0;

        ll dodatne_poz = 0;
        ll trenutne_poz = 0;


        for (int j = i + 1; j <= n; j++){

          trenutne_poz += j;
          dodatne_poz += poz[j] + bit1.sum(n) - bit1.sum(poz[j]);
          //cout << trenutne_poz << " " << dodatne_poz << endl;
          brin += inv.sum(n) - inv.sum(poz[j]);
          //cout << brin << endl;
          inv.upd(poz[j], 1);

          ll tren = dp[i] + dodatne_poz - trenutne_poz;
          ll manji = min(brin, ((j-i)*(j-i-1))/2 - brin);
          tren += manji;
          dp[j] = min(dp[j], tren);


        }

        bit1.upd(poz[i+1], 1);

    }

    cout << dp[n];

}

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