akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cstring>
using namespace std;

const int MAX_K = 1e6, MAX_N = 1e6, MOD = 1e9 + 7;
int k;
char s[MAX_N + 1];
int pow26[MAX_K + 1];

int po(int x, int y) {
    int ans = 1;
    while (y > 0) {
        if (y & 1) ans = static_cast<long>(ans) * x % MOD;
        x = static_cast<long>(x) * x % MOD;
        y >>= 1;
    }
    return ans;
}

int fac[MAX_N + MAX_K], inv[MAX_N + MAX_K];

int main() {
    scanf("%d", &k);
    scanf("%s", s);
    int n = strlen(s);

    fac[0] = 1;
    for (int i = 1; i <= n + k - 1; i++) {
        fac[i] = static_cast<long>(fac[i - 1]) * i % MOD;
    }
    inv[n + k - 1] = po(fac[n + k - 1], MOD - 2);
    for (int i = n + k - 2; i >= 0; i--) {
        inv[i] = static_cast<long>(inv[i + 1]) * (i + 1) % MOD;
    }
    pow26[0] = 1;
    for (int i = 1; i <= k; i++) {
        pow26[i] = static_cast<long>(pow26[i - 1]) * 26 % MOD;
    }

    int ans = 0;
    for (int i = 0, pow25 = 1; i <= k; i++) {
        int temp = static_cast<long>(fac[n + i - 1]) * inv[n - 1] % MOD
                 * inv[i] % MOD * pow25 % MOD * pow26[k - i] % MOD;
        ans = (ans + temp) % MOD;
        pow25 = static_cast<long>(pow25) * 25 % MOD;
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 22184
<?php

list($n, $k) = explode(' ', trim(fgets(STDIN)));

$children = range(1, $n);
$have_treat = [];
for ($i = 1; $i <= $k; ++$i) {
    list($d) = explode(' ', trim(fgets(STDIN)));
    $have_treat = array_merge($have_treat, explode(' ', trim(fgets(STDIN))));
}
$have_treat = array_unique($have_treat);

echo count(array_diff($children, $have_treat));


Measured memory_bytes: 17356
import java.util.Scanner;
//import java.io.*;
//import java.util.Arrays;
public class Main {
	public static void main(String[] args) throws java.io.IOException {
		Scanner scan = new Scanner(System.in);
		//InputStreamReader is = new InputStreamReader(System.in);
		//BufferedReader br = new BufferedReader(is);
		int t = scan.nextInt();
		while(t != 0){
			int n = scan.nextInt();
			int sum = 0;
			int s;
			int f;
			for(int i = 0 ; i < n ; i++){
				s = scan.nextInt();
				f = scan.nextInt();
				sum += (f-s);
			}
			if(sum >= t){
				System.out.println("OK");
			}else{
				System.out.println(t-sum);
			}
			t = scan.nextInt();
		}
	}
}

Measured memory_bytes: 31928
INF = float('inf')
N, W = map(int, input().split())

# dp[i][j] : i番目までの品物を使い、価値がjとなるときの重さ
dp = [[INF] * 100010 for _ in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(100010):
        if j >= v:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v] + w)
        else:
            dp[i][j] = dp[i - 1][j]

ans = 0
for i in range(100010):
    if dp[N][i] <= W:
        ans = max(ans, i)

print(ans)


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

int n,a[100010];

int main(){
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	int ans=1,t=-1;
	for(int i=1;i<n;i++){
		if(t==-1){
			if(a[i-1]>a[i])t=1;
			if(a[i-1]<a[i])t=0;
		}
		if(t==1){
			if(a[i-1]<a[i])ans++,t=-1;
		}
		if(t==0){
			if(a[i-1]>a[i])ans++,t=-1;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <algorithm>
#include <ctime>
#include <vector>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;

#define PI 3.14159265358979323846264338327950L

int res;

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

    string s;
    cin >> s;
    int tmp = 0;
    for (int i = 0; i < s.length(); i++)
    {

        if (s[i] == 'S')
        {
            tmp = 0;
        }
        else
        {
            tmp++;
            if (res < tmp)
            {
                res = tmp;
            }
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3648
#[test]
fn test_solve() {
    assert_eq!(
        solve("5\n1 2 1\n1 3 1\n2 4 1\n3 5 1\n3 1\n2 4\n2 3\n4 5\n"),
        "3\n2\n4\n"
    );
    assert_eq!(
        solve("7\n1 2 1\n1 3 3\n1 4 5\n1 5 7\n1 6 9\n1 7 11\n3 2\n1 3\n4 5\n6 7\n"),
        "5\n14\n22\n"
    );
    assert_eq!(solve("10\n1 2 1000000000\n2 3 1000000000\n3 4 1000000000\n4 5 1000000000\n5 6 1000000000\n6 7 1000000000\n7 8 1000000000\n8 9 1000000000\n9 10 1000000000\n1 1\n9 10\n"), "17000000000\n");
}

fn solve(src: &str) -> String {
    let mut sc = Scanner::from_str(src);

    let n: usize = sc.read();
    let mut nbr = vec![Vec::new(); n];
    for _ in 0..n - 1 {
        let a: usize = sc.read();
        let b: usize = sc.read();
        let c: usize = sc.read();
        nbr[a - 1].push((b - 1, c));
        nbr[b - 1].push((a - 1, c));
    }
    let q: usize = sc.read();
    let k: usize = sc.read();
    let sdf = shortest_dists_from(k - 1, &nbr);

    let mut ret = String::new();
    use std::fmt::Write;
    for _ in 0..q {
        let x: usize = sc.read();
        let y: usize = sc.read();
        writeln!(&mut ret, "{}", sdf[x - 1] + sdf[y - 1]).unwrap();
    }
    ret
}

#[derive(PartialEq, Eq, Debug)]
struct Rev<T>(T);
impl<T: PartialOrd> PartialOrd for Rev<T> {
    fn partial_cmp(&self, other: &Rev<T>) -> Option<std::cmp::Ordering> {
        other.0.partial_cmp(&self.0)
    }
}
impl<T: Ord> Ord for Rev<T> {
    fn cmp(&self, other: &Rev<T>) -> std::cmp::Ordering {
        other.0.cmp(&self.0)
    }
}
fn shortest_dists_from(start: usize, neighbor: &[Vec<(usize, usize)>]) -> Vec<usize> {
    use std::collections::BinaryHeap;
    use std::iter::FromIterator;
    let n = neighbor.len();
    let mut dist = vec![usize::max_value() / 2; n];
    dist[start] = 0;
    let mut que: BinaryHeap<_> = FromIterator::from_iter(dist.iter().map(|&d| Rev(d)).zip(0..n));
    while let Some((Rev(d), u)) = que.pop() {
        for &(v, l) in &neighbor[u] {
            let alt = d + l;
            if dist[v] > alt {
                dist[v] = alt;
                que.push((Rev(alt), v));
            }
        }
    }
    dist
}

fn main() {
    let mut buf = String::new();
    use std::io;
    use std::io::{Read, Write};
    io::stdin().read_to_string(&mut buf).unwrap();
    io::stdout().write_all(solve(&buf).as_bytes()).unwrap();
}

struct Scanner<'a>(std::str::SplitWhitespace<'a>);
impl<'a> Scanner<'a> {
    fn from_str(src: &str) -> Scanner {
        Scanner(src.split_whitespace())
    }
    fn get(&mut self) -> &str {
        self.0.next().unwrap()
    }
    fn read<T: std::str::FromStr>(&mut self) -> T {
        self.get().parse().ok().unwrap()
    }
}


Measured memory_bytes: 26804
#include <stdio.h>
#include <string.h>
int main(void){
    // Your code here!
    char s[100001];
    gets(s);
    
    
    for(int i=0;i<strlen(s);i++){
        
        if(strncmp(s+i,"dreamer",7)==0 && s[i+7]!='a'){
            i+=6;
        }else if(strncmp(s+i,"dream",5)==0){
            i+=4;
        }else if(strncmp(s+i,"eraser",6)==0  && s[i+6]!='a'){
            i+=5;
        }else if(strncmp(s+i,"erase",5)==0){
            i+=4;
        }else{
            printf("NO\n");
            return 0;
            break;
        }
        
        
    }
    printf("YES\n");
    return 0;
}


Measured memory_bytes: 1628
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ll long long int
#define INF INT_MAX
#define mod
#define chutiyaap ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
bool sortbysec(const pair<ll,ll> &a,const pair<ll,ll> &b){return (a.second < b.second);}
ll gcd(ll a, ll b){if(a==0)return b;return gcd(b % a, a);}
int main()
{
	chutiyaap;
	ll n,m;cin>>n>>m;
	ll vis[51]={0};
	for(ll i=0;i<n;i++)
	{
		ll k;cin>>k;
		ll a[k+1];
		for(ll i=0;i<k;i++)
		{
			cin>>a[i];
			vis[a[i]]++;
		}
	}
	ll res=0;
	for(ll i=0;i<51;i++)if(vis[i]==n)res++;
	cout<<res;
	
}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
using namespace std;
using ll = long long;

int n, l[10];
int main() {
	scanf("%d", &n);
	int sum = 0, maxl = 0;
	for (int i = 0; i < n; i++) {
		scanf("%d", l + i);
		sum += l[i];
		maxl = max(maxl, l[i]);
	}
	printf(maxl < (sum - maxl) ? "Yes\n" : "No\n");
}

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

// ソルバー
class Abc140a {
    public:
    int solve(int n);
};

int Abc140a::solve(int n) {
    return n*n*n;
}

// 実行
int main () {
    int n;
    std::cin >> n;
    Abc140a p;
    std::cout << p.solve(n) << std::endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
using ll = long long;

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

    if (a > b) swap(a, b);

    for (int i = 0; i < b; i++) {
        cout << a;
    }
    cout << endl;

    return 0;
}

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

int main(int argc, const char * argv[]) {
    // insert code here...
    int A, B;
    cin >> A >> B;
    
    if (A + B < 24) cout << A + B << endl;
    else cout << A + B - 24 << endl;
    
    return 0;
}


Measured memory_bytes: 256
/******************************************
* AUTHOR : Ashish Joshi* 
* INSTITUTION : NIT Hamirpur *
******************************************/
#include <bits/stdc++.h>
using namespace std;

#define N 100005
#define MOD 1000000007
#define PI 3.141592653589793

#define dd double
#define loop(i, n) for(int i = 0; i < n; i++)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep1(i,b) for(int i=1;i<=b;i++)
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
#define set(b,i) (b|(1<<i))
#define unset(b,i) (b&!(1<<i))
#define cbit(b,i) bool(b&(1<<i))

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<pair<long long,long long> > vpll;
typedef vector<vector<ll> > vvll;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//ios_base& scientific (ios_base& str);
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++){
	if(a[i]%2==0){
		if(a[i]%3!=0 && a[i]%5!=0)
		{
			cout<<"DENIED";
			return 0;
		}
	}
}
cout<<"APPROVED";

return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
long long a, b, n;
long long func(long long x) {
    x = min(n, x / b * b + b - 1);
    return (a*x)/b - a*(x/b);
}
double ts(double start, double end){
    double l = start, r = end;
    for(int i = 0; i < 200; ++i) {
      long long l1 = (l*2+r)/3;
      long long l2 = (l+2*r)/3;
      long long f1 = func(l1);
      long long f2 = func(l2);
      if(f1 > f2)r = l2;
      else if(f2 > f1)l = l1;
      else r = l2, l = l1;
    }
    return max(func(l), func(r));
}
void solve() {
    cin >> a >> b >> n;
    cout << ts(0, n);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tc = 1;
  // cin >> tc;
  for(int i = 1; i <= tc; ++i) {
    // cout << "Case #" << i <<": ";
    solve();
  }
  return 0;
}

Measured memory_bytes: 3716
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define pb push_back 
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)

int main(int argc, char** argv) {
	string s;
	string t;
	cin>>s>>t;
	int ans=0;
	rep(i,0,s.length()-1)
	{
		if(s[i]!=t[i])ans++;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 3916
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define rrep(i, a, n) for (int i = (int)(a); i >= (int)(n); --i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) \
  rep(f, 0, (x.size() - 1)) cerr << x[f] << (f == (x.size() - 1) ? "\n" : " ")
#define debug2(x, y)                       \
  cerr << "(" << #x << "," << #y << ") = " \
       << "(" << x << "," << y << ")\n"
#define all(x) x.begin(), x.end()
#define each(a, x) for (auto& a : (x))
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define int long long
#define yn(x) puts((x ? "Yes" : "No"))
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
const int MX = 1e5 + 5, INF = 5LL << 57, MOD = 1e9 + 7;

int N, M;
string S;
vi va, vb;

void input() {
  ;
  cin>>N;
  bool ans=false;
  while(N){
    if (N%10 == 7) ans=true;
    N/=10;
  }
  yn(ans);
  ;
}
void solve() {
  ;
  ;
}
signed main() {
  cout << setprecision(12);
  input();
  solve();
  return 0;
}

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

su=sum(A)
cnt=1
for i in range(N-1,0,-1):
    if (su-A[i])*2<A[i]:
        break
    else:
        cnt+=1
        su=su-A[i]

print(cnt)

Measured memory_bytes: 14304
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int cnt = 1;
    int a,b;
    cin >> a >> b;
    if(b == 0)cout << a << endl;
    else{
        vector<int> v(400);
        for(int i=0;i<400;i++)v[i] = -150+i;
        for(int i=0;i<b;i++){
            int c;
            cin >> c;
            v[150+c] = -700;
        }
        if(v[150+a] == a)cout << a << endl;
        else{
            while(true){
                if(v[150+a-cnt] == a-cnt){
                    cout << a-cnt << endl;
                   break;
                }
                if(v[150+a+cnt] == a+cnt){
                    cout << a+cnt << endl;
                    break;
                }
                cnt++;
            }
        }
            
    }
}


Measured memory_bytes: 3616
#include<bits/stdc++.h>
#include<cmath>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
typedef long long ll;
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(ll i=num, i##_len=(n); i<i##_len; ++i)
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; }
#define print(x) cout << (x) << endl;
#define pb push_back
#define mp make_pair
#define sz(x) int(x.size())
 
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int INF = 1e9;
const ll LLINF = 1e16;

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}
 
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};



int main(void){
    cout.tie(0);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    int a,b,c;
    cin >> a >> b >> c;
    if(a + b + c >= 22) {
      print("bust");
    }else{
      print("win");
    }

}


Measured memory_bytes: 256
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const int mod = 998244353;
int mult(int a, int b) {
    return (1LL * a * b) % mod;
}
int sum(int a, int b) {
    int s = a + b;
    if (s >= mod) s -= mod;
    return s;
}
int sub(int a, int b) {
    int s = a - b;
    if (s < 0) s += mod;
    return s;
}
const int maxN = 3005;
int dp[maxN][maxN];
int A, B, C, D;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.txt", "r", stdin);
    cin >> A >> B >> C >> D;
    dp[A][B] = 1;
    for (int i = A; i <= C; i++) {
        for (int j = B; j <= D; j++) {
            if (i == A && j == B) continue;
            if (i > A) dp[i][j] = sum(dp[i][j], mult(dp[i - 1][j], j));
            if (j > B) dp[i][j] = sum(dp[i][j], mult(dp[i][j - 1], i));
            dp[i][j] = sub(dp[i][j], mult(dp[i - 1][j - 1], mult(i - 1, j - 1)));
        }
    }
    cout << dp[C][D];
    return 0;
}

Measured memory_bytes: 38748
import sys

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


def main():
    s = input()
    t = ""

    for c in s:
        if c != "x":
            t += c

    lt = len(t)
    lh = lt // 2
    tf = t[:lh]
    ts = t[lt-lh:][::-1]

    if tf == ts:
        cnt_end = lh + 1

        cnt = 0
        xf = []
        cur = 0
        for c in s:
            if c != "x":
                xf.append(cur)
                cur = 0
                cnt += 1
                if cnt == cnt_end:
                    break
            else:
                cur += 1

        cnt = 0
        xs = []
        cur = 0
        for c in s[::-1]:
            if c != "x":
                xs.append(cur)
                cur = 0
                cnt += 1
                if cnt == cnt_end:
                    break
            else:
                cur += 1

        ans = 0
        for x1, x2 in zip(xf, xs):
            ans += abs(x1 - x2)

        print(ans)
    else:
        print(-1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 97452
n=int(input())
ans=[]
for i in range(n-1):
  if i%2:
    ans+=[(i,0)]
for i in range(n-1):
  if i%6==1:
    for j in range(2,n):
      if j%2==0:
        ans+=[(i,j)]
  if i%6==4:
    for j in range(n):
      if j%2:
        ans+=[(i,j)]
for j in range(n):
  if(n-1+j)%2:
    ans+=[(n-1,j)]
print(len(ans))
for x,y in ans:
  print(x,y)

Measured memory_bytes: 20648
import java.util.*;
import static java.util.Arrays.*;
import static java.lang.Math.*;

public class Main {

	static Scanner sc = new Scanner(System.in);
	static int N, M;
	static int[][][] flr = new int[100][100][2];
	static boolean read() {
		N = sc.nextInt();
		if (N == 0) return false;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				flr[i][j][0] = sc.nextInt();
				flr[i][j][1] = sc.nextInt();
			}
		}
		
		return true;
	}

	static int[][] step = new int[100][100];
	static int sol;
	static void solve() {
		sol = 0;
		for (int i = 0; i < N; i++) fill(step[i], -1);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				rec(j, i, i * N + j);
			}
		}
		System.out.println(sol);
	}
	
	static void rec(int x, int y, int s) {
		if (step[y][x] == s) {
			sol++;
		} else if (step[y][x] == -1) {
			step[y][x] = s;
			rec(flr[y][x][0], flr[y][x][1], s);
		}
	}
	
	public static void main(String[] args) {
		while (read())
			solve();
	}
}

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

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

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

template<typename T> class BinaryIndexedTree {
  private:
    int S;
    std::vector<T> v;
  public:
    BinaryIndexedTree<T> (int _S) {
      S = _S;
      v.resize(S+1);
    }
    void update(int i, T k) {
      for(i++; i <= S; i += i&-i) v[i] = v[i] + k;
    }
    T read(int i) {
      T sum = 0;
      for(i++; i; i -= i&-i)  sum = sum + v[i];
      return sum;
    }
    T read(int l, int r) {
      return read(r) - read(l-1);
    }
};

int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  int n, q; std::cin >> n >> q;
  std::vector<int> c(n); rep(i,n) std::cin >> c[i];

  std::vector<std::vector<int>> ps(n);
  std::unordered_map<int,int> idx;
  for(int i=n-1; i>=0; i--) {
    if (idx.count(c[i]) != 0 ) {
      ps[i].push_back(idx[c[i]]);
    }
    idx[c[i]] = i;
  }

  std::vector<std::vector<std::pair<int,int>>> Query(n);
  rep(i,q) {
    int l, r; std::cin >> l >> r;
    l--, r--;
    Query[l].emplace_back(r,i);
  }

  BinaryIndexedTree<int> bit(n+1);
  std::vector<int> ans(q);
  for(int x=n-1; x>=0; x--) {
    for(auto&& p : ps[x]) bit.update(p,1);
    for(auto&& q : Query[x]) {
      int r = q.first;
      int i = q.second;
      ans[i] = r - x + 1 - bit.read(x,r);
    }
  }
  for(auto&& a : ans) std::cout << a << std::endl;

  return 0;
}



Measured memory_bytes: 62700
using System;

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

            int index = 0;
            int k = 0;
            string sub = string.Empty;
            while (index < s.Length)
            {
                if (sub.Equals(s.Substring(index, 1)))
                {
                    if (index + 2 <= s.Length)
                    {
                        sub = s.Substring(index, 2);
                        index += 2;
                        k++;
                    }
                    else
                    {
                        index += 1;
                    }
                }
                else
                {
                    sub = s.Substring(index, 1);    
                    index += 1;
                    k++;
                }
            }

            Console.WriteLine(k);
        }
    }


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

#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'
#define rep(i,n) for(int_fast32_t i = 0; i < ((int_fast32_t)(n)); i++)   // 0-indexed up
#define rep1(i,n) for(int_fast32_t i = 1; i <= ((int_fast32_t)(n)); i++) // 1-indexed up
#define rrep(i,n) for(int_fast32_t i = ((int_fast32_t)(n)-1); i >= 0; i--)  // 0-indexed down
#define rrep1(i,n) for(int_fast32_t i = ((int_fast32_t)(n)); i >= 1; i--)   // 1-indexed down
#define all(x) (x).begin(),(x).end()

using namespace std;

template<typename T>
using vec = vector<T>;
using i32 = int_fast32_t;
using i64 = int_fast64_t;
using u32 = uint_fast32_t;
using u64 = uint_fast64_t;
using ll = long long;
using ld = long double;
using vi = vec<int_fast32_t>;
using vl = vec<int_fast64_t>;
using vld = vec<ld>;
using vii = vec<vi>;
using PII = pair<int_fast32_t, int_fast32_t>;

template<class T>
using maxheap = std::priority_queue<T>;
template<class T>
using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template<class T,class U> inline bool chmax(T &a, const U &b){if(a<b){a=b;return 1;}return 0;}
template<class T,class U> inline bool chmin(T &a, const U &b){if(a>b){a=b;return 1;}return 0;}

const ld Pi = std::acos(-1.0L);
constexpr ll infll = (1LL<<62)-1;
constexpr int inf = (1<<30)-1;
const int mod = 1000000007;
// const int mod = 998244353;


/*FUNCs=================================================*/


/*MAIN==================================================*/
signed main(){
    double START_TIME = clock();
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
//    cout << fixed << setprecision(15);


    // Point
    // A[i]をx個取って得られる総和がx(mod k)であるとは、
    // 仮に同じA[i]-1をx個取ってきたときに総和が x - x = 0 (mod k) になるということである
    // つまり、A[i]-1の累積和をmod kで取って、
    // それをもとに部分和が0になるものを探せばよい
    // これは区間の両端の一致と同値なのでそれを数える
    // ここで注意しなければいけないのは区間の長さはkを越えないことである。
    // でなければ"mod kで"一致するということに反する
    // ...fin

    i32 n,k; cin >> n >> k;
    vl a(n); rep(i,n) cin >> a[i];
    for(auto &aa : a) --aa;
    vl csum(n+1); rep(i,n) csum[i+1] = (csum[i] + a[i]) % k;

    i64 ans = 0;
    map<i64, i32> mp;  // mp[i] := 先頭からの累積和が i (mod k) になるものの個数
    mp[0] = 1;
    for(i32 i = 0; i < n; ++i) {  // 右端として選ぶAiの添え字をiとしてこれを線形探索
        if(i+1-k >= 0) {
            mp[csum[i+1-k]]--;  // 区間外のデータを削除
        }
        ans += mp[csum[i+1]];  // 区間内のAのうちi番目のAと先頭からの累積和が一致するものの個数
        mp[csum[i+1]]++;  // つぎのイテレーションでは自分も区間内の一つになる
    }

    cout << ans << '\n';

//     printf("ElapsedTime: %5.3f ms\n",1000*((clock()-START_TIME)/CLOCKS_PER_SEC));
}


Measured memory_bytes: 18712
package main

import "fmt"

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

func main() {
	var s int
	fmt.Scan(&s)
	memo := make([]bool, 10000000)
	i := 1
	for {
		if memo[s] {
			break
		}
		memo[s] = true
		i++
		s = f(s)
	}
	fmt.Println(i)
}


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

int main(int argc, const char * argv[]) {
    
    int a,b;
    cin >> a >> b;
    
    if(a<b){
        cout << "a < b" << endl;
    }
    else if(a>b){
        cout << "a > b" << endl;
    }
    else{
        cout << "a == b" << endl;
    }

    return 0;
}

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

using namespace std;

int main(){
	int N;
  	cin >> N;
  	vector<int> V(N);
  	vector<int> C(N);
  for(int i=0; i<N; i++)
    cin >> V[i];
  for(int i=0; i<N; i++)
    cin >> C[i];
  
  int max=0;
  for(int i=0; i<N; i++){
  	if(V[i] - C[i] > 0)
      max += V[i] - C[i];
  }
  cout << max << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){

  int k,s;
  scanf("%d %d", &k, &s);
  int count = 0;
  int z;
  for (int x = 0; x <= k; x++) {
    for (int y = 0; y <= k; y++) {
      z = s-x-y;
      if (z >= 0 && z <= k) {
        count++;
      }
    }
  }
  printf("%d\n", count);

  return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int W = sc.nextInt();
		int H = sc.nextInt();
		int N = sc.nextInt();
		int[][] xya = new int[N][3];
		for (int i = 0; i < N; i++) {
			int[] temp = new int[3];
			temp[0] = sc.nextInt();
			temp[1] = sc.nextInt();
			temp[2] = sc.nextInt();
			xya[i] = temp;
		}
		int[][] M = new int[H][W];
		for (int i = 0; i < N; i++) {
			if (xya[i][2] == 1) {
				for (int y = 0; y < H; y++) {
					for (int x = 0; x < xya[i][0]; x++) {
						M[y][x] = 1;
					}
				}
			} else if (xya[i][2] == 2) {
				for (int y = 0; y < H; y++) {
					for (int x = xya[i][0]; x < W; x++) {
						M[y][x] = 1;
					}
				}
			} else if (xya[i][2] == 3) {
				for (int y = H - 1; y > H - 1 - xya[i][1]; y--) {
					for (int x = 0; x < W; x++) {
						M[y][x] = 1;
					}
				}
			} else if (xya[i][2] == 4) {
				for (int y = 0; y < H - xya[i][1]; y++) {
					for (int x = 0; x < W; x++) {
						M[y][x] = 1;
					}
				}
			}
		}
		int ret = 0;
		for (int y = 0; y < H; y++) {
			for (int x = 0; x < W; x++) {
				ret += M[y][x];
			}
		}
		System.out.println(W * H - ret);
	}
}

Measured memory_bytes: 23380
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
int main() {
  int n;
  string s;
  cin >> n >> s;
  bool ans = true;
  if(s.size() % 2 != 0) ans = false;
  rep(i,n/2){
    if(s.at(i) != s.at(n/2+i)) ans = false;
  }
  puts(ans ? "Yes":"No");
  }


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <tuple>
using namespace std;
int main(){
    int N, M, L;
    cin >> N >> M >> L;
    long long INF = 1e18;
    vector<vector<long long>> d(N, vector<long long> (N, INF));
    for(int i = 0; i < N; i++) d[i][i] = 0;
    for(int i = 0; i < M; i++){
        int a, b;
        long long c;
        cin >> a >> b >> c;
        a--;
        b--;
        d[a][b] = c;
        d[b][a] = c;
    }
    for(int k = 0; k < N; k++){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
    vector<vector<long long>> cnt(N, vector<long long> (N, INF));
    for(int i = 0; i < N; i++) cnt[i][i] = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(d[i][j] <= L) cnt[i][j] = 1;
        }
    }
    for(int k = 0; k < N; k++){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++) cnt[i][j] = min(cnt[i][j], cnt[i][k] + cnt[k][j]);
        }
    }
    int Q;
    cin >> Q;
    for(int i = 0; i < Q; i++){
        int s, t;
        cin >> s >> t;
        s--;
        t--;
        if(cnt[s][t] == INF) cout << -1 << endl;
        else cout << cnt[s][t] - 1 << endl;
    }
}

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

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  auto s2i = [](string s) {
    int res = 0;
    for (int i = 0; i < (int)s.size(); ++i) {
      if (s[i] == 'm') {
        res += (i and isdigit(s[i - 1]) ? s[i - 1] - '0' : 1) * 1000;
      }
      if (s[i] == 'c') {
        res += (i and isdigit(s[i - 1]) ? s[i - 1] - '0' : 1) * 100;
      }
      if (s[i] == 'x') {
        res += (i and isdigit(s[i - 1]) ? s[i - 1] - '0' : 1) * 10;
      }
      if (s[i] == 'i') {
        res += (i and isdigit(s[i - 1]) ? s[i - 1] - '0' : 1) * 1;
      }
    }
    return res;
  };
  int n;
  cin >> n;
  while (n--) {
    string s, t;
    cin >> s >> t;
    int x = s2i(s) + s2i(t);
    if (x >= 1000) {
      if (x >= 2000) {
        cout << x / 1000;
      }
      cout << 'm';
    }
    x %= 1000;
    if (x >= 100) {
      if (x >= 200) {
        cout << x / 100;
      }
      cout << 'c';
    }
    x %= 100;
    if (x >= 10) {
      if (x >= 20) {
        cout << x / 10;
      }
      cout << 'x';
    }
    x %= 10;
    if (x >= 1) {
      if (x >= 2) {
        cout << x / 1;
      }
      cout << 'i';
    }
    cout << '\n';
  }
}



Measured memory_bytes: 3040
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>

constexpr int INF = 1 << 16;

struct Edge {
    int start;
    int cost = INF;
    std::vector<int> to;
    std::unordered_map<int, int> time;
};

bool operator>(const Edge& lhs, const Edge& rhs)
{
    return lhs.cost > rhs.cost;
}

bool operator<(const Edge& lhs, const Edge& rhs)
{
    return lhs.cost < rhs.cost;
}

std::vector<Edge> makeEdgeFromData(int data_num, int& max_city);

int calcMinimumTimeToAllCitys(int start_city, int max_city,
    std::vector<Edge> edge);

int main()
{
    int data_num;
    while (std::cin >> data_num) {
        if (data_num == 0) {
            break;
        }
        int max_city;
        const auto edge = makeEdgeFromData(data_num, max_city);

        int min_cost
            = calcMinimumTimeToAllCitys(edge.at(0).start, max_city, edge);
        int min_city = 0;

        for (int i = 1; i <= max_city; ++i) {
            int cost = calcMinimumTimeToAllCitys(edge.at(i).start, max_city, edge);
            if (cost < min_cost) {
                min_cost = cost;
                min_city = i;
            }
        }

        std::cout << min_city << " " << min_cost << std::endl;
    }

    return 0;
}

std::vector<Edge> makeEdgeFromData(int data_num, int& max_city)
{
    std::vector<Edge> edge(10);

    max_city = 0;
    for (int i = 0; i < data_num; ++i) {
        int start, goal, time;
        std::cin >> start >> goal >> time;
        edge.at(start).start = start;
        edge.at(start).to.push_back(goal);
        edge.at(start).time[goal] = time;

        edge.at(goal).start = goal;
        edge.at(goal).to.push_back(start);
        edge.at(goal).time[start] = time;

        max_city = std::max({start, goal, max_city});
    }

    return edge;
}

int calcMinimumTimeToAllCitys(
    int start_city,
    int max_city,
    std::vector<Edge> edge)
{
    for (auto& e : edge) {
        e.cost = INF;
    }

    edge.at(start_city).cost = 0;

    std::priority_queue<Edge> Q;
    Q.push(edge.at(start_city));

    while (!Q.empty()) {
        auto q = Q.top();
        Q.pop();

        for (int to : q.to) {
            if (edge.at(to).cost > q.cost + q.time.at(to)) {
                edge.at(to).cost = q.cost + q.time.at(to);
                Q.push(edge.at(to));
            }
        }
    }

    int cost = 0;
    for (int i = 0; i <= max_city; ++i) {
        cost += edge.at(i).cost;
    }

    return cost;
}

Measured memory_bytes: 3148
#include<iostream>
using namespace std;
#define ll long long
int main()
{
	ll n,y;
	cin>>n>>y;
	ll i,j,k;
	y/=1000;
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=n-i;j++)
		{
			k=n-i-j;
			if(i*10+j*5+k==y)
			{
				cout<<i<<" "<<j<<" "<<k<<endl;
				return 0;
			}
		}
	}
	cout<<-1<<" "<<-1<<" "<<-1<<endl;
	return 0;
} 

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

typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<long long> vll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vector<bool>> vvb;
typedef vector<vector<int>> vvi;

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

int main() {
	int n;
	cin >> n;
	vi p(n);
	rep(i, n) {
		cin >> p.at(i);
	}
	bool ok = true;
	int cnt = 0;
	while (ok) {
		ok = false;

		rep(i, n) {
			if (p.at(i) == i + 1) {
				if (i != n - 1) {
					swap(p.at(i), p.at(i + 1));
				}
				else {
					swap(p.at(i), p.at(i - 1));
				}
				cnt++;
			}
		}

		rep(i, n) {
			if (p.at(i) == i + 1) {
				ok = true;
				break;
			}
		}
	}
	cout << cnt << endl;
	return 0;
}

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

int main() {
    float y = 0.0, b = 0.0, x;
    string s;
    int n, i;
    cin >> n;
    for(i = 0; i < n; i ++)
    {
        cin >> x >> s;
        if(s == "JPY")
            y += x;
        else
            b += x;
    }
    cout << y + (b * 380000.0);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define dbg1(x) cerr<<#x<<"="<<(x)<<" "
#define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"
#define dbg3(x) cerr<<#x<<"\n"
using namespace std;
#define reg register
inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
const int MN=2e5+5;
ll a[MN],N,t1,t2,t3,ans;
ll cal(ll x,ll y,ll z)
{
	ll _1=a[x],_2=a[y]-a[x],_3=a[z]-a[y],_4=a[N]-a[z];
	return abs(max(max(_1,_2),max(_3,_4))-min(min(_1,_2),min(_3,_4)));
}
int main()
{
	N=read();
	reg int i;
	for(i=1;i<=N;++i) a[i]=read()+a[i-1];
	t1=1;t2=2;t3=3;ans=cal(1,2,3);
	for(;t2<=N-2;++t2)
	{
		while(t1+1<t2&&abs(a[t2]-2*a[t1+1])<abs(a[t2]-2*a[t1]))++t1;
		while(t3+1<N&&abs(a[N]-2*a[t3+1]+a[t2])<abs(a[N]-2*a[t3]+a[t2]))++t3;
		ans=min(ans,cal(t1,t2,t3));
	}
	return 0*printf("%lld\n",ans);
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max/32*15+208;

int main(){
    int n, m;
    while(cin >> n >> m, n|m){
        vector<int> v(n);
        for(auto &&i : v) cin >> i;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += min(v[i], m/n);
        }
        cout << ans << "\n";
    }
    return 0;
}


Measured memory_bytes: 3084
#include <bits/stdc++.h>
#define pb push_back
#define IOS                                                                    \
  ios_base::sync_with_stdio(false);                                            \
  cin.tie(0);                                                                  \
  cout.tie(0)
#define ll long long int
#define ld long double
#define el '\n'
#define PI (ld)3.141592653589793238462643383279502884197169399375105820974944
#define inf (ll)1000000000
#define mod (ll)1000000007
#define mod1 (ll)998244353
#define fo(i, n) for (long long i = 0; i < int(n); i++)
#define pll pair<ll, ll>
#define ml map<ll,ll>
#define vli vector<pair<ll,int>>
#define vpl vector<pll>
#define vvl vector<vector<ll> >
#define vvpl vector< vector<pll> >
#define ff first
#define ss second
#define pqueue priority_queue< ll >
#define pdqueue priority_queue< ll,vl ,greater< ll > >
#define mem(a,b) memset(a,b,sizeof(a));
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define sz(a) (ll)a.size()
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fd(i,a,b) for(ll i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define vl vector<ll>
//#define x ff
//#define y ss
#define pt(a) for(auto it:a)cout<<it<<" ";cout<<endl;
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
using namespace std;

double gcd(double a, double b) { return a < 0.01 ? b : gcd(fmod(b, a), a); }

vector<ll> parent, rak;

void make_set(int f){
    fo(i,f+1)parent.pb(i);
    rak.assign(f+1,1);
}

ll find_set(ll v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

ll union_sets(ll a, ll b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rak[a] < rak[b])
            swap(a, b);
        parent[b] = a;
        rak[a]+=rak[b];
        return (rak[a]-rak[b])*(rak[b]);
    }
    return 0;
}

long long bpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1)
      res = res * a % m;
      a = a * a % m;
      b >>= 1;
  }
  return res;
}
ll extend_gcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll x1,y1;
    ll ans =extend_gcd(b,a%b,x1,y1);
    x=y1;
    y=x1-(a/b)*y1;

    return ans;
}
ll inverse(ll a,ll m){
    ll x,y;
    extend_gcd(m,a,x,y);
    y%=m;
    y+=m;
    y%=m;
    return y;
}

/*const int N = 1000001;
int lp[N+1];
vector<int> pr;
void s(){
for (int i=2; i<=N; ++i) {
        if (lp[i] == 0) {
            lp[i] = i;
            pr.push_back (i);
        }
        for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
            lp[i * pr[j]] = pr[j];
    }
}*/


ll kv;
ll t,n,x,y,h,k,z,p,q,w;
string s;
//vvl v;
//vl vis,d;

int main() {
    IOS;
    cin>>n;
    fo(i,n)cin>>x,h+=x,p=max(p,x);
    cout<<h-p/2;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int N, a[3001];
  int i, sum=0;
  scanf("%d\n", &N);

  for(i=1;i<=N;i++){
  scanf("%d", &a[i]);
  sum+=a[i];
  }

  sum-=N;
  printf("%d", sum);
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(){
	int N,K,ans=1;
	cin>>N>>K;
	N=N-K;
	K--;
	if(N%K==0) ans=ans+N/K;
	else ans=ans+1+N/K;
	cout<<ans;
	return 0;
}

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

/*BigInteger
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>
namespace xxx = boost::multiprecision;
using Bint = xxx::cpp_int;
using Real = xxx::number<xxx::cpp_dec_float<1024>>;
*/

#define int long long
#define pb(x) push_back(x)
#define m0(x) memset((x), 0LL, sizeof(x))
#define mm(x) memset((x), -1LL, sizeof(x))

//container
#define ALL(x) (x).begin(), (x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
#define PERM(c) \
  sort(ALL(c)); \
  for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))

// debug
#define GET_VAR_NAME(variable) #variable
#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;

// bit_macro
#define Bit(n) (1LL << (n))
#define Bitset(a, b) (a) |= (1LL << (b))
#define Bitunset(a, b) (a) &= ~(1LL << (b))
#define Bitcheck(a, b) ((((a) >> (b)) & 1LL) == 1LL)
#define Bitcount(a) __builtin_popcountll((a))

//typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

//constant
constexpr int INF = (int)1e18;
constexpr int MOD = (int)1e9 + 7;
constexpr double PI = (double)acos(-1);
constexpr double EPS = (double)1e-10;
constexpr int dx[] = {-1, 0, 0, 1, 0, -1, -1, 1, 1};
constexpr int dy[] = {0, -1, 1, 0, 0, 1, -1, 1, -1};

//
template <typename T>
void chmax(T &a, T b) { a = max(a, b); }
template <typename T>
void chmin(T &a, T b) { a = min(a, b); }
//
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
struct Accelerate_Cin {
  Accelerate_Cin() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
  };
};

signed main() {
  int H, W;
  cin >> H >> W;
  static int dp[1010][1010];
  dp[0][0] = 1;

  static char c[1010][1010];

  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> c[i][j];
    }
  }

  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (c[i][j] == '#') continue;
      dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % MOD;
      dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % MOD;
    }
  }

  cout << dp[H - 1][W - 1] << endl;
  return 0;
}


Measured memory_bytes: 9088
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;

int main()
{
  int N,Y,i,j,sum=0,f,k=0,t,d[10],A,B,C,D;
  scanf("%d",&A);
  d[0] = A / 1000;
  d[1] = (A / 100) % 10;
  d[2] = (A / 10 ) % 10;
  d[3] = A % 10;
  for(i=0;i<8;i++){
    sum += d[0];
    for(j=0;j<3;j++){
      f = (i >> j) & 1;
      if(f){
        sum += d[j+1];
      }else{
        sum -= d[j+1];
      }
    }
    if(sum==7)
      {
        printf("%d",d[0]);
        for(j=0;j<3;j++){
          if((i >> j) & 1)
            printf("+");
          else
            printf("-");
          printf("%d",d[j+1]);
        }
        printf("=7\n");
        return 0;
      }
    sum = 0;
  }
 
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long int
#define ar array
#define mp make_pair
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int a,b;
	cin>>a>>b;
	cout<<((a+b)>=24?(a+b-24):a+b);
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

        int n = sc.nextInt();
        int[] a = new int[n];

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        boolean flag = true;
        int cnt = 0;
        while (flag) {
            flag = false;
            for (int i = n-1; i > 0; i--) {
                if (a[i] < a[i-1]) {
                    int z = a[i];
                    a[i] = a[i-1];
                    a[i-1] = z;
                    flag = true;
                    cnt++;
                }
            }
        }

        for (int i = 0; i < n-1; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println(a[n-1]);
        System.out.println(cnt);
    }
}



Measured memory_bytes: 26136
#include <bits/stdc++.h>
using namespace std;
const int MN = 1e5+9;
int N,a[MN]; long long b[MN];
int main(){
    scanf("%d",&N);
    for(int i=1; i<=N; i++)
        scanf("%d", &a[i]);
    sort(a+1,a+N+1);
    for(int i=1; i<=N; i++)
        b[i] = b[i-1]+a[i];
    int M = N;
    for(; M; M--)
        if(b[M]*2<a[M+1]) break;
    printf("%d\n",N-M);
}


Measured memory_bytes: 1408
n = gets.to_i
t = n.times.map{gets.to_i}
tmp = t[0]
for i in 1..n-1
  m = t[i]
  l = tmp
  while l%m != 0
    l,m = m,l%m
  end
  tmp = (t[i]*tmp)/m
end
puts tmp

Measured memory_bytes: 1788
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

fn main() {
    let mut a: String = input();
    let b: String = input();

    a.push_str(&b);
    let c: i64 = a.parse().ok().unwrap();

    let mut ok = false;
    for i in 1..c {
        if i * i == c {
            ok = true
        }
    }
    println!("{}", if ok { "Yes" } else { "No" });
}


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

const long long MOD = 1000000007;

int main(void) {
    int X,Y;
    cin >> X >> Y;
    int diff = abs(X - Y);
    if(diff > min(X,Y)) {
        printf("0\n");
        return 0;
    } else if((min(X,Y) - diff) % 3 != 0) {
        printf("0\n");
        return 0;
    } else {
        int p = (min(X,Y) - diff) / 3;
        int n = p * 2 + diff;
        int k = p + diff;
        vector<long long> a(n + 3), b(n + 3), c(n + 3);
        a[0] = a[1] = b[0] = b[1] = c[0] = c[1] = 1;
        for(int i = 2; i <= n; i++) {
            a[i] = a[i - 1] * i % MOD;
            b[i] = MOD - b[MOD%i] * (MOD / i) % MOD;
            c[i] = c[i - 1] * b[i] % MOD;
        }
        printf("%lld\n", a[n] * (c[k] * c[n - k] % MOD) % MOD);
    }
    return 0;
}


Measured memory_bytes: 15872
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
  
int main() {
  int N;
  cin >> N;
  vi A(N);
  rep(i,N) {
    cin >> A[i];
  }
  v(ll) sum(N+1,0);
  rep(i,N) {
    sum[i+1] = sum[i] + (ll)(A[i]);
  }
  map<ll,ll> mp;
  rep(i,N+1) {
    mp[sum[i]]++;
  }
  ll ans = 0;
  for(auto x:mp) {
    ans += (x.second * (x.second-1))/2;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 15104
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x) x
#define rep(...) MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c) c.begin(),c.end()
#define mp make_pair
#define write(x) cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T, class U>bool chmax(T& a, U&& b) { return a < b ? a = b, 1 : 0; }
template<class T, class U>bool chmin(T& a, U&& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

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

    ll multi = 1;
    ll add = 0;
    rep(i, N) {
        int q, x;
        cin >> q >> x;
        
        if (q == 1) {
            multi = x * multi;
            add = x * add;
        }
        else if (q == 2) {
            add += x;
        }
        else {
            add -= x;
        }
    }

    cout << -add << ' ' << multi << endl;
}


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

char c[200005];

int main(){
    scanf(" %s", &c);
    int ans = 0;
    for (int i = 0; i < strlen(c); ++i){
        ans += (int) (c[i] - '0');
    }
    if (ans % 9 == 0) printf("Yes");
    else printf("No");
}


Measured memory_bytes: 3940