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

double min(double x,double y){
  if(x<y) return x;
  else return y;
}

int main(){
  int n,t[100],sum[100],i,j;
  double dis=0,vl[40002],vv[40002],v[100];
  scanf("%d",&n);
  scanf("%d",&t[0]);
  sum[0]=t[0];
  for(i=1;i<n;i++){
    scanf("%d",&t[i]);
    sum[i]=sum[i-1]+t[i];
  }
  int max=sum[n-1];
  for(i=0;i<=2*max;i++)
    vl[i]=100.0;
  for(i=0;i<200;i++)
    vl[2*max-i]=(double)i/2;
  for(i=0;i<n;i++){
    scanf("%lf",&v[i]);
  }
  for(i=n-1;i>0;i--){
    for(j=2*sum[i-1];j<=2*sum[i];j++){
      vl[j]=min(vl[j],v[i]);}
    for(j=0;(double)j/2+v[i]<=100&&2*sum[i-1]-j>=0;j++)
      vl[2*sum[i-1]-j]=min(vl[2*sum[i-1]-j],v[i]+((double)j/2));
  }
  for(j=0;j<=2*sum[0];j++){
      vl[j]=min(vl[j],v[i]);}
  vv[0]=0.0;
  for(i=0;i<=2*max;i++){
    if(vv[i]<vl[i+1]) vv[i+1]=vv[i]+0.5;
    else if(vv[i]>vl[i+1]) vv[i+1]=vv[i]-0.5;
    else vv[i+1]=vv[i];
    dis+=vv[i+1]/2;
  }
  printf("%lf\n",dis);
  
}

Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_map>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>
#include<iomanip>
#include<bitset>

using namespace std;

#define ll long long int

ll const MOD = 1000000007;
ll const INF = (long long int)1 << 61;

ll mypow(ll x,ll n){
    ll ret = 1;
    while(n > 0){
        if(n&1){
            ret = (ret*x)%MOD;
        }
        x = (x*x)%MOD;
        n >>= 1;
    }
    return ret;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n;
    cin >> n;
    string str;
    cin >> str;

    ll a = 0;
    ll b = 0;

    for(int i = 0; i < n; i++){
        if(str[i] == 'R'){
            a++;
        }else{
            b++;
        }
    }

    if(a > b){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 1000000007;
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

int main() {
	int n;
	cin >> n;
	for(int i = 1;i <= 9;i++) {
		if (n % i == 0 && n / i <= 9) {
			cout << "Yes";
			return 0;
		}
	}
	cout << "No";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
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 INF=1LL<<60;
const int inf=1<<30;
const int mod=1e9+7;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    double r;cin >> r;
    cout << fixed << setprecision(10) << 2*r*M_PI << endl;
}

Measured memory_bytes: 3796
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <chrono>

using namespace __gnu_pbds;
using namespace std;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)

#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define pi pair<ll,ll>
#define pii pair<ll,pi >
#define ppi pair<pi,ll>
#define ppp pair<pi,pi >
#define ex(str,a,b) str.substr((int)(a),min((int)str.size()-a,(int)(b-a+1))) 
#define all(X) X.begin(),X.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// for pair comparison function(ascending order) use return (i1.ff < i2.ff);

/* string operations :
   str.substr (x,y) : returns a substring str[x],str[x+1],...str[x+y-1]
   __builtin_popcount(n) : no. of set bits in n.
*/

const int M = (1<<20)+5;
const int md = 1e9+7;

priority_queue<ll,vector<ll >,greater<ll > > pq;

ll pwr(ll a,ll n,ll m)
{
	ll p=1;
	while(n>0)
	{
		if(n%2==1)
			p=(p*a)%m;
		a=(a*a)%m;
		n=n/2;
	}
	return p;
}

ll ar[M];

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

	ll n,i,p=1,v,fl = 0;

	cin >> n;
	for(i=1;i<=n;++i)
	{
		cin >> ar[i];
		v = (ll)(1e18)/p;
		if(ar[i] == 0)
		{
			cout << 0 << "\n";
			return 0;
		}
		// cout << v << " " << ar[i] << "\n";
		if(ar[i]<=v)
			p = p*ar[i];
		else
			fl = 1;	
	}

	if(fl == 0)
		cout << p << "\n";
	else
		cout << -1 << "\n";
}


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

char a, b, c, d;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> a >> b >> c >> d;
    if(a == b || b == c || c == d)
        cout << "Bad\n";
    else
        cout << "Good\n";
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
int n;
using namespace std;
int main()
{
	cin >> n;
	set<string>s;
	for (int i = 0; i < n; i++)
	{
		string t;
		cin >> t;
		s.insert(t);
	}
	cout << s.size();
	return 0;
}

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

using namespace std;
using ll = long long;
using ii = pair<ll, ll>;

const int MAX { 200010 };
const ll MOD { 1000000007 }, oo { 1LL << 62 };

double E(ll n)
{
    return (n + 1)/2.0;
}

double solve(int N, int K, const vector<ll>& xs)
{
    double sum = 0.0, ans;

    for (int i = 0; i < K; ++i)
        sum += E(xs[i]);

    ans = sum;

    for (int i = K; i < N; ++i)
    {
        sum = sum - E(xs[i - K]) + E(xs[i]);
#ifdef DEBUG
    cout << "res = " << res << ", ans = " << ans << endl;
#endif
        ans = max(ans, sum);
    }
 
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);

    int N, K;
    cin >> N >> K;

    vector<ll> xs(N);

    for (int i = 0; i < N; ++i)
        cin >> xs[i];

    auto ans = solve(N, K, xs);

    cout.precision(15);
    cout << fixed << ans << '\n';

    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;
using P = pair<int, int>;

void solve(ll H, ll W) {
  if (H == 1 || W == 1)
    cout << 1 << endl;
  else
    cout << ((H + 1) / 2) * ((W + 1) / 2) + (H / 2) * (W / 2) << endl;
}

int main(){
  // int 3E4
  // ll 2E9
  // ll ll 9E18
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll H, W;
  cin >> H >> W;
  solve(H, W);
  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>
#define DEBUG true
#ifdef ONLINE_JUDGE
#undef DEBUG
#define DEBUG false
#endif 

using namespace std;

#define TRACE(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); cerr << endl;}

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << "[" << *it << " = " << a << "]";
	err(++it, args...);
}

#define MAXN ((int)2e5+5)
#define MOD ((int)1e9 + 7)
#define INF ((int)1e9 + 9)
#define ll long long
#define _ << " " <<
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define LOG(x) if(DEBUG) cerr << x << endl;
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pii pair<int,int>
#define mid ((l+r)/2)

int n,m,t;
ll dp[3005][3005][4];
ll mp[3005][3005];

ll max4(ll mx0, ll mx1, ll mx2, ll mx3)
{
	return max(max(mx0, mx1), max(mx2,mx3));
}

ll maxa(int x, int y)
{
	return max4(dp[x][y][0], dp[x][y][1], dp[x][y][2], dp[x][y][3]);
}

signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin >> n >> m >> t;

	for (int i = 0; i < t; ++i)
	{
		int a,b,c;
		cin >> a >> b >> c;
		mp[a][b] = c;
	}	

	dp[1][1][1] = mp[1][1];

	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			for (int k = 0; k < 4; ++k)
				dp[i][j][k] = max4(
					dp[i][j-1][k],
					(k>0) * (dp[i][j-1][k-1] + mp[i][j]),
					(k == 0) * (maxa(i-1, j)),
					(k == 1) * (maxa(i-1, j) + mp[i][j])
					);

	cout << maxa(n,m) << endl;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
*/

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

int main() {
    int n;
    cin >> n;
    vector<string> s;
    vector<vector<int>> m;
    m.resize(n);
    s.resize(n);
    rep(i,n){
        cin >> s[i];
        m[i].resize(26,0);
        rep(j,s[i].length()){
            m[i][s[i][j]-'a']++;
        }
    }
    vector<int> ans;
    ans.resize(26,100);
    rep(i,26){
        rep(j,n)
        ans[i]=min(ans[i],m[j][i]);
    }

    rep(i,26){
        rep(j,ans[i])printf("%c", 'a'+i);
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
S = input()
s = list(S)
L = int(s[0] + s[1])
R = int(s[2] + s[3])
if 0< L <= 12:
    if 0<R<=12:
        print('AMBIGUOUS')
    else:
        print('MMYY')        
elif 0< R <= 12:
    print('YYMM')
else:
    print('NA')

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <cmath>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define FOR(i,a,b) for (int i=(int)(a);i<(int)(b);++i)
#define FORE(i,a,b) for (int i=(int)(a);i<=(int)(b);++i)
#define REP(i,n) FOR(i,0,n)
#define REPE(i,n) FOR(i,0,n)

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

int main() {
  int N; cin >> N;
  int ans = 0;
  
  FORE(i,1,N) {
    string tmp = to_string(i);
    if (tmp.size() & 1) ans++;
  }
  cout << ans;

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
  int a, b, c;
  cin >> a >> b >> c;
  
  if(((a == b) && (a == c)) || ((a != b) && (b != c) && (c != a)))
    cout << "No" << endl;
  else
    cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 3580
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, L; cin >> N >> L;
  ll a, b; cin >> a;
  int j = -1;
  ll mx = 0;
  FOR(i,1,N) {
    cin >> b;
    if(mx < a + b) {
      mx = a + b;
      j = i;
    }
    a = b;
  }
  if(mx >= L) {
    cout << "Possible" << endl;
    FOR(i,1,N) {
      if(i == j) break;
      cout << i << endl;
    }
    for(int i = N - 1; i >= 1; i--) {
      if(i == j) break;
      cout << i << endl;
    }
    cout << j << endl;
  } else {
    cout << "Impossible" << endl;
  }
  return 0;
} 

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

int main() {
	int N, K;
	cin >> N >> K;
	long long ans = 0;
	for (int b = K + 1; b <= N; b++) {
		int MAX = (N - K) / b;
		ans += (b - K) * (MAX + 1);
		ans -= max(0, b * (MAX + 1) - N - 1);
		if (K == 0) ans--; //a*0+0
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
N, M = map(int, input().split())
sc = [[] for _ in range(M)]
for i in range(M):
    sc[i] = list(map(int, input().split()))


S = " " * N
sc = list(set(map(tuple, sc)))

memo = [-1] * N
S = list(S)
for numbers in sc:
    if memo[numbers[0]-1] == -1 or S[numbers[0]-1] == numbers[1]:
        S[numbers[0]-1] = str(numbers[1])
        memo[numbers[0]-1] = 1
    else:
        print(-1)
        break

    if numbers == (1, 0) and N > 1:
        print(-1)
        break
else:
    for i in range(N):
        if S[i] == " ":
            if i == 0 and N > 1:
                S[i] = "1"
            else:
                S[i] = "0"
    S = list(map(int, S))
    for i in range(len(S)):
        print(S[i], end="")




        

Measured memory_bytes: 38384
#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int main()
    {
    	int a,b,c;
    	cin>>a>>b>>c;
        if(a==b && b!=c)
         cout<<"Yes";
        else if(b==c && b!=a)
         cout<<"Yes";
        else if(a==c && b!=a)
         cout<<"Yes";
        else
         cout<<"No";
        return 0;

    }


Measured memory_bytes: 3636
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
#define rep(i,a,b) for (int i = (a); i < (b); i++)
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef complex<double> com;
const int mod = 1e9 + 7;
const int MOD = 998244353;
const int inf = 2e9;

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

int main() {
	int n; cin >> n;
	ll a, b; cin >> a >> b;
	rep(i, 1, n) {
		ll p1, p2; cin >> p1 >> p2;
		ll d = max(a / p1 + (a % p1 == 0 ? 0 : 1), b / p2 + (b % p2 == 0 ? 0 : 1));
		a = max(p1, p1 * d),b = max(p2, p2 * d);
	}
	printf("%lld", a + b);
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#define mod 1000000007
#define int long long
int n,a,b,c,d,f[10010],fac[10010],inv[10010];
int quickpow(int x,int y){
	if(y==0)return 1;
	if(y%2==0)return quickpow(x*x%mod,y/2);
	if(y%2==1)return quickpow(x*x%mod,y/2)*x%mod;
}
signed main(){
	scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d);
	fac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%mod;
	inv[n]=quickpow(fac[n],mod-2);
	for(int i=n-1;i>=0;i--)
		inv[i]=inv[i+1]*(i+1)%mod;
	f[0]=1;
	for(int i=a;i<=b;i++)
		for(int j=std::min(i*d,n);j>=i*c;j--)
			for(int k=c,now=quickpow(inv[i],c),M=j-c*i;k<=d&&M>=0;k++,M-=i,now=now*inv[i]%mod)
                (f[j]+=fac[j]*now%mod*inv[M]%mod*f[M]%mod*inv[k]%mod)%=mod;
    printf("%lld\n",f[n]);
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <iomanip>
#define MOD 1000000007
#define pb push_back
using namespace std;

long long dp[3030][3030];
long long a[3030];

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

	for (int i = 1; i <= n; i++) cin >> a[i];

	for (int r = 1; r <= n; r++) {
		for (int l = r; l >= 1; l--) {
			if (l == r) dp[l][r] = a[l];
			else dp[l][r] = max(a[l] - dp[l + 1][r], a[r] - dp[l][r - 1]);
		}
	}

	cout << dp[1][n];
	return 0;
}

Measured memory_bytes: 71936
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <functional>
#include <queue>
#include <stack>
#include <string.h>
#include <list>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define all(a)  (a).begin(), (a).end()
#define rall(a) (a).rbegin(),(a).rend()
#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 PB push_back
#define MP make_pair
#define EPS (1e-7)
#define INF (1e12)
#define PI (acos(-1))

int main(){
    int a, b, x;
    cin >> a >> b >> x;
    string res;
    if(a <= x && x <= a+b) res = "YES";
    else res = "NO";
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main (void)
{
  int n,i,j,k,l,b,f,r,v,count[5][4][11];
  for(i=0;i<5;i++){
    for(j=0;j<4;j++){
      for(k=0;k<11;k++)
	count[i][j][k]=0;
	}
  }
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d%d%d%d",&b,&f,&r,&v);
    count[b][f][r]+=v;
      }
  for(i=1;i<=4;i++){
    for(j=1;j<=3;j++){
      for(k=1;k<=10;k++){
	printf(" %d",count[i][j][k]);
      }
      printf("\n");
    }
    if(i!=4){
      printf("####################\n");
    }
  }
  return 0;
}

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

s = input()
n = len(s)
flag = False

def isKaibun (bun):
    rev = ''.join(list(reversed(bun)))
    f = False
    if rev == bun:
        f = True
    return f

s_sub_0 = s[ : int((n - 1) / 2)]
s_sub_1 = s[int((n + 3) / 2) - 1:]

if not isKaibun(s):
    flag = False
elif isKaibun(s_sub_0) and isKaibun(s_sub_1):
    flag = True

if flag:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3188
#include <stdio.h>

struct Rule{
	int dx;
	int dy;
};

Rule rule[4];

int countPattern(int board[16], int pos)
{
	if(board[pos]){
		if(pos < 15) return countPattern(board, pos+1);
		else{
			return 1;
		}
	}
	board[pos] = pos+1;
	
	int sum = 0;
	int other_posx, other_posy;
	
	for(int i = 0; i < 4; i++){
		other_posx = pos % 4 + rule[i].dx;
		other_posy = pos / 4 + rule[i].dy;
		if(other_posx < 0 || other_posx >= 4 || other_posy < 0 || other_posy >= 4 || board[other_posx + other_posy * 4]) continue;
		board[other_posx + other_posy * 4] = pos+1;
		sum += countPattern(board, pos+1);
		board[other_posx + other_posy * 4] = 0;
	}
	
	board[pos] = 0;
	return sum;
}

	
int main(void)
{
	int board[16];
	
	while(1){
		for(int i = 0; i < 4; i++){
			scanf("%d", &rule[i].dx);
			if(rule[i].dx >= 4) goto end;
			scanf("%d", &rule[i].dy);
		}
		
		for(int i = 0; i < 16; i++) board[i] = 0;
		
		printf("%d\n", countPattern(board, 0));
	}
	
	end:
	return 0;
}

Measured memory_bytes: 2524
#include<iostream>

using namespace std;

int main(){
	int A, B, K;

	cin >> K >> A >> B;

	for(int i = A; i <= B; ++i){
		if(i % K == 0){
			cout << "OK" << endl;
			return 0;
		}
	}

	cout << "NG" << endl;
	return 0;
}

Measured memory_bytes: 3616
#include<bits/stdc++.h>
#define LLI long long int
#define pii pair<int,int>
#define fst first
#define sec second
#define ULTRA 2134567890
#define MOD 1000000007LL
#define de(x) if(x!=0 && MODE==x)
#define MODE 0
using namespace std;

LLI fac[200007];

void prepare()
{
    fac[0] = 1;
    for( LLI i=1; i<=200000; i++)
    {
        fac[i] = fac[i-1] * i % MOD;
    }
}

LLI pwr( LLI a, LLI b)
{
    LLI ans = 1;
    while(b)
    {
        if(b&1)
            ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

LLI C( LLI a, LLI b)
{
    LLI ans = 1;
    for( LLI i=0; i<b; i++)
    {
        ans = ans * ( a - i ) % MOD;
        ans = ans * pwr( i+1, MOD-2) % MOD;
    }
    return ans;
}

int main()
{
    int i,j;
    LLI n, a, b;

    prepare();
    scanf("%lld %lld %lld", &n, &a, &b);
    LLI x1 = pwr( 2, n);
    LLI x2 = C( n, a);
    LLI x3 = C( n, b);
    LLI ans = ( x1 - x2 - x3 - 1LL + MOD * 3LL ) % MOD;
    de(1)
    {
        printf(" x1 = %lld\n", x1);
        printf(" x2 = %lld\n", x2);
        printf(" x3 = %lld\n", x3);
    }
    printf("%lld\n", ans);

    return 0;
}

//
//          ___ ___  __________  __________
//         /////\  \/\   ______\/\\\\\\\\\\\  Code by ~Ice Tea~ of
//        //// \ \  \ \  \_____/\ \\\\_____/      New Empire of CHSH ...
//       ////   \ \  \ \  \      \ \\\\\\\\\\\
//      ////__   \ \  \ \  \      \ \\\\_____/
//     ///////\   \ \  \ \  \______\ \\\\_______   ________
//    ////____/    \ \__\ \___   ___\ \\\\\\\\\\\ _\  ___  \_
//   /__/           \/__/\/__/\  \__/\ \\\\_____//\  .\_/\_  \
//                           \ \  \   \ \\\\\\\\\\\\  \_\/_\  \
// ... with the AC Power of   \ \  \   \ \\\\_____/ \   _____  \
//   The Great Tsundere Doggy. \ \  \   \ \\\\     \ \  \  \ \  \
//                              \ \__\   \ \\\\\\\\\\ \__\  \ \__\
//                               \/__/    \/________/\/__/   \/__/
//


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

typedef long long ll;

#define        optimize           ios::sync_with_stdio(0); cin.tie(0);
#define PI    acos(-1.0)
#define pb push_back
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define RESET(a, b) memset(a, b, sizeof(a))
#define pii pair <int, int>
#define pll pair <ll, ll>
#define setbiti(x) __builtin_popcount(x)
#define setbitll(x) __builtin_popcountll(x)
#define gcd(a, b) __gcd(a, b)

#define        MX        200005

int main()
{
    optimize
    ll n, k, x, y;
    cin>>n>>k>>x>>y;

    if(k >= n){
        cout<<n*x<<endl;
        return 0;
    }

    ll prothom = k, baki = n-k;

    cout<<prothom*x+baki*y<<endl;
}


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

using namespace std;

int main () {
	int n;
	cin >> n;
	for (int i = 1; i <= 9; ++i) {
		if (n % i == 0 && n / i <= 9) {
			cout << "Yes";
			return 0;
		}
	}
	cout << "No";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N][N];

int main() {
  int A, B;
  cin >> A >> B;
  for(int i = 1; i <= 50; ++i) 
    for(int j = 1; j <= 100; ++j) 
      a[i][j] = 1;
  A--, B--;
  for(int i = 1; i <= 50; i += 2)
    for(int j = 1; j <= 100; j += 2) {
      if(A) a[i][j] = 0, A--;
    }
  for(int i = 52; i <= 100; i += 2)
    for(int j = 1; j <= 100; j += 2) {
      if(B) a[i][j] = 1, B--;
    }
  printf("100 100\n");
  for(int i = 1; i <= 100; ++i) {
    for(int j = 1; j <= 100; ++j) {
      if(a[i][j]) printf("#");
      else printf(".");
    }
    puts("");
  }
  return 0;
}

/*
2 3 
3 3
##.
..#
#.#
*/

Measured memory_bytes: 384
#include <stdio.h>
#include<string.h>
int main()
{
long long int a,b,c=0,d=0,w=0,i,str1=0,str2=0,flag,j,count=0,k,n,sum=0;

scanf("%lld %lld %lld",&a,&b,&c);
if(a+b==c || b+c==a || a+c==b )   
{
    printf("Yes\n");
}else{
    printf("No\n");
}
 return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <algorithm>
#include <cmath>
#include <stack>
#include <map>
#include <numeric>
using namespace std;

#define REP(i,n) for(int (i)=0; (i)<(n); (i)++)
#define FOR(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define PUSH(n,v) for(int i=0; i<(n); i++) {int j; cin >> j; v.push_back(j);}
#define ALL(v) v.begin(), v.end()
#define print(s) cout << (s) << endl

int main() {
    double xa1,ya1,xa2,ya2,xb1,yb1,xb2,yb2;
    while(cin>>xa1>>ya1>>xa2>>ya2>>xb1>>yb1>>xb2>>yb2) {
        if (xb1 < xa1) {
            if (xb2 < xa1) cout << "NO" << endl;
            else {
                if (yb1 > ya1) {
                    if (yb1 > ya2) cout << "NO" << endl;
                    else cout << "YES" << endl;
                }else {
                    if (yb2 < ya1) {
                        cout << "NO" << endl;
                    }else {
                        cout << "YES" << endl;
                    }
                }
            }
        }else {
            if (xa2 < xb1) cout << "NO" << endl;
            else {
                if (ya1 > yb1) {
                    if (ya1 > yb2) cout << "NO" << endl;
                    else cout << "YES" << endl;
                }else {
                    if (ya2 < yb1) {
                        cout << "NO" << endl;
                    }else {
                        cout << "YES" << endl;
                    }
                }
            }
        }
    }
    return 0;
}

Measured memory_bytes: 1220
#!/usr/bin/env python3
import sys

def solve(N: int, K: int, A: "List[int]"):
    ans = 0
    max_bit = 40
    for i in range(max_bit+1):
        t = 2**(max_bit-i)
        count = len([1 for a in A if a&t > 0])
        if t <= K and count < N / 2:
            count = N - count
            K -= t
        ans += count * t
    print(ans)
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()


Measured memory_bytes: 16868
using System;
using System.Linq;

namespace ProgramingStydying
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var a = Console.ReadLine().Split().Select(int.Parse).ToList();
            a.Sort();
            a.Reverse();

            var alice = 0;
            var bob = 0;

            for (int i = 0; i < n; i += 2) 
            {
                alice += a[i];
            }
            for (int i = 1; i < n; i += 2)
            {
                bob += a[i];
            }
            Console.WriteLine(alice - bob);
        }
    }
}

Measured memory_bytes: 28304
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

vector<int> divisor(int n) {
  vector<int> ret;
  for(int i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(ALL(ret));
  return ret;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<int> a(n);
  map<int, int> mp;
  REP(i,n){ 
    cin >> a[i];
    mp[a[i]]++;
  }
  //sort(ALL(a));
  if(mp[1]>0){
    cout << (mp[1]==1 ? 1 : 0) << endl;
    return 0;
  }

  int ans = n;
  REP(i,n){
    mp[a[i]]--;

    auto div = divisor(a[i]);
    for(auto d: div){
      if(mp[d]>0){
        ans--;
        break;
      }
    }

    mp[a[i]]++;
  }

  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 32936
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int H,W;
  cin >> H >> W;
  vector<string> letter(H);
  
  for(int i = 0; i < H; i++) {
    cin >> letter.at(i);
  }
  
  for(int j = 0; j < W + 2; j++) {
    cout << "#";
  }
  
  cout << endl;
  
  for(int i = 0; i < H; i++) {
    cout << "#" << letter.at(i) << "#" << endl;
  }
  
  for(int j = 0; j < W + 2; j++) {
    cout << "#";
  }
  
  cout <<endl;
}

Measured memory_bytes: 256
// </> : towhid1zaman

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair< int, int > pii;
typedef pair< pii, int > ppi;
#define fill(a,b) memset(a,b,sizeof(a))
#define all(v) (v).begin(),(v).end()
#define sp(k) cout<<setprecision(k)<<fixed;
#define rep(i,a) for(int i=0;i<a;i++)
#define rep1(i,a,b) for(int i=(a);i<=(b);++i)
#define irep(i,b,a) for(int i=(b);i>=(a);--i)
#define minv(v) *min_element(all(v))
#define maxv(v) *max_element(all(v))
#define unq(v) sort(all(v)),(v).erase(unique(all(v)),(v).end())
#define _ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
#define sqr(a) ((a)*(a))
#define sz(a) int(a.size())
#define ff first
#define ss second
#define pb push_back

const double pi = acos(-1.0);
const int mod = 1000000007; // (int)1e9+7
const int inf = 0x3f3f3f3f;// (int)3e18;
const int maxn = 2000100;



int main(){
        _
        int n;
        cin >> n;
        vll a(n + 1);
        vll b(n);
        rep(i, n + 1) cin >> a[i];
        rep(i, n) cin >> b[i];
        ll ans = 0;
        rep(i, n) {
            int left = min(a[i], b[i]);
            ans += left;
            a[i] -= left;
            b[i] -= left;
            int right = min(a[i + 1], b[i]);
            ans += right;
            a[i + 1] -= right;
            b[i] -= right;
        }
        cout << ans << endl;


return 0;
}



Measured memory_bytes: 1792
S=input()
ans="WA"
for i in range(len(S)):
  if S[i]=="A" and S[2:-1].count("C")==1:
    s=S.find("C",2,-1)-1
    SS=S[1:]
    SS=SS[:s]+SS[s+1:]
    if SS.islower() is True:
      ans="AC"
      break
print(ans)

Measured memory_bytes: 3060
#include<stdio.h>
int main()
{
    int a[]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int k;
    scanf("%d",&k);
    printf("%d",a[k-1]);
    return 0;
}

Measured memory_bytes: 128
#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <functional>

using namespace std;


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

	sort(s.begin(), s.end());

	//manca se c'è solo una lettera
	if (s.length() == 1 && s[0] != 'a')
	{
		char c = s[0] - 1;
		cout << c << endl;
		return 0;
	}
	else if (s.length() == 1 && s[0] == 'a')
	{
		cout << 'b' << endl;
		return 0;
	}

	//e se manca tipo la lettera a
	if (s[0] != 'a')
	{
		cout << 'a' << endl;
		return 0;
	}


	for (int a = 1; a < s.length(); ++a)
	{
		if ((s[a] - s[a-1]) > 1)
		{
			char c = s[a - 1] + 1;
			cout << c << endl;
			return 0;
		}	
	}
	if (s[s.length() - 1] != 'z')
	{
		char c = s[s.length() - 1] + 1;
		cout << c << endl;
	}
	else
		cout << "None" << endl;

	return 0;
}

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

using namespace std;


int main(){
	int n, m;
	cin >> n >> m;
	int par[100];

	for(int i = 0; i < n; i++) cin >> par[i];

	auto fc = [&](int k){
		for(int i = 0; i < n-1; i++){
			if(par[i]%k > par[i+1]%k) swap(par[i], par[i+1]);
		}
		return;
	};

	for(int i = 1; i <= m; i++) fc(i);

	for(int i = 0; i < n; i++){
		cout << par[i] << endl;
	}

	return 0;
}


Measured memory_bytes: 3100
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();
    int[] a = new int[N];
    int[] b = new int[N];
    for (int i = 0; i < N; i++) {
      a[i] = sc.nextInt();
      b[i] = sc.nextInt();
    }
    int[] c = new int[M];
    int[] d = new int[M];
    for (int i = 0; i < M; i++) {
      c[i] = sc.nextInt();
      d[i] = sc.nextInt();
    }
    for (int i = 0; i < N; i++) {
      int min = Integer.MAX_VALUE;
      int index = -1;
      for (int j = 0; j < M; j++) {
        int dist = Math.abs(a[i] - c[j]) + Math.abs(b[i] - d[j]);
        if (dist < min) {
          min = dist;
          index = j;
        }
      }
      System.out.println(index + 1);
    }
  }
}

Measured memory_bytes: 23508
#include <bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef pair<int, int> Pint;
typedef pair<int64_t, int64_t> Pll;

int main() {
    int R, N, G, B, ans = 0;
    cin >> R >> G >> B >> N;

    for (int i = 0; i * R <= N; i++){
        for (int j = 0; j * G <= N - i * R; j++){
            if ((N - i * R - j * G) % B == 0){
                ans++;
            }
        }
    }
    cout << ans << endl;
}


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

typedef vector<int> vi;
typedef vector<vi> vvi;

#define loop(i,a,b) for(int i=(a); i<int(b); i++)
#define rep(i,b) loop(i,0,b)

int main(){
    int M,T,P,R;
    while(cin>>M>>T>>P>>R && M){
        vector<vector<vector<pair<int,bool>>>> v(T,vector<vector<pair<int,bool>>>(P));
        rep(i,R){
            int m,t,p,j;
            cin>>m>>t>>p>>j;
            t--,p--;
            v[t][p].push_back(make_pair(m,j==0));
        }
        // solved, time, id
        vvi rank(T);
        rep(i,T){
            int s = 0;
            int t = 0;
            rep(j,P)if(v[i][j].size()!=0 && v[i][j].back().second){
                s++;
                t+=v[i][j].back().first;
                t+=20*(v[i][j].size()-1);
            }
            rank[i] = vi{s,t,i+1};
        }
        sort(rank.begin(),rank.end(),[](const vi& a, const vi& b){
                if(a[0]!=b[0]) return a[0]>b[0];
                if(a[1]!=b[1]) return a[1]<b[1];
                else return a[2]>b[2];
            });
        cout << rank[0][2];
        rep(i,T-1){
            if(rank[i+1][0]==rank[i][0] && rank[i+1][1]==rank[i][1]){
                cout << "=";
            }
            else cout << ",";
            cout << rank[i+1][2];
        }
        cout << endl;
    }
}

Measured memory_bytes: 1256
from collections import Counter

S = input()

"""
counts = Counter()
total = 0
for d in S:
    d = int(d)
    nextCounts = Counter()
    nextCounts[d] += 1
    for k, v in counts.items():
        nextCounts[(10 * k + d) % 2019] += v

    counts = nextCounts
    total += counts[0]
    #print(counts)

print(total)

"""

"""
def modInverse(a, m):
    m0 = m
    y = 0
    x = 1

    if m == 1:
        return 0

    while a > 1:

        # q is quotient
        q = a // m

        t = m

        # m is remainder now, process
        # same as Euclid's algo
        m = a % m
        a = t
        t = y

        # Update x and y
        y = x - q * y
        x = t

    # Make x positive
    if x < 0:
        x = x + m0

    return x
"""


#div10 = modInverse(10, 2019)

div10 = 202
#m = 1
mInv = 1

off = 0
counts = [0 for i in range(2019)]
total = 0
for d in S:
    d = int(d)
    off = (10 * off + d) % 2019
    #m *= 10
    mInv = (mInv * div10) % 2019
    #assert modInverse(m, 2019) == mInv
    counts[((d - off) * mInv) % 2019] += 1
    total += counts[((0 - off) * mInv) % 2019]

print(total)


Measured memory_bytes: 68708
class node:
    parent = None
    depth = 0
    degree = 0
    height = 0

    def __init__(self, no, l, r,sib):
        self.no = no
        self.left = l
        self.right = r
        self.sibling = sib
    
    def setsibdepth(self, nodes, d):
        if self.left is None:
            return
        self.depth = d
        self.left.sibling = self.right
        self.right.sibling = self.left
        self.left.setsibdepth(nodes, d+1)
        self.right.setsibdepth(nodes, d+1)

    def setheight(self, nodes, h):
        if self.left is None:
            return h-1
        return max(self.left.setheight(nodes, h+1), self.right.setheight(nodes, h+1))


def preorder(head, h, A):
    if h.left is None:
        return
    A.append(h.no)
    preorder(head, h.left, A)
    preorder(head, h.right, A)
    if head == h:
        print('', *A)

def inorder(head, h, B):
    if h.left is None:
        return
    inorder(head, h.left, B)
    B.append(h.no)
    inorder(head, h.right, B)
    if head == h:
        print('', *B)

def postorder(head, h, C):
    if h.left is None:
        return
    postorder(head, h.left, C)
    postorder(head, h.right, C)
    C.append(h.no)
    if head == h:
        print('', *C)

#葉はNULL, 根の親はNone

NULL = node(-1, None, None, None)
head = None
nodes = []
n = int(input())
for i in range(n):
    temp = node(i, None, None, NULL)
    nodes.append(temp)

for i in range(n):
    temp = list(map(int,input().split()))
    if temp[1] == -1:
        nodes[temp[0]].left = NULL
    else:
        nodes[temp[0]].left = nodes[temp[1]]
        nodes[nodes[temp[0]].left.no].parent = nodes[temp[0]]

    if temp[2] == -1:
        nodes[temp[0]].right = NULL
    else:
        nodes[temp[0]].right = nodes[temp[2]]
        nodes[nodes[temp[0]].right.no].parent = nodes[temp[0]]

    if temp[1] == -1 and temp[2] == -1:
        nodes[temp[0]].degree = 0
    elif temp[1] != -1 and temp[2] != -1:
        nodes[temp[0]].degree = 2
    else:
        nodes[temp[0]].degree = 1

for i in range(n):
    if nodes[i].parent is None:
        head = nodes[i]
        break

head.setsibdepth(nodes, 0)

for i in range(n):
    nodes[i].height = nodes[i].setheight(nodes, 0)

A = []
B = []
C = []
print("Preorder")
preorder(head, head, A)
print("Inorder")
inorder(head, head, B)
print("Postorder")
postorder(head, head, C)


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

const int inf = 10, maxn = 1e5;

int ans;

namespace MCMF{
	int head[maxn], nxt[maxn], to[maxn], c[maxn], r[maxn], tot = 1;
	void add(int u, int v, int w, int f) {
		assert(++tot < maxn);
		nxt[tot] = head[u];
		to[tot] = v;
		c[tot] = w;
		r[tot] = f;
		head[u] = tot;
	}
	void add2(int u, int v, int w, int f) {
		add(u,v,w,f), add(v,u,-w,0);
	}
#define mp make_pair
	typedef pair<long long, int> qnode;
	int dis[maxn], inq[maxn], pre[maxn];
	void spfa(int s) {
		memset(dis, 0x3f, sizeof(dis));
		memset(pre, 0, sizeof(pre));
		queue<int> q;
		dis[s] = 0;
		q.push(s);
		while (!q.empty()) {
			int u = q.front();
			q.pop(); inq[u] = 0;
			for (int e = head[u]; e; e = nxt[e]) {
				if (!r[e]) continue;
				int v = to[e], w = c[e];
				if (dis[u]+w < dis[v]) {
					pre[v] = e;
					dis[v] = dis[u]+w;
					if (!inq[v]) {
						q.push(v);
						inq[v] = 1;
					}
				}
			}
		}
	}
	void augment(int t) {
		int flow = inf;
		for (int e = pre[t]; e; e = pre[to[e^1]]) {
			flow = min(flow, r[e]);
		}
		for (int e = pre[t]; e; e = pre[to[e^1]]) {
			r[e] -= flow;
			r[e^1] += flow;
		}
		ans += flow*dis[t];
	}
}
using namespace MCMF;


int n, rx[maxn], ry[maxn], rc[maxn], bx[maxn], by[maxn], bc[maxn];
signed main() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> rx[i] >> ry[i] >> rc[i];
		add2(1, i+10, 0, rc[i]);
		add2(i+10, 3, rx[i]+ry[i], inf);
		add2(i+10, 4, rx[i]-ry[i], inf);
		add2(i+10, 5, -rx[i]+ry[i], inf);
		add2(i+10, 6, -rx[i]-ry[i], inf);
	}
	for (int i = n; i < 2*n; ++i) {
		cin >> bx[i] >> by[i] >> bc[i];
		add2(3, i+10, -bx[i]-by[i], inf);
		add2(4, i+10, -bx[i]+by[i], inf);
		add2(5, i+10, bx[i]-by[i], inf);
		add2(6, i+10, bx[i]+by[i], inf);
		add2(i+10, 2, 0, bc[i]);
	}
	while (spfa(1), pre[2]) augment(2);
	cout << -ans;
}

Measured memory_bytes: 8576
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
signed main() {
    cin>>n;
    int dp[n+1];
    int a[n];
    for(int i = 0;i<n;i++) {
        cin>>a[i];
    }
    dp[n-1] = 0;
    dp[n-2] = abs(a[n-1]-a[n-2]);
//    if (n>=3) dp[n-3] = min(dp[n-2] + abs(a[n-3]-a[n-2]) ,abs(a[n-3]-a[n-1]));
    for(int i = n-3;i>=0;i--) {
        dp[i] = min(dp[i+1] + abs(a[i]-a[i+1]),dp[i+2] + abs(a[i]-a[i+2]));
    }
    cout << dp[0];
}



Measured memory_bytes: 1792
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoderCSharp {
    class Program {
        static void Main(string[] args) {
            var n = Console.ReadLine();
            var s = Console.ReadLine();

            var count = 0;
            for (var i = 0; i < int.Parse(n) - 2; i++) {
                if (s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C') {
                    count++;
                }
            }
            Console.WriteLine(count);
        }
    }
}


Measured memory_bytes: 13140
#include<iostream>
#include<cstdio>
#include<string>
#pragma warning(disable:4996)

using namespace std;

int main() {
	string a, b, c;
	cin >> a;
	cin >> b;
	cin >> c;
	char ch = 'a';
	bool loop = true;
	while (loop)
	{
		switch (ch)
		{

		case 'a':
			if (a.size() == 0) {
				cout << 'A';
				loop = false;
				break;
			}
			ch = a[0];
			a.erase(0, 1);
			break;
		case 'b':
			if (b.size() == 0) {
				cout << 'B';
				loop = false;
				break;
			}
			ch = b[0];
			b.erase(0, 1);
			break;
		case 'c':
			if (c.size() == 0) {
				cout << 'C';
				loop = false;
				break;
			}
			ch = c[0];
			c.erase(0, 1);
			break;
		default:
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 256
//#############################################################################
#include "bits/stdc++.h"
//#############################################################################
//Macros 
#define MOD 1000000007
#define eb emplace_back
#define mp make_pair
#define fr first
#define sc second
#define vec vector
#define len(x) x.size()
#define min3(a, b, c) min(a, min(b, c))
#define max3(a, b, c) max(a, max(b, c))
#define all(v) v.begin(), v.end()
#define alla(a, n) a, a + n
//Type Defs
typedef long long ll;
typedef unsigned long long ull;
//#############################################################################
using namespace std;
//#############################################################################
//Helpers
void io_handler()
{
#ifdef LOCAL_TESTING
    freopen("inputf.in", "r", stdin);
    freopen("outputf.in", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
void print_matrix(vector<vector<ll>> mat){
    for(auto row: mat){
        for(auto e : row){cout << e << " ";}
        cout << endl;
    }
}
void print_vector(vector<ll> v){
    for(auto e : v){cout<< e <<" ";}
    cout<<endl;
}
map<int,int> get_count(vector<ll> v){
    map<int,int> count;
    for(auto e: v){
        if(count.find(e)!=count.end()){count[e]++;}
        else{count[e] = 1;}}
    return count;
}
//#############################################################################
//Solution
void solve(){
    int n,m; 
    cin>>n>>m;
    vec<vec<char>> grid(n,vec<char>(m));
    vec<vec<ll>> dp(n,vec<ll>(m,0));
    for(int i = 0; i<n; i++){
        for(int j = 0; j<m; j++){
            cin>>grid[i][j];
        }
    }
    dp[0][0] = 1;
    //For columns
    for(int i  = 1; i<m; i++){
        if(grid[0][i] == '#'){
            dp[0][i] = 0LL;
        } else {
            dp[0][i] = (dp[0][i]%MOD + dp[0][i-1]%MOD)%MOD;
        }
    }
    //For rows
    for(int i = 1; i<n; i++){
        if(grid[i][0]=='#'){
            dp[i][0] = 0LL;
        } else {
            dp[i][0] =  (dp[i][0]%MOD + dp[i-1][0]%MOD)%MOD;
        }
    }
    for(int i = 1; i<n; i++){
        for(int j = 1; j<m; j++){
            if(grid[i][j]=='#'){
                dp[i][j] = 0LL;
            } else {
                dp[i][j] = (dp[i][j]%MOD 
                    +dp[i-1][j]%MOD + dp[i][j-1]%MOD)%MOD;
            }
        }
    }
    cout<<dp[n-1][m-1]<<endl;
}
//#############################################################################
//Driver
int main()
{
    io_handler();
    int t = 1;
    //cin>>t;
    for (int i = 0; i < t; i++){
        solve();
    }
#ifdef LOCAL_TESTING
    cout << "⏰ Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}
//#############################################################################

Measured memory_bytes: 9088
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string str = Console.ReadLine();
		string ans = "Good";
		for(var i=0;i<=2;i++){
			if(str.Substring(i,1)==str.Substring(i+1,1)){
				ans = "Bad";
			}
		}
		Console.WriteLine(ans);
	}
}

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

int main() {
  string s, t;
  cin >> s >> t;
  int ls = s.size();
  int lt = t.size();
  string ans = "UNRESTORABLE";
  for (int si = 0; si + lt - 1 < ls; si++) {
    string ss = s;
    bool same = true;
    rep(i, lt) { 
      if (ss[si + i] == '?') ss[si + i] = t[i];
      if (ss[si + i] != t[i]) same = false;
    }
    if (!same) continue;
    rep(i, ls) if (ss[i] == '?') ss[i] = 'a';
    ans = ss;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3540
(declaim (optimize (speed 3) (debug 0) (safety 0)))

(defun make-union-find (n)
  (let ((x (make-array n)))
    (loop for i from 0 below n
       do (setf (aref x i) i))
    x))

(defun lookup (uf n)
  (if (= (aref uf n) n)
      n
      (setf (aref uf n)
	    (lookup uf (aref uf n)))))

(defun unite (uf n m)
  (setf (aref uf (lookup uf n))
	(lookup uf m)))

(defun force (uf)
  (loop for x from 0 below (length uf)
     do (lookup uf x)))

(defun main ()
  (let* ((n (read))
	 (k (read))
	 (l (read))
	 (road (make-union-find n))
	 (rail (make-union-find n)))
    (loop repeat k
       do (let ((p (1- (read)))
		(q (1- (read))))
	    (unite road p q)))
    (loop repeat l
       do (let ((r (1- (read)))
		(s (1- (read))))
	    (unite rail r s)))
    (force road)
    (force rail)

    (let ((table (make-hash-table)))
      (labels ((idx (i) (+ (* (lookup road i) n)
			   (lookup rail i))))
	(loop for i from 0 below n
	   do (if (gethash (idx i) table)
		  (incf (gethash (idx i) table))
		  (setf (gethash (idx i) table) 1)))
	(loop for i from 0 below n
	   do (format t "~a " (gethash (idx i) table)))
	(terpri)))))

(main)


Measured memory_bytes: 69784
#include <stdio.h>
#include <math.h>

int main(void){
    
    double q;
    
    while(scanf("%lf", &q)!= EOF && q != -1) {
        double x, a;
        x=q/2;
        
        while(1){
            if(fabs(x*x*x-q)<0.00001*q)
            break;
            x=x-((x*x*x-q)/(3*x*x));
            x = x;
        }
            
        printf("%.6f\n",x);
            
    }
        
    return 0;
    
}


Measured memory_bytes: 2556
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <functional>
#include <complex>

using namespace std;

const int INF = (1<<30) - 1;

int dw[] = {0, 0, 1, -1};
int dh[] = {1, -1, 0, 0};

int dfs(vector<string>& field, int h, int w){
    int H = field.size();
    int W = field[0].size();
    
    field[h][w] = 'a';
    int res = 1;
    
    for(int i=0; i<4; i++){
        int nh = h + dh[i];
        int nw = w + dw[i];
        if(nh<0 || H<=nh || nw<0 || W<=nw || field[nh][nw] != '.')
            continue;
        res += dfs(field, nh, nw);
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int W, H;
    while(cin>>W>>H, W|H){
        vector<string> field(H);
        for(int i=0; i<H; i++)
            cin >> field[i];
        
        for(int i=0; i<H; i++){
            for(int j=0; j<W; j++){
                if(field[i][j] == '@'){
                    cout << dfs(field, i, j) << endl;
                    break;
                }
            }
        }
    }
    
    return 0;
}

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

int main() {
    int k;
    cin >> k;
    int ans = (k / 2) * ((k + 1) / 2);
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
  int n;
  while (cin >> n) {
    int i, j, k, l, r = 0;
    for (i = 0; i < 10; i++)
      for (j = 0; j < 10; j++)
        for (k = 0; k < 10; k++)
          for (l = 0; l < 10; l++)
            if (i + j + k + l == n) r++;
    cout << r << endl;
  }
  return 0;
}

Measured memory_bytes: 0
// atcoder/panasonic2020/D/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; for (auto& i: v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { for (auto& i: v) is >> i; return is; }
template<typename T> ostream& operator << (ostream& os, set<T> s) { os << "#{"; for (auto& i: s) os << i << ","; os << "}"; return os; }
template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "{"; for (auto& i: m) os << i << ","; os << "}"; return os; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

using lli = long long int;
using ull = unsigned long long;
using point = complex<double>;
using str = string;
template<typename T> using vec = vector<T>;

int di[] = {0, 1, -1, 0, 1, -1, 1, -1};
int dj[] = {1, 0, 0, -1, 1, -1, -1, 1};
constexpr lli mod = 1e9 + 7;

char buff[11];
int n;
void bt(int m, char c)
{
  if (n == m) {
    puts(buff);
    return ;
  }

  for (char d = 'a'; d <= c; ++d) {
    buff[m] = d;
    bt(m + 1, c);
  }
  buff[m] = c + 1;
  bt(m + 1, c + 1);

  return ;
}

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  while (cin >> n) {
    bt(0, 'a' - 1);
  }

  return 0;
}


Measured memory_bytes: 1536
import java.util.*;
public class Main {

	public void doIt(){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		while(n-- > 0){
			String str1 = new StringBuilder(sc.next()).reverse().toString();
			String str2 = new StringBuilder(sc.next()).reverse().toString();
			int maxlen = Math.max(str1.length(), str2.length());
			if(maxlen >80){
				System.out.println("overflow");
				continue;
			}
			int [] ans = new int [maxlen+1];
			int len = str1.length();
			for(int i=0; i < len; i++){
				ans[i] = str1.charAt(i) - '0';
			}
			len = str2.length();
			for(int i=0; i < len; i++){
				ans[i] += str2.charAt(i) - '0';
			}
			len= ans.length - 1 ;
			for(int i=0; i < len; i++){
				if(ans[i] >= 10){
					ans[i+1]++;
					ans[i] = ans[i] - 10;
				}
			}

			if(ans.length == 81 && ans[80] != 0){
				System.out.println("overflow");
			}
			else{
				if(ans[len] == 1){
					System.out.print(1);
				}
				for(int i=ans.length-2; i >= 0; i--){
					System.out.print(ans[i]);
				}
				System.out.println("");
			}
		}
	}
	public static void main(String[] args) {
		Main obj = new Main();
		obj.doIt();
	}
}

Measured memory_bytes: 12000