akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def solve(f):
    a,b,c,x,y = f.read_int_list()

    ans = float('inf')
    ans = min(ans, a*x+b*y)
    ans = min(ans, max(x,y)*2*c)
    if y > x:
        ans = min(ans, x*2*c+(y-x)*b)
    else:
        ans = min(ans, y*2*c+(x-y)*a)

    return ans


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)


Measured memory_bytes: 5144
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for (int i = (a), i##_end_ = (b); i >= i##_end_; ++i)
typedef long long LL;

const int Maxn = 5009;
string s, t;
int len1, len2;
int dp[Maxn][Maxn], fa[Maxn][Maxn];

void output(int Fr, int Fr1) {
	if (Fr == 0 || Fr1 == 0) return ;
	if (fa[Fr][Fr1] == 1) output(Fr - 1, Fr1);
	if (fa[Fr][Fr1] == 2) output(Fr, Fr1 - 1);
	if (fa[Fr][Fr1] == 3) {
		output(Fr - 1, Fr1 - 1);
		printf("%c", s[Fr]);
	}
}

int main() {
//    freopen("F.in", "r", stdin);
  //  freopen("F.out", "w", stdout);

	cin >> s >> t;
	s = '$' + s, t = '#' + t;
	len1 = s.size() - 1, len2 = t.size() - 1;

    rep(i, 1, len1) 
        rep(j, 1, len2) {
			if (dp[i - 1][j] > dp[i][j - 1]) fa[i][j] = 1; else fa[i][j] = 2;
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

            if(s[i] == t[j]) {
				if (dp[i - 1][j - 1] + 1 > dp[i][j]) fa[i][j] = 3;
				dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
			}
        }

	if (dp[len1][len2]) output(len1, len2);
    return 0;
}


Measured memory_bytes: 120960
#ジュっピー
n = int(input())
sp = []#操作用の配列
for i in range(n):
    s,p = map(str,input().split())
    sp.append([s,int(p),i+1])
    #操作用の配列にデータを入れる
    #都市名、得点（整数化）、順番(i)は１始まりに
#ソート順に注意、重要なソートほど、後にする
sp.sort(key=lambda x:x[1],reverse = True)#最初に、得点の降順
sp.sort(key=lambda x:x[0])#重要な都市名の辞書順の昇順ソートは後回し

for e in sp:#操作用配列の１個１個の要素をeとして処理
    print(e[2])#i番目に紹介されるレストランの番号を出力

Measured memory_bytes: 3060
#pragma once
#include <stdio.h>
#include <sstream>
#include <string>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <limits>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define bit(x,v) ((ll)x << v)

const ll INF = 1000000007;
const int MAX = 210000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int pr[100010];
void uini(int n) {
	for (size_t i = 0; i <= n; i++)
	{
		pr[i] = i;
	}
}

int parent(int x) {
	if (x == pr[x]) return x;
	return pr[x] = parent(pr[x]);
}

bool unit(int x, int y) {
	int px = parent(x);
	int py = parent(y);

	if (px == py) return false;
	if (px < py) {
		pr[py] = px;
	}
	else {
		pr[px] = py;
	}
	return true;
}

ll bit[200010];
int max_n = 200000;
int pm = 0;
void add(int x) {

	while (max_n >= x)
	{
		bit[x]++;
		x += x & -x;
	}
}
void sub(int x) {
	while (max_n >= x)
	{
		bit[x]--;
		x += x & -x;
	}
}
int search(int x) {

	int k = 0;
	int p = 1;
	while (p * 2 <= max_n)
	{
		p *= 2;
	}
	for (int i = p; i > 0; i /= 2)
	{
		if (i + k < max_n && bit[i + k] < x) {
			x -= bit[i + k];
			k += i;
		}
	}
	return k + 1;
}
void solv() {

	int n, m, l;
	cin >> n >> m >> l;
	ll tb1[105][105];
	ll tb2[105][105];
	for (size_t i = 0; i < n; i++)
	{
		for (size_t j = 0; j < m; j++)
		{
			cin >> tb1[i][j];
		}
	}

	for (size_t i = 0; i < m; i++)
	{
		for (size_t j = 0; j < l; j++)
		{
			cin >> tb2[i][j];
		}
	}
	ll tb3[105][105];
	memset(tb3, 0, sizeof(tb3));
	for (size_t i = 0; i < n; i++)
	{
		for (size_t j = 0; j < l; j++)
		{
			for (size_t k = 0; k < m; k++)
			{
				tb3[i][j] += tb1[i][k] * tb2[k][j];
			}
		}
	}

	for (size_t i = 0; i < n; i++)
	{
		for (size_t j= 0; j < l; j++)
		{
			if (j > 0) cout << " ";
			cout << tb3[i][j];
		}
		cout << endl;
	}
}
int main() {
	//	COMinit();
	solv();
	return 0;
}



Measured memory_bytes: 3324
//Volume0-0057
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		//declare
		int n;

        //input
        Scanner sc = new Scanner(System.in);
        while((sc.hasNext())){
        	n = sc.nextInt();

        	//output
        	System.out.println(1+n*(1+n)/2);
        }
	}
}

Measured memory_bytes: 17360
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define R register
namespace IO{
	char buf[1<<15],*S,*T;
	inline char gc(){
		if (S==T){
			T=(S=buf)+fread(buf,1,1<<15,stdin);
			if (S==T) return EOF;
		}return *S++;
	}
	inline int read(){
		R int x; R bool f; R char c;
		for (f=0; (c=gc())<'0'||c>'9'; f=c=='-');
		for (x=c^'0'; (c=gc())>='0'&&c<='9'; x=(x<<1)+(x<<3)+(c^'0'));
		return f?-x:x;
	}
}
#define MN 100005
int d[MN],n,ans1,f[MN],h[MN],to[MN<<1],nt[MN<<1],en,rt,a[MN],cnt;bool flag;
inline void ins(int u,int v){to[++en]=v; nt[en]=h[u]; h[u]=en;}
inline void insw(int u,int v){++d[u],++d[v];ins(u,v);ins(v,u);}
inline bool check2(int k,int ln){
	R int l=1,r=cnt;
	if (l==k) ++l;
	if (r==k) --r;
	while(l<r){
		if (a[l]+a[r]>ln) return 0;
		++l,--r;
		if (l==k) ++l;
		if (r==k) --r;
	}return 1;
}
void dfs(int u,int ln,int fa=0){
	for (R int i=h[u]; i; i=nt[i])
		if (to[i]!=fa) dfs(to[i],ln,u);
	cnt=0;for (R int i=h[u]; i; i=nt[i])
		if (to[i]!=fa) a[++cnt]=f[to[i]];
	if (!cnt) return (void)(f[u]=1);
	if (~cnt&1) a[++cnt]=0;
	std::sort(a+1,a+cnt+1);
	R int l=1,r=cnt;while(l<r)
		if (check2(l+r>>1,ln)) r=l+r>>1;
		else l=l+r+2>>1;
	if (l==cnt&&!check2(cnt,ln)) flag=0;
	f[u]=a[l]+1;
}
inline bool check(int len){
	flag=1;dfs(rt,len);
	return flag&&f[rt]<=len+1;
}
int main(){
	n=IO::read();for (R int i=1; i<n; ++i) insw(IO::read(),IO::read());
	for (R int i=1; i<=n; ++i) if (d[i]&1) rt=i,++ans1;
	ans1>>=1;R int l=1,r=n;while(l<r)
		if (check(l+r>>1)) r=l+r>>1;else l=l+r+2>>1;
	printf("%d %d\n",ans1,l);
	return 0;
}

Measured memory_bytes: 7552
/******************************\
*  Everyone has a different way of thinking, so God Created us
Hope You Respect My Way..,Thank You ):  *
*                            *
*   Created by : Murad   *
\******************************/
//std::transform(s1.begin(), s1.end(), s1.begin(),::tolower);
#include<bits/stdc++.h>
using namespace std;
#define pi 3.1415926536
#define forn(i,a,b)for(int i=a;i<b;i++)
#define LL long long
#define MP make_pair
#define ff first
#define ss second
#define INF 2147483647
#define _INF -2147483647
#define pq priority_queue
#define MM multimap
#define PB push_back
#define ipair pair<int,int>
#define lpair pair<LL,LL>
#define MAXN 100004
#define El3zba ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define modd 1000000007
LL MMIN(LL a, LL b)
{
	if (a <= b)
		return a;
	else
		return b;
}
LL MMAX(LL a, LL b) {
	if (a >= b)
		return a;
	else
		return b;
}
int main()
{
	El3zba;
	int n;
	cin >> n;
	int ans = 0;
	if (n < 10)return cout << n << endl, 0;
	for (int i =1; i <= n; i++)
	{
		string s = to_string(i);
		if (s.length() % 2 != 0)
			ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int MOD=1e9+7;
const double pi=acos(-1);


int main(){
  int n;
  cin >> n;
  vector<string>ans;
  stack<string>st;
  st.emplace("a");
  while(!st.empty()){
    string t=st.top();
    st.pop();
    int m=t.size();
    if(m==n){
      ans.push_back(t);
    }
    else{
      char c=*max_element(t.begin(),t.end());
      c++;
      for(auto d='a';d<=c;d++){
        string s=t+d;
        st.emplace(s);
      }
    }
  }
  sort(ans.begin(),ans.end());
  ans.erase(unique(ans.begin(),ans.end()),ans.end());
  rep(i,ans.size()){
    cout << ans[i] << endl;
  }
  
}


Measured memory_bytes: 9588
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vint = vector<int>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vchar = vector<char>;
using vvchar = vector<vchar>;
using vp = vector<P>;
using vpp = vector<pair<P, P>>;
using vvp = vector<vp>;

#define rep(i, n) for (int i = 0; i < n; ++i)
#pragma region Debug
istream &operator>>(istream &is, P &a)
{
    return is >> a.first >> a.second;
}
ostream &operator<<(ostream &os, const P &a) { return os << "(" << a.first << "," << a.second << ")"; }

template <typename T>

void view(const std::vector<T> &v)
{
#ifndef ONLINE_JUDGE
    for (const auto &e : v)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;
#endif
}
template <typename T>
void view(const std::vector<std::vector<T>> &vv)
{
    for (const auto &v : vv)
    {
        view(v);
    }
}
#pragma endregion

const int MAX_VAL = 1e6 + 5;
int main()
{
    int k;
    cin >> k;
    ll x = 7;
    ll ans = 1;
    rep(i, MAX_VAL)
    {
        if (!(x % k))
            break;
        x = (x * 10) % k;
        x += 7;
        x %= k;
        ans++;
    }

    if (ans - 1 == MAX_VAL)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
	int n,p,sum = 0;
	vector<int> vec;
	cin >> n >> p;
	for(int i = 0;i < n;i++){
		int w,b;
		cin >> w >> b;
		sum -= b * p;
		vec.push_back((100 - p) * w + p * b);
	}
	sort(vec.begin(),vec.end(),greater<int>());
	for(int i = 0;i < n;i++){
		if(sum >= 0){
			cout << i << endl;
			return 0;
		}
		sum += vec[i];
	}
	cout << n << endl;
	return 0;
}

Measured memory_bytes: 1528
#include <iostream>
using namespace std;

int D[9][9];
int V[9];
int pathCount;

void dfs(int s,int N,int depth){
  
  if(depth==N){
    pathCount++;
    return ;
  }

  for(int i=2;i<=N;i++){
    if(D[s][i]==1&&V[i]==0){
      V[i]=1;
      dfs(i,N,depth+1);
      V[i]=0;
    }
  }
  
}

int main(){
  int N,M;
  cin>>N>>M;

  for(int i=0;i<M;i++){
    int ai,bi;
    cin>>ai>>bi;
    D[ai][bi]=D[bi][ai]=1;
  }

  pathCount =0;
  V[1]=1;
  dfs(1,N,1);

  cout<<pathCount<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;

int main(){
    int n,i,j;
    i=0;
    while( cin >> n ){
        int f[5], s[5];
        if(i) cout << endl;
        for(i=4;i>=0;i--){
            f[i] = n%10/5;
            s[i] = n%5;
            n /= 10;
        }
        for(i=0;i<5;i++){
            if(!f[i]) cout << "*";
            else cout << " ";
        }
        cout << endl;
        for(i=0;i<5;i++){
            if(f[i]) cout << "*";
            else cout << " ";
        }
        cout << endl;
        cout << "=====" << endl;
        for(i=0;i<5;i++){
            for(j=0;j<5;j++){
                if(s[j]==i) cout << " ";
                else cout << "*";
            }
            cout << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1152
/**
 *   author: malviyanshiv
 *   created: 09 January 2019  23:27:27
**/

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for(int i = a; i < b; i++)
#define RREP(i, a, b) for(int i = a-1; i >= b; i--)
#define PB push_back
#define MP make_pair
#define MOD 1000000007
#define INF 0x7fffffff
#define MAX 100005

typedef long long ll;
typedef pair< int, int > PII;

void fastscan(int &x){
    bool neg=false;
    register int c;
    x =0;
    c=getchar();
    if(c=='-'){
        neg = true;
        c=getchar();
    }
    for(;(c>47 && c<58);c=getchar())
        x = (x<<1) + (x<<3) +c -48;
    if(neg)
        x *=-1;
}

void optimizeIO(){
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
}

int dp[MAX][2][2][2];
int h[MAX][3];

int cal(int idx, int a, int b, int c){
    if( idx < 0 )
        return 0;
    int &res = dp[idx][a][b][c];
    if( res )
        return res;
    if( a != 1 )
        res = max( res, cal(idx-1, a+1, 0, 0) + h[idx][0] );
    if( b != 1 )
        res = max( res, cal(idx-1, 0, b+1, 0) + h[idx][1] );
    if( c != 1 )
        res = max( res, cal(idx-1, 0, 0, c+1) + h[idx][2] );
    return res;
}

int main(){
	optimizeIO();
    int n, a, b, c;
    cin >> n;
    REP(i, 0, n)
        cin >> h[i][0] >> h[i][1] >> h[i][2];

    cout << max( max( cal(n-2, 0, 0, 1) + h[n-1][2], cal(n-2, 1, 0, 0) + h[n-1][0]) , cal(n-2, 0, 1, 0) + h[n-1][1] ) << endl;
	
	return 0;
}


Measured memory_bytes: 13952
import sys
input = sys.stdin.readline
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
cnt = Counter(A)
l = []
ans = 0

for k in cnt.keys():
    if cnt[k]>=4:
        ans = max(ans, k*k)
    
    if cnt[k]>=2:
        l.append(k)

l.sort(reverse=True)

if len(l)>=2:
    ans = max(ans, l[0]*l[1])

print(ans)

Measured memory_bytes: 64920
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
a = list(map(int, input().split()))

class SegTree:
  def segfunc(self, x, y):
    return max(x, y)
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res

seg = SegTree(N + 1, -1, [-1] + a)
for _ in range(Q):
  t, x, v = map(int, input().split())
  if t == 1: seg.update(x, v)
  if t == 2: print(seg.query(x, v + 1))
  if t == 3:
    ok = N + 1
    ng = x - 1
    while ok - ng > 1:
      m = (ok + ng) // 2
      if seg.query(x, m + 1) >= v: ok = m
      else: ng = m
    print(ok)

Measured memory_bytes: 102720
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#include <iomanip>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << endl
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
int dx8[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy8[8] = {0, 1, 0, -1, 1, 1, -1, -1};
int dx4[4] = {1, 0, -1, 0};
int dy4[4] = {0, 1, 0, -1};
template <class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template <class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val){ fill((T*)array, (T*)(array+N), val); }
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };


int main()
{
  int N;
  cin >> N;
  
  string S[N];
  
  ll ABCount=0;
  ll ACount=0;
  ll BCount=0;

  rep(i,N){
      cin >> S[i];
  }
  bool flag = false;
  rep(i,N){
      rep(j,S[i].length()-1){
          if(S[i][j] == 'A' && S[i][j+1] == 'B') ABCount++;
      }
      if(S[i][0] == 'B') BCount++;
      if(S[i][S[i].length()-1] == 'A') ACount++;
      //すべてB---Aみたいになっていれば結果から-1しなければならない、環状につながない限りこの場合ABをすべて使えない
      //↓はB--or--Aならflagがtrue、B--Aならflagがfalseのまま
      if((S[i][0] == 'B' || S[i][S[i].length()-1] == 'A') && !(S[i][0] == 'B' && S[i][S[i].length()-1] == 'A')) flag=true;
  }

  ll ans=0;
  ans += ABCount;
  ans += min(ACount,BCount);
  if(!flag&&min(ACount,BCount)) ans-=1;

  fin(ans);
  
}



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

#define int long long

template<class T>
void Add(T &a, const T &b, const T &mod=1000000007) {
  int val = ((a % mod) + (b % mod)) % mod;
  if (val < 0) { val += mod; }
  a = val;
}

// ------------------------------------------------------------------------------------------

string K;
int D;
int dp[11111][2][111]; // dp[i桁目][未満フラグ][mod Dした値] = 総数

signed main() {
  cin >> K >> D;

  dp[0][0][0] = 1; // 初期化
  // DP
  for (int digit = 0; digit < K.size(); digit++) {
    for (int smaller : {0, 1}) {
      for (int modD = 0; modD < D; modD++) {
        int lim = (smaller ? 9 : K[digit] - '0');
        for (int num = 0; num <= lim; num++) {
          int nSmaller = smaller || (num < lim);
          if (smaller == 1 && nSmaller == 0) continue;
          Add(dp[digit+1][nSmaller][(modD + num) % D], dp[digit][smaller][modD]);
        }
      }
    }
  }

  int ans = 0;
  for (int smaller : {0, 1}) {
    Add(ans, dp[K.size()][smaller][0]);
  }

  Add(ans, -1LL); // 0になる場合の数を引く
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 18688
#include <iostream>

using namespace std;
int arr[100005];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", arr + i);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        int j = i + 1;
        while (j < n && arr[j] <= arr[j - 1]) ++j;
        ans = max(ans, j - i - 1);
        i = j - 1;
    }
    printf("%d",ans);
}

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

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int R, G, B, N;
	long long ans=0;
	cin>>R>>G>>B>>N;
	for(int i=0;i<=N/R;i++) for(int j=0;j<=(N-i*R)/G;j++) ans+=(N-R*i-G*j)%B==0;
	cout<<ans<<'\n';
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <queue>
#include <cmath>

using namespace std;
using ll = long long;
using ull = unsigned long long;


void ABC061D()
{
	int N, M;
	cin >> N >> M;

	struct Edge {
		int from_;
		int to_;
		ll score_;
	};

	vector<Edge> graph(M);
	for (int i = 0; i < M; ++i)
	{
		int a, b;
		ll c;
		cin >> a >> b >> c;
		graph[i] = Edge{a - 1, b - 1, c };
	}

	constexpr ll INIT = -1000000000000000;
	vector<ll> dist(N, INIT);
	dist[0] = 0;
	int i = 0;
	ll distN = -1000000000000000;
	for (; i < 2 * N; ++i)
	{
		bool updated = false;
		for (int j = 0; j < M; ++j)
		{
			Edge e = graph[j];
			if (dist[e.from_] != INIT && dist[e.to_] < dist[e.from_] + e.score_)
			{
				dist[e.to_] = dist[e.from_] + e.score_;
				updated = true;
			}
		}
		if (!updated)
			break;
		if (i == N - 1)
		{
			distN = dist[N - 1];
		}
	}
	if (i == 2 * N && dist[N-1] != distN)
	{
		cout << "inf" << endl;
		return;
	}
	cout << dist[N - 1] << endl;

}

int main()
{
	ABC061D();
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using lint = long int;
using llint = long long int;
using namespace std;

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

    string s;
    cin >> s;
    if (s[2] == s[3] && s[4] == s[5]) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
//
//  main.cpp
//  ABC167F
//
//  Created by TakahiroUryu on 2020/06/14.
//  Copyright © 2020 TakahiroUryu. All rights reserved.
//

#include <iostream>
#include <vector>
#include <string>
using namespace std;
using P=pair<int,int>;
bool check(vector<P> s){
    int h=0;
    for (P p:s) {
        int b=h+p.first;
        if(b<0) { // 最下点がマイナスになるならフォルス
            return false;
        }
        h+=p.second;
    }
    return true;
}
int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    vector<P> ls,rs; // 左側と右側
    int total =0;
    for (int i=0; i<n; i++) {
        string s;
        cin >> s;
        int h=0; // 最終点
        int b=0; // 最下点
        for (char c:s) {
            if(c=='('){
                h++;
            }else{
                h--;
            }
            b=min(b,h);
        }
        if (h>0) {
            ls.emplace_back(b,h);
        }else{
            rs.emplace_back(b-h,-h);
        }
        total += h;
    }
    sort(ls.rbegin(),ls.rend()); // 最下点の大きい順にソート
    sort(rs.rbegin(),rs.rend());
    if (check(ls)&&check(rs)&&total==0) {
        cout <<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}


Measured memory_bytes: 18484
if __name__ == '__main__':
    N, A = map(int, input().split())
    x = list(map(int, input().split()))

    x.insert(0, 0)

    dp = [[[0 for _ in range(N * A + 1)] for _ in range(N + 1)] for _ in range(N + 1)]
    for i in range(N + 1):
        dp[i][0][0] = 1

    for i in range(1, N + 1):
        for j in range(1, i + 1):
            for k in range(1, N * A + 1):
                dp[i][j][k] = dp[i - 1][j][k]
                if k >= x[i]:
                    dp[i][j][k] += dp[i - 1][j - 1][k - x[i]]

    ans = 0
    for j in range(1, N + 1):
        ans += dp[N][j][A * j]

    print(ans)


Measured memory_bytes: 95196
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T>
using vec = std::vector<T>;

int main() {
    string N;
    cin >> N;
    bool A = N[0]==N[1]&&N[0] == N[2];
    bool B = N[1]==N[2]&&N[1] == N[3];
    cout << ((A||B)?"Yes":"No") << endl;
}

Measured memory_bytes: 384
N, M = map(int, input().split())
A = [list(input()) for _ in range(N)]
B = [list(input()) for _ in range(M)]

import numpy as np
A = np.array(A)
B = np.array(B)
# print(A)
# print()
# print(B)
# print()

if N==M:
    if np.all(A==B):
        print('Yes')
    else:
        print('No')
else:
    for i in range(N-M):
        for j in range(N-M):
    #         print(i,j)
            a = A[i: i+M, j: j+M]
    #         print(a)
    #         print()
            if np.all(a == B):
                print('Yes')
                break
        else:
            continue
        break
    else:
        print('No')

Measured memory_bytes: 12460
#include <stdio.h>

void swap(int* a, int* b) {
  int temp = 0;
  
  temp = *a;
  *a = *b;
  *b = temp;
}

int main(){
  int a, b, c = 0;
  
  scanf("%d %d %d", &a, &b, &c);
  
  swap(&a, &b);
  swap(&a, &c);
  
  printf("%d %d %d", a, b, c);
}

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

typedef long long ll;
#define inf 1e9+7

int n;
ll dp[102][102];
ll p[102];

void init(){
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            dp[i][j]=inf;
        }
        dp[i][i]=0;
    }
}

void cal(int l, int r){
    if(l>=r)return;
    if(dp[l][r]<inf)return;
    for(int k=l;k<r;k++){
        cal(l,k);
        cal(k+1,r);
        dp[l][r] = min(dp[l][r], dp[l][k]+dp[k+1][r]+p[l]*p[k+1]*p[r+1]);
    }
}

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

    cin >> n;
    init();
    cin >> p[0] >> p[1];
    ll a,b;
    for(int i=1;i<n;i++){
        cin >> a >> b;
        p[i+1]=b;
    }
    cal(0,n-1);
    cout << dp[0][n-1] << endl;
    return 0;
}



Measured memory_bytes: 3220
#include<stdio.h>
#include<string.h>
int main()
{
 char a[100],b[100],c[100],x,y,z;
 scanf("%s %s %s",a,b,c);
 x=strlen(a);
 y=strlen(b);
 z=strlen(c);
 if(a[x-1]==b[0] && b[y-1]==c[0])
  printf("YES\n");
else
  printf("NO\n");
return 0;
}


Measured memory_bytes: 128
X, Y = [int(arg) for arg in input().split()]

def f(X, Y):
    for i in range(X + 1):
        for j in range(X + 1):
            kame = i
            tsuru = j
            if kame + tsuru == X and kame * 4 + tsuru * 2 == Y:
                return 'Yes'
    return 'No'

print(f(X, Y))

Measured memory_bytes: 9044
#include<iostream>
using namespace std;

int main(){
	int a,b;
	cin>>a>>b;
	if(a<b){
		cout<<"a < b"<<endl;
}else if(a>b){
	cout<<"a > b"<<endl;
}else{
	cout<<"a == b"<<endl;
}
	return 0;
}

Measured memory_bytes: 1156
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;
int x[200];
int main(void){
    char s[100001];
    cin>>s;
    int l=strlen(s);
    for(int i=0;i<l;i++){
        x[s[i]]++;
    }
    int i;
    for(i='a';i<='z'&&x[i];i++);
    if(i>'z')cout<<"None\n";
    else cout<<(char)i<<endl;
    
}


Measured memory_bytes: 384
/*
 * TogglingCases.cpp
 *
 *  Created on: 2014/07/27
 *      Author: WanWan1985
 */
#include <iostream>
#include <cctype>
using namespace std;

int main(void) {

	string strInput = "";
	getline(cin, strInput);

	for (unsigned int i = 0; i < strInput.size(); i++) {

		char ch = strInput.at(i);
		if (islower(ch)) {			// 小文字
			ch = toupper(ch);
		} else if (isupper(ch)) {	// 大文字
			ch = tolower(ch);
		}
		cout << ch;
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 1184
#include<bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
const ll MOD = 1000000007;
 
int main() {
  string s;
  cin >> s;
  cout << s.substr(0, 4) << " " << s.substr(4) << endl;
  return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int w, h;
  cin >> w >> h;
  vector<pair<int, int>> v;
  for (int i = 0; i < w; i++) {
    int x;
    cin >> x;
    v.emplace_back(x, 0);
  }
  for (int i = 0; i < h; i++) {
    int x;
    cin >> x;
    v.emplace_back(x, 1);
  }
  sort(v.begin(), v.end());
  w++;
  h++;
  long long ans = 0;
  for (auto i : v) {
    if (i.second) ans += 1LL * w * i.first, h--;
    else ans += 1LL * h * i.first, w--;
  }
  cout << ans << endl;
  return 0; 
}

Measured memory_bytes: 2420
#include <iostream>
using namespace std;

int main(){
  string S;
  cin >> S;
  for (long i=0; i<S.length(); i++){
    if(i % 2 == 0){
      if(S[i] == 'L') {
        cout << "No" << endl;
        exit(0);
      }
    }
    else{
      if(S[i] == 'R'){
        cout << "No" << endl;
        exit(0);
      }
    }
  }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,s;
bool check(ll base)
{
    ll tmp=n;
    ll ans=0;
    while(tmp)
    {
        ans+=tmp%base;
        tmp/=base;
    }
    return ans==s;
}
bool check(ll i,ll sum)
{
    ll a1=s-i;//x0
    ll a2=sum/i+1;//b
    if(a1>=0&&a1<a2&&i<a2)return 1;
    return 0;
}
int main()
{
    scanf("%lld%lld",&n,&s);
    /*第一种情况
    x0+x1*b^1+x2*b^2+...=n
    x0+x1+x2+...=s
    这个时候b^2<=n
    所以b<=根号n
    这个时候暴力枚举即可
    */
    ll Sn=(ll)(sqrt(n))+1;
    ll base;
    for(base=2;base<=Sn;base++)
    {
        if(check(base))
        {
            printf("%lld\n",base);
            return 0;
        }
    }
    /*
    第二种情况
    */
    if(n<=s)
    {
        if(n==s)
        {
            printf("%lld\n",n+1);
        }else
        {
            printf("-1\n");
        }
        return 0;
    }
    /*
    第三种情况暴力枚举
    x0+x1*b^1=n;
    x0+x1=s;
    这个时候联立二式子
    得到x1*(b-1)=n-s
    我们枚举x1，然后判断是否成立，包括题目条件以及进制常识
    */
    ll sum=n-s;
    ll up=sum/Sn+1;
    for(ll i=up;i>=1;i--)
    {
        if(!(sum%i)&&(check(i,sum)))
        {
            printf("%lld\n",sum/i+1);
            return 0;
        }
    }
    printf("-1\n");
    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
const long double PI = acos(-1.0L);
const long long MOD = 1000000007LL;
// const long long MOD = 998244353LL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
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; }
///////////////////////////////////////////////////////////////////////////////////////////////////

class UnionFind {
public:
  vector <ll> par;
  vector <ll> siz;
  UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
    for (ll i = 0; i < sz_; ++i) par[i] = i;
  }
  void init(ll sz_) {
    par.resize(sz_);
    siz.assign(sz_, 1LL);
    for (ll i = 0; i < sz_; ++i) par[i] = i;
  }
  ll root(ll x) {
    while (par[x] != x) {
      x = par[x] = par[par[x]];
    }
    return x;
  }
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }
    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }
    ll size(ll x) {
        return siz[root(x)];
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N; cin >> N;
    vector<int> xx(N),yy(N);
    vector<pii> x(N),y(N);
    rep(i,N) {
        cin >> xx[i] >> yy[i];
        x[i] = make_pair(xx[i],i);
        y[i] = make_pair(yy[i],i);
    }

    UnionFind uf(N);
    sort(all(x)); sort(all(y));
    for (int i = 1; i < N; i++) {
        if (x[i].first == x[i-1].first) {
            uf.merge(x[i].second,x[i-1].second);
        }
        if (y[i].first == y[i-1].first) {
            uf.merge(y[i].second,y[i-1].second);
        }
    }

    vector<set<int>> dicx(N),dicy(N);
    rep(i,N) {
        dicx[uf.root(i)].emplace(xx[i]);
        dicy[uf.root(i)].emplace(yy[i]);
    }
    ll ans = -N;
    rep(i,N) {
        ans += (ll)dicx[i].size() * (ll)dicy[i].size();
    }

    cout << ans << endl;
}

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

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pl;

const int INT_INF = 2147483646;
const ll LL_INF = 9223372036854775807;

bool SecondCompare(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second<b.second;
}
 
bool SecondCompareDes(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second>b.second;
}

ll minll(ll a, ll b){
    if(a >= b)  return b;
    else    return a;
}

ll maxll(ll a, ll b){
    if(a >= b)  return a;
    else    return b;
}

ll gcd(ll a, ll b){
    ll tmp;
    if(a%b == 0){
        return b;
    }
    else{
        return gcd(b, a%b);
    }
}


const ll SIZE = 1e5+10;
ll n;

int main(){
    cin >> n;
    for(int i = 1; i <= 9; i++){
        for(int j = 1; j <= 9; j++){
            if(n == i*j){
                cout << "Yes\n";
                return 0;
            }
        }
    }

    cout << "No\n";
}

Measured memory_bytes: 256
#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <string>
    #include <numeric>
    using namespace std;
     
    int main(){
     
        long long sx, sy, tx, ty;
        cin >> sx >> sy >> tx >> ty;
     
        string s;
        for(int i = 0; i < ty-sy; i++ ){
            s.push_back('U');
        }
        for(int i = 0; i < tx-sx; i++ ){
            s.push_back('R');
        }
        for(int i = 0; i < ty-sy; i++ ){
            s.push_back('D');
        }
        for(int i = 0; i < tx-sx; i++ ){
            s.push_back('L');
        }
     
        s.push_back('L');
        for(int i = 0; i < ty-sy + 1; i++ ){
            s.push_back('U');
        }
        for(int i = 0; i < tx-sx + 1; i++ ){
            s.push_back('R');
        }
        s.push_back('D');
        s.push_back('R');
        for(int i = 0; i < ty-sy+1; i++ ){
            s.push_back('D');
        }
        for(int i = 0; i < tx-sx+1; i++ ){
            s.push_back('L');
        }
        s.push_back('U');
     
        cout << s << endl;
     
     
    }

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

using namespace std;
int dp[10000];
int a[1005],b[1005],n,m;
int ans;

void dfs(int pos,int d,int cost)
{
    if(dp[d]!=-1&&cost>dp[d]) return;
    dp[d] = cost;
    if(pos>=m||d>=ans) return;
    dfs(pos+1,d|b[pos],cost+a[pos]);
    dfs(pos+1,d,cost);
}

int main()
{
    memset(dp,-1,sizeof(dp));
    scanf("%d%d",&n,&m);
    int ta,tb;
    ans = 1<<n;--ans;

    for(int i=0;i<m;++i){
        scanf("%d%d",a+i,&tb);
        for(int j=0;j<tb;++j){
            scanf("%d",&ta);
            b[i]|=(1<<(ta-1));
        }
    }
    dfs(0,0,0);
    printf("%d\n",dp[ans]);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int main(){
	string s;
	cin >> s;
	if((s[0] != s[1]) && (s[1] != s[2]) && (s[2] != s[0])) cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define mp make_pair
#define pb(x) push_back(x)
#define vi vector<int>
#define vs vector<string>
#define vll vector<long long>
#define vc vector<char>
#define vs vector<string>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define pcc pair<char, char>
#define pdd pair<double, double>
#define mll map<long long, long long>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define flsh fflush(stdout)
#define gcd __gcd
#define clr(x) memset(x, 0, sizeof(x))
#define mod 1000000007LL
#define mod2 998244353LL
#define INF 1000000000007
 

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> o_tree;


void solve()
{
   ll n,k;
   cin>>n>>k;
   ll res=0;
   ll i;
   
   for(i=0;i<n;i++)
   {
       ll x;
       cin>>x;
       if(x>=k)
       {
           res++;
       }
   }
   cout<<res<<"\n";
}


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


if (fopen("input.txt","r" ))
  {
     freopen("input.txt", "r", stdin);
     freopen("output.txt", "w", stdout);
  }
cout<<setprecision(20);


ll t=1;


// cin>>t;


while(t--)
{
solve();
} 


return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#define s 100
int main()
{
  int i,j,p,key,N,A[s];
  scanf("%d",&N);
  for(i=0;i<N;i++)
    scanf("%d",&A[i]);
  for(i=0;i<N;i++){
    key=A[i];
    /* insert A[i] into the sorted sequence A[0,...,j-1] */
    j=i-1;
    while(j>=0&&A[j]>key){
      A[j+1]=A[j];
      j--;
    }
    A[j+1]=key;
    for(p=0;p<N;p++){
      if(p>=1) printf(" ");
      printf("%d",A[p]); 
    }
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 604
#include<iostream>
using namespace std;

int main(){
    int N;
    long long A[105];
    long long min,max;

    cin>>N;
    for(int i=0; i<N;i++){
        cin>>A[i];
    }
    min=A[0];
    max=A[0];

    for(int i=0;i<N;i++){
        if(min>A[i]){
            min=A[i];
        }
        if(max<A[i]){
            max=A[i];
        }
    }
    cout << max-min << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#include<assert.h>
#include<chrono>
#include<random>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
template<typename T>inline void chkmin(T &x,T y){x=x<y?x:y;}
template<typename T>inline void chkmax(T &x,T y){x=x>y?x:y;}
const int mod=998244353;
const int MAXN=3005;
void ad(int &x,int y){x+=y;if(x>=mod)x-=mod;}
void dl(int &x,int y){x-=y;if(x<0)x+=mod;}
int n,S,a[MAXN],f[MAXN][MAXN];
int main()
{
	n=read();S=read();
	for(int i=1;i<=n;i++)a[i]=read();
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		memcpy(f[i],f[i-1],sizeof(f[i]));
		for(int j=S-a[i];j>=1;j--)if(f[i-1][j])
		{
			if(j+a[i]!=S)ad(f[i][j+a[i]],f[i-1][j]);
			else
			{
				ad(ans,1LL*n*f[i-1][j]%mod);
				dl(ans,1LL*(i-1)*f[i-1][j]%mod);
			}
		}
		if(a[i]==S)ad(ans,1LL*i*(n-i+1)%mod);
		else if(a[i]<S)ad(f[i][a[i]],i);
	}pr2(ans);
	
	return 0;
}



Measured memory_bytes: 35456
N = int(input())
A = list(map(int, input().split()))

from collections import Counter

ctr = Counter(A)

if N % 2 and ctr[0] != 1:
    print(0)
    exit()

if N % 2 == 0:
    for i in range(1, N ,2):
        if ctr[i] != 2:
            print(0)
            exit()
else:
    for i in range(2, N, 2):
        if ctr[i] != 2:
            print(0)
            exit()

MOD = 10 ** 9 + 7
ans = 2 ** (N//2) % MOD
print(ans)

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

int main()
{
	int64_t n10,n9,n8;
	const int modulo=1000000000+7;

	int n;
	cin >> n;

	if (n==1)
	{
		cout << 0 << endl;
		return 0;
	}

	n10=1;
	n9=1;
	n8=1;
	for (int i=0;i<n;++i)
	{
		n10*=10;
		n10%=modulo;
		n9*=9;
		n9%=modulo;
		n8*=8;
		n8%=modulo;
	}

	n10-=n9*2;
	n10+=n8;
	n10+=modulo;
	n10+=modulo;
	n10%=modulo;
	cout << n10 << endl;
}






Measured memory_bytes: 3632
while True:
  H, W = map(int, input().split())
  if H == 0 and W == 0:
    break
  for i in range(H):
    for j in range(W):
      if i == 0 or i == H-1 or j == 0 or j == W-1:
        print("#", end="")
      else:
        print(".", end="")
    print()
  print()


Measured memory_bytes: 7000
a, b, c ,k = map(int,input().split())
ans = 0
if a<=k:
  ans += a
  k -=a
else:
  print(k)
  exit()

if b<k:
  k -=b
else:
  print(ans)
  exit()

if c<=k:
  ans -=c
else:
  ans -= k
print(ans)

Measured memory_bytes: 61812
# row = [int(x) for x in input().rstrip().split(" ")]
# n = int(input().rstrip())
# s = input().rstrip()

def resolve():
    import sys
    input = sys.stdin.readline

    s = input().rstrip()

    g = []
    if s[0] != s[1]:
        g.append(1)
        g.append(2)
        if s[1] == s[2]:
            g.append(2)
        else:
            g.append(3)
    else:
        g.append(1)
        g.append(1)
        g.append(2)


    for i in range(3, len(s)):
        if s[i] == s[i-1]:
            g.append(g[i-3]+2)
        else:
            g.append(g[i-1]+1)

    print(g[len(g)-1])




if __name__ == "__main__":
    resolve()


Measured memory_bytes: 86432
use std::io;
use std::io::{stdout, Write};
use std::cmp;

fn main() {
    let mut X = String::new();
    let mut P = String::new();
    io::stdin().read_line(&mut X);
    io::stdin().read_line(&mut P);
    let mut vec :Vec<&str> = X.trim().split_whitespace().collect();
    let mut x :usize = vec[0].parse().unwrap();
    let mut n :usize = vec[1].parse().unwrap();
    let mut vecP :Vec<usize> = P.trim().split_whitespace().map(|e| e.parse::<usize>().unwrap()).collect();
    let mut x1 :usize = x;
    let mut x2 :usize = x;
    loop{
        if x1 == 0{
            println!("{}",x1);
            return()
        }else if !vecP.contains(&x1){
            println!("{}",x1);
            return()
        }else if !vecP.contains(&x2){
            println!("{}",x2);
            return()
        }
        x1 -=1;
        x2 +=1;
    }
}

Measured memory_bytes: 2144
#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int minus = 0;
    long long a[n];
    long long min = LLONG_MAX;
    int p = -1;
    for (int i=0; i < n; i++) {
        cin >> a[i];
        if (a[i] < 0) minus++;
        if (abs(a[i]) < min) {
            min = abs(a[i]);
            p = i;
        }
    }
    long long x = 0;
    if (minus % 2 == 0) {
        for (int i = 0; i < n; i++) {
            x += abs(a[i]);
        }
    } else {
        for (int i = 0; i < n; i++) {
            if (i == p) {
                if (a[i] > 0) {
                    x -= a[i];
                } else {
                    x += a[i];
                }
            }
            else {
                x += abs(a[i]);
            }
        }
    }
    cout << x << endl;
}

Measured memory_bytes: 3884
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL<<60;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP2(i,m,n) for(int i=m;i<n;i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

int main(){
    int n;
    string s,t;
    cin >>n;
    cin>>s;
    cin>>t;

    int tmp=0;
    int ans=-1;
    REP2(i,1,n+1){
        if(s.substr(n-i,i)==t.substr(0,i)){
            tmp=i;
        } 
       
    }
    
    
    
    cout<<2*n-tmp<<endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string n;
  cin >> n;

  int sum = 0;
  for(char a : n){
    int ia = a - '0';
    sum += ia;
  }
  
  //cout << sum << endl;
  
  if(sum%9 == 0 || sum == 0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  
  
  return 0; 
}

Measured memory_bytes: 3684
import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque

if __name__ == '__main__':
    s= input()
    ans = int(s[:4]+s[5:7]+s[8:])
    if ans > 20190430:
        print("TBD")
    else:
        print("Heisei")




Measured memory_bytes: 3828
cards = [s + str(i+1) for i in range(13) for s in ['S ','H ','C ','D ']]
n = int(input())
for i in range(n): cards.remove(input())
for i in cards[:]:
	if i.startswith('S'): 
		print(i)
		cards.remove(i)
for i in cards[:]:
	if i.startswith('H'): 
		print(i)
		cards.remove(i)
for i in cards[:]:
	if i.startswith('C'): 
		print(i)
		cards.remove(i)
for i in cards[:]:
	if i.startswith('D'): 
		print(i)
		cards.remove(i)


Measured memory_bytes: 7752
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int main()
{
	int N, M;
	cin >> N >> M;
	cout << N * (N - 1) / 2 + M * (M - 1) / 2 << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int H,W;
	int i,j;
	while(1){
	scanf("%d %d",&H,&W);
	if(H == 0 && W == 0)break;
		for(i = 0; i < H; i++){
		for(j = 0; j < W; j++){
			printf("#");
		}
		printf("\n");
	}
	puts("");
	}
	return 0;
}

Measured memory_bytes: 2608
n,k = map(int,raw_input().split())

arr = [0 for i in range(100001)]

for i in range(n):
	a,b = map(int,raw_input().split())
	arr[a] += b

i = 0
while k > 0 :
	i += 1
	k -= arr[i]
	

print i


Measured memory_bytes: 8028
#include<bits/stdc++.h>
using namespace std;
int dp[100009][9];

int main(){
  int n;
  int a[100009][9];
  cin>>n;
  for(int i=0;i<n;i++){
    for(int j=0;j<3;j++){
      cin>>a[i][j];
    }
  }

  for(int i=0;i<n;i++){
    for(int j=0;j<3;j++){
      for(int k=0;k<3;k++){
	if(j!=k){
	  dp[i+1][j]=max(dp[i+1][j],dp[i][k]+a[i][j]);
	}
      }
    }
  }

  int ans=0;
  for(int i=0;i<3;i++){
    ans=max(ans,dp[n][i]);
  }

  cout<<ans<<endl;
  return(0);
}


Measured memory_bytes: 7296
import sys
input = sys.stdin.readline
N = int(input())
X = [[] for _ in range(N)]
P = [-1] * N
for i in range(N-1):
    a, b = map(int, input().split())
    X[a-1].append((i, b-1))
    #print(X)
    P[b-1] = a-1

Q = [(0, -1)]
ANS = [-1] * (N-1)
while Q:
    x, c0 = Q.pop()
    c = 1
    for i, y in X[x]:
        if c == c0: c += 1
        ANS[i] = c
        Q.append((y, c))
        c += 1

print(max(ANS))
for ans in ANS:
    print(ans)

Measured memory_bytes: 30860
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws FileNotFoundException {

		//    	File file = new File("src/in.txt");
		//    	Scanner sc = new Scanner(file);

		Scanner sc = new Scanner(System.in);

		int[][] A = new int[3][3];

		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				A[i][j] = sc.nextInt();
			}
		}
		int N = sc.nextInt();
		for (int k = 0; k < N; k++) {
			int x = sc.nextInt();
			for (int i = 0; i < 3; i++) {
				for (int j = 0; j < 3; j++) {
					if (A[i][j] == x) {
						A[i][j] = 0;
					}
				}
			}
		}
		boolean a = (A[0][0] + A[0][1] + A[0][2] == 0);
		boolean b = (A[1][0] + A[1][1] + A[1][2] == 0);
		boolean c = (A[2][0] + A[2][1] + A[2][2] == 0);
		boolean d = (A[0][0] + A[1][0] + A[2][0] == 0);
		boolean e = (A[0][1] + A[1][1] + A[2][1] == 0);
		boolean f = (A[0][2] + A[1][2] + A[2][2] == 0);
		boolean g = (A[0][0] + A[1][1] + A[2][2] == 0);
		boolean h = (A[0][2] + A[1][1] + A[2][0] == 0);
		if (a || b || c || d || e || f || g || h) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}

}

Measured memory_bytes: 23252