akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr ll mod=1e9+7;

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

int main()
{
  int h,w,k;
  cin>>h>>w>>k;
  pair<int,int> start,goal;
  cin>>start.first>>start.second;
  cin>>goal.first>>goal.second;
  start.first--;
  start.second--;
  goal.first--;
  goal.second--;
  vector<string> field(h);
  for (int i = 0; i < h; ++i)
  {
    cin>>field[i];
  }
  vector<vector<bool>> seen(h,vector<bool>(w,false));
  vector<vector<int>> dist(h,vector<int>(w,-1));
  dist[start.first][start.second]=0;
  seen[start.first][start.second]=true;
  queue<pair<int,int>> next;
  next.push(start);
  while(!next.empty())
  {
    int x=next.front().first;
    int y=next.front().second;
    next.pop();
    for (int i = 0; i < 4; ++i)
    {
      for (int j = 1; j <= k; ++j)
      {
        int nx=x+dx[i]*j;
        int ny=y+dy[i]*j;
        if(nx<0||nx>=h||ny<0||ny>=w) break;
        if(field[nx][ny]=='@') break;
        if(seen[nx][ny]&&dist[nx][ny]<dist[x][y]+1) break;
        dist[nx][ny]=dist[x][y]+1;
        if(!seen[nx][ny]) next.push({nx,ny});
        seen[nx][ny]=true;
      }
    }
  }
  cout<<dist[goal.first][goal.second];
}

Measured memory_bytes: 12356
#include<iostream>
#include<string>
#include <cmath>
#include <ctype.h>
#include<vector>
#include<algorithm>
using namespace std;
int N;
vector<int> v;
int main() {
    cin >> N;
    if(N==1) cout << 1 << endl;
    if(N>=2&&N<4) cout << 2 << endl;
    if(N>=4&&N<8) cout << 4 << endl;
    if(N>=8&&N<16) cout << 8 << endl;
    if(N>=16&&N<32) cout << 16 << endl;
    if(N>=32&&N<64)cout << 32 << endl;
    if(N>=64) cout << 64 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
 
int main() {
    string S;
    cin >> S;
    if (S[0] != 'A') {
        cout << "WA" << endl;
        return 0;
    }
    int len = S.size();
    int cnt = 0;
    int idx = -1;
    for (int i = 2; i < len - 1; i++) {
        if (S[i] == 'C') {
            idx = i;
            cnt++;
        }
    }
    if (cnt != 1) {
        cout << "WA" << endl;
        return 0;
    }

    for (int i = 1; i < len; i++) {
        if (i != idx && 'A' <= S[i] && S[i] <= 'Z') {
            cout << "WA" << endl;
            return 0;
        }
    }
    cout << "AC" << endl;

    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string>
#include<iostream>
#include<cctype>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include <algorithm>
#include<math.h>
#include<set>
#include<map>
#include<iomanip>

//#include<bits/stdc++.h>


using namespace std;



int main() {
	long long int r = 99999999999999999,a,b,c,d;
	int x, y;
	cin >> x >> y;
	a = y - x;
	b = y + x+1;
	c = -y - x+1;
	d = -y + x+2;
	if (a < r&&a>0)r = a;
	if (b < r&&b>0)r = b;
	if (c < r&&c>0)r = c;
	if (d < r&&d>0)r = d;
	cout << r<<endl;
	return 0;

}




Measured memory_bytes: 256
import math

n = int(input())
dp = [[0 for j in range(n+1)] for i in range(n+1)]
p = []

def init(p):
    global dp
    for i in range(1, n):
        dp[i][i+1] = p[i-1]*p[i]*p[i+1]

def solve(r, c):
    global dp
    smallest = math.inf
    for i in range(r, c):
        temp = p[r-1]*p[i]*p[c] + dp[r][i] + dp[i+1][c]
        if temp < smallest:
            smallest = temp
    return smallest

first = list(map(int,input().split()))
p.append(first[0])
p.append(first[1])
for i in range(n-1):
    temp = list(map(int,input().split()))
    p.append(temp[1])

init(p)
for j in range(3, n+1):
    for i in range(j-2, 0, -1):
        dp[i][j] = solve(i, j)
print(str(dp[1][n]))


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

const ll MOD = 1e9 + 7;

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

    vector<ll> list(n);
    vector<ll> cnt(100010, 0);
    cnt[0] = 3;
    ll ans = 1;
    for(int i = 0; i < n; i++)
    {
        cin >> list[i];
        ans = (ans * cnt[list[i]]) % MOD;
        cnt[list[i]]--;
        cnt[list[i] + 1]++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4744
#include <bits/stdc++.h>
 
using namespace std;
//using namespace __gnu_pbds;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
 
#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) for (int i=0; i<a; i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
 
const int MOD = 1000000007;
double PI = 4*atan(1);
 
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int x; cin >> x;
	int sum = 0, cur = 0;
	while (sum<x) {
		cur++;
		sum += cur;
	}
	cout << cur << "\n";
}

Measured memory_bytes: 256
/* 137b */
#include<stdio.h>
#include<math.h>
int main(void)
{
  int k,x,i;
  scanf("%d %d",&k,&x);
  for(i=x-k+1;i<x+k-1;i++){
    printf("%d ",i);
  }
  printf("%d\n",x+k-1);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <cmath>

using namespace std;

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x, y;
		x = y = 0;
		int xx, yy;
		int dist = 0;
		int a, b;
		a = b = 0;
		for (int j = 0; ; j++) {
			cin >> xx >> yy;
			if (xx == 0 && yy == 0) {
				break;
			}
			x += xx;
			y += yy;
			if (dist < x*x+y*y) {
				dist = x*x+y*y;
				a = x;
				b = y;
			} else if (dist == x*x+y*y) {
				if (x > a) {
					a = x;
					b = y;
				}
			}
		}
		cout << a << ' ' << b << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
from collections import defaultdict
sdic,tdic=defaultdict(int),defaultdict(int)
s=input()
t=input()

def count(str,dic):
    for i in str:
        dic[i]+=1
    dic=sorted(dic.items(),key=lambda x:x[1])
    lst=[]
    for i in range(len(dic)):
        lst.append(dic[i][1])
    return lst
  
slist=count(s,sdic); tlist=count(t,tdic)
if slist==tlist:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 4144
#include<bits/stdc++.h>
#define N 1000005 
#define LL long long 
using namespace std;
bool check(LL n,LL K){
	while(n%K==0)n/=K;
	n%=K;
	return n==1;
}
int main(){
	LL n,ans=1;//K=n 
	cin>>n;
	for(LL i=2;i*i<=n;i++){
		if(n%i==0){
			if(check(n,i))ans++;
			if(i*i!=n&&check(n,n/i))ans++; 
		}
	}
	n--;
	for(LL i=1;i*i<=n;i++){
		 if(n%i==0){
		 	ans++;
		 	if(i*i!=n)ans++;
		 }
	}
	ans--;//K=1;
	cout<<ans<<endl; 
	return 0;
}

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

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;

typedef complex<double> P;
const double EPS = 1e-10;
const double INF = 1e12;

struct L {
    P a, b, v;
    L(){}
    L(P _a, P _b) : a(_a), b(_b), v(b - a) {}
    L(double _ax, double _ay, double _bx, double _by) : L(P(_ax, _ay), P(_bx, _by)) {}
};

double cross(P a, P b) {
    return imag(conj(a) * b);
}

double dot(P a, P b) {
    return real(conj(a) * b);
}

int ccw(P p0, P p1, P p2) {
    if (cross(p1 - p0, p2 - p0) > 0) return +1; // counter-clockwise
    if (cross(p1 - p0, p2 - p0) < 0) return -1; // clockwise
    if (dot(p1 - p0, p2 - p0) < 0) return +2;   // online_back
    if (dot(p0 - p1, p2 - p1) < 0) return -2;   // online_front
    return 0;                                   // on_segment
}

bool intersectSS(L l1, L l2) {
    return (ccw(l1.a, l1.b, l2.a) * ccw(l1.a, l1.b, l2.b) <= 0 &&
            ccw(l2.a, l2.b, l1.a) * ccw(l2.a, l2.b, l1.b) <= 0);
}

double crosspointSS(L l1, L l2) {
    double d1 = abs(cross(l2.v, l1.a - l2.a));
    double d2 = abs(cross(l2.v, l1.b - l2.a));
    double t = d1 / (d1 + d2);
    // return l1.a + t * l1.v;
    return t;
}

L readL() {
    double xa, ya, xb, yb;
    cin >> xa >> ya >> xb >> yb;
    return L(xa, ya, xb, yb);
}

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

    int T;
    cin >> T;
    rep(_, T) {
        L blue = readL();
        int n;
        cin >> n;
        vector<L> lines(n);
        V layer(n);
        rep(i, n) {
            lines[i] = readL();
            int o, l;
            cin >> o >> l;
            layer[i] = l;
            if (o == 0) layer[i] ^= 1;
        }

        vector<pair<double, int>> v; // {t, id} 
        rep(i, n) {
            if (!intersectSS(blue, lines[i])) continue;
            v.emplace_back(make_pair(crosspointSS(blue, lines[i]), i));
        }
        sort(all(v));

        int ans = 0;
        rep(i, (int)v.size() - 1) {
            if (layer[v[i].second] != layer[v[i + 1].second]) {
                ans++;
            }
        }

        cout << ans << endl;

    }
}

Measured memory_bytes: 3184
package main

import (
	"fmt"
)

func main() {
	var n, min, max int
	fmt.Scan(&n, &min, &max)

	ans := 0
	for i := 1; i <= n; i++ {
		sum := totalEachDigit(i)
		if sum >= min && sum <= max {
			ans += i
		}
	}
	fmt.Println(ans)
}

func totalEachDigit(num int) int {
	sum := 0
	for num > 0 {
		d := num % 10
		sum += d
		num /= 10
	}
	return sum
}


Measured memory_bytes: 512
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define max(p,q) ((p)>(q)?(p):(q))
#define min(p,q) ((p)<(q)?(p):(q))
#define chmax(a,b) ((a)=(a)>(b)?(a):(b))
#define chmin(a,b) ((a)=(a)<(b)?(a):(b))
#define abs(p) ((p)>=(0)?(p):(-(p)))
#define MOD 1000000007
ll power(ll a,ll b){ll r=1;rep(i,b){r*=a;}return r;}
#define swap(a,b) do{ll w=(a);(a)=(b);(b)=w;}while(0)
#define swapd(a,b) do{double w=(a);(a)=(b);(b)=w}while(0)
//your code here!

int cmp(const void *a, const void *b){
    ll A=*(ll *)a, B=*(ll *)b;
    if(A==B)return 0;
    else return A>B ? 1:-1;//昇順ソート
}
/*
int main(void){
    ll N, L[10010], ans=0;
    scanf("%lld", &N);
    rep(i, N) scanf("%lld", L+i);
    qsort(L, N, sizeof(ll), cmp);
    for(ll i=N-1; i>=2; i--) {
        ll j=i-1;
        while(j>=1) {
            ll k=j-1;
            while(k>=0) {
                if(L[i]<L[j]+L[k]) ans++;
                else break;
                k--;
            }
            j--;
        }
    }
    printf("%lld\n", ans);
    return 0;
}
*/
//フレンズさんのコードをカンニングして二分探索
ll N, L[10010];
//配列aは昇順済みを前提として、target以上の値を持つ最小の添字を返す
ll binal_search(ll *a, ll target){
    //左右の右側を返すので、例外処理
    if(a[0]>=target) return 0;

    ll l=0, r=N-1;
    while(r-l > 1) {
        ll m = (l+r) / 2;
        if(a[m]>=target) r=m;
        else             l=m;
    }
    return r;
}
int main(void){
    scanf("%lld", &N);
    rep(i, N) scanf("%lld", L+i);
    qsort(L, N, sizeof(ll), cmp);//昇順ソート

    ll ans=0;
    for(ll i=N-1; i>=2; i--){
        for(ll j=i-1; j>=1; j--){
            ll k = binal_search(L, L[i] - L[j] + 1);
            ans += max(j-k, 0);
        }
    }
    printf("%lld\n", ans);
}


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

int main(){
  
  int H, W;
  cin >> H >> W;
  
  int i;
  for(i = 0; i < W + 2; i++)
    cout << "#";
  
  cout << endl;
  
  for(i = 0; i < H; i++){
    cout << "#";
    string text;
    cin >> text;
    cout << text;
    cout << "#" << endl;
  }
  
  for(i = 0; i < W + 2; i++)
    cout << "#";
}
  
  

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3121000;
long long fact[C_SIZE];
long long finv[C_SIZE];
long long inv[C_SIZE];
long long Comb(int a,int b){
 	if(a<b||b<0)return 0;
 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
void init_C(int n){
	fact[0]=finv[0]=inv[1]=1;
	for(int i=2;i<n;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<n;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}
long long pw(long long a,long long b){
	long long ret=1;
	while(b){
		if(b%2)ret=ret*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return ret;
}
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
// ここから編集しろ
long long x[210000];
long long sum[210000];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%lld",x+i);
	// int a=200000;
	// int b=1000000000;
	// for(int i=0;i<a;i++)x[i]=b-i;reverse(x,x+a);
	long long ret=(1LL<<62);
	for(int i=0;i<a;i++){
		sum[i+1]=sum[i]+x[i];
	}
	for(int i=1;i<=a;i++){
		long long tmp=(long long)(i+a)*b;
		int right=a-1;
		int cur=0;
		while(right>=0){
			long long tmp2=sum[right+1]-sum[max(0,right+1-i)];
			tmp2*=max(5,cur*2+3);
			cur++;
			tmp+=tmp2;
			if(tmp>=ret)break;
			right-=i;
		}
		ret=min(ret,tmp);
	}
	printf("%lld\n",ret);
}

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

int main(){
    int a, b, h, m;
    cin >> a >> b >> h >> m;
    /* 1m -> 6 degree, 
     1h -> 30 degree => 1m -> 0.5 degree
    */
    double hd = h * 30 + (double)(m * 0.5);   //時針
    double md = m * 6;    //分針
    if(h >= 6 and m==0) md=360;
    double bd;
    if(hd > md) bd = hd - md;
    else bd = md - hd;
    double ans;
    if(bd == 0) ans = abs(a-b);
    //double rad = bd * (M_PI/180.0);
    else ans = sqrt(a*a + b*b - 2*a*b * cos(bd * (M_PI/180.0)));    // cosはradianを引数としてる
    cout << fixed << setprecision(20) << ans << endl;
  
  return 0;
}

Measured memory_bytes: 4096
#![allow(dead_code,unused_variables)]
use proconio::{fastout, input};
use std::cmp::min;

#[fastout]
fn main() {
    input! {
        n: usize,
        h:[i32;n],
    }

    let mut dp = vec![1000000000;n+10];
    dp[0] = 0;
    dp[1] = (h[1] - h[0]).abs();

    for i in 2..n{
        dp[i] = min(dp[i],dp[i-1] + (h[i]-h[i-1]).abs());
        dp[i] = min(dp[i],dp[i-2] + (h[i]-h[i-2]).abs());
    }

    println!("{}",dp[n-1]);
}


Measured memory_bytes: 3152
N = int(input())
A = [list(map(int, input().split())) for i in range(2)]

for i in range(N):
	if(i):
		A[0][i] += A[0][i-1]
		A[1][N-1-i] += A[1][N-i]

ans = 0
for i in range(N):
	ans = max(ans, A[0][i]+A[1][i])

print(ans)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		
		int s = sc.nextInt();
		int w = sc.nextInt();
		
		if(w>=s)
			System.out.println("unsafe");
		else
			System.out.println("safe");

		
	}

}


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

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

  if (count(S.begin(), S.end(), 'o') + (15 - S.size()) >= 8)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 3592
U = 10**5
is_prime = [1]*(U+1)
is_prime[0] = 0
is_prime[1] = 0
for p in range(2, int(U**.5)+1):
    if is_prime[p]:
        for q in range(2*p, U+1, p):
            is_prime[q] = 0

primes = [p for p, tf in enumerate(is_prime) if tf]


A = [0]*(10**5+1)
for prime in primes:
    if is_prime[(prime+1)//2]:
        A[prime] = 1


S = [0]*(10**5+1)
for i in range(1, 10**5+1):
    S[i] = S[i-1]+A[i]


q = int(input())
for _ in range(q):
    L, R = map(int, input().split())
    ans = S[R]-S[L-1]
    print(ans)

Measured memory_bytes: 8284
#include <bits/stdc++.h>
using namespace std;
int main(){
	string s;
  cin>>s;
  int n=s.length();
  stack<char> st;
  for(int i=0;i<n;i++){
  	if(s[i]=='B'){
      if(!st.empty())st.pop();
    }
    else st.push(s[i]);
  }
  string g="";
  while(!st.empty()){
    g+= string(1,st.top());
    st.pop();
  }
  reverse(g.begin(),g.end());
  cout<<g<<endl;
}

Measured memory_bytes: 3608
/* 
	Author: ankrypt
*/


#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int

ll N;
ll Vs[25];
ll Cs[25];
ll dp[25][2005][2005];

ll rec(int ind, int val, int cost) {
	if(ind == N) {
		return val - cost;
	}
	ll &ans = dp[ind][val][cost];
	if(ans != -1) {
		return ans;
	}
	ans = max(rec(ind + 1, val, cost), rec(ind + 1, val + Vs[ind], cost + Cs[ind]));
	return ans;
}

int main() {
	scanf("%lld", &N);
	for(int i = 0; i < N; i++) {
		scanf("%lld", &Vs[i]);
	}
	for(int i = 0; i < N; i++) {
		scanf("%lld", &Cs[i]);
	}
	memset(dp, -1, sizeof(dp));
	cout << rec(0, 0, 0);
	return 0;
}
/*
	Powered by Buggy Plugin
*/


Measured memory_bytes: 785536
N,M=map(int,input().split())
par=[i for i in range(N+1)]
size=[1 for i in range(N+1)]
def find(x):
    if x!=par[x]:
        par[x]=find(par[x])
    return par[x]
def union(x,y):
    if find(x)!=find(y):
        x, y = par[x], par[y]
        par[y] = par[x]
        size[x] += size[y]
res=N
for i in range(M):
    s,e=map(int,input().split())
    union(s,e)
print(max(size))

Measured memory_bytes: 18484
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int max = sc.nextInt();
		int P = max;
		int b;
		for(int i=0;i<N-1;i++) {
			b = sc.nextInt();
			if(b>max) {
				max =b;
			}
			P+=b;
		}
		max = max/2;
		P = P-max;
       System.out.println(P);		
	}
}


Measured memory_bytes: 23380
#include <iostream>

using namespace std;
int main() {
    char s[200001];
    cin >> s;
    //   ABC BC
    //   ABC ABC
    // A A BC    -> A BC A -> BC A A
    // A A BC BC -> A BC A BC
    long long accum = 0;
    long long score = 0;
    for (int i=0; s[i]; i++) {
        if (s[i] == 'A') accum++;
        else if (s[i] == 'B' && s[i+1]== 'C') {score += accum; i++;}
        else accum = 0;
    }
    cout << score << endl;
    return 0;
}



Measured memory_bytes: 384
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rrep(i, n) for(int i = n-1; i >= 0; --i)
#define fi first
#define se second
using namespace std;
using lint = long long;
using uint = unsigned int;
using ulint = unsigned long long;
using ldouble = long double;
using pii = pair<int, int>;
using pli = pair<lint, lint>;
using pdd = pair<double, double>;
using pld = pair<ldouble, ldouble>;
using v1i = vector<int>;
using v1li = vector<lint>;
using v2i = vector<vector<int>>;
using v2li = vector<vector<lint>>;
using v3i = vector<vector<vector<int>>>;
using v3li = vector<vector<vector<lint>>>;
using v1b = vector<bool>;
using v2b = vector<vector<bool>>;
using v3b = vector<vector<vector<bool>>>;
using v1c = vector<char>;
using v2c = vector<vector<char>>;
using v3c = vector<vector<vector<char>>>;
constexpr lint mod1 = 1e9+7;
constexpr lint mod2 = 998244353;

int main(){
  int n, q; cin >> n;
  vector<pii> v(n); rep(i, n) cin >> v[i].fi >> v[i].se;
  cin >> q;
  v2i u(511, v1i(100001, 0));
  rep(i, 511){
    if(i == n) break;
    if(i == 0){
      rep(j, 100000) if(j+1 >= v[0].se) u[0][j+1] = v[0].fi;
      continue;
    }
    rep(j, 100000){
      u[i][j+1] = u[(i-1)/2][j+1];
      if(j+1 >= v[i].se) u[i][j+1] = max(u[i][j+1], u[(i-1)/2][j+1-v[i].se] + v[i].fi);
    }
  }
  rep(i, q){
    int y, z, tk, ans = 0; cin >> y >> z; --y;
    v1i tv;
    while(y > 510){
      tv.push_back(y);
      y = (y-1)/2;
    }
    tk = tv.size();
    if(tk == 0) ans = u[y][z];
    else{
      rep(j, 1 << tk){
        int tc = 0, td = 0;
        rep(k, tk){
          if(j & 1 << k){
            tc += v[tv[k]].fi;
            td += v[tv[k]].se;
          }
        }
        if(td > z) continue;
        ans = max(ans, u[y][z-td] + tc);
      }
    }
    cout << ans << "\n";
  }
  return 0;
}

Measured memory_bytes: 205984
#include<bits/stdc++.h>
#define pr std::pair<ll,ll>
#define fir first
#define sec second
typedef long long ll;
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
ll mid;
std::vector<pr>f[131113];
int ls[131113],lw[131113],rs[131113],rw[131113];
void Merge(int A,int B,std::vector<pr>&F){
	int i=0;
	for(pr _:f[A]){
		ll a=_.fir,b=_.sec;
		while(i<f[B].size()-1&&b+f[B][i+1].fir<=mid)++i;
		if(i<f[B].size()&&b+f[B][i].fir<=mid){
			ll d=f[B][i].sec;
			F.emplace_back(a,d);
			F.emplace_back(d,a);
		}
	}
}
void dfs(int x){
	f[x].clear();
	if(!ls[x]){f[x].emplace_back(0,0);return;}
	dfs(ls[x]),dfs(rs[x]);
	for(pr&i:f[ls[x]])i.fir+=lw[x],i.sec+=lw[x];
	for(pr&i:f[rs[x]])i.fir+=rw[x],i.sec+=rw[x];
	Merge(ls[x],rs[x],f[x]);
	Merge(rs[x],ls[x],f[x]);
	std::sort(f[x].begin(),f[x].end());
	pr lst(-1,9e18);
	for(pr&i:f[x])
		if(i.sec>=lst.sec)i.fir=9e18;
		else lst=i;
	std::sort(f[x].begin(),f[x].end());
	while(!f[x].empty()&&f[x].back().fir==9e18)f[x].pop_back();
}
int main(){
#ifdef XZZSB
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	int n=gi();
	for(int i=2;i<=n;++i){
		int fa=gi(),w=gi();
		if(ls[fa])rs[fa]=i,rw[fa]=w;
		else ls[fa]=i,lw[fa]=w;
	}
	ll l=0,r=n*131072ll;
	while(l<r){
		mid=(l+r)>>1;
		dfs(1);
		if(!f[1].empty())r=mid;
		else l=mid+1;
	}
	printf("%lld\n",l);
	return 0;
}


Measured memory_bytes: 46864
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower

using namespace std;
 
int main(){
    string a;
    cin >> a;
    if(a.at(0) == a.at(1) && a.at(1) == a.at(2) && a.at(0) == a.at(2) || a.at(3) == a.at(1) && a.at(1) == a.at(2) && a.at(3) == a.at(2)){
        cout << "Yes" << endl;
    }
    else cout << "No" << endl;
}

Measured memory_bytes: 3488
import java.util.Scanner;

class Main{

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		String k = s.next();
		if(k.compareTo("Sunny")==0) {
			System.out.println("Cloudy");
		}
		else if(k.compareTo("Cloudy")==0) {
			System.out.println("Rainy");
		}
		else if(k.compareTo("Rainy")==0) {
			System.out.println("Sunny");
		}
	}
}


Measured memory_bytes: 20948
#include <iostream>
#include <numeric>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
int Max(int(a), int(b), int(c)) {
	return max(max(a, b), c);
}
int Min(int(a), int(b), int(c)) {
	return min(min(a, b), c);
}





int main() {

	string S = "no";
	string N;
	cin >> N;

	set<char> ve;

	rep(i, N.size()) {
		
		ve.insert(N.at(i));
	}
	if (ve.size() == N.size()) {
		S = "yes";
	}
	cout << S << endl;


}


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
  int a,i,flag=0,flag2=0;
  scanf("%d",&a);
  int b[a];
  for(i=0;i<a;i++){
  	scanf("%d",&b[i]);
    if( b[i]%2==0){
        flag2++;
    if( b[i]%10==0 || b[i]%6==0)
        flag++;
  }
  }
  if(flag==flag2){
    printf("APPROVED");
    return 0;
  }
  	printf("DENIED");
    return 0;
}

Measured memory_bytes: 1720
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 998244353;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
int main(){
	int x1, x2, y1, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	int dx = x2 - x1;
	int dy = y2 - y1;
	int ndx = -dy;
	int ndy = dx;
	int nx = x2 + ndx;
	int ny = y2 + ndy;
	cout << nx << " " << ny << " ";
	dx = -ndy;
	dy = ndx;
	cout << nx + dx << " "<<ny+dy<<endl;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	class Pair{
		public int Gain, Rest;
		public Pair(int g, int r){
			Gain = g; Rest = r;
		}
	}
	public void Solve(){
		
		List<int> L = new List<int>();
		int cnt = 1;
		for(int i=1;i<N;i++){
			if(S[i] == S[i-1]){
				cnt++;
			} else {
				L.Add(cnt);
				cnt = 1;
			}
		}
		L.Add(cnt);
		
		int M = L.Count;
		String LR = S[0] == 'L' ? "LR" : "RL";
		
		// into R
		int[] gain = new int[M];
		List<Pair> gs = new List<Pair>();
//Console.WriteLine(String.Join(" ",L));		
//Console.WriteLine(String.Join(" ",gain));		
		int rsc = 0;
		for(int i=0;i<L.Count;i++){
			if(LR[i % 2] == 'R'){
				gain[i] = L[i] - 1;
				rsc += gain[i];
			} else {
				gain[i] = L[i];
				if(i == M - 1) gain[i]--;
				if(i > 0) gain[i]++;
				gs.Add(new Pair(gain[i], L[i] - 1));
			}
		}
		gs.Sort((p, q) => {
			if(p.Gain == q.Gain) return p.Rest.CompareTo(q.Rest);
			else return -1 * p.Gain.CompareTo(q.Gain);
		});
		for(int i=0;i<gs.Count;i++){
			if(i < K) rsc += gs[i].Gain;
			else rsc += gs[i].Rest;
		}
		// into L
		gain = new int[M];
		gs = new List<Pair>();
		
		int lsc = 0;
		for(int i=0;i<L.Count;i++){
			if(LR[i % 2] == 'L'){
				gain[i] = L[i] - 1;
				lsc += gain[i];
			} else {
				gain[i] = L[i];
				if(i == 0) gain[i]--;
				if(i < M - 1) gain[i]++;
				gs.Add(new Pair(gain[i], L[i] - 1));
			}
		}
		gs.Sort((p, q) => {
			if(p.Gain == q.Gain) return p.Rest.CompareTo(q.Rest);
			else return -1 * p.Gain.CompareTo(q.Gain);
		});
		for(int i=0;i<gs.Count;i++){
			if(i < K) lsc += gs[i].Gain;
			else lsc += gs[i].Rest;
		}
		
		//Console.WriteLine("{0} {1}",lsc, rsc);
		Console.WriteLine(Math.Max(lsc, rsc));
	}
	int N,K;
	String S;
	public Sol(){
		var d = ria();
		N = d[0]; K = d[1];
		S = rs();
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 17504
#include<bits/stdc++.h>
using namespace std;
int main() {
	int a,b,c;
	cin>>a>>b>>c;
	for(int i=b;i<=c;i++){
		if(i%a==0){
			cout<<"OK";
			return 0;
		}
	}
	cout<<"NG";
	return 0;
}


Measured memory_bytes: 3624
import sys
from collections import deque
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    g = [[] for i in range(n+1)]
    for i in range(n-1):
        a, b = LI()
        g[a].append(b)
        g[b].append(a)

    s = 1
    Q = deque([s])
    ans = k
    Qappend = Q.append
    searched = [0] * (n+1)
    searched[s] = 1
    Qp = Q.popleft
    cand = k - 1
    while len(Q) != 0:
        temp = 1
        v = Qp()
        for i in g[v]:
            if searched[i] == 1:
                continue
            searched[i] = 1
            temp = temp * cand % MOD
            cand -= 1
            Qappend(i)
        ans = ans * temp % MOD
        cand = k - 2
    print(ans % MOD)


if __name__ == "__main__":
    main()


Measured memory_bytes: 30104
#include<cstdio>
#include<algorithm>
const int MAXN=5+5;
struct data{double l,per;int v;};
data d[MAXN];int n;
bool comp(data a,data b){return a.per<b.per;};
int main()
{
	int v;long long ans=0;
	d[1].l=0.25; d[2].l=0.5; d[3].l=1; d[4].l=2;
	for(int i=1;i<=4;i++)
	{
		scanf("%d",&d[i].v);
		d[i].per=d[i].v/d[i].l;
	}
	scanf("%d",&n);
	std::sort(d+1,d+4+1,comp);
	for(int i=1;i<=4;i++)
	{
//		printf("per=%.2lf",d[i].per);
		v=n/d[i].l;
		ans+=(long long)v*d[i].v;
//		printf("v=%d unit=%.2lf\n",v,d[i].l);
		n-=v*d[i].l;
		n=std::max(0,n);
//		printf("leftn=%d\n",n);
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
struct mint {
  long long x;
  mint(long long x=0):x(x%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
};
mint dp[2003][2003];
void ncr()
{
  for(int i=0;i<=2002;i++)
  {
    dp[i][0]=1;
    dp[i][i]=1;
  }
  for(int i=1;i<=2002;i++)
    for(int j=1;j<i;j++)
      dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
}
mint c(int n,int r)
{
  return dp[n][r];
}

int main()
{
  int n,k;
  cin>>n>>k;
  ncr();
  for(int i=1;i<=k;i++)
  {
    mint b1=c(n-k+1,i);
    mint b2=c(k-1,i-1);
    mint a=b1*b2;;
    cout<<a.x<<endl;
  }
  return 0;
}
   

Measured memory_bytes: 31616
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

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

    vint sum(N+1,0);
    REP(i,N){
        sum[i+1]=sum[i]+(s[i]=='E');
    }
    
    int ans=N;
    REP(i,N){
        int l=i-sum[i];
        int r=sum[N]-sum[i+1];
        ans=min(ans,r+l);
    }
    cout<<ans<<endl;
    
}


Measured memory_bytes: 3076
using System;

class Program
{
  public static void Main(string[] args)
  {
    string[] read = Console.ReadLine().Split(' ');
    int a = int.Parse(read[0]);
    int b = int.Parse(read[1]);
    int d = a/b;
    int r = a%b;
    double f = (double)a/(double)b;
    Console.WriteLine("{0} {1} {2:f8}",d,r,f);
  }
}

Measured memory_bytes: 9164
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main implements Closeable {

  private InputReader in = new InputReader(System.in);
  private PrintWriter out = new PrintWriter(System.out);

  public void solve() {
    int n = in.ni();
    x = new long[n];
    for (int i = 0; i < n; i++) {
      x[i] = in.nl();
    }
    dp = new Long[n][n];
    out.println(recurse(0, n - 1));
  }

  private long[] x;
  private Long[][] dp;

  private Long recurse(int left, int right) {
    if (left > right) return 0L;

    if (dp[left][right] != null) return dp[left][right];

    return dp[left][right] = Math.max(x[left] - recurse(left + 1, right), x[right] - recurse(left, right - 1));
  }

  @Override
  public void close() throws IOException {
    in.close();
    out.close();
  }

  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public int ni() {
      return Integer.parseInt(next());
    }

    public long nl() {
      return Long.parseLong(next());
    }

    public void close() throws IOException {
      reader.close();
    }
  }

  public static void main(String[] args) throws IOException {
    try (Main instance = new Main()) {
      instance.solve();
    }
  }
}


Measured memory_bytes: 226364
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
const double eps=1e-10;

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

int main(){
    int n; cin>>n;
    vector<int> a(n);
    vector<int> cnt(n, 0);
    for(int i=0; i<n; i++){
        cin>>a[i];
        cnt[a[i]]++;
    }

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

    if(a[0] == a[n-1]){
        if(a[0] <= n/2){
            cout << "Yes" << endl;
            return 0;
        }
    }

    for(int i=0; i<n; i++){
        if(cnt[n-i] == 2*i && cnt[n-i-1] == n-2*i){
            cout << "Yes" << endl;
            return 0;
        }
    }
    
    cout << "No" << endl;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#include <numeric>

using namespace std;

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

    int N;
    cin >> N;

    deque<int> a;
    for (int i=0; i<N; i++) {
      int64_t c;
      cin >> c;
      if (i % 2 == 0) {
        a.push_back(c);
      } else {
        a.push_front(c);
      }
    }

    if (N % 2 == 1) {
      for(auto itr = a.rbegin(); itr != a.rend(); ++itr) {
        cout << *itr << " ";
      }
    } else {
      for(auto itr = a.begin(); itr != a.end(); ++itr) {
        cout << *itr << " ";
      }
    }
    cout << endl;
    return 0;
}


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

const int Max = 100000;
typedef long long llong;

int check(llong A[], int k, int n, llong P){
    int v=0;
    for(int j=0; j<k; j++){
        llong s=0;
        while(s + A[v] <= P){
            s += A[v];
            v++;
            if(v==n)return n;
        }
    }
    return v;
}

int solve(llong A[], int k, int n){
    llong left = 0, right = Max * 10000;
    int mid;
    while(left < right - 1){
        mid = (left + right) /2;
        int v = check(A, k, n, mid);
        if (n <= v){
            right = mid;
        }
        else left = mid;
    }
    return right;
}

int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    llong A[n];
    for(int i=0; i<n; i++){
        scanf("%lld", &A[i]);
    }
    llong ans = solve(A, k, n);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4020
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

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

    int ans = 0;
    int temp1, temp2;
    int b = 0;

    for (int i = 0; i < n; i++) {
        cin >> temp1 >> temp2;

        if (temp1 == temp2)b++;
        else b = 0;

        if (b == 3)ans++;
    }

    if (ans > 0)cout << "Yes";
    else cout << "No";

    return 0;
}

Measured memory_bytes: 3632
#include<stdio.h>
int main (void){
 int a[100000];
 int n;
 int i=0;
 int t=0;
 int f=0;
 scanf("%d",&n);
 while(i<n){
  scanf("%d",&a[i]);
  i++;
 }
 i=0;
 while(i<n){
  if(a[i]%4){
   if((a[i]%2)==0)
    t++;
  }else{
   f++;
  }
  i++;
 }
 if(f>=(n-t-f)){
  printf("Yes\n");
 }else if(t==0&&(n%2)==1&&(f+1)==(n-t-f)){
  printf("Yes\n");
 }else{
  printf("No\n");
 }
 return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
const int INF=1e9;
const int MOD=1e9+7;
//const int MOD=998244353;
const long long LINF=1e18;
using namespace std;
#define int long long
#define fin {cout<<""<<endl;return 0;}
//template

//main
signed main(){
  int N;cin>>N;
  std::vector<int> a(N),b(N);
  for(int i=0;i<N;i++)cin>>a[i]>>b[i];
  for(int i=0;i<N;i++){
    int K=a[i]*b[i];
    int l=0,h=MOD;
    while(h-l>1){
      int m=(h+l)/2;
      if(m*m<K)l=m;
      else h=m;
    }
    int ans=2*l;
    if(l*(l+1)>=K)ans--;
    if(l>=min(a[i],b[i]))ans--;
    cout<<ans<<endl;
  }
}


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

using namespace std;

int main() {
    int A, B, T;
    cin >> A >> B >> T;
    int ans = 0;
    for (int i = A; i <= T; i += A) {
        ans += B;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define dd double
#define endl "\n"
#define pb push_back
#define all(v) v.begin(),v.end()
#define mp make_pair
#define fi first
#define se second
#define fo(i,n) for(int i=0;i<n;i++)
#define fo1(i,n) for(int i=1;i<=n;i++)
ll mod=1000000007;
ll n,k,t,m,q,flag=0;
ll po(ll k ,ll n,ll ans,ll temp,ll ans1){
    if(n==0)return ans;
    while(temp<=n){
        ans*=ans1;ans%=mod;ans1=ans1*ans1;ans1%=mod;n=n-temp;temp*=2;
    }
    return po(k,n,ans,1,k)%mod;
    //eg. po(2,78,1,1,2);
}
ll min(ll a,ll b){if(a>b)return b;else return a;}
ll max(ll a,ll b){if(a>b)return a;else return b;}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    //cin>>t;
    t=1;
    while(t--){
        cin>>n>>m;
        char a[n+1][m+1];
        fo1(i,n)fo1(j,m)cin>>a[i][j];
        ll change[n+1][m+1];
        if(a[1][1]=='.')change[1][1]=0;
        else change[1][1]=1;
        for(int d=3;d<=m+n;d++){
            for(int i=1;i<=d && i<=n;i++){
                ll j=(d-i);
                if(j>=1 && j<=m){
                    if(i==1){change[i][j]=change[i][j-1]; if(a[i][j]=='#'&& a[i][j-1]=='.')change[i][j]++;}
                    else if(j==1){change[i][j]=change[i-1][j];if(a[i][j]=='#'&& a[i-1][j]=='.')change[i][j]++;}
                    else {
                        //change[i][j]=min(change[i][j-1] , change[i-1][j]);
                        ll t1=change[i][j-1];
                        if(a[i][j]=='#'&& a[i][j-1]=='.')t1++;
                        ll t2=change[i-1][j];
                        if(a[i][j]=='#'&& a[i-1][j]=='.')t2++;
                        change[i][j]=min(t1,t2);
                    }
                    
                }
            }
        }
        cout<<change[n][m];
        
    }

    return 0;
}


Measured memory_bytes: 384
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_macros)]
#![allow(unused_imports)]

use std::cmp::*;
use std::collections::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
    ($iter:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    }
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

macro_rules! chmax {
    ($x:expr, $e:expr) => {
        if $x < $e {
            $x = $e;
        }
    };
}
macro_rules! chmin {
    ($x:expr, $e:expr) => {
        if $x > $e {
            $x = $e;
        }
    };
}

const MOD: usize = 1000000007;
const MAX: usize = 1800000;

struct Comb {
    fac: Vec<usize>,
    finv: Vec<usize>,
    inv: Vec<usize>,
}

impl Comb {
    fn com_init(&mut self) {
        self.fac[0] = 1;
        self.fac[1] = 1;
        self.finv[0] = 1;
        self.finv[1] = 1;
        self.inv[1] = 1;
        for i in 2..MAX {
            self.fac[i] = self.fac[i-1] * i % MOD;
            self.inv[i] = MOD - self.inv[MOD%i] * (MOD / i) % MOD;
            self.finv[i] = self.finv[i-1] * self.inv[i] % MOD;
        }
    }
    fn com(&self, n: usize, k: usize) -> usize {
        if n < k {
            return 0;
        }
        self.fac[n] * (self.finv[k] * self.finv[n - k] % MOD) % MOD
    }
}

const INF: i64 = 1 << 60;

fn main() {
    input!{
        X: usize,
        Y: usize,
    }
    if (X + Y) % 3 != 0 {
        println!("0");
        return;
    }
    let N = (X + Y) / 3;
    let K = max(X, Y) - N;
    let mut com = {
        let fac = vec![0; MAX];
        let finv = vec![0; MAX];
        let inv = vec![0; MAX];
        Comb { fac: fac, finv: finv, inv: inv }
    };
    com.com_init();
    println!("{}", com.com(N, K));
}


Measured memory_bytes: 47356
h, w = map(int, input().split())

lis = []
tmp =["."]*(w+2)
lis.append(tmp)

for i in range(h):
    a = ["."]+list(input())+["."]
    lis.append(a)

lis.append(tmp)

for i in range(1,h+1):
    for j in range(1,w+1):
        if lis[i][j] == "#":
            continue
        
        else:
            n = 0
            if lis[i-1][j-1] == "#":
                n += 1
            if lis[i-1][j] == "#":
                n += 1
            if lis[i][j-1] == "#":
                n += 1
            if lis[i][j+1] == "#":
                n += 1
            if lis[i+1][j-1] == "#":
                n += 1
            if lis[i+1][j] == "#":
                n += 1
            if lis[i+1][j+1] == "#":
                n += 1
            if lis[i-1][j+1] == "#":
                n += 1
            
            lis[i][j] = n

for i in range(1, h+1):
    for j in range(1, w+1):
        print(lis[i][j], end="")
    print()
   

Measured memory_bytes: 9164
n,k = map(int,input().split())
lst = list(map(int,input().split()))

id = lst.index(1)

left = len(lst[0:id])
right = len(lst[id+1:])
mod = max(left%(k-1),right%(k-1))

total = left + right

counter = 0
while total > 0:
    counter += 1
    total -= k - 1

print(counter)

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

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define mod 998244353
#define pb push_back
#define ff first
#define ss second
#define con continue
#define ub upper_bound
#define lb lower_bound
#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

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

const int dx8[] = {-1, 0, 1, 0,1,1,-1,-1};
const int dy8[] = {0, -1, 0, 1,1,-1,1,-1};



void solve()
{
 ll n,k ;
 cin >> n >> k ;
 vector<ll> dp(n+1,0);
 vector<pair<ll,ll> > q ;

 for( ll i=0;i<k;i++)
 {

     ll a,b ;
     cin >> a >> b;
     q.pb({a,b});
 }
 dp[0]=1;
 for(ll i =0 ;i<n; i++)
 {

     for(ll j=0 ; j<k;j++)
     {
         ll x,y;
         x=i+q[j].ff;
         y=i+q[j].ss;
         if(x>=n) continue ;
         y=min(y,n-1) ;
         dp[x] = (dp[x]%mod + dp[i]%mod)%mod;
         dp[y+1]= (dp[y+1]%mod-dp[i]%mod+mod)%mod ;
     }
     if(i==0 ) continue;
     dp[i+1]= (dp[i+1]%mod+dp[i]%mod)%mod;
 }
 cout << dp[n-1] << endl ;
}



int main()
{
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
   solve();
}


Measured memory_bytes: 4776
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>

#define rep(i, n) for(int i = 0; i < n; i++)
#define in_arr(type, a, n) for(int i = 0; i < n; i++) scanf(type, &((a)[i]));
#define ll long long int
#define MOD 1000000007

void merge_sort(int *a, int n){
    if(n < 2) return;
    int mid = n / 2;
    int *left = malloc(sizeof(int) * mid);
    int *right = malloc(sizeof(int) * (n - mid));
    for(int i = 0; i < mid; ++i){
        left[i] = a[i];
    }
    
    for(int i = 0; i < n - mid; ++i){
        right[i] = a[i + mid];
    }
    merge_sort(left, mid);
    merge_sort(right, n - mid);
    for(int i = 0; i < n; ++i){
        printf("%d\t", a[i]);
    }
    printf("\n");
    int li = 0, ri = 0;
    for(int i = 0; i < n; ++i){
        if(li >= mid){
            for(; ri < n - mid; ++ri){
                a[i] = right[ri];
                ++i;
            }
            break;
        }
        
        if(ri >= n - mid){
            for(; li < mid; ++li){
                a[i] = left[li];
                ++i;
            }
            break;
        }
        
        if(left[li] < right[ri]){
            a[i] = left[li];
            li++;
        }else{
            a[i] = right[ri];
            ri++;
        }
    }
    free(left);
    free(right);
}

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

ll mod_add(ll a, ll b){
    return (a + b) % MOD;
}

ll mod_sub(ll a, ll b){
    return (a - b + MOD) % MOD;
}

ll mod_mul(ll a, ll b){
    return (a * b) % MOD;
}

ll mod_pow(ll a, ll b){
    if(b == 0){
        return 1;
    }else if(b == 1){
        return a;
    }else{
        ll half = mod_pow(a, b / 2);
        return mod_mul(mod_mul(half, half), b % 2 == 0 ? 1 : a);
    }
}

ll mod_inverse(ll a){
    return mod_pow(a, MOD - 2);
}

ll mod_div(ll a, ll b){
    return mod_mul(a, mod_inverse(b));
}

int main(){
    int n;
    scanf("%d", &n);
    int *count;
    count = malloc(sizeof(int) * 26);
    for(int i = 0; i < 26; ++i){
        count[i] = 1;
    }
    char c;
    scanf("%c", &c);
    for(int i = 0; i < n; ++i){
        scanf("%c", &c);
        ++count[c - 'a'];
    }
    ll ret = 1;
    for(int i = 0; i < 26; ++i){
        ret = mod_mul(ret, count[i]);
    }
    printf("%lld\n", mod_sub(ret, 1));
    free(count);
    return 0;
}


Measured memory_bytes: 128