Submission #20533

#	Time	Username	Problem	Language	Result	Execution time	Memory
20533		안녕하세요 투어리스트입니다 진짜에요 (#35)	복불복 (OJUZ11_luck)	C++14	34 / 100	233 ms	322192 KiB

luck

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
void read(int& x){ scanf("%d",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back

int n, k;
int a[1010];
int b[1010];
const ll M=1'000'000'007;

void in(){
	read(n, k);
    for(int i=1; i<=n; ++i) read(a[i]); sort(a+1, a+n+1, greater<int>());
    for(int i=1; i<=n; ++i) read(b[i]); sort(b+1, b+n+1);
}

void naive(){
	int ind[1010];
    for(int i=1; i<=n; ++i) ind[i]=i;
	int ans=0;
	int c[1010];
	do {
		for(int i=1; i<=n; ++i) c[i]=a[i]+b[ind[i]];
		bool flg=1;
		int max_rnk = 0;
		for(int i=1; i<=k; ++i){
			int rnk = count_if(c+1, c+n+1, [&](int x){ return x > c[i]; })+1;
			max_rnk = max(max_rnk, rnk);
			if(rnk > k)
				flg=0;
		}
		for(int i=k+1; i<=n; ++i){
			int rnk = count_if(c+1, c+n+1, [&](int x){ return x > c[i]; })+1;
			if(rnk < max_rnk)
				flg=0;
		}
		ans += flg;
	} while(next_permutation(ind+1, ind+n+1));
	printf("%d\n", ans);
}

int dp[1<<15][2001];
bool chk[1<<15][2001];

int work(int mask, int lmin){
	if(mask+1 == (1<<n))
		return 1;
	int& ret=dp[mask][lmin];
	if(chk[mask][lmin]) return ret;
	chk[mask][lmin]=1;
	int p=__builtin_popcount(mask);
	if(p < k){
		for(int i=0; i<n; ++i) if((1&(mask>>i))==0) {
			ret += work(mask|(1<<i), min(lmin, a[p+1]+b[i+1]));
			ret %= M;
		}
	} else {
		for(int i=0; i<n; ++i) if((1&(mask>>i))==0) {
			if(a[p+1]+b[i+1] <= lmin)
				ret += work(mask|(1<<i), lmin);
			ret %= M;
		}
	}
	return ret;
}

void nksmall(){
	printf("%d\n", work(0, 2000));
}

void solve(){
}

int main()
{
#ifdef NAMSEO
	freopen("in", "r", stdin);
#endif
    in();
    if(n<=8) naive();
    else if(n<=15) nksmall();
    else solve();
    return 0;
}

Compilation message (stderr)

luck.cpp: In function 'void read(int&)':
luck.cpp:5:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                                  ^

• Subtask 1: 9 / 9
• Subtask 2: 0 / 13
• Subtask 3: 25 / 25
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27