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

int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 0;i < k;i++) {
		int x, y;
		cin >> x >> y;
		int a = (n + 1) / 2;
		if (x > a)x = n - x + 1;
		if (y > a)y = n - y + 1;

		int c = min(x, y);
		if (c % 3 == 0)cout << '3' << endl;
		else cout << c % 3 << endl;
	}
	return 0;
}

Measured memory_bytes: 3072
#include "bits/stdc++.h"
 
using namespace std;
 
main(){
  string s;
  cin >> s;
  bool f = true;
for(int i = 0; i < s.size(); ++i){
    if(i%2==1){
        if((s[i]=='L')||(s[i]=='U')||(s[i]=='D')){
        }else{
            f = false;
            break;
        }
    }else{
        if((s[i]=='R')||(s[i]=='U')||(s[i]=='D')){
        }else{
            f = false;
            break;
        }
    }
}
  if(f){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    [h, w] <- getIntList
    let hd = h `div` 2
    let hm = h `mod` 2
    let wd = w `div` 2
    let wm = w `mod` 2
    print $ if h == 1 || w == 1 then 1 else hd * w + hm * (wd + wm)

Measured memory_bytes: 380
N = int(input())
w1 = 10**5
w2 = 1
try:
    for h in range(1,3501):
        for n in range(1,3501):
            if (4*h*n-N*(h+n))>0:
                w1 = (N*h*n)//(4*h*n-N*(h+n))
                w2 = (N*h*n)/(4*h*n-N*(h+n))
            if w1==w2 and w1>0:
                raise(Exception)
except Exception:
    print(h,n,w1)

Measured memory_bytes: 3064
import math

# 試し割法により素因数分解
# https://note.nkmk.me/python-prime-factorization/
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


def main():
    A, B = map(int,input().split())
    G = math.gcd(A, B)
    primes = prime_factorize(G)
    print(1 + len(set(primes)))

if __name__ == "__main__":
    main()


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

int facctorialMethod(int k);

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

    int P[N];
    int Q[N];
    int i;

    for (i = 0; i < N; i++){
        cin >> P[i];
    }
    for (i = 0; i < N; i++){
        cin >> Q[i];
    }

    int a = 0;
    int b = 0;
    int j = 0;
    int cnt = 0;

    for (i = 0; i < N-1; i++){
        cnt = 0;

        if (i >= 1){
            for (j = 0; j < i; j++){
                if (P[j] < P[i]){
                    cnt++;
                }
            }
        }
        a += (P[i]-cnt-1) * facctorialMethod(N-i-1);
        // cout << a << endl;
    }


     for (i = 0; i < N-1; i++){
         cnt = 0;
         if (i >= 1){
            for (j = 0; j < i; j++){
                if (Q[j] < Q[i]){
                    cnt++;
                }
            }
         }
        b += (Q[i]-cnt-1) * facctorialMethod(N-i-1);
            //  cout << b << endl;
    }

    // cout << a+1 << " " << b+1 << " " << abs(a-b) << endl;
    cout << abs(a-b) << endl;
    return 0;
}

int facctorialMethod(int k){
    // if(k == 0){
    //     return 0;
    // }
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  if(A+B == C+D){
	cout << "Balanced" << endl;
  }
  else if(A+B > C+D){
    cout << "Left" << endl;
  }
  
  else if(A+B < C+D){
    cout << "Right" << endl;
  }
  
  
}

Measured memory_bytes: 384
#define debug_interval ','
#define dump_interval ' '
#define debug_toggle 1
//{
#include<bits/stdc++.h>
using namespace std;
#define hi cout<<"hi"<<endl;
#define int long long
#define INT_MAX LLONG_MAX
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define fi first
#define se second
#define mp make_pair
#define rev reverse
#define dans dump(ans)
#define MOD 1000000007
#define amp(v,n) (v).count(n)?v[n]++:v[n]=1;

//{
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class...A> inline void dump(){cout<<endl;}
template<class...A> inline void dump_rest() {cout<<endl;}
template<class T, class...A> inline void dump_rest(const T& first, const A&... rest){cout<<dump_interval<<first;dump_rest(rest...);}
template<class T,class...A> inline void dump(const T&first,const A&...rest){cout<<first;dump_rest(rest...);}
template<class...A> inline void debug(){cerr<<endl;}
template<class...A> inline void debug_rest() {cerr<<endl;}
template<class T, class...A> inline void debug_rest(const T& first, const A&... rest){cerr<<debug_interval<<first;debug_rest(rest...);}
template<class T,class...A> inline void debug(const T&first,const A&...rest){if(debug_toggle)cerr<<first,debug_rest(rest...);}
//}

typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
template<int m>class mint{private:int i;public:mint() : i(0){}mint(int i): i((i%m+m)%m){}mint operator+(const mint& o){return o.i+i;}mint operator*(const mint& o){return o.i*i;}mint operator-(){return -i;}operator int() {return i;}};

int ans;
string s;

main(){
    int a,b;
    cin>>a>>b;
    if(a+b==15)cout<<"+";
    else if(a*b==15)cout<<"*";
    else cout<<"x";
    cout<<endl;
}



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

using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VD = vector<double>;
using VVD = vector<VD>;
using VS = vector<string>;
using PII = pair<int, int>;
using VPII = vector<PII>;
using VL = vector<long long>;
using VVL = vector<VL>;

#define sz(var) (int)var.size()
#define REP(var, start, end) for(int var = start; var < (int)end; ++var)
#define CLEAR(var, with) memset(var, with, sizeof(var))
#define ALL(x) x.begin(), x.end()
#define LL long long
#define ULL unsigned long long
#define TIME cout << "Time elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms" << endl;

struct DisjointSet
{
	VI parent, rank;
	DisjointSet(int N) : parent(N), rank(N, 1) {
		for(int i = 0; i < N; ++i)
			parent[i] = i;
	}

	int find(int u)
	{
		if(parent[u] == u)
			return u;
		return parent[u] = find(parent[u]);
	}

	void merge(int u, int v)
	{
		u = find(u); v = find(v);
		if(u == v) return;
		if(rank[u] > rank[v]) swap(u, v);
		parent[u] = v;
		if(rank[u] == rank[v]) ++rank[v];
	}
};

int n, k, l;
void connected()
{
	DisjointSet road(n), rail(n);

	int u, v;
	for(int i = 0; i < k; ++i) {
		cin >> u >> v;
		--u; --v;
		road.merge(u, v);
	}

	for(int i = 0; i < l; ++i) {
		cin >> u >> v;
		--u; --v;
		rail.merge(u, v);
	}

	map<PII, int> mp;
	for(int i = 0; i < n; ++i)
		++mp[PII(road.find(i), rail.find(i))];
	
	for(int i = 0; i < n; ++i)
		cout << mp[PII(road.find(i), rail.find(i))] << " ";
	cout << endl;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
#ifndef ONLINE_JUDGE
//	freopen("tmp.in", "r", stdin);
//	freopen("tmp.out", "w", stderr);
#endif
	cin >> n >> k >> l;

	connected();

	return 0;
}

Measured memory_bytes: 15104
#include <iostream>

int main(){
	int n,debt=100000;
	std::cin>>n;
	for(int i=0;i<n;i++){
		debt*=1.05;
		debt=debt%1000 ? debt/1000*1000+1000 : debt;
	}
	std::cout<<debt<<'\n';
	return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define fl(i,a,b) for(int i=a;i<b;++i)
#define fa(i,a) for(auto (i):(a))
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(),a.end()
#define vi vector <int>
#define ii pair <int,int>
#define pb push_back
using namespace std;
template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));
if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar()))x=x*10+c-48;if(nega)x=-x;}
template <typename T> inline void writep(T x){if(x>9)writep(x/10);putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');}
template <typename T> inline void writeln(T x){write(x);putchar('\n');}
template <typename R, typename D> inline void Min(R &a, D b){if(a>b) a=b;}
template <typename D, typename R> inline void Max(D &a, R b){if(a<b) a=b;}
const int N=200005,M=300005;
int n,a[N],b[N],c,q,d,T;
int main(){
	ios_base::sync_with_stdio(NULL);
	cin. tie(NULL); cout. tie(NULL);
	#ifndef ONLINE_JUDGE
	freopen(".inp" , "r", stdin);
	#endif
	cin>>n;
	fo(i,1,n) cin>>a[i];
	fo(i,1,n) cin>>b[i];
	sort(b+1,b+1+n,greater<int>());
	fo(i,1,n)if(a[i]==b[i]){
        int tar=a[i];
        int cnt=0;
        int j=i;
        int liml;
        fo(i,1,n) if(a[i]==tar){
            liml=i;
            break;
        }
        int limr;
        fd(i,n,1) if(a[i]==tar){
            limr=i;
            break;
        }
        while(a[i]==b[i]){
            ++i;
            ++cnt;
        }
        int l=liml-1;
        fo(i,1,n){
            if(b[i]==tar){
                Min(l,i-1);
                break;
            }
        }
        int r=n-limr;
        fd(i,n,limr){
            if(b[i]==tar){
                Min(r,n-i);
                break;
            }
        }
        if(l+r<cnt){
            cout<<"No";
            return 0;
        }
        cout <<"Yes\n";
        fo(k,1,l){
            swap(b[j],b[k]);
            ++j;
            if(j==i) break;
        }
        fd(k,n,n-r+1){
            swap(b[j],b[k]);
            ++j;
            if(j==i) break;
        }
        fo(k,1,n) cout<<b[k]<<' ';
        return 0;
	}
    cout <<"Yes\n";
    fo(i,1,n) cout<<b[i]<<' ';
    return 0;
}

Measured memory_bytes: 5196
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
  int n, k;
  cin >> n >> k;
  double ans = 0;
  for(int i = 1; i <= n; i++) {
    double tmp = i;
    double p = 1.0 / n;
    while(tmp < k) {
      tmp*= 2;
      p /= 2.0;
    }
    ans += p;
  }
  printf("%.10f", ans);
  return 0;
}

Measured memory_bytes: 3744
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,unsafe-math-optimizations")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,tune=native")
#include "bits/stdc++.h"
#include <assert.h>
#include <immintrin.h>
#include <emmintrin.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PB push_back
#define MP make_pair
const int MOD=1000000007;
#define endl "\n"
#define fst first
#define snd second
const int UNDEF = -1;
const int INF=1<<30;
template<typename T> inline bool chkmax(T &aa, T bb) { return aa < bb ? aa = bb, true : false; }
template<typename T> inline bool chkmin(T &aa, T bb) { return aa > bb ? aa = bb, true : false; }
typedef pair<ll,ll> pll;typedef vector<ll> vll;typedef pair<int,int> pii;typedef vector<int> vi;typedef vector<vi> vvi;
#ifdef ONLINE_JUDGE
#define assert(...) /* nothing */
#endif
#define DEBUG_CAT
#ifdef DEBUG_CAT
#define dbg(...)   printf( __VA_ARGS__ )
#else 
#define dbg(...)   /****nothing****/
#endif
int rint();char rch();long long rlong();
const int mn=100000+4;
const int mx=mn;
class UnionFind {
  typedef int UFTYPE;
public:
  int ufParent[mx];
  int rank[mx];
  inline void ufreset(int x) {
    ufParent[x]=x;
    rank[x]=0;
  }
  void init() {
    for (int x=0;x<mx;x++) {
      ufreset(x);
    }
  }
  int ffind(int x) {
    if (ufParent[x] != x) {
      ufParent[x] = ffind(ufParent[x]);
    }
    return ufParent[x];
  }
  void funion(int _x, int _y) {
    int xr = ffind(_x);
    int yr = ffind(_y);
    if (xr==yr) return;
    if (rank[xr] > rank[yr]) swap(xr,yr);
    if (rank[xr]==rank[yr]) rank[yr]++;
    ufParent[xr] = yr;
  }
};


bitset<mn> seen;
int p[mn];
UnionFind uf;
int main()
{
  ios_base::sync_with_stdio(false); cin.tie(0);
  uf.init();
  int n=rint(),m=rint();
  for (int x=1;x<=n;x++) p[x]=rint();
  for (int i=0;i<m;i++) {
    int x=rint(),y=rint(); uf.funion(x,y);
  }
  int ans=0;
  for (int x=1;x<=n;x++) {
    if (uf.ffind(x)==uf.ffind(p[x])) ++ans;
  }
  printf("%d\n",ans);
}


inline int _read_char() {
  static char buf[1 << 16], *ptr = buf, *end_ptr = buf;
  if (ptr == end_ptr) {
    int len = fread(buf, 1, sizeof(buf), stdin);
    if (len <= 0) return EOF;
    ptr = buf;
    end_ptr = buf + len;
  }
  return *ptr++;
}

inline char rch() {
  char ch=_read_char();
  while(ch=='\0'||ch=='\n') ch=_read_char();
  return ch;
}

inline int rint() {
  int ch; bool sg = 0;
  do {
    ch = _read_char();
    if (ch == '-') sg = 1;
  } while (ch < '0' || ch > '9');
  int x = ch - '0';
  while (true) {
    ch = _read_char();
    if (ch < '0' || ch > '9') break;
    x = x * 10 + ch - '0';
  }
  return (sg?-x:x);
}

inline long long rlong() {
  int ch; bool sg = 0;
  do {
    ch = _read_char();
    if (ch == '-') sg = 1;
  } while (ch < '0' || ch > '9');
  long long x = ch - '0';
  while (true) {
    ch = _read_char();
    if (ch < '0' || ch > '9') break;
    x = x * 10 + ch - '0';
  }
  return (sg?-x:x);
}


Measured memory_bytes: 1536
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

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

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

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
    int n;
    cin>>n;
    vector<P> job(n);
    for(int i = 0; i < n; i++){
        cin>>job[i].second>>job[i].first;
    }
    // sort(all(job),greater<P>());
    // int now = job[n-1].first;
    // for(int i = 0; i < n; i++){
    //     now -= job[i].second;
    //     if(i==n-1){
    //         if(now<0){
    //             cout<<"No"<<endl;
    //             return 0;
    //         }
    //         break;
    //     }
    //     if(now>job[i+1].first){
    //         now = job[i].first;
    //     }
    // }
    // cout<<"Yes"<<endl;

    sort(all(job));
    int now = 0;
    for(int i = 0; i < n; i++){
        now += job[i].second;
        if(now>job[i].first){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;

    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL INF=1e18;
LL N,i,ans,P;
LL A[123456];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>N;
    for(i=0;i<N;i++)
        cin>>A[i];
    A[N++]=0;
    sort(A,A+N);
    P=N;
    for(i=1;i<N;i++)
    {
        P--;
        if(A[i]-A[i-1]&1)
            ans^=P;
    }
    if(ans==0)
        cout<<"second";
    else
        cout<<"first";
    cout<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int32_t main(){
	string s;
	cin>>s; 
	set<char> t; 
	for(auto &it:s)
		t.insert(it); 
	if(t.size()==1)
		cout<<"No"<<endl; 
	else 
		cout<<"Yes"<<endl;
}

Measured memory_bytes: 256
count = 0
data = []
while True:
  count += 1
  h, x = map(int,(input().split()))
  data.append([h, x])
  if x == 0 and h == 0:
    break
for i in range(count-1):
  h, x = data[i]
  for j in range(h):
    if 0 < j < (h-1):
      print("#" + "." * (x - 2) + "#")
    else:
      print("#" * x)
  print("")


Measured memory_bytes: 5624
def slove():
    import sys, heapq
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    a = list(map(int, input().rstrip('\n').split()))
    bc = [list(map(int, input().rstrip('\n').split())) for _ in range(m)]
    heapq.heapify(a)
    bc = sorted(bc, key=lambda x: x[1], reverse=True)
    for b, c in bc:
        bo = True
        for i in range(b):
            p = heapq.heappop(a)
            if p < c:
                heapq.heappush(a, c)
            else:
                heapq.heappush(a, p)
                bo = False
                break
        if not bo:
            break
    print(sum(a))


if __name__ == '__main__':
    slove()


Measured memory_bytes: 91008
import java.util.Scanner;

public class Main {

	/*
	 * 0と1が両方とも残っているということは、どこかで隣り合っているはず。
	 * つまり、どちらか一方がすべて消えるまでしか処理は行えない。
	 * どちらか一方が消える　=　0と1のどちらか小さい個数に合わせる必要がある
	 * 消えるのはAとBの二つなので、ブロックの個数をそれぞれC0とC1と置くと
	 * Math.min(C0,C1)*2が答え 
	 * 
	 */
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String S = in.next();
		int C0 = 0;
		int C1 = 0;
		for (int i = 0; i < S.length(); i++) {
			if (S.charAt(i) == '0') C0++;
			else C1++;
		}
		
		System.out.println(Math.min(C0, C1)*2
				);
	}

}


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

#define trace(...) __f( #__VA_ARGS__ , __VA_ARGS__ )
template <typename Arg1>
void __f( const char* name , Arg1&& arg1 ) {
        cerr << name << " : " << arg1 << "\n";
}
template <typename Arg1, typename... Args>
void __f( const char* na , Arg1&& arg1 , Args&&... args ) {
        const char* c = strchr( na + 1 , ',' );
        cerr.write( na , c - na ) << " : " << arg1 << " , ";
        __f( c + 1 , args... );
}
#define endl "\n"
#define all(V) V.begin(),V.end()
#define Unique(V) sort(all(V)),V.erase(unique(all(V)),V.end())
#define IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long int LL;
typedef pair <int,int> pii;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const double EPS = 1e-9;
const double PI = acos(-1.0);
const long long INF = 1e18;
const int N = 1e5 + 5;

int main( ) {
        IO;
        #ifdef LOCAL
            freopen( "input.txt" , "r" , stdin );
        #endif // LOCAL
        int n;
        string s;
        cin >> n >> s;
        if( n >= 3200 ) cout << s << endl;
        else cout << "red" << endl;
        return 0;
}










Measured memory_bytes: 384
N, C = map(int,input().split())
D = []
for i in range(C):
    t = list(map(int,input().split()))
    D.append(t)
c = []
for i in range(N):
    t = list(map(int,input().split()))
    c.append(t)
Dsum = []
for k in range(C):
    ccc = [0, 0, 0]
    for i in range(N):
        for j in range(N):
            ccc[(i+j)%3] += D[c[i][j]-1][k]
    Dsum.append(ccc)
ans = 9876543210
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i != j and j != k and k != i:
                ans = min(ans, Dsum[i][0]+Dsum[j][1]+Dsum[k][2])
print(ans)

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

int main () {
  int N, T;
  cin >> N >> T;
  vector<int> c(N);
  vector<int> t(N);
  for(int i = 0; i < N; i++) {
    cin >> c.at(i) >> t.at(i);
  }
  
  int ans = c.at(0);
  int judge = t.at(0);
  for(int i = 1; i < N; i++) {
    if (t.at(i) <= T && c.at(i) < ans) {
      ans = c.at(i);
      judge = t.at(i);
    }
  }
  if (judge > T) cout << "TLE" << endl;
  else cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

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

        int N = sc.nextInt();
        int[] T = new int[N];
        for (int i = 0; i < T.length; ++i) {
            T[i] = sc.nextInt();
        }
        int M = sc.nextInt();
        int[] P = new int[M];
        int[] X = new int[M];
        for (int i = 0; i < M; ++i) {
            P[i] = sc.nextInt();
            X[i] = sc.nextInt();
        }

        System.out.println(solve(T, P, X));

        sc.close();
    }

    static String solve(int[] T, int[] P, int[] X) {
        int total = Arrays.stream(T).sum();

        return IntStream.range(0, P.length).mapToObj(i -> String.valueOf(total + X[i] - T[P[i] - 1]))
                .collect(Collectors.joining("\n"));
    }
}

Measured memory_bytes: 27980
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll MOD = 998244353;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
ll a[100000];int n;
bool can(int k) {
	ll sum = 0;
	rep(i, k) {
		sum += a[i];
	}
	Rep(i, k, n) {
		if (sum * 2 >= a[i])sum += a[i];
		else return false;
	}
	return true;
}
int main() {
	cin >> n;
	rep(i, n) {
		cin >> a[i];
	}
	sort(a, a + n);
	int le = 0; int ri = n;
	while (ri - le > 1) {
		int mid = (ri + le) / 2;
		if (can(mid))ri = mid;
		else le = mid;
	}
	cout << n-ri+1 << endl;
	return 0;
}

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

using namespace std;
using ll = long long;

const int MOD = 1e9+7;

int main()
{
    int N;cin >> N;
    vector<int> vec;
    for(int i = 0;i < N;i++){
        int b;cin >> b;
        vec.push_back(b);
    }
    ll ans = 0;
    sort(vec.begin(), vec.end());
    for(int i = 0;i < N-1;i++){
        for(int j = i + 1;j < N;j++){
            int sum = vec.at(i) + vec.at(j);
            int uku = abs(vec.at(i) - vec.at(j));
            if(vec.front() >= sum)continue;
            int ok = 0;
            int ng = N;
            while(ng  - ok > 1){
                int mid = (ok + ng) / 2;
                if(vec.at(mid) < sum){
                    ok = mid;
                }else{
                    ng = mid;
                }
            }
            auto usi = upper_bound(vec.begin(), vec.end(), uku);
            if(usi == vec.end())continue;
            int uu = usi - vec.begin();

            //cout<<i<<" "<<j<<" "<<uu<<" "<<ok<<endl;

            ans += max(ok - uu + 1, 0);
            if(uu <= i && i <= ok){
                ans--;
            }
            if(uu <= j && j <= ok){
                ans--;
            }
           // cout<<ans<<endl;
        }
    }
    cout<<ans/3<<endl;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")

#include <bits/stdc++.h>

// 汎用マクロ
#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for (long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define DSRNG(i,is,ie) for (long long i=(is), i##_end=(ie); i>=i##_end; i--)
#define UNIQUE(v) { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); }
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 (a > b) {a = b; return 1;} return 0; }
#define INF 0x7FFFFFFF
#define LINF 0x7FFFFFFFFFFFFFFFLL
#define Yes(q) (q ? "Yes" : "No")
#define YES(q) (q ? "YES" : "NO")
#define DUMP(q) cerr << "[DEBUG] " #q ": " << (q) << " at " __FILE__ ":" << __LINE__ << endl
#define DUMPALL(q) { cerr << "[DEBUG] " #q ": ["; REP(dumpall_i, (q).size()) { cerr << q[dumpall_i] << (dumpall_i == (q).size() - 1 ? "" : ", "); } cerr << "] at " __FILE__ ":" << __LINE__ << endl; }

// gcc拡張マクロ
#define gcd __gcd
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// エイリアス
using  ll = long long;
using ull = unsigned long long;
using  ld = long double;
using namespace std;

// モジュール


// 処理内容
int main() {
    
    ll n, m; cin >> n >> m;
    vector<pair<ll,ll>> c;
    REP(i, n) {
        ll a; cin >> a;
        c.emplace_back(a, 1);
    }
    REP(i, m) {
        ll b, c_; cin >> b >> c_;
        c.emplace_back(c_, b);
    }

    sort(ALL_OF(c), greater<pair<ll,ll>>());
    ll ans = 0;
    for (ll rem = n, i = 0, l = c.size(); i < l && rem > 0; i++) {
        ll g = min(rem, c[i].second);
        rem -= g;
        ans += c[i].first * g;
    }
    cout << ans << endl;
    
}

Measured memory_bytes: 6384
import java.io.*;
import java.util.*;

/**
 * @author:26019
 */
public class Main {

    public static void main(String[] args) throws Exception {
        solve();
    }

    private static long gcd(long x, long y) {
        if (y == 0) return x;
        return gcd(y, x % y);
    }

    private static int cal(int x) {
        int res = 1;
        while (x != 1) {
            if ((x & 1) == 1) {
                x = x * 3 + 1;
            } else {
                x >>= 1;
            }
            res++;
        }
        return res;
    }

    private static void solve() throws Exception {
        FastScanner cin = new FastScanner();
        int n = cin.nextInt();
        String s = cin.next() + " ";
        int res = 0;
        for (int i = 1; i <= n; i++) {
            if (s.charAt(i) != s.charAt(i - 1))
                res++;
        }
        System.out.println(res);
    }


    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        FastScanner() throws IOException {
        }

        public String next() {
            while (!st.hasMoreTokens())
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

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

        public int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

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

        private void close() {
            try {
                br.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
}


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

int n;

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


int main(){
	cin >> n;
	vector<int> ashiba(n);
	for (int i = 0; i < n;i++) cin >> ashiba.at(i);
	vector<int> ashiba_sum(n,INT_MAX);
	ashiba_sum.at(0) = 0;
	ashiba_sum.at(1) = abs(ashiba.at(1) - ashiba.at(0));
 	for (int j =2;j < n;j++){
		chmin(ashiba_sum.at(j), ashiba_sum.at(j-1) + abs(ashiba.at(j) - ashiba.at(j-1)));
        chmin(ashiba_sum.at(j), ashiba_sum.at(j-2) + abs(ashiba.at(j) - ashiba.at(j-2)));
	}
	cout << ashiba_sum.at(n-1)  << endl;
}

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

typedef int64_t Int;
#define all(x) (x).begin(), (x).end()
 
const double EPS = 1e-10;
const Int INF = 1e18;
const int inf = 1e9;
const Int mod = 1e9+7;

bool print_space_enable = false;
void print() { 
    cout << endl; 
    print_space_enable = false;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    if (print_space_enable) cout << " ";
    cout << fixed << setprecision(15) << head;
    print_space_enable = true;
    print(std::forward<Tail>(tail)...);
}

template<typename T>
void print(vector<T> v) {
    for (size_t i = 0; i < v.size(); i++) {
        if (i > 0) std::cout << " ";
        std::cout << v[i];
    }
    std::cout << std::endl;
}

int main() {
    Int n;
    cin >> n;
    vector<Int> a(n);
    for (Int i = 0; i < (Int)n; i++) {
        cin >> a[i];
    }
    map<Int, Int> mp;
    for (Int i = 0; i < (Int)n; i++) {
        mp[a[i]]++;
    }
    Int sum = 0;
    for (Int i = 0; i < (Int)n; i++) {
        sum += a[i];
    }
    Int q;
    cin >> q;
    for (Int i = 0; i < (Int)q; i++) {
        Int b, c;
        cin >> b >> c;
        sum -= mp[b] * b;
        sum += mp[b] * c;
        mp[c] += mp[b];
        mp[b] = 0;
        print(sum);
    }
    return 0;
}

Measured memory_bytes: 10040
#include <bits/stdc++.h>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <map>
#include <bitset>
#include <cmath>
#include <set>

#define INF 1000000000000
#define MOD 1000000007 //10^9+7:合同式の法

using namespace std;
typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)

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

    ll d;

    d = c - a - b;;

    if(d > 0 and d * d > 4 * a * b){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define va first
#define vb second
#define lb lower_bound
#define pb push_back
#define all(v) v.begin(),v.end()
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
using ll = long long;
using lf = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
ll D[100005];
int h[100005];
int n;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> h[i];
    h[0] = 1e9;
    for(int i = 2; i <= n; i++){
        D[i] = min(D[i-1] + abs(h[i] - h[i-1]), D[i-2] + abs(h[i] - h[i-2]));
    }
    cout << D[n] << '\n';
}


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

t=0
T=[]
for i in range(N):
    for j in range(N):
        if i==j:
            t+=A[0][j]+A[1][j]
        elif i<j:
            t+=A[1][j]
        elif i>j:
            t+=A[0][j]
        if j==N-1:
            T.append(t)
            t=0


print(max(T))


Measured memory_bytes: 3064
#include<stdio.h>
#include<string.h>

int n, c;
int a[33], b[33], memo[33][1<<18];

void input(){

  memset(a, 0, sizeof(a));
  memset(b, 0, sizeof(b));
  memset(memo, -1, sizeof(memo));
  int i, j, p;

  for(i=0;i<n;i++)
    for(j=0;j<16;j++){
      scanf("%d", &p);
      a[i] |= p<<j;
    }
  
  for(i=0;i<c;i++)
    for(j=0;j<16;j++){
      scanf("%d", &p);
      b[i] |= p<<j;
    }
}

int cnt(int bit){
  int ret = 0;
  for(;bit;bit=bit>>1) ret += bit&1;

  return ret;
}

int max(int a, int b){
  return a>b?a:b;
}

int solve(int p, int bit){
  
  if(p == n) return 0;
  if(~memo[p][bit]) return memo[p][bit];

  int ret = -1<<28, i;
  for(i=0;i<c;i++)
    ret = max(ret, solve(p+1, (a[p+1]|(bit&(bit^b[i]))))+cnt((bit&b[i])));

    return memo[p][bit] = ret;
}

int main(){

  while(!scanf("%d%d", &n, &c)|n|c){
    input();
    printf("%d\n", solve(0, a[0]));
  }

}

Measured memory_bytes: 34400
N = int(input())
A = [0]*N

for r in range(N): A[r] = int(input())
A_max = max(A)
A_sec = sorted(A)[-2]

for r in range(N):
  if A[r] == A_max: print(A_sec)
  elif A[r] == A_sec: print(A_max)
  else: print(A_max)

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

using namespace std;

int main(){
    string n;cin>>n;
    long long zbr=0;
    for(int i=0;i<n.size();i++){
        zbr+=(int)n[i]-48;
    }
    if(zbr%9==0)
        cout <<"Yes"<<endl;
    else
        cout <<"No"<<endl;
}


Measured memory_bytes: 3752
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <numeric>
#define R(a,b,c) for(register int a = (b); a <= (c); ++a)
#define nR(a,b,c) for(register int a = (b); a >= (c); --a)
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define MP make_pair
#ifdef QWQ
#define D_e_Line printf("\n--------\n")
#define D_e(x) cout << (#x) << " : " << x << endl
#define C_e(x) cerr << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <assert.h>
#define TIME() fprint(stderr, "TIME : %.3lfms\n", (double)clock() / CLOCKS_PER_SEC)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#else
#define D_e_Line
#define D_e(x)
#define C_e(x)
#define Pause
#define FileOpen()
#define FileSave()
#define TIME()
#define dbg(...)
#endif
struct FastIO {
	template<typename ATP> inline FastIO& operator >> (ATP &x) {
		x = 0; int f = 1; char c;
		for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
		while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();
		if(f == -1) x = -x;
		return *this;
	}
} io;
using namespace std;
template<typename ATP> inline ATP Max(ATP x, ATP y) {
	return x > y ? x : y;
}
template<typename ATP> inline ATP Min(ATP x, ATP y) {
	return x < y ? x : y;
}
template<typename ATP> inline ATP Abs(ATP x) {
	return x < 0 ? -x : x;
}
#include <vector>

const int N = 1e5 + 7;

vector<int> G[N];

int f[N];
int siz[N];
inline void DFS(int u, int father) {
	R(i,0,G[u].size() - 1){
		int v = G[u][i];
		if(v == father) continue;
		DFS(v, u);
		f[u] ^= f[v] + 1;
	}
}

int main() {
	int n;
	io >> n;
	R(i,2,n){
		int u, v;
		io >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	DFS(1, 1);
//	R(i,1,n) D_e(f[i]);
	if(f[1]){
		printf("Alice");
	}
	else{
		printf("Bob");
	}
	return 0;
} 

Measured memory_bytes: 10112
#include <iostream>

using namespace std;

int main() {
  int A, B;
  cin >> A >> B;

  if(B == 1) {
    cout << 0 << endl;
    return 0;
  }

  int outlet = A;
  int count = 1;
  while(outlet < B) {
    outlet += (A - 1);
    count++;
  }
  cout << count << endl;

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main()
{
    string s,t,u;
    int a,b;
    cin>>s>>t>>a>>b>>u;
    if(s==u)
        a-=1;
    else
        b-=1;
    cout<<a<<" "<<b<<endl;
}

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

int main(){
  string s;
  char ans;
  int p[30] = {0};
  
  cin >> s;
  for(int i = 0; i < s.size(); i++){
    p[s[i] - 'a'] = 1;
  }
  
  for ( int i = 0; i < 26; i++){
    if(p[i] == 0){
      ans = 'a' + i;
      cout << ans << endl;
      return 0;
    }
  }
  cout << "None" << endl;
}

Measured memory_bytes: 512
// https://atcoder.jp/contests/dp/tasks/dp_h

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DUMP(a, n) REP(i, n) printf("%d%c", a[i], i + 1 == n ? '\n' : ' ')
#define DUMP2D(a, n, m) REP(i, n) REP(j, m) printf("%d%c", a[i][j], j + 1 == m ? '\n' : ' '); puts("")

const int H_MAX = 1000;
const int W_MAX = 1000;
const int MOD = 1e9+7;

int H, W;
char a[H_MAX][W_MAX + 1];

int dp[H_MAX][W_MAX];

void solve() {
  dp[0][0] = 1;
  REP(i, H) REP(j, W) {
    if (a[i][j] != '.') continue;
    if (j + 1 < W && a[i][j + 1] == '.') {
      dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % MOD;
    }
    if (i + 1 < H && a[i + 1][j] == '.') {
      dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % MOD;
    }
  }
  // DUMP2D(dp, H, W);
  printf("%d\n", dp[H - 1][W - 1]);
}

void input() {
  scanf("%d%d", &H, &W);
  REP(i, H) scanf("%s", a[i]);
}

int main() {
  input();
  solve();
  return 0;
}


Measured memory_bytes: 5120
#include <cstdio>
#include <iostream>
#include<complex>

using namespace std;
typedef complex<double> P;
 
P project(P a, P b, P c){
  b -= a, c -= a;
  return a + b * real(c / b);
}

int main(){
  int n;
  double ax, ay, bx, by, cx, cy;
  cin >> ax >> ay >> bx >> by >> n;
  while(n--) {
    cin >> cx >> cy;
    P p = project(P(ax, ay), P(bx, by), P(cx, cy));
    printf("%.8f %.8f\n",p.real(),p.imag());
  }
  return 0;
}



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

#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#define dumpv(...)
#endif

#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
const int MOD = 1e9 + 7;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;

ll dp[100005][2]; // [i][less]

#define mins(x, y) (x = min(x, y))
#define maxs(x, y) (x = max(x, y))

void solve() {
  int n;
  ll k;
  cin >> n >> k;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  int m = 40;
  // while (!((k >> (m - 1)) & 1)) m--;
  dump(n, k, m, a);
  vi c(m);
  rep(i, m) rep(j, n) {
    int x = (int)((a[j] >> i) & 1);
    if (x) c[i]++;
  }
  dump(c);
  rep(i, m) rep(less, 2) dp[i][less] = -1;
  dp[0][0] = 0;
  // rep(i, m) rep(less, 2) rep(d, 2) {
  //   int j = m - i - 1;
  //   int x = (int)((k >> j) & 1);
  //   int nless = less;
  //   if (less == 0 && x < d) continue;
  //   if (less == 0 && x > d) nless = 1;
  //   ll val;
  //   if (x == 0) val = c[j] * (ll)(1ll << j);
  //   else if (d == 0) val = c[j] * (ll)(1ll << j);
  //   else val = (n - c[j]) * (ll)(1ll << j);
  //   if (dp[i][less] >= 0) {
  //     dp[i + 1][nless] = max(dp[i + 1][nless], dp[i][less] + val);
  //     dump(i, j, d, x, less, nless, c[j], val, dp[i][less], dp[i+1][nless]);
  //   }
  // }
  rep(i, m) {
    int j = m - i - 1;
    int x = (int)((k >> j) & 1);
    ll mask = 1ll << j;
    if (dp[i][1] >= 0) {
      //これは、すでに X < Kなる場合が存在する時
      //この時、この桁については1でも0でも構わない
      maxs(dp[i + 1][1], dp[i][1] + mask * max(c[j], n - c[j]));
    }
    if (dp[i][0] >= 0) {
      if (x == 0) {
        maxs(dp[i + 1][0], dp[i][0] + mask * c[j]);
      } else {
        maxs(dp[i + 1][1], dp[i][0] + mask * c[j]);
        maxs(dp[i + 1][0], dp[i][0] + mask * (n - c[j]));
      }
    }
    dump(i, j, x, dp[i + 1][0], dp[i + 1][1]);
  }
  dump(dp[m][0], dp[m][1]);
  ll ans = max(dp[m][0], dp[m][1]);
  cout << ans << endl;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  // freopen("temp.1", "r", stdin);
  solve();
  return 0;
}

Measured memory_bytes: 1024
import sys

x, y = map(int, input().split())

for i in range(1,x + 1):
    if 2 * i + 4 * (x-i) == y:
        print('Yes')
        sys.exit()
        
for i in range(1,x + 1):
    if 4* i + 2* (x-i) == y:
        print('Yes')
        sys.exit()
print('No')


Measured memory_bytes: 9176
import math
i=int(input())
alphabet=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
ans=""
a=0
b=0
for k in range (100):
    a+=math.pow(26,k+1)
    if i<=a:
        co=k+1
        break
    b+=math.pow(26,k+1)

i=i-b-1
for k in range(co):
    j=int(i%26)
    ans=alphabet[j]+ans
    i=i//26

print(ans)

Measured memory_bytes: 9364
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define pb push_back
#define inf 10000000000000000
#define N 1000000007
#define speed ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
template<class L,class R> ostream& operator<<(ostream& cout,pair<L, R> P)
{return cout<<'('<<P.x<<','<< P.y<<')';}
template<class T> ostream& operator<<(ostream& cout,vector<T> V)
{cout<<"[ ";for(auto v:V)cout<<v<<' ';return cout<<']';}

int n,m;
vector<string> inp;




//edge cases when n=1 , m=1. wrong variable in loop. if<->while
signed main()
{
	speed

	cin>>n>>m;
	inp.resize(n);
	for (int i = 0; i < n; ++i)
	{
		cin>>inp[i];
	}
	vector<vector<int> > dp(n,vector<int> (m,inf));
	dp[0][0]=(inp[0][0]=='#');
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<m;++j)
		{
			if(i==0 and j==0){continue;}

			int lx=i;
			int ly=j-1;
			if(ly>=0)
			{
				if(inp[lx][ly]==inp[i][j])
				{
					dp[i][j]=min(dp[i][j],dp[lx][ly]);
				}
				else
				{
					if(inp[i][j]=='#'){dp[i][j]=min(dp[i][j],dp[lx][ly]+1);}
					else
					{
						dp[i][j]=min(dp[i][j],dp[lx][ly]);
					}
				}
			}
			lx=i-1;
			ly=j;
			if(lx>=0)
			{
				if(inp[lx][ly]==inp[i][j])
				{
					dp[i][j]=min(dp[i][j],dp[lx][ly]);
				}
				else
				{
					if(inp[i][j]=='#'){dp[i][j]=min(dp[i][j],dp[lx][ly]+1);}
					else
					{
						dp[i][j]=min(dp[i][j],dp[lx][ly]);
					}
				}
			}
		}
	}
	cout<<dp[n-1][m-1]<<"\n";
}

Measured memory_bytes: 384
/*
ID: richard124
PROB: kimbits
LANG: C++11
*/


#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <chrono>
#include <algorithm>
#include <bitset>

using namespace std;
using namespace std::chrono;

typedef pair<int, int> pii;
#define pb push_back;

string s;
int ans = 0;

int main() {
	high_resolution_clock::time_point t1 = high_resolution_clock::now();
	
	cin >> s;
	for (int i=0; i<4; i++) {
     if (s[i] == '+') {
      ans++; 
     }
      else {
       ans--; 
      }
    }
	cout << ans;

	
	return 0;
}

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

void combination(int n, vector<vector<int>> &v) {
	vector<int> nums(n);
	for (int i = 0; i < n; i++) {
		nums.at(i) = i;
	}
	do {
		vector<int> vec(n);
		vec = nums;
		v.push_back(vec);
	} while (next_permutation(nums.begin(), nums.end()));

}

double distance(vector<int> p1, vector<int> p2) {
	double d = sqrt(pow(p2.at(1) - p1.at(1), 2) + pow(p2.at(2) - p1.at(2), 2));
	return d;
}

int main()
{
	int N;
	cin >> N;
	vector<vector<int>> points(N);
	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		points.at(i) = {i, x, y};
	}

	vector<vector<int>> comb;
	combination(N, comb);
	double d_sum = 0;
	for (auto p : comb) {
		double d = 0;
		for (int i = 0; i < N - 1; i++) {
			d += distance(points.at(p.at(i)), points.at(p.at(i + 1)));
		}
		d_sum += d;
	}
	double ans = d_sum / comb.size();
	cout << fixed << setprecision(10) << ans << endl;

}


Measured memory_bytes: 3256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
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 (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
    //cout << fixed << setprecision(15);
	
    ll H; cin >> H;
    ll H2 = H;
    ll n = 0;
    ll ans = 0;
    while(H2 > 0) { H2 /= 2; n++; }
    ll wa = 1;
    ll wa2 = 1;
    rep(i,n) {
        ans += wa;
        wa2 *= 2;
        wa = wa2 - 1;
    }
    cout << wa << endl;

}

Measured memory_bytes: 256
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <set>
#include <stdio.h>
#include <string>
#include <utility>
#include <vector>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<long long> v(n);
  for (int i = 0; i < n; i++)
    cin >> v[i];
  sort(v.begin(), v.end());
  if (n == 2) {
    cout << abs(v[0] - v[1]) << endl;
    return 0;
  } else if (n == 3) {
    cout << max(max(abs(v[0] - v[2]) + abs(v[1] - v[2]),
                    abs(v[2] - v[0]) + abs(v[0] - v[1])),
                abs(v[1] - v[0]) + abs(v[2] - v[0]))
         << endl;
    return 0;
  }
  if (n % 2 == 0) {
    vector<long long> up, down;
    for (int i = 0; i < n / 2 - 1; i++) {
      down.push_back(v[i]);
      up.push_back(v[n - 1 - i]);
    }
    long long mi = v[n / 2 - 1], mm = v[n / 2];
    long long ans = (mm - mi) * (n - 1);
    for (int i = 0; i < down.size(); i++) {
      ans += (mi - down[i]) * 2;
    }
    for (int i = 0; i < up.size(); i++) {
      ans += (up[i] - mm) * 2;
    }
    cout << ans << endl;
  } else {
    vector<long long> up, down;
    int mii = n / 2 - 1, mmi = n / 2;
    for (int i = 0; i < mii; i++) {
      down.push_back(v[i]);
    }
    for (int i = n - 1; i > mmi; i--) {
      up.push_back(v[i]);
    }
    long long ans1 = (v[mmi] - v[mii]) * (n - 2);
    for (int i = 0; i < down.size(); i++) {
      ans1 += (v[mii] - down[i]) * 2;
    }
    for (int i = 0; i < up.size(); i++) {
      ans1 += (up[i] - v[mmi]) * 2;
    }
    up.clear();
    down.clear();
    mii = n / 2;
    mmi = n / 2 + 1;
    for (int i = 0; i < mii; i++) {
      down.push_back(v[i]);
    }
    for (int i = n - 1; i > mmi; i--) {
      up.push_back(v[i]);
    }
    long long ans2 = (v[mmi] - v[mii]) * (n - 2);
    for (int i = 0; i < down.size(); i++) {
      ans2 += (v[mii] - down[i]) * 2;
    }
    for (int i = 0; i < up.size(); i++) {
      ans2 += (up[i] - v[mmi]) * 2;
    }
    cout << max(ans1, ans2) << endl;
  }
  return 0;
}


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

#define rep(i,n) for(int i=0;i<(int)n;++i)
#define SZ(a) (int)((a).size())
#define mp make_pair
#define pb push_back
#define F first
#define S second
typedef pair<int,int> PI;
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};

int w,h;
int mei[100][100];
void solve(){
  //cout << w << h << endl;
  memset(mei,0,sizeof(mei));
  
  rep(i,100)rep(j,100) mei[i][j]=i%2 && j%2;
  int cnt = 0;
  
  rep(i,h*2-1){
    rep(j,w-(~i&1)){
      //cout <<w-(~i&1) << endl;
      ++cnt;
      int t;
      cin >> t;
      if(i&1) mei[i][j*2] = t;
      else mei[i][j*2+1] = t;
    }
  }
  //cout << cnt << endl;

  

  queue<pair<int,PI> > q;
  q.push(mp(0,mp(0,0)));
  
  while(!q.empty()){
    int cc = q.front().F;
    int cx = q.front().S.F;
    int cy = q.front().S.S;

    q.pop();
    if(cx >= h*2 || cy >= w*2 || cx<0 || cy < 0) continue;    
    if(mei[cx][cy]) continue;
    mei[cx][cy]  = 1;
    
    if( cx == h*2-2 && cy == w*2-2){
      cout << cc/2 +1<< endl;
      return;
    }
    rep(i,4) q.push(mp(cc+1,mp(cx+dx[i],cy+dy[i])));
  }
  
  cout << 0 << endl;
}

int main(){
  while(cin >> w >> h,w) solve();
}

Measured memory_bytes: 1264