oj.uz

답안 #414648

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
414648 2021-05-30T23:09:12 Z aaru2601 은행 (IZhO14_bank) C++17
52 / 100
 118 ms 262148 KB 
#include<bits/stdc++.h>
#define lld long long
#define pb push_back
#define mk make_pair
#define MAX (lld)1e18+7
#define lim (lld)1e9+7
#define MAX2 (lld)2e5+9
#define ff first
#define ss second
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

const lld mod=lim;

lld power(lld x, lld y, lld p)  
{   lld res = 1;     x = x % p; if (x == 0) return 0;  
  
    while (y > 0)  
    { if (y & 1) res = (res*x) % p;  y = y>>1; x = (x*x) % p;   }  
    return res;  } 


lld extend_gcd(lld a, lld b, lld& x, lld& y) {
    if (b == 0) { x = 1;y = 0;return a;}
    lld x1, y1;
    lld d = extend_gcd(b, a % b, x1, y1);
    x = y1; y = x1 - y1 * (a / b);return d;	}

lld modinv(lld a, lld p)
{return power(a,p-2,p);}

lld rowNum[]={-1,0,0,1};
lld colNum[]={0,-1,1,0};
int recur(vector<int>&v,vector<int>&b,vector<vector<int>>&dp,
	int cur,int val,int mask)
{
	if(cur==v.size()-1 && val==0)
		return 1;

	if(val<0)
		return 0;

	if(dp[val][mask]!=-1)
		return dp[val][mask];
	int ans = 0;
	for(int i=0;i<b.size();i++)
	{
		if((mask&(1<<i))==0)
		{
			int temp = (mask|(1<<i));
			if(val-b[i]<0)
				continue;
			if(val-b[i]==0)
				ans|=recur(v,b,dp,cur+1,v[cur+1],temp);

			if(val-b[i]>0)
				ans|=recur(v,b,dp,cur,val-b[i],temp);	
		
		}
	}

	dp[val][mask] = ans;
	return dp[val][mask];
}

int main()
{
	fastio
	int n,m;
	cin>>n>>m;
	std::vector<int> v(n+1),b(m);
	int mx = 0;
	for(int i=0;i<n;i++)
	{	
		cin>>v[i];
		mx = max(mx,v[i]);
	}
	v[n] = 0;
	for(int i=0;i<m;i++)
		cin>>b[i];
	
	vector<vector<int>>dp(mx+1,vector<int>(1<<(m+1),-1));

	int cur = 0;
	int val = v[0];
	int mask = 0;
	int res = recur(v,b,dp,cur,val,mask);

	if(res==1)
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;
}

Compilation message

bank.cpp: In function 'int recur(std::vector<int>&, std::vector<int>&, std::vector<std::vector<int> >&, int, int, int)':
bank.cpp:37:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  if(cur==v.size()-1 && val==0)
      |     ~~~^~~~~~~~~~~~
bank.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i=0;i<b.size();i++)
      |              ~^~~~~~~~~

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 16 ms 30540 KB Output is correct
5 Runtime error 118 ms 262148 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

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

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 79868 KB Output is correct
2 Correct 61 ms 130680 KB Output is correct
3 Correct 70 ms 130344 KB Output is correct
4 Correct 2 ms 1844 KB Output is correct
5 Correct 7 ms 12876 KB Output is correct
6 Correct 51 ms 109288 KB Output is correct
7 Correct 41 ms 85836 KB Output is correct
8 Correct 52 ms 110636 KB Output is correct
9 Correct 60 ms 113596 KB Output is correct
10 Correct 52 ms 113588 KB Output is correct
11 Correct 4 ms 3128 KB Output is correct

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 16 ms 30540 KB Output is correct
5 Runtime error 118 ms 262148 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -