akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_macros)]
macro_rules! parse_line {
    ( $t:ty ) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            iter.next().unwrap().parse::<$t>().unwrap()
        }
    );

    ( $( $t:ty), +) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ( $(iter.next().unwrap().parse::<$t>().unwrap()),* )
        }
    );
}

#[allow(unused_macros)]
macro_rules! read_line {
    () => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            line.pop();
            line
        }
    )
}

#[allow(unused_macros)]
macro_rules! parse_vec {
    ( $t:ty ) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let iter = line.split_whitespace();
            iter.map(|v| v.parse::<$t>().unwrap()).collect::<Vec<_>>()
        }
    )
}

fn solve(s: String) -> Option<Vec<(usize, usize)>> {

    let cvec = s.chars().collect::<Vec<_>>();
    let n = cvec.len();

    if cvec[0] != '1' { return None }
    if cvec[n-1] != '0' { return None }

    let mut parent = n;
    let mut ans = Vec::new();

    for i in (0..(n-1)).rev() {
        if cvec[i] != cvec[n-i-2] { return None }

        ans.push((parent, i+1));
        if cvec[i] == '1' {
            parent = i+1;
        }
    }

    return Some(ans)
}

fn main() {
    let s = read_line!();
    match solve(s) {
        Some(vec) => {
            for v in vec {
                println!("{} {}", v.0, v.1);
            }
        },
        _ => println!("-1")
    };
}

#[test]
fn solve_test() {
    assert_eq!(solve("1110".to_owned()), Some(vec![(4,3), (3,2), (2,1)]));
}


Measured memory_bytes: 7548
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		new Main().run();
	}

	private void run() {
		Scanner scanner = new Scanner(System.in);
		for (int i = 0; i < 7; i++) {
			System.out.println(scanner.nextInt() - scanner.nextInt());
		}
	}
}

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

typedef long long int ll;
typedef unsigned long long int ull;

int main() {
  int x, y;

  cin >> x >> y;
  if (y % 2 != 0) {
    cout << "No" << endl;
    return 0;
  }
  if (2 * x <= y && 4 * x >= y) {
    for (int i = 0; i <= x; i++) {
      if (2 * i + 4 * (x - i) == y) {
        cout << "Yes" << endl;
        break;
      }
    }
  } else {
    cout << "No" << endl;
  }
}


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

int main(){
    int n, a, b;
    cin >> n >> a >> b;

    int sum = 0;
    for(int i = 1; i <= n; i++){
        int total = 0;
        int number = i;
        while(number > 0){
            total += number % 10;
            number /= 10;
        }
        if(a <= total && total <= b)
            sum += i;
    }

    cout << sum << endl;

    return 0;
}

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

int main(int argc, char** argv)
{
    int num;

    cin >> num;
    for (int i = 0; i < num; i++) {
        vector<int> v = vector<int>(3);
        cin >> v[0] >> v[1] >> v[2];
        sort(v.begin(), v.end());
        if (v[0] * v[0] + v[1] * v[1] == v[2] * v[2]) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}
 

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

int main()
{
  pair<pair<string, int>, int> guide[110];

  int n;
  cin >> n;

  for(int i = 0; i < n; i++){
    string s;
    int p;

    cin >> s >> p;

    guide[i] = make_pair(make_pair(s, -p), i);
  }

  sort(guide, guide+n);

  for(int i = 0; i < n; i++){
    cout << guide[i].second + 1 << endl;
  }

  return 0;

}


Measured memory_bytes: 256
n = int(input())

input_list = list(map(int, input().split()))

ans = 0
tmp_max = input_list[0]
for i in range(1, n):
    if input_list[i] < tmp_max:
        ans +=  tmp_max - input_list[i]
        
    if input_list[i] > tmp_max:
        tmp_max = input_list[i]
        
        
print(ans)

Measured memory_bytes: 32056
#include <stdio.h>
int main(void){
    int i,a,b,c,s[4],max=0,total;
    scanf("%d%d%d",&a,&b,&c);
    total=a+b+c;
    s[1]=a;s[2]=b;s[3]=c;
    for(i=1;i<=3;i++){
        if(s[i]>max) max=s[i];
    }
    for(i=1;i<=3;i++){
        if(s[i]==max) {s[i]=0;break;}
    }
    if(max==total-max) printf("Yes");
    else printf("No");
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <set>
#include <utility>
#include <algorithm>

struct paircomp {
    using T = std::pair<long long, long long>;
    bool operator()(const T& l, const T& r) const {
        return l.first > r.first || (!(r.first > l.first) && l.second < r.second);
    }
};

int main() {
    long long n, t, count = 0, minimum;
    std::cin >> n;
    std::vector<long long> ret(n);
    /* remain, number */
    std::set<std::pair<long long, long long>, paircomp> s;
    for (auto i = 0ll; i < n; i++) {
        std::cin >> t;
        s.insert({ t, i });
    }

    //std::for_each(s.begin(), s.end(), [](auto& el) { std::cout << el.second << " " << el.first << std::endl; });

    minimum = s.begin()->second;
    while (!s.empty()) {
        auto curr = *s.begin();
        minimum = std::min(minimum, s.begin()->second);
        while (!s.empty() && s.begin()->first == curr.first) {
            s.erase(s.begin());
            count++;
        }
        ret[minimum] += (curr.first - (s.empty()?0:s.begin()->first)) * count;
    }

    for (auto el : ret) std::cout << el << std::endl;

    return 0;
}

Measured memory_bytes: 9472
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <map>

using namespace std;
using llong = long long;
const int MOD=1000000007;


int main(int argc, char**argv){
    int n, m;
    cin >> n >> m;
    // vector<int> k(n, 0);
    int k;

    vector<int> like(m, 0);
    for (int j = 0; j < n; j++) {
        cin >> k;
        for (int i = 0; i < k; i++) {
            int tmp;
            cin >> tmp;
            like[tmp-1]++;
        }
    }
    int ans = 0;
    for (int i = 0; i < m; i++){
        if (like[i] == n){
            ans++;
        }
    }
    cout << ans << endl;

    return 0;
}














Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <ctype.h>
#include <map>
#include <vector>
#include <stdlib.h>
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define REP1(j,n) for(int j=0;j<(int)n;++j)
#define REPD(i,n) for(int i=n;i>=0;--i)
#define REPD1(j,n) for(int j=n;j=>0;--j)
#define REPS(i,n) for(int i=1;i<=(int)n;++i)
#define REPS1(j,n) for(int j=1;j<=(int)n;++j)
#define rep(i,a,n) for(int i=a;i<=(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define DescSort(a) sort(a.begin(),a.end(),std::greater<int>())

using namespace std;
typedef long long ll;

int main(void) {
	int a, b, c;
	cin >> a >> b >> c;
	int sum1 = a + b, sum2 = b + c, sum3 = a + c;
	cout << min({ sum1,sum2,sum3 }) << endl;
	return 0;
}


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

int main(){
  int N, num=0;
  bool flag = false;
  cin >> N;
  for(int i=0; i<N; i++){
    int d1, d2;
    cin>> d1 >> d2;
    if(d1 == d2){
      num++;
      if(num == 3){
        flag = true;
        break;
      }
    }else
      num = 0;
  }
  
  if(flag == true)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  
  return 0;
}


Measured memory_bytes: 3592
N=int(input())
a=list(map(int,input().split()))
odd=1
cnt=0
while True:
    for i in range(N):
        if a[i]%2!=0:
            odd=0
    if odd==0:
        break
    for i in range(N):
        a[i]=a[i]/2
    cnt+=1
print(cnt)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#include <sstream>
#include <iomanip>
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define min_3(a,b,c) min(a,min(b,c))
#define max_3(a,b,c) max(a,max(b,c))
#define nout(ans) cout << (ans) << "\n"
#define sout(ans) cout << (ans) << " "
using namespace std;

const double pi = 3.14159265359;
const ll INF = 1e12;
const ll MOD = 1e9 + 7;
const ll N = 1e5 + 5;
/*
Decimal Places: cout << fixed << setprecision(n) << ans << endl

String to integer:
stringstream dark(s);
int x = 0; dark >> x;
*/

bool compare(const pair<int, int>&i, const pair<int, int>&j)
{
    return i.second < j.second;
}


int a, b, c;

void solve()
{
    cin >> a >> b >> c;
    nout((a+b+c>=22) ? "bust" : "win");
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    //cin >> t;
    for (int i=1; i<=t; i++)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 256
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;

void main()
{
    auto N = readln.chomp.to!int;

    bool[int] data;
    foreach(_; 0..N){
        auto A = readln.chomp.to!int;
        if(A in data)
            data.remove(A);
        else
            data[A] = true;
    }
    writeln(data.length);
}

Measured memory_bytes: 7548
#include <bits/stdc++.h>
using namespace std;
#define REP(asd, fgh) for(int asd = 0; asd < fgh; asd++)
#define MAX_N 200000

class RMinQ{
  public:
  int n;
  int data[MAX_N * 2 - 1];

  void init(){
    for(int i=0; i < 2 * n - 1; i++){
      data[i] = INT_MAX;
    }
  }
  void update(int i, int x){
    i += n - 1;
    data[i] = x;
    while(i > 0){
      i = (i-1) / 2;
      data[i] = min(data[i*2+1], data[i*2+2]);
    }
  }
  int query(int a, int b, int k, int l, int r){
    if(r <= a || b <= l) return INT_MAX;
    if(a <= l && r <= b) return data[k];
    else{
      int vl = query(a, b, k*2+1, l, (l+r)/2);
      int vr = query(a, b, k*2+2, (l+r)/2, r);
      return min(vl, vr);
    }
  }
};

int main(void){
  int n;
  int a[MAX_N];
  RMinQ r;
  int res = INT_MIN;
  int tmp=1;
  cin >> n;
  while(1){
    if(pow(2, tmp) >= n){
      r.n = pow(2, tmp);
      break;
    }
    tmp++;
  }
  r.init();
  REP(i, n){
    cin >> a[i];
    r.update(i, a[i]);
  }





  for(int i = n-1; i >= 1; i--){
    res = max(res, a[i] - r.query(0, i, 0, 0, r.n));
  }

  cout << res << endl;

  return 0;
}

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

using namespace std;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<queue<int> > g(N + 1);
    queue<pair<int, int> > q;
    for (int i = 1; i < N + 1; ++i) {
        for (int j = 0; j < N - 1; ++j) {
            int a;
            cin >> a;
            g[i].push(a);
        }
    }
    for (int i = 1; i < N + 1; ++i) {
        if (g[g[i].front()].front() == i && i < g[i].front()) q.push({i, g[i].front()});
    }
    int ans = 0;
    for (int cnt = 0; cnt < N * (N - 1) / 2; ++ans) {
        if (q.empty()) {
            // is cyclic
            puts("-1");
            return 0;
        }
        for (int i = q.size(); i--; ++cnt, q.pop()) {
            int a = q.front().first;
            g[a].pop();
            if (g[g[a].front()].front() == a) {
                q.push({a, g[a].front()});
            }
            a = q.front().second;
            g[a].pop();
            if (g[g[a].front()].front() == a) {
                q.push({a, g[a].front()});
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}


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

#define fi first
#define se second
#define all(x) x.begin(), x.end()
using namespace std;
using ull = unsigned long long;
using ll = long long;

struct __INIT {
    __INIT() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(15);
    }
} __init;

int main() {
    vector<pair<ll, double>> A(4);
    for(int i = 0; i < 4; i++){
        cin >> A[i].fi;
    }
    ll N;
    cin >> N;
    //price, L
    A[0].se = 0.25;
    A[1].se = 0.50;
    A[2].se = 1.0;
    A[3].se = 2.0;
    for(int i = 0; i < 4; i++) A[i].fi /= (A[i].se / 2);
    sort(all(A));
    for(int i = 0; i < 4; i++) A[i].fi *= (A[i].se / 2);

    ull sum = 0;
    for(auto p : A){
        if(N == 0) break;
        sum += p.fi * (int)(N / p.se);
        N -= (int)(N / p.se) * p.se;

    }
    cout << sum << endl;
}

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

int main()
{
  int n,x;cin >> n >> x;
  vector<int> a(n);
  long long  check = 0;
  for (auto &&i: a)
  {
    cin >> i;
    check += i;
  }
  if (check < x)
  {
    cout <<  n - 1 << endl;
    return 0;
  }
  sort(a.begin(), a.end());
  long long sum = 0;
  int ans = 0;
  for (ans; ans < n; ans++)
  {
    sum += a[ans];
    if (sum > x)
    {
      break;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3576
def main(argv)
  (h, w, a, b) = gets.chomp.split(' ').map(&:to_i)

  s = []

  (h - b).times do |y|
    s[y] = [0] * a + [1] * (w - a)
  end

  b.times do |y|
    s[y + (h - b)] = [1] * a + [0] * (w - a) 
  end

  puts s.map{|row| row.map(&:to_s).join('')}.join("\n")
end

if self.to_s == 'main' then
  main(ARGV)
end

Measured memory_bytes: 16508
N = int(input())
A = list(map(int,input().split()))

buy = []
sell = []

if A[0] < A[1]:
    buy.append(0)
    f = True #上がり目
else:
    f = False #下がり目
for i in range(1,len(A)-1):
    if f == True:
        if A[i] > A[i+1]:
            sell.append(i)
            f = False
    else:
        if A[i] < A[i+1]:
            buy.append(i)
            f = True
if f == True:
    sell.append(len(A)-1)

ans = 1000
stock = 0
for i in range(len(buy)):
    stock = ans // A[buy[i]]
    ans %= A[buy[i]]
    ans += A[sell[i]] * stock
    stock = 0
print(ans)


Measured memory_bytes: 9228
#include <bits//stdc++.h>
using namespace std;
#define int long long
#define rep(i,n,k) for(int i=n;i<k;i++)
#define P make_pair
#define F first
#define S second
#define M LLONG_MAX
signed main(void){
    int n,m,ans,w,p,q;
    ans=0;
    string s,s1,s2;
    cin>>n>>m>>p;
    vector<int> v,x,y;
    rep(i,0,n){
        cin>>q;
        x.push_back(q);
    }
    rep(i,0,m){
        cin>>q;
        y.push_back(q);
    }
    rep(i,0,p){
        int a,b;
        cin>>a>>b>>q;
        v.push_back(x[a-1]+y[b-1]-q);
    }
    sort(x.begin(),x.end());
    sort(y.begin(),y.end());
    v.push_back(x[0]+y[0]);
    sort(v.begin(),v.end());
    cout<<v[0]<<endl;
    
}


Measured memory_bytes: 3316
#include<iostream>
using namespace std;
int main(){
	int n;
	long long s=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		if(i%3!=0 && i%5!=0){
			s+=i;
		}
	}
	cout<<s;
	return 0;
}

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

#define REP(i ,n) for(int i=0 ;i < n; i++)
#define REPB(i ,n) for(int i=n; i >= 0; i--)
#define FOR(i ,m ,n) for(int i=m; i < n; i++)
#define FORB(i, m, n) for(int i=m; i>= m; i--)
#define ll long long
#define pb push_back
#define popb pop_back
using namespace std;
const int MAX_N = 100000;
const int INF = 1000000;

int n;
int h[MAX_N + 2];
int dp[MAX_N + 2];

int dprec(int i){
  int res;
  if(dp[i] != -1){
      return dp[i];
      }
     if(i < 2){
        res = 0;
      }else{
        res = min(
        dprec(i - 1) + abs(h[i] - h[i - 1]),
        dprec(i - 2) + abs(h[i] - h[i - 2])
        );
        }
      return dp[i] = res;
  }
void solve(){
    memset(dp, -1, sizeof(dp));
    cout << dprec(n+1) << endl;
  }

int main(){
  cin >> n;
  REP(c, n){
      cin >> h[c + 2];
    }
    REP(p, 2) h[p] = h[2];
    solve();
//REP(a, (n+2)) cout << dp[a] << " ";
}


Measured memory_bytes: 2560
using System;
using System.Linq;
using System.Collections.Generic;

namespace myapp
{
    class AtCoder_abc117_c
    {
        public static void Main()
        {
            IReadOnlyList<int> lineString = Console.ReadLine().Split(' ').Select(str => int.Parse(str)).ToList();
            int pieceCount = lineString[0];
            int pointCount = lineString[1];

            List<int> conditionList = Console.ReadLine().Split(' ').Select(str => int.Parse(str)).OrderBy(v => v).ToList();
            if (pointCount == 1 || pieceCount >= pointCount)
            {
                Console.WriteLine(0);
                return;
            }

            if (pieceCount == 1)
            {
                Console.WriteLine(conditionList.Last() - conditionList.First());
                return;
            }

            Dictionary<int, int> dictionary1 = new Dictionary<int, int>();
            for (int i = 0; i < conditionList.Count; i++)
            {
                int difference = 0;
                if (i > 0)
                {
                    difference = conditionList[i] - conditionList[i - 1];
                }
                dictionary1.Add(conditionList[i], difference);
            }

            pieceCount--;
            Dictionary<int, int> dictionary2 = dictionary1;
            foreach (var item in dictionary1.OrderByDescending(item => item.Value))
            {
                if (item.Value == 0)
                {
                    continue;
                }
                dictionary2[item.Key] = 0;

                pieceCount--;
                if (pieceCount == 0)
                {
                    break;
                }
            }

            Console.WriteLine(dictionary2.Sum(item => item.Value));
            return;
        }
    }
}

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

#define ms(x, y) memset(x, y, sizeof(x))
#define FOR(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define INF (int) 1e9
#define ri(x) scanf("%d", &x)
#define pi(x) printf("%d", x)
#define rii(x, y) scanf("%d%d", &x, &y)
#define pii(x, y) printf("%d%d", x, y)
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef queue<int> qi;

const int modval = 1000000007;
int rows, cols;
long long dp[1001][1001];
char graph[1001][1001];

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

    cin >> rows >> cols;
    
    FOR (i, 0, rows) {
        cin >> graph[i];
    }

    dp[0][0] = 1;

    FOR(i, 0, rows) {
        FOR (j, 0, cols) {

            dp[i][j] %= modval;

            if (graph[i + 1][j] != '#') {
                dp[i + 1][j] += dp[i][j];
            }

            if (graph[i][j + 1] != '#') {
                dp[i][j + 1] += dp[i][j]; 
            }
        }
    }

    
    printf("%lld", dp[rows - 1][cols - 1]);

    return 0;
}

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

using namespace std;

const int M = 1e9 +7;

int main(){
	int h , w; 
	cin >> h >> w;
	vector<vector<int>> dp(h, vector<int>(w,0));
	dp[0][0] = 1;
	for(int i = 0; i < h; ++i){
		for(int j = 0; j < w; ++j){
			char c; 
			cin >> c;
			if(c=='.'){
				if(j != 0)
					dp[i][j] = (dp[i][j] + dp[i][j-1]) % M;
				if(i != 0)
					dp[i][j] = (dp[i][j] + dp[i-1][j]) % M;
			}
		}
	}
	cout << dp[h-1][w-1];
			
	return 0;
}


Measured memory_bytes: 7548
#include<iostream>
#include<iomanip>
#include<cassert>
#include<stdexcept>
#include<utility>
#include<functional>
#include<numeric>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<array>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<complex>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<bitset>
#include<memory>
using namespace std;
using ll=long long;

int main(){
    int h,w;
    cin>>h>>w;
    vector<string> s(h);
    for(int i=0;i<h;i++) cin>>s[i];

    int res = max(h,w);
    vector<vector<int>> b(h-1,vector<int>(w-1));
    auto judge=[&](int i,int j){
        return (int)(s[i][j]=='#');
    };
    for(int i=0;i+1<h;i++){
        for(int j=0;j+1<w;j++){
            int cnt = judge(i,j) + judge(i+1,j) +judge(i,j+1) + judge(i+1,j+1);
            b[i][j] = (cnt%2==0);
        }  
    }

    vector<vector<int>> sum(h,vector<int>(w));
    for(int i=0;i<h-1;i++){
        for(int j=0;j<w-1;j++){
            if(b[i][j]) sum[i+1][j] = sum[i][j]+1;
        }
    }
    
    for(int i=0;i<h-1;i++){
        int x = i+1;
        stack<pair<int,int>> lh;
        lh.push({-1,0});
        for(int y=0;y<w;y++){
            while(sum[x][y]<lh.top().second){
                auto tmp = lh.top(); lh.pop();
                int height = tmp.second;
                int width = y-lh.top().first;
                res = max(res,width*(height+1));
            }
            lh.push({y,sum[x][y]});
        }
    }
    cout<<res<<endl;
    
    return 0;
}


Measured memory_bytes: 35712
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};

int main(void){
    int H,W;
    cin >> H >> W;
    char S[H][W];
    rep(i,H) cin >> S[i];
    int dp[H][W];
    rep(i,H) rep(j,W) dp[i][j]=INF;
    dp[0][0]=0;
    rep(i,H) rep(j,W){
        if(i<H-1) dp[i+1][j]=min(dp[i+1][j],dp[i][j]+((S[i][j]==S[i+1][j])?0:1));
        if(j<W-1) dp[i][j+1]=min(dp[i][j+1],dp[i][j]+((S[i][j]==S[i][j+1])?0:1));
    }
    if(S[0][0]=='#') dp[H-1][W-1]++;
    cout << (dp[H-1][W-1]+1)/2 << endl;
}

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

typedef long long ll;

using Graph = vector<vector<int>>;

vector<int> to[200005];
vector<int> ans;

void dfs(int v, int p=-1) {
    for (int u : to[v]) {
        if (u == p) continue;
        ans[u] += ans[v];
        dfs(u, v);
    }
}

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n-1; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        to[a].push_back(b);
        to[b].push_back(a);
    }

    ans.resize(n);
    for (int i = 0; i < q; i++) {
        int p, x;
        cin >> p >> x;
        p--;
        ans[p] += x;
    }

    dfs(0);

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



Measured memory_bytes: 23424
input = gets.chomp

input_num = input.length


b= (input_num - 1) / 2

input_array = input.split("")
c = b - 1
smarl_sentence = input_array[0..c]

d = smarl_sentence.join

e = (input_num + 3) / 2

f = e - 1
h = input_num - 1
smarl_sentence_2 = input_array[f..h]

g = smarl_sentence_2.join

input_reverse =  input.reverse

if input == input_reverse and d == d.reverse and g == g.reverse
    puts "Yes"
else
    puts "No"
end




Measured memory_bytes: 3836
a = gets.chomp
b = gets.chomp
c = gets.chomp
f = "a"
while (true) 
  if(f == "a")
    break if(a[0] == nil)
    f = a[0]
    a[0] = ""
  elsif(f == "b")
    break if(b[0] == nil)
    f = b[0]
    b[0] = ""
  else
    break if(c[0] == nil)
    f = c[0]
    c[0] = ""
  end
end
puts f.upcase

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

int main()
{
    int a,b,c,count=0;
    cin>>a>>b>>c;
    if(a==b)
    count++;
    if(b==c)
    count++;
    if(a==c)
    count++;
    if(count==1) 
    cout<<"Yes";
    else
    cout<<"No";
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define repp(i,l,r)for(long long i=(l);i<(r);i++)
#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define per(i,n) for (long long i = (n); i >= 0; --i)
const int INF = 2147483647;//int max
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
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; }
//ミョ(-ω- ?)
int main() {
    ll a;
    cin >> a;
    cout << a + a*a + a*a*a << endl;
    return 0;
}

Measured memory_bytes: 3636
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int[][] map = new int[8][8];
		for(int i=0;i<8;i++){
			char[] s = sc.next().toCharArray();
			for(int j=0;j<8;j++){
				if(s[j]=='x') map[i][j] = 1;
				else if(s[j]=='.') map[i][j] = 2;
			}
		}
		
		int[] p = new int[]{1,1,1,0,-1,-1,-1,0};
		int[] q = new int[]{1,0,-1,-1,-1,0,1,1};
		int cnt, max, mx, my;
		boolean flag;
		while(true){
			flag = false;
			for(int z=0;z<2;z++){
				mx = -1;
				my = -1;
				max = 0;
				for(int y=0;y<8;y++){
					for(int x=0;x<8;x++){
						if(map[y][x]==2){
							cnt = 0;
							for(int i=0;i<8;i++){
								for(int j=1;;j++){
									if(0<=x+j*p[i] && x+j*p[i]<8 && 0<=y+j*q[i] && y+j*q[i]<8){
										if(map[y+j*q[i]][x+j*p[i]]==z){
											cnt += (j-1);
											break;
										}
										else if(map[y+j*q[i]][x+j*p[i]]==2) break;
									}else{
										break;
									}
								}
							}
							if(cnt>0){
								flag = true;
								if(cnt>max-z){
									max = cnt;
									mx = x;
									my = y;
								}
							}
						}
					}
				}
				
				if(mx!=-1){
					map[my][mx] = z;
					for(int i=0;i<8;i++){
						for(int j=1;;j++){
							if(0<=mx+j*p[i] && mx+j*p[i]<8 && 0<=my+j*q[i] && my+j*q[i]<8){
								if(map[my+j*q[i]][mx+j*p[i]]==2) break;
								else if(map[my+j*q[i]][mx+j*p[i]]==z){
									for(int k=1;k<j;k++) map[my+k*q[i]][mx+k*p[i]] = z;
									break;
								}
							}else{
								break;
							}
						}
					}
				}
			}
			if(flag==false) break;
		}
		
		for(int u=0;u<8;u++){
			for(int v=0;v<8;v++){
				if(map[u][v]==0) System.out.print("o");
				else if(map[u][v]==1) System.out.print("x");
				else System.out.print(".");
			}
			System.out.println();
		}
	}	
}

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

int main() {
  int n;
  cin>>n;
  ll a[3*n];
  for(int i=0;i<3*n;i++){
    cin>>a[i];
  }
  sort(a,a+3*n);
  ll strength=0;
  for(int i=0;i<n;i++){
    strength += a[3*n-2*(i+1)];
  }
  cout<<strength<<endl;
  return 0;
}

Measured memory_bytes: 2560
using System;
class ProgramC
    {
        static void Main(string[] args)
        {
            
            //入力
            string input = Console.ReadLine();
            int x = int.Parse(input);
            int ans = 0;
            
            if(x == 3 || x == 2)
            {
                Console.WriteLine(x);
                return;
            }

            for(int i = x; i < 200000;i++)
            {
                int count = 0;
                for(int j = 2; j <= Math.Sqrt(i); j++)
                {
                    if(i % j != 0)
                        count++;
                    
                    if(count == (int)Math.Sqrt(i) - 1)
                    {
                        ans = i;
                    }
                }

                if(ans != 0)
                    break;
            }

            Console.WriteLine(ans);
        }
    }

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


int main()
{
	int a, b, t;
	cin >> a >> b >> t;

	int time = 0;
	int ans = 0;
	while (true) {
		time += a;
		if (time <= t) {
			ans += b;
		} else {
			break;
		}
	}

	cout << ans << endl;
}



Measured memory_bytes: 256
// package app;

import java.math.BigDecimal;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.Scanner;
import java.util.StringJoiner;
import java.util.stream.Stream;

public class Main {

    public static void main(final String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);

        // long N = sc.nextLong();
        // long K = sc.nextLong();
        int N = sc.nextInt();

        int[] P = new int[N];
        int[] P2 = new int[N];

        for (int i = 0; i < N; i++) {
            int tmp = sc.nextInt();
            P[i] = tmp;
            P2[i] = tmp;
        }

        Arrays.sort(P2);

        int cnt = 0;
        for (int i = 0; i < P2.length; i++) {
            if (P[i] != P2[i]) cnt++;
        }


        System.out.println(cnt <= 2 ? "YES" : "NO");
    }
}

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

int main()
{
	string str;
	cin >> str;
	int num = str.size()-3;
	if (str[0] != str[str.size()-1]) num++;
	if (num%2 == 0) cout << "Second" << endl;
	else cout << "First" << endl;
	return 0;
}

Measured memory_bytes: 512
n=int(input())
m = [[-1 for i in range(n)] for j in range(n)]
for i in range(n): #隣接の辺のコストを入力
  nums = list(map(int, input().split()))
  for j in range(n):
    m[i][j] = nums[j]

d=[0]+[10**9]*(n-1)
visited=[0]*n

while 1:
  u=-1
  for i in range(n):
    if not visited[i] and (u<0 or d[i]<d[u]):
      u = i
  if u < 0:
    break
  visited[u]=1
  for v in range(n):
    if not visited[v] and m[u][v]!=-1:
      if m[u][v]<d[v]:
        d[v]=m[u][v]

print(sum(d))


Measured memory_bytes: 5776
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define fir first
#define sec second
using namespace std;
const int MAXN = 51;
int n, m, LCA[MAXN][MAXN];
ll mi[MAXN];
vector<int>G[MAXN], son[MAXN];
pii path[MAXN];
int tag[MAXN], cnt = 0;
void dfs(int u, int fa)
{
    for (int v : G[u]) if (v != fa) dfs(v, u), tag[u] += tag[v];
    if (tag[u] > 0) cnt++;
}
ll deal(int sta)
{
    for (int i = 1; i <= n; i++) tag[i] = 0;
    for (int i = 0; i < m; i++) if ((sta >> i) & 1)
    {
        int u = path[i].fir, v = path[i].sec;
        tag[u]++; tag[v]++; tag[LCA[u][v]] -= 2;
    }
    cnt = 0; dfs(1, 0);
    int sig = 1;
    if (__builtin_popcount(sta) & 1) sig = -1;
    return mi[n - 1 - cnt] * sig;
}
void DFS(int u, int fa)
{
    son[u].push_back(u);
    for (int v : G[u]) if (v != fa) 
    {
        DFS(v, u);
        for (int sonv : son[v]) son[u].push_back(sonv);
    }
    for (int sonu : son[u]) LCA[u][sonu] = LCA[sonu][u] = u;
    for (int x : G[u]) if (x != fa)
        for (int y : G[u]) if (y != fa && x != y)
            for (int sonx : son[x])
                for (int sony : son[y])
                    LCA[sonx][sony] = u;
}
int main()
{
    mi[0] = 1; for (int i = 1; i <= 50; i++) mi[i] = mi[i - 1] * 2;
    scanf("%d", &n);
    for (int i = 1, u, v; i < n; i++) 
    {
        scanf("%d%d", &u, &v);
        G[u].push_back(v); G[v].push_back(u);
    }
    DFS(1, 0);
    // for (int i = 1; i <= n; i++)
    //     for (int j = 1; j <= n; j++)
    //         printf("%d%c", LCA[i][j], " \n"[j == n]);
    scanf("%d", &m);
    for (int i = 0; i < m; i++) scanf("%d%d", &path[i].fir, &path[i].sec);
    ll ans = 0;
    for (int sta = 0; sta < (1 << m); sta++) ans += deal(sta);
    printf("%lld\n", ans);
    return 0;
}

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

using namespace std;
typedef long long ll;

#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 INF 1e9
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((ll)(x).size())
#define SORT(x) sort((x).begin(), (x).end())
#define dump(x) cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl

int main(int argc, char const *argv[])
{
    ll n;
    cin >> n;
    string a, b, c;
    cin >> a;
    cin >> b;
    cin >> c;
    ll res = 0;
    REP(i, n)
    {
        ll d = 0;
        if (a[i] == b[i] && b[i] == c[i] && c[i] == a[i])
            ;
        else if (a[i] != b[i] && b[i] != c[i] && c[i] != a[i])
            res += 2;
        else
            res++;
    }
    cout << res << endl;
    return 0;
}


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

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

    int n;
    cin >> n;
    int x, y;
    x = n * 800;
    y = n / 15 * 200;    

    cout << x - y << endl;

    return 0;
}

Measured memory_bytes: 256
#! env/bin/local python3
# -*- coding:utf-8 -*-

# -- submit ----

# --- fetch input ---
inputs: list = []
while True:
    try:
        inputs.append(input().strip('\n'))
    except EOFError:
        break

# --- write code below ---

s, w = [int(i) for i in inputs[0].split(' ')]
print('unsafe' if s <= w else 'safe')


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

#define ll long long
const int mod = 1000000007;

int main(){

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false); 

	int x;
	cin >> x;
	if (x >= 30){
		cout << "Yes";
	} else {
		cout << "No";
	}


	
}

Measured memory_bytes: 3636
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
signed main(){
  string s;
  cin >> s;
  for(int i=0;i<s.size();i++){
    if((i%2==0&&s[i]=='L')||(i%2==1&&s[i]=='R')){
      cout <<"No\n";
      return 0;
    }
  }
      cout <<"Yes\n";
}


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

n = int(input())
given_s = input()
s = list(given_s)

nr = nw = 0 
nr = s.count('R')
nw = n-nr
ans = 0 

if nw == 0:
    print(ans)
    exit()

l = s[:nr]
ans = l.count('W')
print(ans)


Measured memory_bytes: 12024
#if 0
#endif

#include <iostream>
using namespace std;

int P[10010]; // 0 から 10000 までの頂点を取り扱い可能

void init(int N)
{ // 初期化 はじめは全ての頂点はバラバラ
    for (int i = 0; i <= N; ++i)
        P[i] = i;
    // 注: 通常は [0,N-1] または [1,N] の範囲を使うが
    // どちらでも対応できるように資料では[0,N]の範囲とした
}

int root(int a) // aのroot(代表元)を求める
{
    if (P[a] == a)
        return a;               // aはroot
    return (P[a] = root(P[a])); // aの親のrootを求め，aの親とする
}

bool is_same_set(int a, int b) // a と b が同じグループに属するか?
{
    return root(a) == root(b);
}

void unite(int a, int b) // a と b を同一グループにまとめる
{
    P[root(a)] = root(b);
}

int main()
{
    int N, Q;
    cin >> N;
    init(N);
    cin >> Q;
    for (int i = 0; i < Q; i++)
    {
        int query, x, y;
        cin >> query >> x >> y;
        if (query == 0)
        {
            // unite
            unite(x, y);
        }
        else if (query == 1)
        {
            // same
            cout << is_same_set(x, y) << endl;
        }
    }
}



Measured memory_bytes: 3168
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <numeric>
#include <limits>
using namespace std;

int main(){
    string w;
    cin >> w;
    set<char> s;
    string ans;
    if(w.size()%2!=0) ans = "No";
    else{
        int counter = 0;
        for(size_t j = 0; j < w.size(); j++)
        {
            for(size_t k = 0; k < w.size(); k++)
            {
                if(w[j] == w[k]) counter ++;
            }
            if(counter%2 == 0) ans = "Yes";
            else {
                ans = "No";
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
  int N,M;
    cin >> N >> M;
  int A = max(N,M);
    int B;
    if(A==N) B=max(N-1,M);
    else B=max(N,M-1);
      
      cout<<A+B<<endl;
}

Measured memory_bytes: 256
n=int(input())
v=list(map(int,input().split()))
v1 = [v[2*i] for i in range(n//2)]

if len(set(v))==1:
    print(n//2)
    exit()
d1 = {}
for x in v1:
    if x in d1.keys():
        d1[x] = d1[x] + 1
    else:
        d1[x] = 1
d1 = sorted(d1.items(), key=lambda x:-x[1])

d2 = {}
v2 = [v[2*i+1] for i in range(n//2)]
ma2=0
for x in v2:
    if x in d2.keys():
        d2[x] = d2[x] + 1
    else:
        d2[x] = 1
d2 = sorted(d2.items(), key=lambda x:-x[1])
if d1[0][0] != d2[0][0]:
    print(n-d1[0][1]-d2[0][1])
else:
    if len(d1) == 1:
        print(n-d1[0][1]-d2[1][1])
    elif len(d2) == 1:
        print(n-d1[1][1]-d2[0][1])
    else:
        print(n-max(d1[0][1]+d2[1][1],d1[1][1]+d2[0][1]))

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

#define MAXN 200005

using namespace std;

int n, x;
int d[MAXN << 1], h[MAXN];

int main() {
    scanf("%d%d%d", &n, &d[1], &x);
    for (int i = 2; i <= (n << 1); ++i)
        d[i] = d[i - 1] + x;
    for (int i = 1; i <= (n << 1); ++i)
        d[i] += d[i - 1];
    for (int i = 1; i <= n; ++i)
        h[i] = d[i << 1];
    long double ans = 0, sum = 0;
    for (int i = 2; i <= n; ++i)
        sum += 1.0 / i;
    for (int i = 1; i <= n; ++i) {
        ans += (0.5 + 0.25 * sum) * (h[i] - h[i - 1]);
        sum = sum + 1.0 / (i + 1) - 1.0 / (n - i + 1);
    }
    printf("%.10Lf\n", ans);
}

Measured memory_bytes: 2560
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

class Program
{
    static void Main(string[] args)
    {
        var sc = new Scanner();
        string s = sc.next();

        int ans = 0;

        for (int i = 0; i < s.Length / 2; i++)
        {
            if (s[i] != s[s.Length - 1 - i]) ans++;
        }

        Console.WriteLine(ans);
    }
}

// chokudai's Scanner
class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }

    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}


Measured memory_bytes: 13140
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
  class Main  {
     public static void main(String[]args){
         Scanner scan = new Scanner(System.in);
         int x = scan.nextInt();
         double arr[] = new double[x];
         for(int i = 0 ; i < x ;i++){
             arr[i] = scan.nextInt();
         }
         Arrays.sort(arr);
         for(int i = 0 ;i<x-1 ; i++){
             
             arr[i+1] = (arr[i] + arr[i+1])/2 ;
         }
         if(arr[arr.length-1]  - (int)arr[arr.length-1] == 0 ){
             System.out.println((int)arr[arr.length-1]);
         }else{
         System.out.println(arr[arr.length-1]);
     
         }
     }
}


Measured memory_bytes: 22868
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };

template<typename T>
T power(T x, long long n, const T &m){
    if(n == 0) return 1;
    if(n == 1) return x;
    T tmp = power(x, n/2, m);
    if(n%2 == 0) return tmp * tmp % m;
    else return tmp * tmp % m * x % m;
}

template<typename T>
T inverse(T x, T m){
    return power(x, m-2, m);
}

int N;
vector<int> e[200000];

int par[200000];
int sz[200000];
int dfs(int n, int p){
    par[n] = p;
    sz[n] = 1;
    rep(i, e[n].size()){
        if(e[n][i] == p) continue;
        sz[n] += dfs(e[n][i], n);
    }
    return sz[n];
}

// n 個の頂点のうち少なくとも 1 つが黒である確率
// 余事象：n 個の頂点すべてが白である確率
ll calc1(int n){
    ll yo = 1LL*inverse(power(2LL, n, MOD), MOD);
    return (1LL-yo+MOD)%MOD;
}

// 各部分木に黒が存在する確率が v[i] であるとき，
// 部分木のうち少なくとも 2 つに黒が存在する確率
// 余事象：1 つも黒が存在しない or 1 つの部分木だけに存在する
ll calc2(vector<ll> v){
    ll product = 1;
    rep(i, v.size()){
        product *= (1-v[i]+MOD)%MOD;
        product %= MOD;
    }
    ll yo = product; //全部が黒である確率
    rep(i, v.size()){
        yo += product * inverse((1-v[i]+MOD)%MOD, MOD)%MOD * v[i]%MOD;
        yo %= MOD;
    }
    return (1LL-yo+MOD)%MOD;
}

signed main(){
    cin >> N;
    rep(i, N-1){
        int a, b;
        cin >> a >> b;
        a--; b--;
        e[a].pb(b);
        e[b].pb(a);
    }

    dfs(0, -1);
    ll ans = 0;
    rep(i, N){ // 頂点 i が穴あきになる期待値を求める
        vector<ll> v;
        if(par[i] != -1) v.pb(N-sz[i]);
        rep(j, e[i].size()){
            if(e[i][j] == par[i]) continue;
            v.pb(sz[e[i][j]]);
        }
        //rep(j, v.size()) cout << v[j] << " ";
        //cout << endl;
        rep(j, v.size()) v[j] = calc1(v[j]);
        //rep(j, v.size()) cout << v[j] << " ";
        //cout << endl;
        ans += calc2(v) * inverse(2LL, MOD)%MOD;
        //cout << calc2(v) * inverse(2LL, MOD)%MOD << endl;
        ans %= MOD;
    }
    cout << ans << endl;
}

Measured memory_bytes: 25472
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p


p = 10 ** 9 + 7
N = 2 * 10 ** 5  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

n, k = map(int, input().split())
ans = 0
k = min(k, n - 1)
for i in range(k+1):
    ans += cmb(n, i, p) * cmb(n - 1, i, p)
    ans %= p
print(ans % p)

Measured memory_bytes: 81008
#include <bits/stdc++.h>
#define lsb(x) ((x) & (-x))
using namespace std;

const int NMAX = 20010;
int aib[2][NMAX + 10];

void update(int c, int poz, int val)
{
    while (poz <= NMAX && poz) {
        aib[c][poz] += val;
        poz += lsb(poz);
    }
}

int query(int c, int poz)
{
    int ans(0);
    while (poz) {
        ans += aib[c][poz];
        poz -= lsb(poz);
    }
    return ans;
}

void get_querys()
{
    for (int c(0); c <= 1; c++)
        for (int i(NMAX); i >= 1; i--)
            aib[c][i - lsb(i)] += aib[c][i];
}


int pozinperm[NMAX + 10];

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


    for (int i(1); i <= n; i++) {
        cin >> c;
        pozinperm[i] = c;
    }

    for (int i(n - 1), add(1); i >= 1; i--, add++) {
        update(0, pozinperm[i] + 1, add);
        update(1, 1, add);
        update(1, pozinperm[i], -add);
    }

    ///get_querys();

    for (int i(1); i <= n; i++)
        cout << query(0, i) + i << ' ';///aib[0][i] << ' ';
    cout << '\n';
    for (int i(1); i <= n; i++)
        cout << query(1, i) + n - i + 1 << ' ';///cout << aib[1][i] << ' ';

    return 0;
}


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

using namespace std;

using ll = long long;
using ld = long double;
using vi = vector<ll>;
using vvi = vector<vi>;

#define all(a) a.begin(), a.end()
#define mp make_pair
#define pb push_back

void solve() {
    ll n; cin >> n;
    map<string, ll> cnt;
    for (int i = 0; i < n; i++) {
        string t; cin >> t;
        cnt[t]++;
    }
    cout << "AC x " << cnt["AC"] << "\n";
    cout << "WA x " << cnt["WA"] << "\n";
    cout << "TLE x " << cnt["TLE"] << "\n";
    cout << "RE x " << cnt["RE"] << "\n";
}

int main() {
    solve();
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
typedef long long ll;

int main(){
    int a,b,c,d;
    cin>>a>>b>>c;
    d=a+b+c;
    if(d>=22){
        cout<<"bust";
    }else{
        cout<<"win";
    }
    return 0;
}


Measured memory_bytes: 256
def therefore(N: int)->str:
    if (N % 10) in [2, 4, 5, 7, 9]:
        return 'hon'
    if (N % 10) in [0, 1, 6, 8]:
        return 'pon'
    return 'bon'


if __name__ == "__main__":
    N = int(input())
    ans = therefore(N)
    print(ans)


Measured memory_bytes: 9176
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(10)

using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    cin >> N;
    vector<int> A(N);
    REP(i, N) cin >> A[i];

    int prev = -1;
    int ans = 0;
    int cur = 0;
    REP(i, A.size()) {
        if (prev == -1) {
            prev = A[i];
            continue;
        }
        int diff = A[i] - prev;
        if (diff == 0) continue;

        if ((cur > 0 && diff < 0) || (cur < 0 && diff > 0)) {
            ans++;
            cur = 0;
            prev = A[i];
            continue;
        }
        cur = diff;
        prev = A[i];
    }
    cout << ans + 1 << endl;
    return 0;
}


Measured memory_bytes: 1024
N,M=map(int,input().split())
S={1}
C=[1] * (N+1)
for _ in range(M):
    a,b=map(int,input().split())
    if a in S:
        S.add(b)
        if C[a] == 1:
            S.remove(a)
    C[b] += 1
    C[a] -= 1
print(len(S))

Measured memory_bytes: 12780
#include<bits/stdc++.h>
// Begin Header {{{
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i,n) for(ll i=0; i<n; i++)
#define loop(i, j, n) for(ll i=j; i<n; i++)
#define all(x) (x).begin(), (x).end()
constexpr int INF  = 0x3f3f3f3f;
const long long mod=1e9+7;
const long double PI = acos(-1);
// }}} End Header

int main() {
	int a, b;
	char t;
	cin >> a >> t >> b;
	if(t == '+'){
		cout << a+b << endl;
	}else{
		cout << a-b << endl;
	}
 	return 0;
}

Measured memory_bytes: 256
S = input()
numofzero = 0
numofone = 0
N = len(S)
for i in range(N):
    if S[i] == "0":
        numofzero += 1
    else:
        numofone += 1
if numofone > numofzero:
    print(numofzero*2)
else:
    print(numofone*2)


Measured memory_bytes: 3188
from math import gcd

from math import factorial as f

from math import ceil,floor,sqrt


import bisect
import re
import heapq


from copy import deepcopy
import itertools

from sys import exit

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

yes = "Yes"
no = "No"

def main():
    a,b,c,d = mi()
    while True:
        c-=b
        a-=d
        if c<=0:
            print(yes)
            exit()
        if a<=0:
            print(no)
            exit()




main()




Measured memory_bytes: 10024
N = gets.chomp.to_i
arrA = gets.chomp.split.map(&:to_i)

h = {}
arrA.each do |i|
    h[i].nil? ? h[i] = 1 : h[i] += 1
end

for i in (1..N) do
    if h.has_key?(i) then
        puts h[i]
    else
        puts 0
    end
end

Measured memory_bytes: 40988