Submission #204156

#	Time	Username	Problem	Language	Result	Execution time	Memory
204156		Rouge_Hugo	Kitchen (BOI19_kitchen)	C++14	100 / 100	44 ms	1816 KiB

kitchen

        #include<bits/stdc++.h>
        #define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        #define ll long long
        using namespace std;
        ll n,m,k;
        const int inf=1e14;
        const int N=309;
        ll d[2][N*N],c[N],b[N],a[N];
        int g (int x)
        {
            return x%2;
        }
        int go (int i)
        {
            if (d[g(m-1)][i]>=n*k)return 1;
            return 0;
        }
        int main()
        {
            cin>>n>>m>>k;ll s=0;
            for(int i=0;i<n;i++){cin>>a[i];if (a[i]<k){cout<<"Impossible";return 0;}s+=a[i];}
            for(int i=0;i<m;i++){cin>>b[i];c[i]=min(b[i],n);}

            for(int j=0;j<90009;j++)d[0][j]=-inf,d[1][j]=-inf;d[0][0]=0;
            d[0][b[0]]=c[0];
            for(int i=1;i<m;i++)
            {
                for(int j=0;j<=90009;j++)
                {
                    d[g(i)][j]=d[g(i-1)][j];
                    if (j-b[i]<0)continue;
                    d[g(i)][j]=max(d[g(i)][j],d[g(i-1)][j-b[i]]+c[i]);
                }
            }
            for(int i=s;i<=90009;i++)
            if (go(i))
            {
                cout<<i-s;return 0;
            }
            cout<<"Impossible";
        }

Compilation message (stderr)

kitchen.cpp:6:23: warning: overflow in implicit constant conversion [-Woverflow]
         const int inf=1e14;
                       ^~~~
kitchen.cpp: In function 'int main()':
kitchen.cpp:24:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
             for(int j=0;j<90009;j++)d[0][j]=-inf,d[1][j]=-inf;d[0][0]=0;
             ^~~
kitchen.cpp:24:63: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
             for(int j=0;j<90009;j++)d[0][j]=-inf,d[1][j]=-inf;d[0][0]=0;
                                                               ^

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 28 / 28