Submission #973411

#	Time	Username	Problem	Language	Result	Execution time	Memory
973411		modwwe	Group Photo (JOI21_ho_t3)	C++17	100 / 100	327 ms	756 KiB

Main

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define int long long
//#define ll long long
#define down cout<<'\n';
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void ngha();
const int mod2=1e9+7;
const int  mod1=998244353;
struct ib {
    int a;
    int b;
};
struct icd {
    int a,b;
};
struct ic {
    int a,b,c;
};
struct id {
    int a,b,c,d;
};
struct ie {
    int a,b,c, d,e;

};
int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l;
int  i,s10,s12;
int el=29;
main() {
//#ifndef ONLINE_JUDGE
    /// fin(task),fou(task);
//#endif
//NHP
//modwwe
    //  cin>>res;
    ngha(),down
    checktime
}
int bit[5001];
int bit2[5001];
int a[5001];
void upd(int x) {
    for(x; x; x-=x&-x)bit[x]++;
}
void upd2(int x) {
    for(x; x<=n; x+=x&-x)bit2[x]++;
}
int get(int x) {
    int ss=0;
    for(x; x<=n; x+=x&-x) ss+=bit[x];
    return ss;
}
int get2(int x) {
    int ss=0;
    for(x; x; x-=x&-x)ss+=bit2[x];
    return ss;
}
int dp[5001];
void ngha() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>l;
        a[l]=i;
    }
    memset(dp,0x3f,sizeof dp);
    dp[0]=0;
    for(int i=0; i<=n-1; i++) {
        memset(bit2,0,sizeof bit2);
        s2=dp[i];
        for(int j=i+1; j<=n; j++) {
            s2+=get(a[j])+get2(a[j]);
            dp[j]=min(s2,dp[j]);
            upd2(a[j]);

        }
        upd(a[i+1]);
    }
    cout<<dp[n];
}

Compilation message (stderr)

Main.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main() {
      | ^~~~
Main.cpp: In function 'void upd(long long int)':
Main.cpp:54:9: warning: statement has no effect [-Wunused-value]
   54 |     for(x; x; x-=x&-x)bit[x]++;
      |         ^
Main.cpp: In function 'void upd2(long long int)':
Main.cpp:57:9: warning: statement has no effect [-Wunused-value]
   57 |     for(x; x<=n; x+=x&-x)bit2[x]++;
      |         ^
Main.cpp: In function 'long long int get(long long int)':
Main.cpp:61:9: warning: statement has no effect [-Wunused-value]
   61 |     for(x; x<=n; x+=x&-x) ss+=bit[x];
      |         ^
Main.cpp: In function 'long long int get2(long long int)':
Main.cpp:66:9: warning: statement has no effect [-Wunused-value]
   66 |     for(x; x; x-=x&-x)ss+=bit2[x];
      |         ^

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