oj.uz

Submission #46390

# Submission time Handle Problem Language Result Execution time Memory
46390 2018-04-20T05:12:46 Z ffresh 즐거운 채소 기르기 (JOI14_growing) C++17
0 / 100
 4 ms 712 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];
            memset(pen,0,sizeof(pen));
            update(ar[i],1);
            
            for(int j=i-1;j>=1;--j){
                update(ar[j],1);
                dp[j] += query(ar[i]-1);
            }
        }
        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:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&ar[i]);
         ~~~~~^~~~~~~~~~~~~
growing.cpp:72:17: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 if(j<ind){
                 ^~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 536 KB Output is correct
2 Correct 2 ms 672 KB Output is correct
3 Correct 2 ms 672 KB Output is correct
4 Incorrect 2 ms 676 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 712 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 4 ms 712 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -