Submission #46338

#	Time	Username	Problem	Language	Result	Execution time	Memory
46338		ffresh	즐거운 채소 기르기 (JOI14_growing)	C++17	30 / 100	1091 ms	262144 KiB

growing

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 15
• Subtask 4: 0 / 55