fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define for1(i,m,n) for(int i=m,n_=(n);i<=n_;i++)
  5. #define for0(i,m,n) for(int i=m;i<n;i++)
  6. #define forr1(i,m,n) for(int i=m;i>=n;i--)
  7. #define forr2(i,m,n) for(int i=m;i>n;i--)
  8. #define mini(a,b) (a)=min((a),(b))
  9. #define maxi(a,b) (a)=max((a),(b))
  10. #define ll long long
  11. #define el '\n'
  12. #define fi first
  13. #define se second
  14. #define ii pair<ll,int>
  15. #define vll(i) i.begin(),i.end()
  16. #define pb push_back
  17. #define fr front()
  18. #define int long long 
  19. #define MASK(i) ((1ll) << (i))
  20. #define BIT(i,n) (((i)>>(n))&1)
  21. const string NAME= "hamming";
  22. const int N=1e5+ 30;
  23. const int MOD=1e9 + 9;
  24. int n;
  25. vector< ii > v;
  26. int  f[N], dp[N];
  27. int Get( int x){
  28.  int s = 0;
  29.  for( int x_ = x; x_ > 0; x_ -= x_ & -x_) 
  30.    s = ( s + dp[x_]) % MOD;
  31.  
  32.   return s;
  33.  
  34. }
  35. void Update( int x, int val) {
  36.   for(int x_ = x; x_ <= n; x_ += x_ & -x_) 
  37.    dp[x_] = (dp[x_] + val) % MOD;
  38. }
  39. signed main() {
  40. if (fopen((NAME + ".INP").c_str(), "r")) {
  41. freopen((NAME + ".INP").c_str(), "r", stdin);
  42. freopen((NAME + ".OUT").c_str(), "w", stdout);
  43. }
  44. ios::sync_with_stdio(0);
  45. cin.tie(0);
  46. cout.tie(0);
  47.  
  48.  cin >> n; n++;
  49. for1(i,2,n) {
  50.   int x; cin >> x;
  51.   f[i] = f[i - 1] + x;
  52.   v.pb({f[i], i});
  53. }
  54. v.pb({0, 1});
  55. sort(vll(v));
  56. int ans = 0;
  57.  
  58. for(auto [x,id]:v){
  59.   int t = Get( id);
  60.  if ( id == 1)
  61.   Update( id,  1);
  62.   else Update(id, t);
  63.   if( id == n){
  64.     cout << t;
  65.     return 0;
  66.   }
  67. }
  68.  
  69. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uODZDX
số cách chia dãy thanh các đoạn không âm
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!