結果

問題 No.1279 Array Battle
ユーザー クケクケ
提出日時 2020-11-07 11:30:09
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 29 ms / 2,000 ms
コード長 3,370 bytes
コンパイル時間 908 ms
コンパイル使用メモリ 99,584 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-22 14:23:42
合計ジャッジ時間 1,565 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 5 ms
5,376 KB
testcase_14 AC 4 ms
5,376 KB
testcase_15 AC 28 ms
5,376 KB
testcase_16 AC 28 ms
5,376 KB
testcase_17 AC 28 ms
5,376 KB
testcase_18 AC 27 ms
5,376 KB
testcase_19 AC 29 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'long long int lcm(std::vector<long long int>)':
main.cpp:74:145: warning: 'n' may be used uninitialized [-Wmaybe-uninitialized]
   74 | ll lcm(vector<ll> a){ll n;rep(i,1,a.size()){n=a[i-1]*a[i];ll k=a[i-1]%a[i];while(k!=0){a[i-1]=a[i];a[i]=k;k=a[i-1]%a[i];}n/=a[i];a[i]=n;}return n;}
      |                                                                                                                                                 ^
main.cpp:74:25: note: 'n' was declared here
   74 | ll lcm(vector<ll> a){ll n;rep(i,1,a.size()){n=a[i-1]*a[i];ll k=a[i-1]%a[i];while(k!=0){a[i-1]=a[i];a[i]=k;k=a[i-1]%a[i];}n/=a[i];a[i]=n;}return n;}
      |                         ^

ソースコード

diff # 

#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<list>
#define ll long long
#define str string
#define ld long double
#define vec vector
#define vll vec<ll>
#define vvll vec<vll>
#define rep(i,a,b) for(ll i=(a);i<(b);i++)
#define rrep(i,b,a) for(ll i=(b);i>=(a);i--)
#define repset(itr,a) for(auto itr=a.begin();itr!=a.end();itr++)
#define repnck(bit,n,k) for(ll bit=(1ll<<(k))-1;bit<(1ll<<(n));bit=(bit==0?(1ll<<(n)):nec(bit)))
#define bi1(bit,i) ((bit)&1ll<<(i)?true:false)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define kai "\n"
#define prque priority_queue
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mie min_element
#define mae max_element
#define tos to_string
#define sep setprecision
#define lob lower_bound
#define upb upper_bound
#define bis binary_search
#define nep next_permutation
#define MOD 1000000007ll
#define MAX 2147483647ll
#define MIN 0.0000000001l
#define equal(a,b) (abs((a)-(b))<MIN)
using namespace std;
void solve();
struct ll2{ll x,y;bool operator<(const ll2 &l)const{return x!=l.x?x<l.x:y<l.y;};};
struct ll3{ll x,y,z;bool operator<(const ll3 &l)const{if(x!=l.x)return x<l.x;if(y!=l.y)return y<l.y;return z<l.z;};};

class ufset{
public:
	ufset(ll n) {rank.resize(n,0);rep(i,0,n)p.pub(i);}
	bool same(ll i,ll j){return find(i)==find(j);}
	void unite(ll i,ll j){link(find(i),find(j));}
	ll find(ll i){if(i!=p[i])p[i]=find(p[i]);return p[i];}
private:
  vll rank,p;
	void link(ll i,ll j){if(rank[i]>rank[j])p[j]=i;else{p[i]=j;if(rank[i]==rank[j])rank[j]++;}}
};

class nck{
public:
	nck(ll maxn,ll mod=MOD){
		NUM=maxn+1;p=mod;
		fac.resize(NUM);finv.resize(NUM);inv.resize(NUM);
		fac[0]=fac[1]=finv[0]=finv[1]=inv[1]=1;
		rep(i,2,NUM){fac[i]=fac[i-1]*i%p;inv[i]=p-inv[p%i]*(p/i)%p;finv[i]=finv[i-1]*inv[i]%p;}
	}
	ll c(ll n,ll k){return fac[n]*(finv[k]*finv[n-k]%p)%p;}
private:
  ll NUM,p;
	vll fac,finv,inv;
};

ll gcd(vector<ll> a){rep(i,1,a.size()){ll k=a[i-1]%a[i];while(k!=0){a[i-1]=a[i];a[i]=k;k=a[i-1]%a[i];}}return a.back();}
ll lcm(vector<ll> a){ll n;rep(i,1,a.size()){n=a[i-1]*a[i];ll k=a[i-1]%a[i];while(k!=0){a[i-1]=a[i];a[i]=k;k=a[i-1]%a[i];}n/=a[i];a[i]=n;}return n;}
ll pow2(ll a,ll b,ll p=MOD){if(b==-1)return pow2(a,p-2,p);ll res=1;if(b>0){res=pow2(a,b/2,p);if(b%2==0)res=res*res%p;else res=res*res%p*a%p;}return res;}
ll nec(ll bit){ll x=bit&-bit,y=bit+x;return (((bit&~y)/x)>>1)|y;}
ll bisz(ll bit){ll size=0;while(bit>0){bit/=2;size++;}return size;}
ll ransu(){static unsigned int TX=123456789, TY=362436069, TZ=521288629, TW=88675123;unsigned int tt=(TX^(TX<<11));TX=TY;TY=TZ;TZ=TW;return (TW=(TW^(TW>>19))^(tt^(tt>>8)));}
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed;
	solve();
}
ll n;vll a,b,seen;
ll f(ll i,ll s){
	if(i==n)return s;
	ll k=0;
	rep(j,0,n){
		if(!seen[j]){
			seen[j]=1;
			k=max(k,f(i+1,s+max(0ll,a[j]-b[i])));
			seen[j]=0;
		}
	}
	return k;
}
ll sum,ans=0;
void g(ll i,ll s){
	if(i==n){
		if(s==sum)ans++;
		return;
	}
	rep(j,0,n){
		if(!seen[j]){
			seen[j]=1;
			g(i+1,s+max(0ll,a[j]-b[i]));
			seen[j]=0;
		}
	}
}
void solve(){
	cin>>n;a.resize(n);b.resize(n);
	rep(i,0,n)cin>>a[i];
	rep(i,0,n)cin>>b[i];
	seen.resize(n,0);
	sum=f(0,0);
	g(0,0);
	cout<<ans<<kai;
}
0