oj.uz

답안 #459636

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
459636 2021-08-08T21:06:38 Z gupta_samarth Asceticism (JOI18_asceticism) C++14
4 / 100
 5 ms 460 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=1;j<=n;j++)
	{
		pref[j][0] = dp[j][0];
		for(int k=1;k<=n;k++)
			pref[j][k] = pref[j][k-1] + 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++)
			{
				add( ndp[bad][last], pref[bad][last-1] );
				add( ndp[bad][last], mod( pref[bad-1][i-1] - pref[bad-1][last-1] ) );
			}
		}

		dp = ndp;
		for(int j=1;j<=n;j++)
		{
			pref[j][0] = dp[j][0];
			for(int k=1;k<=n;k++)
				pref[j][k] = pref[j][k-1] + 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Incorrect 5 ms 460 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Incorrect 5 ms 460 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Incorrect 5 ms 460 KB Output isn't correct
12 Halted 0 ms 0 KB -