oj.uz

Submission #459637

# Submission time Handle Problem Language Result Execution time Memory
459637 2021-08-08T21:10:21 Z gupta_samarth Asceticism (JOI18_asceticism) C++14
24 / 100
 600 ms 24016 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 6 ms 460 KB Output is correct
12 Correct 177 ms 2472 KB Output is correct
13 Correct 179 ms 2472 KB Output is correct
14 Correct 178 ms 2484 KB Output is correct
15 Correct 180 ms 2628 KB Output is correct
16 Correct 179 ms 2584 KB Output is correct
17 Correct 50 ms 1788 KB Output is correct
18 Correct 106 ms 1860 KB Output is correct
19 Correct 14 ms 756 KB Output is correct
20 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 6 ms 460 KB Output is correct
12 Correct 177 ms 2472 KB Output is correct
13 Correct 179 ms 2472 KB Output is correct
14 Correct 178 ms 2484 KB Output is correct
15 Correct 180 ms 2628 KB Output is correct
16 Correct 179 ms 2584 KB Output is correct
17 Correct 50 ms 1788 KB Output is correct
18 Correct 106 ms 1860 KB Output is correct
19 Correct 14 ms 756 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Execution timed out 1080 ms 24016 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 6 ms 460 KB Output is correct
12 Correct 177 ms 2472 KB Output is correct
13 Correct 179 ms 2472 KB Output is correct
14 Correct 178 ms 2484 KB Output is correct
15 Correct 180 ms 2628 KB Output is correct
16 Correct 179 ms 2584 KB Output is correct
17 Correct 50 ms 1788 KB Output is correct
18 Correct 106 ms 1860 KB Output is correct
19 Correct 14 ms 756 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Execution timed out 1080 ms 24016 KB Time limit exceeded
22 Halted 0 ms 0 KB -