akhauriyash/Code-Regression huggingface dataset:
A, B = map(int, input().split())

minA = A / 0.08
maxA = (A+1) / 0.08
minB = B / 0.1
maxB = (B+1) / 0.1

if minB <= minA and minA < maxB: print(int(minA) + (1 if minA > int(minA) else 0))
elif minA <= minB and minB < maxA: print(int(minB) + (1 if minB > int(minB) else 0))
else: print("-1")



Measured memory_bytes: 3060
"""
# 標準入力取得
## 文字列
 = sys.stdin.readline().rstrip()
 = list(sys.stdin.readline().rstrip())

## 数値
 = int(sys.stdin.readline())
 = map(int, sys.stdin.readline().split())
 = list(map(int, sys.stdin.readline().split()))
 = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]
"""

import math
import sys
import itertools
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

if __name__ == "__main__":
    D,N = map(int, sys.stdin.readline().split())
    if N != 100:
        print((100**D)*N)
    else:
        print((100**D)*101)

Measured memory_bytes: 5072
l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
n = int(input())
print(l[n - 1])


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

int main(){
  vector<int> A(9);
  for(int i=0; i<9; i++){
    cin>>A.at(i);
  }
  int N;
  cin>>N;
  vector<int> b(N);
  for(int i=0; i<N; i++){
    cin>>b.at(i);
  }
  vector<bool> c(9,false);
  for(int i=0; i<N; i++){
    for(int j=0; j<9; j++){
      if(b.at(i)==A.at(j)){
        c.at(j)=true;
      }
    }
  }
  if(c.at(0)==true&&c.at(1)==true&&c.at(2)==true){
    cout<<"Yes"<<endl;
  }
  else if(c.at(3)==true&&c.at(4)==true&&c.at(5)==true){
    cout<<"Yes"<<endl;
  }
  else if(c.at(6)==true&&c.at(7)==true&&c.at(8)==true){
    cout<<"Yes"<<endl;
  }
  else if(c.at(0)==true&&c.at(3)==true&&c.at(6)==true){
    cout<<"Yes"<<endl;
  }
  else if(c.at(1)==true&&c.at(4)==true&&c.at(7)==true){
    cout<<"Yes"<<endl;
  }
  else if(c.at(2)==true&&c.at(5)==true&&c.at(8)==true){
    cout<<"Yes"<<endl;
  }
  else if(c.at(0)==true&&c.at(4)==true&&c.at(8)==true){
    cout<<"Yes"<<endl;
  }
  else if(c.at(2)==true&&c.at(4)==true&&c.at(6)==true){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}

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

using ll = long long;
#define ALL(c) (c).begin(), (c).end()
const int MOD = 1000000007;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    int t = 0;
    int b = n - 1;

    int c = 0;
    while (t < b) {
        if (s[t] != s[b]) {
            c++;
            if (s[t] == 'x') {
                t++;
            } else if (s[b] == 'x') {
                b--;
            } else {
                cout << -1 << endl;
                return 0;
            }
        } else {
            t++;
            b--;
        }
    }

    cout << c << endl;
}


Measured memory_bytes: 512
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

class Data{
public:
	int a,b,c,i;
};

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

	int N=in();
	vector<Data> D(N);
	REP(i,N){
		D[i].a = in();
		D[i].i = i;
	}
	REP(i,N){
		D[i].b = in();
	}
	REP(i,N-1){
		D[i].c = in();
	}
	D[N-1].c=0;
	//sort(ALL(D),[](Data& l,Data& r){return l.a<r.a;});
	int sum = 0;
	REP(i,N){
		int index = D[i].a-1;
		sum += D[index].b;
		
		if(i>0){
			int old_index = D[i-1].a-1;
			if(index==old_index+1){
				sum += D[old_index].c;
			}
		}
	}
	out(sum);
	return 0;
}


Measured memory_bytes: 256
def partition(A,p,r):
    x = A[r]
    i = p 
    j = p+1
    while i < r:
        if A[i] <= x:
            i += 1
            if i == j:
                j += 1
        else:
            while j <= r:
                if A[j] <= x:
                    if j == r:
                        temp = A[j]
                        A[j] = A[i]
                        A[i] = "[{}]".format(temp)
                        i += 1
                        i = r
                        break 
                    temp = A[j]
                    A[j] = A[i]
                    A[i] = temp
                    i += 1
                    break
                else:
                    j += 1
    return A
    
    
n = int(input())
A = list(map(int,input().split()))
print(*partition(A,0,n-1))

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

int main(){
	ll n;
	cin>>n;
	int ans=1000000;
	rep(i,n){
		ll a;
		cin>>a;
		int count=0;
		while(a%2==0){a/=2;count++;}
		ans=min(ans,count);
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;

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

	    while (true) {
		    String line = br.readLine();
		    int a  = Integer.parseInt(line.split(" ")[0]);
		    String op = line.split(" ")[1];
		    int b  = Integer.parseInt(line.split(" ")[2]);

		    if("?".equals(op)) break;

		    if ("+".equals(op)) {
			    System.out.println(a + b);

		    } else if("-".equals(op)) {
			    System.out.println(a - b);

		    } else if("*".equals(op)) {
			    System.out.println(a * b);

		    } else if("/".equals(op)) {
			    System.out.println((int)(a / b));

		    }
	    }
	}
}

Measured memory_bytes: 24224
#include <bits/stdc++.h>
#include <ext/numeric>

using namespace std;
using namespace __gnu_cxx;

#define sz(v)           ((int)((v).size()))
#define clr(v, d)       memset(v, d, sizeof(v))
#define rep(i, v)       for(int i=0; i<sz(v); ++i)
#define lp(i, n)        for(int i=0; i<(int)(n); ++i)
#define lpi(i, j, n)    for(int i=(j); i<(int)(n); ++i)
#define lpd(i, j, n)    for(int i=(j); i>=(int)(n); --i)
//#define INF             1000000000
//#define INF             100000000000000

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

void init(){
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

const int N = 1e5+5;
const int M = 104;

int dp[N][2];

int arr[M];

int n, k;

bool solve(int cur_k, bool turn){
	if(cur_k < 0)
		return turn;
	int & cur = dp[cur_k][turn];
	if(cur != -1)
		return cur;
	lp(i, n)
		if(solve(cur_k - arr[i], !turn) == turn)
			return (cur = turn);
	return (cur = !turn);
}

int main()
{
	clr(dp, -1);
	cin >> n >> k;
	lp(i, n)
		cin >> arr[i];
	cout << (solve(k, 0)?"Second":"First");
	return 0;
}

Measured memory_bytes: 8832
#include <iostream>

int main(){
    long long n, m;
    std::cin >> n >> m;

    long long ans = (n - 2) * (m - 2);
    if(1 == n && 1 == m){
        ans = 1;
    }else if(1 == n || 1 == m){
        ans = n * m - 2;
    }else if(2 == n || 2 == m){
        ans = 0;
    }

    std::cout << ans << std::endl;

    return 0;
}

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

int main(){
  int n,i,j;
  cin>>n;
  int a[n];
  int sum,mi=10000000;
  for(i=0;i<n;i++)cin>>a[i];
  
  for(i=-100;i<=100;i++){
    sum=0;
    for(j=0;j<n;j++){
      sum+=(i-a[j])*(i-a[j]);
    }
    mi=min(mi,sum);
  }
  cout<<mi;
}

Measured memory_bytes: 256
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}
 
ll nCr(ll n, ll r){
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
 
//-----------------------ここから-----------

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

    priority_queue<ld, vector<pair<ld,ld>>, less<pair<ld,ld>>> qu;
    for(int i = 0; i < n; i++){
        ld a;
        cin >> a;
        qu.push(make_pair(a / 2.0, a));
    }
    int cnt = 0;
    while(cnt < m){
        pair<ld,ld> tmp = qu.top();
        qu.pop();

        pair<ld,ld> pu;
        pu.first = tmp.first / 2.0;
        pu.second = tmp.first;

        qu.push(pu);
        cnt++;
    }

    ll ans = 0;
    while(!qu.empty()){
        ans += floor(qu.top().second);
        qu.pop();
    }

    cout << ans << endl;


}

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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define INF         INT_MAX/3
#define LLINF       LLONG_MAX/3
#define MOD         (1000000007LL)
#define MODA(a, b)  a=((a)+(b))%MOD
#define MODP(a, b)  a=((a)*(b))%MOD
#define inc(i, l, r)   for(int i=(l);i<(r);i++)
#define dec(i, l, r)   for(int i=(r)-1;i>=(l);i--)
#define pb          push_back
#define se          second
#define fi          first
#define mset(a, b)  memset(a, b, sizeof(a))

using LL  = long long;
using G   = vector<vector<int>>;

int di[] = {0, -1, 0, 1};
int dj[] = {1, 0, -1, 0};
// }}}


LL cnt(LL n, LL i) {
    if(i > n) return 0;
//    cout << n/(i*2)*i << endl;
    return n/(i*2)*i + max(0LL, n%(i*2LL)-i+1);
}

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    LL a, b;
    cin >> a >> b;
    LL ans = 0;
//    while(true){
//        cin >> a >> b;
//        cout << cnt(a, b) << endl;
//    }
//    cout << cnt(a, b) << endl;
    for(LL i=1LL;i<=b;i<<=1LL){
        //if(i > b) break;
        if((cnt(b, i)-cnt(max(a-1LL, 0LL), i))%2 == 0){
            ans += 0;
        }else{
            ans += i;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <tuple>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <array>
#include <valarray>

using namespace std;

int main()
{
    int N;
    scanf("%d\n", &N);
    int even = 0;
    int odd = 0;
    for (int i = 0; i < N; ++i){
        int Ai;
        scanf("%d", &Ai); getchar();
        if (Ai % 2){
            ++odd;
        }else{
            ++even;
        }
    }
    if (odd % 2){
        puts("NO");
    }else{
        puts("YES");
    }
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

int lcm(int a,int b){
  return (a/__gcd(a,b))*b;
}

int N;
int A[25][25];
int ps[]={13,17,23};

int main(){
  while(1){
    scanf("%d",&N);
    if(N==0)break;
    memset(A,0,sizeof(A));
    int sz=1;
    rep(i,N){
      int D,T;
      scanf("%d%d",&D,&T);
      bool ok=true;
      rep(j,3)if(ps[j]==D)ok=false;
      if(ok)sz=lcm(sz,D);
      rep(j,D){
        int B;
        scanf("%d",&B);
        A[D][(j-T+D)%D]+=B;
      }
    }
    vector<int> sum(sz,0);
    int res=0;
    rep(i,3)res+=*max_element(A[ps[i]],A[ps[i]]+25);
    repl(i,1,25){
      bool ok=true;
      rep(j,3)if(ps[j]==i)ok=false;
      if(!ok)continue;
      rep(j,sz)sum[j]+=A[i][j%i];
    }
    res+=*max_element(all(sum));
    printf("%d\n",res);
  }
  return 0;
}



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

int selection_sort(vector<int>& a){
    int count_swap{0};

    for (int i = 0; i < a.size(); i++){
        int minj{i};
        for (int j = i; j < a.size(); j++){
            if (a[minj] > a[j]){
                minj = j;
            };
        }
        if (minj != i){
            swap(a[minj], a[i]);
            count_swap += 1;
        };
    };
    return count_swap;
}

int main(){

    int N{0};
    cin >> N;
    //#unique_ptr<array<int, N>> a;
    vector<int> a(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    int count_swap{0};
    count_swap = selection_sort(a);
    for (int i = 0; i < N; i++) {
        if (i) cout << " ";
        cout << a[i];
    }
    cout << endl << count_swap << endl;
    return 0;
}



Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
using ll = long long; // ll は long long　と同じとする。(int64_t)
int B[100005];
int main(){
    int N , K , Q;
    cin >> N >> K >> Q;
    for(int i = 1; i <= Q; i++){
        int t;
        cin >> t;
        B[t]++;
    }
    for(int i = 1; i <= N; i++){
        if(K + B[i] > Q){
            cout << "Yes" << endl;
        }
        else{
            cout << "No" << endl;
        }
    }
}


Measured memory_bytes: 1024
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
#include <functional>

#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 62;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}

ll conbinationMemo[100][100];

ll cmemoInit(){
    rep(i, 100){
        rep(j, 100){
            conbinationMemo[i][j] = -1;
        }
    }
}
 
ll nCr(ll n, ll r){
    if(conbinationMemo[n][r] != -1) return conbinationMemo[n][r];
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return conbinationMemo[n][r] = (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
 
//-----------------------ここから-----------
ll factorial[201000];
ll invfactorial[201000];

ll extGCD(ll a, ll b, ll &x, ll &y){
	if (b == 0){
		x = 1;
		y = 0;
		return a;
	}
 
	ll d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
ll nCrM(ll n, ll r){
	ll ret = factorial[n];
	ret *= invfactorial[n - r];
	ret %= MOD;
	ret *= invfactorial[r];
	ret %= MOD; 
	return ret;
}
int main(void){
    // factorial[0] = 1;

    // for (int i = 1; i < 201000; i++){
    //     factorial[i] = (factorial[i - 1] * i) % MOD;
    // }
    // for (int i = 0; i < 201000; i++){
    //     ll x, y;
    //     ll g = extGCD(factorial[i], MOD, x, y);
    //     while (x < 0) x += MOD;
    //     x %= MOD;
    //     invfactorial[i] = x;
    // }

    ll n, k;
    cin >> n >> k;
    ll ans = 0;

    vector<ll> sum1(n + 1, 0);
    for(ll i = 0; i <= n; i++){
        sum1[i + 1] = i + sum1[i];
    }
    vector<ll> sum2(n + 1, 0);
    for(ll i = 0; i <= n; i++){
        sum2[i + 1] = n - i + sum2[i];
    }
    for(ll i = k; i <= n + 1; i++){
        //cout << i << " " << sum1[i] << " " << sum2[i] << endl;
        ans += sum2[i] - sum1[i] + 1;
        ans %= MOD;
    }

    cout << ans << endl;

}

Measured memory_bytes: 6424
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <utility>
#include <algorithm>
using namespace std;

int main(void){
    
    int h, w;
    cin>>h>>w;
    
    vector<int> s(h*w);
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            char c;
            cin>>c;
            if(c=='#'){
                s[i*w+j]=1;
            }else{
                s[i*w+j]=0;
            }
        }
    }
    
    vector<int> wc, hc;
    
    for(int i=0; i<h; i++){
        int cnt=0;
        for(int j=0; j<w; j++){
            cnt+=s[i*w+j];
        }
        
        if(cnt>0){
            hc.push_back(i);
        }
    }
    
    for(int j=0; j<w; j++){
        int cnt=0;
        for(int i=0; i<h; i++){
            cnt+=s[i*w+j];
        }
        if(cnt>0){
            wc.push_back(j);
        }
    }
    
    for(int i=0; i<hc.size(); i++){
        for(int j=0; j<wc.size(); j++){
            cout<<(s[hc[i]*w+wc[j]]==1?'#':'.');
        }
        cout<<endl;
    }
    cout<<endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

template <typename T>
void cout_seq(T seq[],int n){
  for(int i=0;i<n;i++){
    if(i){
      cout<<" ";
    }
    cout<<seq[i];
  }
  cout<<endl;
}

int insertion_sort(int A[],int n,int g){
  int cnt = 0;
  for(int i=g;i<n;i++){
    int v = A[i];
    int j = i - g;
    while(j>=0 && A[j]>v){
      A[j+g] = A[j];
      j = j - g;
      cnt++;
    }
    A[j+g] = v;
  }
  return cnt;
}

int shell_sort(int A[],int n){
  int cnt = 0;
  int G[n];
  int v = (n > 1) ? n-1:1;
  int m = 0;
  for(int i=0;;i++){
    G[i] = v;
    if(v==1){ m = i+1; break;}
    v = v / 2;
  }
  cout<<m<<endl;
  cout_seq(G,m);
  for(int i=0;i<m;i++){
    cnt += insertion_sort(A, n, G[i]);
  }
  return cnt;
}

int main() {
  int n; cin>>n;
  int seq[n];
  for(int i=0;i<n;i++) cin>>seq[i];
  int count = 0;
  count = shell_sort(seq,n);
  cout<<count<<endl;
  for(auto a:seq)
  {
    cout<<a<<endl;
  }
}

Measured memory_bytes: 7000
//Sandcastle
#include <iostream>
#include <queue>
#include <set>

using namespace std;

static const int drow[8] = {0, -1, -1, -1, 0, 1, 1, 1};
static const int dcol[8] = {-1, -1, 0, 1, 1, 1, 0, -1};

int main() {
    int H, W;
    cin >> H >> W;
    int S[H + 2][W + 2], T[H + 1][W + 1];
    for(int i = 0; i < H + 2; i++) {
        S[i][0] = 0;
        S[i][W + 1] = 0;
    }
    for(int j = 0; j < W + 2; j++) {
        S[0][j] = 0;
        S[H + 1][j] = 0;
    }
    char c;
    for(int i = 1; i < H + 1; i++) {
        for(int j = 1; j < W + 1; j++) {
            cin >> c;
            if(c == '.') S[i][j] = 0;
            else S[i][j] = c - '0';
        }
    }

    queue<int> P, Q;
    set<int> E;
    for(int i = 1; i < H + 1; i++) {
        for(int j = 1; j < W + 1; j++) {
            T[i][j] = 0;
            for(int k = 0; k < 8; k++) {
                int si = i + drow[k];
                int sj = j + dcol[k];
                if(S[si][sj] == 0) T[i][j]++;
            }
            if(S[i][j] != 0 && T[i][j] >= S[i][j]) {
                P.push(i * W + j);
                E.insert(i * W + j);
            }
        }
    }

    int cnt = 0;
    while(!P.empty() || !Q.empty()) {
        while(!P.empty()) {
            int i = P.front() / W;
            int j = P.front() % W;
            P.pop();
            S[i][j] = 0;
            for(int k = 0; k < 8; k++) {
                int si = i + drow[k];
                int sj = j + dcol[k];
                T[si][sj]++;
                if(S[si][sj] != 0 && T[si][sj] >= S[si][sj] && E.find(si * W + sj) == E.end()) {
                    Q.push(si * W + sj);
                    E.insert(si * W + sj);
                }
            }
        }
        swap(P, Q);
        cnt++;
    }
    
    cout << cnt << endl;
}


Measured memory_bytes: 57676
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; char c; };

ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int main() {
	for (;;) {
		int N, M, S, T;
		cin >> N >> M >> S >> T;
		if (!N) break;
		int n = N;
		vector<edge> E;
		while (M--) {
			int x, y; string s;
			cin >> x >> y >> s;
			vector<int> a;
			a.push_back(x);
			for (int i = 0; i < s.length() - 1; i++)
				a.push_back(n++);
			a.push_back(y);
			for (int i = 0; i < s.length(); i++)
				E.push_back(edge{a[i], a[i + 1], s[i]});
		}
		int m = E.size();
		vector<bool> pos(n);
		pos[T] = true;
		for (int t = 0; t < n; t++)
			for (int i = 0; i < m; i++)
				if (pos[E[i].v])
					pos[E[i].u] = true;
		if (!pos[S]) {
			cout << "NO" << endl;
			continue;
		}
		vector<vector<edge> > EE(26);
		for (int i = 0; i < m; i++)
			EE[E[i].c - 'a'].push_back(E[i]);
		string s;
		vector<bool> a(n);
		a[S] = true;
		int t;
		for (t = 0; t < n; t++) {
			if (a[T]) break;
			vector<bool> _a(n);
			char c;
			for (c = 'a'; c <= 'z'; c++) {
				vector<edge> E = EE[c - 'a'];
				bool ok = false;
				for (int i = 0; i < E.size(); i++)
					if (E[i].c == c && a[E[i].u] && pos[E[i].v]) {
						_a[E[i].v] = true;
						ok = true;
					}
				if (ok) break;
			}
			s.push_back(c);
			a = _a;
		}
		if (t == n) cout << "NO" << endl;
		else cout << s << endl;
	}
}

Measured memory_bytes: 3128
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int a[100000];
long long dp1[100000],dp2[100000],sum[100000];

void solve(){
    dp1[1] = max(a[0]+a[1],-a[0]-a[1]);
    dp2[1] = max(a[0]-a[1],-a[0]+a[1]);
    for(int i=2; i<n; i++){
        dp1[i] = max(dp1[i-1]+a[i],dp2[i-1]-a[i]);
        dp2[i] = max(dp1[i-1]-a[i],dp2[i-1]+a[i]);
    }
    cout << dp1[n-1] << endl;
}

int main(){
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    solve();
    return 0;
}


Measured memory_bytes: 2176
#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>;

const int mod = 998244353;

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  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 { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}

};

istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }

} c(200005);

int main(){
  int n, m, k;
  cin >> n >> m >> k;
  mint ans = 0;
  mint col = m;
  for (int x=n-1; x>=0; --x){
    mint now = col;
    now *= c(n-1, x);
    if (x <= k) ans += now;
    col *= m-1;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 6260
#include <iostream>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
int h, w;
char grid[1010][1010];
ll dp[1010][1010];

int main() {
    cin >> h >> w;
    for (int i = 0; i < h; i++) cin >> grid[i];
    dp[0][0] = 1;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (i + 1 < h && grid[i+1][j] == '.') dp[i+1][j] += dp[i][j] % MOD;
            if (j + 1 < w && grid[i][j+1] == '.') dp[i][j+1] += dp[i][j] % MOD;
        }
    }
    int ans = dp[h-1][w-1] % MOD;
    cout << ans << endl;
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REP1(i,n) for(int i=1, i##_len=(n); i<i##_len; ++i)
#define ll long long
static const int MAX = 10000;
static const ll INFTY = 1e12;

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 ll MRINF = 5000000000000000;

int main() {

  int A, B, C;
  cin >> A >> B >> C;

  if(A+B>=C) cout << "Yes" << endl;
  else cout << "No" << endl;

  
  

}
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         pass System Test!
*/

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

bool priorityAscending(pair<long long int, long long int> a, pair<long long int, long long int> b) {
    return a.second > b.second;
}

bool priorityDescending(pair<long long int, long long int> a, pair<long long int, long long int> b) {
    return a.second < b.second;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;
    vector<pair<long long int, long long int>> sushi(N);
    for (int i = 0; i < N; ++i) {
        cin >> sushi[i].first >> sushi[i].second;
    }

    sort(sushi.begin(), sushi.end(), priorityAscending);

    vector<pair<long long int, long long int>> temp;
    vector<int> sushiCount(N + 10, 0);
    long long int nowPoint = 0, answerPoint = 0;
    for (int i = 0; i < K; ++i) {
        temp.push_back(sushi[i]);
        ++sushiCount[sushi[i].first];
        nowPoint += sushi[i].second;
    }
    long long int various = 0;
    for (int i = 0; i <= N + 5; ++i) {
        if (sushiCount[i] >= 1) ++various;
    }
    answerPoint = nowPoint + (various * various);
    sort(temp.begin(), temp.end(), priorityDescending);
    /* for (int i = 0; i < sushi.size(); ++i) {
        cout << sushi[i].first << " " << sushi[i].second << endl;
    } */

    /* for (int i = 0; i < temp.size(); ++i) {
        cout << temp[i].first << " " << temp[i].second << endl;
    } */

    int tempCoordinate = 0;
    for (int i = K; i < N; ++i) {
        if (sushiCount[sushi[i].first] >= 1) continue;

        while (tempCoordinate != K) {
            if (sushiCount[temp[tempCoordinate].first] == 1) {
                ++tempCoordinate;
            } else break;
        }

        if (tempCoordinate == K) break;

        nowPoint -= temp[tempCoordinate].second;
        --sushiCount[temp[tempCoordinate].first];
        nowPoint += sushi[i].second;
        ++sushiCount[sushi[i].first];
        ++various;
        ++tempCoordinate;
        // cout << i << " " << nowPoint + (various * various) << endl;
        answerPoint = max(answerPoint, nowPoint + (various * various));
    }
    cout << answerPoint << endl;
}

Measured memory_bytes: 4340
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


template<typename T,T MOD = 1000000007>
struct Mint{
  static constexpr T mod = MOD;
  T v;
  Mint():v(0){}
  Mint(signed v):v(v){}
  Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}

  Mint pow(long long k){
    Mint res(1),tmp(v);
    while(k){
      if(k&1) res*=tmp;
      tmp*=tmp;
      k>>=1;
    }
    return res;
  }

  static Mint add_identity(){return Mint(0);}
  static Mint mul_identity(){return Mint(1);}

  Mint inv(){return pow(MOD-2);}

  Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
  Mint& operator/=(Mint a){return (*this)*=a.inv();}

  Mint operator+(Mint a) const{return Mint(v)+=a;}
  Mint operator-(Mint a) const{return Mint(v)-=a;}
  Mint operator*(Mint a) const{return Mint(v)*=a;}
  Mint operator/(Mint a) const{return Mint(v)/=a;}

  Mint operator-() const{return v?Mint(MOD-v):Mint(v);}

  bool operator==(const Mint a)const{return v==a.v;}
  bool operator!=(const Mint a)const{return v!=a.v;}
  bool operator <(const Mint a)const{return v <a.v;}

  static Mint comb(long long n,int k){
    Mint num(1),dom(1);
    for(int i=0;i<k;i++){
      num*=Mint(n-i);
      dom*=Mint(i+1);
    }
    return num/dom;
  }
};
template<typename T,T MOD> constexpr T Mint<T, MOD>::mod;
template<typename T,T MOD>
ostream& operator<<(ostream &os,Mint<T, MOD> m){os<<m.v;return os;}

//INSERT ABOVE HERE
const int MAX = 303;
using M = Mint<int>;
M dp[MAX][MAX][MAX]={};
signed main(){
  int n,m;
  cin>>n>>m;
  vector<int> ls(m),rs(m),xs(m);
  for(int i=0;i<m;i++) cin>>ls[i]>>rs[i]>>xs[i];

  vector< vector<int> > G(MAX);
  for(int i=0;i<m;i++) G[rs[i]].emplace_back(i);

  M ans{0};
  dp[0][0][0]=M(1);
  for(int i=0;i<=n;i++){
    for(int j=0;j<=n;j++){
      for(int k=0;k<=n;k++){
        int p=max({i,j,k});
        for(int t:G[p]){
          int l=ls[t],x=xs[t];
          int c=(l<=i)+(l<=j)+(l<=k);
          if(c!=x) dp[i][j][k]=M(0);
        }
        if(p==n) ans+=dp[i][j][k];
        int q=p+1;
        dp[q][j][k]+=dp[i][j][k];
        dp[i][q][k]+=dp[i][j][k];
        dp[i][j][q]+=dp[i][j][k];
      }
    }
  }

  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 108928
#include <assert.h>
#include <limits.h>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using ll = long long;
using P = std::pair<ll, ll>;

#define rep(i, a, b) for (ll(i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cerr << i << "\n"

//const ll MOD = 998244353;
const ll MOD = 1e9+7;
 
int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  //問題文中の添え字が0-indexか1-indexか確認!

  ll n;
  std::cin>>n;

  std::vector<ll> a(3*n),l(n+1,0),r(n+1,0);

  std::priority_queue<ll> lque,rque;

  rep(i,0,3*n)std::cin>>a[i];

  rep(i,0,n){
    l[0]+=a[i];
    lque.push(-a[i]);
    r[n]+=a[2*n+i];
    rque.push(a[2*n+i]);
  }

  rep(i,1,n+1){
    l[i]=l[i-1]+a[n-1+i];
    lque.push(-a[n-1+i]);

    ll temp=-lque.top();lque.pop();

    l[i]-=temp;

    r[n-i]=r[n+1-i]+a[2*n-i];
    rque.push(a[2*n-i]);

    temp=rque.top();rque.pop();

    r[n-i]-=temp;
  }

  ll ans=-LLONG_MAX;

  rep(i,0,n+1){
    //std::cout<<l[i]<<" "<<r[i]<<"\n";
    ans=std::max(ans,l[i]-r[i]);
  }

  std::cout<<ans;

  return 0;
}

Measured memory_bytes: 6000
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<(n);i++)
#define rep2(i,a,n) for(int i=a;i<n;i++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
const int mod =1000000007;

int main(){
    string s;
	cin >> s;
	int n = s.size();
	rep(i, n) {
		if (i + 1 < n && s[i] == s[i + 1]) {
			cout<< i + 1<<' '<< i + 2<<endl;
			return 0;
		}
		if (i + 2 < n && s[i] == s[i + 2]) {
			cout<< i + 1<<' '<< i + 3<<endl;
			return 0;
		}
	}
	cout<<-1<<' '<< -1<<endl;
}

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

int main() {
	while(1) {
		int a, b;
		char op;
		cin >> a >> op >> b;
		auto result = 0;
		if (op == '?') break;
		switch (op) {
		  case '+': result = a + b; break;
		  case '-': result = a - b; break;
		  case '*': result = a * b; break;
		  case '/': result = a / b; break;
		}
		cout << result << endl;
	}
}

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

int main(){
    int A, B, C;
    scanf("%d %d %d", &A, &B, &C);
    int a, b, c, x, ans;
    a = abs(A - B);
    b = abs(B - C);
    c = abs(C - A);
    x = max({a, b, c});
    ans = a + b + c - x;
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <deque>
#include <cassert>
#define For(i, a, b) for (int i = a; i < b; ++i)
#define Out(i, a, b) for (int i = a - 1; i >= b; --i)
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define files(FileName) read(FileName); write(FileName)
#define read(FileName) freopen((FileName + ".in").c_str(), "r", stdin)
#define write(FileName) freopen((FileName + ".out").c_str(), "w", stdout)
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }

using namespace std;

typedef long long base;
typedef pair <int, int> point;

const string FILENAME = "input";
const int MAXN = 1e5 + 1, RAME = 10;
const int dirx[4] = {0, 1, 0, -1}, diry[4] = {1, 0, -1, 0};


int n;
int len[MAXN];
vector <int> edge[MAXN];
set <pair <int, int>> que;

void erase(int i) {
    for (int j: edge[i]) {
        pair <int, int> v = {len[j], j};
        if (que.count(v)) {
            que.erase(v);
            --len[j];
            que.insert({len[j], j});
        }
    }
    que.erase({len[i], i});
}

int main() {
    //read(FILENAME);
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        edge[a].pb(b);
        edge[b].pb(a);
    }
    for (int i = 0; i < n; ++i) {
        que.insert({edge[i].size(), i});
        len[i] = edge[i].size();
    }
    bool turn = true;
    while (que.size()) {
        auto v = *que.begin();
        if (v.x == 0 && turn) {
            cout << "First" << endl;
            return 0;
        }
        if (!turn) {
            erase(v.y);
        } else {
            for (int j: edge[v.y]) {
                if (que.count({len[j], j})) {
                    erase(j);
                    break;
                }
            }
        }
        turn ^= 1;
    }
    cout << "Second" << endl;
}

Measured memory_bytes: 12928
#include <iostream>
#include <vector>
#include <algorithm>
using i64 = long long;

i64 memo[41][2];
i64 a, b, c, x;

i64 rec(const i64 i, const bool j) {
    if (i < 0) return 0;
    if (memo[i][j] != -2) return memo[i][j];
    const i64 mask = 1ll << i;
    const i64 p = mask & a, q = mask & x, r = mask & c;
    i64 ret;
    if (!q) {
        if (!r) {
            ret = rec(i - 1, j || p);
        } else {
            if (!p && !j) ret = -1;
            else if (const auto o = rec(i - 1, j); o >= 0) {
                ret = mask | o;
            } else {
                ret = -1;
            }
        }
    } else {
        if (!r) {
            const i64 z = rec(i - 1, j || p),
                o = !p && !j ? -1 : (rec(i - 1, j) >= 0 ? rec(i - 1, j) | mask : -1);
            ret = std::max(z, o);
        } else {
            ret = -1;
        }
    }

    return memo[i][j] = ret;
}

int main() {
    for (auto &v : memo) v[0] = v[1] = -2;
    int n;
    std::cin >> n >> a >> b;
    for (int i = 2; i < n; i++) {
        i64 in;
        std::cin >> in;
        x ^= in;
    }

    const i64 t = a + b - x;
    if (t < 0 || t % 2) {
        std::cout << -1 << std::endl;
        return 0;
    }

    c = t / 2;

    const i64 ret = rec(40, false);
    std::cout << (ret <= 0 ? -1 : a - ret) << std::endl;

    return 0;
}


Measured memory_bytes: 3604
#include <iostream>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

struct Edge {
    int a;
    int b;
    int cost;
    bool used;
    Edge(int a, int b, int cost) : a(a), b(b), cost(cost), used(false) {}
};


int VERY_BIG = 99999999;
Edge* g_map[101][101];

Edge g_noedge(-1, -1, VERY_BIG);

int mymin(int* cost, bool* done)
{
    int idx = -1, val = VERY_BIG;
    for(int i=0;i<101;i++) {
        if (!done[i] && cost[i] < val) {
            idx = i;
            val = cost[i];
        }
    }
    return idx;
}

void myupdate(int basecost, int* cost, Edge** arr, Edge** from)
{
    for(int i=1;i<101;i++) {
        if (arr[i]->cost + basecost < cost[i]) {
            cost[i] = arr[i]->cost + basecost;
            from[i] = arr[i];
        }
    }
}

void dijk(int s, int n)
{
    //cerr << "dijk: " << s << endl;
    bool done[101];
    int cost[101];
    Edge* from[101];
    for (int i=0;i<101;i++) { done[i] = false; cost[i] = VERY_BIG; }
    cost[s] = 0;
    done[s] = true;
    while (--n) {
        myupdate(cost[s], cost, g_map[s], from);
        int m = mymin(cost, done);
        if (m == -1) break;
        //cerr << "  use: " << from[m]->a << " " << from[m]->b << endl;
        from[m]->used = true;
        done[m] = true;
        s = m;
    }
}

void to_map(vector<Edge>& edges)
{
    for (int i = 0; i<101; i++) for (int j = 0; j<101; j++) g_map[i][j] = &g_noedge;
    for (auto it = edges.begin(); it != edges.end(); ++it) {
        g_map[it->a][it->b] = g_map[it->b][it->a] = &(*it);
    }
}

int main()
{
    int n, m;

    cin >> n >> m;
    vector<Edge> edges;
    edges.reserve(m);
    g_noedge.used = true;
    for (int i=0;i<m;i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges.emplace_back(a, b, c);
    }
    to_map(edges);
    for (int i=0;i<n;i++) dijk(i, n);
    int cnt = 0;
    for (auto it = edges.cbegin(); it != edges.cend(); ++it) {
        if (!it->used) cnt++;
        //cerr << "use?: " << it->used << endl;
    }
    cout << cnt << endl;
    return 0;
}


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

using namespace std;
using llong = long long;
using ldbl = long double;
using lpair = pair<llong, llong>;
using llpair = pair<int, lpair>;

#define ALL(x) x.begin(), x.end()

template<typename T>
constexpr T inf = static_cast<T>(pow(10, static_cast<int>(log10(numeric_limits<T>::max())))) + 7;
constexpr llong mod = 1e9+7;
constexpr array<llong, 9> nw = {0, 1, 0, -1, -1, 1, 1, -1, 0};
constexpr array<llong, 9> nh = {1, 0, -1, 0, 1, 1, -1, -1, 0};

llong H, W;
vector<string> area;

int dijkstra() {
  vector<vector<int>> dis(H, vector<int>(W, mod));
  priority_queue<llpair, vector<llpair>, greater<llpair>> que;

  dis[0][0] = area[0][0] == '#';
  que.push(llpair(dis[0][0], lpair(0, 0)));
  while (que.size()) {
    auto now = que.top();
    que.pop();

    if (dis[now.second.first][now.second.second] < now.first) continue;
    for (int i = 0; i < 2; ++i) {
      int h = now.second.first + nh[i];
      int w = now.second.second + nw[i];
      if (h < 0 || w < 0 || h >= H || w >= W) continue;
      llpair next(now.first + (area[now.second.first][now.second.second] == '.' && area[h][w] == '#'), lpair(h, w));
      if (dis[h][w] > next.first) {
        dis[h][w] = next.first;
        que.push(next);
      }
    }
  }

  return dis.back().back();
}

int main() {
  cin >> H >> W;
  area.resize(H);
  for (auto &h: area) {
    cin >> h;
  }

  cout << dijkstra() << endl;

  return 0;
}


Measured memory_bytes: 384
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
s1 = readline().rstrip().decode()
s2 = readline().rstrip().decode()
mod = 10 ** 9 + 7

if s1[0] == s2[0]:
    ans = 3
    cnt = 1
else:
    cnt = 2
    ans = 6

for i in range(n):
    if cnt >= n:
        break
    if s1[cnt] != s2[cnt]:
        if s1[cnt - 1] == s2[cnt - 1]:
            ans *= 2
        else:
            ans *= 3
        cnt += 2
    else:
        if s1[cnt - 1] != s2[cnt - 1]:
            ans *= 1
        else:
            ans *= 2
        cnt += 1
    ans %= mod
print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <math.h>
#include <vector>
#include <map>
#include <queue>
#include <utility>
#include <algorithm>
#include <string>
#include <set>
#include <random>
using namespace std;

int main() {
  string s;
  cin >> s;
  int ans = 0;
  for (int i = 0; i < 4; i++) {
	  ans -= 1;
	  if (s[i] == '+') {
		  ans += 2;
		}
	}
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string.h>

int c[4];

int f( char *str )
{
	if( !strcmp( str, "A" ) ){
	 	return 0;
	}
	else if( !strcmp( str, "B" ) ){
	 	return 1;
	}
	else if( !strcmp( str, "AB" ) ){
	 	return 2;
	}
	else if( !strcmp( str, "O" ) ){
	 	return 3;
	}
}

int main()
{
	int n;
	char str[3];
	
	while( scanf( "%d,%s", &n, str ) != EOF ){
		c[f( str )]++;
	}
	
	for( int i = 0; i < 4; i++ ){
		printf( "%d\n", c[i] );
	}

	return 0;
}

Measured memory_bytes: 1188
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main(void){
    int width;
    int a,b;

//    printf("Input the width of square:");
    scanf("%d",&width);
  //  printf("Input the x coodinates of the under square:");
    scanf("%d",&a);
    //printf("Input the x coodinates of the upper square:");
    scanf("%d",&b);
    if(a<=b&&b<=a+width){
        printf("0");
    }
    else if(b<=a&&a<=b+width){
        printf("0");
    }
    else if(a+width<b){
        printf("%d",b-(a+width));
    }
    else if(b+width<a){
        printf("%d",a-(b+width));
    }
    return 0;
}

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

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = ReadArrayLong();
            var N = input[0];
            var M = input[1];
            var inf = long.MaxValue;
            var sides = new long[M, 3];
            var dis = Enumerable.Repeat(inf, (int)N + 1).ToArray();
            for (int i = 0; i < M; i++)
            {
                input = ReadArrayLong();
                sides[i, 0] = input[0];
                sides[i, 1] = input[1];
                sides[i, 2] = -input[2];
            }
            dis[1] = 0;
            for (int i = 0; i < N - 1; i++)
            {
                for (int j = 0; j < M; j++)
                {
                    if (dis[sides[j, 0]] != inf && dis[sides[j, 1]] > dis[sides[j, 0]] + sides[j, 2])
                    {
                        dis[sides[j, 1]] = dis[sides[j, 0]] + sides[j, 2];
                    }
                }
            }
            var ans = -dis[N];
            var neg = new bool[N + 1];
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < M; j++)
                {
                    if (dis[sides[j, 0]] != inf && dis[sides[j, 1]] > dis[sides[j, 0]] + sides[j, 2])
                    {
                        dis[sides[j, 1]] = dis[sides[j, 0]] + sides[j, 2];
                        neg[sides[j, 1]] = true;
                    }
                    if (neg[sides[j, 0]] == true) neg[sides[j, 1]] = true;
                }
            }

            Console.WriteLine(neg[N] ? "inf" : ans.ToString());
            Console.ReadLine();
        }

        static string Read() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Read()); }
        static long ReadLong() { return long.Parse(Read()); }
        static int[] ReadArrayInt() { return Read().Split(' ').Select(s => int.Parse(s)).ToArray(); }
        static long[] ReadArrayLong() { return Read().Split(' ').Select(s => long.Parse(s)).ToArray(); }
    }
}

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

#define rep(i, n) for(i = 0; i < n; i++)
#define of(i, n) for(i = n - 1; i >= 0; i--)
#define ll long long

bool comp(int a, int b)
{
    return (a < b);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,k,max=0,flag=0,cnt=0,m,i,j,sum=0,t,y;
    long long x,ans,min;
    int a[3][3];
    rep(i,3) {rep(j,3) cin>>a[i][j];}
    cin>>n;
    vector<int> v;
    rep(i,n) {cin>>k; v.push_back(k);}
    int b[3][3];
    rep(i,n){
    rep(j,3){rep(k,3) if(v[i]==a[j][k]) b[j][k]=1; }
    }
    rep(i,3) if(b[0][i]+b[1][i]+b[2][i]==3){cout<<"Yes"<<endl; return 0;}
    rep(i,3) if(b[i][0]+b[i][1]+b[i][2]==3){cout<<"Yes"<<endl; return 0;}
    if(b[1][1]+b[2][2]+b[0][0]==3){cout<<"Yes"<<endl; return 0;}
    else if (b[0][2]+b[1][1]+b[2][0]==3) {cout<<"Yes"<<endl; return 0;}
    else cout<<"No"<<endl;
}






Measured memory_bytes: 256
// 答え見た

package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	c := make([]int, n-1)
	s := make([]int, n-1)
	f := make([]int, n-1)
	for i := 0; i < n-1; i++ {
		fmt.Scan(&c[i], &s[i], &f[i])
	}

	for i := 0; i < n; i++ {
		t := 0
		for j := i; j < n-1; j++ {
			if t < s[j] {
				t = s[j]
			} else if t%f[j] != 0 {
				t = t + f[j] - t%f[j]
			}
			t += c[j]
		}
		fmt.Println(t)
	}
}


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

import collections
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

c = collections.Counter(prime_factorize(n))
res = 0
for key,value in c.items():
    i = 1
    while value >= i :
        value -= i
        res+=1
        i+=1
print(res)


Measured memory_bytes: 9468
#include <stdio.h>
int a[200005];
int n;
int main(){
	int x;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		a[x]=i;
	}
//	for(int i=1;i<=n;i++) printf("%d%c",a[i],i==n?'\n':' ');
	int ans=1;
	int cur=1;
	for(int i=2;i<=n;i++){
		if(a[i]>a[i-1]){
			cur++;
		}else{
			if(cur>ans) ans=cur;
			cur=1;
		}
	}
	if(cur>ans) ans=cur;
	printf("%d\n",n-ans);
	return 0;
}

Measured memory_bytes: 1024