oj.uz

Submission #46388

# Submission time Handle Problem Language Result Execution time Memory
46388 2018-04-20T04:58:41 Z ffresh 즐거운 채소 기르기 (JOI14_growing) C++17
0 / 100
 5 ms 976 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Incorrect 2 ms 768 KB Output isn't correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5 ms 976 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -