Submission #459637

#	Time	Username	Problem	Language	Result	Execution time	Memory
459637		gupta_samarth	Asceticism (JOI18_asceticism)	C++14	24 / 100	1080 ms	24016 KiB

asceticism

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
#define nl cout<<"\n"
#define all(x) x.begin(),x.end()

template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }

const ll MOD = 1000000007;
// const ll MOD = 998244353;
template<class T1, class T2> void add( T1 &x, T2 y, ll m = MOD ){ x += y; if( x >= m ) x -= m; }
template<class T1, class T2> void sub( T1 &x, T2 y, ll m = MOD ){ x -= y; if( x < 0 ) x += m; }
ll mod( ll n, ll m=MOD ){ n%=m;if(n<0)n+=m;return n; }

const int MAXN = 1e5+5;
const int LOGN = 21;
const ll INF = 1e16;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

void solve()
{
	int n,k;
	cin>>n>>k;

	// dp[i][bad][last] = dp[i-1][bad][<last] + dp[i-1][bad-1][>=last]
	vector<vector<ll>> dp(n+1, vector<ll>(n+1,0)), pref(n+1, vector<ll>(n+1,0));

	dp[1][1] = 1;
	for(int j=0;j<=n;j++)
	{
		pref[j][0] = dp[j][0];
		for(int k=1;k<=n;k++)
		{
			pref[j][k] = pref[j][k-1];
			add( pref[j][k], dp[j][k] );
		}
	}

	for(int i=2;i<=n;i++)
	{
		vector<vector<ll>> ndp(n+1, vector<ll>(n+1,0));
		for(int bad=1;bad<=i;bad++)
		{
			for(int last=1;last<=i;last++)
			{
				// for(int j=1;j<last;j++)
				// 	add( ndp[bad][last], dp[bad][j] );
				add( ndp[bad][last], mod( pref[bad][last-1] - pref[bad][0] ) );

				// for(int j=last;j<i;j++)
				// 	add( ndp[bad][last], dp[bad-1][j] );
				add( ndp[bad][last], mod( pref[bad-1][i-1] - pref[bad-1][last-1] ) );
			}
		}

		dp = ndp;
		for(int j=0;j<=n;j++)
		{
			pref[j][0] = dp[j][0];
			for(int k=1;k<=n;k++)
			{
				pref[j][k] = pref[j][k-1];
				add( pref[j][k], dp[j][k] );
			}
		}

	}

	ll ans = 0;
	for(int last=1;last<=n;last++)
		add( ans, dp[k][last] );
	cout<<ans,nl;
}

int main()
{
	#ifdef gupta_samarth
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
	fastio();

	int t = 1;
	// cin>>t;
	for(int test=1;test<=t;test++)
	{
		// cout<<"Case #"<<test<<": ";
		solve();
	}

	cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 0 / 25
• Subtask 4: 0 / 51