akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
long long mo = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
ld PI=3.14159265358979323846;

int main(){
    ll N;
    cin >> N;
    vector<ll> A(N);
    deque<ll> que;
    rep(i,N){
        cin >> A[i];//.first;
        //A[i].second = i;
    }
    ll cnt = 0;
    rep(i,N){
        ll itr = lower_bound(que.begin(), que.end(), A[i]) - que.begin();
        if(itr == 0){
            que.push_front(A[i]);
        }else{
            que[itr-1] = A[i];
        }
    }
    cout << que.size() << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vpii;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef vector<ll> vll;
#define INF 0x3f3f3f3f
#define MOD 1000000007LL
#define HF   500000004LL
#define EPS 0.00001
#define f first
#define s second
#define pb push_back

#define FOR(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define F0R(i, a) for (int i=0; i<(signed)(a); i++)
#define RFOR(i, a, b) for (int i=(a); i >= b; i--)

#define MN 5005
int n;
int p[MN];

int dsu[MN];
int ec[MN];
int fd(int x){
    if(dsu[x] < 0) return x;
    return dsu[x] = fd(dsu[x]);
}
bool jn(int x, int y){
    x = fd(x); y = fd(y);
    if(x == y) return false;
    if(dsu[x] > dsu[y]) swap(x, y);
    dsu[x] += dsu[y];
    dsu[y] = x;
    ec[x] += ec[y];
    return true;
}

ll modExp(ll b, ll ex){
    ll prod = 1;
    while(ex > 0){
        if(ex % 2 == 0){
            b = (b * b) % MOD;
            ex /= 2;
        } else{
            prod = (prod*b) % MOD;
            ex--;
        }
    }
    
    return prod;
}
ll aah[MN];
void mult(int sz){
    RFOR(i, n, 1){
        aah[i] = (aah[i]+aah[i-1]*sz)%MOD;
    }
}
ll fac[MN];
int main(){
    //ios_base::sync_with_stdio(false);
    //cin.tie(0);

    int cyccnt = 0;
    int uncnt = 0;
    cin >> n;
    FOR(i, 1, n) dsu[i] = -1;
    FOR(i, 1, n){
        cin >> p[i];
        if(p[i] != -1) ec[fd(i)]++;
        //cout << "hi\n";
        if(p[i] == -1) ++uncnt;
        else if(!jn(i, p[i])) ++cyccnt;
    }
    int bruh = 0;
    FOR(i, 1, n){
        if(p[i] == -1){
            int x = fd(i);
            if(dsu[x]+ec[x] != 0) ++bruh;
            //cout << i << " yay\n";
        }
    }
    //cout << "hi\n";
    ll ans = (modExp(n-1, uncnt)*cyccnt)%MOD;
    aah[0] = 1;
    //FOR(i, 1, n) cout << dsu[i] << " " << ec[i] << "\n";
    FOR(i, 1, n){
        if(dsu[i] < 0 && ec[i]+dsu[i] != 0){
            //cout << "mult " << i << " " << dsu[i] << "\n";
            mult(-dsu[i]); //multiply by 1+sz*x
        }
    }
    fac[0] = 1;
    FOR(i, 1, n){
        fac[i] = (fac[i-1]*i)%MOD;
    }
    //cout << "hi\n";
    //F0R(i, uncnt+1) cout << aah[i] << " ";
    //cout << "\n";
    FOR(i, 1, uncnt){
        //if i=1, answer loses a bit
        ll numCycs = (aah[i]*fac[i-1])%MOD;
        if(i == 1){
            numCycs = (numCycs-bruh+MOD)%MOD;
        }
        ll ot = modExp(n-1, uncnt-i);
        ans = (ans+numCycs*ot)%MOD;
    }
    //cout << ans << "\n";
    ll fin = (modExp(n-1, uncnt)*n-ans+MOD)%MOD;
    cout << fin << "\n";

    return 0;
}


Measured memory_bytes: 3748
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>

#define REP(i,a,n) for(int i=a;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define REV(i,a,n) for(int i=n;i>=a;--i)
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define mod 1000000007
#define show(n) cerr<<#n<<" = "<<n<<endl
#define shows(n) for(auto z:n){cerr<<z<<", ";}cerr<<endl
#define showsp(n) for(auto z:n){cerr<<z.fs<<" "<<z.sc<<", ";}cerr<<endl;

//ここからAtCoder向けdefine
#define yes cout << "YES" << endl
#define no cout << "NO" << endl

using namespace std;

using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vd = vector<double>;
using pint = pair<int,int>;

const int INF = (1 << 30);

int maxn = 1000000000;

ll tgt;
vector<pair<double,pair<double,ll> > > e(4);

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    rep(i,4) {
        e[i].sc.fs=(1<<i)/4.0;
        cin>>e[i].sc.sc;
        e[i].fs=e[i].sc.sc*(4.0/(1<<i));
        //cerr<<e[i].sc.fs<<endl;
    }
    cin>>tgt;
    //showsp(e);
    sort(all(e));
    //showsp(e);
    //show(e[0].fs);
    ll cur=0;
    ll are;
    rep(i,4){
        are=tgt/e[i].sc.fs;
        cur+=e[i].sc.sc*are;
        tgt-=e[i].sc.fs*are;
    }
    cout<<cur<<endl;
    return 0;
}

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

int main() {
  string n;
  cin >> n;
  int sum = 0;
  int a;
  
  for (int i = 0; i < n.length(); i++){
    a = n[i] - '0';
    sum += a;
  }
  
  if (sum % 9 == 0){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 3696
#include<stdio.h>

int main()
{
	int a, b, c,maximum,ans;

	scanf("%d%d%d", &a, &b, &c);

	if (a >= b&&a >= c)
		ans = a * 10 + b + c;
	if (b >= a&&b >= c)
		ans = b * 10 + a + c;
	if (c >= a&&c >= b)
		ans = c * 10 + a + b;
	
	printf("%d\n", ans);

	return 0;
}

Measured memory_bytes: 128
import sys
input=sys.stdin.readline

A,B,C,D,E,F = list(map(int, input().split()))

wa = []
for a in range(0,F//(A*100)+1):
    for b in range(0,F//(B*100)+1):
        w = a*A*100 + b*B*100
        if w < F and w not in wa:
            wa.append(w)
wa.remove(0)

md = 0
sw = 0
ss = 0
limit_dens = (100*E)/(100+E)
for w in wa:
    for c in range(0,F//C+1):
        for d in range(0,F//D+1):
            s = c*C + d*D
            if w + s <= F:
                d = (100*s)/(w+s)
                if d <= limit_dens:
                    if md <= d:
                        md = d
                        sw = w+s
                        ss = s
                        if d == limit_dens:
                            print(sw, ss)
                            exit()
print(sw, ss)

Measured memory_bytes: 3064
//
// Created by Edward on 4/25/2020.
//

//
// Created by Edward on 4/25/2020.
//

#include <bits/stdc++.h>

using namespace std;

namespace ballbox10{
    int N, K;
    long long dp[1001][1001];

    int main(){
        cin >> N >> K;
        for(int i = 0; i <= 1000; i++){
            dp[0][i] = 1;
            dp[i][1] = 1;
        }
        for(int i = 1; i <= 1000; i++){
            for(int j = 2; j <= 1000; j++){
                if(i >= j){
                    dp[i][j] = dp[i-j][j] + dp[i][j-1];
                    dp[i][j] %= 1000000007;
                }
                else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        cout << dp[N][K] << endl;
    }
}

int main(){
    ballbox10::main(); return 0;
}


Measured memory_bytes: 10928
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;
const int INF = 1000000009;
const ll LINF = 1e18;

vector<pair<long long, long long>> prime_factorize(long long N) {
  vector<pair<long long, long long>> res;
  for (long long a = 2; a * a <= N; ++a) {
    if (N % a != 0) continue;
    long long ex = 0;

    while (N % a == 0) {
      ++ex;
      N /= a;
    }
    res.push_back({a, ex});
  }
  if (N != 1) res.push_back({N, 1});
  return res;
}

int main() {
  long long N;
  cin >> N;
  if (N == 1) {
    cout << 0 << endl;
    return 0;
  }
  long long ans = 0;
  const auto &res = prime_factorize(N);
  for (auto p : res) {
    long long x = p.second;
    long long b = 1;
    while(b <= x) {
      x -= b;
      b++;
      ++ans;
    }
  }
  cout << ans << endl;
}


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

int main(){
	char s[110]={},t[110]={};
	
	cin>>s>>t;
	int N,M;
	for(int i=0;s[i]!=0;i++)
		N++;
	for(int i=0;t[i]!=0;i++)
		M++;
	
	sort(s,s+N);
	sort(t,t+M,greater<int>());
	
	int min;
	if(N<=M)
		min=N;
	else 
		min=M;
	
	for(int i=0;i<min;i++){
		if(s[i]<t[i]){
			cout<<"Yes"<<endl;
			return 0;
		}
		else if(t[i]<s[i]){
			cout<<"No"<<endl;
			return 0;
		}
	}
	if(N>=M)
		cout<<"No"<<endl;
	else
		cout<<"Yes"<<endl;
	
	return 0;
}

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

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define inv(n, a) for(int i = 0; i < n; i++) cin >> a[i]
#define MOD 1000000007
#define INF 1e7
#define LINF 1e15
typedef long long ll;
typedef long double ld;
using Graph = vector<vector<int>>;
// 'a' = 97 'z' = 122 => 'a' = 0 'z' = 25

int main() {
    int n;
    string s;
    cin >> n >> s;
    ll ans = 1;
    vector<int> v(25);
    rep(i, n){
        v[(int)s[i]-97]++;
    }
    rep(i, 26){
        ans %= MOD;
        ans = (ans%MOD * (v[i]+1))%MOD;
    }
    cout << ans-1 << endl;
    return 0;
}




Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <bitset>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
#define rep(i,n) for(i=1 ; i < (n); ++i)
#define rrep(i,n) for(i  1; i <= (n); ++i)
#define drep(i,n) for(i  (n)-1; i >= 0; --i)
#define fin(ans) cout<<(ans)<<endl
#define P 1000000007
#define STI(s) atoi(s.c_str())//string to int
#define mp(p,q) make_pair(p,q)
#define Sort(a) sort(a.begin(),a.end())
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const int INF = INT_MAX;
const long long LLINF = 1LL<<60;
//g++ -std=c++1z main.cpp
//./a.exe

bool isPrime(int x){
    int i;
    if(x < 2)return 0;
    else if(x == 2) return 1;
    if(x%2 == 0) return 0;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return 0;
    return 1;
}

int main(void){ios::sync_with_stdio(false);cin.tie(0);
//////////////////////////////////////////////////////
  int i,n,a,ans;
  cin >> n;
  rep(i,10){
     a = i*100 + i*10 + i;
     if(a>=n){
         ans = a;
           break;
     }
  }
  cout << ans << endl;
///////////////////////////////////////////////////////
return 0;}

Measured memory_bytes: 256
#include <bits/stdc++.h>  // ver1.8
#define int long long
#define ALL(v) (v).begin(),(v).end()
#define Vi vector<int>
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repeq(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define repreq(i,a,b) for(int i=a;i>=b;i--)
#define leng(n) (int)(log10(n)+1)
#define INF 9000000000000000000  //  9.0 * 10^18
#define MOD 1000000007  //  10^9 + 7
#define PAI 3.14159265358979
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm

signed main() {
  cout << fixed << setprecision(14);
  string s;
  cin >> s;
  if(s.size()==3) reverse(ALL(s));
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 256
from sys import stderr
from fractions import gcd
from collections import defaultdict
def lcm(n,m): return n*m//gcd(n,m)
def func(i,l,n): return i*l//n + 1
N,M = map(int,input().split())
S = input()
T = input()
l = lcm(N,M)
dicS = defaultdict(int)
for i in range(0,len(S)):
    dicS[i+1] = func(i,l,N)
dicT = defaultdict(int)
for i in range(0,len(T)):
     dicT[func(i,l,M)] = i+1
print(dicS,file=stderr)
print(dicT,file=stderr)

flag = True
for i in range(1,N+1):
    if dicS[i] in dicT.keys():
        if S[i-1] != T[dicT[dicS[i]]-1]:
            flag = False
            break
if flag: print(l)
else: print(-1)

Measured memory_bytes: 31180
import sys
import math
import numpy as np
import copy


class unionfind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0 for i in range(n)]
        self.groupnum = n

    def unite(self, a, b):
        pa = self.find(a)
        pb = self.find(b)
        if pa == pb:
            return
        if(self.rank[pa] < self.rank[pb]):
            self.parent[pa] = pb
        else:
            self.parent[pb] = pa
            if self.rank[pa] == self.rank[pb]:
                self.rank[pa] += 1
        self.groupnum -= 1

    def same(self, a, b):
        pa = self.find(a)
        pb = self.find(b)
        return pa == pb

    def find(self, a):
        if self.parent[a] == a:
            return a
        p = self.find(self.parent[a])
        self.parent[a] = p
        return p
    


def main():
    n, m = map(int, input().split())
    edges = [[] for i in range(n)]

    edge_list = []

    for i in range(m):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        edges[a].append(b)
        edges[b].append(a)
        edge_list.append((a, b))

    cnt = 0
    # 除外する辺ごとに。
    for i in range(m):
        uf = unionfind(n)
        for j in range(m):
            if i == j:
                continue
            uf.unite(edge_list[j][0], edge_list[j][1])
        if uf.groupnum >= 2:
            cnt += 1


    print(cnt)
    return 0

if __name__ == '__main__':
    sys.exit(main())

Measured memory_bytes: 12224
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
signed main(){
  Int n;
  double l;
  while(cin>>n>>l,n){
    vector<double> s(n),t(n),u(n);
    for(Int i=0;i<n;i++) cin>>s[i]>>t[i]>>u[i];
    auto check2=[&](double x,double y){
      y=min(y+x*s[0],l);
      for(Int i=0;i<n;i++){
	y+=(x-u[i])*(t[i]-s[i]);
	if(y<=0) return double(-1);
	y=min(y,l);
	if(i+1<n)
	  y=min(y+x*(s[i+1]-t[i]),l);
      }
      y=min(y+x*(86400-t[n-1]),l);
      return y;
    };
    auto check=[&](double x){
      if(check2(x,l)<0) return false;
      if(check2(x,l)==l) return true;
      double lb=0,ub=l;
      for(Int i=0;i<50;i++){
	double mid=(lb+ub)/2;
	if(check2(x,mid)<0) lb=mid;
	else ub=mid;
      }
      //cout<<x<<" "<<ub<<":"<<check2(x,ub)<<endl;
      return check2(x,ub)>=ub;
    };
    double lb=0,ub=*max_element(u.begin(),u.end());
    for(Int i=0;i<50;i++){
      double mid=(lb+ub)/2;
      if(check(mid)) ub=mid;
      else lb=mid;
    }
    //cout<<n<<" "<<l<<endl;
    cout<<fixed<<setprecision(12)<<ub<<endl;
  }
  return 0;
}



Measured memory_bytes: 5104
#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--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;

ll n, k;
ll a[200010];

ll calc(ll x){ // かけてx以下になるものの個数を返す
    ll tmp = 0;
    rep(i, n){
        if (a[i] > 0){
            ll ok = n;
            ll ng = -1;
            while(abs(ok - ng) > 1){
                ll mid = (ok + ng) / 2;
                if (a[mid] * a[i] > x) ok = mid;
                else ng = mid;
            }
            tmp += ok;
        }
        else if (a[i] < 0){
            ll ok = n;
            ll ng = -1;
            while(abs(ok - ng) > 1){
                ll mid = (ok + ng) / 2;
                if (a[mid] * a[i] <= x) ok = mid;
                else ng = mid;
            }
            tmp += n - ok;
        }
        else if (x >= 0) tmp += n;
        
        if (a[i] * a[i] <= x) tmp--;
    }
    return tmp / 2;
}


bool isOK(ll x, ll key) {
    ll cnt = calc(x); // かけてx以下のペアの個数
    if (cnt >= key) return true;
    else return false;
}

ll binary_search(ll key) {
    ll ng = -1e+18 + 100;
    ll ok = 1e+18 - 100;
    while (abs(ok - ng) > 1) {
        ll mid = (ok + ng) / 2;
        if (isOK(mid, key)) ok = mid; // かけてmid以下のペアがk個以下か？
        else ng = mid;
    }
    return ok;
}


int main(){
    cin >> n >> k;
    rep(i, n) cin >> a[i];
    sort(a, a+n);

    cout << binary_search(k) << endl;    

    return 0;
}


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

using namespace std;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    const int mod=1000000007;
    int n;
    cin >> n;
    vector<int> c((1<<n),0);
    for(int i=0;i<(1<<n);i++) c[i]=__builtin_popcount(i);
    vector<vector<int>> v(n,vector<int>(n,0));
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin >> v[i][j];
    vector<int> dp((1<<n),0);
    dp[0]=1;
    for(int i=0;i<n;i++)
    {
        for(int m=0;m<(1<<n);m++)
        {
            if(c[m]!=i) continue;
            for(int j=0;j<n;j++) if(v[i][j]==1&&(m&(1<<j))==0) dp[m^(1<<j)]=(dp[m^(1<<j)]+dp[m])%mod;
        }
    }
    cout << dp[(1<<n)-1] << "\n";
    return 0;
}


Measured memory_bytes: 16640
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'

using namespace std;

main()
{
    fast;
    int n;
    cin>>n;
    if (n<1000)
        cout<<"ABC\n";
    else
        cout<<"ABD\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,x,n) for(int i=(x);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define int long long
using namespace std;
const int MOD=1e9+7;
const int INF=1e9;
const double ESP=1e-5;
template<typename T> void cmax(T &a, T b) {a = max(a, b);}
template<typename T> void cmin(T &a, T b) {a = min(a, b);}

int d[100005];
signed main(){
  int n;
  cin>>n;
  rep(i,n){
    int a,b;
    cin>>a>>b;
    a--;
    d[a]++;
    d[b]--;
  }
  int ans=0;
  rep(i,100000)d[i+1]+=d[i];
  loop(i,1,100001)if(d[i]>=i)ans=i;
  cout<<ans<<endl;
 return 0;
}



Measured memory_bytes: 3884
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/stack:512000000")
#include<utility>
#include<iostream>
#include<fstream>
#include<vector>
#include<array>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<functional>
#include<random>
#include<climits>
#include<queue>
#include<stack>
#include<deque>
#include<bitset>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<cassert>
#include<ccomplex>

#ifdef ONLINE_JUDGE
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("unroll-loops")
#endif

//4Head

#define all(x) x.begin(), x.end()
#define mp make_pair
#define X first
#define Y second

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
mt19937_64 gen(time(nullptr));

ll const mod = 1e9 + 7;

namespace {
	ll mul(ll a, ll b) {
		ll val = a * b - (ll)((ld)a * b / mod) * mod;
		if (val < 0) val += mod;
		if (val >= mod) val -= mod;
		return val;
	}

	ll poww(ll a, ll b) {
		ll val = 1;
		a %= mod;
		while (b > 0) {
			if (b % 2) val = mul(a, val);
			a = mul(a, a);
			b >>= 1;
		}
		return val % mod;
	}

	ll inv(ll a) {
		return poww(a, mod - 2);
	}
}

int const maxn = 3e5 + 5;

int a[200][200];
int dp[500][500];

void solveA() {

	int n, m; cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char c; cin >> c;
			a[i][j] = (c == '#');
			dp[i][j] = n * m + 1000;
		}
	}

	if (a[0][0]) {
		dp[0][0] = 1;
	} else dp[0][0] = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i][j]) {
				// left
				if (j) {
					if (a[i][j - 1]) dp[i][j] = min(dp[i][j], dp[i][j - 1]);
					else dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
				}
				// up
				if (i) {
					if (a[i - 1][j]) dp[i][j] = min(dp[i][j], dp[i - 1][j]);
					else dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
				}
			} else {
				// left
				if (j) {
					dp[i][j] = min(dp[i][j], dp[i][j - 1]);
				}
				// up
				if (i) {
					dp[i][j] = min(dp[i][j], dp[i - 1][j]);
				}
			}
		}
	}

	cout << dp[n - 1][m - 1] << endl;
}



signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	solveA();

	return 0;
}

/*
5
2 6 15 5 10

4
2 6 15 5

*/

Measured memory_bytes: 512
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

s = input()
if len(s) % 2 != 0:
  print("No")
  exit()
else:
  for i in range(0,len(s),2):
    if not (s[i] == "h" and s[i+1] == "i"):
      print("No")
      exit()
print("Yes")

Measured memory_bytes: 38384
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = [1]
    t = [True] * n

    t[1] = True
    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p


@mt
def slv(Q, LR):
    N = 100000
    p = eratosthenes(N)
    qt = [0] * N
    for i in range(2, N):
        qt[i] = qt[i-1]
        if i % 2 == 0:
            continue

        q = (i+1)//2
        qi = bisect.bisect_left(p, q)
        ii = bisect.bisect_left(p, i)
        if qi != len(p) and p[qi] == q and ii != len(p) and p[ii] == i:
            qt[i] += 1

    for l, r in LR:
        print(qt[r] - qt[l-1])
    # ans = 0
    # return ans


def main():
    Q = read_int()
    LR = [read_int_n() for _ in range(Q)]
    # print(slv(Q, LR))
    slv(Q, LR)


if __name__ == '__main__':
    main()


Measured memory_bytes: 92244
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define MAX_P 100000 
int a[MAX_P];
int P;
int getLIS(){
	int dp[MAX_P];
	fill(dp, dp + P, INT_MAX);
	rep(i,P) *lower_bound(dp, dp+P, a[i]) = a[i];
	return lower_bound(dp, dp+P, INT_MAX) - dp;
}
int main(void){
    cin >> P;
    rep(i,P)cin >> a[i];
    cout << getLIS() << endl;
}


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

int main(){
	int N,M,D[1000],C[1000],dp[1050][1050];
	cin >> N >> M;
	for(int i = 0;i < N;i++) cin >> D[i];
	for(int i = 0;i < M;i++) cin >> C[i];
	for(int i = 0;i <= N;i++){
		for(int j = 0;j <= M;j++){
			dp[i][j] = 10000000000;
		}
	}
	dp[0][0] = 0;
	for(int i = 0;i <= N;i++){
		for(int j = 1;j <= M;j++){
			if(i == 0) dp[i][j] = min(dp[i][j],dp[i][j - 1]);
			dp[i][j] = min(dp[i][j - 1],dp[i - 1][j - 1] + D[i - 1] * C[j - 1]);
		}
	}
	cout << dp[N][M] << endl;
	return 0;
}

Measured memory_bytes: 4504
#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
#include<map>
#include<vector>

using namespace std;

int main() {
	int H, W;
	int h, w;
	int HW;
	int hw;
	cin >> H >> W;
	cin >> h >> w;
	HW = H * W;
	hw = (H - h) * (W - w);
	cout << hw << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define rep(i, n) for(int i = 0; i < n; i++)
#define iter(m) for(auto it = m.begin(); it != m.end(); it++)
#define iterr(m) for(auto it = m.rbegin(); it != m.rend(); it++)
#define N 500500
#define PI 3.14159265358979323846264338327950L
#define speed ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    
signed main(){
    speed;
    string s; cin >> s;
    int ans = 0;
    int cnt = 0;
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == 'R') cnt++;
        else cnt = 0;
        ans = max(ans, cnt);
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 3644
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <stack>

using namespace std;

typedef long long i64;
typedef i64 int_t;
typedef vector<int_t> vi;
typedef vector<vi> vvi;

typedef pair<int_t, int_t> pi;

#define tr(c, i) for(auto i = (c).begin(); i != (c).end(); i++)
#define pb push_back
#define sz(a) int((a).size())
#define all(c) (c).begin(), (c).end()
#define REP(s, e, i) for(i=(s); i < (e); ++i)

int main(int argc, char *argv[]) {

  i64 N, u, v, i;
  cin >> N >> u >> v;
  u--; v--;
  vvi edges(N);  
  REP(0, N-1, i) {
    i64 A, B;
    cin >> A >> B;
    A--; B--;
    edges[A].pb(B);
    edges[B].pb(A);
  }

  vi dists_u(N, -1), dists_v(N, -1);
  auto compute_dist = [&](i64 a, vi &dists) {
    stack<i64> st;
    st.push(a);
    dists[a] = 0;
    while(!st.empty()) {
      i64 u = st.top();
      st.pop();
      for(auto e: edges[u]) {
	if(dists[e] == -1) {
	  dists[e] = dists[u] + 1;
	  st.push(e);
	}
      }
    }
  };

  compute_dist(u, dists_u);
  compute_dist(v, dists_v);

  i64 d_uv = dists_u[v];
  //cout << "d_uv " << d_uv << endl;
  i64 max_dist = 0;
  REP(0, N, i) {
    if(dists_v[i] >= d_uv / 2 && dists_u[i] < dists_v[i]) {
      max_dist = max(max_dist, dists_v[i]);
      //cout << "dists_v " << dists_v[i] << endl;
    }
  }
  
  cout << max_dist - 1 << endl;
  return 0;
}


Measured memory_bytes: 7936
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<(n);++i)
#define rep2(i,a,b) for (ll i=(a);i<(b);++i)
#define debug(x) cout << #x << '=' << x << endl
#define all(v) (v).begin(),(v).end()
const ll MOD=1e9+7;
//const ll MOD=998244353;
const ll INF=1e9;
const ll IINF=1e18;
const double EPS=1e-8;
const double pi=acos(-1);

template<class T> inline bool chmin(T &a,T b){
    if (a>b){a=b; return true;}
    return false;
}
template<class T> inline bool chmax(T &a,T b){
    if (a<b){a=b; return true;}
    return false;
}


ll gcd(ll x,ll y){
    if (y==0) return x;
    return gcd(y,x%y);
}
ll lcm(ll x,ll y){
    return x/gcd(x,y)*y;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,M; cin >> N >> M;
    vector<ll> A(N);
    rep(i,N) cin >> A[i],A[i]/=2;
    ll g=A[0];
    rep(i,N-1) g=lcm(g,A[i+1]);
    ll ans=(M/g+1)/2;
    rep(i,N) if ((g/A[i])%2==0) ans=0;
    cout << ans << endl;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<cmath>
#include<climits>
#include<algorithm>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<utility>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<map>
#include<list>

using namespace std;
using ll = long long;

#define in(s) cin >> s
#define out(s) cout << s << endl
#define rep(i,n) for(int i=0; i<n; i++)
#define rept(i,a,b) for(int i=a; i<b; i++)
#define pcnt __builtin_popcount
#define pcntll(x) __builtin_popcountll(x)
#define DMAX DBL_MAX;
#define IMIN INT_MIN;
#define IMAX INT_MAX;

const long long MOD = 1e9+7;
const long long MAX = 3e5+1;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    string S, T;
    in(S); in(T);
    bool flag=true;
    if (S.size()+1 != T.size()) flag = false;
    for (int i=0; i<S.size(); i++) {
        if (S[i] != T[i]) flag = false;
    }
    cout << ((flag)? "Yes": "No") << endl;



    return 0;
}


Measured memory_bytes: 3648
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <assert.h>
#include <cstdio>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr long long int infll = 1001001001001001LL;
constexpr int INF = 1000000007;
constexpr int inf = 1000000007;
const int mod = 1000000007;


//----------------------------------------------------------------

int main()
{
    ll n;
    cin >> n;
    set<string> ans;
    string s;
    for (ll i = 0; i < n; i++)
    {
        cin >> s;
        ans.insert(s);
    }
    cout << ans.size() << endl;
}


Measured memory_bytes: 19180
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define INF 1000000000
#define rep(i,a,b) for(int i =(a);i<(b);i++)
#define fs first
#define ss second
inline int Scan() {
    int x=0;int f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}

template<typename T, typename U>
static inline void amin(T &x, U y)
{
    if (y < x)
        x = y;
}

// call by reference is used in x
template<typename T, typename U>
static inline void amax(T &x, U y)
{
    if (x < y)
        x = y;
}
//////////////////////////////////////end of template//////////////////////////////////////

int main(){

 int n,k;
 cin >> n >> k;
 int a[n+1];
 rep(i,1,n+1) cin >> a[i];
 a[0] = 0;
 vector<int> dp(n+1,INT_MAX);
 
 dp[1] = 0;
 for(int i = 2;i<=n;i++){
	 for(int j =1;j<=k && i-j>=1;j++){
	 dp[i] = min(dp[i],dp[i-j] + abs(a[i-j] - a[i]));
  }
	// cout << dp[i] << endl;	 
 }
 
 cout << dp[n] <<endl;
   
	   
} 





Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (long long i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<double, double>;
using T = tuple<int, int, bool>;
const int INF = 1001001007;
const int mod = 1000000007;
//const int MOD = 998244353;
const ll inf = 1e18;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

int main() {
    int n, k; cin >> n >> k;
    string s; cin >> s;
    int le = 0;
    int ri = 0;
    int ans = 1;
    int so = 0; if (s[0] == '0') so++;
    while (ri != n-1){
        int x = so;
        if (s[ri] == '1' && s[ri+1] == '0') x++;
        if (x <= k){
            ri++;
            so = x;
        }
        else {
            if (s[le] == '0' && s[le+1] == '1') so--;
            le++;
        }
        ans = max(ans,ri-le+1);
        //cout << le << " " << ri << " " << so << endl;
    }
    cout << ans << endl;
}

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

# define REP(i,n) for (int i=0;i<(n);++i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
typedef long long int ll;
typedef pair<ll,ll> P_ii;
typedef pair<double,double> P_dd;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}

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

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}


const int MOD = 1000000007;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;

void addM(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

void mulM(long long &a, long long b) {
    a = ((a%MOD)*(b%MOD))%MOD ;
}

const int MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

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

    vector<pair<ll,ll>> v(N);

    REP(i,N) cin >> v[i].second >> v[i].first;
    sort(all(v));

    bool ans = true;
    ll now = 0;
    REP(i,N){
        now += v[i].second;
        if(now > v[i].first){
            ans = false;
            break;
        }
    }

    Yes(ans)

    return 0;
}


Measured memory_bytes: 3328
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String T = sc.next();
		sc.close();

		StringBuffer sb = new StringBuffer();

		if(T.charAt(0) == '?') {
			sb.append('D');
			for(int i = 1; i < T.length(); i++) {
				if(T.charAt(i) != '?') {
					sb.append(T.charAt(i));
					continue;
				}else {
					if(T.charAt(i - 1) == 'P') {
						sb.append('D');
					}else {
						sb.append('D');
					}
				}
			}
		}else {
			for(int i = 0; i < T.length(); i++) {
				if(T.charAt(i) != '?') {
					sb.append(T.charAt(i));
					continue;
				}else {
					if(T.charAt(i - 1) == 'P') {
						sb.append('D');
					}else {
						sb.append('D');
					}
				}
			}
		}
		System.out.println(sb.toString());
	}

}

Measured memory_bytes: 42752
#include <bits/stdc++.h>
using namespace std;
long long pow(long long a,long long b,long long q){
	long long res=1;
	while(b){
		if(b%2)res=res*a%q;
		b/=2;
		a=a*a%q;
	}return res;
}
int n,m,q=1e9+7;
int main(){
	cin>>n>>m;
	cout<<pow(n,m,q)<<endl;
	return 0;
}


Measured memory_bytes: 3104
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

# (nxt, cnt)
D = {
    0: (0, 1),
    1: (2, 1),
    2: (4, 1),
    3: (6, 1),
    4: (8, 1),
    5: (1, 2),
    6: (3, 2),
    7: (5, 2),
    8: (7, 2),
    9: (9, 2),
}

M = INT()
C = Counter()
for i in range(M):
    d, c = MAP()
    C[d] += c

def calc(a, cnt):
    sm = 0
    odd = []
    while cnt > 1:
        if cnt % 2 == 1:
            odd.append(a)
            cnt -= 1
        cnt //= 2
        sm += cnt * D[a][1]
        a = D[a][0]
    for b in odd:
        a += b
        sm += 1
        if a >= 10:
            a = int(str(a)[0]) + int(str(a)[1])
            sm += 1
    return (a, sm)

ans = 0
A = []
for k, v in C.items():
    a, sm = calc(k, v)
    ans += sm
    A.append(a)

for i in range(1, len(A)):
    A[i] += A[i-1]
    ans += 1
    if A[i] >= 10:
        A[i] = int(str(A[i])[0]) + int(str(A[i])[1])
        ans += 1
print(ans)


Measured memory_bytes: 3380
#include <bits/stdc++.h>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int INF = 2100100100;
const int MOD = 1e9 + 7;

// 多次元 vector 生成
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
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;
}

int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    string Sd, T;
    cin >> Sd >> T;

    string ans = "{";
    REP(i, Sd.size() - T.size() + 1) {
        string tmp = Sd;
        REP(j, T.size()) {
            if (tmp[i + j] == '?') {
                tmp[i + j] = T[j];
            } else if (tmp[i + j] != T[j]) {
                tmp = "UNRESTORABLE";
                break;
            }
        }
        // cout << i << " " << tmp << endl;
        if (tmp == "UNRESTORABLE") {
            continue;
        } else {
            REP(i, tmp.size()) {
                if (tmp[i] == '?') {
                    tmp[i] = 'a';
                }
            }
            // cout << tmp << endl;
            chmin(ans, tmp);
        }
    }
    if (ans == "{") {
        cout << "UNRESTORABLE" << endl;
    } else {
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
#include <random>
#include <string.h>
#include <cmath>
#include <unordered_map>
#include <cstdio>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long ll;

ll gcd(ll x, ll y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
ll lcm(ll x, ll y) {
	return x / gcd(x, y)*y;
}
ll kai(ll x, ll y, ll m) {
	ll res = 1;
	for (ll i = x - y + 1; i <= x; i++) {
		res *= i; res %= m;
	}
	return res;
}
ll mod_pow(ll x, ll y, ll m) {
	ll res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}

ll comb(ll x, ll y, ll m) {
	if (y > x)return 0;
	return kai(x, y, m) * mod_pow(kai(y, y, m), m - 2, m) % m;
}

int n, q, x[300010], w[300010];
int d[520][100010];
int p[10];

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> x[i] >> w[i];
	for (int i = 1; i <= min(n, 511); i++) {
		int k = i / 2;
		for (int j = 0; j <= 100000; j++)d[i][j] = d[k][j];
		for (int j = 0; j <= 100000 - w[i]; j++)d[i][j + w[i]] = max(d[i][j + w[i]], d[k][j] + x[i]);
		for (int j = 1; j <= 100000; j++)d[i][j] = max(d[i][j], d[i][j - 1]);
	}
	cin >> q;
	for (int i = 0; i < q; i++) {
		int v, l; cin >> v >> l;
		int ans = 0;
		int m = 0;
		while (512 <= v) {
			p[m] = v;
			m++;
			v /= 2;
		}
		for (int j = 0; j < (1 << m); j++) {
			int cnt1 = 0, cnt2 = 0;
			for (int k = 0; k < m; k++)if (j&(1 << k))cnt1 += x[p[k]], cnt2 += w[p[k]];
			if (l < cnt2)continue;
			ans = max(ans, d[v][l - cnt2] + cnt1);
		}
		cout << ans << endl;
	}
}


Measured memory_bytes: 205284
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<functional>
#include<math.h>
using namespace std;
#define N (1000000000+7)
#define INF 1e16
typedef long long ll;
typedef pair<ll,ll> P;
 



int main(void){
    string s;
    cin>>s;
    int n = s.length();
    int k1 = (n-1)/2;
    int k2 = (n+3)/2;
    string t = s;
    reverse(t.begin(),t.end());
    if(s==t){
        string t1 = s.substr(0,k1);
        string t2 = s.substr(k2-1,n-k2+1);
        //cout<<t1<<" "<<t2<<endl;
        string u1 = t1;
        string u2 = t2;
        reverse(u1.begin(),u1.end());
        reverse(u2.begin(),u2.end());
        if(t1 == u1 && t2 == u2)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    else cout<<"No"<<endl;
    return 0;
}



Measured memory_bytes: 256
#include<iostream>

int n,m,p[50][50],w[100][100];
int x,y,tx,ty;

bool match(int xx, int yy){
	for(int i=0; i<m; i++)
		for(int k=0; k<m; k++)
			if(p[i][k] != w[i+yy][k+xx] && p[i][k] != -1)
				return false;
	for(int i=0; i<m; i++){
		for(int k=0; k<m; k++){
			if(p[i][k] != -1){
				tx = k+xx,ty = i+yy;
				return true;
			}
		}
	}
}

bool match90(int xx, int yy){
	for(int i=0; i<m; i++)
		for(int k=0; k<m; k++)
			if(p[i][k] != w[(m-k-1)+yy][i+xx] && p[i][k] != -1)
				return false;
	for(int k=m-1; k>=0; k--){
		for(int i=0; i<m; i++){
			if(p[i][k] != -1){
				tx = i+xx,ty = m-k+yy-1;
				return true;
			}
		}
	}
}

bool match180(int xx, int yy){
	for(int i=0; i<m; i++)
		for(int k=0; k<m; k++)
			if(p[i][k] != w[(m-i-1)+yy][(m-k-1)+xx] && p[i][k] != -1)
				return false;
	for(int k=m-1; k>=0; k--){
		for(int i=m-1; i>=0; i--){
			if(p[i][k] != -1){
				tx = m-i+xx-1,ty = m-k+yy-1;
				return true;
			}
		}
	}
}

bool match270(int xx, int yy){
	for(int i=0; i<m; i++)
		for(int k=0; k<m; k++)
			if(p[i][k] != w[k+yy][(m-i-1)+xx] && p[i][k] != -1)
				return false;
	for(int k=0; k<m; k++){
		for(int i=m-1; i>=0; i--){
			if(p[i][k] != -1){
				tx = m-i+xx-1,ty = k+yy;
				return true;
			}
		}
	}
}

void solve(){
	x = 1000;
	y = 1000;
	for(int i=0; i<=n-m; i++){
		for(int k=0; k<=n-m; k++){
			if(i>y+m)
				return;
			if(match(k,i))
				if(ty < y || (ty == y && tx < x))
					x = tx,y = ty;
 			if(match90(k,i))
				if(ty < y || (ty == y && tx < x))
					x = tx,y = ty;
			if(match180(k,i))
				if(ty < y || (ty == y && tx < x))
					x = tx,y = ty;
			if(match270(k,i))
				if(ty < y || (ty == y && tx < x))
					x = tx,y = ty;
		}
	}
}

int main(){
	while(true){
		std::cin >> n >> m;
		if(!n && !m)
			return 0;
		for(int i=0; i<n; i++)
			for(int k=0; k<n; k++)
				std::cin >> w[i][k];
		for(int i=0; i<m; i++)
			for(int k=0; k<m; k++)
				std::cin >> p[i][k];
		solve();
		if(x == 1000 && y == 1000)
			std::cout << "NA\n";
		else
			std::cout << x+1 << ' ' << y+1 << std::endl;
	}
}

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

int main() {
	
	//vector<int> a(n);  sort(a.begin(),a.end());
	//cout << "test" << endl;

	cin.tie(0);
	ios::sync_with_stdio(false);
	
	//string ans="YES";


	int n;
	cin >> n;
	
	vector<pair<int,int>> a(n);
	rep(i,n) {
		a[i].second=i;
		cin >> a[i].first;
	}
	
	sort(a.begin(),a.end());
	
	rep(i,n) cout << a[i].second+1 << " ";
	cout << endl;
	
	
	
	
	
	//cout << ans << "\n";
	
	
	return 0;

    }

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  vector<int> p(n);
  for (int i = 0; i < n; i++) {
    cin >> p.at(i);
  }
  int ans = 0;
  for (int i = 1; i < n - 1; i++) {
    if (p.at(i) > p.at(i + 1) && p.at(i) < p.at(i - 1)) {
      ans++;
    }
    if (p.at(i) < p.at(i + 1) && p.at(i) > p.at(i - 1)) {
      ans++;
    }
  }
  cout << ans << endl;
}
    

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
int vector_finder(std::vector<ll> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

int main() {
  string S; cin >> S;
  ll ans = 0;
  ll cnt = 0;
  for(int i = 0; i < S.size(); ++i) {
    if(S[i] == 'A' || S[i] == 'T' || S[i] == 'G' || S[i] == 'C') {
      cnt++;
    } else {
      if(ans < cnt) ans = cnt;
      cnt = 0;
    }
    if(i == S.size() - 1) {
      if(ans < cnt) ans = cnt;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
import Control.Monad
import Data.List

f c [] [] = c
f c (a:as) [] = if a=='x' then f (c+1) as [] else -2
f c [] (b:bs) = if b=='x' then f (c+1) [] bs else -2
f c (a:as) (b:bs)
  | a==b      = f c as bs
  | a=='x'    = f (c+1) as (b:bs)
  | b=='x'    = f (c+1) (a:as) bs
  | otherwise = -2

g s = flip div 2 $ f 0 s $ reverse s

main = getLine >>= print . g

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

int ans=-1;
int N,M,X,sumC=0;
vector<vector<int>> C;
vector<int> C_list;
vector<int> U;

void alls(int loop){
	int loop_in;
	if(loop+1<N){
		alls(loop+1);
		for(loop_in=0;loop_in<M;loop_in++){
			U[loop_in]+=C[loop][loop_in];
		}
		sumC+=C_list[loop];
		alls(loop+1);
		for(loop_in=0;loop_in<M;loop_in++){
			U[loop_in]-=C[loop][loop_in];
		}
		sumC-=C_list[loop];
	}else{
		for(loop_in=0;loop_in<M;loop_in++){
			if(U[loop_in]<X){
				break;
			}
			if(loop_in==M-1&&(ans==-1||ans>sumC)){
				ans=sumC;
			}
		}
		for(loop_in=0;loop_in<M;loop_in++){
			U[loop_in]+=C[loop][loop_in];
		}
		sumC+=C_list[loop];
		for(loop_in=0;loop_in<M;loop_in++){
			if(U[loop_in]<X){
				break;
			}
			if(loop_in==M-1&&(ans==-1||ans>sumC)){
				ans=sumC;
			}
		}
		for(loop_in=0;loop_in<M;loop_in++){
			U[loop_in]-=C[loop][loop_in];
		}
		sumC-=C_list[loop];
	}
	return;
}

int main(){
	cin >> N >> M >> X;
	C.resize(N,vector<int>(M));
	C_list.resize(N);
	U.resize(M,0);
	int loop,loop2;
	for(loop=0;loop<N;loop++){
		cin >> C_list[loop];
		for(loop2=0;loop2<M;loop2++){
			cin >> C[loop][loop2];
		}
	}
	alls(0);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3636