oj.uz

Submission #528787

# Submission time Handle Problem Language Result Execution time Memory
528787 2022-02-21T13:10:13 Z NaimSS Asceticism (JOI18_asceticism) C++14
4 / 100
 600 ms 218056 KB 
#include <bits/stdc++.h>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define Unique(v) sort(all(v));v.erase(unique(all(v)),v.end());
#define sz(v) ((int)v.size())
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
//#define left oooooopss
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
#define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll b,ll e,ll m){
  b%=m;
  ll ans = 1;
  for (; e; b = b * b % m, e /= 2)
      if (e & 1) ans = ans * b % m;
  return ans;
}

// debug:
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){ 
  cerr << ' ' << H; 
  dbg_out(T...); 
}
#ifdef LOCAL
#define dbg(...) cerr<<"(" << #__VA_ARGS__<<"):" , dbg_out(__VA_ARGS__) , cerr << endl
#else
#define dbg(...) 42
#endif
//

const int N = 303;
ll dp[N][N][N];
const ll M = 1e9 + 7;
int nn,kk;

ll solve(int n,int k,int l){
  ll&x = dp[n][k][l];
  if(x!=-1)return x;
  if(n==nn+1){
    return x = (k == kk);
  }
  x=0;
  for(int nv=1;nv<=n;nv++){
    x+=solve(n+1,k + (nv<=l),nv);
    if(x>=M)x-=M;
  }
  return x;
}


int32_t main(){
  fastio;
  cin >> nn >> kk;
  ms(dp,-1);
  cout << solve(2,1,1) << endl;

  // math -> gcd it all
  // Did u check N=1? Did you switch N,M?
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 218056 KB Output is correct
2 Correct 90 ms 217960 KB Output is correct
3 Correct 81 ms 217972 KB Output is correct
4 Correct 81 ms 217960 KB Output is correct
5 Correct 85 ms 217932 KB Output is correct
6 Correct 84 ms 217960 KB Output is correct
7 Correct 82 ms 218016 KB Output is correct
8 Correct 81 ms 218052 KB Output is correct
9 Correct 82 ms 217976 KB Output is correct
10 Correct 82 ms 218032 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 218056 KB Output is correct
2 Correct 90 ms 217960 KB Output is correct
3 Correct 81 ms 217972 KB Output is correct
4 Correct 81 ms 217960 KB Output is correct
5 Correct 85 ms 217932 KB Output is correct
6 Correct 84 ms 217960 KB Output is correct
7 Correct 82 ms 218016 KB Output is correct
8 Correct 81 ms 218052 KB Output is correct
9 Correct 82 ms 217976 KB Output is correct
10 Correct 82 ms 218032 KB Output is correct
11 Correct 199 ms 218048 KB Output is correct
12 Execution timed out 1078 ms 218048 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 218056 KB Output is correct
2 Correct 90 ms 217960 KB Output is correct
3 Correct 81 ms 217972 KB Output is correct
4 Correct 81 ms 217960 KB Output is correct
5 Correct 85 ms 217932 KB Output is correct
6 Correct 84 ms 217960 KB Output is correct
7 Correct 82 ms 218016 KB Output is correct
8 Correct 81 ms 218052 KB Output is correct
9 Correct 82 ms 217976 KB Output is correct
10 Correct 82 ms 218032 KB Output is correct
11 Correct 199 ms 218048 KB Output is correct
12 Execution timed out 1078 ms 218048 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 218056 KB Output is correct
2 Correct 90 ms 217960 KB Output is correct
3 Correct 81 ms 217972 KB Output is correct
4 Correct 81 ms 217960 KB Output is correct
5 Correct 85 ms 217932 KB Output is correct
6 Correct 84 ms 217960 KB Output is correct
7 Correct 82 ms 218016 KB Output is correct
8 Correct 81 ms 218052 KB Output is correct
9 Correct 82 ms 217976 KB Output is correct
10 Correct 82 ms 218032 KB Output is correct
11 Correct 199 ms 218048 KB Output is correct
12 Execution timed out 1078 ms 218048 KB Time limit exceeded
13 Halted 0 ms 0 KB -