Submission #46388

#	Time	Username	Problem	Language	Result	Execution time	Memory
46388		ffresh	즐거운 채소 기르기 (JOI14_growing)	C++17	0 / 100	5 ms	976 KiB

growing

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 5005;

int dp[N];

int pen[N];

int ar[N],temp[N];

int find(int x,int n){
    int l = 1,r = n,mid;
    while(l<r){
        mid = (l+r+1)/2;
        if(x<temp[mid])
            r= mid-1;
        else
            l = mid;
    }
    return l;
}   
    
void update(int ind,int add){
    while(ind<N)
        pen[ind]+=add,ind +=ind&(-ind);
}   
int query(int ind){
    int ret=0;
    while(ind)
        ret += pen[ind],ind = ind&(ind-1);
    return ret;
}   
int main(){

    int n;
    cin>>n;
    for(int i=1;i<=n;++i){
        scanf("%d",&ar[i]);
        temp[i]= ar[i];
    }
    sort(temp+1,temp+n+1);

    for(int i=1;i<=n;++i)ar[i]= find(ar[i],n);

    int maxi =0, ind;
    
    for(int i=1;i<=n;++i){
        if(maxi<=ar[i]){
            maxi = ar[i];
            ind = i;
            dp[i]= dp[i-1];
            for(int j=1;j<=i-1;++j){
                dp[j]= dp[j] + i-j;
            }
        }   
        else{
            dp[i]= dp[i-1];
            memset(pen,0,sizeof(pen));
            update(ar[i],1);
            for(int j=i-1;j>=1;--j){
                
                if(j<ind){
                    update(ar[j],1);
                }
                dp[j] += query(ar[i]-1);
                if(ind<=j){
                    update(ar[j],1);
                }
            }   
            dp[i] +=  i- query(ar[i]);
        }   
    }
    int ret = 1e9;
    for(int i=1;i<=n;++i)ret= min(ret,dp[i]);
    cout<<ret<<endl;
    return 0;
}

Compilation message (stderr)

growing.cpp: In function 'int main()':
growing.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&ar[i]);
         ~~~~~^~~~~~~~~~~~~
growing.cpp:70:17: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 if(ind<=j){
                 ^~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 15
• Subtask 4: 0 / 55