oj.uz

답안 #39085

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
39085 2018-01-09T09:22:59 Z mrtsima22 은행 (IZhO14_bank) C++14
52 / 100
 140 ms 9484 KB 
#include <bits/stdc++.h>
using namespace std;
#define lo long
lo b[100003],n,m,s[100003],sum[100003];
lo g[100003],d[23][100003],jam[100003];
string ans="NO";
int main(){std::ios::sync_with_stdio(false);
cin>>n>>m;
for(lo i=0;i<n;i++)
{
	cin>>b[i];
	sum[i]=sum[i-1]+b[i];
}
for(lo i=0;i<m;i++)
{
	cin>>g[i];
}
for(lo i=0;i<(1<<m);i++)
{
	for(lo j=0;j<m;j++)
	{
		if(!((i>>j)&1))
		{
			jam[i|(1<<j)]=jam[i]+g[j];
		}
	}
}
d[0][0]=1;
for(lo i=0;i<=n;i++)
{
	for(lo j=0;j<(1<<m);j++)
	{
		if(!d[i][j])
		{
			continue;
		}
		if(i==n)
		{
			ans="YES";
			break;
		}
		if(sum[i]==jam[j])
		{
			d[i+1][j]=1;
		}
		for(lo t=0; t<m; t++)
		{
			if(!((j>>t)&1))
			{
				d[i][j|(1<<t)]=1;		
			}
		}
	}
}
cout<<ans<<endl;
}
/*

                   *         *
                  * *       * *
                 *   *     *   *
                *     *   *     *
               *       * *       *
               *        *        *
                *               *
                 *             *
                  *           *
                   *         *
                    *       *
                     *     *
                      *   *
                       * *
                        *



*/

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 448 KB Output is correct
4 Correct 6 ms 1232 KB Output is correct
5 Incorrect 140 ms 9484 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9484 KB Output is correct
2 Correct 2 ms 9484 KB Output is correct
3 Correct 2 ms 9484 KB Output is correct
4 Correct 2 ms 9484 KB Output is correct
5 Correct 2 ms 9484 KB Output is correct
6 Correct 2 ms 9484 KB Output is correct
7 Correct 2 ms 9484 KB Output is correct
8 Correct 2 ms 9484 KB Output is correct
9 Correct 2 ms 9484 KB Output is correct
10 Correct 2 ms 9484 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9484 KB Output is correct
2 Correct 4 ms 9484 KB Output is correct
3 Correct 5 ms 9484 KB Output is correct
4 Correct 4 ms 9484 KB Output is correct
5 Correct 4 ms 9484 KB Output is correct
6 Correct 4 ms 9484 KB Output is correct
7 Correct 4 ms 9484 KB Output is correct
8 Correct 4 ms 9484 KB Output is correct
9 Correct 5 ms 9484 KB Output is correct
10 Correct 4 ms 9484 KB Output is correct
11 Correct 5 ms 9484 KB Output is correct

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 448 KB Output is correct
4 Correct 6 ms 1232 KB Output is correct
5 Incorrect 140 ms 9484 KB Output isn't correct
6 Halted 0 ms 0 KB -