akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

int main(void){
    int r,c,i,j;
    int mat[101][101] = {};
    int sumr,sumc;
    sumr = 0;
    sumc = 0;

    scanf("%d %d",&r,&c);

    for(i=0;i<r;i++){
        for(j=0;j<c;j++){
            scanf("%d",&mat[i][j]);
            sumr = sumr + mat[i][j];
            printf("%d ",mat[i][j]);
        }
        printf("%d\n",sumr);
        sumr = 0;
    }

    for(j=0;j<c;j++){
        for(i=0;i<r;i++){
            sumc = sumc + mat[i][j];
        }
        mat[c][r] = mat[c][r] + sumc;
        printf("%d ",sumc);
        sumc = 0;
    }
    printf("%d\n",mat[c][r]);
    return(0);
}

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

from pprint import pprint
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


n = int(input())
x = input()
x_pc = x.count('1')
x_pc_plus = x_pc + 1
x_pc_minus = x_pc - 1

# 2 ** i % x_pc_plus, 2 ** i % x_pc_minus を予め計算しておく
r_plus_list = [pow(2, i, x_pc_plus) for i in range(n+1)]
r_minus_list = [0] * (n+1)
if x_pc_minus > 0:
    r_minus_list = [pow(2, i, x_pc_minus) for i in range(n+1)]

x = x[::-1]
r_plus = 0
r_minus = 0
for i in range(n):
    if x[i] == '1':
        r_plus += r_plus_list[i]
        r_minus += r_minus_list[i]

for i in range(n-1, -1, -1):
    if x[i] == '0':
        diff = (r_plus + r_plus_list[i]) % x_pc_plus
    elif x_pc_minus >= 1:
        diff = (r_minus - r_minus_list[i]) % x_pc_minus
    else:
        print(0)
        continue
    ans = 1
    while diff > 0:
        diff = diff % bin(diff).count('1')
        ans += 1
    print(ans)


Measured memory_bytes: 105004
#include <cstdio>
#include <algorithm>
using namespace std;

int map[3][101], dp[3][101];

int main()
{
	int N;
	int x, y;
	
	scanf("%d", &N);
	
	for(y=1; y<=2; y++)
		for(x=1; x<=N; x++)
			scanf("%d", &map[y][x]);
	
	for(x=1; x<=N; x++)
		dp[1][x] = dp[1][x-1] + map[1][x];
	
	for(x=1; x<=N; x++)
		dp[2][x] = max(dp[2][x-1], dp[1][x]) + map[2][x];
	
	printf("%d", dp[2][N]);
	
	return 0;
}

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
	ost<<"{";
	for(int i=0;i<v.size();i++){
		if(i)ost<<",";
		ost<<v[i];
	}
	ost<<"}";
	return ost;
}

inline int topbit(unsigned long long x){
	return x?63-__builtin_clzll(x):-1;
}

inline int popcount(unsigned long long x){
	return __builtin_popcountll(x);
}

inline int parity(unsigned long long x){
	return __builtin_parity(x);
}

template<uint32_t mod>
struct ModInt{
	uint32_t a;
	ModInt& s(uint32_t vv){
		a=vv<mod?vv:vv-mod;
		return *this;
	}

	ModInt(int64_t x=0){s(x%mod+mod);}

	ModInt& operator+=(const ModInt &x){return s(a+x.a);}
	ModInt& operator-=(const ModInt &x){return s(a+mod-x.a);}
	ModInt& operator*=(const ModInt &x){
		a=uint64_t(a)*x.a%mod;
		return *this;
	}
	ModInt& operator/=(const ModInt &x){
		*this*=x.inv();
		return *this;
	}

	ModInt operator+(const ModInt &x)const{return ModInt(*this)+=x;}
	ModInt operator-(const ModInt &x)const{return ModInt(*this)-=x;}
	ModInt operator*(const ModInt &x)const{return ModInt(*this)*=x;}
	ModInt operator/(const ModInt &x)const{return ModInt(*this)/=x;}
	bool operator==(const ModInt &x)const{return a==x.a;}
	bool operator!=(const ModInt &x)const{return a!=x.a;}
	bool operator<(const ModInt &x)const{return a<x.a;}

	ModInt operator-()const{return ModInt()-*this;}
	ModInt pow(int64_t n)const{
		ModInt res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}

	ModInt inv()const{return pow(mod-2);}
};

template<uint32_t mod>
istream& operator>>(istream& in,ModInt<mod>& a){
	return (in>>a.a);
}
template<uint32_t mod>
ostream& operator<<(ostream& out,const ModInt<mod>& a){
	return (out<<a.a);
}
using mint=ModInt<998244353>;

int N;
string S;
int K;

vector<int>A;
mint dp[310][310][310];
signed main(){
	cin>>S>>K;
	S+='0';
	N=S.size();
	int cur=0;
	rep(i,S.size()){
		if(S[i]=='1')cur++;
		else{
			A.pb(cur);
			cur=0;
		}
	}
	reverse(all(A));
	dp[0][0][0]=1;

	rep(i,A.size()){
		for(int j=1;j<=N;j++){
			for(int k=1;k<=N;k++){
				dp[i+1][j][k]=dp[i+1][j-1][k-1]+dp[i][j-1][k-1];
				if(j>A[i]&&k>A[i])dp[i+1][j][k]-=dp[i][j-A[i]-1][k-A[i]-1];
			}
		}
		
		rep(k,N+1){
			mint sum=0;
			for(int j=N;j>=0;j--){
				sum+=dp[i][j][k];
				dp[i+1][j][k]+=sum;
			}				
		}
	}

	mint ans;
	for(int i=0;i<=N&&i<=K;i++)ans+=dp[A.size()][0][i];
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 120008
#include <bits/stdc++.h>
 
#define loop(i, n) for(int i = 0; i < n; i++)
#define loop1(i, a, n) for(int i = a; i < n; i++)
#define PI 3.141592653589793238
#define bc __builtin_popcountll
#define pf push_front
#define pb push_back
#define rf pop_front
#define rb pop_back
#define fs first
#define sc second
#define mp make_pair
#define fi ios_base::sync_with_stdio(false); cin.tie(NULL)
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
const ll M = 1e9 + 7;
const ll INF = 1e9;
inline ll pwr(ll base, ll n, ll m) {ll ans = 1;while( n > 0 ) {if ( n & 1 ) ans = (ans * base) % m; base = (base * base) % m; n>>=1;}return ans;}

const int N = 1e5 + 10;
int n, a[N];

int main() {
    fi;
 
    // #ifndef ONLINE_JUDGE
    // freopen( "input.txt", "r", stdin );
    // freopen( "output.txt", "w", stdout );
    // #endif

    cin >> n;
    loop(i, n)
        cin >> a[i];

    int mx = 0, cnt = 0;
    loop(i, n-1) {
        if( a[i] >= a[i+1] ) cnt++;
        else cnt = 0;
        mx = max(mx, cnt);
    }

    cout << mx;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const ll mod = 1e9 + 7;
const ll inf = 1e18;

int main(){
	cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    ll n, m, q;
    cin >> n >> m >> q;

    vll a(q), b(q), c(q), d(q);
    REP(i, q) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--, b[i]--;
    }
    ll res = 0;
    
    std::function<void(int, int, vll& v)> dfs = [&](int id, int cur, vll& v) {
        if (id == n) {
            ll mem = 0;
            REP(i, q) {
                if (v[b[i]] - v[a[i]] == c[i]) mem += d[i];
            }
            chmax(res, mem);
        }
        else {
            // v[id + 1] を [cur, m] から自由に決めることを再帰的に繰り返す
            for (int nxt = cur; nxt <= m; nxt++) {
                v[id + 1] = nxt;
                dfs(id + 1, nxt, v);
            }
        }
    };
    vll v(n, 1);
    dfs(0, 1, v);
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3640
n,m,x,y = [int(i) for i in input().split()]
xs = [int(i) for i in input().split()]
ys = [int(i) for i in input().split()]
if max(xs) < min(ys):
    if x < min(ys) <= y:
        print("No War")
    else:
        print("War")
else:
    print('War')


Measured memory_bytes: 2940
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
using ull = long long;
using ll = long long;

ull GCD(ull a, ull b) {
	if (a < b)
		swap(a, b);
	while (b) {
		ull r = a % b;
		a = b;
		b = r;
	}
	return a;
}
ull LCM(ull a, ull b) {
	if (a < b)
		swap(a, b);
	return a / GCD(a, b) * b;
}
int main() {
	ll n;
	ull t, plcm = 1;
	scanf("%lld", &n);
	scanf("%llu", &plcm);
	for (int i = 1; i < n; i++) {
		scanf("%llu", &t);
		plcm = LCM(plcm, t);
	}
	printf("%lld\n", plcm);
}

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

#define REP(i, n) for(int (i)=0;(i)<(n);++(i))
#define REPV(iter, v) for(auto (iter)=(v).begin(); (iter)!=(v).end();++(iter))
#define ALL(v) (v).begin(),(v).end()

#define MOD 1000000007

using namespace std;

typedef long long ll;

int main()
{
    string S;
    cin >> S;

    ll n = S.size();
    vector<ll> a(n + 1, -1);

    bool flag = false;
    for (ll i = 0; i < n; ++i)
    {
        if (S[i] == '<')
        {
            if (flag)
            {
                a[i] = a[i - 1] + 1;
            }
            else
            {
                a[i] = 0;
                flag = true;
            }
            if (i == n - 1)
            {
                a[i + 1] = a[i] + 1;
            }
        }
        else
        {
            flag = false;
        }
    }

    flag = false;
    for (ll i = n - 1; i >= 0; --i)
    {
        if (S[i] == '>')
        {
            if (flag)
            {
                a[i + 1] = a[i + 2] + 1;
            }
            else
            {
                flag = true;
                a[i + 1] = 0;
            }
            if (i == 0)
            {
                a[i] = a[i + 1] + 1;
            }
        }
        else
        {
            flag = false;
        }
    }

    ll ans = 0;
    REP(i, n + 1)
    {
        if (a[i] == -1)
        {
            a[i] = max(a[i - 1] + 1, a[i + 1] + 1);
        }
        ans += a[i];
    }

    cout << ans << endl;
}


Measured memory_bytes: 4740
import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Main ans = new Main();
		System.out.println(ans.solve());
	}

	private long solve() {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		Map<Integer, List<Integer>> graph =new HashMap<>();
		for(int i=1;i<=M;i++){
			int u = sc.nextInt();
			int v = sc.nextInt();
			List<Integer> children = graph.getOrDefault(u, new ArrayList<Integer>());
			children.add(v);
			graph.put(u, children);
		}
		long [] dp = new long[N+1];
		long ans =0;
		for(int i=1;i<=N;i++){
			ans = Math.max(ans, solve(graph, i, dp));
		}

		return ans;
	}

	private long solve(Map<Integer, List<Integer>> graph, int u, long []dp) {
		if (!graph.containsKey(u))  return 0;
		if (dp[u]!=0) return dp[u];
		long bestChild =0;
		for(int child: graph.get(u)) {
			bestChild = Math.max(bestChild, solve(graph, child, dp));
		}
		dp[u] = bestChild+1;
		return dp[u];
	}



}

Measured memory_bytes: 83080
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#define pb push_back
#define ll long long int
using namespace std;
bool dp[5555][5555];
bool iruka[5555];
int n,k;
vector<int> a;
void makedp(int noti){
  int i,j;
  for(i=0;i<=n;i++){
    dp[i][0]=true;
    for(j=1;j<=k;j++){
      dp[i][j]=false;
    }
  }
  int tmpa=a[noti-1];
  a[noti-1]=0;
  for(i=1;i<=n;i++){{
      for(j=0;j<=k;j++){
        if(dp[i-1][j]==true){
          dp[i][j]=true;
          if(j+a[i-1]<5555) dp[i][j+a[i-1]]=true;
        }
      }
    }
  }
  a[noti-1]=tmpa;
}

bool hituyou(int i){
  makedp(i);
  int j;
  if(k-a[i-1]>0) j=k-a[i-1];
    else j=0;
    for(;j<k;j++){
      if(dp[n][j]==true) return true;
    }
    return false;
}

int nibutan(int l,int r){
  //cout<<"l,r"<<l<<" "<<r<<endl;
  if(l+1>=r) return r;
  int m=(l+r)/2;
  if(iruka[m]=hituyou(m)) return nibutan(l,m);
  else return nibutan(m,r);
}

int main(void){
  int i,j,l,x;
  cin>>n>>k;
  for(i=0;i<n;i++){
    cin>>x;
    a.pb(x);
  }
  sort(a.begin(),a.end());
  int res=n;

  if(hituyou(n)&&!hituyou(1)){
    iruka[n]=true;
    iruka[1]=false;
    res=nibutan(1,n)-1;
  }
  else if(hituyou(n)) res=0;
  cout<<res<<endl;
}

Measured memory_bytes: 28928
#include <bits/stdc++.h>
#define REP(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define VSORT(v) sort(v.begin(), v.end());
#define VREV(v) reverse(v.begin(), v.end());
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
using vll = vector<ll>;
using vdouble = vector<double>;
using vstr = vector<string>;
typedef pair<int,int> P;
int dx[4] = {1, 0, -1, 0},dy[4] = {0, 1, 0, -1};

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main(){
    ll N;
	cin>>N;
	vll P(N),Q(N);
	REP(i,N) cin>>P[i];
	REP(i,N) cin>>Q[i];
	
	vll a(N);
	REP(i,N) a[i]= i+1;//a={1,2,3};
  
    map<vll, ll> mp;
    //mpはvll→llの写像a={1,2,3}に対して1を、mp={1,3,2}に対して2を返す
	do{
		mp[a] = mp.size();//mpの配列のサイズ
        //cout<<mp[a]<<endl;
	}while(next_permutation(a.begin(), a.end()));
    //next_permutationで文字列を入れ替えて順列aを順番に生成していく
	
	ll ans = abs(mp[P] - mp[Q]);
	cout << ans <<endl;
	return 0;
}

Measured memory_bytes: 6528
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str[] = br.readLine().split(" ");

		int n = Integer.parseInt(str[0]);
		long k = Long.parseLong(str[1]);

		int a[] = new int[n];

		str = br.readLine().split(" ");
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(str[i]) - 1;
		}

		List<Integer> path = new ArrayList<>();

		Set<Integer> set = new HashSet<>();
		int next = 0;

		while (!set.contains(next)) {
			path.add(next);
			set.add(next);
			next = a[next];
		}

		int size = path.size();
		int pred = path.indexOf(next);
		int hsize = size - pred;

		if (k <= pred) {
			System.out.println(path.get((int) k) + 1);
		} else {
			System.out.println(path.get((int) ((k - pred) % hsize) + pred) + 1);
		}
	}
}


Measured memory_bytes: 70888
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int N = sc.nextInt();
      	int M = sc.nextInt();
      	
        System.out.println((N*(N-1)/2)+(M*(M-1)/2));
	}
}


Measured memory_bytes: 21972
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define sz(a) signed(a.size())
using namespace std;

void solve(){
	ll a;
	long double b1;
	cin >> a >> b1;
	ll b = (long long)(b1 * 100 + 0.5);
	ll ans = (a * b)/(100);
	cout << ans; 
}

int main() {
    FAST;
    ll t=1;
    //cin>>t;
    while(t--) solve();	
    return 0;
}



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

int main(){
    int n,m;
    while(cin>>n>>m,n|m){
        int sf=0,ss=0;
        vector<int> vf(n),vs(m);
        for(auto &x:vf){
            cin>>x;
            sf+=x;
        }

        for(auto &x:vs){
            cin>>x;
            ss+=x;
        }

        if(abs(sf-ss)&1){
            cout<<-1<<endl;
            continue;
        }

        sort(vf.begin(),vf.end());
        sort(vs.begin(),vs.end());

        bool f=false;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(sf+vs[j]-vf[i] == ss+vf[i]-vs[j]){
                    cout << vf[i] << " " << vs[j] << endl;
                    f=true;i=n;j=m;
                }
            }
        }

        if(!f) cout << -1 << endl;
    }
}

Measured memory_bytes: 1208
fn read_ls<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn main(){
    let lst : Vec<i32> = read_ls();
    let (a, b, c) = (lst[0], lst[1], lst[2]);

    if a < b && b < c {
        println!("Yes");
    }else{
        println!("No");
    }
}




Measured memory_bytes: 5028
#include<iostream>
#include<iomanip>

using namespace std;

#define rep(i, a, n) for (int i = (a); i < (n); ++i)

int main(){
  std::cin.tie(nullptr);                  // 標準入出力高速化
  std::ios_base::sync_with_stdio(false);  // SとS++の入出力出力を非同期
  string s;
  cin>>s;
  cout<<s.substr(0,3)<<8<<s.substr(4,7)<<endl;
}

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

void comb(vector<vector<long long int>> &v){
    for(int i = 0; i < v.size(); i++){
        v[i][0] = 1;
        v[i][i] = 1;
    }
    for(int k = 1; k < v.size(); k++){
        for(int j = 1; j < k; j++){
            v[k][j] = (v[k - 1][j - 1] + v[k - 1][j]) % 1000000007;
        }
    }
}

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

    vector<vector<long long int>> v(n + 1, vector<long long int>(n + 1,0));
    comb(v);

    long long int ans;
    for (long long int i = 1; i < k + 1; i++) {
        ans = ((v[n - k + 1][i] % 1000000007) * (v[k - 1][i - 1] % 1000000007)) % 1000000007;
        cout << ans << endl;
    }
}


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

#define N 100
#define INF 1000000
int main(){
	int n, tmp, p[N + 1], dp[N + 1][N + 1];
	
	cin >> n;
	
	for(int i = 1 ; i <= n ; i++){
		cin >> p[i-1] >> p[i];
	}
	
	for(int i = 1 ; i <= n ; i++){
		dp[i][i] = 0;
	}
	
	for(int l = 2 ; l <= n ; l++){    //l = ???????????????????????????????????????
		for(int i = 1 ; i <= n - l + 1 ; i++){
			int j = i + l - 1; 
			dp[i][j] = INF;
			for(int k = i ; k <= j - 1 ; k++){
				tmp = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
			if(dp[i][j] > tmp) dp[i][j] = tmp;
			else dp[i][j] = dp[i][j];
				}
		}
	}
	
	cout << dp[1][n] << endl;
	
	return 0;
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; (i) < (n); ++(i))
#define ALL(x) begin(x), end(x)
#define double __float128
#define ll long long
using namespace std;

void count_ranges(int n, vector<vector<double> > const & ast, ll *cnt) {
    // flatten
    vector<double> a, expr, term;
    int size = 0;
    REP (i, ast.size()) {
        REP (j, ast[i].size()) {
            a.push_back(ast[i][j]);
            expr.push_back(i);
            term.push_back(j);
        }
        size += ast[i].size();
    }

    // two-pointers
    int l = 0, r = 0;
    double acc = 0;
    deque<double> deq;
    while (r < size) {
        int k = 0;
        // extend right
        while (r < size and ((l == r ? 0 : acc) < n or (a[r] == 1 and term[r] >= 1))) {
            if (term[r] == 0) {
                deq.push_back(1);
                k = 0;
            } else {
                acc -= deq.back();
            }
            k = a[r] == 1 ? k + 1 : 1;
            deq.back() *= a[r];
            acc += deq.back();
            ++ r;
        }
        // shrink left
        while (l < r and acc >= n) {
            if (acc == n) *cnt += min(k, r - l);
            acc -= deq.front();
            deq.front() /= a[l];
            if (term[l] == ast[expr[l]].size() - 1) {
                deq.pop_front();
            } else {
                acc += deq.front();
            }
            ++ l;
        }
    }
}

double solve_expr(int n, const char **s, ll *cnt);
vector<double> solve_term(int n, const char **s, ll *cnt);
double solve_formula(int n, const char **s, ll *cnt);

double solve_expr(int n, const char **s, ll *cnt) {
    double acc = 0;
    vector<vector<double> > ast;
    while (true) {
        auto it = solve_term(n, s, cnt);
        ast.push_back(it);
        acc += accumulate(ALL(it), 1.0, multiplies<double>());
        if (**s != '+') break;
        ++ *s;
    }
    count_ranges(n, ast, cnt);
    return acc;
}

vector<double> solve_term(int n, const char **s, ll *cnt) {
    vector<double> values;
    while (true) {
        values.push_back(solve_formula(n, s, cnt));
        if (**s != '*') break;
        ++ *s;
    }
    return values;
}

double solve_formula(int n, const char **s, ll *cnt) {
    char c = **s;
    ++ *s;
    if (isdigit(c)) {
        return c - '0';
    } else {
        assert (c == '(');
        double value = solve_expr(n, s, cnt);
        assert (**s == ')');
        ++ *s;
        return value;
    }
}

int main() {
    while (true) {
//	cerr << "---" << endl;
        int n; cin >> n;
        if (n == 0) break;
        string s; cin >> s;
//	cerr << "n = " << n << endl;
// 	cerr << "s = " << s << endl;
        const char *ptr = s.c_str();
        ll cnt = 0;
        solve_expr(n, &ptr, &cnt);
        cout << cnt << endl;
//	cerr << "answer = " << cnt << endl;
    }
    return 0;
}



Measured memory_bytes: 124056
#include<stdio.h>
int main(){
  int h,w,i,j,k;
  scanf("%d %d",&h,&w);
  for(i=0;;i++){
    for(j=0;j<h;j++){
      for(k=0;k<w;k++){
        printf("%c",'#');
        if(j==h-1&&k==w-1){
          printf("\n");
        }
      }
      printf("\n");
    }
    h=0;
    w=0;
    scanf("%d %d",&h,&w);
    if(h==0&&w==0){
      break;
    }
  }
  return 0;
}


Measured memory_bytes: 2140
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MAX = 5100000;
ll gcd(ll a, ll b) {
    return (b==0) ? a : gcd(b, a%b);
}

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;
    }
}

// 二項係数計算
ll 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;
}

// 以下から
const int MAX_N = 100000;
struct Edge {
    int to;
    int id;
};


vector<int> to[100005];
int n;
vector<int> dist;
void dfs(int v, int d=0, int p=-1) {
    dist[v] = d;
    for (int u: to[v]) {
        if (u == p) continue;
        dfs(u, d+1, v);
    }
}

vector<int> calcDist(int s){
    dist = vector<int>(n);
    dfs(s);
    return dist;
}

int main() {
    string s,t; cin >> s >> t;
    stringstream ss;
    ss << t << s;
    cout << ss.str() << endl;
}


Measured memory_bytes: 4352
#include <iostream>
using namespace std;
int main() {
	int a,b;
	
	cin >> a >> b;
	
	if (a<b) {
		cout << "a < b" << endl;
	}
	else if (a>b) {
		cout << "a > b" << endl;
	}
	else {
		cout << "a == b" << endl;
	}
	
	return 0;
}


Measured memory_bytes: 3076
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define LB(a,x) lb(all(a),x)-a.begin()
#define UB(a,x) ub(all(a),x)-a.begin()
#define mod 1000000007
#define FS fixed<<setprecision(15)
using namespace std;
typedef long long ll;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const ll INF=1e18;
ll a[20][20];

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    ll n ,m,x;
    cin>>n>>m>>x;
    V<ll> c(n);
    rep(i,n){
        cin>>c[i];
        rep(j,m) cin>>a[i][j];
    }
    bool ok=0;
    ll ans=INF;
    rep(i,(1<<n)){
        ll cnt=0;
        V<bool> z(m,0);
        V<ll> y(m,0);
        rep(j,n){
            if(i>>j&1){
                cnt+=c[j];
                rep(k,m){
                    y[k]+=a[j][k];
                    //z[k]=1;
                }
            }
        }
        bool flag=1;
        rep(j,m){
            if(y[j]<x) flag=0;
        }
        if(flag){
            chmin(ans,cnt);
        }
    }
    if(ans<INF) cout<<ans<<endl;
    else cout<<-1<<endl;
}
//ペナルティ出しても焦らない　ACできると信じろ！！！
//どうしてもわからないときはサンプルで実験　何か見えてくるかも
//頭で考えてダメなら紙におこせ！！
/*
V,P(大文字)使用不可
乗算などの際にオーバーフローに注意せよ！
(適切にmodをとれ　にぶたんで途中で切り上げろ)
制約をよく読め！
{
    ・全探索できるなら全探索しろ
    ・異常な制約ならそこに注目
}
stringの計算量(扱い)注意
コーナー注意！(特に数値が小さいものについては要検証)
N行出力のときは'¥n'
グリッド上では行先が範囲内におさまるかif文で確認(RE注意)
if文ではちゃんと比較演算子==を使え('='でもエラー出ない)
配列(vector)の大きさが0か1以上かで場合分けせよ(RE注意)
(vector<int> a(m)でm==0というものはできない)
modはなるべく最後に取れ！
*/

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

int main(void){
  
  long long int a,b;
  cin >> a >> b;
  
  if(abs(a-b) <= 1 )
    cout << "Brown" << endl;
  else
    cout << "Alice" << endl;
  
  return 0;
}


Measured memory_bytes: 256
n = gets.chomp.to_i
d, x = gets.chomp.split(' ').map(&:to_i)
a = (1..n).map{ gets.chomp.to_i }

def chocolate_count(a, d)
  (d - 1) / a + 1
end

puts x + a.reduce(0) { |sum, i| sum += chocolate_count(i, d) }


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

int main()
{
    int a = 0, b = 0;
    string s;
    cin >> s;

    for (auto i : s) {
		if (i == '0')
			a++;
		else
			b++;
    }

    cout << 2 * min(a, b) << endl;

    return 0;
}


Measured memory_bytes: 512
n,m = gets.split.map &:to_i
g = n.times.map{gets.split.map &:to_i}
c = m.times.map{gets.split.map &:to_i}.reverse

g.each{|a|
  min = 10**9
  ans = -1
  c.each.with_index{|b,i|
    z = (a[0]-b[0]).abs + (a[1]-b[1]).abs
    if z <= min then
      min = z
      ans = m-i
    end
  }
  puts ans
}

Measured memory_bytes: 1788
#include <iostream>
#include <cstring>
using namespace std;
int a[110] , lev[20];
int main() {
    int n;
    cin >> n;
    memset(lev , 0 , sizeof(lev));
    for(int i = 1 ; i <= n ; i++) cin >> a[i];
    for(int i = 1 ; i <= n ; i++) {
        lev[a[i] / 400]++;
    }
    int ans1 = 0 , ans2 = 0;
    for(int i = 0 ; i < 8 ; i++) {
        if(lev[i]) ans1++;
    }
    ans2 = ans1;
    for(int i = 8 ; i < 20 ; i++) {
        ans2 += lev[i];
    }
    if(ans1 == 0) ans1 = 1;
    cout << ans1 << ' ' << ans2 << endl;
    return 0;
}

Measured memory_bytes: 256
kMod = 1000000007
m, n = map(int, input().split())

buf = {1:m}

i = 2

while i <= n:
    prev = buf[i // 2]
    cur = (prev * prev) % kMod
    buf[i] = cur
    i *= 2

ans = 1
i = 0
while (1 << i) <= n:
    if (1<<i) & n:
        ans *= buf[1<<i]
        ans %= kMod
    i += 1
print(ans)




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

typedef long long ll;

string S;
ll mod = 998244353;
int cnt = 0;
ll dp[200010][3][3];

ll pow_mod(ll a,ll b)
{
    if(b == 0)return 1;
    ll res = pow_mod(a * a % mod,b / 2);
    if(b & 1)res = res * a % mod;
    return res;
}

int main()
{
    cin >> S;

    int N = S.size();
    for(int i = 0; i < N - 1; i++)if(S[i] == S[i + 1])cnt++;

    if(cnt == N - 1)
    {
        printf("1\n");
        return 0;
    }
    ll all = 1;
    for(int i = 0; i < N; i++)all = (all * 3) % mod;
    ll mem = 1;
    for(int i = 0; i < N - 1; i++)mem = (mem * 2) % mod;
    mem = (mem * 3) % mod;
    if(N % 3)
    {
        ll ans = ((all - mem + mod) % mod * pow_mod(3,mod - 2) + (cnt == 0)) % mod;
        printf("%lld\n",ans);
    }
    else
    {
        dp[1][0][0] = dp[1][1][1] = dp[1][2][2] = 1;
        for(int i = 0; i <= N; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                for(int k = 0; k < 3; k++)
                {
                    for(int l = 0; l < 3; l++)
                    {
                        if(k == l)continue;
                        dp[i + 1][(j + l) % 3][l] += dp[i][j][k];
                        dp[i + 1][(j + l) % 3][l] %= mod;
                    }
                }
            }
        }
        ll sum = 0;
        for(int i = 0; i < N; i++)sum = (sum + (S[i] - 'a')) % 3;
        if(sum != 0)
        {
            ll ans = ((all - (dp[N][1][0] * 9) % mod + mod) % mod * pow_mod(3,mod - 2) + (cnt == 0)) % mod;
            printf("%lld\n",ans);
        }
        else
        {
            if(N == 3)
            {
                printf("%d\n",3);
            }
            else
            {
                ll ans = (all * pow_mod(3,mod - 2) % mod - dp[N][0][0] - dp[N][0][1] - dp[N][0][2] + (cnt == 0) + 3 * mod) % mod;
                printf("%lld\n",ans);
            }
        }
    }
    return 0;
}


Measured memory_bytes: 14596
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
#define tll tuple<ll, ll, ll>
#define all(c) c.begin(),c.end()
 
const ll inf = 1000000001;
const ll INF = 1e18;
const ll MOD = 1000000007;

int main() {
  ll n;
  cin >> n;
  double A[n];
  for (int i=0;i<n;i++) cin >> A[i];
  double ans = 0;
  for (int i=0;i<n;i++) ans += 1/A[i];
  //cout << ans << endl;
  double ans2 = 1/ans;
  cout << setprecision(10) << ans2 << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		sc.close();

		if ((b - a) % 2 == 0) {
			System.out.println("Alice");
		} else {
			System.out.println("Borys");
		}
	}
}


Measured memory_bytes: 21844
n, y = list(map(int, input().split()))

for i in range(2000+1):
    for j in range(2000+1):
        if i*10000 + j*5000 + (n-i-j)*1000 == y and (n-i-j)>=0:
            print(str(i) + ' ' + str(j) + ' ' + str(n-i-j) + ' ')
            exit()
print('-1 -1 -1')

Measured memory_bytes: 9120
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, r;
  cin >> n >> r;
  if (n > 10) {
    cout << r << endl;
  }
  else {
    //内部レーティング-100*(10-n)=表示レーティング
    cout << r + 100 * (10 - n) << endl;
  }
}

Measured memory_bytes: 3596
n = int(input())
s = input()

l = [0]
r = [0]

for i in s:
    if i == "W":
        l.append(l[-1] + 1)
    else:
        l.append(l[-1])

for i in s[::-1]:
    if i == "E":
        r.append(r[-1] + 1)
    else:
        r.append(r[-1])

l = l[1:]
r = r[1:][::-1]

ans = 10 ** 9

for i in zip(l, r):
    ans = min(sum(i), ans)

print(ans-1)

Measured memory_bytes: 22776
#include <iostream>

int main(int argc, const char * argv[]) {
    int b,f,r,v,n,m,l,o,p,a[4][3][10]={0};
    std::cin>>n;
    for(m=0;m<n;m++){
        std::cin>>b>>f>>r>>v;
        a[b-1][f-1][r-1]+=v;
    }
    for(l=0;l<4;l++){
        for(o=0;o<3;o++){
            for(p=0;p<10;p++){
                std::cout<<" "<<a[l][o][p];
            }
            std::cout<<std::endl;
        }
        if(l!=3){
            std::cout<<"####################"<<std::endl;
        }
    }
    return 0;
}



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

void solve(long long N, long long M, vector<long long> X){
	vector<long long> Y(M-1);
	long long sum = 0;
	sort(X.begin(), X.end());
	for (int i = 0; i < M-1; i++) {
		Y[i] = X[i+1] - X[i];
		sum += Y[i];
	}
	sort(Y.begin(), Y.end());
	for (int i = M-2; i >= max(M-N,0LL) ; i--) {
		sum -= Y[i];
	}
	printf("%lld\n", sum);
}

int main(){
	long long N;
	long long M;
	scanf("%lld",&N);
	scanf("%lld",&M);
	vector<long long> X(M-1+1);
	for(int i = 0 ; i <= M-1 ; i++){
		scanf("%lld",&X[i]);
	}
	solve(N, M, X);
	return 0;
}


Measured memory_bytes: 2560
#include <iostream>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
#include <array>
#include <algorithm>
#include <numeric>
#include <limits>
#include <string>
#include <regex>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

int main()
{
    long long N;
    cin >> N;
    printf("%lld\n", N * (N - 1) / 2);
    return 0;
}


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

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

    if(S>W)
    {
        cout<<"safe"<<endl;
        return 0;
    }
    else
    {
        cout<<"unsafe"<<endl;
        return 0;
    }

}

Measured memory_bytes: 3632
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    a = int(input().rstrip())
    b = int(input().rstrip())
    if a > b:
        print('GREATER')
    elif b > a:
        print('LESS')
    else:
        print('EQUAL')
    
if __name__ == '__main__':
    main()


Measured memory_bytes: 3572
#include <stdio.h>
int main(void){
    int m, f, b, debt;
    scanf("%d %d %d", &m, &f, &b);
    
    if(m>=b){
        printf("0\n");
    }
    
    else{
        debt = b-m;
        if(f>=debt){
            printf("%d\n", debt);
        }
        else printf("NA\n");
    }
    return 0;
}



Measured memory_bytes: 2104
var
 a,b,c,i,x:longint;
begin
 readln(a,b,c);
 for i:=1 to 100 do
  begin
   x:=a*i;
   if x mod b=c then
    begin
     writeln('YES');
     halt;
    end;
  end;
 writeln('NO');
end.

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);

		String w=sc.nextLine();
		int len=w.length();

		char c[]=new char[len];
		for(int i=0;i<len;i++){
			c[i]=w.charAt(i);
		}

		int jud=0,flg=0;
		for(int i=0;i<len;i++){
			for(int j=0;j<len;j++){
				if(c[i]==c[j])	jud++;
			}
			if(jud%2==1)	flg=1;
		}

		if(flg==0)	System.out.println("Yes");
		else	System.out.println("No");
	}
}

Measured memory_bytes: 8660
// Author: Vamsi Krishna Reddy Satti
// With love for Competitive Programming!
 
#pragma GCC optimize ("Ofast,unroll-loops,-ffloat-store")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")

#include <bits/stdc++.h>
using namespace std;

string to_string(const string& s) { return '"' + s + '"'; }
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cout << " " << to_string(H);
    debug_out(T...);
}
#ifdef LOCAL
    #define debug(...) cout << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
    #define debug(...) 3
#endif
 
#define cin_exception cin.exceptions(cin.failbit);
#define cout_precision cout.setf(ios::fixed); cout.precision(15);
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
using ll = int_fast64_t; using ld = long double;

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

map<int, pair<int, int>> m;
int r[3], c[3];

void solve() {
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            int a; cin >> a;
            m[a] = {i, j};
        }
    }
    int ans = 0, d1 = 0, d2 = 0;
    int n; cin >> n;
    for (int i = 0; i < n; ++i) {
        int b; cin >> b;
        if (m.find(b) == m.end()) continue;
        auto p = m[b];
        int x = p.first, y = p.second;
        r[x]++; c[y]++;
        if (x + y == 2) d1++;
        if (x == y) d2++;
    }
    for (int i = 0; i < 3; ++i) {
        if (r[i] == 3) ++ans;
        if (c[i] == 3) ++ans;
    }
    if (d1 == 3) ++ans;
    if (d2 == 3) ++ans;
    if (ans >= 1) {
        cout << "Yes\n";
        return;
    }
    cout << "No\n";
}

int main() {
    fast_io; cin_exception;
    int t = 1; // cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int n, d, e, k[200][2], i, MIN[2], MAX[2];
int main() {
	while (true) {
		cin >> n; k[0][0] = 100; k[0][1] = 100; MIN[0] = 100; MIN[1] = 100; MAX[0] = 100; MAX[1] = 100;
		if (n == 0) {
			break;
		}
		for (i = 1; i < n; i++) {
			cin >> d >> e;
			if (e == 0) {
				k[i][0] = k[d][0]-1;
				k[i][1] = k[d][1];
			}
			if (e == 1) {
				k[i][0] = k[d][0];
				k[i][1] = k[d][1] + 1;
			}
			if (e == 2) {
				k[i][0] = k[d][0] + 1;
				k[i][1] = k[d][1];
			}
			if (e == 3) {
				k[i][0] = k[d][0];
				k[i][1] = k[d][1] - 1;
			}
		}
		for (int i = 0; i < n; i++) {
			MIN[0] = min(MIN[0], k[i][0]);
			MIN[1] = min(MIN[1], k[i][1]);
			MAX[0] = max(MAX[0], k[i][0]);
			MAX[1] = max(MAX[1], k[i][1]);
		}
		cout << MAX[0] - MIN[0] + 1 << ' ' << MAX[1] - MIN[1] + 1 << endl;
	}
}

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

int main() {
	int d, n;
	cin >> d >> n;
	int ans = n;
	if (n == 100) {
		ans = 101;
		
	}
	for (int i = 0; i < d; i++) {
		ans *= 100;
	}
	cout << ans;
	return 0;
}

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

using namespace std;

#define all(c) (c).begin(), (c).end()
#define sz(c) (static_cast<int>(c.size()))
#define endl "\n"

using ld = long double;
using ll = long long;

const ll MOD = 1e9+7;

template <typename T, typename Z> inline T power(T base, Z exponent)
{
    T ret = 1;
    for (; exponent > 0; exponent >>= 1, base = base * base % MOD)
        if (exponent & 1) ret = ret * base % MOD;
    return ret;
}
template <typename Z> Z gcd(const Z& a, const Z& b)
{
    if (b == 0) return a;
    return gcd(b, a % b);
}
template <typename Z> Z extended_gcd(const Z& a, const Z& b, Z& x, Z& y)
{
    if (b == 0) return x = 1, y = 0, a;
    Z gcd = extended_gcd(b, a % b, y, x);
    y -= (a / b) * x;
    return gcd;
}
#ifdef DEBUG
template <typename... T>
void debug(T&&... args)
{
    ((cerr << args << " "), ..., (cerr << endl));
}
#else
template <typename... T> void debug(T&&... args) {}
#endif
#define vardump(...) #__VA_ARGS__":", (__VA_ARGS__)
// }}}

const ll INFL = numeric_limits<ll>::max() / 2;
const ll INF = numeric_limits<int>::max() / 2;


struct wall {
    int r, c;
    friend istream& operator>>(istream& stream, wall &w) {
        return stream >> w.r >> w.c;
    }
    friend bool operator<(wall& a, wall& b) {
        return a.r < b.r || (a.r == b.r && a.c < b.c);
    }
};

const int N = 3e3 + 5;
const int RN = 1e5 + 5;
wall w[N];
ll f[2*RN], inv[2*RN];
ll dp[N][2];

void solve()
{
    int H, W, n; cin >> H >> W >> n;
    for (int i = 0; i < n; i++) cin >> w[i];
    sort(w, w+n);

    f[0] = 1, inv[0] = 1;
    for (int i = 1; i <= H+W; i++) f[i] = f[i-1] * i % MOD;
    for (int i = 1; i <= H+W; i++) inv[i] = power(f[i], MOD-2);

    auto fn = [](ll r, ll c) {
        return f[r+c] * inv[r] % MOD * inv[c] % MOD;
    };
    for (int i = 0; i < n; i++) {
        dp[i][1] = fn(w[i].r-1, w[i].c-1);
    }
    ll bad = 0;
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 2; c++) {
            for (int j = i+1; j < n; j++) {
                int dr = w[j].r - w[i].r;
                int dc = w[j].c - w[i].c;
                if (dc < 0) continue;
                dp[j][!c] += fn(dr, dc) * dp[i][c] % MOD;
                dp[j][!c] %= MOD;
                debug(j, i, c, dp[j][!c]);
            }
            if (c) bad += dp[i][c] * fn(H-w[i].r, W-w[i].c);
            else bad -= dp[i][c] * fn(H-w[i].r, W-w[i].c);
            bad %= MOD;
            if (bad < 0) bad += MOD;
        }
        debug(i, bad);
    }
    ll ans = fn(H-1, W-1) - bad;
    if (ans < 0) ans += MOD;
    cout << ans << endl;
}

// main {{{
int main()
{
    cin.sync_with_stdio(0); cin.tie(NULL);
    solve();
    return 0;
}
// }}}



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

using namespace std;

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)

signed main(){

    lli n;
    cin>>n;
    vector<lli> a(n);
    vector<lli> s(n+1);
    s[0]=0;
    map<lli,lli> cnt;
    cnt[0]++;

    REP(i,0,n){
        cin>>a[i];
        s[i+1] = s[i] + a[i];
        cnt[s[i+1]]++;
    }

    lli ans = 0;
    for(auto e:cnt){
        if(DEBUG)cout<<"e.first="<<e.first<<" e.second="<<e.second<<endl;
        ans += (e.second)*(e.second-1)/2;
    }
    cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 15872
from collections import deque

def linersearch(A,n,key):
    i = 0
    A.append(key)
    while A[i] != key:
        i += 1
    if i == n:
        A.pop()
        return False
    else:
        A.pop()
        return True

n = int(input())
S = deque([int(x) for x in input().split()])
q = int(input())
T = [int(x) for x in input().split()]
ans = 0

for q in T:
    if linersearch(S,n,q):
        ans += 1

print(ans)


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

struct UnionFind
{
  vector<int> par;
  vector<int> rank;
  vector<int> group_size;

  UnionFind(int n = 1)
  {
    init(n);
  }

  void init(int n = 1)
  {
    par.resize(n);
    rank.resize(n);
    group_size.resize(n);
    for (int i = 0; i < n; ++i)
      par[i] = i, rank[i] = 0, group_size[i] = 1;
  }

  int root(int x)
  {
    if (par[x] == x)
      return x;
    int r = root(par[x]);
    return par[x] = r;
  }

  bool same(int x, int y)
  {
    return root(x) == root(y);
  }

  bool unite(int x, int y)
  {
    x = root(x);
    y = root(y);
    if (x == y)
      return false;
    if (rank[x] < rank[y])
      swap(x, y);
    if (rank[x] == rank[y])
      ++rank[x];
    par[y] = x;
    group_size[x] += group_size[y];
    group_size[y] = group_size[x];
    return true;
  }
};

int main()
{
  int64_t N, K, L, p, q;
  cin >> N >> K >> L;
  UnionFind Roads(N), Rails(N);
  for (int i = 0; i < K; i++)
  {
    cin >> p >> q;
    p--;
    q--;
    Roads.unite(p, q);
  }
  for (int i = 0; i < L; i++)
  {
    cin >> p >> q;
    p--;
    q--;
    Rails.unite(p, q);
  }
  map<pair<int, int>, int> mp;
  for (int i = 0; i < N; i++)
  {
    mp[{Roads.root(i), Rails.root(i)}]++;
  }
  for (int i = 0; i < N; i++)
  {
    cout << mp.at({Roads.root(i), Rails.root(i)});
    if (i != N - 1)
      cout << ' ';
  }
  cout << endl;
}


Measured memory_bytes: 16640
#include<iostream>
#include<cmath>
#include<complex>
#include<algorithm>

using namespace std;

typedef pair<double, double> P;

int N;
P pos[300];

double calcabs(P a, P b){
  return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2));
}

int main(){
  while(1){
    cin >> N;
    if(N == 0)break;
    for(int i = 0; i < N; i++)cin >> pos[i].first >> pos[i].second;
    
    int ans = 1;

    for(int i = 0; i < N; i++){
    for(int j = i + 1; j < N; j++){
	if(calcabs(pos[i], pos[j]) > 2)continue;
	
	P center[2];
	//calc the center of the circle which we put on the selected 2 points.
	
	center[0].first = (pos[i].first + pos[j].first) / 2.0 + 
	  sqrt(1.0 - pow(calcabs(pos[i], pos[j]) , 2)/ 4.0) * 
	  1.0 / calcabs(pos[i], pos[j]) * (-1 * (pos[i].second - pos[j].second));
	
	center[0].second = (pos[i].second + pos[j].second) / 2.0 + 
	  sqrt(1.0 - pow(calcabs(pos[i], pos[j]), 2) / 4.0) * 
	  1.0 / calcabs(pos[i], pos[j]) *  (pos[i].first - pos[j].first);
	
	center[1].first = (pos[i].first + pos[j].first) / 2.0 - 
	  sqrt(1.0 - pow(calcabs(pos[i], pos[j]), 2) / 4.0) * 
	  1.0 / calcabs(pos[i], pos[j]) * (-1 * (pos[i].second - pos[j].second));
	
	center[1].second = (pos[i].second + pos[j].second) / 2.0 - 
	  sqrt(1.0 - pow(calcabs(pos[i], pos[j]), 2) / 4.0) * 
	  1.0 / calcabs(pos[i], pos[j]) *  (pos[i].first - pos[j].first);
	
	int cnt = 0;
	for(int k = 0; k < N; k++){
	  if(calcabs(center[0], pos[k]) <= 1.0001)cnt++;
	}
	ans = max(ans, cnt);
	
	cnt = 0;
	for(int k = 0; k < N; k++){
	  if(calcabs(center[1], pos[k]) <= 1.0001)cnt++;
	}
	ans = max(ans, cnt);
	
    }
    }
    cout << ans << endl;
  }
  return 0;
}



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

#define rep(i,n) for(int i = 0; i < (n); i++)
#define ll long long

using namespace std;

int main(){
  ll n;cin>>n;
  vector<ll> a(n);
  rep(i, n)cin>>a[i];

  if(a[0]!=0) {cout<<-1;return 0;}

  ll pre = a[0];
  ll result=0;
  map<ll, ll>m;
  m[pre]++;
  for(ll i=1; i<n; i++){
    if(a[i]-pre>1){cout<<-1;return 0;}
    if(a[i]<pre){
      result+=pre;
      m.clear();
      m[a[i]]++;
    }else{
      m[a[i]]++;
      if(m[a[i]]>1)result += a[i];
    }
    pre=a[i];
//cout<<result<<' '<<pre<<endl;
  }

//  for(auto p:m) cout<<p.first<<' '<<p.second<<endl;

  result+=pre;
  cout<<result;

  return 0;
}

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

using namespace std;
typedef long long ll;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mp make_pair
#define pb push_back
#define lp(i,s,f) for(ll i = s; i < ll(f); i++)
#define inF freopen("input.in", "r", stdin);
#define outF freopen("output.in", "w", stdout);
#define endl '\n'
#define MOD 1000000007
#define mm(arr) memset(arr, 0, sizeof(arr))
const int N = 1e5 + 1;
int dp[N];
int arr[N];
int k;
int calc(int idx){
    if(idx == 0){
        return 0;
    }
    if(dp[idx] != -1){
        return dp[idx];
    }
    int num = 1e9;
    for(int i = 1; i <= k; i++){
        if(idx - i < 0)break;
        num = min(num, calc(idx - i) + abs(arr[idx] - arr[idx - i]));
    }
    return dp[idx] = num;;
}
int main(){
    FAST
    int n; cin >> n >> k;
    for(int i = 0; i < n; i++)cin >> arr[i];
    memset(dp, -1, sizeof(dp));
    cout << calc(n - 1) << endl;
    return 0;
}


Measured memory_bytes: 9044
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
using namespace std;
using ll = long long;
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 = 1e9;
const ll MOD = 1e9 + 7;

int main(){
    const double PI = acos(-1);
    double a, b, h, m;
    cin >> a >> b >> h >> m;

    double rad = 2*PI*((h/12.0) + (m/60.0)/12.0 - (m/60.0));
    double d = a*a + b*b -2*a*b*cos(rad);
    cout << fixed << setprecision(15) << sqrt(d) << endl;
}

Measured memory_bytes: 4184
#include<stdio.h>

int main()
{
    long int r,d,x,i,j;

    scanf("%ld%ld%ld",&r,&d,&x);

    for(i=0;i<10;i++)
    {
        x=r*x-d;
        printf("%ld\n",x);
    }




    return 0;
}


Measured memory_bytes: 128