akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005,p=1000000007;
int read(){
	int f=1,g=0;
	char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int qpow(int x,int k){
	int t=1;
	for (;k;k>>=1){
		if (k&1) t=(ll)t*x%p;
		x=(ll)x*x%p;
	}
	return t;
}
int n,m,cnt,a[N],pos[N],ans;
struct node{int x,y;}b[N];
bool cmp2(int x,int y){return a[x]<a[y];}
bool cmp(node a,node b){return (a.x!=b.x) ? (a.x<b.x) : (a.y>b.y);}
void check(int &x,int y){if ((x+=y)>=p) x-=p;}
struct BIT{
	int f[N];
	inline int lowbit(int x){return x&(-x);}
	void add(int x,int t){for (;x<=n;x+=lowbit(x)) check(f[x],t);}
	int query(int x){
		int t=1;
		for (;x;x-=lowbit(x)) check(t,f[x]);
		return t;
	}
}f;
int main(){
	n=read();m=read();
	for (int i=1;i<=n+m;i++) a[i]=read(),pos[i]=i;
	sort(pos+1,pos+n+m+1,cmp2);
	int las=0;
	for (int i=1;i<=n+m;i++){
		int x=pos[i];
		if (x>n) las=x;
		else b[x].x=(las) ? a[x]-a[las] : 0;
	}
	las=0;
	for (int i=n+m;i;i--){
		int x=pos[i];
		if (x>n) las=x;
		else b[x].y=(las) ? a[las]-a[x] : 0;
	}
	cnt=0;
	for (int i=1;i<=n;i++)
	if (b[i].x&&b[i].y) {b[++cnt]=b[i];a[cnt]=b[i].y;}
	sort(b+1,b+cnt+1,cmp);
	sort(a+1,a+cnt+1);
	ans=1;
	for (int i=1;i<=cnt;i++)
	if (cmp(b[i-1],b[i])){
		int x=lower_bound(a+1,a+cnt+1,b[i].y)-a;
		int t=f.query(x-1);f.add(x,t);
		check(ans,t);
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 2944
#  --*-coding:utf-8-*--

# CODE FESTIVAL 2017 qual C
# C - Inserting 'x'
# http://code-festival-2017-qualc.contest.atcoder.jp/tasks/code_festival_2017_qualc_c

def f(str):
    numOfX = 0
    numOfXs = []
    letters = []
    
    for c in str:
        if c == 'x':
            numOfX += 1
        else:
            letters.append(c)
            numOfXs.append(numOfX)
            numOfX = 0
            
    numOfXs.append(numOfX)

    if any(letters[i] != letters[-i-1] 
           for i in range(len(letters)//2)):
        return -1

    return sum(abs(numOfXs[i] - numOfXs[-i-1]) 
            for i in range(len(numOfXs)//2))

def test():
    assert f('xabxa') == 2
    assert f('ab') == -1
    assert f('a') == 0
    assert f('oxxx') == 3


def main():
    str = input()
    print(f(str))

if __name__ == '__main__':
    main()



Measured memory_bytes: 4836
#include <cstdio>

int main()
{
    char s[1201];
    int c;
    while (1)
    {
        scanf("%s", s);
        c = 0;
        if (s[0] == '0')
        {
            break;
        }
        for (int i = 0; s[i] != '\0'; i++)
        {
            c += s[i] - 48;
        }
        printf("%d\n", c);
    }
}


Measured memory_bytes: 2740
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

mod = 10**9+7
# m**n
def modpow(m,n,mod=1000000007):
    res = 1
    while n>0:
        if n&1: res = res * m % mod
        m = m * m % mod
        n >>= 1
    return res

n = ii()

b = modpow(10,n)
s = modpow(8,n)
m = modpow(9,n)

ans = b - s - 2*(m-s)

print(ans%mod)

Measured memory_bytes: 9204
#include<iostream>
using namespace std;
long long p=1000000007,ans;
int main()
{
    int n,i;
    long long t1,t2,t3;
    cin>>n;
    t1=t2=t3=1;
    for(i=1;i<=n;i++)
    {
        t1=t1*10%p;
        t2=t2*9%p;
        t3=t3*8%p;
    }
    ans=(t1+t3-2*t2)%p;
    cout<<(ans+p)%p;
}


Measured memory_bytes: 3632
#include<stdio.h>
#include<stdlib.h>

int compare(const void *a, const void *b) {
    return ( *(int*)a - *(int*)b );
}

int main() {
    int N, i, c, d, e;
    int A[100000];

    d = scanf("%d", &N);
    c = 0;
    for (i = 0; i < N; i++) {
        d = scanf("%d", &A[i]);
    }
    qsort(A, N, sizeof(int), &compare);
    d = 0, e = 0;
    for (i = 0; i < N; i++) {
        if (d != A[i]) {
            if (e % 2 == 1) { c++; }
            d = A[i], e = 1;
        } else {
            e++;
        }
        //        printf("d = %d, e = %d, e = %d\n", d, e, c);
    }
    if (e % 2 == 1) { c++; }
    printf("%d\n", c);
}


Measured memory_bytes: 892
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <limits>
#include <numeric>
#include <stack>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;	//using vi = vector<int>;

#define rep(i, N) for (int i = 0; i < N; i++)

int main()
{
	int n, k,ans;
	ans = 0;
	cin >> n >> k;
	vi v(n);
	rep(i, n)cin >> v[i];

	for (int i = 0; i < n; i++) {
		if (abs(k - v[i]) < v[i]) {
			ans += (k - v[i])*2;
		}
		else {
			ans += (v[i])*2;
		}
	}

	cout << ans << endl;
	//system("pause");

	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>

char T[1000001],P[10001];
int n,m; // T:text, P:pattern, n:T's length, m:P's length
int F[10001]; // Prefix Function

void Prefix_Table(char P[], int m){
	int i=1,j=0;
	F[0] = 0;
	while(i<m){
		if(P[i] == P[j]){
			F[i] = j+1;
			i++;
			j++;
		}
		else if(j>0)
			j=F[j-1];
		else{ F[i] = 0;
			i++;
		}
	}
}

int KMP(char T[], int n, char P[], int m){
	int i=0,j=0;
	Prefix_Table(P,m);
	while(i<n){
		if(T[i]==P[j]){
			if(j==m-1)
				printf("%d\n",i-j);
			i++;
			j++;
			
		}
		else if(j>0)
			j=F[j-1];
		else i++;
	}
	return -1;
}

int main(){
	scanf("%s",T);
	scanf("%s",P);
	n = strlen(T); m = strlen(P);
	KMP(T,n,P,m);
	return 0;
}

Measured memory_bytes: 3752
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n=int(input())
    aa=LI()
    cnt=1
    for a in aa:
        if cnt==a:
            cnt+=1
    if cnt==1:
        print(-1)
    else:
        print(n-cnt+1)
main()

Measured memory_bytes: 25456
n,m = map(int,input().split())
l = list(map(int,input().split()))
l = sorted(l)

diff = []

if n >= m:
    ans = 0
else:

    for i in range(m-1):
     diff.append(l[i+1]-l[i])

    diff = sorted(diff,reverse=True)

    for i in range(n-1):
        diff.pop(0)
    
    ans = sum(diff)
    

print(ans)

Measured memory_bytes: 13960
/* 
****	
	AUTHOR :- @soham01 
****
*/
#include "bits/stdc++.h"
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	long long int a,b,aa=0,bb=0,i,j;
	cin>>a>>b;
	for(i=0;i<a;i++)
	{
		aa=aa*10+b;
	}
	for(i=0;i<b;i++)
	{
		bb=bb*10+a;
	}
	cout<<max(aa,bb)<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vvi vector<vi>
#define BITLE(n) (1LL<<((ll)n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))
#define ALL(a) (a).begin(),(a).end()
using namespace std;
typedef struct it{
  ll weight,cost;
}Item;
ll knapsack(ll n,ll w,Item item[]){
  ll ret=-1;
  ll dp[w+10];
  for(int j=0;j<w+10;j++)
   dp[j]=llINF;
  dp[0]=0;
  for(int i=0;i<n;i++){
    for(int j=0;j<=w;j++){
      if(dp[j]!=llINF){
	dp[min(w,j+item[i].weight)] = min(dp[min(w,j+item[i].weight)],dp[j]+item[i].cost);
      }
    }
  }

  return dp[w];
}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll h,n;cin>>h>>n;
  Item item[n];
  for(int i=0;i<n;i++){
    ll a,b;cin>>a>>b;
    item[i].weight=a;
    item[i].cost=b;
  }
  cout<<knapsack(n,h,item)<<endl;
  return 0;
}


Measured memory_bytes: 384
import sys
sys.setrecursionlimit(10**6)
n,*a = map(int,input().split())
s = [[*input()] for _ in range(n)]
a = {"A":a[0], "B":a[1], "C":a[2]}
ans = ["Yes"]+[0]*n
def dfs(i):
    if i==n:
        print("\n".join(ans))
        exit()
    for p,m in [s[i],s[i][::-1]]:
        if a[m]:
            a[p]+=1; a[m]-=1; ans[i+1]=p
            dfs(i+1)
            a[p]-=1; a[m]+=1
dfs(0)
print("No")

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

int main()
{
    char s1, s2, s3;
    cin >> s1 >> s2 >> s3;
    int count = 0;
    if(s1 == '1') count++;
    if(s2 == '1') count++;
    if(s3 == '1') count++;

    cout << count << endl;
}

Measured memory_bytes: 3620
#include <iostream>
#include <string>
using namespace std;
int main()
{
	string ch;
	cin >> ch;
	int kq=0;
	for(int i=0; i<ch.size(); i++)
	{
		if(ch[i]=='o') kq++;
	}
	cout << (kq+(15-ch.size())>=8?"YES":"NO");
}

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

// 解説を見た
int main(){
    ll n, x;
    cin >> n >> x;
    
    // 最初の2回分の反射
    ll ans = x + n-x; // virtually n

    /// a, bからなる平行四辺形が出来る
    ll a = max(n-x, x), b = min(n-x, x);
    
    while(b != 0){
        // 図示するとわかるが(x > n/2とするとわかりやすい)、
        // 平行四辺形内を光が反射しまくって
        // 新しい平行四辺形を作り上げるとき、長辺aの長さを短辺b
        // の長さで割ったときの商(切り捨て)の2倍だけ長さbの軌跡が残る
        // 新しく出来る平行四辺形の長さはb, a%b(euclidそのもの)
        ans += a/b*2*b;
        ll tmp = a;
        a = b;
        b = tmp%b;
    }

    // 最後(平行四辺形でなくなってしまう)とき、bを1回余計に足している
    // これは、最後の平行四辺形内の軌跡を構成する線分群のうち、
    // 1辺だけ既にもっと長い線分の一部として計算済であることからわかる
    // そのときのbはaに格納されているので、ansからaを引く
    cout << ans-a << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    static Scanner sc = new Scanner(System.in);


    public static void main(String[] args) {
        int a = sc.nextInt();
        int b = sc.nextInt();

        if (a <= 8 && b <= 8) {
            System.out.println("Yay!");
        } else {
            System.out.println(":(");
        }
    }
}


Measured memory_bytes: 21844
A,B = map(int,input().split())

def factorize(n):
	b = 2
	factor = []
	while b * b <= n:
		while n % b == 0:
			n //= b
			factor.append(b)
		b = b + 1
	if n > 1:
		factor.append(n)
	
	factor = set(factor)
	return factor
    
pryA = factorize(A)
pryB = factorize(B)
 
com = (pryA & pryB)

print(len(com) + 1)



Measured memory_bytes: 3060
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>



#define REP(i,n) for (int i = 0; (i) < (n); ++ (i))

using namespace std;
int a,b;

int main(){
  cin >> a >> b;
cout << (a-1)*(b-1) << endl;

  
  return 0;
}



Measured memory_bytes: 256
//{{{ #include <bits/stdc++.h>
#ifndef __clang__
#include <bits/stdc++.h>
#endif
using namespace std; //}}}
const long long MOD = static_cast<int>(1e9) + 7;
//{{{TEMPLATE_BEGIN
#include <unistd.h>
using namespace std::rel_ops;
typedef long long lint;
typedef unsigned long long ulint;
typedef long double ldouble;
typedef vector<int> vint;
#define rep(i, n)                                                              \
    for (int i = 0, i##_len = static_cast<int>(n); i < i##_len; i++)
#define all(c) begin(c), end(c)
#define perm(c)                                                                \
    sort(all(c));                                                              \
for (bool c##p = 1; c##p; c##p = next_permutation(all(c)))
#define uniquenize(v) (v).erase(unique(all(v)), end(v))
#define cauto const auto &
#define memset(x, y) memset(x, y, sizeof(x))
#define popcount __builtin_popcount
#define gcd __gcd
inline lint bit(int x) {
    return 1LL << x;
}
template <class T>
inline int size(const T &a) {
    return (int)a.size();
}
template <class T>
inline bool chmin(T &a, const T &b) {
    return a > b ? a = b, 1 : 0;
}
template <class T>
inline int clamp(T v, T lo, T hi) {
    return (v > hi) - (v < lo);
}
template <class T>
inline bool chmax(T &a, const T &b) {
    return a < b ? a = b, 1 : 0;
}
template <class T>
inline pair<vector<T>, char> operator*(const vector<T> &v, const char &c) {
    return make_pair(v, c);
}
template <class T>
inline istream &operator>>(istream &is, vector<T> &v) {
#ifdef ZEROKUGI
    if (v.empty()) {
        cerr << "Error L" << __LINE__ << ": vector size is zero." << endl;
        exit(EXIT_FAILURE);
    }
#endif
    for (auto &x : v)
        is >> x;
    return is;
}
template <class T>
inline ostream &operator<<(ostream &os, const pair<vector<T>, char> &v) {
    bool t = 0;
    for (const T &x : v.first) {
        if (t)
            os << v.second;
        os << x;
        t = 1;
    }
    return os;
}
template <class T>
inline ostream &operator<<(ostream &os, vector<T> &v) {
    return os << v * ' ';
}
struct before_main {
    before_main() {
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout << fixed << setprecision(20);
    };
} __before_main;
//}}}TEMPLATE_END


struct dish {
    lint a, b;
};
int main() {
    int n;
    cin >> n;
    vector<dish> d;
    rep(i, n) {
        int a, b;
        cin >> a >> b;
        d.push_back({a, b});
    }
    sort(all(d), [](const dish &p, const dish &q){
            return p.a+p.b > q.a + q.b;
            });

    lint ans = 0;
    rep(i, n) {
        if(i % 2 == 0) ans += d[i].a;
        else ans -= d[i].b;
    }
    cout << ans << endl;
}



Measured memory_bytes: 2420
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rrep(i,n) for(ll i = 1; i <= (n); ++i)
#define drep(i,n) for(ll i = (n)-1; i >= 0; --i)
#define all(v) v.begin(),v.end()
#define len(x) (ll)(x).length()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (ll)(x).size()
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
ll gcd(ll a,ll b){if(a%b==0){return b;}else{return(gcd(b,a%b));}}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const int INF=1e9;
const ll MX = 1e18;
const ll MOD=INF+7;
const int di[] = {-1,0,1,0};
const int dj[] = {0,-1,0,1};
const double PI=acos(-1);
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
const int MAX = 1000001;
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;}

int main() {
  ll n;
  cin>>n;
  vi a(n);
  rep(i,n) cin>>a[i];
  sort(all(a));
  reverse(all(a));
  ll ans=0;
  ans+=a[0];
  ll cnt=2;
  if(cnt==n){
      cout<<ans<<endl;
      return 0;
    }
  for(int i=1;i<n;i++){
    ans+=a[i];
    cnt++;
    if(cnt==n){
      break;
    }
    ans+=a[i];
    cnt++;
    if(cnt==n){
      break;
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 3992
#include<bits/stdc++.h>
#define For(a,b,c) for(int a=b;a<=c;++a)
#define Dor(a,b,c) for(int a=b;a>=c;--a)
using namespace std;
int main() {
	int a,b;
	cin>>a>>b;
	cout<<max(0,a-2*b);
	return 0;
}

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

int main() {
  // ここにプログラムを追記
  string S;
  cin>>S ;
  if (S[0]!='2')S[0]='2';
        if (S[1]!='0')S[1]='0';
           if (S[2]!='1')S[2]='1';
              if (S[3]!='8')S[3]='8';
                
  cout<< S <<endl;
}


Measured memory_bytes: 256
n = int(input())
ab = []
pushCount = 0

for i in range(n):
    ab.append(list(map(int, input().split())))

ans = 0
for i in range(n)[::-1]:
    ab[i][0] += pushCount
    if ab[i][0] % ab[i][1] != 0:
        ans += ab[i][1] - ab[i][0] % ab[i][1]
        pushCount += ab[i][1] - ab[i][0] % ab[i][1]

print(ans)

Measured memory_bytes: 31348
n, m = gets.chomp.split(" ").map(&:to_i)
sc = m.times.map { gets.chomp.split(" ").map(&:to_i) }
ans = Array.new(n, nil)
sc.each do |s, c|
  if ans[s - 1].nil?
    ans[s - 1] = c
  elsif ans[s - 1] != c
    puts "-1"
    exit
  end
end
ans[0] = 1 if ans[0].nil? && n > 1
if ans[0] == 0 && n > 1
  puts "-1"
  exit
end
puts ans.map(&:to_i).join

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

# 累積和
s=[0]
K=0
for i in range(N):
    K+=A[i]
    s.append(K)
U=0
for i in range(N-1):
    U+=A[i]*(s[N]-s[i+1])
print(U%(10**9+7))

Measured memory_bytes: 31540
#include <bits/stdc++.h>
using namespace std;
#define rep(i,e) for(int i= s; i< (int)(e); i++)
#define reps(i,s,e) for (int i = s; i < (int)(e); i++)
long bigp = 1000000007;

int main(){
    int n, k;
    cin >> n >> k;

    vector<vector<long>> c(n+1, vector<long>(n+1));
    c[0][0]=1;
    reps(i,1,n+1){
        c[i][0]=1;
        reps(j,1,i+1){
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%bigp;
        }
    }
    reps(g,1,k+1){
        if(n-k+1 < g){
            cout << 0 << endl;
        }
        else{
            long ans = (c[k-1][g-1] * c[n-k+1][g])%bigp; 
            cout << ans << endl;
        }
    }
}

Measured memory_bytes: 31616
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<string>
#define nl n<<1
#define nr (n<<1)  1
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int INF=0x3f3f3f3f;
const ll INFF=0x3f3f3f3f3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-9;
const ll mod=1e9+7;
int main()
{
    ll k;
    scanf("%lld",&k);
    if(k==0)
    {
        printf("2\n1 1\n");
        return 0;
    }
    if(k==1)
    {
        printf("2\n0 2\n");
    }
    else if(k<=50)
    {
        printf("%lld\n",k);
        for(ll i=1;i<k;i++)
        {
            printf("%lld ",k);
        }
        printf("%lld\n",k);
    }
    else
    {
        printf("50\n");
        ll num=k%50;
        for(ll i=1;i<=num;i++)
        {
            printf("%lld ",k/50-k%50+100);
        }
        for(ll i=num+1;i<=50;i++)
            printf("%lld ",k/50+50-k%50-1);
    }
    return 0;
}



Measured memory_bytes: 256
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <fstream>
#include <iomanip>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toStr(T x) { ostringstream sout; sout << x; return sout.str(); }
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = INT_MAX / 2;
const int MOD = 1000000007;
typedef vector<ll> vl;
typedef vector<vl> vvl;

int main() {
	int N, K;
	cin >> N >> K;
	if (N + 1 < 2 * K) {
		cout << "NO" << endl;
	}
	else {
		cout << "YES" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	
	static int ans = 0;
	static int temp3,temp5,temp7;
	

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = Integer.parseInt(sc.next());
		temp3 = 0; temp5 = 0; temp7 = 0;
		dfs(n,0L);
		System.out.println(ans);
		

	}
	
	static void dfs(int n , long num) {
		
		if(num*10+ 3 <= n) {
			temp3++;
			dfs(n,num*10+3);
			temp3--;
		}
		if(num*10+5 <= n) {
			temp5++;
			dfs(n,num*10+5);
			temp5--;
		}
		if(num*10+7 <= n) {
			temp7++;
			dfs(n,num*10+7);
			temp7--;
		}
		
		if(temp3 > 0 && temp5 > 0 && temp7 > 0) {
			ans++;
		}
		return;
	}

}


Measured memory_bytes: 22996
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
static const int MAX = 100000;
static const int NIL = -1;

int n;
vector<int> G[MAX];
int color[MAX];

void dfs(int r, int c){
  stack<int> S;
  S.push(r);
  color[r] = c;
  while (!S.empty())
  {
    int u = S.top();
    S.pop();
    for(int i=0;i<G[u].size();i++){
      int v = G[u][i];
      if(color[v]==NIL){
        color[v]=c;
        S.push(v);
      }
    }
  }
}

void assignColor(){
  int id=1;
  for(int i= 0;i<n;i++) color[i]=NIL;
  for(int u=0;u<n;u++){
    if(color[u]==NIL) dfs(u,id++);
  }
}

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

  for(int i=0;i<m;i++){
    cin >> s >> t;
    G[s].push_back(t);
    G[t].push_back(s);
  }

  assignColor();

  cin >> q;

  for(int i=0;i<q;i++){
    cin >> s >> t;
    if(color[s]==color[t]){
      cout << "yes" << endl;
    }else{
      cout << "no" << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 8968
/*
                _____________   ______________       __
               / _________  /\ /_____   _____/\     / /\
              / /\       / /  \\    /  /\    \ \   / /  \
             / /  \_____/ /   / \__/  /  \____\/  / /   /
            / /   /    / /   /    /  /   /       / /   /
           / /   /    / /   /    /  /   /       / /   /
          / /   /    / /   /    /  /   /       / /   /
         / /___/____/ /   /    /  /   /       / /___/________
        /____________/   /    /__/   /       /______________/\
        \            \  /     \  \  /        \              \ \
         \____________\/       \__\/          \______________\/
           ___       ___               ___    ___________
          /  /\     /  /\             /  /\  /_______   /\
         /  /__\___/  /  \           /  /  \ \      /  /  \
        /____    ____/   /          /  /   /  \____/  /   /
        \   /   /\   \  /          /  /   /       /  /   /
         \_/   /  \___\/ ___      /  /   /       /  /   /
          /   /   /     /  /\    /  /   /       /  /   /
         /   /   /     /  /__\__/  /   /       /  /___/____
        /___/   /     /___________/   /       /___________/\
        \   \  /      \           \  /        \           \ \
         \___\/        \___________\/          \___________\/

          A FAN OF FIZZYDAVID

*/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <iomanip>
#include <utility>
#include <functional>
using namespace std;
//orz jzm
#define ll long long
#define ull unsigned ll
#define orz int
#define yjz main
#define fizzydavid return
#define ak 0
#define la ;
const ll PR=19260817;
const ll inv2=500000004;
const ll inv3=333333336;
int n, m;
set<int> g[200005];
orz yjz() {
	ios::sync_with_stdio(false);cin.tie(0);
	cin>>n>>m;
	for (int i=0; i<m; i++) {
		int u, v;
		cin>>u>>v;
		g[u].insert(v);
		g[v].insert(u);
	}
	for (set<int>::iterator it=g[1].begin(); it!=g[1].end(); it++) {
		if (g[*it].count(n)) {
			puts("POSSIBLE");return 0;
		}
	}
	puts("IMPOSSIBLE");
	fizzydavid ak la
}

Measured memory_bytes: 28416
#include <bits/stdc++.h>
using namespace std;
int a[1000];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, ans = 0;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        if(i%2 == 1 && a[i]%2 == 1) ans++;
    }   
    cout << ans << "\n";
}

Measured memory_bytes: 3648
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;

const int N=200005;
const int MOD=1000000007;

int n,m,a,b,jc[N],ny[N];

int C(int n,int m)
{
    return (LL)jc[n]*ny[m]%MOD*ny[n-m]%MOD;
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&a,&b);
    jc[0]=jc[1]=ny[0]=ny[1]=1;
    for (int i=2;i<=n+m;i++) jc[i]=(LL)jc[i-1]*i%MOD,ny[i]=(LL)(MOD-MOD/i)*ny[MOD%i]%MOD;
    for (int i=2;i<=n+m;i++) ny[i]=(LL)ny[i-1]*ny[i]%MOD;
    int ans=0;
    for (int i=1;i<=n-a;i++) (ans+=(LL)C(i+b-2,b-1)*C(n-i+m-b-1,n-i)%MOD)%=MOD;
    printf("%d",ans);
    return 0;
}

Measured memory_bytes: 1792
const line = require('fs').readFileSync('/dev/stdin', 'utf-8').split('\n');

let cnt = 0;

const merge = (arr, left, mid, right) => {
    const n1 = mid - left;
    const n2 = right - mid;
    const L = [];
    const R = [];

    for (let i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (let i = 0; i < n2; i++) {
        R[i] = arr[mid + i];
    }

    L[n1] = 1/0;
    R[n2] = 1/0;

    let i = 0;
    let j = 0;
    for (let k = left; k < right; k++) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
            cnt += n1-i;
        }
    }
};

const msort = (arr, left, right) => {
    if (left + 1 < right) {
        const mid = Math.floor((left + right) / 2);
        msort(arr, left, mid);
        msort(arr, mid, right);
        merge(arr, left, mid, right);
    }
};

const data = line[1].split(' ').map(Number);
msort(data, 0, data.length);
console.log(cnt);



Measured memory_bytes: 46740
#include <bits/stdc++.h>
using namespace std;
int main() {
    string s; cin >> s;
    int n = s.size();
    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }
    for (int i = 0; i < n-1; i++) {
        if (s[i] != s[i+1]) break;
        if (i == n-2) {
            cout << 0 << endl;
            return 0;
        }
    }
    int ans = 1e9;
    for (int c = 0; c < 26; c++) {
        int ch = c + 'a';
        string ss = s; int cnt = 0;
        while (true) {
            cnt++;
            bool ok = true;
            for (int i = 0; i < n-cnt; i++) {
                if (ss[i] == ch || ss[i+1] == ch) {
                    ss[i] = ch;
                }
                if (ss[i] != ch) ok = false;
            }
            if (ok) break;
        }
        ans = min(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
    int n,k;
    //char s[101];
    scanf("%d",&n);
    scanf("%d",&k);
    //printf("%d,%d\n",n,k);
    int x[n+2];
    int i;
    for(i=0;i<n;i++){
        scanf(" %d",&x[i]);
    }
    //printf("%d",x[0]);
    int sum = 0;
    for(i=0;i<n;i++){
        if(x[i] > k - x[i]){
            sum += k - x[i];
        }else{
            sum += x[i];
        }
    }
    printf("%d\n",sum*2);
    return 0;
}


Measured memory_bytes: 128
Imports System.Console
Module Module1
    Dim n, m, k As Integer
    Dim dp() As Int64
    Dim a() As Int64
    Dim b() As Int64
    Sub Main()
        Dim s1() As String = ReadLine().Split
        n = s1(0)
        m = s1(1)
        k = s1(2)
        Dim da() As String = ReadLine.Split
        Dim db() As String = ReadLine.Split
        ReDim a(n)
        ReDim b(m)
        Dim w1, w2 As Int64
        For i = 1 To n
            w1 += da(i - 1)
            a(i) = w1
        Next
        For i = 1 To m
            w2 += db(i - 1)
            b(i) = w2
        Next
        Dim max As Int64
        ReDim dp(n)
        For i = 0 To n
            If k >= a(i) Then
                dp(i) = B_read(i)
                If dp(i) + i > max Then
                    max = dp(i) + i
                End If
            End If
        Next
        WriteLine(max)
    End Sub
    Private Function B_read(ByVal n As Integer)
        Dim nokori As Int64 = k - a(n)
        Dim w As Integer
        If n > 0 Then
            w = dp(n - 1)
        End If
        Do Until w > m OrElse b(w) > nokori
            w += 1
        Loop
        w -= 1
        Return w
    End Function
End Module


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

struct Item {
    int time, taste;
};
 

int main() {
    int N, T; cin >> N >> T;
    vector<Item> items(N);
    for (int i = 0; i < N; i++) {
        cin >> items[i].time >> items[i].taste;
    }
 
    // Sort by time in the ascending order.
    sort(items.begin(), items.end(), [](Item x, Item y) {return x.time < y.time;});
 
    vector<int> dp(T, 0);
    int ans = 0;
    for (auto &x : items) {
        ans = max(ans, dp.back() + x.taste);
 
        for (int w = T - 1; w >= x.time; --w) {
            dp[w] = max(dp[w], dp[w - x.time] + x.taste);
        }
    }
 
    cout << ans << endl;
    return 0;
}

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

void init() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
}

void solve() {
	string s[3]; cin >> s[0] >> s[1] >> s[2];
	unsigned int p[3] = {};
	int move = 0;
	while (true) {
		if (p[move] >= s[move].size()) {
			printf("%c", move+'A');
			return;
		}
		move = s[move][p[move]++]-'a';
	}
}

int main() {
	init();
	int t = 1; //scanf("%d", &t);
	while (t--) {
		solve();
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001
#define mod 1000000007
#define pi 3.141592653589793
typedef vector<int> vi;
typedef vector<ll> vl;
ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll g=gcd(a,b);
    return a/g*b;
}
ll rep_jijo(ll n,ll x){
    if(x==0) return 1;
    if(x%2==0){
        ll t=rep_jijo(n,x/2);
        return t*t%mod;
    }
    return n*rep_jijo(n,x-1)%mod;
}
ll com(ll n,ll r){
    ll x=1,y=1;
    ll tmp=n;
    while(tmp>=n-r+1){
        x=x*tmp%mod;
        tmp--;
    }
    while(r>0){
        y=y*r%mod;
        r--;
    }
    return x*rep_jijo(y,mod-2)%mod;
}


int main (){
    int n,k;
    cin >> n >> k;
    map<int,int>mp;
    rep(i,n){
        int a;
        cin >> a;
        mp[a]++;
    }
    int len=mp.size();
    if(len<=k){
        cout << 0 << endl;
        return 0;
    }
    int y=len-k;
    vector<int>x(len);
    int i=0;
    for(auto p:mp){
        x[i]=p.second;
        i++;
    }
    sort(x.begin(),x.end());
    ll ans=0;
    rep(j,y){
        ans+=x[j];
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

int main() {
  int H, W;
  cin >> H >> W;

  int result = 1e9;

  for (int i = 0; i < 2; i++) {
    for (int h0 = max(1, H / 3 - 1); h0 <= H / 3 + 1; h0++) {
      int h12 = H - h0;
      for (int h1 = max(1, h12 / 2 - 1); h1 <= h12 / 2 + 1; h1++) {
        int h2 = h12 - h1;
        if (h2 <= 0) continue;
        vector<int> S = {h0 * W, h1 * W, h2 * W};
        sort(S.begin(), S.end());
        result = min(result, S[2] - S[0]);
      }

      for (int w1 = max(1, W / 2 - 1); w1 <= W / 2 + 1; w1++) {
        int w2 = W - w1;
        if (w2 <= 0) continue;
        vector<int> S = {h0 * W, h12 * w1, h12 * w2};
        sort(S.begin(), S.end());
        result = min(result, S[2] - S[0]);
      }
    }
    swap(H, W);
  }

  printf("%d\n", result);

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> Pii;

string S;

int main() {
    cin >> S;

    bool f = false;
    for (int i = 0; i < S.length(); i++) {
        if (S[i] == '7') {
            f = true;
        }
    }

    cout << (f ? "Yes" : "No") << endl;
    
    return 0;
}


Measured memory_bytes: 3624
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;

int main(){
  string S;
  cin >> S;
  int l = S.length();

  int flag = 0;
  for(int i = 0; i < l; i++){
    if(i %2 == 0) {
      if(S[i] != 'R' && S[i] != 'U' && S[i] != 'D') flag = 1;
    }
    else {
      if(S[i] != 'L' && S[i] != 'U' && S[i] != 'D') flag = 1;
    }
  }

  if(flag == 1) {cout << "No" << endl;}
  else {cout << "Yes" << endl;}



  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int W,H,x,y,r;
    scanf("%d%d%d%d%d",&W,&H,&x,&y,&r);
    if(W>x&&H>y&&(x+r)<=W&&(y+r)<=H&&(x-r)>=0&&(y-r)>=0)
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}



Measured memory_bytes: 2096
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>

#define INF 1000000000
#define LINF 9000000000000000000
#define mod 1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair

using namespace std;

/*
   cin.tie(0);
   ios::sync_with_stdio(false);
   */

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<long long>vll;
typedef pair<int,int> pi;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

/*---------------------------------------------------*/

char board[10][10];
int x=0,y=0;

void print_board(){
  rep(i,y){
    rep(j,x)cout<<board[i][j];
    cout<<endl;
  }
}

void to_board(string s){
  for(int i=0;i<(int)s.size();i++){
    if(s[i]=='/'){
      x=0;y++;
    }else if(isdigit(s[i])){
      rep(j,s[i]-'0'){board[y][x]='.';x++;}
    }else{
      board[y][x]='b';x++;
    }
  }
  y++;
}

string to_jfen(){
  string ret="";
  for(int i=0;i<y;i++){
    int cnt=0;
    for(int j=0;j<x;j++){
      if(board[i][j]=='b'){
	if(cnt!=0)ret+=to_string(cnt);
	ret.push_back('b');
	cnt=0;
      }else{
	cnt++;
      }
    }
    if(cnt!=0)ret+=to_string(cnt);
    if(i!=y-1)ret+='/';
  }
  return ret;
}

void solve(string s){
  x=0;y=0;
  to_board(s);
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  a--;b--;c--;d--;
  swap(board[a][b],board[c][d]);
  cout<<to_jfen()<<endl;
}

int main(){
  string s;
  while(cin>>s){
    if(s=="#")break;
    solve(s);
  }
  return 0;
}



Measured memory_bytes: 3212
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Pradyumn Agrawal coderbond007
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskA {
        public void solve(int testNumber, FastReader in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();
            out.println((n - 1) * (m - 1));
        }

    }

    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[8192];
        private int curChar;
        private int pnumChars;
        private FastReader.SpaceCharFilter filter;

        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        private int pread() {
            if (pnumChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= pnumChars) {
                curChar = 0;
                try {
                    pnumChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (pnumChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = pread();
            while (isSpaceChar(c))
                c = pread();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = pread();
            }
            int res = 0;
            do {
                if (c == ',') {
                    c = pread();
                }
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = pread();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        private boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        private static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}



Measured memory_bytes: 21460
import java.util.*;
public class Main {
    
    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int a[] = new int[N];

        for (int i = 0; i < a.length; i++) {
            a[i] = scanner.nextInt()-1;
        }
        int ans = 0;
        for (int i = 0; i < a.length; i++) {
            if(a[a[i]] == i) ans++;
        }
        System.out.println(ans/2);
    }
}

Measured memory_bytes: 50308
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		List<Integer> x = new ArrayList<>();
		int n = sc.nextInt();
		int m = sc.nextInt();

		for(int i=0; i<m; i++) {
			x.add(sc.nextInt());
		}
		x.sort(null);
		List<Integer> dif = new ArrayList<>();
		for(int i=0;i<x.size()-1;i++) {
			dif.add(x.get(i+1)-x.get(i));
		}
		dif.sort(null);
		int sum = 0;
		for(int i=0;i<dif.size()-n+1;i++) {
			sum = sum + dif.get(i);
		}
		System.out.println(sum);
	}
}


Measured memory_bytes: 50564
#include<bits/stdc++.h>
//#include<tr1/unordered_map>
#pragma GCC optimize ("Ofast")
#define ll long long
#define pll pair<long long,long long>
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define forn(i, n) for(int i=0; i<int(n); i++)
#define Forn(i, n) for(int i=1; i<=int(n); i++)

using namespace std;

/*#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;*/

int main()
{
    cin.tie(0);ios_base::sync_with_stdio(false);
    int n;
    string s, t;
    cin >> n >> s >> t;
    forn(i,n) cout << s[i] << t[i];
    cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll= long long;
using vi= vector<int>;
using vvi= vector<vi>;
using vd= vector<double>;
using vvd= vector<vd>;
using vc= vector<char>;
using vb= vector<bool>;
using vl= vector<ll>;
using vs= vector<string>;
#define rep(i,x,n) for(int i=x; i<n; i++)
#define all(x) x.begin(), x.end()

int main(){
  ll n,a,b,ans,rem,rep;
  cin >> n >> a >> b;

  rep= n/(a+b);
  rem= n%(a+b);
  ans=rep*a;
  ans+= min(rem,a);

  cout << ans;
  return 0;
}


Measured memory_bytes: 256
// In the name of God

#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>
#include <complex>

using namespace std;

#define rep(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline bool smin(T &a, const T &b)   { return a > b ? a = b : a;    }
template<typename T> inline bool smax(T &a, const T &b)   { return a < b ? a = b : a;    }

typedef long long LL;

const int N = (int) 20, mod = (int) 1e9 + 7;
vector<pair<int, int>> query[N];
int dp[1 << N - 1], f[1 << N - 1], g[1 << N - 1];
void sadd(int &x, int y) {
	x += y;
	if (x >= mod) {
		x -= mod;
	}
}
int main() {
	int n, m, k;
	cin >> n >> m >> k;
	for (int j = 0; j < k; ++j) {
		int a, b, c;
		cin >> a >> b >> c;
		--a; --b;
		query[a].push_back(mp(b, c));
	}
	dp[0] = 1;
	for (int use = 0; use < m; ++use) {
		memset(f, 0, sizeof f);
		for (int mask = 0; mask < (1 << n - 1); ++mask) {
			f[mask] = dp[mask];	
		}
		for (int j = 0; j < n - 1; ++j) {
			memcpy(g, f, sizeof g);
			memset(f, 0, sizeof f);
			for (int mask = 0; mask < (1 << n - 1); ++mask) {
				for (int turn = (mask >> j & 1); turn <= 1; ++turn) {
					int nmask = mask;
					if (turn != (mask >> j & 1)) {
						nmask ^= 1 << j;
						if (__builtin_popcount(mask >> j + 1) != 0) {
							nmask ^= ((mask >> j + 1) & -(mask >> j + 1)) << j + 1;
						}
					}
					sadd(f[nmask], g[mask]);
				}
			}
		}
		for (int mask = 0; mask < (1 << n - 1); ++mask) {
			dp[mask] = f[mask];
			for (auto x : query[use]) {
				int pos = x.first, val = x.second;
				if ((mask >> pos & 1) != val) dp[mask] = 0;
			}
		}
	}
	int res = 0;
	for (int mask = 0; mask < (1 << n - 1); ++mask) sadd(res, dp[mask]);
	cout << res << endl;
}










Measured memory_bytes: 6400
#include<bits/stdc++.h>
using namespace std;
#define int long
main(){
  int c=0;
  string s;
  cin>>s;
  for(int i=0;i<s.size();++i){
    if(i%2)c+=s[i]=='g';
    else c-=s[i]=='p';
  }
  cout<<c;
}

Measured memory_bytes: 512
# import sys
# input = sys.stdin.readline

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

class UnionFind():
    def __init__(self, n):
        # uf.parentsで各ノードの親をリストで返す
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        # uf.find(x)で処理を行う
        #　要素xが属するグループの根を返す（経路圧縮）
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        # uf.union(x,y)で処理を行う
        # 要素xが属するグループと要素yが属するグループを併合する
        # 小さい部分木を大きい部分木にくっつける
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        # uf.size(x)で処理を行う
        # 要素xが属するグループの要素数を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):
        # uf.same(x,y)で処理を行う
        # 要素x,yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):
        # uf.members(x)で処理を行う
        # 要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        # uf.roots()で処理を行う
        #　すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        # uf.group_count()で処理を行う
        # グループの数を返す
        return len(self.roots())

    def all_group_members(self):
        # all_group_members()で処理を行う
        # ｛ルート要素：[グループに属する要素のリスト]｝をdict型で返す
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        # ルート要素：[グループに属する要素のリスト]を文字列で返す
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m = mp()
uf = UnionFind(n)
used = set()
for i in range(m):
    a,b = mp()
    if (a,b) not in used:
        uf.union(a-1,b-1)
        used.add((a,b))
        used.add((b,a))
ans = -1
for i in range(n):
    ans = max(uf.size(i), ans)
print(ans)



Measured memory_bytes: 147336
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for( int i = 0 ; i < n ; i++ )
typedef long long ll ;
int main() {

  int N , M , L , O ;
  cin >> N >> M >> L >> O ;
  //vector<int> A(N) ;
  //rep(i,N) cin >> A.at(i) ;
  map<int,int> mp ;
  mp[N]++ ;
  mp[M]++ ;
  mp[L]++ ;
  mp[O]++ ;
  if( mp[1]==1 && mp[9]==1 && mp[7]==1 && mp[4]==1) cout <<  "YES" << endl;
  else cout << "NO" << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python
import sys

def main():
    S = sys.stdin.readline().rstrip()
    N = len(S)

    ans = float("inf")
    tmp1 = 0
    tmp2 = 0
    for i in range(N):
        if i % 2 == 0:
            s1 = "1"
            s2 = "0"
            if S[i] != s1:
                tmp1 += 1
            elif S[i] != s2:
                tmp2 += 1
        elif i % 2 == 1:
            s1 = "0"
            s2 = "1"
            if S[i] != s1:
                tmp1 += 1
            elif S[i] != s2:
                tmp2 += 1
    print(min(tmp1, tmp2))

if __name__ == '__main__':
    main()

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

#define rep(i,n) for(signed i=0;i<n;++i)
#define int long long
#define str string
#define debg(a) cout<<#a<<":"<<a<<endl;
#define vint vector<signed>
#define all(a) a.begin(),a.end()
#define pb(a) push_back(a)
#define yn(a) cout<<((a)?"Yes":"No")<<endl;
#define YN(a) cout<<((a)?"YES":"NO")<<endl;
#define call(a) for(auto i:(a))cout<<i<<" ";cout<<endl;
#define ENDL printf("\n");
signed main(){
  int c[3][3];
  rep(i,3)rep(j,3)cin>>c[i][j];
  
  for(int a1=0;a1<101;++a1){
    for(int a2=0;a2<101;++a2){
      for(int a3=0;a3<101;++a3){
        int b1=c[0][0]-a1;
        int b2=c[0][1]-a1;
        int b3=c[0][2]-a1;
        if(c[1][0]-b1!=a2)continue;
        if(c[2][0]-b1!=a3)continue;
        if(c[1][1]-b2!=a2)continue;
        if(c[2][1]-b2!=a3)continue;
        if(c[1][2]-b3!=a2)continue;
        if(c[2][2]-b3!=a3)continue;
        cout<<"Yes"<<endl;
        return 0;
      }
    }
  }cout<<"No"<<endl;

  return 0;
}


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

using namespace std;

#define DBG cerr << '!' << endl;
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)
#define INF 1000000000
#define MOD 1000000007

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

int main()
{
	int n;cin >> n;
	vector<int> v(n);
	REP(i,n)cin >> v[i];
	sort(ALL(v));
	int ans = -1;
	
	REP(i,n){
		if(max(v[i],v[v.size()-1]-v[i]) < max(ans,v[v.size()-1]-ans)){
			ans = v[i];
		}
	}
	
	cout << v[v.size()-1] << ' ' << ans << endl;
	
	
	return 0;
}

Measured memory_bytes: 640
N, W = map(int, input().split())
X = [list(map(int, input().split())) for i in range(N)]
DP=[[float("inf")]*(N*10**3+1) for i in range(N+1)]
DP[0][0] = 0
for i in range(1, N+1):
    for j in range(N*10**3+1):
        if j-X[i-1][1] >= 0:
            DP[i][j]=min(DP[i-1][j], DP[i-1][j-X[i-1][1]]+X[i-1][0])
        else:
            DP[i][j] = DP[i-1][j]
ans = 0
for i in range(N+1):
    for j in range(N*10**3+1):
        if DP[i][j] <= W:
            ans = max(ans, j)
print(ans)


Measured memory_bytes: 310936
#include <bits/stdc++.h>
using namespace std;
void disp(vector<int> &v) {
    for(int i = 0; i < v.size(); i++) {
        cout << v[i];
        if (i < v.size() - 1)
            cout << " ";
    }
    cout << "\n";
}
int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    
    disp(a);
    for(int i = 1; i < n; i++) {
        int v = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > v)
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = v;
        disp(a);
    }

  
    return 0;
}


Measured memory_bytes: 3100
#include <iostream>
#include <algorithm>

#define ll long long
using namespace std;

int main() {
	ll a, b, k;
	cin >> a >> b >> k;
	k = min(k, a + b);
	if (a > k)
		cout << a - k << " " << b;
	else
		cout << 0 << " " << b - (k - a);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
using namespace std;
int n,ans,s;
char x[200005];
int main(void){
    cin>>x;
    n=strlen(x);
    for(int i=0;i<n;i++){
        if(x[i]=='S')s++;
        else{
            if(s>0)s--;
            else ans++;
        }
    }
    cout<<ans+s<<endl;
}

Measured memory_bytes: 384