akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define pb                push_back
#define ppb               pop_back
#define pf                push_front
#define ppf               pop_front
#define all(x)            (x).begin(),(x).end()
#define sz(x)             (int)((x).size())
#define int               long long
#define M                 1000000007
#define MM                998244353
#define fr                first
#define sc                second
#define pii               pair<int,int>
#define rep(i,a,b)        for(int i=a;i<b;i++)
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define ppc               __builtin_popcount

template<typename T1,typename T2>
std::istream& operator>>(std::istream& in,pair<T1,T2> &a)
{
	in>>a.fr>>a.sc;
	return in;
}
template<typename T1,typename T2>
std::ostream& operator<<(std::ostream& out,pair<T1,T2> &a)
{
	out<<a.fr<<" "<<a.sc;
	return out;
}

int a[105];
int dp[105][100005];
void solve(){
	int n,k;
	cin>>n>>k;
	rep(i,0,n){
		cin>>a[i];
	}
	if(k==0){
		cout<<1;return;
	}
	rep(j,0,a[0]+1){
		dp[0][j]=1;
	}
	rep(j,1,k+1){
		dp[0][j]+=dp[0][j-1];
		dp[0][j]%=M;
	}
	rep(i,1,n){
		rep(j,0,k+1){
			dp[i][j]=dp[i-1][j];
			if(j>a[i])dp[i][j]+=M-dp[i-1][j-a[i]-1];
			dp[i][j]%=M;
		}
		// rep(j,a[i],k+1){
		// 	dp[i][j]+=dp[i-1][j-a[i]];
		// 	dp[i][j]%=M;
		// }
		rep(j,1,k+1){
			dp[i][j]+=dp[i][j-1];
			dp[i][j]%=M;
		}
	}
	cout<<(dp[n-1][k]+M-dp[n-1][k-1])%M;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	#ifdef SEIVE
		seive();
	#endif
	#ifdef NCR
		init();
	#endif
	#ifdef DSU
		cleardsu(MAXDSUSIZE);
	#endif
	int t=1;
	//cin>>t;
	while(t--) solve();
	return 0;
}


Measured memory_bytes: 80128
#include <bits/stdc++.h>

#pragma GCC optimize("O3")

using namespace std;

#define MAXN 100005

#define FOR(i, n) for (int i = 0; i < n; i++)
#define FORR(j, i, n) for (int i = j; i < n; i++)
#define FORD(i, n) for (int i = n - 1; i >= 0; i--)
#define FOBIR(i, n) for (int i = 1; i <= n; i++)
#define pb push_back
#define mp make_pair
#define endl '\n'
#define DUEHOANG                  \
	ios_base::sync_with_stdio(0); \
	cin.tie(NULL);                \
	cout.tie(NULL)

#define fileio(in, out) \
	freopen(in, "r", stdin); \
	freopen(out, "w", stdout);

#define long long long

typedef set<int> si;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef priority_queue<int> pqi;
typedef stack<int> sti;
typedef queue<int> qi;
typedef deque<int> di;
typedef map<int, int> mii;
#define f first
#define s second

string s;
int main()
{
    cin >> s;
    map<string, int> m;
    m["SUN"] = 7;
    m["MON"] = 6;
    m["TUE"] = 5;
    m["WED"] = 4;
    m["THU"] = 3;
    m["FRI"] = 2;
    m["SAT"] = 1;
    cout << m[s] << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <map>
#include <algorithm>
using namespace std;
const int maxn=500005;
struct node
{
    int l,r,sum;
} tree[maxn*4];
struct ques
{
    int l,r,index;
}ask[maxn];
int a[maxn];
int ans[maxn];
void build(int i,int left,int right)
{
    tree[i].l=left,tree[i].r=right;
    tree[i].sum=0;
    if(left==right)
        return;
    int mid=left+right>>1;
    build(i<<1,left,mid);
    build(i<<1|1,mid+1,right);
}
map<int,int> has;
void update(int i,int pos ,int w)
{
    if(tree[i].l==pos&&tree[i].r==pos)
    {
        tree[i].sum+=w;
        return ;
    }
    int mid=(tree[i].l+tree[i].r)>>1;
    if(pos<=mid)
        update(i<<1,pos ,w);
    else
        update(i<<1|1,pos ,w);
    tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
}
int query(int i,int left,int right)
{
    if(tree[i].l==left&&tree[i].r==right)
    {
        return tree[i].sum;
    }
    int mid=(tree[i].l+tree[i].r)>>1;
    if(right<=mid)
        return query(i<<1,left,right);
    else if(left>mid)
        return query(i<<1|1,left,right);
    else
        return query(i<<1,left,mid)+query(i<<1|1,mid+1,right);
}
bool cmp(ques a,ques b)
{
    return a.r<b.r;
}
int main()
{
    int n;int m;
    scanf("%d",&n); scanf("%d",&m);
    build(1,1,n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    
   
    for(int i=1;i<=m;i++)
    {
        ask[i].index=i;
        scanf("%d%d",&ask[i].l,&ask[i].r);
    }
    sort(ask+1,ask+1+m,cmp);
    int cur=1;
    for(int i=1;i<=m;i++)
    {
        for(int j=cur;j<=ask[i].r;j++)
        {
            if(has.find(a[j])!=has.end())
            {
                int p=has[a[j]];
                update(1,p ,-1);
            }
            update(1,j, 1);
            has[a[j]]=j;
        }
        cur=ask[i].r+1;
        ans[ask[i].index]=query(1,ask[i].l,ask[i].r);
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
} 

Measured memory_bytes: 49320
#include <bits/stdc++.h>
#define exrep(i, a, b) for(long long i = a; i <= b; i++)
#define rep(i,n)for(long long i=0;i<(long long)(n);i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vector<ll> > vvl;
typedef vector<vector<P> > vvp;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const int MAX=510000;
const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false); 
  
  string s;
  cin >> s;
  if(s=="ABC")cout << "ARC" << endl;
  else cout << "ABC" << endl;
  return 0;     
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int L,R;
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  L = A+B;
  R = C+D;
  if(L > R) {
      cout << "Left" << endl;
  } else if(R > L) {
      cout << "Right" << endl;
  } else {
      cout << "Balanced" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
using namespace std;
const double PI = acos(-1.0);
const string alp = "abcdefghijklmnopqrstuvwxyz";
const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define SUM(c) accumulate((c).begin(),(c).end(),0)
#define UNIQ(c) (c).erase(unique((c).begin(), (c).end()), (c).end());
#define Yn(b) puts(b?"Yes":"No")
#define YN(b) puts(b?"YES":"NO")

bool isprime(int p) {
  if (p==1) return false;
    FOR(i,2,p) {
      if (p%i==0) return false;
    }
  return true;
}

int main(){
  long a,b,c;
  unsigned long k;
  cin >> a >> b >> c >> k;
  if (k%2==1) {
    cout << b-a;
  } else {
    cout << a-b;
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;

int getSumOfDigits(int n){
    int sum = 0;
    while(n>0){
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int main(){
    int n;
    cin >> n;
    int min = 99999999;
    for(int i=1;i<n;i++){
        int temp1 = getSumOfDigits(i);
        int temp2 = getSumOfDigits(n-i);
        if(min>temp1+temp2)min = temp1+temp2;
    }
    cout << min << endl;
    return 0;
}

Measured memory_bytes: 256
X,Y,A,B,C=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))

p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)

ans=[]
ans.append(p[:X])
ans.append(q[:Y])
ans.append(r)
ans=sum(ans,[])
ans.sort(reverse=True)
ans=ans[:X+Y]
print(sum(ans))

Measured memory_bytes: 23328
n = int(input())
L = [0 for i in range(100)]
L[0] = 2
L[1] = 1
def Lucas(n):
    if L[n] != 0:
        return L[n]
    else:
        L[n - 1] = Lucas(n - 1)
        L[n - 2] = Lucas(n - 2)
        return L[n - 1] + L[n - 2]
print(Lucas(n))


Measured memory_bytes: 3060
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int H, W;
  int N;
  while(true) {
    cin>>H>>W;
    if(H==0 && W==0) return 0;
    cin>>N;
    vector<pair<int, int> > node1(N), node2(N);
    int x1, y1, x2, y2;
    vector<int> xarr, yarr;
    map<int, int> xmap, ymap;
    for(int i=0;i<N;++i) {
      cin>>x1>>y1>>x2>>y2;
      node1[i] = mp(x1, y1);
      node2[i] = mp(x2, y2);
      if(xmap[x1]==0) xarr.push_back(x1);
      xmap[x1]++;
      if(xmap[x2]==0) xarr.push_back(x2);
      xmap[x2]++;
      if(ymap[y1]==0) yarr.push_back(y1);
      ymap[y1]++;
      if(ymap[y2]==0) yarr.push_back(y2);
      ymap[y2]++;
    }
    if(xmap[0]==0) xarr.push_back(0);
    if(xmap[H]==0) xarr.push_back(H);
    if(ymap[0]==0) yarr.push_back(0);
    if(ymap[W]==0) yarr.push_back(W);
    sort(xarr.begin(), xarr.end());
    sort(yarr.begin(), yarr.end());
    map<int, int> xxmap, yymap;
    for(int i=0;i<xarr.size();++i) {
      xxmap[xarr[i]] = i;
    }
    for(int i=0;i<yarr.size();++i) {
      yymap[yarr[i]] = i;
    }
    H = xxmap[xarr[xarr.size()-1]];
    W = yymap[yarr[yarr.size()-1]];
    int zaatu[H][W];
    for(int i=0;i<H;++i) {
      for(int j=0;j<W;++j) {
        zaatu[i][j] = 0;
      }
    }
    for(int i=0;i<N;++i) {
      x1 = xxmap[node1[i].fi];
      y1 = yymap[node1[i].se];
      x2 = xxmap[node2[i].fi];
      y2 = yymap[node2[i].se];
      for(int x=x1;x<x2;++x) {
        for(int y=y1;y<y2;++y) {
          zaatu[x][y]++;
        }
      }
    }
    queue<pair<int, int> > que;
    pair<int, int> state;
    int ans = 0;
    int x, y;
    for(int i=0;i<H;++i) {
      for(int j=0;j<W;++j) {
        if(zaatu[i][j]==0) {
          ans++;
          que.push(mp(i, j));
          while(!que.empty()) {
            state = que.front();que.pop();
            x = state.fi;
            y = state.se;
            if(zaatu[x][y]>0) continue;
            zaatu[x][y]++;
            if(x>0 && zaatu[x-1][y]==0) {
              que.push(mp(x-1, y));
            }
            if(x<H-1 && zaatu[x+1][y]==0) {
              que.push(mp(x+1, y));
            }
            if(y>0 && zaatu[x][y-1]==0) {
              que.push(mp(x, y-1));
            }
            if(y<W-1 && zaatu[x][y+1]==0) {
              que.push(mp(x, y+1));
            }
          }
        }
      }
    }
    cout<<ans<<endl;
  }
}



Measured memory_bytes: 4384
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

    def root(self, x):
        return self.__table[x]

    def same(self, x, y):
        return self.__root(x) == self.__root(y)

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x != y:
            self.__size[y] += self.__size[x]
            self.__table[x] = y

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g

@mt
def slv(N, M, K, AB, CD):
    g = defaultdict(set)
    f = UnionFind()
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)
        f.union(a, b)


    direct = defaultdict(int)
    for a, b in AB:
        direct[a] += 1
        direct[b] += 1
    block = defaultdict(set)
    for c, d in CD:
        block[c].add(d)
        block[d].add(c)


    ans = []
    for i in range(1, N+1):
        cand = f.size(i)
        for u in block[i]:
            if f.same(i, u):
                cand -= 1
        cand -= direct[i]
        cand -= 1
        ans.append(cand)
    return ans



def main():
    N, M, K = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    CD = [read_int_n() for _ in range(K)]
    print(*slv(N, M, K, AB, CD))

if __name__ == '__main__':
    main()


Measured memory_bytes: 157704
// 標準入力から一行を読み取り、指定の型に変換する
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

// 標準入力から一行を読み取り、空白文字で分割し、各要素を指定の型に変換する関数
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

// 標準入力からn行を読み取り、各行を空白文字で分割し、各要素を指定の型に変換する関数
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

use std::cmp::*;

fn main() {
    let n: f64 = read();
    let abcde: Vec<Vec<u64>> = read_vec2(5);
    let mut minvalue = 1e15 as u64;

    for i in abcde
    {
        minvalue = min(i[0], minvalue);
    }

    let result: f64 = n / minvalue as f64 + 4.0;

    println!("{}", result.ceil());
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define rrep(i,n) for(int i=(int)n-1;i>=0;--i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T& a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U& u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U& u,const V... v){for(auto& e:u)fill_v<T>(e,v...);}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<P> arm;
    rep(i, n) {
        int x, l;
        cin >> x >> l;
        arm.push_back(P(x+l, x-l));
    }
    sort(arm.begin(), arm.end());
    int ans = 1;
    int now = arm[0].first;
    for (int i = 1; i < n; ++i) {
        if (now <= arm[i].second) {
            ans++;
            now = arm[i].first;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 4224
#include <bits/stdc++.h>
#define REP(i, n) for (ll i = 0; i < n; ++i)
#define FOR(i, b, n) for (ll i = b; i < n; ++i)

using namespace std;
using ll = long long;
using P = pair<int, int>;
const string YES = "YES";
const string NO = "NO";

void solve(string S) {
  int lose(0);
  REP(i, S.length())
    if (S[i] == 'x')
      lose++;
  cout << (lose < 8 ? YES : NO) << endl;
}

int main(){
  // int 3E4  long 2E9  ll 9E18
  cin.tie(0);
  ios::sync_with_stdio(false);

  string S;
  cin >> S;

  solve(S);

  return 0;
}


Measured memory_bytes: 3652
#include<iostream>
#include<cstdio>
#include<cstring>
//#include<vector>
#include<algorithm>


#ifdef L_JUDGE
#pragma warning(disable:4996)
#endif

using namespace std;
typedef long long int LL;
const int MAXN=1e5+10;

LL X[MAXN];
LL N;
LL A,B;


int main(){
	#ifdef L_JUDGE
		freopen("in.txt","r",stdin);
//		freopen("out.txt","w",stdout);
	#endif
    cin.sync_with_stdio(false);
    cin>>N>>A>>B;
    for(int ni=1;ni<=N;ni++){
         cin>>X[ni];
    }
    LL ans=0;
    for(int ni=2;ni<=N;ni++){
        LL dist=X[ni]-X[ni-1];
        ans=ans+min(dist*A,B);
    }
    printf("%lld\n",ans);

	#ifdef L_JUDGE
		fclose(stdin);
		fclose(stdout);
//		system("out.txt");
	#endif

	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int x,i;
    i=0;
    while (1>0)
    {
        x=i=0;
        cin>>x>>i;
        if (x==0 && i==0) return 0;
        if (x>i) swap(x,i);
        cout<<x<<" "<<i<<endl;
    }
}



Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
 
/*
#define cin ifs
#define cout ofs
ifstream ifs("in.txt");
ofstream ofs("out.txt");
//*/
 
signed main() {
    int A;
    cin >> A;
    cout << A / 3 << endl;
    cerr << "hogehoge" << endl;
    return 0;
}

Measured memory_bytes: 256
M=10**9+7
N,K=gets.split.map(&:to_i)
A=gets.split.map(&:to_i).sort{|l,r|l.abs<=>r.abs}
PLS=A.select{|a|0<=a}.sort{|l,r|r<=>l}
MNS=A.select{|a|a<0}.sort

def calc(n)
  m=K-n
  MNS[0...n].inject(1){|s,a|s*a%M} * PLS[0...m].inject(1){|s,a|s*a%M} % M
end

def odd(n)
  m=K-n
  return 0 if calc(n).zero?
  return calc(n-1) if n==K
  return calc(n-1) if m.zero?
  return calc(n-1) if n==MNS.size
  return calc(n+1) if m==PLS.size
  x=Rational(PLS[m].abs, MNS[n-1].abs)
  y=Rational(MNS[n].abs, PLS[m-1].abs)
  x<y ? calc(n+1) : calc(n-1)
end

if N==K
  s=A.inject(1){|s,a|s*a%M}
  s+=M
  p s%M
  exit
end

if K.odd? && PLS.empty?
  s=A[0...K].inject(1){|s,a|s*a%M}
  s+=M
  p s%M
  exit
end

n=A[-K..-1].count{|a|a<0}
p n.even? ? calc(n) : odd(n)

Measured memory_bytes: 36084
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef long double ld;

template <class T>
using lim = numeric_limits<T>;

const int maxn = 500;


struct train{
	int l, r;
	train(){l=r=0;}
	train(int a, int b){
		l = a;
		r = b;
	}
};

vector<train> arr[maxn+1];
int starts[maxn+2][maxn+2];

int main() {
	ios_base::sync_with_stdio(false) ;
	cin.tie(0);
	
	memset(starts, 0, sizeof starts);
	
	int n, m, Q;
	cin >> n >> m >> Q;
	for (int i = 0; i < m; i++){
		int l, r;
		cin >> l >> r;
		arr[l].push_back(train(l,r));
	}
	
	for (int i = 1; i <= n; i++){
		for (train t : arr[i]){
			starts[i][t.r]++;
		}
	}
	
	// how many trains starts below i inclusive but ends before j
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			starts[i][j] += starts[i][j-1] + starts[i-1][j] - starts[i-1][j-1];
		}
	}
	
	while(Q--){
		int p, q;
		cin >> p >> q;
		
		cout << starts[q][q]-starts[p-1][q] << endl;
	}
}



Measured memory_bytes: 4480
#include <iostream>
#include <algorithm>
#include <string>

const int MOD = 10007;



int n;
int dp[1010][8];
int chief[1010];

const std::string member = "JOI";

int main() {
	std::string tmp;
	std::cin >> n;
	std::cin >> tmp;

	for(int i = 0; i < n; ++i) {
		chief[i] = member.find(tmp[i]);
	}

	for(int i = 0; i < n; ++i) {
		int bit = 1 << chief[i];

		for(int j = 0; j < 8; ++j) {
			if((j & bit) == 0) {
				continue;
			}else if (i == 0 && j & 1) {
				dp[i][j] = 1;
			}
			
			for(int k = 0; k < 8; ++k) {
				if((j & k) != 0) {
					dp[i + 1][k] += dp[i][j];
					dp[i + 1][k] %= MOD;
				}
			}
		}
	}
	
	int sum = 0;
	for(int i = 0; i < 8; ++i) {
		if((1 << chief[n - 1]) & i)
			sum += dp[n - 1][i];
	}
	std::cout << sum % MOD << std::endl;
}

Measured memory_bytes: 3184
#include <iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  char s[101];
  cin >> s;
  int cnt = 0;
  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == 'I') cnt++;
    else cnt--;
    if (cnt > ans) {
      ans = cnt;
    }
  }
  cout << ans;
  return 0;
}


Measured memory_bytes: 256
// Last Change: 03/21/2019 22:33:22.
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

namespace NS {
void LoopUntilZeroInpput() {
  int hogegegege = 0;
  while (cin >> hogegegege && hogegegege != 0) {
  }
}
} // namespace NS

int main() {
  ll N;
  cin >> N;

  vector<ll> A(N + 2);
  ll sumA = 0;
  A[0] = 0;
  A[N + 1] = 0;
  for (ll i = 1; i <= N; ++i) {
    cin >> A[i];
    sumA += llabs(A[i] - A[i - 1]);
  }
  sumA += llabs(A[N + 1] - A[N]);

  for (ll i = 1; i <= N; ++i) {
    cout << sumA - llabs(A[i] - A[i - 1]) - llabs(A[i + 1] - A[i])
                + llabs(A[i + 1] - A[i - 1])
         << endl;
  }

  //NS::LoopUntilZeroInpput();
}


Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
long long isPrime(long long n)
{
    long long i;
    for(i = 2; i < n; i++) if (n % i == 0) return 0;
    return 1;
}

long long fun(long long num)
 {
    num=num+1;
    while(1)
    {
        if(isPrime(num))
            break;
        num++;
    }
    return num;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    long long a;
    cin>>a;
    cout<<fun(a-1);
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<set>
#include<map>
#include<bitset>

using namespace std;
typedef long long ll;
#define i_7 (ll)(1E9+7)
#define i_5 (ll)(1E9+5)
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    else return c+i_7;
}
typedef pair<int,int> i_i;
typedef pair<ll,ll> l_l;
ll inf=(ll)1E12;/*10^12*/
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}

////////////////////////////////////////


int main(){
    int n,k;cin>>n>>k;
    vector<int>e[n];
    i_i edge[n-1];
    rep(i,0,n-2){
        int a,b;cin>>a>>b;a--;b--;
        e[a].pb(b);e[b].pb(a);
        edge[i]=i_i(a,b);
    }
    int ans[n];ans[n-1]=0;
    if(k%2==0){
        rep(i,0,n-1){
            int d[n];rep(j,0,n-1)d[j]=-1;
            d[i]=0;
            queue<int>q;
            q.push(i);
            while(!q.empty()){
                int t=q.front();q.pop();
                for(auto x:e[t]){
                    if(d[x]==-1){
                        d[x]=d[t]+1;
                        q.push(x);
                    }
                }
            }
            int count=0;
            rep(j,0,n-1)if(d[j]<=k/2)count++;
            ans[i]=count;
           // rep(j,0,n-1)cout<<d[j]<<" ";cout<<endl;
        }
    }else{
        rep(i,0,n-2){
            int d[n];rep(j,0,n-1)d[j]=-1;
            d[edge[i].first]=0;d[edge[i].second]=0;
            queue<int>q;
            q.push(edge[i].first);q.push(edge[i].second);
            while(!q.empty()){
                int t=q.front();q.pop();
                for(auto x:e[t]){
                    if(d[x]==-1){
                        d[x]=d[t]+1;
                        q.push(x);
                    }
                }
            }
            int count=0;
            rep(j,0,n-1)if(d[j]<=k/2)count++;
            ans[i]=count;
            // rep(j,0,n-1)cout<<d[j]<<" ";cout<<endl;
        }
    }
    //rep(i,0,n-1)cout<<ans[i]<<" ";cout<<endl;
    int ma=0;
    rep(i,0,n-1)ma=max(ma,ans[i]);
    cout<<n-ma<<endl;
    
    return 0;
}

Measured memory_bytes: 384
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn main(){
    let abc:Vec<i32> = read_vec();
    let ans = if abc[0] + abc[1] >= abc[2] {
        "Yes".to_string()
    } else {
         "No".to_string()
    };
    println!("{}",ans);
}

Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(a,b) for(int a=0;a<b;a++)
#define Sort(a) sort(a.begin(),a.end())
#define rev(a) reverse(a.begin(),a.end())
#define fi first
#define se second
 int wari(int a,int b) {
   if(a%b==0)
     return a/b;
   else
     return a/b+1;
 }
 int keta(int a){
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
 }
 int souwa(int a){
  return a*(a+1)/2;
 }
 int lcm(int a,int b){
  int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return d*e/f;
    }
  int gcm(int a,int b){
      int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return f;
  }
 bool prime(int a){
   if(a<2)
     return false;
   else if(a==2)
     return true;
   else if(a%2==0)
     return false;
   double b=sqrt(a);
    for(int i=3;i<=b;i+=2){
      if(a%i==0){
        return false;
      }
    }
   return true;
 }
signed main(){
  int a,b;
  cin>>a>>b;
  vector<int> c(a),d,e(a,0),f(a,0);
  fo(i,a)
    cin>>c[i];
  d=c;
  fo(i,a)
    d.push_back(c[i]);
  fo(i,a){
    for(int j=i+1;j<a;j++){
      if(c[i]>c[j])
        e[i]++;
    }
  }
  fo(i,a){
    for(int j=i+1;j<2*a;j++){
      if(d[i]>d[j])
        f[i]++;
    }
  }
  long long g=0,h;
  fo(i,a)
    f[i]-=e[i];
  h=b;
    h%=1000000007;
    h*=b-1;
    h/=2;
    h%=1000000007;
  fo(i,a){
    g+=e[i]*b;
    g+=f[i]*h;
    g=g%1000000007;
  }
  cout<<g<<endl;
}

Measured memory_bytes: 384
def main():
    [N, W] = [int(num) for num in input().split()]

    products = []
    v_all = 0
    for i in range(N):
        w_v = [int(num) for num in input().split()]
        products.append(w_v)
        v_all += w_v[1]

    dp = [[10**10] * (v_all+1) for _ in range(N+1)]

    dp[0][0] = 0

    for i in range(N+1):
        if i == 0:
            continue
        for v in range(v_all+1):
            if v < products[i-1][1]:
                dp[i][v] = dp[i-1][v]
            else:
                dp[i][v] = min(dp[i-1][v-products[i-1][1]] + products[i-1][0], dp[i-1][v])

    ans = 0
    for v in range(v_all+1):
        if dp[N][v] <= W:
            ans = v

    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 118768
// https://atcoder.jp/contests/abc149/tasks/abc149_d
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define DIV(a, b) ((a - 1) / b + 1)
// int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
// int lcm(int c, int d) { return c / gcd(c, d) * d; }

enum RSP { RSP_R, RSP_S, RSP_P };

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, K, R, S, P;
    cin >> N >> K >> R >> S >> P;
    string str;
    cin >> str;

    // K回目までは必ず勝てる
    vector<vector<int>> score(N, vector<int>(3));

    // R: グー (Rock)
    // S: チョキ (Scissors)
    // P: パー (Paper)
    REP(i, K) {
        if (str[i] == 'r') {
            // 相手グーなのでパーで勝つ
            score[i][RSP_P] = P;
        } else if (str[i] == 's') {
            // 相手チョキなのでグーで勝つ
            score[i][RSP_R] = R;
        } else if (str[i] == 'p') {
            // 相手パーなのでチョキで勝つ
            score[i][RSP_S] = S;
        }
    }

    FOR(i, K, str.length()) {
        int t = 0;
        REP(j, 3) { t = max(t, score[i - K][j]); }
        if (str[i] == 'r') {
            // 相手グーなのでパーで勝つ
            score[i][RSP_P] = max(score[i - K][RSP_R], score[i - K][RSP_S]) + P;
            score[i][RSP_R] = t;
            score[i][RSP_S] = t;
        } else if (str[i] == 's') {
            // 相手チョキなのでグーで勝つ
            score[i][RSP_R] = max(score[i - K][RSP_S], score[i - K][RSP_P]) + R;
            score[i][RSP_S] = t;
            score[i][RSP_P] = t;
        } else if (str[i] == 'p') {
            // 相手パーなのでチョキで勝つ
            score[i][RSP_S] = max(score[i - K][RSP_R], score[i - K][RSP_P]) + S;
            score[i][RSP_R] = t;
            score[i][RSP_P] = t;
        }
    }
    int ans = 0;
    REP(i, K) {
        int t = 0;
        REP(j, 3) { t = max(t, score[str.length() - 1 - i][j]); }
        ans += t;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 5840
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } else return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } else return 0; }
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 1e9+100;
const ll INFL = 1e18+100;
const ll MOD = 1e9+7;
const bool debug = 0;

string S, T;

int main() {
	cin >> S >> T;
	
	int len = S.size();
	S += S;
	
	
	REP(i, len) {
		if (S.substr(i, len) == T) {
			puts("Yes");
			return 0;
		}
	}
	puts("No");
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<bitset>
#include<ctime>
#include<deque>
#include<stack>
#include<functional>
#include<sstream>
//#include<cctype>
//#pragma GCC optimize(2)
using namespace std;
#define maxn 2000005
#define inf 0x7fffffff
//#define INF 1e18
#define rdint(x) scanf("%d",&x)
#define rdllt(x) scanf("%lld",&x)
#define rdult(x) scanf("%lu",&x)
#define rdlf(x) scanf("%lf",&x)
#define rdstr(x) scanf("%s",x)
typedef long long  ll;
typedef unsigned long long ull;
typedef unsigned int U;
#define ms(x) memset((x),0,sizeof(x))
const long long int mod = 1e9 + 7;
#define Mod 1000000000
#define sq(x) (x)*(x)
#define eps 1e-4
typedef pair<int, int> pii;
#define pi acos(-1.0)
//const int N = 1005;
#define REP(i,n) for(int i=0;i<(n);i++)
typedef pair<int, int> pii;
inline ll rd() {
    ll x = 0;
    char c = getchar();
    bool f = false;
    while (!isdigit(c)) {
        if (c == '-') f = true;
        c = getchar();
    }
    while (isdigit(c)) {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return f ? -x : x;
}
 
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a%b);
}
int sqr(int x) { return x * x; }
 
 
/*ll ans;
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1; y = 0; return a;
    }
    ans = exgcd(b, a%b, x, y);
    ll t = x; x = y; y = t - a / b * y;
    return ans;
}
*/
 
 
int n;
int tot;
struct node {
    int x, y;
    int d;
    node(){}
    node(int x,int y,int d):x(x),y(y),d(d){}
 
}nd[maxn],nd2[maxn];
 
bool cmp(node a, node b) {
    return a.x < b.x;
}
bool cmp2(node a, node b) {
    return a.y < b.y;
}
 
bool cmp3(node a, node b) {
    return a.d < b.d;
}
 
int fa[maxn];
void init() {
    for (int i = 0; i <= n; i++)fa[i] = i;
}
int findfa(int x) {
    if (x == fa[x])return x;
    return fa[x] = findfa(fa[x]);
}
 
void merge(int u, int v) {
    int p = findfa(u);
    int q = findfa(v);
    if (p != q) {
        fa[p] = q;
    }
}
 
bool chk(int x, int y) {
    if (findfa(x) == findfa(y))return true;
    else return false;
}
 
int kruskal() {
    int sum = 0;
    init();
    for (int i = 0; i < tot; i++) {
        node tmp = nd2[i];
        if (tmp.d == 0)merge(tmp.x, tmp.y);
        if (!chk(tmp.x, tmp.y)) {
            merge(tmp.x, tmp.y); sum += tmp.d;
        }
    }
    return sum;
}
 
int main() {
//  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        rdint(nd[i].x); rdint(nd[i].y);
        nd[i].d = i;
    }
    tot = 0;
    sort(nd + 1, nd + 1 + n, cmp);
    for (int i = 2; i <= n; i++) {
        nd2[tot++] = node(nd[i].d, nd[i - 1].d, nd[i].x - nd[i - 1].x);
    }
    sort(nd+1, nd + n+1, cmp2);
    for (int i = 2; i <= n; i++) {
        nd2[tot++] = node(nd[i].d, nd[i - 1].d, nd[i].y - nd[i - 1].y);
    }
    sort(nd2, nd2 + tot, cmp3);
    int sum = kruskal();
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 7588
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

#define int long long

bool canUse(bitset<31> b, int lim){
	rep(i,lim){
		if(b[i]) return false;
	}
	if(not b[lim]) return false;
	return true;
}

signed main(){
	int n;
	cin >> n;

	vector<bitset<31>> a(n);
	vector<bool> used(n,0);
	bitset<31> b(0);
	rep(i,n){
		int in;
		cin >> in;
		a[i] = bitset<31>(in);
		b ^= a[i];
	}

	int ans = 0;
	for(int i = 30; i >= 0; i--){
		if(b[i]){
			int tmp = (1 << (i + 1)) - 1;

			rep(j,n){
				if(used[j]) continue;
				if(not canUse(a[j], i)) continue;
				b ^= tmp;
				ans++;
				break;
			}
		}
	}

	cout << (b == 0 ? ans : -1) << endl;
}


Measured memory_bytes: 1024
/**
 *      purpose : 
 *      author  : kyomukyomupurin
 *      created : 
**/

// input/output
#include <fstream>
#include <iostream>
#include <sstream>
// container class
#include <array>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// math, algorithm
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
// etc
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstring>
#include <chrono>
#include <iomanip>
#include <random>
#include <utility>
// using-directive
using namespace std;
// alias template
using int64 = long long;
using vi = vector<int>;
using vl = vector<int64>;
using pii = pair<int, int>;
using pii = pair<int, int>;
using pll = pair<int64, int64>;
// text macro replacement
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define print(x) cout << (x) << '\n'
#define debug(x) cerr << #x << ": " << (x) << '\n'
#define dbg(v) for (size_t _ = 0; _ < v.size(); ++_){cerr << #v << "[" << _ << "] : " << v[_] << '\n';}
// variadic template
template<typename T> inline void chmin(T &a, T b) {if (a > b) a = b; return;}
template<typename T> inline void chmax(T &a, T b) {if (a < b) a = b; return;}
// constant
const int INF = (1<<30) - 1;
const int64 INF64 = (1LL<<62) - 1;
const int MOD = 1000000007;

int calcdigit(const string &s) {
  int ret = 0;
  for (size_t i = 0; i < s.size(); ++i) {
    ret += s[i] - '0';
  }
  return ret;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  while (1) {
    string s; cin >> s;
    if (s == "0") {
      break;
    } else {
      cout << calcdigit(s) << '\n';
    }
  }

  return 0;
}


Measured memory_bytes: 3136
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

const int MX = 210000;
int bit[MX];
int sum(int i){
	int res = 0;
	for(; i; i -= i & -i) res += bit[i];
	return res;
}
void add(int i, int x){
	for(; i < MX; i += i & -i) bit[i] += x;
}
int find(int k){
	int lo = 0, hi = 1 << 32 - __builtin_clz(MX), mid;
	while(lo + 1 < hi){
		mid = (lo + hi) / 2;
		if(mid > MX || bit[mid] >= k) hi = mid;
		else k -= bit[lo = mid];
	}
	return hi;
}
int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	
	int n; cin >> n;
	vi x(n); rep(i, n) cin >> x[i];
	
	vi v = x;
	sort(all(v)); v.erase(unique(all(v)), v.end());
	rep(i, n){
		x[i] = lower_bound(all(v), x[i]) - v.begin() + 1;
		add(x[i], 1);
	}
	
	rep(i, n){
		add(x[i], -1);
		cout << v[find(n / 2) - 1] << endl;
		add(x[i], 1);
	}
	
	return 0;
}

Measured memory_bytes: 4480
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
ll dp[1005][1005];
int n,a,b,c,d;
ll modpow(ll x,ll n)
{
	ll res=1;
	while(n>0)
	{
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
ll F[100005],R[100005];
void make(){
	F[0] = 1;
	for(int i=1;i<100005;i++) F[i] = F[i-1]*i%mod;
	for(int i=0;i<100005;i++) R[i] = modpow(F[i],mod-2);
}
ll C(int a,int b){
	return F[a]*R[b]%mod*R[a-b]%mod;
}
int main(){
	cin>>n>>a>>b>>c>>d; make();
	dp[0][a-1] = 1;
	for(int i=a;i<=b;i++){
		for(int j=0;j<=n;j++){
			if(dp[j][i-1] == 0) continue;
			dp[j][i] += dp[j][i-1];
			while(dp[j][i]>=mod) dp[j][i]-=mod;
			ll hoge = 1;
			for(int k=1;k<=d;k++){
				if(j+i*k > n) break;
				hoge *= C(n-j-i*(k-1),i); hoge%=mod;
				hoge *= modpow(k,mod-2); hoge%=mod;
				if(k>=c){
    				dp[j+i*k][i] += dp[j][i-1]*hoge%mod;
    				while(dp[j+i*k][i]>=mod) dp[j+i*k][i]-=mod;
				}
				//cout<<j+i*k<<" "<<i<<endl;
				//cout<<dp[j+i*k][i]<<endl;
			}
		}
	}
	cout<<dp[n][b]<<endl;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll, vl/*, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
typedef pair<ll, ll> pl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, n) for(ll i = 1; i <= ll(n); ++i)
//#define rep(i, k, n) for(ll i = k-1; i < ll(n); ++i)
//#define rep2(i, k, n) for(ll i = k; i <= ll(n); ++i)
#define all(v) (v).begin(), (v).end()
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 1e9;
const char newl = '\n';

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  ll k, s, ans=0;
  cin >> k >> s;
  rep(x, k+1) rep(y, k+1) if(s-x-y>=0 && s-x-y<=k) ans++;
  cout << ans << newl;
  return 0;
}

Measured memory_bytes: 256
// <--sbhmsh-- Shubham Jaiswal-->//

  #include <bits/stdc++.h>
  #define FASTIO std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  using namespace std;
  #define endl '\n'
  #define deb cout<<"sab_badhiya"<<endl;
  typedef long long int ll;
  // const long long INF = 1000 * 1000 * 1000 * 1ll * 1000 * 1000 * 1000;
  const long INF = 2000 * 1000 * 1000 + 7;
  vector<pair<int,int>> a;
  bool check(string s) {
    for (int i = 0; i < s.length(); i++) {
      if (s[i] != s[s.length() - i - 1]) {
        return false;
      }
    }
    return true;
  }
  int main() {
    FASTIO
    string s;
    cin >> s;
    int n = (int)s.length();
    // cout << s.substr(0, (n - 1) / 2) << " " << s.substr((n + 3) / 2 - 1, n + 1 - (n + 3) / 2) << endl;
    if (check(s.substr(0, (n - 1) / 2)) && check(s.substr((n + 3) / 2 - 1, n + 1 - (n + 3) / 2)) && check(s)) {
      cout << "Yes" << endl;
    }
    else {
      cout << "No" << endl;
    }
  }


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <iomanip>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <complex>
#include <ctime>


using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef int itn;
const ll LINF = 1e18;
const int INF = 1e9;

//マクロ定義
#define vvint(vec,n,m,l) vector<vector<int>> vec(n, vector<int>(m,l));	// lで初期化
#define vvll(vec,n,m,l) vector<vector<ll>> vec(n,vector<ll>(m,l));
#define vint vector<int>
#define pint pair<int,int>
#define rep(i,a) for(int i=0;i<(a);i++)
#define all(x) (x).begin(),(x).end()
#define debug system("pause")				//デバッグ用
#define ret return 0

template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

using Graph = vector<vector<ll>>;

#define ketasitei setprecision(15) //15桁表示

const ll MOD = 1000000007;
const double PI = 3.1415926535897932;


int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
    cout<<ketasitei;

	int a, b;
	cin >> a >> b;
	int h, m;
	cin >> h >> m;

	double dx, dy;
	double hx, mx, hy, my;
	hx = (double)a * cos(2.0 * PI * ((double)h*60.0 + (double)m)/ 720.0);
	mx = (double)b * cos(2.0 * PI * (double)m / 60.0);
	hy = (double)a * sin(2.0 * PI * ((double)h*60.0+(double)m )/ 720.0);
	my = (double)b * sin(2.0 * PI * (double)m / 60.0);
	dx = abs(hx - mx);
	dy = abs(hy - my);


	
	cout << sqrt(dx * dx + dy * dy) << endl;

	return 0;
}

Measured memory_bytes: 4116
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <map>

int main() {
  size_t N;
  scanf("%zu", &N);

  std::vector<intmax_t> A(N);
  for (auto& ai: A) scanf("%jd", &ai);

  std::vector<intmax_t> B(N);
  for (size_t i = 0; i < N; ++i) {
    if (i % 2 == 0) {
      B[0] += A[i];
    } else {
      B[0] -= A[i];
    }
  }
  for (size_t i = 1; i < N; ++i)
    B[i] = 2*A[i-1] - B[i-1];

  for (size_t i = 0; i < N; ++i)
    printf("%jd%c", B[i], i+1<N? ' ':'\n');
}


Measured memory_bytes: 2816
#include <iostream>
#include <vector>
#include <bitset>

using namespace std;
constexpr int BASE = 80 * 160 + 10;
constexpr int SIZE = BASE * 2 + 1;
using bitflg = bitset<SIZE>;

int main() {
	int h, w;
    cin >> h >> w;
    vector<vector<int>> d(h+1, vector<int>(w+1));
    for(int y=1; y<=h; y++) {
        for(int x=1; x<=w; x++) {
            cin >> d[y][x];
        }
    }
    for(int y=1; y<=h; y++) {
        for(int x=1; x<=w; x++) {
            int b;
            cin >> b;
            d[y][x] = abs(d[y][x] - b);
        }
    }
    vector<vector<bitflg>> b(h+1, vector<bitflg>(w+1));
    b[1][0].set(BASE);
    for(int y=1; y<=h; y++) {
        for(int x=1; x<=w; x++) {
            b[y][x] |= (b[y-1][x] << d[y][x]) | (b[y-1][x] >> d[y][x]) | (b[y][x-1] << d[y][x]) | (b[y][x-1] >> d[y][x]);
        }
    }
    const auto& bt = b[h][w];
    int ans;
    for(int i=0; i<=BASE; i++) {
        if(bt[BASE+i] || bt[BASE-i]) {
            ans = i;
            break;
        }
    }
    cout << ans << endl;
	return 0;
}

Measured memory_bytes: 21248
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define INX(x) (cin >> x)
#define INXV(vec, cnt) for(ll i; i < cnt; i++) INX(vec[i])
#define OUTX(x) (cout << x << endl)
#define OUTXV(vec) for(ll i; i < (ll)vec.size(); i++) OUTX(vec[i])

#define ADD emplace_back
#define MP make_pair
#define VVEC(type) vector<vector<type>>

int main()
{
    string S;
    INX(S);

    S.resize(3);
    OUTX(S);


    return 0;
}


Measured memory_bytes: 3628
n, k = map(int, input().split())

mod = pow(10, 9) + 7

a = list(range(n+1))

def cumulative_sum(array):
    ret = []
    for index, a in enumerate(array):
        if index != 0:
            ret.append(ret[-1] + a)
        else:
            ret.append(a)
    return ret

a_cumulative_sum = cumulative_sum(a)
a_rev_cumulative_sum = cumulative_sum(a[::-1])

ans = 0
for i in range(k, n + 2):
    ans += (a_rev_cumulative_sum[i - 1] - a_cumulative_sum[i - 1] + 1) % mod

ans %= mod
print(ans)

Measured memory_bytes: 97180
#include <bits/stdc++.h>

using namespace std;

int A[1000005];

int main(){
	string str;
	cin >> str;
	int N = str.size();
	for (int i = 0; i < N; i++) {
		A[i] = str[i] - '0';
	}
	int ans = 0;
	int k = -1;
	bool sobra = false;
	for (int i = N - 1; i > 0; i--) {
		if (A[i] < 10 - A[i]) {
			ans += A[i];
		}
		else {
			if ((A[i] == 5) && (A[i - 1] < 5)){
				ans += A[i];
			} else {
				ans += 10 - A[i];
				k = i - 1;
				if (k == 0) sobra = true;
				while (true) {
					if (k == 0) {
						sobra = true;
						break;
					}
					A[k]++;
					if (A[k] == 10) {
						A[k] = 0;
						k--;
					} else {
						break;
					}
				}
			}
		}
	}
	if (sobra) {
		A[0]++;
		if (A[0] == 10) {
			ans++;
			A[0] = 0;
		}
	}
	if (A[0] <= 10 - A[0]) {
		ans += A[0];
	} else {
		ans += 10 - A[0];
		ans++;
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 5252
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
Mod = 1000000007




def main(): #startline--------------------------------------------
    n,x = map(int,input().split())
    a = list(map(int,input().split()))
    ans = 0
    if a[0] > x:
        ans += a[0]-x
        a[0] = x
    for i in range(n-1):
        if a[i+1]+a[i] > x:
            ans += a[i+1]+a[i]-x
            a[i+1] -= a[i+1]+a[i]-x
        else:
            pass
    print(ans) 
if __name__ == "__main__":
    main() #endline===============================================





def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n < 2 is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))):
        if prime[i] == 1:
            for j in range(2*i,n):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n):
        if prime[i] == 1:
            res.append(i)
    return res

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py

    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

Measured memory_bytes: 16228