oj.uz

Submission #46338

# Submission time Handle Problem Language Result Execution time Memory
46338 2018-04-19T12:58:52 Z ffresh 즐거운 채소 기르기 (JOI14_growing) C++17
30 / 100
 1000 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 20;

int val[N];

int dp[N][1<<N][2];

int check(int front,int cur,int inc){
    if(inc==0)return front<=cur;
    return front>=cur;
}
int solve(int prev,int bit,int inc,int lim,int n){

    int &ret= dp[prev][bit][inc];
    if(bit==lim)ret = 0;
    if(ret!=-1)return ret;

    ret = 1e9;

    if(inc==0)
        ret= solve(prev,bit,1,lim,n);

    int front = val[prev];
    if(bit==0)front = -1e9;
    int fr= 0;

    for(int i=0;i<n;++i){
        if(!(bit&(1<<i)))  {
            if(check(front,val[i],inc))
                ret = min(ret, fr + solve(i,bit|(1<<i),inc,lim,n) );
            ++fr;
        }
    }
    return ret;
}

int main(){
    //freopen("input.txt","r",stdin);

    int n;
    cin>>n;
    for(int i=0;i<n;++i)scanf("%d",&val[i]);
    memset(dp,-1,sizeof(dp));
    int lim = (1<<n)-1;
    printf("%d\n",solve(0,0,0,lim,n));

    return 0;
}

Compilation message

growing.cpp: In function 'int main()':
growing.cpp:47:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0;i<n;++i)scanf("%d",&val[i]);
                         ~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 164456 KB Output is correct
2 Correct 135 ms 164584 KB Output is correct
3 Correct 143 ms 164584 KB Output is correct
4 Correct 119 ms 164588 KB Output is correct
5 Correct 137 ms 164628 KB Output is correct
6 Correct 119 ms 164704 KB Output is correct
7 Correct 120 ms 164740 KB Output is correct
8 Correct 118 ms 164748 KB Output is correct
9 Correct 121 ms 164752 KB Output is correct
10 Correct 132 ms 164792 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 164812 KB Output is correct
2 Correct 136 ms 164944 KB Output is correct
3 Correct 127 ms 164944 KB Output is correct
4 Correct 195 ms 164956 KB Output is correct
5 Correct 295 ms 164988 KB Output is correct
6 Correct 154 ms 164988 KB Output is correct
7 Correct 191 ms 164988 KB Output is correct
8 Correct 166 ms 164988 KB Output is correct
9 Correct 187 ms 164988 KB Output is correct
10 Correct 208 ms 164988 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 262144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

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