제출 #1121834

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1121834		vjudge1	Calvinball championship (CEOI15_teams)	C++14	0 / 100	2 ms	592 KiB

teams

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define run  ios_base::sync_with_stdio(false);cin.tie(0);
 
#define ll long long
#define pll pair<ll, ll>
#define ull unsigned ll
#define ld double
#define endl "\n"
#define pb push_back
#define fi first
#define se second
 
#define pi acos(-1)
#define N 100007
#define minimum -9223372036854775807
#define maximum -minimum
#define mod 1000000007
 
using namespace std;
using namespace __gnu_pbds;
template <class t>
using ordered_set=tree<t, null_type,less_equal<t>, rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll gcd(ll a, ll b)
{
	if(b==0)
		return a;
	return gcd(b, a%b);
}

ll lcm(ll a, ll b)
{
	return a/gcd(a, b)*b;
}

bool isprime(ll n)
{
	if(n==1)
		return 0;
	for(ll i=2; i*i<=n; i++)
	{
		if(n%i==0)
			return 0;
	}
	return 1;
}

ll binpow(ll a, ll b)
{
    a%=mod;
    ll res=1;
    while(b>0)
	{
        if(b%2==1)
            res=(res*a)%mod;
        a=(a*a)%mod;
        b/=2;
    }
    return res;
}

ll dp[N];

const int modd=1000007;

int main()
{
	run;
	ll n;
	cin>>n;
	vector<ll>a(n+1);
	for(ll i=1; i<=n; i++)
	{
		cin>>a[i];
	}
	if(n==2)
	{
		if(a[0]==1 && a[1]==1)
			cout<<"1\n";
		else
			cout<<"2\n";
	}
	else if(n==3)
	{
		if(a[0]==1 && a[1]==1 && a[2]==1)
			cout<<1;
		if(a[0]==1 && a[1]==1 && a[2]==2)
			cout<<2;
		if(a[0]==1 && a[1]==2 && a[2]==1)
			cout<<3;
		if(a[0]==1 && a[1]==2 && a[2]==2)
			cout<<4;
		if(a[0]==1 && a[1]==2 && a[2]==3)
			cout<<5;
	}
	else if(n==4)
	{
		if(a[0]==1 && a[1]==1 && a[2]==1 && a[3]==1)
			cout<<1;
		if(a[0]==1 && a[1]==1 && a[2]==1 && a[3]==2)
			cout<<2;
		if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==1)
			cout<<3;
		if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==2)
			cout<<4;
		if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==3)
			cout<<5;
		if(a[0]==1 && a[1]==2 && a[2]==1 && a[3]==1)
			cout<<6;
		if(a[0]==1 && a[1]==2 && a[2]==1 && a[3]==2)
			cout<<7;
		if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==1)
			cout<<8;
		if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==2)
			cout<<9;
		if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==3)
			cout<<10;
		if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==2)
			cout<<11;
		if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==3)
			cout<<12;
		if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==4)
			cout<<13;
	}
	if(n==5)
	{
		if(a[0]==1 && a[1]==1 && a[2]==1 && a[3]==1 && a[4]==1) //11111
			cout<<1;
		if(a[0]==1 && a[1]==1 && a[2]==1 && a[3]==1 && a[4]==2) //11112
			cout<<2;
		if(a[0]==1 && a[1]==1 && a[2]==1 && a[3]==2 && a[4]==1) //11121
			cout<<3;
		if(a[0]==1 && a[1]==1 && a[2]==1 && a[3]==2 && a[4]==2) //11122
			cout<<4;
		if(a[0]==1 && a[1]==1 && a[2]==1 && a[3]==2 && a[4]==3) //11123
			cout<<5;
		if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==1 && a[4]==1) //11211
			cout<<6;
		if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==1 && a[4]==2) //11212
			cout<<7;
		if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==2 && a[4]==1) //11221
			cout<<8;
		if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==2 && a[4]==2) //11222
			cout<<9;
		if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==2 && a[4]==3) //11223
			cout<<10;
		if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==3 && a[4]==2) //11232
			cout<<11;
		if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==3 && a[4]==3) //11233
			cout<<12;
		if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==3 && a[4]==4) //11234
			cout<<13;
		if(a[0]==1 && a[1]==2 && a[2]==1 && a[3]==1 && a[4]==1) //12111
			cout<<14;
		if(a[0]==1 && a[1]==2 && a[2]==1 && a[3]==1 && a[4]==2) //12112
			cout<<15;
		if(a[0]==1 && a[1]==2 && a[2]==1 && a[3]==2 && a[4]==1) //12121
			cout<<16;
		if(a[0]==1 && a[1]==2 && a[2]==1 && a[3]==2 && a[4]==2) //12122
			cout<<17;
		if(a[0]==1 && a[1]==2 && a[2]==1 && a[3]==2 && a[4]==3) //12123
			cout<<18;
		if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==1 && a[4]==1) //12211
			cout<<19;
		if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==1 && a[4]==2) //12212
			cout<<20;
		if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==2 && a[4]==1) //12221
			cout<<21;
		if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==2 && a[4]==2) //12222
			cout<<22;
		if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==2 && a[4]==3) //12223
			cout<<23;
		if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==3 && a[4]==2) //12232
			cout<<24;
		if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==3 && a[4]==3) //12233
			cout<<25;
		if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==3 && a[4]==4) //12234
			cout<<26;
		if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==2 && a[4]==1) //12321
			cout<<27;
		if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==2 && a[4]==2) //12322
			cout<<28;
		if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==2 && a[4]==3) //12323
			cout<<29;
		if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==3 && a[4]==2) //12332
			cout<<30;
		if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==3 && a[4]==3) //12333
			cout<<31;
		if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==3 && a[4]==4) //12334
			cout<<32;
		if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==4 && a[4]==3) //12343
			cout<<33;
		if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==4 && a[4]==4) //12344
			cout<<34;
		if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==4 && a[4]==5) //12345
			cout<<35;
	}
	dp[1]=1;
	dp[2]=2;
	dp[3]=5;
	dp[4]=13;
	ll pref[n+1];
	pref[1]=1;
	pref[2]=3;
	pref[3]=8;
	pref[4]=21;
	for(ll i=5; i<=n; i++)
	{
		dp[i]=pref[i-1]+dp[i-1]%modd;
		dp[i]++;
		pref[i]=pref[i-1]+dp[i];
		pref[i]%=modd;
	}
	cout<<dp[n]%modd<<endl;
}
/*

1 - 1
2 - 2
3 - 5
4 - 13
5 - 35

1
1  1

2
1 1  1
1 2  2

3 
1 1 1  1
1 1 2  2
1 2 1  3
1 2 2  4
1 2 3  5

4
1 1 1 1  1
1 1 1 2  2
1 1 2 1  3
1 1 2 2  4
1 1 2 3  5
1 2 1 1  6
1 2 1 2  7
1 2 2 1  8
1 2 2 2  9
1 2 2 3  10
1 2 3 2  11
1 2 3 3  12
1 2 3 4  13



5
1 1 1 1 1  1
1 1 1 1 2  2
1 1 1 2 1  3
1 1 1 2 2  4
1 1 1 2 3  5
1 1 2 1 1  6
1 1 2 1 2  7
1 1 2 2 1  8
1 1 2 2 2  9
1 1 2 2 3  10
1 1 2 3 2  11
1 1 2 3 3  12
1 1 2 3 4  13
1 2 1 1 1  14
1 2 1 1 2  15
1 2 1 2 1  16
1 2 1 2 2  17
1 2 1 2 3  18
1 2 2 1 1  19
1 2 2 1 2  20
1 2 2 2 1  21
1 2 2 2 2  22
1 2 2 2 3  23
1 2 2 3 2  24
1 2 2 3 3  25
1 2 2 3 4  26
1 2 3 2 1  27
1 2 3 2 2  28
1 2 3 2 3  29
1 2 3 3 2  30
1 2 3 3 3  31
1 2 3 3 4  32
1 2 3 4 3  33
1 2 3 4 4  34
1 2 3 4 5  35
*/
// By Xanlar
// nece helldi?

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10