akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using P = pair<int, int>;
typedef long long ll;

int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<int> L(n, 0);
  for (int i = 1; i < n; i++){
    if (s[i - 1] == 'W'){
      L[i] = L[i - 1] + 1;
    } else {
      L[i] = L[i - 1];
    }
  }
  vector<int> R(n, 0);
  for (int i = n - 2; i >= 0; i--){
    if (s[i + 1] == 'E'){
      R[i] = R[i + 1] + 1;
    } else {
      R[i] = R[i + 1];
    }
  }
  int ans = n;
  for (int i = 0; i < n; i++){
    ans = min(ans, L[i] + R[i]);
  }
  cout << ans << endl;
}

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

ll N,A;
ll ans=0;
ll x[100] = {0};
ll dp[100][100][3000];

int main(){
  cin>>N>>A; 
  for(ll i=1;i<=N;++i){cin>>x[i];}
  REP(k,N+1){REP(s,N*50+1){dp[0][k][s]=0;}}
  dp[0][0][0] = 1;
  for(ll j=1;j<=N;++j){
    for(ll k=0;k<=N;++k){
      for(ll s=0;s<=N*50;++s){
        if(s<x[j]){ dp[j][k][s] = dp[j-1][k][s];}
        else if(k>=1){ dp[j][k][s] = dp[j-1][k][s]+ dp[j-1][k-1][s-x[j]];}
        else{ dp[j][k][s]=0;}
      }
    }
  }
  for(ll k=1;k<=N;++k){ans += dp[N][k][k*A];}
  cout << ans <<"\n";
}


Measured memory_bytes: 118144
#include <iostream>
using namespace std;
int main(){
  int l,m,n;
  while(  cin >> l,l ){
    int s = 0;
    int ans;
    int f = 1;
    for(int i = 1 ; i <= 12 ; i++ ){
      cin >> m >> n;
      s += (m - n);
      if(s >= l && f == 1){ans = i;f = 0;}
    }
    if(f == 1)cout << "NA" << endl;
    else cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
package main

import (
	"fmt"
	"strings"
)

func f(s string) bool {
	chars := strings.Split(s, "")
	for _, c := range chars {
		if c != chars[0] {
			return false
		}
	}
	return true
}

func main() {
	var n string
	fmt.Scan(&n)
	if f(n[1:]) || f(n[:(len(n)-1)]) {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 640
N = int(input())
A = [int(input()) for i in range(N)]

import bisect
from collections import deque

temp = deque()
temp.appendleft(A[0])
for i in range(1,N):
  if temp[0] >= A[i]:
    temp.appendleft(A[i])
  else:
    temp[bisect.bisect_left(temp,A[i])-1] = A[i]
print(len(temp))

Measured memory_bytes: 8092
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll a7=1000000007;
ll inf=1000000000000000;
typedef pair<ll,ll> l_l;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back


ll min(ll a,ll b){
    if(a<b)return a;
    return b;
}
ll max(ll a,ll b){
    if(a>b)return a;
    return b;
}

int main(){
    ll n;cin>>n;
    ll a[n];
    rep(i,0,n-1){
        cin>>a[i];
    }
    ll b[3];
    rep(i,0,2){
        b[i]=0;
    }
    ll c;
    ll ans=1;
    rep(i,0,n-1){
        c=0;
        rep(j,0,2){
            if(a[i]==b[j]){
                c++;
            }
        }
        ans=(ans*c)%a7;
        rep(j,0,2){
            if(a[i]==b[j]){
                b[j]++;
                break;
            }
        }
    }
    cout<<ans<<endl;
    
    return 0;
}


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

#define INF 100000000
#define ABS(a) (a<0?-(a):a)
#define MIN(a,b) (a>b?b:a)
#define MAX(a,b) (a>b?a:b)
#define REP(i,a) for(int i=0;i<a;i++) 

using namespace std;
int main(){
  char a, b;
  cin >> a >> b;
  if(a == 'H'){
    if(b == 'H'){
      cout << 'H' << endl;
    }else{
      cout << 'D' << endl;
    }
  }else{
    if(b != 'H'){
      cout << 'H' << endl;
    }else{
      cout << 'D' << endl;
    }
  
  }

}



Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<numeric>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n;i++)
#define ll long long
#define INF 2147483647
using namespace std;
using Graph=vector<vector<int>>;

int main(){
  ll mod=1000000007;
  ll n,k,ans=0; cin>>n>>k;
  ll a[n],totalsm[n]={},rightsm[n]={};
  rep(i,n){
    cin>>a[i];
  }
  rep(i,n){
    rep(j,n){
      if(a[i]>a[j]){
        totalsm[i]++;
        if(i<j){
          rightsm[i]++;
        }
      }
    }
  }
  rep(i,n){
    ll tmp=(k*(k-1)/2)%mod;
    ans+=(tmp*totalsm[i]+k*rightsm[i])%mod;
    ans%=mod;
  }
  cout<<ans;
}

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

using namespace std;
typedef long long ll;


int main(){
	string s;
	cin>>s;
	char prev = '.';
	int ans = 0;
	for(int i = 0;i<s.length();i++){
		if(s[i] == 'W'){
			if(prev!='W'){
				ans++;
				prev = 'W';
			}
		}
		else{
			if(prev!='B'){
				ans++;
				prev = 'B';
			}
		}
	}
	cout<<ans-1;
	return 0;
}

Measured memory_bytes: 512
while True:
    a,b = input().split(" ")
    bn = int(b) - 2
    an = int(a) - 2
    i = int(a) + int(b)
    if i == 0:
        break
    for n in range(int(b)):
        print("#",end="")
    print('\r')
    for a in range(an):
        print("#",end="")
        for m in range(bn):
            print(".",end="")
        print("#")
    for n in range(int(b)):
        print("#",end="")
    print('\r')
    print('\r')


Measured memory_bytes: 7008
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream>
#include <numeric>

#define rep(i, j) for(int i = 0; i < j; i++)
#define For(i, a, j) for(int i = a; i < j; i++)
#define all(i) i.begin(), i.end()

using namespace std;

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

	string in; cin >> in;
	in.insert(4, " ");
	cout << in << "\n";

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>

typedef long long ll;
using namespace std;

ll gcd( ll m, ll n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	// ユークリッドの方法
	while( m != n )
	{
		if ( m > n ) m = m - n;
		else         n = n - m;
	}
	return m;
}//gcd
//最小公倍数を求める。
//*********************************************************
// 最小公倍数（Least Common Multiple）を返す。
// 引数に０がある場合は０を返す。
//*********************************************************
ll lcm( ll m, ll n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}//

int main()
{
    ll N, M, tmp, a, b, k, l;
    string S, T;

    cin >> N >> M;
    cin >> S >> T;

    tmp = lcm(N, M);
    a = tmp/N;
    b = tmp/M;

    k = lcm(a, b);

    for(ll i=0; i<tmp; i+=k){
        //if(i > min(M, N) - 1)break;
        //cout << i << endl;
        if(S[i/a] != T[i/b]){
            cout << "-1" << endl;
            return 0;
        }
    }

    cout << tmp << endl;
    return 0;
}


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


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    string s, t; cin >> s;
    cin >> t;
    int ns = 10000;
    for(int i = 0; i < s.length()-t.length() + 1; i++){
        int diff = 0;
        for(int j = i; j < i + t.length(); j++){
            if(s[j] != t[j - i])
                diff++;
        }
        ns = min(diff, ns);
    }
    cout << ns << endl;
    return 0;
}


Measured memory_bytes: 3620
N = int(input())
A = [int(n) for n in input().split(" ")]

K = 1000000007

sumA = 0
for a in A:
    sumA += a
    sumA = sumA
    #print(sumA)

sumA2 = (sumA * sumA)

sumAA = 0
for a in A:
    sumAA += a * a
    #print(sumAA)
    sumAA = sumAA
    #print(sumAA)

X = (sumA2 - sumAA) // 2 % K

print(X)
    


Measured memory_bytes: 31756
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, m, n) for(int i=(m); i<(n); ++i)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define Cout(x) cout << (x) << endl
#define Cout2(x, y) cout << (x) << " " << (y) << endl
#define dump(x) cerr << #x << " = " << (x) << endl;
typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
const int inf = 1e9;
const double pi = acos(-1.0);

int main() {
	int n; cin >> n;
	VI a(n), w(n);
	rep(i, n)cin >> a[i];
	rep(i, n)cin >> w[i];

	VI l, r;
	rep(i, n) {
		if (a[i])l.pb(w[i]);
		else r.pb(w[i]);
	}

	int ans;
	if (l.empty() || r.empty()) {
		ans = 0;
	}
	else {
		ans = *min_element(all(l)) + *min_element(all(r));
	}
	Cout(ans);
}


Measured memory_bytes: 3152
import java.util.*;

public class Main {
	public static void main(String[] args) {  
  		Scanner sc = new Scanner(System.in);
		int[] antena = new int[5];
      	
      	for(int i = 0; i < 5; i++) {
        	antena[i] = sc.nextInt();
        }
      	int maxDis = sc.nextInt();
      	String res = "Yay!";
      	for(int i = antena.length -1; i >= 0; i--) {
        	for(int j = antena.length - 2; j >= 0; j--) {
            	 if(antena[i] - antena[j] > maxDis) {
                 	res = ":(";
                 } 
            }
        }
      	System.out.println(res);
    }
}

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

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

#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()

const int N = 52;

ll n, target, ans, x[N], dp[N][N][N * N]; // prefix, taken, sum

int main() {
	cin >> n >> target;
	for (ll i = 1; i <= n; i++)
		cin >> x[i];	
	for (ll i = 0; i <= n; i++)
		dp[i][0][0] = 1;
	for (ll i = 1; i <= n; i++)
		for (ll j = 1; j <= i; j++)
			for (ll s = 0; s <= n * target; s++) {
						dp[i][j][s] = dp[i - 1][j][s];
						if (x[i] <= s) 
							dp[i][j][s] += dp[i - 1][j - 1][s - x[i]];
					}
	for (ll i = 1; i <= n; i++)
		ans += dp[n][i][i * target];
	cout << ans;
}


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

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

	multimap<long long, long long> tasks;

	for (int i = 0; i < N; i++) {
		long long A, B;
		cin >> A >> B;
		tasks.emplace(B, A);
	}

	bool is_succes = true;
	long long current_time = 0;
	for (const auto& task : tasks) {
		current_time += task.second;
		if (current_time > task.first) {
			is_succes = false;
			break;
		}
	}


	if (is_succes) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}

}


Measured memory_bytes: 12800
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	if(n%1000==0){
		cout<<"0\n";
	}
	else{
		int ans;
		if(n<1000){
			ans=1000-n;
		}
		else{
			int x=(n)/1000;
			int z=(x+1)*1000;
			ans=z-n;
		}
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define all(obj) obj.begin(), obj.end()
#define debug(x) cerr << #x << ":" << x << "\n"
#define vdebug(vec) cerr << #vec << ":"; for (auto e : vec) cerr << e << " "; cout << "\n"
#define vvdebug(vv) cerr << #vv << ":\n"; for (auto vec : vv) { for (auto e : vec) cerr << e << " "; cerr << endl; }
#define YN(f) cout << (f ? "YES" : "NO") << endl
#define Yn(f) cout << (f ? "Yes" : "No") << endl
#define yn(f) cout << (f ? "yes" : "no") << endl
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;

int main () {
	int N, K; cin >> N >> K;
	int ans = 0;
	while (N > 0) {
		N /= K;
		ans++;	
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
use proconio::*;

fn is_month(n: u32) -> bool {
    return n >= 1 && n <= 12;
}

fn main() {
    input! {
        s: u32
    };
    let bef = s / 100;
    let aft = s % 100;
    if is_month(bef) && is_month(aft) {
        println!("AMBIGUOUS");
    } else if is_month(bef) {
        println!("MMYY");
    } else if is_month(aft) {
        println!("YYMM");
    } else {
        println!("NA");
    }
}


Measured memory_bytes: 2080
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
if 2**(k)>=n**10:
    for i in range(n):
        print(n,end='')
        print(' ',end='')
else:
    for _ in range(k):
        sub=[0]*n
        for i in range(n):
            sub[max(0,i-a[i])]+=1
            if i+a[i]<n-1:
                sub[i+a[i]+1]-=1
        for i in range(1,n):
            sub[i]=sub[i]+sub[i-1]
        a=sub
    for i in sub:
        print(i,end='')
        print(' ',end='')










Measured memory_bytes: 140528
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

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<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }

int N;
int main() {
    while (cin >> N) {
        cout << N * 800 - (N/15) * 200 << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,x;
    cin>>a>>b>>x;
    if(x-a<0)
    cout<<"NO"<<endl;
    else if(a+b<x)
    cout<<"NO"<<endl;
    else
    cout<<"YES"<<endl;
}

Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long
#define sd(a) scanf("%d", &a)
#define sd2(a,b) scanf("%d%d", &a, &b)
#define sd3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define sld(a) scanf("%lld", &a)
#define sld2(a,b) scanf("%lld%lld", &a, &b)
#define sld3(a, b, c) scanf("%lld%lld%lld", &a, &b, &c)
#define pd(a) printf("%d", a)
#define pld(a) printf("%lld", a)
#define sp printf(" ")
#define nl printf("\n")
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define clr(a, val) memset((a), (val), sizeof(a))
#define pb push_back
#define endl "\n"
#define mp(a, b) make_pair(a, b)
#define pii pair<int, int>
#define xx first
#define yy second
#define mx 100001
map<int, int> m;
int main()
{
	int n;sd(n);
	for(int i=0;i<n;i++)
	{
		int d;sd(d);
		if(m.find(d)==m.end())
			m[d] = 1;
		else
			m[d]++;
	}
	int me;sd(me);
	int f = 1;
	for(int i=0;i<me;i++)
	{
		int t;sd(t);
		if(m.find(t)==m.end() || m[t] == 0)
			f = 0;	
		else if(m.find(t)!=m.end())
			m[t]--;
	}
	if(f)printf("YES\n");
	else printf("NO\n");
}

Measured memory_bytes: 9600
import java.util.*;

public class Main {

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int t = sc.nextInt();
		int a = sc.nextInt();
		double height = (t - a) / 0.006;
		int min = 0;
		double min_value = Double.MAX_VALUE;
		for (int i = 0 ; i < n; i++) {
			double tmp = Math.abs(height - sc.nextInt());
			if (tmp < min_value) {
				min_value = tmp;
				min = i + 1;
			}
		}
		System.out.println(min);
	}
	
	
}

Measured memory_bytes: 22484
def main():
    MOD = 10 ** 9 + 7

    def choose(n, a, mod=MOD):
        x, y = 1, 1
        for i in range(a):
            x = x * (n - i) % mod
            y = y * (i + 1) % mod
        return x * pow(y, mod - 2, mod) % mod

    N, A, B = map(int, input().split())

    ans = pow(2, N, MOD) - choose(N, A) - choose(N, B) - 1  # 0本の組み合わせを差し引く
    ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
n = int(input())
XYH = [list(map(int, input().split())) for _ in range(n)]
XYH.sort(key=lambda x:x[2])
X, Y, H = XYH[-1]
for cx in range(101):
    for cy in range(101):
        h = H + abs(cx-X) + abs(cy-Y)
        flag = False
        for xyh in XYH:
            if xyh[2] != max(h-abs(cx-xyh[0])-abs(cy-xyh[1]), 0):
                flag = True
        if flag: continue
        print(cx, cy, h)

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

int main(){
    long long int N, K; cin >> N >> K;
    long long int ans;
    if(N >= K) N = N % K;
    if(N*2 <= K) ans = N;
    else {
        N = K - N;
    }
    cout << N << endl;

    return 0;
}

Measured memory_bytes: 256
/*
 * drish1001
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional>  
#include <iostream> 
using namespace __gnu_pbds; 
using namespace std;
#define     pb                 push_back
#define     mp                 make_pair
#define     ff                 first
#define     ss                 second
#define    MOD                1000000007
#define     pll                pair<ll,ll>
void        sorta(auto &v)     {sort(v.begin(),v.end());} 
void        sortd(auto &v)     {sort(v.begin(),v.end(), greater<>());} 
void        fast()            {ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
typedef        long long        ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> magic; 

//all variables and functions be1ow this ..


int main()
{
	ll n;
	cin >> n;
	vector<ll> v(n);
	for(ll i=0;i<n;i++)
		cin >> v[i];
	vector<ll> sum(n);
	sum[n-1] = v[n-1];
	for(ll i=n-2;i>=0;i--)
	{
		sum[i] = (v[i]+sum[i+1])%MOD;
	}
	ll ans=0;
	for(ll i=0;i<n-1;i++)
	{
		ll temp = (v[i]*sum[i+1])%MOD;
		ans=(ans+temp)%MOD;
	}
	cout << ans << endl;
}


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

int main()
{
	int a,b;

	while(cin >> a >> b)
	{
		int t = 0;
		int c = b;
		while(c)
		{
			t++;
			c /= 10;
		}
		while(t)
		{
			a *= 10;
			t--;
		}
		a += b;
		int k = sqrt(a);
		//cout<<t<<" "<<a<<" "<<k<<endl;
		if(k*k == a)
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
	}
}

Measured memory_bytes: 256
//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;
#define wis(x) "[" << #x << " : " << x << "] " << 
typedef long long ll;

const int MAXN = 1e7 + 10, MOD = 1e9 + 7, INF = 1e9 + 5;

ll dp[MAXN];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	for(ll i = 1; i < MAXN; i++){
		for(ll j = i; j < MAXN; j += i){
			dp[j]++;
		}
	}
	int n;
	cin >> n;
	ll ans = 0;
	for(int i = 1; i <= n; i++)
		ans += i * dp[i];
	cout << ans << '\n';
}


Measured memory_bytes: 81772
n = int(input())
l = []
for i in range(1, n+1):
    num = 2
    while i != 1:
        if i % num==0:
            i //= num
            l.append(num)
        else:
            num += 1
ans = 1
for i in set(l):
    ans *= (l.count(i) + 1) % (10**9+7)
print(ans% (10**9+7))

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

// #include <boost/algorithm/string/join.hpp>
// using boost::algorithm::join;
//
// #include "boost/multi_array.hpp"
// boost::multi_array<int, 3> dp;
// dp.resize(boost::extents[10][9][8]);
//
// #include <boost/multiprecision/cpp_dec_float.hpp>  // quite slowly
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision; // mp::log10
// using bigint = boost::multiprecision::cpp_int;
// using rational = mp::cpp_rational;  // double d = static_cast<double>(r);

typedef long long ll;
typedef unsigned long long ull;
//typedef long double ld;

typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<double,double> pdd;
typedef set<int> si;
typedef set<ll> sll;
typedef vector<int> vi;
typedef vector<pair<int, int > > vii;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vll> vvll;

//constexpr ll MOD = 1e9+7;
template<typename T>constexpr auto inf=numeric_limits<T>::max()/4;
constexpr int INF=inf<int>;
constexpr ll LINF=inf<ll>;

#define Sort(x) sort(begin(x),end(x))
#define Reverse(x) reverse(begin(x),end(x))
#define ABS(a,b) ((a)<(b)?(b)-(a):(a)-(b))
#define nbit(n) (1ull<<(n))
#define _ol3(_1,_2,_3,name,...)name
#define _rep(i,n)_repi(i,0,n)
#define _repi(i,a,b)for(int i=a,i##_l=(b);i<i##_l;++i)
#define REP(...) _ol3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)
#define REPR(i,n) for(int i=n-1;i>=0;--i)
#define REPA(i,v) REP(i,(v).size())

// sort(begin(x), end(x), greater<ll>());
// lower_bound(a.begin(), a.end(), val): a[i] ≥ valである最左の位置
// upper_bound(a.begin(), a.end(), val): a[i] > valである最左の位置

// Returns minimum of a and b.
// If a is less b, a is set to b.
template<typename T>
T chmin(T& a, T b) {
  if (a > b) {
    a = b;
  }
  return a;
}

// Returns maximum of a and b.
// If a is less b, a is set to b.
template<typename T>
T chmax(T& a, T b) {
  if (a < b) {
    a = b;
  }
  return a;
}

template <typename T>
void dumpContents(const T& v, const string& msg)
{
  cerr << "### " << msg << " ###\n";
  for (const auto& x : v) {
    cerr << x << " ";
  }
  cerr << endl;
}

struct before_main_function {
  before_main_function() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<setprecision(20)<<fixed;
#define endl "\n"
  }
} before_main_function;

// ========== end of template ==========
vii R;

bool check(int x) {
  vi v;
  if (x==0) {
    v.emplace_back(0);
  } else {
    while (x>0) {
      v.emplace_back(x%10);
      x /= 10;
    }
  }
  Reverse(v);

  for (auto p : R) {
    if (v[p.first-1] != p.second) return false;
  }

  return true;
}

int main(int argc, char** argv) {
  int N, M;
  cin >> N >> M;

  REP(i, M) {
    int s, c;
    cin >> s >> c;
    R.emplace_back(s, c);
  }

  int imax = 1;
  REP(i, N) {
    imax *= 10;
  }
  int imin = imax/10;
  if (imin == 1) imin=0;

  REP(i, imin, imax) {
    if (check(i)) {
      cout << i << endl;
      return 0;
    }
  }

  cout << -1 << endl;

  return 0;
}

/* vim: set expandtab shiftwidth=2 softtabstop=2 : */


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void bubble_sort(int *score, int *num, int n)
{
	int i, j, k;
	
	for (i = 0; i < n; i++){
		for (j = 0; j < n; j++){
			if (score[i] < score[j]){
				num[i]++;
			}
		}
	}
}

int main(void)
{
	int n;
	int i;
	int score[100], num[100];
	int ta, tb, sa, sb;
	
	scanf("%d", &n);
	memset(score, 0, sizeof(score));
	
	for (i = 0; i < n; i++){
		num[i] = 1;
	}
	
	for (i = 0; i < n * (n - 1) / 2; i++){
		scanf("%d%d%d%d", &ta, &tb, &sa, &sb);
		
		if (sa > sb){
			score[ta - 1] += 3;
		}
		else if (sa < sb){
			score[tb - 1] += 3;
		}
		else {
			score[ta - 1]++;
			score[tb - 1]++;
		}
	}
	
	bubble_sort(score, num, n);
	
	for (i = 0; i < n; i++){
		printf("%d\n", num[i]);
	}
	
	return (0);
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define loop(i,a,b) for(ll i=a;i<b;i++)
const int inf=1e9+7;

int main()
{	
     ll n,k;
     cin>>n>>k;
     ll h[n];
     loop(i,0,n)
     {
     	cin>>h[i];
	 }
	 ll dp[n]={0};
	 dp[0]=0;
	 dp[1]=abs(h[0]-h[1]);
	 loop(i,2,n)
	 {
	 	 ll val=LLONG_MAX;
	 	loop(j,1,k+1)
	 	{
	 		if(i-j<0)
	 		break;
	 		ll x=abs(h[i]-h[i-j])+dp[i-j];
	 		val=min(x,val);
		 }
	 	dp[i]=val;
	 }
	 cout<<dp[n-1];
    return 0;
}


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

int main(){
	int n,m;
	int ans=0;
	cin>>n>>m;
	vector<int>src_h(n);
	vector<int>max_h(n);
	rep(i,n){
		cin>>src_h[i];
	}
	fill_n(max_h.begin(),n,0);
	rep(i,m){
		int a,b;
		cin>>a>>b;
		a-=1;b-=1;
		max_h[a]=max(max_h[a],src_h[b]);
		max_h[b]=max(max_h[b],src_h[a]);
	}
	rep(i,n){
		if(max_h[i]<src_h[i])ans++;
	}
	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 4056
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()		 //sort(all(vi S)) sort(all(string S))
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }

using P = pair<int, int>;		//P.first, P.second
typedef long long ll;
typedef vector<int> vi;
typedef set<int> seti;
typedef vector<string> vs;

const int MOD = 1e9+7;
const int INF = 1e9;
int main() {
    int N;
    cin>>N;
    vector<ll> A(N),B(N),C(N);
    rep(i,N){
        cin>>A[i];
        A[i]--;
    }
    rep(i,N)cin>>B[i];
    rep(i,N-1)cin>>C[i];
    //print(A);print(B);print(C);
    int ans =  B[A[0]]; 
    rep1(i,N){
        //cerr<<ans<<endl;
        ans += B[A[i]];
        if(A[i-1]+1==A[i]){
            ans += C[A[i-1]];
        }
    }
    cout<<ans<<endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>
#include <utility>


using namespace std;
typedef long long ll;
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; }
// const ll INF = 1LL <<60;
// const int INF = 10000;

//最大公約数
ll gcd(ll x, ll y) {
  ll tmp = 0;
  if (x < y){
    tmp=x;
    x=y;
    y=tmp;
  }
  while (y > 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//最大公倍数
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}

const int MAX = 1e6+1;
const int MOD = 1e9+7;

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 kaijo(ll k){
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum *= i;
        sum%=1000000000+7;
    }
    return sum;
}

//for(int i = ; i < ; i++){}

ll lmax(ll s,ll t){
  if(s>t){
    return s;
  }
  else{
    return t;
  }
}

ll lmin(ll s,ll t){
  if(s<t){
    return s;
  }
  else{
    return t;
  }
}

long long modpow(long long res,long long a, long long n, long long mod) {
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

//sieve(MAX);でベクトルIsPrimeに「MAXまでの数値の素数の真偽」を格納する。
vector<bool> IsPrime;
void sieve(size_t max){
    if(max+1 > IsPrime.size()){     // resizeで要素数が減らないように
        IsPrime.resize(max+1,true); // IsPrimeに必要な要素数を確保
    } 
    IsPrime[0] = false; // 0は素数ではない
    IsPrime[1] = false; // 1は素数ではない

    for(size_t i=2; i*i<=max; ++i) // 0からsqrt(max)まで調べる
        if(IsPrime[i]) // iが素数ならば
            for(size_t j=2; i*j<=max; ++j) // (max以下の)iの倍数は
                IsPrime[i*j] = false;      // 素数ではない
}
// ここから開始
int main(){
  int n;
  cin>>n;
  ll a[n];
  for(int i = 0; i < n; i++){
    cin>>a[i];
  }
  ll ds[n+1];
  ds[0] = 0;
  for(int i = 1; i <= n; i++){
    ds[i] = ds[i-1]+a[i-1];
  }
  ll ans = 0;
  // for(int i = 0; i < n+1; i++){
  //   for(int j = i+1; j < n+1; j++){
  //     if(ds[j]-ds[i]==0) ans++;
  //   }
  // }
  sort(ds,ds+n+1);
  ll tmp = 1;
  for(int i = 1; i < n+1; i++){
    if(ds[i-1]==ds[i]) tmp++;
    else{
      if(tmp==1){
        continue;
      }
      else{
        ans+=tmp*(tmp-1)/2;
        tmp = 1;
      }
    }
    // cout<<ans<<endl;
  }
  if(tmp==0){
        ;
      }
      else{
        ans+=tmp*(tmp-1)/2;
      }
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 3328
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		int a = scn.nextInt();
        int b = scn.nextInt();
        int t = scn.nextInt();
        int sum = b * (t / a);
        System.out.println(sum);
	}
}


Measured memory_bytes: 23252
#include <bits/stdc++.h>
#define  rep(i,n) for(li i=0;i<(n);i++)
#define  red(i,n) for(li i=(n)-1;i>=0;i--)
#define  all(a)   begin(a),end(a)
#define  pb(a)    push_back(a)
using namespace std;
using li = long long;
using vi = vector<li>;
using vs = vector<string>;

int main()
{
    int n,ans=0;
    cin>>n;
    int a[n+1]={0},x;
    rep(i,n) {
        cin>>x;
        a[i+1]=x;
        if(a[x]==i+1) ans++;
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<stack>
#include<functional>
#include<list>
using namespace std;

bool o[10];
int a[9];
int S = 0;
void saiki(int b) {
	if (b == 9) {
		if (a[0] + a[2] + a[5] + (a[1] + a[4]) * 10 + a[3] * 100 == a[6] * 100 + a[7] * 10 + a[8])S++;
		return;
	}
	if (a[b] == -1) {
		for (int i = 1; i <= 9; i++) {
			if (!o[i]) {
				a[b] = i;
				o[i] = true;
				saiki(b + 1);
				a[b] = -1;
				o[i] = false;
			}
		}
	}
	else {
		saiki(b + 1);
	}
}
int main() {
	for (int b = 0; b < 9; b++) { cin >> a[b]; if (a[b] != -1)o[a[b]] = true; }
	saiki(0);
	cout << S << endl;
}

Measured memory_bytes: 3032
from collections import defaultdict

N = int(input())
A = [0]+list(map(int, input().split()))

d1 = defaultdict(int)
d2 = defaultdict(int)

for i in range(1, N+1):
    d1[i-A[i]] += 1
    d2[i+A[i]] += 1

ans = 0
for k in d1.keys():
    ans += d1[k]*d2[k]
print(ans)

Measured memory_bytes: 71348
MOD = 10 ** 9 + 7

N, K = map(int, input().split())

ans = 0
for k in range(K, N + 2):
    min_s = (k - 1) * k // 2
    max_s = (N + N - k + 1) * k // 2
    ans += max_s - min_s + 1
    ans %= MOD
print(ans)


Measured memory_bytes: 9180
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
using Graph = vector<vector<ll>>;
using P = pair<int,int>;
#define MOD 1000000007
#define INF 1000000
#define PI 3.14159265358979323846

ll S[200020];

//a-bまでの和は、S[b]-S[a-1]
void init()
{
  S[0]=0;
  for (int i=1;i<=200010;i++)
  {
    S[i] = S[i-1]+i;
  }
}

int main()
{
  ll N,K;cin>>N>>K;
  
  init();

  ll up=0;
  ll down=0; 
  ll diff=0;
  ll count =0;
  for (int k=K;k<=N+1;k++)
  {
    //k個選ぶとする
    //下からk個足した数
    down = S[k-1];
    //上からk個足した数
    up = S[N]-S[N-k];
    //cout<<"up:"<<up<<" down:"<<down<<endl; 
    diff = up - down + 1;
    count += diff;
    count %= MOD;
  }
  cout<<count<<endl;
}

Measured memory_bytes: 5168
from collections import deque
import sys

n,m=map(int,input().split())

all_like=deque(list(map(int,input().split())))
all_like.popleft()

for _ in range(n-1):
    like=deque(list(map(int,input().split())))
    k=like.popleft()
    for _ in range(len(all_like)):
        eq=0
        al=all_like[0]
        for i in range(k):
            if al==like[i]:
                eq=1
                
        if eq==1:       
            all_like.append(all_like.popleft())
        else:
            all_like.popleft()
            if len(all_like)==0:
                print(0)
                sys.exit()
                
print(len(all_like))

Measured memory_bytes: 3316
#include<iostream>
using namespace std;
int main()
{
    long long int n,r,total=1,count=1;
    cin>>n;
    while(1)
    {
        if(n<=1)
            break;
        n/=2;
        count=count*2;
        total=total+count;
    }
    cout<<total<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
int n;
  int temp;
  cin>>n;
  int a[n+1];
  for(int i=0;i<=n;i++)
  {
    a[i] = 0;
  }
  for(int i=1;i<=100;i++)
  {
    for(int j=1;j<=100;j++)
    {
      for(int k=1;k<=100;k++)
      {
        temp = (i*i + j*j + k*k) + (i*j + j*k + k*i);
        if(temp<=n)
          a[temp]++;
      }
    }
  }
  for(int i=1;i<=n;i++)
    cout<<a[i]<<endl;
    
return 0;
}

Measured memory_bytes: 3492
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N=2e5+2,inf=1e9;
int a[N],b[N];
int n,m,i,x,l,r,mid,c,zx,as;
inline void read(int &x)
{
	c=getchar();
	while ((c<48)||(c>57)) c=getchar();
	x=c^48;c=getchar();
	while ((c>=48)&&(c<=57))
	{
		x=x*10+(c^48);
		c=getchar();
	}
}
inline int ab(int x)
{
	if (x>=0) return x;
	return -x;
}
bool pd()
{
	for (i=1;i<=m;i++) b[i]=(a[i]>=mid);zx=inf;
	for (i=2;i<=m;i++) if (b[i]==b[i-1])
	{
		if ((i==n)||(i==n+1)) return b[i];
		x=min(ab(i-n),ab(n-(i-1)));
		if (x<zx)
		{
			zx=x;
			as=b[i];
		}
	}
	if (zx!=inf) return as;
	return b[1];
}
int main()
{
	read(n);m=(n<<1)-1;
	for (i=1;i<=m;i++) read(a[i]);
	l=1;r=m;
	while (l<r)
	{
		mid=l+r+1>>1;
		if (pd()) l=mid; else r=mid-1;
	}
	printf("%d",l);
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;

int main() {
  int N;
  cin >> N;
  VI ar(N);
  rep(i, N - 1) {
    int a;
    cin >> a;
    a--;
    ar.at(a) += 1;
  }
  rep(i, N) { cout << ar.at(i) << endl; }
  return 0;
}


Measured memory_bytes: 4052
#include "bits/stdc++.h"
#include "sstream"
#define EPS 1e-9
using namespace std;
const int N=2e5;
const  int oo=1e6;
typedef long long ll;
int main() {
int n,m,x; cin>>n>>m; ll sum=0;
   while(m--)
    cin>>x,sum+=x;
   if(sum>n)cout<<-1;
   else cout<<n-sum;
}


Measured memory_bytes: 3612
n, k = map(int, input().split())
plst = list(map(int, input().split()))
clst = list(map(int, input().split()))
check = [False for _ in range(n)]
loop_s = []
for i in range(n):
    if check[i]:
        continue
    check[i] = True
    loop = []
    start = i
    while 1:
        loop.append(clst[i])
        i = plst[i] - 1
        check[i] = True
        if i == start:
            break
    loop_s.append(loop)

ans = -10 ** 20
for loop in loop_s:
    ans_tmp = 0
    l = len(loop)
    kk = k
    if l < k:
        ans_tmp = max(0, sum(loop) * (k // l - 1))
        kk = k % l + l
    tmp2 = -10 ** 20
    for i in range(l):
        tmp3 = 0
        for j in range(kk):
            pos = (i + j) % l
            tmp3 += loop[pos]
            tmp2 = max(tmp2, tmp3)
    ans = max(ans_tmp + tmp2, ans)
print(ans)
    
    

Measured memory_bytes: 69052
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <utility>
#include <cstdlib>
#include <memory>
#include <queue>
#include <cassert>
#include <cmath>
#include <ctime>
#include <complex>
#include <bitset>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <numeric>

using namespace std;

#define ws ws_____________________
#define y1 y1_____________________
#define y0 y0_____________________
#define left left_________________
#define right right_______________
#define next next_________________
#define prev prev_________________
#define hash hash_________________

#define pb push_back
#define fst first
#define snd second
#define mp make_pair 
#define sz(C) ((int) (C).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define ford(i, n) for (int i = int(n) - 1; i >= 0; --i)
#define all(C) begin(C), end(C)

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef long double ld;
typedef complex<double> cd;

#define FILE_NAME "a"


int R, C, N;
vi x1;
vi y1;
vi x2;
vi y2;

bool read() {
	if  (scanf("%d%d%d", &R, &C, &N) < 3) {
		return 0;
	}
	x1.resize(N);
	y1.resize(N);
	x2.resize(N);
	y2.resize(N);
	forn(i, N) {
		scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i]);
	}
	return 1;
}

bool on_border(int x, int y) {
	return x == 0 || x == R || y == 0 || y == C;
}

int dist(int x, int y) {
	assert(on_border(x, y));
	if (x == 0) {
		return y;
	}
	if  (y == C) {
		return C + x;
	}
	if  (x == R) {
		return C + R + (C - y);
	}
	assert(y == 0);
	return C + R + C + (R - x);
}

bool solve(const vi& who, int l, int r) {
	const int len = r - l + 1;
	if  (len & 1) {
		return 0;
	}
	if  (l > r) {
		return 0;
	}

	const int m = who[l];
	if  (!(l <= m && m <= r)) {
		return 0;
	}

	if  (l + 1 <= m - 1) {
		if  (!solve(who, l + 1, m - 1)) {
			return 0;
		}
	}

	if  (m + 1 <= r) {
		if  (!solve(who, m + 1, r)) {
			return 0;
		}
	}

	return 1;
}

bool solve() {
	vi ds;
	forn(i, N) {
		if  (on_border(x1[i], y1[i]) && on_border(x2[i], y2[i])) {
			const int d1 = dist(x1[i], y1[i]);
			const int d2 = dist(x2[i], y2[i]);
			ds.pb(d1);
			ds.pb(d2);
		}
	}

	sort(all(ds));

	vi who(sz(ds), -1);
	forn(i, N) {
		if  (on_border(x1[i], y1[i]) && on_border(x2[i], y2[i])) {
			const int d1 = dist(x1[i], y1[i]);
			const int d2 = dist(x2[i], y2[i]);
			
			const int p1 = lower_bound(all(ds), d1) - ds.begin();
			const int p2 = lower_bound(all(ds), d2) - ds.begin();

			who[p1] = p2;
			who[p2] = p1;
		}
	}

	return solve(who, 0, sz(who) - 1);
}

int main() {
#ifdef LOCAL
	freopen(FILE_NAME ".in", "r", stdin);
	// freopen(FILE_NAME ".out", "w", stdout);
#endif

	while (read()) {
		puts(solve() ? "YES" : "NO");
	}

#ifdef LOCAL
	cerr.precision(5);
	cerr << "Time: " << fixed << (double) clock() / CLOCKS_PER_SEC << endl;
#endif
	return 0;
}


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

using namespace std;

typedef long long ll;

ll n, k;
const ll maxn = 100+5;
const ll maxk = (1e5+5)*2;
ll MOD = 1e9+7;
ll a[maxn];
bool dp[maxk];

int main()
{
  cin >> n >> k;
  for(int i = 0; i < n; i++) cin >> a[i];
  dp[0] = 0;
  for(int i = 0; i <= k; i++)for(int j = 0; j < n; j++)
    dp[i+a[j]] |= (dp[i]==0);
  cout << (dp[k]?"First":"Second") << endl;
  return 0;
}


Measured memory_bytes: 384
H,W=map(int,input().split())
C=[[0 for i in range(0,10)] for i in range(0,10)]
for i in range(0,10):
    C[i]=list(map(int,input().split()))
A=[[0 for i in range(0,W)] for i in range(0,H)]
for i in range(0,H):
    A[i]=list(map(int,input().split()))

for i in range(0,10):
    for j in range(0,10):
        for k in range(0,10):
            if C[j][k]>C[j][i]+C[i][k]:
                C[j][k]=C[j][i]+C[i][k]

numbers=[0 for i in range(0,10)]
for i in range(0,H):
    for j in range(0,W):
        if A[i][j]!=-1:
            numbers[A[i][j]]+=1

print(sum(numbers[i]*C[i][1] for i in range(0,10)))


Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
//型名省略
typedef long long ll;
typedef vector<long long> vl;
typedef vector<vector<long long>> vll;
typedef vector<char> vc;
typedef vector<vector<char>> vcc;
typedef vector<string> vs;
//マクロ
#define rep(i,n) for(ll i = 0; i < (ll) n; i++)
#define rep2(i,x,n) for(ll i = (ll) x; i < (ll) n; i++)
#define all(A) A.begin(), A.end()
//正誤判定
void Yes(bool ans){cout << (ans? "Yes" : "No") << endl;}
void YES(bool ans){cout << (ans? "YES" : "NO") << endl;}

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

    Yes(t.substr(0,s.size()) == s);
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i=0; i<ll(n); i++)
#define REPR(i, n) for(ll i=n-1; i>=0; i--)
#define FOR(i, m, n) for(ll i=m; i<ll(n); i++)
#define ALL(v) v.begin(), v.end()
#define SIZE(x) ll(x.size()) 
using P = pair<int, int>;
const int INF = 2e9;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int x; cin >> x;
  cout << (x>=30 ? "Yes\n" : "No\n");

  return 0;
}


Measured memory_bytes: 3644
#!/usr/bin/env python3

import sys
import os

def solve(s, t, a, b, u):
    if u == s:
        return a - 1, b
    else:
        return a, b - 1

def main():
    s, t = sys.stdin.readline().split()
    a, b = [int(x) for x in sys.stdin.readline().split()]
    u = sys.stdin.readline().strip()

    a_, b_ = solve(s, t, a, b, u)

    print(a_, b_)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

ll Pow(ll n,ll p){
	ll r=1;
	for(;p>0;p>>=1){
		if(p&1) r=(r*n)%mod;
		n=(n*n)%mod;
	}
	return r;
}

const int M=100005;
ll F[M];

void Init(){
	F[0]=1;
	for(int i=1;i<M;i++) F[i]=F[i-1]*i%mod;
}

ll Div(ll n,ll m){
	return n*Pow(m,mod-2)%mod;
}

ll nCk(ll n,ll k){
	return Div(F[n],F[n-k]*F[k]%mod);
}

ll nPk(ll n,ll k){
	if(n<k) return 0; 
	return Div(F[n],F[n-k]);
}

int n,k;
vvi g;
vl dp;

void dfs(int v,int p){
	dp[v]=1;
	for(auto u:g[v]) if(u!=p){
		dfs(u,v);
		(dp[v]*=dp[u])%=mod;
		(dp[v]*=nPk(k-2,(int)g[u].size()-1))%=mod;
	}
}

int main(){
	Init();
	cin>>n>>k;
	g=vvi(n);
	dp=vl(n);
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		u--;v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(0,-1);
	cout<<dp[0]*nPk(k,(int)g[0].size()+1)%mod<<endl;
}

Measured memory_bytes: 13184
import sys

def main():
    n = int(input())
    t_, x_, y_ = 0, 0, 0
    for nn in range(n):
        t, x, y = map(int, input().split())
        diff = abs(x - x_) + abs(y - y_)
        if diff > t - t_ or (diff + t - t_) % 2:
            print('No')
            exit(0)
    print('Yes')

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include<stdio.h>
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<n;++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)

void printV(vector<ll> A){
    cout << "[vector]" << endl;
    for(int i=0; i<A.size(); i++){
        cout << A[i] << " ";
    }
    cout << endl;
}

int main(){
    // input
    string s;
    cin >> s;

    int minDiff = 10000;
    
    for(int i=0; i<s.length()-2; i++){
        string a = s.substr(i, 3);
        int val = stoi(a);
        int diff = abs(val - 753);
        if(diff < minDiff){
            minDiff = diff;
        }
    }

    cout << minDiff << endl;

    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from collections import deque
N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)
i0 = min([i for i in range(N) if len(X[i]) == 1])

P = [-1] * N
Q = deque([i0])
R = []
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)

mod = 10 ** 9 + 7
pow2 = [1]
for i in range(N + 10):
    pow2.append(pow2[-1] * 2 % mod)
inv2 = (mod + 1) // 2

invpow2 = [pow(pow2[-1], mod-2, mod)]
for i in range(N + 10)[::-1]:
    invpow2.append(invpow2[-1] * 2 % mod)
invpow2 = invpow2[::-1]

A = [1] * N
for i in R[::-1]:
    s = 0
    for j in X[i]:
        A[i] += A[j]

ans = 0
for i in range(N):
    s = pow(inv2, N - A[i], mod)
    t = 1 + (1-invpow2[N-A[i]]) * pow2[N-A[i]]
    for j in X[i]:
        s = (s * invpow2[A[j]]) % mod
        t = (t + (1-invpow2[A[j]]) * pow2[A[j]]) % mod
    ans = (ans + 1 - s * t) % mod

print(ans * inv2 % mod)

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

unordered_map<long long,bool> board;

int howmany(int x,int y){
	int ans=0;	
	for(int i=x-1;i<=x+1;i++){
		for(int j=y-1;j<=y+1;j++){
			if(board[(long long)i*1000000000+(long long)j]) ans++;
		}
	}
	return ans;
}
long long qnt[20];
int main(){
	long long h,w,n;
	cin>>h>>w>>n;
	qnt[0]=(h-2)*(w-2);
	for(int q=1;q<=n;q++){
		int a,b;
		scanf("%d%d",&a,&b);
		int up=a-1;
		int down=a+1;
		int left=b-1;
		int right =b+1;
		if(up<2) up=2;
		if(down>h-1) down=h-1;
		if(left<2) left=2;
		if(right>w-1) right=w-1;
		for(int i=up;i<=down;i++){
			for(int j=left;j<=right;j++){
				qnt[howmany(i,j)]--;
				qnt[howmany(i,j)+1]++;
			}
		}
		board[(long long)a*1000000000+(long long)b]=1;
	}
	for(int i=0;i<=9;i++){
		cout<<qnt[i]<<endl;
	}
	
}

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

int main()
{
    int h, w, k;
    cin >> h >> w >> k;
    char b[6][6];
    int total = 0;
    vector<int> hcount(h, 0);
    vector<int> wcount(w, 0);
    int ans = 0;
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            cin >> b[i][j];
            if (b[i][j] == '#')
            {
                total++;
                hcount[i]++;
            }
        }
    }
    for (int j = 0; j < w; j++)
    {
        for (int i = 0; i < h; i++)
        {
            if (b[i][j] == '#')
                wcount[j]++;
        }
    }
    for (int tmp = 0; tmp < (1 << (h + w)); tmp++)
    {
        bitset<12> s(tmp);
        vector<int> hc;
        vector<int> wc;
        int count = total;
        for (int i = 0; i < (h + w); i++)
        {
            if (s.test(i))
            {
                if (i >= h)
                {
                    wc.push_back(i - h);
                    count -= wcount[i - h];
                }
                else
                {
                    hc.push_back(i);
                    count -= hcount[i];
                }
            }
        }
        for (int i : hc)
        {
            for (int j : wc)
            {
                if (b[i][j] == '#')
                    count += 1;
            }
        }
        if (count == k)
            ans += 1;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <algorithm>
#include <cmath>
#include <climits>
#include <iomanip>
#include <queue>
#include <stack>

using namespace std;

typedef long long ll;

const int MAX = 1000000;
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;
}



int main() {
    ll s;   cin >> s;
    ll ans = 0;
    ll k = s/3;

    COMinit();

    for (ll l = 1; l <= s/3; l++) {
        ll n = s - 3*l;
        ans = (ans + COM(n+l-1, l-1)) % MOD;
    }

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

Measured memory_bytes: 27068