akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;

namespace chrono = std::chrono;
using namespace std::literals;

[[gnu::constructor]]
void fast_iostream() {
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cerr.tie(nullptr);
}

template <class T>
T** alloc_matrix(int n, int m) {
    T* data = new T[n * m];
    T** mat = new T*[n];
    for (int i = 0; i < n; ++i) {
        mat[i] = data + i * m;
    }
    return mat;
}

template <class T>
void free_matrix(T** mat) {
    delete[] *mat;
    delete[] mat;
}

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

    long long** to_add = alloc_matrix<long long>(3 * k + 1, 3 * k + 1);
    long long** add = alloc_matrix<long long>(3 * k + 1, 3 * k + 1);
    while (n--) {
        int x; cin >> x;
        int y; cin >> y;
        char c; cin >> std::skipws >> c;
        if (c == 'B') {
            x += k;
        }
        int x1 = x + 1;
        int y1 = y + 1;
        int x2 = x + k + 1;
        int y2 = y + k + 1;
        
        int u = std::min(x1 / k, y1 / k);
        x1 -= u * k;
        y1 -= u * k;
        x2 -= u * k;
        y2 -= u * k;

        u = x1 / (2 * k);
        x1 -= u * 2 * k;
        x2 -= u * 2 * k;

        u = y1 / (2 * k);
        y1 -= u * 2 * k;
        y2 -= u * 2 * k;

        to_add[x1][y1] += 1;
        to_add[x1][y2] -= 1;
        to_add[x2][y1] -= 1;
        to_add[x2][y2] += 1;
    }

    std::vector<long long> vadd(3 * k, 0);
    for (int i = 0; i < 3 * k; ++i) {
        long long cur = 0;
        for (int j = 0; j < 3 * k; ++j) {
            vadd[j] += to_add[i][j];
            cur += vadd[j];
            add[i][j] = cur;
        }
    }
    for (int i = 0; i < 3 * k; ++i) {
        for (int j = 0; j < 3 * k; ++j) {
            if (i < k && j < 2 * k) continue;
            int x = i, y = j;
            while (x >= k) {
                x -= k;
                y += k;
            }
            while (y >= 2 * k) {
                y -= 2 * k;
            }
            add[x][y] += add[i][j];
            /* add[i][j] += add[x][y]; */
        }
    }
    long long ans = 0;
    for (int i = 0; i < k; ++i) {
        for (int j = 0; j < 2 * k; ++j) {
            ans = std::max(ans, add[i][j]);
        }
    }
    cout << ans << endl;
    free_matrix(add);
    free_matrix(to_add);
}


Measured memory_bytes: 140672
import java.util.Scanner;
class Main {
	Scanner scan = new Scanner(System.in);
	public static void main(String args[]){
		Main app = new Main();
		while(app.scan.hasNext()){
			int n = Integer.parseInt(app.scan.nextLine());
			int[][] entrant = new int[n][2];
			app.input(n, entrant);
			int index = app.max(n,entrant);
			System.out.println(entrant[index][0]+" "+entrant[index][1]);
		}
	}
	
	public void input(int n,int[][] e){
		String[] splitLine;
		for(int i=0;i<n;i++){
			splitLine = scan.nextLine().split(" ");
			e[i][0] = Integer.parseInt(splitLine[0]);
			e[i][1] = Integer.parseInt(splitLine[1]);
		}
	}
	
	public int max(int n,int[][] e){
		int max=0;
		int index = 0;
		
		for(int i=0;i<n;i++){
			if(e[i][1] > max){
				max = e[i][1];
				index = i;
			}
		}
		
		for(int i=0;i<n;i++){
			if(e[i][1] == max){
				if(e[i][0] < e[index][0]){
					index = i;
				}
			}
		}
		
		return index;
	}
}

Measured memory_bytes: 17332
x = int(input())

p5 = []
m = 1000
for i in range(-m, m+1):
    p5.append(i**5)

for ci in range(2*m+1):
    if p5[ci] - x in p5:
        a = [ci-m, p5.index(p5[ci] - x)-m]
        break
a = [str(i) for i in a]
print(' '.join(a))

Measured memory_bytes: 9256
T = int(input())

for t in range(T):
    N, A, B, C, D = map(int, input().split())
    memo = {}

    def dist(n):
        if n == 0:
            return 0
        if n == 1:
            return D
        if n in memo:
            return memo[n]
        
        ret = min(
            D * n,
            D * abs(n - n//5*5) + C + dist(n//5),
            D * abs(n - (n+4)//5*5) + C + dist((n+4)//5),
            D * abs(n - n//3*3) + B + dist(n//3),
            D * abs(n - (n+2)//3*3) + B + dist((n+2)//3),
            D * abs(n - n//2*2) + A + dist(n//2),
            D * abs(n - (n+1)//2*2) + A + dist((n+1)//2)
        )

        memo[n] = ret
        return ret
    print(dist(N))


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

#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

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

    if (n == 3) {
        cout << "2 3 25" << endl;
    } else {
        const auto* delim = "";
        auto m = n / 8;
        for (auto i : irange(0L, m)) {
            cout << delim << 12 * i + 2;
            delim = " ";
            cout << delim << 12 * i + 3;
            cout << delim << 12 * i + 4;
            cout << delim << 12 * i + 6;
            cout << delim << 12 * i + 8;
            cout << delim << 12 * i + 9;
            cout << delim << 12 * i + 10;
            cout << delim << 12 * i + 12;
        }
        switch (n % 8) {
            case 0:
                cout << endl;
                break;
            case 1:
                cout << delim << 12 * m + 6 << endl;
                break;
            case 2:
                cout << delim << 12 * m + 2 << " " << 12 * m + 4 << endl;
                break;
            case 3:
                cout << delim << 12 * m + 2 << " " << 12 * m + 4 << " "
                     << 12 * m + 6 << endl;
                break;
            case 4:
                cout << delim << 12 * m + 2 << " " << 12 * m + 3 << " "
                     << 12 * m + 4 << " " << 12 * m + 9 << endl;
                break;
            case 5:
                cout << delim << 12 * m + 2 << " " << 12 * m + 3 << " "
                     << 12 * m + 4 << " " << 12 * m + 6 << " " << 12 * m + 9
                     << endl;
                break;
            case 6:
                cout << delim << 12 * m + 2 << " " << 12 * m + 3 << " "
                     << 12 * m + 4 << " " << 12 * m + 8 << " " << 12 * m + 9
                     << " " << 12 * m + 10 << endl;
                break;
            case 7:
                cout << delim << 12 * m + 2 << " " << 12 * m + 3 << " "
                     << 12 * m + 4 << " " << 12 * m + 8 << " " << 12 * m + 9
                     << " " << 12 * m + 10 << " " << 12 * m + 12 << endl;
                break;
        }
    }
}

Measured memory_bytes: 384
//
//  ROIGold.cpp
//  Main calisma
//
//  Created by Rakhman on 05/02/2019.
//  Copyright © 2019 Rakhman. All rights reserved.
//

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>

#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define FOR(i, start, finish, k) for(int i = start; i <= finish; i += k)

const int MXN = 2e5 + 200;
const long long MNN = 2e3 + 200;
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
const int OO = 1e9 + 500;

typedef long long llong;
typedef unsigned long long ullong;

using namespace std;

llong n, m, k, f[MXN];

llong binpow(llong a, llong b){
    if(b == 0) return 1;
    if(b % 2 == 1) return binpow(a, b - 1) * a % MOD;
    else{
        llong x = binpow(a, b / 2);
        return x * x % MOD;
    }
}

llong C(llong n, llong k){
    llong up = f[n];
    llong down = (f[k] * f[n - k]) % MOD;
    return (up * binpow(down, MOD - 2)) % MOD;
}

llong d() {
    llong num = m - 1;
    llong res_x = 0, res_y = 0;
    res_x = (num + 1) * (2 * num + 4) * num / 12 % MOD;
    res_x = res_x * n * n % MOD;
    num = n - 1;
    res_y = (num + 1) * (2 * num + 4) * num / 12 % MOD;
    res_y = res_y * m * m % MOD;
    return (res_x + res_y) % MOD;
}

int main () {
    ios;
    cin >> n >> m >> k;
    f[0] = 1;
    for(int i = 1; i <= n * m; i++){
        f[i] = (f[i - 1] * i) % MOD;
    }
    cout << (C(n * m - 2, k - 2) * d()) % MOD;
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define inf 1000000000 //1E+9
#define mod 1000000007
using namespace std;
int main(){
	int n,k;cin>>n>>k;
	string s;cin>>s;

	int buf;
	int zero=0;
	vector<int> v;
	for(int i=0;i<n;i++){
		if(s[i]=='1'){
			buf=1;
			for(int j=i+1;j<n;j++){
				if(s[j]=='1')buf++;
				else break;
			}
			i+=buf-1;
			v.push_back(buf);
		}
		if(s[i]=='0'){
			buf=1;
			for(int j=i+1;j<n;j++){
				if(s[j]=='0')buf++;
				else break;
			}
			i+=buf-1;
			v.push_back(buf);
			zero++;
		}
	}
	if(v.size()==1 || zero<=k){cout<<s.size()<<endl;return 0;}

	int flag;
	if(s[0]=='0')flag=1;else flag=0;
	vector<int> r(v.size(),0);
	r[0]=v[0];for(int i=1;i<v.size();i++)r[i]=r[i-1]+v[i];
	
	int ans=0;
	if(flag==1){
		ans=max(ans,r[2*k-1]);
		for(int i=1;2*k-1+2*i<v.size();i++)
			ans=max(ans,r[2*k-1+2*i]-r[2*i-2]);
	}
	if(flag==0){
		ans=max(ans,r[2*k]);
		for(int i=1;2*k+2*i<v.size();i++)
			ans=max(ans,r[2*k+2*i]-r[2*i-1]);
	}

	reverse(v.begin(), v.end());
	r[0]=v[0];for(int i=1;i<v.size();i++)r[i]=r[i-1]+v[i];
	if(s[s.size()-1]=='0')flag=1;else flag=0;
	if(flag==1){
		ans=max(ans,r[2*k-1]);
		for(int i=1;2*k-1+2*i<v.size();i++)
			ans=max(ans,r[2*k-1+2*i]-r[2*i-2]);
	}
	if(flag==0){
		ans=max(ans,r[2*k]);
		for(int i=1;2*k+2*i<v.size();i++)
			ans=max(ans,r[2*k+2*i]-r[2*i-1]);
	}

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

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

namespace AtCoder.Abc
{
    class QuestionB
    {
        /// <summary>
        /// https://atcoder.jp/contests/abc168/tasks/abc168_b
        /// </summary>
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 整数の入力
            int num_K = int.Parse(Console.ReadLine());

            // 文字列の入力
            string str_S = Console.ReadLine();
            
            int num_Length = str_S.Length;

            if (num_Length <= num_K)
            {
                Console.WriteLine(str_S);
            }
            else if(num_Length > num_K)
            {
                string str_SS = str_S.Substring(0, num_K) + "...";
                Console.WriteLine(str_SS);
                
            }
            
            Console.Out.Flush();

        }
    }
}


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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 4e3 + 5;

int val[MAXN], col[MAXN];

int ind[2][MAXN];

char s[10];

int cnt[2][MAXN][MAXN];
int cnt0[2][MAXN];

int dp[MAXN][MAXN];

void solve(){
	int n;
	scanf("%d", &n);
	REPN(i, 1, 2 * n){
		scanf("%s%d", &s[0], &val[i]);
		val[i];
		col[i] = (s[0] == 'W');
		//ind[col[i]][val[i]] = i;
	}
	
	REPN(i, 1, 2 * n){
		int v = val[i], c = col[i];
		REP(j, 1, i){
			if (col[j] == c){
				if (val[j] > v){
					cnt0[c][v]++;
				}
			} else {
				cnt[c][v][val[j] - 1] = 1;
			}
		}
	}
	
	REP(c, 0, 2){
		REPN(i, 1, n){
			for(int j = n - 1; j >= 0; j--){
				cnt[c][i][j] += cnt[c][i][j + 1];
			}
		}
		REPN(i, 1, n){
			REPN(j, 0, n){
				cnt[c][i][j] += cnt0[c][i];
			}
		}
	}
	
	REPN(i, 0, n){
		REPN(j, 0, n){
			dp[i][j] = INF;
		}
	}
	dp[0][0] = 0;
	REPN(i, 0, n){
		REPN(j, 0, n){
			if (i < n){
				dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + cnt[0][i + 1][j]);
			}
			if (j < n){
				dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + cnt[1][j + 1][i]);
			}
		}
	}
	int ans = dp[n][n];
	printf("%d\n", ans);
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 98048
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const ll inf=1e9+7;
const ll INF=1e18;

map<int,int> pf;

void prime_factor(int n){
    for(int i=2;i*i<=n;i++){
        while(n%i==0){
            pf[i]++;
            n/=i;
        }
    }
    if(n!=1)pf[n]++;
    return;
}

int main(){
    int n;cin>>n;
    rep2(i,2,n+1)prime_factor(i);
    ll a=0;ll b=0;ll c=0;ll d=0;ll e=0;
    rep2(i,2,n+1){
        if(pf[i]>=74)a++;
        if(pf[i]>=24)b++;
        if(pf[i]>=14)c++;
        if(pf[i]>=4)d++;
        if(pf[i]>=2)e++;
    }
    ll ans=0;
    ans+=a+(b*e-b)+(c*d-c)+(e*d*(d-1)/2-d*(d-1));
    cout<<ans<<endl;
    /*cout<<a<<endl;
    cout<<b<<endl;
    cout<<c<<endl;
    cout<<d<<endl;
    cout<<e<<endl;*/
}

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


using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF 1999999999
#define MINF -1999999999
#define INF64 1999999999999999999
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007


ll h, w, a = 0;
string s[100];
int main(){
	cin >> h >> w;
	REP(i, h) cin >> s[i];
	REP(i, h) {
		REP(j, w) {
			if (s[i][j] == '#') a++;
		}
	}
	cout << (h + w - 1 == a ? "Possible" : "Impossible") << endl;
}



Measured memory_bytes: 256
//Let Our Voices Echo
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAX=2e5+9;
int n,a[MAX];
void no()
{
	cout<<"No";
	exit(0);
}
void yes()
{
	cout<<"Yes";
	exit(0);
}
int main()
{
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for (int i=0;i<n;i++) cin>>a[i];
	int mi=*min_element(a,a+n),mx=*max_element(a,a+n);
	if (mx-mi>1) no();
	bool flg=false;
	if (mi!=mx)
	{
		flg=true;
		int t=0;
		for (int i=0;i<n;i++) if (a[i]==mi) t++;
		mx-=t;
		n=n-t;
	}
	if (mx<=0) no();
	if (mx*2>n && flg) no();
	if (mx==n-1) yes();
	if (mx<=n/2) yes();
	no();
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include <set>

#define DIV 1000000007
using namespace std;
using ll = long long;

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

    ll ans = N % K;
    ans = min(ans, abs((N % K) - K));

    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<unordered_map>
#include<string>
#define ll long long
using namespace std;
const ll INF = 1LL << 60;
const int inf = 1 << 30;
const int N= 1e5 + 10;
inline void fastio()
{ 
     ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

ll poww(int a)
{
    int  base = a, b = 5;
    ll result = 1;
    while(b!=0)
    {
        if((b&1) !=0)
            result *= base;
        base *= base;
        b >>= 1;
    }
    return result;
}
int main()
{
    int n, ans1=0, ans2=0;
    cin >> n;
    bool flag = true;
    for (int i = 0; i <= 4000&&flag;i++)
        for (int j = 0; j <= 4000;j++)
        {
            if(poww(j)+poww(i)==n)
                {
                    ans1 = j;
                    ans2 = -i;
                    flag = false;
                    break;
                }
            if(poww(j)-poww(i)==n)
                {
                    ans1 = j;
                    ans2 = i;
                    flag = false;
                    break;
                }
        }
    cout << ans1<<" "<<ans2;
    return 0;
}



Measured memory_bytes: 3620
import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter

# import math

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    x, y, z = list(map(int, readline().split()))
    x, y, z = z, x, y

    print(x, y, z)


if __name__ == '__main__':
    main()


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

using namespace std;

typedef long long ll;

const int N = 100100;

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int pt = 0, px = 0, py = 0;
    while (n--) {
        int t, x, y;
        cin >> t >> x >> y;
        int dist = abs(x - px) + abs(y - py);
        if (dist > t - pt || dist % 2 != (t - pt) % 2) {
            cout << "No";
            return 0;
        }
        px = x;
        py = y;
        pt = t;
    }
    cout << "Yes";
    return 0;
}

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

int main() {
  
  int n;
  string s;
  cin >> n >> s;
  
  int ans = 0;
  REP(i,n) {
    if (s[i] == 'A' && s[i+1] =='B' && s[i+2] == 'C') ans++;
  }
  
  cout << ans << endl;
    
}

Measured memory_bytes: 256
#pragma warning(disable:4996)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <float.h>

#pragma region 定義
typedef long long  ll;
typedef unsigned long long  ull;


#define _itoa(A,N) sprintf(A, "%d", N);

int i_dsort(const void* a, const void* b);
int i_asort(const void* a, const void* b);

int  _gcd(int a, int b);
int  _swp(int* a, int* b);
int _cknum(char* a, int n);
int _atoi(char* s, int len);

int s_asort(const void* a, const void* b);
int s_dsort(const void* a, const void* b);

//昇順
int s_asort(const void* a, const void* b) {
	return(strcmp((char*)a, (char*)b));
}
int s_dsort(const void* a, const void* b) {
	return(strcmp((char*)b, (char*)a));
}

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

int _gcd(int a, int b) {
	int r, tmp;
	if (a < b) { tmp = a; a = b; b = tmp; }
	r = a % b;
	while (r) {
		if (!r) break;
		a = b; b = r;
		r = a % b;
	}
	return(b);
}
// puts("Yes\n") puts("No\n")
// scanf("%d.%d") 浮動小数点入力を整数２つで得る


//#define pai  3.1415926535 
//#define  _USE_MATH_DEFINES でM_PIが使える

#define deg_rad(X)  (X*(M_PI/180))


int _swp(int* a, int* b)
{
	int tmp;
	tmp = *b; *b = *a; *a = tmp;
	return 0;
}
#define _abs(x) ((x)>0?(x):-(x))
#define _min(x,y) ((x)<(y)?(x):(y))
#define _max(x,y) ((x)<(y)?(y):(x))

int _cknum(char* a, int n) {
	int i;
	char t = '0';

	for (i = 0; i < n; i++) {
		if (a[i] < '0' || a[i]>'9') return 1;
	}
	return 0;
}


int _atoi(char* s, int len) {
	char tmp[20];
	memcpy(tmp, s, len);
	tmp[len] = 0x00;
	return (atoi(tmp));
}

//素因数分解　pf素数が入る　pc 素数の数
ll _pfact(ll a);
static ll pf[100000000];
static ll pc;

ll _pfact(ll a) {
	long i, r;
	if (a % 2 == 0) {
		pf[pc] = 2; pc++;
		return(_pfact(a / 2));
	}
	r = sqrt(a);
	for (i = 3; i <= r; i += 2) {
		if (a % i == 0) {
			pf[pc] = i; pc++;
			return(_pfact(a / i));
		}
	}
	if (a != 1) {
		pf[pc] = a; pc++;
	}
	return 0;

}


#pragma endregion

//ABC 163 -B
//#define MAX 11
#define MAX 101
static int f[MAX+1];
int main(void) {
	int i, x, n, p[MAX];

	scanf("%d %d", &x, &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &p[i]);
		f[p[i]] = 1;
	}

	if (!f[x]) {printf("%d", x); return 0;}

	int l = x - 1; 
	int r = x + 1;
	int ans;
	while (l >= 0 || r <= 101) {
		if (!f[l]) { ans = l; break; }
		if (!f[r]) { ans = r; break; }
		l--; r++;
	}
	printf("%d", ans);
	return 0;
}


Measured memory_bytes: 2152
#include <iostream>

using namespace std;

int main()
{
 int a,b,c;
 cin>>a>>b>>c;
 int z=0;
 int y=0;
 z=b-a;
y=c-b;

  if(z==y)

   {
     cout<<"YES";
   }
 else

 {
     cout<<"NO";
 }



    return 0;
}

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

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define BIT(X,i) ((X>>i)&1)
#define REP(i,a,b) for(int i = (a); i < (b); ++i)
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(rall(a))
#define ina(x,n) rep(x_i,n) cin>>x[x_i]
#define outa(x,n) rep(x_i,n) cerr<<x[x_i]<<" \n"[x_i==n-1]

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vll;

const int mod = 1e9+7;
const int inf = (1<<28);
const ll infl = (1LL<<60);

int a[3][3], e[3][3];

int main() {
  rep(i,3) rep(j,3) {
    cin >> a[i][j];
  }
  int n; cin >> n;
  rep(i,n) {
    int x; cin >> x;
    rep(i,3) rep(j,3) {
      if (x == a[i][j]) e[i][j] = 1;
    }
  }

  bool flag = false;
  rep(i,3) {
    if (e[i][0]+e[i][1]+e[i][2] == 3) flag = true;
    if (e[0][i]+e[1][i]+e[2][i] == 3) flag = true;
  }
  if (e[0][0]+e[1][1]+e[2][2] == 3) flag = true;
  if (e[0][2]+e[1][1]+e[2][0] == 3) flag = true;
  cout << (flag?"Yes":"No") << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>

using namespace std;

int f(int n)
{
    if(n % 2 == 1)
        return 3 * n + 1;
    else
        return n / 2;
}

int main()
{
    int c; cin >> c;
    vector<int> a;
    a.push_back(c);
    int counter = 1;
    while(true)
    {
        int temp = f(a[counter - 1]);
        for(auto item : a)
        {
            if(item == temp)
            {
                cout << counter + 1 << endl;
                return 0;
            }
        }
        counter++;
        a.push_back(temp);
    }
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class MainClass
{
    static void Main()
    {
        int N = int.Parse(ReadLine());
        string S = ReadLine();
        if (N % 2 == 0)
        {
            if (S.Substring(0, N / 2) == S.Substring(N / 2))
            {
                WriteLine("Yes");return;
            }
        }
        WriteLine("No");
    }
}


Measured memory_bytes: 27468
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
using namespace std;

#define rep(i,a,n) for(int i=a; i<n; i++)
#define repq(i,a,n) for(int i=a; i<=n; i++)
#define repr(i,a,n) for(int i=a; i>=n; i--)
#define pb(a) push_back(a)
#define fr first
#define sc second
#define INF 2000000000
#define int long long int

#define X real()
#define Y imag()
#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )
#define LE(n, m) ((n) < (m) + EPS)
#define LEQ(n, m) ((n) <= (m) + EPS)
#define GE(n, m) ((n) + EPS > (m))
#define GEQ(n, m) ((n) + EPS >= (m))

typedef vector<int> VI;
typedef vector<VI> MAT;
typedef pair<int, int> pii;
typedef long long ll;

typedef complex<double> P;
typedef pair<P, P> L;
typedef pair<P, double> C;

int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int const MOD = 1000000007;

namespace std {
    bool operator<(const P& a, const P& b) {
        return a.X != b.X ? a.X < b.X : a.Y < b.Y;
    }
}

signed main() {
    int a, b, h; cin >> a >> b >> h;
    cout << (a + b) * h / 2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// ==================================================
using i64 = int64_t; using u64 = uint64_t;
#define rep(i,a,b) for(i64 i=(int64_t)(a);i<(int64_t)(b);i++)
#define repn(i,n) rep(i,0,n)
#define din(t, ...) t __VA_ARGS__;_din(__VA_ARGS__)
#define v(t,n) vector<t> n
void _din() {} void dout() { cout << endl; }
template <typename T, typename ... Args> inline void _din(T& head, Args& ... rest) { cin >> head; _din(rest...); }
template <typename T, typename ... Args> inline void dout(T head, Args ... rest) { cout << head; if (sizeof...(rest)) cout << ' '; dout(rest...); }
template <typename T>inline void vsortg(vector<T>& v) { sort(v.begin(), v.end(), greater<T>()); }
template <typename T>inline void vsortl(vector<T>& v) { sort(v.begin(), v.end(), less<T>()); }
template <typename T> inline T nmax(T f1, T f2) { return max(f1, f2); }
template <typename T, typename ... Args> inline T nmax(T first, Args ... rest) { return nmax(first, nmax(rest...)); }
template <typename T> inline T nmin(T f1, T f2) { return min(f1, f2); }
template <typename T, typename ... Args> inline T nmin(T first, Args ... rest) { return nmin(first, nmin(rest...)); }
// ==================================================
i64 d[] = { 0,1,2,3,6,7,14,15,30,31,62,63,126,127,254,255,510,511,1022,1023,2046,2047,4094,4095,8190,8191,16382,16383,32766,32767,65534,65535,131070,131071,262142,262143,524286,524287,1048574,1048575,2097150,2097151,4194302,4194303,8388606,8388607,16777214,16777215,33554430,33554431,67108862,67108863,134217726,134217727,268435454,268435455,536870910,536870911,1073741822,1073741823,2147483646,2147483647,4294967294,4294967295,8589934590,8589934591,17179869182,17179869183,34359738366,34359738367,68719476734,68719476735,137438953470,137438953471,274877906942,274877906943,549755813886,549755813887,1099511627774,1099511627775,2199023255550,2199023255551,4398046511102,4398046511103,8796093022206,8796093022207,17592186044414,17592186044415,35184372088830,35184372088831,70368744177662,70368744177663,140737488355326,140737488355327,281474976710654,281474976710655,562949953421310,562949953421311,1125899906842622,1125899906842623 };
bool eat(i64 l, i64& x, i64& t)
{
	if (l == 0)
	{
		x--;
		t++;
		return x == 0;
	}
	l -= 1;
	x--;//bread
	if (x == 0) return true;
	i64 all = d[2 * l] + d[2 * l + 1];
	if (x >= all)
	{
		t += d[2 * l + 1];
		x -= all;
	}
	else if (eat(l, x, t))return true;
	if (x == 0) return true;
	x--; t++;
	if (x == 0) return true;
	if (x >= all)
	{
		t += d[2 * l + 1];
		x -= all;
	}
	else if (eat(l, x, t))return true;
	if (x == 0) return true;
	x--;
	return x == 0;
}
int main()
{
	din(i64, n, x);
	i64 t = 0;
	eat(n, x, t);
	dout(t);
}

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

using namespace std;

#define INF 1000007
#define MOD 1000000007
#define maxn 100
#define int long long int
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) FOR(i, 0, n)

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int lcm(int a, int b) { return a / gcd(a, b) * b; }

int mpow(int N, int P, int M)  //繰り返し自乗法
{
    if (P == 0)
        return 1;
    if (P % 2 == 0) {
        int t = mpow(N, P / 2, M);
        return t * t % M;
    }
    return N * mpow(N, P - 1, M) % M;
}

vector<bool> prime(maxn + 1, true); //素数テーブル
void prime_table(void) {
    prime[0] = false;
    prime[1] = false;
    for (int i = 2; i * i <= maxn; i++) {
        if (!prime[i]) {
            continue;
        }
        for (int j = i + i; j <= maxn; j += j + i) {
            prime[j] = false;
        }
    }
}

signed main() {
    string S;
    cin >> S;
    int ans = 0;
    for (int i = 0; i < S.length() / 2; i++) {
        if (S[i] != S[S.length() - 1 - i]) {
            ans++;
        }
    }
    cout << ans << endl;
}


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

MOD = 998244353
N = 3 * 10**5

fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

ans = 0
for i in range(k+1):
    ans += m * pow(m-1, n-i-1, MOD) * comb(n-1, i)
    ans %= MOD

print(ans)

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

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

ll lcm(ll a, ll b)
{
   return a * b / gcd(a, b);
}
ll count(ll x,ll a,ll b){ //x以下でaでもbでも割れない
    ll p = x / a;
    ll q = x / b;
    ll r = x / lcm(a,b);
    return x - p - q + r;

}

int main(){
    ll a,b,c,d,ans=0;
    cin >> a >> b >> c >> d;
    cout << count(b,c,d) - count(a-1,c,d) << endl;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    /** 入力される数値の数 */
    private static final int NUMBER_OF_INPUT = 2;

    /**
     * 空白区切りの2つの数字を受け取り、その2つの数字の合計値の桁数を出力する。
     *
     * @param args
     */
    public static void main(String[] args) throws IOException {

        // 入力がある限り処理を行う
        String line = null;
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        while((line = reader.readLine()) != null) {

            // 入力文字列を数値配列に変換する
            int[] input = convertStringToIntArray(line);

            // 合計値の桁数を取得する
            int sum = calculateSum(input);
            int numberOfDigit = getNumberOfDigit(sum);

            // 結果を出力する
            System.out.println(numberOfDigit);
        }

        if (reader != null) {
            reader.close();
        }
     }

    /**
     * 空白区切りの数値を取得し、整数の配列として返却する。
     *
     * @param line 空白区切りの数値文字列
     * @return 整数の配列
     */
    protected static int[] convertStringToIntArray(String line){
        int [] result = new int[NUMBER_OF_INPUT];

        String[] splittedLine = line.split(" ");
        for( int i = 0; i < splittedLine.length; i++){
            result[i] = Integer.parseInt(splittedLine[i]);
        }

        return result;
    }

    /**
     * 引数で渡された整数配列の合計値を返す。
     *
     * @param input 整数の配列
     * @return 整数の配列の合計値
     */
    protected static int calculateSum(int[] input) {
        int sum = 0;
        for (int i = 0; i < input.length; i++) {
            sum += input[i];
        }
        return sum;
    }

    /**
     * 指定された数値の桁数を返す。
     *
     * @param target 数値
     * @return 数値の桁数
     */
    protected static int getNumberOfDigit(int target) {
        // 文字列に変換して、文字数を返す
        return String.valueOf(target).length();
    }

}

Measured memory_bytes: 17008
#include <iostream>

using namespace std;

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

    int ans = 0;
    for (int x = 0; x <= k; ++x) {
        for (int y = 0; y <= k; ++y) {
            int z = s - (x + y);
            if (z >= 0 && z <= k) ++ans;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import heapq
N, M = map(int, input().split())
E = [[] for i in range(N)]
revE = [[] for i in range(N)]
for i in range(M):
  a, b, c = map(int, input().split())
  E[a - 1].append([b - 1, -c])
  revE[b - 1].append(a - 1)
revG = [False] * N
revG[-1] = True
Q = []
heapq.heappush(Q, N - 1)
while Q:
  s = heapq.heappop(Q)
  for adj in revE[s]:
    if not revG[adj]:
      revG[adj] = True
      heapq.heappush(Q, adj)
D = [N * 10 ** 9 + 1] * N
D[0] = 0
def bf(D):
  for i in range(N):
    _D = [d for d in D]
    for s in range(N):
      for adj in E[s]:
        _D[adj[0]] = min(D[s] + adj[1], _D[adj[0]])
    D = _D
  return D
D = bf(D)
D1 = [d for d in D]
D = bf(D)
for i in range(N):
  if revG[i] and D1[i] != D[i]:
    print('inf')
    break
else:
  print(-D[-1])

Measured memory_bytes: 3708
s =input()
odd=["R","U","D"]
even=["L","U","D"]
cnt=0
for i in range(len(s)):
    if i%2==0:
        if s[i] in odd:
            cnt+=1
    else:
        if s[i] in even:
            cnt+=1
if cnt==len(s):
    print("Yes")
else:
    print("No")







Measured memory_bytes: 3060
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	var n, m, d float64
	Scan(&n, &m, &d)
	var p float64
	if d == 0 {
		p = 1 / n
	} else {
		p = 2 * (n - d) / (n * n)
	}
	fmt.Printf("%f\n", p*(m-1))
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


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

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-12;
static const double PI = acos(-1.0);

template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;

#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(a) (a).begin(), (a).end()
#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define dbg(x) true
#endif

void solve(long long N, long long M, std::vector<long long> A, std::vector<long long> B) {
  atcoder::dsu dsu(N);
  REP(i, M) {
    dsu.merge(A[i] - 1, B[i] - 1);
  }
  cout << dsu.groups().size() - 1 << endl;
}

int main() {
  long long N;
  scanf("%lld", &N);
  long long M;
  scanf("%lld", &M);
  std::vector<long long> A(M);
  std::vector<long long> B(M);
  for (int i = 0; i < M; i++) {
    scanf("%lld", &A[i]);
    scanf("%lld", &B[i]);
  }
  solve(N, M, std::move(A), std::move(B));
  return 0;
}


Measured memory_bytes: 9112
#!/usr/bin/env python
# -*- coding: utf-8 -*-

for _ in range(3):
    h, m, s, _h, _m, _s = map(int, input().split())

    start = h*3600 + m*60 + s
    end = _h*3600 + _m*60 + _s

    time = end - start

    hours = time//3600
    minutes = time//60%60
    seconds = time%60

    print(hours, minutes, seconds)

Measured memory_bytes: 6724
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<deque>
#include<tuple>
#include<queue>
#include<map>
#include<cstdint>
#include<unordered_map>
//#include<boost/multiprecision/cpp_int.hpp>


#define rep(i, n) for(int i = 0; i < ( int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define F first
#define S second


//namespace mp = boost::multiprecision;

//using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

int main() {
	int N, A, B, C;
	cin >> N >> A >> B >> C;
	vector<int>len(N);
	rep(i, N) {
		scanf("%d", &len[i]);
	}
	int ans = 1e6;
	int i = 0;
	while (i < pow(4, N)) {
		deque<int>base4;
		vector<int>abc(3);
		int tmpi = i;
		while (tmpi > 0) {
			base4.push_front(tmpi % 4);
			tmpi /= 4;
		}
		while (base4.size() < N) {
			base4.push_front(0);
		}
		int count = 0;
		rep(j, N) {
			rep(k, 3) {
				if (base4[j] == k+1) {
					if (abc[k] != 0) {
						count++;
					}
					abc[k]+=len[j];
				}
			}
		}
		bool flag = true;
		rep(k, 3) {
			if (!abc[k]) {
				flag = false;
			}
		}
		if (flag) {
			int a = abs(A - abc[0]);
			int b = abs(B - abc[1]);
			int c = abs(C - abc[2]);
			ans = min(ans, a + b + c + count * 10);
		}
		i++;
	}
	cout << ans << endl;


}


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

const string YES = "Yes";
const string NO = "No";

void solve(long long x, long long y) {
	string ans;
	if(x==1 or x==3 or x==5 or x==7 or x==8 or x==10 or x==12 )x=13;
    else if (x==2)x=15;
    else x=14;
    if(y==1 or y==3 or y==5 or y==7 or y==8 or y==10 or y==12 )y=13;
    else if (y==2)y=15;
    else y=14;
    (x==y)?ans=YES:ans=NO;
    cout<<ans<<endl;
}

// 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)
int main() {
  long long x;
  scanf("%lld", &x);
  long long y;
  scanf("%lld", &y);
  solve(x, y);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <valarray>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <bitset>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <complex>
#include <string>
#include <sstream>

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cmath>

using namespace std;

#define all(c) c.begin(),c.end()
#define repeat(i,n) for(int i=0;i<static_cast<int>(n);i++)
#define debug(x) #x << "=" << (x)
#define dump(x) cerr << debug(x) << " (L:" << __LINE__ << ")"<< endl

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<long> vl;
typedef vector<vector<long> > vvl;
typedef vector<string> vs;

template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec){
    os << "[";
    for(int i = 0; i < vec.size(); i++){
        os << vec[i] << ",";
    }
    os << "]";
    return os;
}

template<typename T>
T input(){
    T t;
    cin >> t;
    return t;
}

template<typename T>
vector<T> input(const int N){
    vector<T> v(N);
    repeat(i,N) cin >> v[i];
    return v;
}

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

long long lcm(long long a, long long b){
    return (a / gcd(a, b)) * b;
}

long long mul(const long long& a, const long long& b, const long long& mod) {
    return ((a % mod) * (b % mod)) % mod;
}

long long power(const long long& x, const long long& y, const long long& mod) {
    if (y == 0) {
        return 1;
    } else if (y == 1) {
        return x % mod;
    } else {
        long long value = power(x, y / 2, mod);
        if (y % 2 == 0) {
            return mul(value, value, mod);
        } else {
            return mul(value, value, mod) * x % mod;
        }
    }
}

long long div(const long long& a, const long long& b, const long long& mod) {
    return mul(a, power(b, mod - 2, mod), mod);
}

map<long long, long long> factorials;
long long factorial(const long long& n, const long long& mod) {
    if (n == 0 || n == 1) {
        return 1;
    }
    if (factorials[n] != 0) {
        return factorials[n];
    }
    factorials[n] = n * factorial(n - 1, mod) % mod;
    return factorials[n] % mod;
}

long long combination(const long long& n, const long long& x, const long long& mod) {
    long long numerator = 1;
    long long denominator = 1;
    repeat(i, x) {
        numerator *= (n - i) % mod;
        numerator %= mod;
        denominator *= (i + 1) % mod;
        denominator %= mod;
    }
    return div(numerator, denominator, mod);
}

int main(){
    int dogs, monkeys;
    cin >> dogs >> monkeys;
    const long long mod = 1000000000 + 7;
    long long patterns = 0;
    if (dogs == monkeys) {
        patterns = mul(mul(factorial(dogs, mod), factorial(monkeys, mod), mod), 2, mod);
    } else if (abs(dogs - monkeys) == 1) {
        patterns = mul(factorial(dogs, mod), factorial(monkeys, mod), mod);
    } else {
        patterns = 0;
    }

    cout << patterns << endl;
    return 0;
}


Measured memory_bytes: 14336
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
using namespace std;
#define ll long long
#define ull unsigned long long
int H,W;
char grid[1001][1001]{};
ull mem[2000][2000]{};
const ll MOD = 1000000007;
ull cntWays(int i , int j)
{
    if(i==H-1 && j==W-1)
        return 1;

    ull &ret = mem[i][j] ;
    if(ret!=-1)
        return ret;
    ret = 0  ;
    if(i+1<H )
    {
        if(grid[i+1][j]=='.')
        ret = ret+cntWays(i+1 , j);
    }
    if(j+1<W)
    {
        if(grid[i][j+1]=='.')
        ret = ret+cntWays(i , j+1);
    }
    return (ret%MOD+MOD)%MOD;
}
int main()
{
    cin>>H>>W;
    memset(mem , -1 , sizeof(mem[0][0])*2000*2000);
    for(int i = 0 ; i<H ; i++)
    {
    for(int j = 0 ; j<W ; j++)cin>>grid[i][j];
    }


    ull ans = cntWays(0,0);
    cout<<(ans%MOD+MOD)%MOD<<endl;
    return 0;
}


Measured memory_bytes: 32640
import java.awt.geom.*;
import java.util.*;
import static java.lang.Math.*;
public class Main{
	final Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		new Main().init();
	}
	void init(){
		new AOJ1183();
	}
	class AOJ1183{
		AOJ1183(){
			while(sc.hasNext()){
				int n = sc.nextInt();
				if(n==0)	break;
				solve(n);
			}
		}
		final double INF = Double.MAX_VALUE/4;
		C[] c;
		Point2D.Double[][] p;
		Point2D.Double[] p2;
		void solve(int n){
			c=new C[n];
			for(int i=0; i<n; ++i)	c[i]=new C(sc.nextInt(),sc.nextInt(),sc.nextInt());
			p = new Point2D.Double[n][2];	// 交点の座標
			for(int i=0; i<n-1; ++i)	p[i]=intersectR(c[i], c[i+1]);
			p2=new Point2D.Double[2*n];
			p2[0]=(java.awt.geom.Point2D.Double) c[0].p;
			p2[2*n-1]=(java.awt.geom.Point2D.Double) c[n-1].p;
			for(int i=0; i<n-1; ++i){
				p2[i*2+1]=p[i][0];
				p2[i*2+2]=p[i][1];
			}
//			System.out.println(Arrays.toString(p2));
			
			double[] dp=new double[2*n];
			for(int i=0; i<2*n; ++i)	dp[i]=INF;
			dp[0]=0;
			for(int i=0; i<2*n; ++i){
				for(int j=i+1; j<2*n; ++j){
					if(!f1(i,j))	continue;
					dp[j]=min(dp[j], dp[i]+p2[i].distance(p2[j]));
//					System.out.println(i+" "+j+" "+dp[j]);
				}
			}
			
			System.out.println(dp[2*n-1]);
		}
		boolean f1(int from,int to){
			int f=(from+1)/2-1, t=(to+1)/2-1;
			Line2D.Double l=new Line2D.Double(p2[from], p2[to]);
			for(int i=f+1; i<t; ++i)if(!new Line2D.Double(p[i][0], p[i][1]).intersectsLine(l))	return false;
			return true;
		}
		Point2D.Double[] intersectR(C a,C b){
			double dis = a.p.distance(b.p);
			if(dis > a.r + b.r)	return null;
			Point2D v = sub(b.p, a.p);
			double rc = (dis*dis+a.r*a.r-b.r*b.r)/(2*dis);
			double rate = rc/dis;
			v = mul(rate,v);
			Point2D c = add(v, a.p);
			double disC2c = c.distance(b.p);
			double disqc = Math.sqrt(b.r*b.r - disC2c*disC2c);
			Point2D v2 = sub(b.p, c);
			v2 = mul(disqc / disC2c, v2);
			Point2D.Double[] ret = new Point2D.Double[2];
			ret[0] = (Point2D.Double)add(normalVector1(v2), c);
			ret[1] = (Point2D.Double)add(normalVector2(v2), c);
			return ret;
		}
		Point2D add(Point2D p1,Point2D p2){
			return new Point2D.Double(p1.getX()+p2.getX(), p1.getY()+p2.getY());
		}
		Point2D sub(Point2D p1,Point2D p2){
			return new Point2D.Double(p1.getX()-p2.getX(), p1.getY()-p2.getY());
		}
		Point2D mul(double v,Point2D p){
			return new Point2D.Double(p.getX()*v, p.getY()*v);
		}
		Point2D normalVector1(Point2D p){
			return new Point2D.Double(-p.getY(), p.getX());
		}
		Point2D normalVector2(Point2D p){
			return new Point2D.Double(p.getY(), -p.getX());
		}
		class C{
			Point2D p;
			double r;
			C(int x,int y,int r){
				this.p=new Point2D.Double(x,y);
				this.r=r;
			}
			
		}
	}
}

Measured memory_bytes: 33972
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()




int main(){
    int a,b,c;
    cin>>a>>b>>c;
    cout<<(a*b/2)<<endl;
}

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

typedef long long ll;
typedef long double ld;
typedef vector<vector<int>> Graph;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
#define pi 3.14159265359
#define inf 2147483647
#define INF 9223372036854775807
#define mod 1000000007
#define mod2 998244353

int main() {
    char X, Y; cin >> X >> Y;
    if(X < Y) cout << '<' << endl;
    else if(X > Y) cout << '>' << endl;
    else cout << '=' << endl;
    return 0;
}

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

int main(){
  double W, H, x, y; cin>>W>>H>>x>>y;
  double S=W*H;
  if(x==W/2 && y==H/2){
    cout<<fixed<<setprecision(10)<<S/2<<" ";
    cout<<1<<endl;
  }
  else{
    cout<<fixed<<setprecision(10)<<S/2<<" ";
    cout<<0<<endl;
  }
}


Measured memory_bytes: 256
N = int(input())
L = list(map(int, input().split()))
ans = 0
for i in range(N-2):
    for j in range (i+1,N-1):
        for k in range(j+1,N):
            if L[i]+L[j]>L[k]:
                if L[j]+L[k]>L[i]:
                    if L[k]+L[i]>L[j]:
                        if (L[i] - L[j]) !=0:
                            if (L[j] -L[k]) !=0:
                                if (L[k]- L[i]) !=0:
                                    ans=ans+1
print(ans)


Measured memory_bytes: 9204
#include<iostream>
using namespace std;
int main()
{
    int n;
    long long int l[86];

    cin>>n;
    l[0]=2;
    l[1]=1;
    for(int i=2;i<=n;i++){
        l[i]=l[i-1]+l[i-2];
    }
    cout<<l[n]<<endl;
}

Measured memory_bytes: 256
/*
读题不规范，爆零两行泪。
数据不清空，爆零两行泪。
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
D P 顺序错，爆零两行泪。
大小少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c;
	cin>>a>>b>>c;
	for(int i=b;i<=c;i++)if(i%a==0)return puts("OK"),0;
	puts("NG");
	return 0;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long int ll;
typedef pair<ll,ll> P;
const ll MOD=1000000009;
const ll INF=1000000010;
const ll LINF=4000000000000000010LL;
const int MAX=310;
const double EPS=1e-9;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int main(){
	vector<int> d,fa;
	bool f[300010];
	for(int i=2;i<=300000;i++){
		if(i%7==1||i%7==6){
			f[i]=true;
			d.push_back(i);
		}else{
			f[i]=false;
		}
	}
	for(int i=0;i<d.size();i++){
		if(f[d[i]]){
			for(int j=d[i]*2;j<=300000;j+=d[i]){
				if(j%d[i]==0){
					f[j]=false;
				}
			}
			fa.push_back(d[i]);
		}

	}
	int n;
	while(cin>>n,n!=1){
		cout<<n<<":";
		for(int i=0;i<fa.size();i++){
			if(n%fa[i]==0){
				cout<<" "<<fa[i];
			}
		}
		cout<<endl;
	}
    return 0;
}



Measured memory_bytes: 3652
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn fanc(n: u64) -> u64 {
    if n == 0 {
        1
    } else {
        (n * fanc(n - 1)) % 1000000007
    }
}

fn main() {
    let n: u64 = read();

    println!("{}", fanc(n));
}


Measured memory_bytes: 5884