akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define Speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

#define st              first
#define nd              second
#define pb              push_back
#define pf              push_front
#define all(a)          (a).begin(), (a).end()
#define lwb             lower_bound
#define upb             upper_bound
#define vvll            vector<vector<ll> >
#define Mset(s, n)      memset(s, n, sizeof(s))
#define Sz(a)           int((a).size())
#define Max(a, b, c)    max(max((ll)(a), (ll)(b)), (ll)(c))
#define Min(a, b, c)    min(min((ll)(a), (ll)(b)), (ll)(c))
#define Unique(a)       sort(all(a)); (a).resize(unique(all(a)) - (a).begin())

typedef long double ld;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;

const ll MOD = 1000000007;
const int oo = 2e9;
const ld PI = acos((ld) -1);
int Getbit(ll x, int k){return (x >> (k - 1)) & 1;}
ll Lcm(ll a, ll b) {return a / __gcd(a, b) * b;}
bool isPrime(ll n){for(ll i = 2; i * i <= n; i++){if(n % i == 0) return 0;} return (n > 1) ? 1 : 0;}
ll Powmod(ll n, ll k, ll p = MOD) {ll r = 1; for(; k; k /= 2, n = n * n % p){if(k & 1) r = r * n % p;} return r;}

const int N = 2e5 + 5;

ll n, m, k;
ll a[N], b[N];

void Solve(){
    string s, t;
    cin >> n;
    cin >> s >> t;
    for(int i = 0; i < n; i++){
        cout << s[i] << t[i];
    }
}

int main(){
    Speed;
    int query = 1; //cin >> query;
    while(query--){
        Solve();
    }
}












Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>

using namespace std;

int main() {
	long long int n;
	cin >> n;
	vector <long long int> a(n);
	for (long long int i = 0; i < n; i++) {
		cin >> a[i];
	}
	long long int nn = 0;
	for (long long int i = 0; i < n; i++) {
		if (a[a[i]-1] == i+1) {
			nn++;
		}
	}
	nn /= 2;
	cout << nn << endl;
	return 0;
}

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

student = [None]*n
for i in range(n):
  student[i] = tuple(map(int, input().split()))

point = [None]*m
for i in range(m):
  point[i] = tuple(map(int, input().split()))

for i in range(n):
  dist = pow(10, 9)
  ans = 0
  x, y = student[i]
  for j in range(m):
    sub = abs(point[j][0]-x) + abs(point[j][1]-y)
    if dist > sub:
      dist = sub
      ans = j+1
  print(ans)

Measured memory_bytes: 9104
n=int(raw_input())
m=int(raw_input())
countlose=[0 for i in range(n+1)]
llist=[[] for i in range(n+1)]
wlist=[[] for i in range(n+1)]
for i in range(m):
    [w,l]=[int(x) for x in raw_input().split()]
    countlose[l]+=1
    wlist[w].append(l)
#for i in range(1,n+1):
#    llist[countlose[i]].append(i)
rank=[]
notyet=range(1,n+1)
only=0
while len(notyet)>0:
    #print countlose
    newtop=[x for x in notyet if countlose[x]==0]
    for x in newtop:
        notyet.remove(x)
    if len(newtop)>1:
    #    print newtop
        only=1
    rank+=newtop
    for j in newtop:
        for k in wlist[j]:
            countlose[k]-=1
for r in rank:
    print r
print only

Measured memory_bytes: 11360
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;

int main(){
  int A,B;
  cin >> A >> B;

  if(A % 2 == 0 || B % 2 == 0){
    cout << "No" << endl;
  }else{
    cout << "Yes" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
const lines=readlines(open("/dev/fd/0"))
input()=shift!(lines)
int(s::String)=parse(Int32,s)
intSub(s::SubString{String})=parse(Int32,s)
intLine()=map(intSub,split(input()))
function main()
    n,m=intLine()
    f=zeros(Int32,n)
    for i in 1:m
        f[int(input())]=1
    end
    a=c=0
    b=1
    m=10^9+7
    for i in 1:n
        a=(b+c)%m*(1-f[i])
        b,c=a,b
    end
    println(a)
end
main()

Measured memory_bytes: 129984
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define P pair<ll,ll>
#define rep(i,n) for(ll (i)=0; (i)<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  lvector v{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};
  ll k;cin>>k;
  print(v[k-1]);
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;

int main(){
    ll n;
    cin>>n;
    ll ans=1e18;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            ans=min(ans,i+n/i-2);
        }
    }
    cout<<ans<<endl;
}

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

using namespace std;

#define LL long long 
#define ULL unsigned LL
#define LD long double

const int MOD = 1e9 + 7;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	int a, b, c;
	int dp[n+1][3];
	dp[0][0] = 0;
	dp[0][1] = 0;
	dp[0][2] = 0;
	for(int i=1; i<=n; i++) {
		cin>>a>>b>>c;
		dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a;
		dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + b;
		dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + c;
	}
	cout<<max(dp[n][0], max(dp[n][1], dp[n][2]));
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll INF = 1e9;
vector<int> dp(5000,INF);
vector<int> bit(5000,0);
int a[5000],b[5000];

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


	for(int i=0;i<m;i++) {
		cin>>a[i]>>b[i];
		for(int j=0;j<b[i];j++) {
			int x; cin>>x; bit[i] += (1<<x-1);
		}
	}

	vector<int> dp(5000,INF);
	dp[0]=0;

	for(int i=0;i<(1<<n);i++){
		for(int j=0;j<m;j++){
			dp[i | bit[j]] = min(dp[i | bit[j]],dp[i] + a[j]);
		}
	}

	if(dp[(1<<n) - 1] == INF) cout<<-1<<endl;
	else cout<<dp[(1<<n)-1]<<endl;

	
}

Measured memory_bytes: 384
using System;

namespace C___Bugged
{
    class Program
    {
        static void Main (string[] args)
        {
            var n = int.Parse (Console.ReadLine ());
            var s = new int[n];
            var sum = 0;
            for (var i = 0; i < n; i++)
            {
                s[i] = int.Parse (Console.ReadLine ());
                sum += s[i];
            }
            if (sum % 10 != 0)
            {
                Console.WriteLine (sum);
            }
            else
            {
                Array.Sort (s);
                for (var i = 0; i < s.Length; i++)
                {
                    if (s[i] % 10 != 0)
                    {
                        Console.WriteLine (sum - s[i]);
                        return;
                    }
                }
                Console.WriteLine (0);
            }
        }
    }
}

Measured memory_bytes: 13140
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define ll long long
#define MAX 10000000
#define SENTINEL 2e10;


int main(){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    while(true){
        c = c - b;
        a = a - d;
        if(c <= 0) {
            cout << "Yes" << endl;
            break;
        }
        if(a <= 0){
            cout << "No" << endl;
            break;
        }
    }
}

Measured memory_bytes: 3632
#include <iostream>
    using namespace std;
     
    long long N, K;
     
    int main() {
    	cin >> N >> K;
    	if (K > (N - 1)*(N - 2) / 2) {
    		cout << "-1" << endl;
    	}
    	else {
    		int rem = (N - 1) * (N - 2) / 2; rem = rem - K;
     
    		cout << (N - 1) + rem << endl;
    		for (int i = 2; i <= N; i++) cout << "1 " << i << endl;
    		for (int i = 2; i <= N - 1; i++) {
    			for (int j = i + 1; j <= N; j++) {
    				if (rem > 0) { cout << i << " " << j << endl; rem--; }
    			}
    		}
    	}
    	return 0;
    }

Measured memory_bytes: 256
#include<cstdio>
#define C(x,y) (fct[x]*ifct[y]%TT*ifct[(x)-(y)]%TT)
using namespace std;
const int maxn=2005,TT=1e9+7;
int n,K,m,F[maxn][maxn];
long long fct[maxn*maxn],ifct[maxn*maxn];
inline int read(){
	int ret=0;bool f=0;char ch=getchar();
	while(ch>'9'||ch<'0') f^=ch=='-',ch=getchar();
	while(ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=getchar();
	return f?-ret:ret;
}
inline long long pow(int x,int y){
	long long ret=1,w=x;
	while(1){
		if(y&1) ret=ret*w%TT;
		if(!(y>>=1)) return ret;
		w=w*w%TT;
	}
}
inline void add(int&x,int y){if((x+=y)>=TT) x-=TT;}
int main(){
	n=read(),K=read();m=n*K;
	if(K==1) return puts("1")&0;
	for (int i=fct[0]=1;i<=m;i++) fct[i]=fct[i-1]*i%TT;
	ifct[m]=pow(fct[m],TT-2);
	for (int i=m;i;i--) ifct[i-1]=ifct[i]*i%TT;
	F[0][0]=1;
	for (int i=1;i<=n;i++)
	for (int j=0;j<=i;j++){
		if(j<i) add(F[i][j],F[i-1][j]);
		if(j) add(F[i][j],C(m-i-(j-1)*(K-1)-1,K-2)*F[i][j-1]%TT);
	}
	printf("%lld\n",fct[n]*F[n][n]%TT);
	return 0;
}

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

int main() {

	int n;
	std::cin >> n;

	std::vector<std::vector<int>> v(n);

	for (int i{}; i < n; ++i) {
		
		int u, k;
		std::cin >> u >> k;

		for (int j{}; j < k; ++j) {
			int t;
			std::cin >> t;
			v[u - 1].emplace_back(t - 1);
		}
	}


	std::vector<int> d(n,0), f(n,0);
	auto time = 0;

	for (int i{}; i < n; ++i)

		[&](int i_,auto gn_)->void {
			gn_(i_, gn_);
		}(i,
			[&](int here, auto fn)->void {
			
				if (d[here] <= 0)
					d[here] = ++time;

				for (const auto&e : v[here])
					if (d[e] <= 0)
						fn(e, fn);
	
				if (f[here] <= 0)
					f[here] = ++time;
				}
		);


		for (int i{}; i < n; ++i)
			std::cout
			<< i + 1 << " "
			<< d[i] << " "
			<< f[i] << "\n";
	return 0;
}


Measured memory_bytes: 3164
#include <bits/stdc++.h>
#define int long long int
#define ld long double
#define MOD 1000000007
#define N 1000006
#define INF 1000000000000000000
using namespace std;

void solve(){
    int n,a,b;
    cin>>n;
    int ans=0;
    pair<int,int> arr[n];
    for(int i=0;i<n;i++){
        cin>>a>>b;
        ans = max(ans, b-a+1);
        arr[i] = {a,b};
    }
    sort(arr,arr+n);
    stack<int> minR;
    minR.push(arr[n-1].second);
    int l2 = arr[n-1].first;

    for(int j=n-2;j>0;j--){
        if(minR.top()>=arr[j].second){
            minR.push(arr[j].second);
        }
    }

    // for(int i=0;i<n;i++){
    //     cout<<arr[i].first<<" "<<arr[i].second<<"\n";
    // }

    int l1=arr[0].first,r1=arr[0].second;
    ans = max(ans, max(r1-l1+1, 0LL) + max(0LL, (int)minR.top()-l2+1));
    //cout<<ans<<"\n";
    for(int i=1;i<n-1;i++){
        if(!minR.empty() && arr[i].second==minR.top()){
            minR.pop();
        }
        ans = max(ans, max(0LL, min(r1,minR.top()) - max(l1,l2) + 1LL ) + arr[i].second - arr[i].first + 1LL);
        r1 = min(r1, arr[i].second);
        l1 = max(l1, arr[i].first);
        ans = max( ans, max(0LL, r1-l1+1) + max(0LL, (int)minR.top()-l2+1) );
        //cout<<ans<<"\n";
    }
    cout<<ans<<"\n";
}

signed main(){
    //fastio
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

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

template<typename T> // なお正数であること
std::uint64_t factrization(T target, std::vector<T> &output)
{
        const auto sq_target = static_cast<T>(sqrt(target)); // 切り捨て
        auto tmp = target;

        std::uint64_t ctr = 0;

        for(auto i = decltype(sq_target)(2); i <= sq_target+2; i++)
        {
                bool flag = false;
                while(tmp % i == 0)
                {
                        tmp /= i;
                        flag = true;
                }

                if(flag)
                {
                        // std::cout << "prime: " <<i << std::endl;
                        output.push_back(i);
                        ctr++;
                }
        }
        if(tmp != 1)
        {
                // std::cout << "prime: " << tmp << std::endl;
                output.push_back(tmp);
                ctr++;
        }

        return ctr;
}

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

        std::uint64_t N,M;
        std::cin >> N;
        std::cin >> M;

        std::priority_queue<std::uint64_t> A;

        for(std::uint64_t i = 0; i < N; i++)
        {
                std::uint64_t n;
                std::cin >> n;
                A.push(n);
        }

        for(std::uint64_t i = 0; i < M; i++)
        {
                const auto target = A.top()/2;
                A.pop();
                A.push(target);
        }

        std::uint64_t ans = 0;
        for(std::uint64_t i = 0; i < N; i++)
        {
                ans += A.top();
                A.pop();
        }
        std::cout << ans << std::endl;
}


Measured memory_bytes: 1400
import java.awt.geom.Line2D;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	class P {
		double x, y;

		P(double x_, double y_) {
			x = x_;
			y = y_;
		}

		P add(P p) {
			return new P(x + p.x, y + p.y);
		}

		P sub(P p) {
			return new P(x - p.x, y - p.y);
		}

		P mul(double v) {
			return new P(x * v, y * v);
		}

		P div(double v) {
			return new P(x / v, y / v);
		}

		double dot(P p) {
			return x * p.x + y * p.y;
		}

		double det(P p) {
			return x * p.y - y * p.x;
		}

		double abs2() {
			return x * x + y * y;
		}

		double abs() {
			return Math.sqrt(abs2());
		}

		P norm() {
			return div(abs());
		}

		P rot90() {
			return new P(-y, x);
		}

		P proj(P src, P dst) {
			P p_sd = dst.sub(src).norm();
			return src.add(p_sd.mul(sub(src).dot(p_sd)));
		}

		P reflect(P src, P dst) {
			P middle = proj(src, dst);
			return add(middle.sub(this).mul(2));
		}

		public String toString() {
			return String.format("%f %f", x, y);
		}
	}

	P isLL(P p1, P p2, P q1, P q2) {
		double d = p2.sub(p1).det(q1.sub(q2));
		if (Math.abs(d) < 1e-10)
			return null;
		return p1.add(p2.sub(p1).mul(q1.sub(q2).det(p1.sub(q2)) / d));
	}

	boolean intersect(P p1, P p2, P q1, P q2) {
		return Line2D.linesIntersect(p1.x, p1.y, p2.x, p2.y, q1.x, q1.y, q2.x, q2.y);
	}

	void run() {

		Scanner sc = new Scanner(System.in);
		int q = sc.nextInt();
		while (q-- > 0) {
			P p1 = new P(sc.nextDouble(), sc.nextDouble());
			P p2 = new P(sc.nextDouble(), sc.nextDouble());
			P q1 = new P(sc.nextDouble(), sc.nextDouble());
			P q2 = new P(sc.nextDouble(), sc.nextDouble());
			System.out.println(intersect(p1, p2, q1, q2) ? 1 : 0);
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}

	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}

}

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

bool contain(string &str, char c) {
  return str.find(c) != string::npos;
}

int main() {
  string s;
  cin >> s;
  string acgt = "ACGT";

  int cnt = 0;
  int max_cnt = 0;
  for (auto& c : s) {
    if (contain(acgt, c)) ++cnt;
    else cnt = 0;
    max_cnt = max(max_cnt, cnt);
  }
  cout << max_cnt << endl;
}


Measured memory_bytes: 256
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int M = sc.nextInt();

		TreeMap<Long, Integer> map = new TreeMap<>();
			for(int i = 0 ; i < N ; i++){
				long cost = sc.nextLong();
				int num = sc.nextInt();
				//map.put(cost,num);
				map.compute(cost, (k,v) -> v==null? num : num+v);
			}
			sc.close();


			long totalcost = 0;
			int bought = 0;

			for(Map.Entry<Long,Integer> kv : map.entrySet()){
				long cost = kv.getKey();
				int maxnum = kv.getValue();

				int buycount = Math.min(maxnum, M-bought);
				totalcost += buycount * cost;
				bought += buycount;

				if(bought > M){
					break;
				}
			}
			System.out.println(totalcost);
	}

}


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

long long n,m,a=1,c;
string s;
bool b;

int main(){
    cin>>n;
    cin>>s;
    for (int i=1; i<n; i++){
        if (s[i]!=s[i-1]){
            a++;
        }
    }
    cout<<a<<endl;
}


Measured memory_bytes: 3764
#include<iostream>
#include<stdio.h>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=50005;
const int mod=1000007;
const double eps=1e-3;
int main()
{
        int n,m;
        while(cin>>n>>m)
        {
                printf("%d\n",(n-1)*(m-1));
        }
	//system("pause");
	return 0;
}


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

int main(){
    int q,x;
    char com[20];

    list<int> v;
    scanf("%d",&q);
    for(int i=0;i<q;i++){
        scanf("%s",com);
        if(com[0]=='i'){
            scanf("%d",&x);
            v.push_front(x);
        }
        else if(com[6]=='F'){
            v.pop_front();
        }
        else if(com[6]=='L'){
            v.pop_back();
        }
        else{
            scanf("%d",&x);
            for(list<int>::iterator it=v.begin();it!=v.end();it++){
                if(*it==x){
                    v.erase(it);
                    break;
                }
            }
        }
    }
    

    list<int>::iterator itr1=v.begin();
    
    for(int i=0;itr1!=v.end();i++){
        if(i++)printf(" ");
        printf("%d",*itr1);
        itr1++;
    }
    printf("\n");

    return 0;
}



Measured memory_bytes: 34456
package main

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

var sc = bufio.NewScanner(os.Stdin)

func Scanner() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, 1000000007)
	sc.Split(bufio.ScanWords)
	n, _ := strconv.Atoi(Scanner())
	ans := 0
	for i := 1; i <= n; i++ {
		if i%3 != 0 && i%5 != 0 {
			ans += i
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 1756
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int k, t;
  cin >> k >> t;

  priority_queue<int> pq;
  rep(i, 0, t) {
    int a;
    cin >> a;
    pq.push(a);
  }

  int ans = 0;
  bool is_first = true, flg = false;
  rep(i, 0, k) {
    if (flg)
      ans++;
    if (pq.size() == 1)
      flg = true;

    if (is_first) {
      int a = pq.top();
      pq.pop();
      a--;
      if (a)
        pq.push(a);
    } else {
      int a = pq.top();
      pq.pop();
      if (!pq.empty()) {
        int b = pq.top();
        pq.pop();
        b--;
        if (b)
          pq.push(b);
      }
      pq.push(a);
    }
    is_first = !is_first;
  }

  cout << ans << endl;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define ll long long
ll gcd(ll a, ll b) {
    if (b==0) return a;
    else return gcd(b, a%b);
}
ll lcm(ll a, ll b) {
    return a * b / gcd(a, b);
}

int main(){
    ll a,b; cin >> a >> b;
    cout << lcm(a,b) << endl;
    return 0;
}

Measured memory_bytes: 256
//@formatter:off
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < int(n); ++i)
#define rrep(i,n) for (int i = int(n)-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = int(s); i < int(n); ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class S,class T> istream& operator>>(istream &is,pair<S,T> &p) { return is >> p.first >> p.second; }
template<class S,class T> ostream& operator<<(ostream &os,const pair<S,T> &p) { return os<<'{'<<p.first<<","<<p.second<<'}'; }
template<class T> istream& operator>>(istream &is,vector<T> &v) { for(T &t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) { os<<'[';rep(i,v.size())os<<v[i]<<(i==int(v.size()-1)?']':','); return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << '\n'; }
void YES(bool b) { cout << (b ? "YES" : "NO") << '\n'; }
template<class T> bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;
//@formatter:on

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int m;
    cin >> m;
    ll ans = -2;
    ll sum = 0;
    rep(_,m) {
        int d;
        ll c;
        cin >> d >> c;
        ans += c;
        sum += c*d;
    }
    ans += (sum+8)/9;
    cout << ans << endl;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define HAIRETU(N,A) for(int i=0;i<N;i++) cin >>A[i]
using namespace std;

int SumDig(int n){
    if (n < 10) return n;
    return SumDig(n / 10) + n % 10;
}

int main(){
    int N;
    cin >> N;
    
    int total=50, B, tmp;
    
    for (int A = 1; A < N; A++) {
        B = N - A;
        tmp = SumDig(A) + SumDig(B);
        total = min(total, tmp);
    }
    cout << total << endl;
    return 0;
}


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


int main() {
int N,L;
cin >> N >> L;
vector<string> vec(N);
rep(i,N) cin >> vec.at(i);
sort(vec.begin(),vec.end());
rep(i,N) cout << vec.at(i);

cout << endl;

return 0;
}


Measured memory_bytes: 3636
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std ;

#define MAXN 200007

int n , k ;
int a[ MAXN ] ;

int br[ MAXN ] ;



void input ( ) {
    scanf ( "%d%d" , &n , &k ) ;
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        scanf ( "%d" , &a[ i ] ) ;
        br[ a[ i ] ] ++ ;
    }
    sort ( br + 1 , br + n + 1 ) ;
}

void solve ( ) {
    int i ;
    int ans = 0 ;
    for ( i = 1 ; i <= ( n - k ) ; i ++ ) {
        ans += br[ i ] ;
    }
    printf ( "%d\n" , ans ) ;
}

int main ( ) {
    input ( ) ;
    solve ( ) ;
    return 0 ;
}


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

class Main {
    public static void bubbleSort(int[] data, int n) {
        int count = 0, tmp;
        for (int i = n - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (data[j] > data[j + 1]) {
                    tmp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = tmp;
                    count++;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (i > 0)
                System.out.print(" ");
            System.out.printf("%d", data[i]);
        }
        System.out.print("\n");
        System.out.println(count);
    }

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

        try {
            int n = Integer.parseInt(br.readLine());
            int nums[] = new int[n];
            String[] input_string = br.readLine().split(" ");

            for (int i = 0; i < n; i++)
                nums[i] = Integer.parseInt(input_string[i]);

            bubbleSort(nums, n);

        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}


Measured memory_bytes: 24956
<?php
$testCaseNum = 1;
while ($inputDate = trim(fgets(STDIN))) {
    outputFormatedDate($testCaseNum, $inputDate);
    $testCaseNum++;
}

function outputFormatedDate($testCaseNum, $inputDate)
{
    printf("Case %d: %d".PHP_EOL, $testCaseNum, $inputDate);
}

Measured memory_bytes: 15084
#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,i,j;
    cin>>n;
    vector<int>a(n);
    for(i=0;i<n-1;++i)
    {
        cin>>j;
        ++a[j-1];
    }
    for(auto it:a)
        cout<<it<<"\n";
    return 0;
}


Measured memory_bytes: 3968
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef std::vector<ll> lls;
constexpr ll INF = 1LL << 60;
constexpr ll MOD = 998244353L;
template<class T> inline void chmin(T& a, T b) { if (a > b) a = b; }
template<class T> inline void chmax(T& a, T b) { if (a < b) a = b; }

void cinv(lls& llVec, ll n, bool to_0_origin = false) {
	ll val;
	llVec.reserve((size_t)(n));
	for (ll i = 0; i < n; i++) {
		cin >> val;
		if (to_0_origin) val--;
		llVec.push_back(val);
	}
}


int main()
{
	ll N, K;
	cin >> N >> K;
	lls h;
	cinv(h, N);
	h.resize(N + K); //+Kは、はみ出しても動くようにする工夫

	lls tbl(N+K, INF); //+Kは、はみ出しても動くようにする工夫
	tbl[0] = 0;

	for (ll i = 0; i < N - 1; i++) {

		for (ll k = 1; k <= K; k++) {
			//if (i + k >= N) break;

			chmin(tbl[i + k], tbl[i] + std::abs(h[i] - h[i + k]));
		}
	}

	cout << tbl[N - 1] << '\n';

	return 0;
}


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


def solve(X: int, t: int):
    print(max(X - t, 0))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    t = int(next(tokens))  # type: int
    solve(X, t)


if __name__ == '__main__':
    main()


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

using namespace std;

int main(){
    int num[3];
    int i,j,k;
    int ans=10000;
    cin>>num[0]>>num[1]>>num[2];
    for(i=0;i<3;i++){
        for(j=0;j<3;j++){
            for(k=0;k<3;k++){
                if (i!=k&&i!=j&&j!=k)
                    ans=min(ans,abs(num[i]-num[j])+abs(num[j]-num[k]));
            }
        }
    }
    cout<<ans;
    return 0;

}

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

#define rep(i, n) for (int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()

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

template<class T> void print(const T& value) {
	std::cout << value << "\n";
}

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

using ll = long long int;


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

	int d;
	int m;

	cin >> m >> d;

	int cnt = 0;
	for (int k = 1; k <= m; k++) {
		for (int i = 22; i <= d; i++) {
			int d10 = i / 10,
				d1 = i % 10;

			if (d1 < 2)	continue;

			if (k == d10 * d1)
				cnt++;
		}
	}

	print(cnt);

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
int asc(const void* a, const void* b)
{
	if (*(long long int*)a > * (long long int*)b)return -1;
	if (*(long long int*)a < *(long long int*)b)return 1;
	return 0;
}
long long int comb(long long int n, long long int r)
{
	if (n < r)
		return 0;
	long long int res = 1;
	long long int i;
	for (i = 0; i < r; i++)
	{
		res *= n - i;
		res /= i + 1;
	}
	return res;
}
int main()
{
	long long int n, a, b;
	scanf("%lld %lld %lld", &n, &a, &b);
	long long int i;
	long long int v[55];
	for (i = 0; i < n; i++)
		scanf("%lld", &v[i]);
	qsort(v, n, sizeof(long long int), asc);
	long long int ave = 0;
	for (i = 0; i < a; i++)
		ave += v[i];
	printf("%.20lf\n", (double)ave / (double)a);
	long long int count = 0;
	for (i = 0; i < n; i++)
		if (v[i] == v[a - 1])
			count++;
	long long int ans = 0;
	if (v[0] == v[a - 1])
	{
		for (i = a; i <= b; i++)
			ans += comb(count, i);
	}
	else
	{
		long long int x = 0;
		for (i = a - 1; i >= 0; i--)
			if (v[i] == v[a - 1])
				x++;
		ans = comb(count, x);
	}
	printf("%lld\n", ans);
	return 0;
}

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

using namespace std;
#define inputInt(a) int a; cin >> a; 
#define inputInt2(a,b) int a; int b; cin >> a >> b; 
#define inputInt3(a,b,c) int a; int b; int c; cin >> a >> b >> c;
#define inputLong(a) long a;cin >> a; 
#define inputIntArray(a,N) int a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputLongArray(a,N) long a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputIntArray2(a,b,N) int a[N]; int b[N]; for(int i=0;i<N;i++){cin >> a[i] >> b[i];}
#define output(answer) cout << answer << endl;
#define fN(i,N)    for(int i=0; i<N; i++)
#define fSE(i,s,e) for(int i=s; i<=e; i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main()
{
  //input
  int r;
  cin >> r;
  cout << 3*r*r << endl;

  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 LOG1(a)			  cerr<< #a << " = " << (a) << "\n"
#define LOG2(a, b)		  cerr<< #a << " = " << (a) << ", " << #b << " = " << (b) << "\n"
#define endl "\n"

typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<int> vi;

const ll INF = 1e18;
const int inf = 1e9;
const int MOD = 1e9 + 7;
const int nax = 1000000 + 10;

int n, arr[nax];
int main()
{
    ios::sync_with_stdio(0);
    ll n, a;
    cin >> n;
    ll sum = 0;
    for(int i = 1; i <= n; i++) cin >> arr[i], sum += arr[i];
    sort(arr + 1, arr + n + 1);
    ll ans = 0;
    for(int i = n; i >= 1; i -= 2) ans += arr[i];
    cout << ans - (sum - ans) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <cstdio>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
#include <cstring>
#include <algorithm>

long long int mod2(long long int x){
  if(x > 0){
    return x%2;
  }
  else if(x==0){
    return 0;
  }
  else{
    return (-x)%2;
  }
}
int main(){
  long long int A, B;
  scanf("%lld%lld", &A, &B);
  
  std::cerr << "Answer:" << std::endl;
  if(mod2(A) == mod2(B)){
    std::cout << (A+B)/2 << std::endl;
  }
  else{
    std::cout << "IMPOSSIBLE" << std::endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
//  Copyright © 2019 Diego Garcia Rodriguez del Campo. All rights reserved.
#include<bits/stdc++.h>
#define MAX 200005
#define pii pair < int , int >
#define fi first
#define se second
#define INF 1e9
#define optimiza_io cin.tie(0); ios_base::sync_with_stdio(0);
using namespace std;
typedef long long i64;

struct node {
    int x, t, d;
    bool operator < ( const node & a ) const {
        return d > a.d;
    }
};

int N, M, S, T;
vector < pii > ady[MAX];
int dist[MAX][3];

void dijkstra( int ini ) {
    
    for( int i = 1; i <= N; i ++ )
        for( int j = 0; j < 3; j ++ )
            dist[i][j] = INF;
        
    priority_queue < node > q;
    q.push( { ini , 0 , 0 } );
    
    while( ! q.empty() ) {
        node n = q.top();
        q.pop();
        if( dist[n.x][n.t] != INF )
            continue;
        dist[n.x][n.t] = n.d;
        for( auto v : ady[n.x] )
            if( dist[v.fi][( n.t + 1 ) % 3] == INF )
                q.push( { v.fi , ( n.t + 1 ) % 3 , n.d + v.se } );
    }
} 

int main()
{
    optimiza_io
    cin >> N >> M;
    while( M -- ) {
        int a, b, c;
        c = 1;
        cin >> a >> b;
        ady[a].push_back( { b , c } );
    }
    
    cin >> S >> T;
    dijkstra( S );
    if( dist[T][0] == INF )
        cout << "-1\n";
    else
        cout << dist[T][0] / 3 << "\n";
    return 0;
}

Measured memory_bytes: 10484
from collections import defaultdict
N = int(input())
A = [int(c) for c in input().split()]
dic = defaultdict(list)
for i,a in enumerate(A):
  dic[a].append(i)
s = 0
for k in dic.keys():
  n = len(dic[k])
  s += n*(n-1)//2
for i,a in enumerate(A):
  n = len(dic[a])
  print(s-n+1)

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

public class Main {
    public static final long mod = (long)1e9+7;
    public static final long INF = Long.MAX_VALUE/10;
    public static final int inf = Integer.MAX_VALUE/10;

    static void solve(InputReader in, PrintWriter out){
        char[] s = in.ns().toCharArray();
        char[] t = in.ns().toCharArray();
        int[] trans = new int[26];
        Arrays.fill(trans, -1);
        boolean flag = true;
        for (int i = 0; i < s.length; i++) {
            if(trans[s[i]-'a']!=-1&&trans[s[i]-'a']!=t[i]-'a'){
                flag = false;
                break;
            }else{
                trans[s[i]-'a'] = t[i]-'a';
            }
        }
        boolean[] alp = new boolean[26];
        Arrays.fill(alp, false);
        for (int i = 0; i < 26; i++) {
            if(trans[i]>0){
                if(alp[trans[i]]) flag = false;
                else alp[trans[i]] = true;
            }
        }
        out.println(flag?"Yes":"No");
    }

    public static void main(String[] args) throws Exception{
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public Double nd(){
            return Double.parseDouble(ns());
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

Measured memory_bytes: 28940
#include<iostream>
using namespace std;
int s[366][26];
int heu = 4;
int main() {

	int d;
	cin >> d;
	int c[26];
	int i, j, j2;
	for (i = 0; i < 26; i++) {
		cin >> c[i];
	}

	for (i = 0; i < d; i++) {
		for (j = 0; j < 26; j++) {
			cin >> s[i][j];
		}
	}
	int last[26];
	for (i = 0; i < 26; i++) {
		last[i] = 0;
	}
	int jmax, jindex, jindex2;
	for (i = 1; i <= d; i++) {

		jmax = 0;
		jindex = -1;
		jindex2 = -1;
		/*for (j = 0; j < 26; j++) {
			if (c[j] *(i - last[j]) > jmax) {
				jmax = c[j] *(i - last[j]);
				jindex = j;
			}
			else if (c[j] *(i - last[j]) == jmax) {
				if (s[i - 1][j] > s[i - 1][jindex]) {
					jindex = j;
				}
			}
		}*/
		for (j = 0; j < 26; j++) {
			for (j2 = 0; j2 < 26; j2++) {
				if (j != j2) {
					if (s[i - 1][j] + heu * c[j] * (i - last[j]) + s[i][j2] + heu * c[j2] * (i + 1 - last[j2]) > jmax) {
						jmax = s[i - 1][j] + heu * c[j] * (i - last[j]) + s[i][j2] + heu * c[j2] * (i + 1 - last[j2]);
						jindex = j;
						jindex2 = j2;
					}
				}
				else {
					if (s[i - 1][j] + heu * c[j] * (i - last[j]) + s[i][j2] + heu * c[j2] > jmax) {
						jmax = s[i - 1][j] + heu * c[j] * (i - last[j]) + s[i][j2] + heu * c[j2];
						jindex = j;
						jindex2 = j2;
					}
				}
			}
		}
		/*for (j = 0; j < 26; j++) {
			if (s[i - 1][j] + 15 * c[j] * (i - last[j]) >= jmax) {
				jmax = s[i - 1][j] + 15 * c[j] * (i - last[j]);
				jindex = j;
			}
		}*/
		last[jindex] = i;
		cout << jindex + 1 << endl;



	}
	return 0;


}

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

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

int MAX = 100000;
int cost_all[200020];
int cost_single[200020];

using pii = pair<int, int>;

void init() {}
bool solve() {
    int N;
    cin >> N;
    if (N == 0) return false;
    vector<int> H(N);
    REP(i, N) cin >> H[i];
    vector<pii> vs, va;
    int M;
    cin >> M;
    REP(i, M) {
        string s;
        cin >> s;
        int cost;
        cin >> cost;
        cin >> s;
        int d;
        cin >> d;
        if (s == "Single") {
            vs.push_back({cost, d});
        } else
            va.push_back({cost, d});
    }
    REP(i, MAX + 100) {
        cost_single[i] = 1e9;
        cost_all[i] = 1e9;
    }
    cost_all[0] = cost_single[0] = 0;
    REP(i, MAX) {
        for (auto p : vs) {
            int cost = p.first;
            int d = p.second;
            int nxt = min(MAX, i + d);
            if (cost_single[nxt] > cost_single[i] + cost) {
                cost_single[nxt] = cost_single[i] + cost;
            }
        }
        for (auto p : va) {
            int cost = p.first;
            int d = p.second;
            int nxt = min(MAX, i + d);
            if (cost_all[nxt] > cost_all[i] + cost) {
                cost_all[nxt] = cost_all[i] + cost;
            }
        }
    }
    for (int i = MAX; i >= 0; i--) {
        cost_single[i] = min(cost_single[i], cost_single[i + 1]);
        cost_all[i] = min(cost_all[i], cost_all[i + 1]);
    }
    int ans = 1e9;
    REP(d, MAX + 1) {
        int res = cost_all[d];
        REP(i, N) {
            int rem = max(0LL, H[i] - d);
            res += cost_single[rem];
        }
        // if (res < ans) cout << d << " " << res << endl;
        ans = min(ans, res);
    }
    cout << ans << endl;
    return true;
}
signed main() {
    init();
    while (solve())
        ;
}


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

using namespace std;

#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;


int main() {
    ios_base::sync_with_stdio(false);
    string s;
    cin >> s;
    int ans = 0;
    forn (i, (int)s.length()) {
        if (s[i] == '1') {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


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

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

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

const ll MAXCYCLE = 16 * 9 * 5 * 7 * 11;
ll cycle[25][25];
ll total[MAXCYCLE];

int main() {
  int n;
  while (scanf("%d", &n), n) {
    MEMSET(cycle, 0);
    MEMSET(total, 0);
    REP(i, n) {
      int d, offset;
      scanf("%d %d", &d, &offset);
      assert(0 <= offset);
      REP(j, d) {
        int q;
        scanf("%d", &q);
        cycle[d][(d - offset + j) % d] += q;
      }
    }
    ll ans = 0;
    FOR(i, 1, 25) {
      if (i == 13 || i == 17 || i == 19 || i == 23) {
        ll maxvalue = 0;
        REP(j, i) {
          maxvalue = max(maxvalue, cycle[i][j]);
        }
        ans += maxvalue;
        continue;
      }
      int hour = 0;
      REP(j, MAXCYCLE) {
        total[j] += cycle[i][hour];
        hour = (hour + 1) % i;
      }
    }
    ll maxvalue = 0;
    REP(i, MAXCYCLE) {
      maxvalue = max(maxvalue, total[i]);
    }
    ans += maxvalue;
    printf("%lld\n", ans);
  }
}

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

int main() {
  long long int X;
  cin>>X;
  long long int money=100;
  long long int answer=0;
  while(money<X){
    long long int up=money/100;
    money+=up;
    answer++;
  }
  cout<<answer<<endl;
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define DEBUG_ARR(v,n) cout<<#v<<":";REP(i,n)cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) { a = b; return true; }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) { a = b; return true; }
    return false;
}
template<class T>
void DEBUG_DP(T* viewdp, int ilen, int jlen){
    REP(i,ilen){
        REP(j,jlen){
            if(viewdp[i][j] != -1)
                printf("[% 4d]", viewdp[i][j]);
            else
                printf("[    ]");
        }
        puts("");
    }
}

int h,w;
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>h>>w;
    vector<vector<char>> m(h+2,vector<char>(w+2,'.'));
    ll dp[1005][1005] = {};
    REP(i,h) REP(j,w) cin>>m[i][j];
    dp[0][0]=1;
    REP(i,h) REP(j,w){
        if(m[i][j]=='.'){
            dp[i+1][j] += dp[i][j] % MOD;
            dp[i][j+1] += dp[i][j] % MOD;
        }
    }

    //DEBUG_DP(dp,21,21);

    cout << dp[h-1][w] << endl;
    return 0;
}

Measured memory_bytes: 9216
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define    endl        '\n'
#define mii         map<ll int,ll int>
#define msi         map<string,ll int>
#define mis         map<ll int, string>
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define repp(i,a,b)    for(ll int i=b-1;i>=a;i--)
#define tr(container,it) for(__typeof__(container.begin()) it = container.begin(); it != container.end(); it++)
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define mpi         map<pair<ll int,ll int>,ll int>
#define vii         vector<pair<ll,pair<ll,ll> > >
#define vs          vector<string>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        998244353
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define what_is(x)  cerr << #x << " is " << x << endl;
using namespace std;
#define N  10000
#define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";



void solve(){
	ll x;
	cin>>x;
	rep(i,-1001,1001){
		rep(j,-1001,1001){
			if(i*i*i*i*i-j*j*j*j*j==x){
				cout<<i<<" "<<j;
				return;
			}
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll TESTS=1,an=1,f;
    // cin>>TESTS;
    while(TESTS--){
        // cout<<"Case #"<<an<<": ";
        an++;
        solve();

    }
    return 0;
}

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

int batas, even, odd, sementara;


int main(){
	cin>>batas;
	if(batas%2==1){
		sementara=batas-1;
		sementara/=2;
		even=sementara;
		odd=batas-sementara;
	}else{
		odd=batas-batas/2;
		even=batas/2;
	}
	cout<<even*odd<<endl;
}

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

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

  if(x>=30) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 3620
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

const long long INF = LLONG_MAX / 2;

long long solve(const vector<vector<vector<long long> > >& v, long long t)
{
    vector<vector<long long> > ans(2, {INF, -INF});
    for(int i=0; i<2; ++i){
        for(int d=-1; d<=1; ++d){
            if(v[i][d+1][0] == INF)
                continue;
            ans[i][0] = min(ans[i][0], v[i][d+1][0] + d * t);
            ans[i][1] = max(ans[i][1], v[i][d+1][1] + d * t);
        }
    }
    return (ans[0][1] - ans[0][0]) * (ans[1][1] - ans[1][0]);
}

int main()
{
    int n;
    cin >> n;
    vector<vector<vector<long long> > > v(2, vector<vector<long long> >(3, {INF, -INF}));
    for(int i=0; i<n; ++i){
        long long x, y;
        char d;
        cin >> x >> y >> d;
        x *= 2;
        y *= 2;

        int dx = 0;
        int dy = 0;
        if(d == 'L')
            dx = -1;
        else if(d == 'R')
            dx = 1;
        else if(d == 'D')
            dy = -1;
        else
            dy = 1;

        v[0][dx+1][0] = min(v[0][dx+1][0], x);
        v[0][dx+1][1] = max(v[0][dx+1][1], x);
        v[1][dy+1][0] = min(v[1][dy+1][0], y);
        v[1][dy+1][1] = max(v[1][dy+1][1], y);
    }

    long long ans = solve(v, 0);
    for(int i=0; i<2; ++i){
        for(int d1=-1; d1<=1; ++d1){
            for(int d2=d1+1; d2<=1; ++d2){
                if(v[i][d1+1][0] == INF || v[i][d2+1][0] == INF)
                    continue;
                for(int j=0; j<2; ++j){
                    long long t = (v[i][d2+1][j] - v[i][d1+1][j]) / (d1 - d2);
                    if(t >= 0)
                        ans = min(ans, solve(v, t));
                }
            }
        }
    }
    printf("%.2f\n", ans / 4.0);

    return 0;
}


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

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
char laz[maxn];
int pi[12*maxn];
int prefix_function(const string &s,const string &t) {
    ///search t on s
    int m=(int)t.length();
    int n = t.length()+s.length()+1;
    auto ss=[&](int idx){
        if(idx==m)return '#';
        if(idx<m)return t[idx];
        return s[idx-m-1];
    };
    pi[0]=0;
    for (int i = 1; i < n; i++) {
        int j = pi[i-1];
        while (j > 0 && ss(i) != ss(j))
            j = pi[j-1];
        if (ss(i) == ss(j))
            j++;
        pi[i] = j;
    }
    int ma=-1;
    for(int i=n-1;i>m;i--){
        pi[i]=(pi[i]==m?1:0);
        if(i+m<n&&pi[i]==1){
            pi[i]+=pi[i+m];
        }
        ma=max(ma,pi[i]);
    }
    return ma;
}
string s,t,a,ss,tt;
/**
There exists a non-negative integer j
such that the concatenation of i copies of t
is a substring of the concatenation of j copies of s.
*/


int main(){
    scanf("%s",laz);
    ss=string(laz);
    scanf("%s",laz);
    t=string(laz);
    s=ss;
    while((int)s.length()<=(int)t.length()+(int)ss.length()){
        s+=ss;
    }
    s+=ss;
    int c=prefix_function(s,t);
    if(c==-1){
       return !printf("0");
    }
    s+=s;
    int cc=prefix_function(s,t);
    if(cc==c){
        return !printf("%d\n",cc);
    }
    else{
        return !printf("-1");
    }
}
/*
    Good Luck
        -Lci70121
*/


Measured memory_bytes: 24072
N, L = map(int, input().split())
apple = []
for i in range(1, N+1):
    apple.append(L + i - 1)
    
apple_eating = []
sum_apple = sum(apple)
for j in apple:
    apple_eating.append(sum_apple - j)
    
temp = 100
ans = 0
for k in apple_eating:
    if abs(sum_apple - k) <= temp:
        temp = abs(sum_apple - k)
        ans = k
        
print(ans)

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

int main(){
  int n;
  std::cin >> n;
  std::vector<int> v(n);
  for(int i=0;i<n;i++)std::cin >> v[i];
  int t = 0;
  for(int i=0;i<n;i++){
    if(i < v[i]-1 && v[v[i]-1]-1==i)t++;
  }
  std::cout << t << std::endl;
  return 0;
}

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

int main(int argc, const char * argv[]) {
    // insert code here...
    int x, y;
    cin >> x >> y;
    
    string a = "0020101001010";
    
    if (a[x] == a[y]) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}


Measured memory_bytes: 256