akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

template <typename T>
struct SegTree {
	T init_val;
	int n;
	vector<T> dat;
	
	SegTree(int _n, T init_val) : init_val(init_val) {
		n = 1;
		while (n < _n) n *= 2;
		dat.resize(n * 2 - 1, init_val);
	}
	
	void update(int i, T x) {
		i += n - 1;
		dat[i] = min(dat[i], x);
		while (i > 0) {
			i = (i - 1) / 2;
			dat[i] = min(dat[i * 2 + 1], dat[i * 2 + 2]);
		}
	}
	
	void set(int i, T x) {
		dat[i + n - 1] = x;
		update(i, x);
	}
	
	// 探索範囲[a,b), 現在見ているkノード[l,r)
	T query(int a, int b, int k = 0, int l = 0, int r = -1) {
		if (r < 0) r = n;
		
		if (r <= a || b <= l) return init_val;
		if (a <= l && r <= b) return dat[k];
		return min( query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r) );
	}
};

using ll3 = tuple<ll, ll, ll>;

int N, M;
int L[112345], R[112345], C[112345];
ll dp[112345];

int main() {
	cin >> N >> M;
	
	vector<ll3> v(M);
	
	REP(i, M) {
		scanf("%d %d %d", L + i, R + i, C + i);
		L[i]--;
		R[i]--;
		
		v[i] = make_tuple(-R[i], -L[i], C[i]);
	}
	sort(ALL(v));
	
	SegTree<ll> seg(N, longINF);
	seg.update(N - 1, 0);
	
	
	REP(i, M) {
		int l, r, c;
		tie(r, l, c) = v[i];
		l = -l;
		r = -r;
		
		seg.update(l, seg.query(l, r + 1) + c);
	}
	
	ll ans = seg.query(0, 1);
	if (ans == longINF) ans = -1;
	cout << ans << endl;
	return 0;
}



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

int main() {
	int n;
	cin>>n;
	int temp,cnt=0;
	multiset<int> s;
	for(temp=0;temp<n;temp++) {
		int x;
		cin>>x;
		s.insert(x);
	}

	while(s.size()>1) {
		auto it=s.end();
		it--;
		int num=*it;
		s.erase(it);
		//cout<<num<<"\n";
		int cur=1;
		for(int temp=0;temp<31;temp++) {
			//cout<<cur<<"\n";
			if(s.find(cur-num)!=s.end()) {
				cnt++;
				s.erase(s.lower_bound(cur-num));
				break;
			}
			cur=cur*2;
		}
	}
	cout<<cnt<<"\n";

}

Measured memory_bytes: 9600
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cctype>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<deque>
#include<list>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<queue>
#include<vector>
using namespace std;

//????????±?????¨??????
int lcs(string X, string Y) {
	static const int MAX_X = 1000, MAX_Y = 1000;
	static int dp[MAX_X + 1][MAX_Y + 1];
	memset(dp, 0, sizeof(dp));
	for (int i = 1; i <= X.size(); i++) {
		for (int j = 1; j <= Y.size(); j++) {
			if (X[i - 1] == Y[j - 1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else {
				dp[i][j] = max(
					dp[i - 1][j],
					dp[i][j - 1]
				);
			}
		}
	}
	return dp[X.size()][Y.size()];
}

int main() {
	int q; cin >> q;
	while (q--) {
		string X, Y; cin >> X >> Y;
		cout << lcs(X, Y) << endl;
	}
	return 0;
}

Measured memory_bytes: 5136
def wantp(n):

    q = []
    while p[n] != n:
        q.append(n)
        n = p[n]

    for i in q:
        p[i] = n

    return n

N = int(input())

oXYi = []
XYi = []
YXi = []

for i in range(N):

    x,y = map(int,input().split())
    oXYi.append([x,y,i])
    XYi.append([x,y,i])
    YXi.append([y,x,i])

p = [i for i in range(N)]
rank = [1] * N

XYi.sort()
YXi.sort()


li = -1
for i in range(N):

    if XYi[i][0] != XYi[li][0]:
        li = i

    else:
        ti = XYi[i][2]
        tli = XYi[li][2]
        ip = wantp(ti)
        lip = wantp(tli)

        if ip != lip:
        
            if rank[ip] < rank[lip]:
                p[ip] = lip
            elif rank[ip] > rank[lip]:
                p[lip] = ip
            else:
                p[lip] = ip
                rank[ip] += 1

li = -1
for i in range(N):

    if YXi[i][0] != YXi[li][0]:
        li = i

    else:
        ti = YXi[i][2]
        tli = YXi[li][2]
        ip = wantp(ti)
        lip = wantp(tli)
        
        if ip != lip:
        
            if rank[ip] < rank[lip]:
                p[ip] = lip
            elif rank[ip] > rank[lip]:
                p[lip] = ip
            else:
                p[lip] = ip
                rank[ip] += 1       

ndic = {}
xkazu = {}
ykazu = {}

for i in range(N):

    np = wantp(i)
    if np not in ndic:
        ndic[np] = 1
    else:
        ndic[np] += 1

    if np not in xkazu:
        xkazu[np] = {}
        ykazu[np] = {}

    xkazu[np][oXYi[i][0]] = 1
    ykazu[np][oXYi[i][1]] = 1

ans = 0

for i in ndic:
    ans += len(xkazu[i]) * len(ykazu[i]) - ndic[i]

print (ans)

Measured memory_bytes: 110680
#include <iostream>

bool sieve[10000001];

int main() {
	int n;

	sieve[1] = true;
	for (int i = 2; i < 10000000; ++i) {
		if (!sieve[i]) {
			for (int j = 2; i*j <= 10000000; ++j)
				sieve[i * j] = true;
		}
	}

	while (std::cin >> n) {
		if (n == 0)
			return 0;
		for (int i = n; i >= 13; --i) {
			if (!(sieve[i] || sieve[i - 2] || sieve[i - 6] || sieve[i - 8])) {
				std::cout << i << std::endl;
				break;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 10924
S = input()

def pj(cond):
  print({True: "Yes", False:"No"}[cond])

d = {}
for c in S:
  if c in d:
    d[c] += 1
  else:
    d[c] = 1
if len(d.keys()) != 2:
  pj(False)
  exit(0)
if not all(i == 2 for i in d.values()):
  pj(False)
  exit(0)
pj(True)

Measured memory_bytes: 8832
object Main extends App {
    val Array(x1,y1,x2,y2) = scala.io.StdIn.readLine().split("\\s").map(_.toInt)

    val v12 = Seq(x2-x1,y2-y1)

    def rotate(v:Seq[Int]):Seq[Int] = {
      val a = Seq(-v(1),v(0))
      a
    }

    val v23 = rotate(v12)

    val point2 = Seq(x2,y2)
    val point3 = (point2 zip v23).map { case (x, y) => x + y }

    val v34 = rotate(v23)
    val point4 = (point3 zip v34).map { case (x, y) => x + y }

    println((point3 ++ point4).map(_.toString).mkString(" "))
}

Measured memory_bytes: 25652
N, X = map( int, input().split())
L = list( map( int, input().split()))

bouncing_cnt_in_range = 1
current_ball_position = 0
for next_step in L:
  current_ball_position += next_step
  if current_ball_position <= X:
    bouncing_cnt_in_range += 1
  else:
    break
  
print( bouncing_cnt_in_range )


Measured memory_bytes: 2940
#include "bits/stdc++.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
/*----------------------------------------------------------------*/

// int MOD = 998244353;
int MOD = 1000000007;
int h,w;
int id(int x,int y){
	return w*x+y;
}
#define N 401
int dp[N][N];
    

/*----------------------------------------------------------------*/
signed main(){


	cin >> h >> w;

	char s[21][21];
	rep(i,h)rep(j,w) cin >> s[i][j];



	rep(i,h*w) rep(j,h*w) dp[i][j] = MOD;
    //costの入力 0-indexedに直して入れる
	rep(i,h)rep(j,w)if(s[i][j] != '#')dp[id(i,j)][id(i,j)] = 1;
	rep(i,h-1)rep(j,w)if(s[i][j] != '#' && s[i+1][j] != '#')dp[id(i,j)][id(i+1,j)] = dp[id(i+1,j)][id(i,j)] = 1;
	rep(i,h)rep(j,w-1)if(s[i][j] != '#' && s[i][j+1] != '#')dp[id(i,j)][id(i,j+1)] = dp[id(i,j+1)][id(i,j)] = 1;

    rep(k,h*w){
        rep(i,h*w){
            rep(j,h*w){
                dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j]);
            }
        }
    }

	int mx = 0;

	rep(si,h){
		rep(sj,w){
			if(s[si][sj] == '#')continue;
			rep(gi,h){
				rep(gj,w){
					if(s[gi][gj] == '#')continue;
					mx = max(mx,dp[id(si,sj)][id(gi,gj)]);
					// cerr << si << "," << sj << " -> " << gi << "," << gj << " : " << dp[id(si,sj)][id(gi,gj)] << endl;
				}
			}
		}
	}
	cout << mx << endl;
	// cerr << dp[id(0,0)][id(0,2)] << endl;




	
	
	return 0;
}
/*----------------------------------------------------------------*/

// g++ -std=c++14 code1.cpp
// sudo pip3 install --upgrade online-judge-tools
// rm -r -f test;oj dl https://code-festival-2018-quala.contest.atcoder.jp/tasks/code_festival_2018_quala_c
// rm -r -f test;oj dl https://ddcc2020-qual.contest.atcoder.jp/tasks/ddcc2020_qual_b
// rm -r -f test;oj dl https://abc151.contest.atcoder.jp/tasks/abc151_b

Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
#define Priq priority_queue<int,vi,greater<int>>
#define pb push_back
#define mp make_pair
#define INF (1ll<<60)
signed main(){
    int H,W,N; cin>>H>>W>>N;
    int ans=H;
    vi A(N),B(N);
    rep(i,0,N) cin>>A[i]>>B[i];
    set<pii> S;
    rep(i,0,N) S.insert(mp(A[i],B[i]));
    vi C(W+1);
    C[1]=1;
    REP(i,2,W){
        C[i]=C[i-1]+1;
        while(1){
            if(S.count(mp(C[i],i))) C[i]++;
            else break;
        }
    }
    rep(i,0,N){
        int X=A[i],Y=B[i];
        X--;
        if(X>=C[Y]){
            ans=min(ans,X);
        }
        //cout<<X<<" "<<Y<<" "<<C[Y]<<endl;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 17408
a, b, c, x = 4.times.map { gets.to_i }
count = 0

(0..a).each do |i|
  (0..b).each do |j|
    (0..c).each do |k|
      count += 1 if 500 * i + 100 * j + 50 * k == x
    end 
  end 
end 

puts count


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

struct Card {char suit, value;};

void bubble(struct Card A[],int N){
    for(int i=0;i<N;i++){
        for(int j=N-1;j>=i+1;j--){
            if(A[j].value<A[j-1].value){
                swap(A[j],A[j-1]);
            }
        }
    }
}

void selection(struct Card A[],int N){
    for(int i=0;i<N;i++){
        int minj=i;
        for(int j=i;j<N;j++){
            if(A[j].value < A[minj].value) minj=j;
        }
        swap(A[i],A[minj]);
    }
}

bool isStable(struct Card C1[],struct Card C2[],int N){
    for(int i=0;i<N;i++){
        if(C1[i].suit != C2[i].suit) return false;
    }
    return true;
}

void print(struct Card A[],int N){
    for(int i=0;i<N;i++){
        if(i) cout << " ";
        cout << A[i].suit << A[i].value;
    }   
    cout << endl;
}

int main(){
    Card C1[100],C2[100];
    int N;
    char ch;

    cin >> N;
    for(int i=0;i<N;i++) cin >> C1[i].suit >> C1[i].value;
    for(int i=0;i<N;i++) C2[i] = C1[i];

    bubble(C1,N);
    selection(C2,N);

    print(C1,N);
    cout << "Stable" << endl;
    print(C2,N);
    if(isStable(C1,C2,N)){
        cout << "Stable" << endl;
    }
    else cout << "Not stable" << endl;

    return 0;
}


Measured memory_bytes: 3120
H, W = map(int, input().split())
if H < W:
  H, W = W, H
if H % 3 == 0 or W % 3 == 0:
  print(0)
else:
  h = -(-H // 3)
  w = W // 2
  s1 = [h * W, (H - h) * w, (H - h) * (W - w)]
  d1 = max(s1) - min(s1)
  s2 = [(h - 1) * W, (H - h + 1) * w, (H - h + 1) * (W - w)]
  d2 = max(s2) - min(s2)
  h = H // 2
  w = -(-W // 3)
  s3 = [H * w, h * (W - w), (H - h) * (W - w)]
  d3 = max(s3) - min(s3)
  s4 = [H * (w - 1), h * (W - w + 1), (H - h) * (W - w + 1)]
  d4 = max(s4) - min(s4)
  print(min([d1, d2, d3, d4, H, W]))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f;
const ll mod = 998244353LL;
clock_t TIME_START, TIME_END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used: %.6lf(s)\n", ((double)TIME_END - TIME_START) / CLOCKS_PER_SEC);
    system("pause");
#endif
}
ll a, b;
ll ans;
ll pri[N * 2], tot;
ll vis[N * 2];
void shaipri()
{
    for (int i = 2; i <= 1000000; ++i)
    {
        if (!vis[i])
            vis[i] = i, pri[++tot] = i;
        for (int j = 1; j <= tot && i * pri[j] <= 1e6; ++j)
        {
            vis[i * pri[j]] = pri[j];
            if (i % pri[j] == 0)
                break;
        }
    }
}

void solve()
{
    shaipri();
    cin >> a >> b;
    ll g = __gcd(a, b);
    ans = 1;
    for (int i = 1; i <= tot; ++i)
    {
        if (g % pri[i] == 0)
        {
            ans++;
            while (g % pri[i] == 0)
                g /= pri[i];
        }
    }
    ans += (g > 1);
    cout << ans << '\n';
}

int main()
{
    TIME_START = clock();
    int Test = 1;
    // cin >> Test;
    while (Test--)
        solve();
    TIME_END = clock();
    program_end();
    return 0;
}

Measured memory_bytes: 12024
/**
 * author: moririn_cocoa       
**/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;

int main(void) {
  
  int a;
  int b;
  int c;
  
  cin >> a;
  cin >> b;
  cin >> c;
  
  if ( b - a == c - b ) {
    
    cout << "YES" << endl;
  }
  
  else {
    
    cout << "NO" << endl;
  }
  
  return 0;
}


Measured memory_bytes: 3576
def main():
    n = int(input())

    if n % 10 in [2, 4, 5, 7, 9]:
        print('hon')
    elif n % 10 in [0, 1, 6, 8]:
        print('pon')
    else:
        print('bon')


if __name__ == '__main__':
    main()


Measured memory_bytes: 61936
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define mod 1000000007
#define all(v)  v.begin(),v.end()
#define pb push_back
#define size(v)  (int) v.size()
#define fast ios_base:: sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
ll power_mod(ll a,ll x){if(x==0) return 1;ll y=power_mod(a,x/2);ll ans=(y*y)%mod; if(x%2) ans=(ans*a)%mod;return ans;}
ll inv(ll a){return power_mod(a,mod-2);}    
ll power(ll a, ll x){ if(x==0) return 1; ll y= power(a,x/2); ll ans=(y*y); if(x%2) ans*=a; return ans;}
ll dp[(1<<16)+3];
int main()
{
	 fast;
	 int n;
	 cin>>n;
	 ll a[n][n];
	 for(int i=0;i<n;i++)
	 {
	 	 for(int j=0;j<n;j++)
	 	 {
	 	 	 cin>>a[i][j];
	 	 }
	 }
	
     ll length = (1<<n);
	 ll cost[length+5]={};
     memset(dp,0,sizeof(dp));
	 for(int mask=0;mask<length;mask++)
	 {
	 	 vector<ll> bits;
         for(int i=0;i<n;i++)
         {
               if(mask&(1<<i))
               {
               	  bits.pb(i);
               }
         }

         int l = size(bits);
        
         ll here = 0;
         for(int i=0;i<l;i++)
         {
         	 for(int j = i+1;j < l;j++)
         	 {
                here = here + a[bits[i]][bits[j]];   
         	 }
         }

         dp[mask]=here;
	 }
     //for(int i=0;i<length;i++) cout<<i<<" "<<cost[i]<<endl;
     
  

  
     
     for(int mask = 1; mask < length; mask++)
     {
     	 for(int s = mask; s > 0; s = (s-1)& mask)
     	 {
     	 	 dp[mask] = max(dp[mask],dp[s^mask]+dp[s]);
     	 }
     }

     cout<<dp[length-1]<<endl;



   







}

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

int main() {
    
    // 1. input.
    int a, b, c;
    cin >> a >> b >> c;
    
    // 2. output answer.
    if(a < b && b < c) cout << "Yes" << endl;
    else               cout << "No"  << endl;
    
    return 0;
    
}


Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
static const int INF (1<<30);
int N, x[10];
int ans = 0;
set<int> cnt_ans;

void judge() {
  long long tmp = 0;
  bool f3, f5, f7;
  f3 = f5 = f7 = false;
  rep(i, 9) {
    tmp += pow(10, i) * x[i];
    if (x[i] == 3) {
      f3 = true;
    } else if (x[i] == 5) {
      f5 = true;
    } else if (x[i] == 7) {
      f7 = true;
    }
  }

  if (tmp > N) return;

  if (f3 && f5 && f7) {
    ans++;
    cnt_ans.insert(tmp);
  }
}



void rec(int digit, int num) {
  if (num == 0) {
    x[digit] = 0;
    if (digit == 8) {
      judge();
    } else {
      rec(digit+1, 0);
    }

    return;
  }

  if (num == 1) {
    x[digit] = 3;
  } else if (num == 2) {
    x[digit] = 5;
  } else if (num == 3) {
    x[digit] = 7;
  }

  if (digit == 8) {
    judge();
  } else {
    rep(i, 4) {
      rec(digit+1, i);
    }
  }
}


int main() {
  cin >> N;

  rep(i, 4) {
    rec(0, i);
  }

  cout << cnt_ans.size() << endl;

  return 0;
}

Measured memory_bytes: 1536
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>
#include <time.h>
#include <numeric>
using namespace std;
//#define int long long
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define l1 list[index]
#define l2 list[index - 1]
#define l3 list[index + 1]
#define iif(i,j) ((i<0 && j<0) || (i>0 && j>0)) ? true : false 
typedef long long ll;
typedef pair<int, int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint, int> P1;
typedef pair<int, pint> P2;
typedef pair<pint, pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD = 1000000007;
const ll INF = 1e18;
const double PI = 3.14159265359;
int ca[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };




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

	if (s.length() <= k) {
		cout << s << endl;
	}
	else {
		string s2 = s.substr(0, k);
		cout << s2 << "..." << endl;
	}

	return 0;
}

Measured memory_bytes: 3584
/*
	Powered by C++11.
	Author : Alex_Wei.
*/

#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize(3)
//#define int long long

#define ll long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb emplace_back
#define all(x) x.begin(),x.end()
#define sor(x) sort(all(x))
#define rev(x) reverse(all(x))
#define mem(x,v) memset(x,v,sizeof(x))

// Templates start.

namespace IO{
	char buf[1<<21],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
	#ifdef __WIN32
		#define gc getchar()
	#else
		#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
	#endif
	#define pc(x) (*O++=x)
	#define flush() fwrite(obuf,O-obuf,1,stdout)

	inline int read(){
		int x=0,sign=0; char s=gc;
		while(!isdigit(s))sign|=s=='-',s=gc;
		while(isdigit(s))x=(x<<1)+(x<<3)+(s-'0'),s=gc;
		return sign?-x:x;
	}
	void print(int x) {if(x>9)print(x/10); pc(x%10+'0');}
}

namespace math{
	const int mod=998244353;
	const int maxn=1e6+5;

	ll ksm(ll a,ll b){ll s=1,m=a; while(b){if(b&1)s=s*m%mod; m=m*m%mod,b>>=1;} return s;}
	ll inv(ll x){return ksm(x,mod-2);}

	ll fc[maxn],ifc[maxn];
	void init_m(int n){
		fc[0]=1; for(int i=1;i<=n;i++)fc[i]=fc[i-1]*i%mod;
		ifc[n]=inv(fc[n]); for(int i=n-1;i>=0;i--)ifc[i]=ifc[i+1]*(i+1)%mod;
	}
	ll C(ll n,ll m){return fc[n]*ifc[m]%mod*ifc[n-m]%mod;}
}

// Templates end. Please give me more points.

using namespace IO;
//using namespace math;

char s; 

int main(){
	cin>>s;
	if(s>='a')cout<<'a';
	else cout<<'A';
	return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
using namespace std;
typedef long long int ll;
typedef long double ld;

#define MOD 998244353

int main(){
    ll n;
    cin >> n;
    for (ll i=n;i<1000;i++){
        if (i/100==i/10-(i/100*10) && i%10==i/100){
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}



Measured memory_bytes: 256
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <ios>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <forward_list>
#include <random>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <unordered_map>
#include <unordered_set>
#endif

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define lcm( a, b ) (a)/__gcd((a),(b))*(b)
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair< int, int > P;
typedef pair< LL, LL > LP;
typedef pair< int, P > iP;
typedef pair< P, P > PP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;
static const int SIZE = 500005;

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

vector< int > Div( int n ) {
    vector< int > ret;
    for( int i = 1; i * i <= n; ++i ) {
        if( n % i == 0 ) {
            ret.pb( i );

            if( i * i != n ) ret.pb( n / i );
        }
    }
    sort( all( ret ) );
    return ret;
}

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

    string s;
    cin >> s;
    LL size = s.size();
    LL al_cnt[26] = {};
    for( int i = 0; i < size; ++i ) {
        ++al_cnt[s[i] - 'a'];

    }

    LL res = (size * (size - 1)) / 2;
    for( int i = 0; i < 26; ++i ) {
        res -= (al_cnt[i] * (al_cnt[i] - 1)) / 2;

    }
    cout << res + 1 << endl;
    return 0;
}


Measured memory_bytes: 720
#include<bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
using LL = long long;
const LL LINF = 1e18;
using namespace std;
#define COUT(v) cout<<(v)<<endl
#define CIN(n)  int(n);cin >> (n)
#define YES(n) cout<<((n)? "YES" : "NO")<<endl
#define Yes(n) cout<<((n)? "Yes" : "No")<<endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) <<endl

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)

#define FOREACH(x,a) for(auto& (x) : (a) )

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

#define P pair<int,int>
#define I vector<int>
#define S set<int>
#define pb(v) push_back(v)
#define V vector
#define rt return
#define rmsame(a) sort(ALL(a)),a.erase(unique(ALL(a)), a.end())
class Edge{
public:
    int from,to,value;
    Edge(int a,int b,int c){
        from = a;
        to = b;
        value = c;
    }
    Edge(int a,int b){
        from = a;
        to = b;
    }
};
int main(){
    string s;cin >> s;
    Yes(s.at(0)=='9'||s.at(1)=='9');
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
int main(void){
	int b = 0,i,j = 0,n,c = 0;
	scanf("%d",&n);
	
	int a[n];
	for(i = 0;i < n;i++){
		scanf("%d",&a[i]);
	}
	for(i = 1;i < n;i++){
		b = sqrt(a[i]);
		for(j =2;j <=b;j++){
			if(a[i]%j ==0){
				c++;
				break;
			}
		}
	}
	printf("%d\n",n-c);
	
}


Measured memory_bytes: 2040
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <map>
#include <algorithm>
#include <math.h>
#include <iostream>     // std::cout, std::fixed
#include <iomanip>
#include<queue>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <iostream>
#include <sstream>
typedef long long ll;
using namespace std;

int main () {
    ios_base::sync_with_stdio(false);
    string s1;
    string s2;
    cin>>s1>>s2;
    reverse(s1.begin(), s1.end());
    if(s1==s2)
        cout<<"YES";
    else
        cout<<"NO";
    return 0;
}


Measured memory_bytes: 256
# https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_c

class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]

N, *AB = map(int, open(0).read().split())
A, B = AB[:N], AB[N:]

AI = sorted((a, i) for i, (b, a) in enumerate(sorted(zip(B, A))))

A.sort()
B.sort()

if any(a > b for a, b in zip(A, B)):
    print("No")
    quit()


uf = UnionFind(N)
for j, (a, i) in enumerate(AI):
    uf.union(i, j)

parents = {uf.find(i) for i in range(N)}
if len(parents) > 1:
    print("Yes")
    quit()

if any(a <= b for a, b in zip(A[1:], B)):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 30864
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int main(void){
    
    
    
    int N;
    cin >> N;
    vector<int> h(N);
    vector<long long> kyori(N);
    
    for(int i = 0; i < N; i++){
        cin >> h[i];
    }
    
    kyori[1] = abs(h[1] - h[0]);
    
    for(int i = 2; i < N; i++){
        int jump1 = kyori[i-1] + abs(h[i] - h[i-1]);
        int jump2 = kyori[i-2] + abs(h[i] - h[i-2]);
        if(jump1 < jump2) kyori[i] = jump1;
        else kyori[i] = jump2;
    }
    
    
    cout << kyori[N-1] << endl;
}


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

bool Prime(int num){
  if(num < 2){
    return false;
  }else if(num == 2){
    return true;
  }else if(num % 2 == 0){
    return false; 
  } 
  double sqrtNum = sqrt(num);
  for(int i=3;i<=sqrtNum;i+=2){
    if(num % i == 0){
      return false;
    }
  }
  return true;
}

signed main(){
  int num;
  bool ans;
  bool f=true;
  cin >> num;
  while (f) {
    ans = Prime(num);
    if(ans){
      cout << num << "\n";
      f = false;
    }
    num++;
  }
  return 0;
}

Measured memory_bytes: 256
#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<ll,ll>;
 
int main() {
    int N;
    char c[200000];
    cin>>N;
    cin>>c;
    int rs=0,ws=0;
    rep(i,N)
    {
      if(c[i]=='R')rs++;
      else ws++;
    }
    int diff=0;
    for(int i=0;i<rs;i++)
    {
      if(c[i]!='R')diff++;
    }
    for(int i=rs;i<N;i++)
    {
      if(c[i]!='W')diff++;
    }
    cout<<diff/2<<endl;
    return 0;
}

Measured memory_bytes: 3780
#include <iostream>
#include <string>

using namespace std;
using ll = long long;

#define ALL(x) begin(x), end(x)
#define REP(i, n) for (size_t i = 0, i##_len = (n); i < i##_len; ++i)

const string YES = "Yay!";
const string NO = ":(";

void solve(ll A, ll B) { cout << (A <= 8 && B <= 8 ? YES : NO) << endl; }

int main() {
  ll A;
  cin >> A;
  ll B;
  cin >> B;
  solve(A, B);
  return 0;
}


Measured memory_bytes: 256
module.exports=function(e){var r={};function n(t){if(r[t])return r[t].exports;var o=r[t]={i:t,l:!1,exports:{}};return e[t].call(o.exports,o,o.exports,n),o.l=!0,o.exports}return n.m=e,n.c=r,n.d=function(e,r,t){n.o(e,r)||Object.defineProperty(e,r,{enumerable:!0,get:t})},n.r=function(e){"undefined"!=typeof Symbol&&Symbol.toStringTag&&Object.defineProperty(e,Symbol.toStringTag,{value:"Module"}),Object.defineProperty(e,"__esModule",{value:!0})},n.t=function(e,r){if(1&r&&(e=n(e)),8&r)return e;if(4&r&&"object"==typeof e&&e&&e.__esModule)return e;var t=Object.create(null);if(n.r(t),Object.defineProperty(t,"default",{enumerable:!0,value:e}),2&r&&"string"!=typeof e)for(var o in e)n.d(t,o,function(r){return e[r]}.bind(null,o));return t},n.n=function(e){var r=e&&e.__esModule?function(){return e.default}:function(){return e};return n.d(r,"a",r),r},n.o=function(e,r){return Object.prototype.hasOwnProperty.call(e,r)},n.p="",n(n.s=0)}([function(e,r,n){n(1)(n(2).readFileSync("/dev/stdin","UTF-8").split("\n"))},function(e,r){function n(e,r){if(e==r)return 0;if(e>r)return 1;if(e<r)return-1;throw new Error("getinc")}e.exports=function(e){var r=Number(e[0]),t=e[1].split(" ").map(function(e){return Number(e)});if(1!=r){for(var o=1,u=n(t[1],t[0]),i=2;i<r;i++){var f=n(t[i],t[i-1]);if(0!=f&&f!=u){if(0==u){u=f;continue}o+=1,i<r-1&&(u=n(t[i+1],t[i]))}}console.log(o)}else console.log(1)}},function(e,r){e.exports=require("fs")}]);

Measured memory_bytes: 17612
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
#include<complex>
#include <cassert>

using namespace std;

#define ll long long
#define ld long double
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

const double PI=acos(-1);
const double EPS=1e-9; //うまくいかなかったらゆるめる

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef vector<pii> vp;
typedef vector<vi> vvi;

int gcd(int a, int b){if(b==0) return a;return gcd(b,a%b);}
int lcm(int a, int b){return a/gcd(a,b)*b;}


signed main(void) {
	string s;
	cin >> s;
	int ans = 0;
	rep(i,s.size()){
		int t = 0;
		while(i < s.size()){
			if(s[i] != 'A' && s[i] != 'C' && s[i] != 'G' && s[i] != 'T'){
				break;
			}else{
				t++;
				i++;
				ans = max(ans, t);
			}
		}
	}
	cout << ans << endl;

}


Measured memory_bytes: 3200
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define INF 1LL<<62

int main() {
	ll n;
	cin>>n;
	ll ch[100010];
	for(ll i=0;i<n;i++){
		cin>>ch[i];
	}
	ll x2=0;
	for(ll i=0;i<n;i++){
		ll now=n-i-1;
		if(i%2==0){
			x2+=ch[now];
		}
		else{
			x2-=ch[now];
		}
	}
	cout <<x2<<endl;x2/=2;
	for(ll i=0;i<n-1;i++){
		cout << (ch[i]-x2)*2<<endl;
		x2=(ch[i]-x2);
	}
	return 0;
}

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

#define CEIL(a,b) ((a) / (b) + ((a) % (b) == 0 ? 0 : 1))

using namespace std;
using ll = long long;
using pii = pair<int, int>;

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'000'000'001;
constexpr ll LLINF = 4'000'000'000'000'000'001;
// constexpr int INF = 2147483647; // 2 * 1e9
// constexpr ll LLINF = 9223372036854775807; // 9 * 1e18

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    int a, b, c;
    string s;
    cin >> a;// >> b >> c;
    cin >> s;
    cout << (a < 3200 ? "red" : s) << "\n";
    return 0;
}

Measured memory_bytes: 256
n = int(input())
f = []
for i in range(n):
    f.append(list(map(int, input().split(" "))))
flag = True
p = []
for i in range(n):
    p.append(list(map(int, input().split(" "))))

storeopen = [0,0,0,0,0,0,0,0,0,1]


maxmoney = None

while flag:
    money = 0
    for store in range(n):
        count = 0
        for i in range(10):
            if f[store][i] == 1 and storeopen[i] == 1:
                count += 1
        money += p[store][count]
    if maxmoney is None:
        maxmoney = money
    else:
        maxmoney = max(maxmoney, money)

    if sum(storeopen) == 10:
        flag = False
    else:
        storeopen[9] += 1
        for i in range(10):
            if storeopen[9-i] == 2:
                storeopen[9-i] = 0
                storeopen[8-i] += 1
print(maxmoney)


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

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

    int max;
    max = a;

    if(b > max) max = b;
    if(c > max) max = c;

    cout << a + b + c - max <<endl;

    return 0;
}

Measured memory_bytes: 256
fun main(arr: Array<String>) {
    val (n,t) = readLine()!!.split(" ").map { it.toInt() }
    val ans = (1..n).map { readLine()!!.split(" ").map { it.toInt() } }.filter { it[1] <= t }.map { it[0] }.min()
    println(ans?:"TLE")
}



Measured memory_bytes: 38100
#include<bits/stdc++.h>
using namespace std;
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    long long ar[n];
    for(int i = 0; i<n; i++){
        cin >> ar[i];
    }
    sort(ar,ar+n);
    long long dist = 100000000000LL;
    long long ans = 0LL;
    for(int i = 0; i+1<n; i++){
        if(llabs(ar[i]*2LL-ar[n-1])<dist){
            dist = llabs(ar[i]*2LL-ar[n-1]);
            ans = ar[i];
        }
    }
    cout << ar[n-1] << " " << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>

using namespace std;

typedef long long ll;

void solve() {
  string s;
  cin >> s;
  int inc;
  cin >> inc;
  int curr = 0;
  while(curr < s.size()) {
    cout << s[curr];
    curr += inc;
  }
  cout << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
  /*
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
  */
}


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

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

ll V[100];

ll dpl[101], dpr[101];

int main() {

    ll N, K;
    cin >> N >> K;
    rep(i, N) cin >> V[i+1];

    ll ans = 0;

    vector<ll> L;
    ll sum = 0;
    for (int l=0; l<=N; ++l) {

        // 減らすか
       if (L.size() > 0) {
           sort(L.begin(), L.end());
           ll tmp = sum;
           rep(k, L.size()) {
               tmp -= L[k];
               dpl[l+k] = max(dpl[l+k], tmp);
           }
       }

       if (l > 0) {
           sum += V[l];
           dpl[l] = max(dpl[l], sum);
           L.push_back(V[l]);
       }

        vector<ll> R;
        ll sumr = 0;
        fill(dpr, dpr+K+1, 0);
        for (int r=N+1, rcur=0; r>l; --r, rcur++) {
            if (R.size() > 0) {
                sort(R.begin(), R.end());
                ll tmp = sumr;
                rep(k, R.size()) {
                    tmp -= R[k];
                    dpr[rcur+k] = max(dpr[rcur+k], tmp);
                }
            }

            if (r <= N) {
                sumr += V[r];
                dpr[rcur] = max(dpr[rcur], sumr);
                R.push_back(V[r]);
            }
        }

        for (int a=0; a<=K; ++a) {
            for (int b=0; b<=K-a; ++b) {
                ans = max(ans, dpl[a]+dpr[b]);
            }
        }
    }
    cout << ans << endl;


    // rep(i, K) cout << dpl[i] << endl;
    // cout << endl;
    // rep(i, K) cout << dpr[i] << endl;
    // cout << ans << endl;


    //
    // vector<ll> l;
    // ll sum = 0;
    // for (int i=0; i<min(N, K); ++i) {
    //
    //     // 減らすか
    //     if (l.size() > 0) {
    //         sort(l.begin(), l.end());
    //         ll tmp = sum;
    //         rep(k, l.size()) {
    //             tmp -= l[k];
    //             dpl[i+1+k] = max(dpl[i+1+k], tmp);
    //         }
    //     }
    //
    //     sum += V[i];
    //     dpl[i+1] = max(dpl[i+1], sum);
    //     l.push_back(V[i]);
    // }
    //
    // reverse(V, V+N);
    //
    // {
    //     vector<ll> l;
    //     ll sum = 0;
    //     for (int i=0; i<min(N, K); ++i) {
    //
    //         // 減らすか
    //         if (l.size() > 0) {
    //             sort(l.begin(), l.end());
    //             ll tmp = sum;
    //             rep(k, l.size()) {
    //                 tmp -= l[k];
    //                 dpr[i+1+k] = max(dpr[i+1+k], tmp);
    //             }
    //         }
    //
    //         sum += V[i];
    //         dpr[i+1] = max(dpr[i+1], sum);
    //         l.push_back(V[i]);
    //     }
    // }
    //
    //
    // ll ans = 0;
    // for (int i=0; i<=; ++i) {
    //     for (int j=0; j<=K-i; ++j) {
    //         ans = max(ans, dpl[i]+dpr[j]);
    //     }
    // }
    //
    // cout << "l" << endl;
    // rep(i, K+1) cout << dpl[i] << endl;
    // cout << "r" << endl;
    // rep(i, K+1) cout << dpr[i] << endl;
    //
    // cout << ans << endl;

}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(final String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final long x = scanner.nextInt();
        final long i = x / 500L;
        final long j = (x - i*500L) / 5L;
        System.out.println(i * 1000L + j * 5L);
    }
}


Measured memory_bytes: 21844
///Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>

#define                           int                         long long
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<int,int>
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);




using namespace std;

const int inf=1e18;
const int mod=1e9+7;
const int M=100009;

inline int bigmod(int B,int P){int R=1;while(P>0){if(P&1){R=(R*B)%mod;}P>>=1;B=(B*B)%mod;}return R;}
inline int ad(int x,int y){int ret=(x%mod+y%mod)%mod;if(ret<0){ret+=mod,ret=ret%mod;}return ret;}
inline int sub(int x,int y){int ret=((x%mod)-(y%mod)+mod)%mod;if(ret<0){ret+=mod,ret=ret%mod;}return ret;}
inline int gun(int x,int y){int ret=((x%mod)*(y%mod))%mod;if(ret<0){ret+=mod,ret=ret%mod;}return ret;}

int h,w;
string s[105];
int dp[105][105][2];
int solve(int x,int y,int last)
{
      if(x<0 || y<0 || x>=h || y>=w)return inf;
      if(x==h-1 && y==w-1)
      {
          if(last==1 || s[x][y]=='#')return 1;
          else return 0;
      }
      int &ret=dp[x][y][last];
      if(ret!=(-1))return ret;
      int ad=0;
      if(last==0)
      {
           if(s[x][y]=='#')
           {
               ret=min(solve(x+1,y,1),solve(x,y+1,1));
           }
           else if(s[x][y]=='.')
           {
               ret=min(solve(x+1,y,0),solve(x,y+1,0));
           }
      }
      else if(last==1)
      {
           if(s[x][y]=='#')
           {
                ret=min(solve(x+1,y,1),solve(x,y+1,1));
           }
           else
           {
              ret=min(solve(x+1,y,0),solve(x,y+1,0))+1;
           }
      }
      return ret;
}
 main()
{
    fast
    memset(dp,-1,sizeof dp);
    cin>>h>>w;
    f(i,0,h-1)
    {
         cin>>s[i];
    }
    int nd=h-1+w-1+1;
    int tmp=0;
    if(s[0][0]=='#')tmp=1;
    int ses=min(solve(1,0,tmp),solve(0,1,tmp));
    cout<<ses<<endl;
    return 0;
}


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

public class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[] mountain = new int[10];
		for(int i = 0;i<10;i++){
			mountain[i] = Integer.parseInt(br.readLine());
		}
		Arrays.sort(mountain);
		for(int i = 0;i<3;i++){
			System.out.println(mountain[9-i]);
		}
	}
}

Measured memory_bytes: 24108
n,k=map(int, input().split())
a=list(map(int, input().split()))
ans=0
rev=0
for i in range(n-1):
  for j in range(i+1,n):
    if a[i]>a[j]:
      ans+=1
    if a[i]<a[j]:
      rev+=1
      
x=(ans*k*(k+1))//2
y=(rev*k*(k-1))//2
print((x+y)%(10**9+7))

Measured memory_bytes: 3188
// eddy1021
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod7=1000000007LL;
inline LL getint(){
  LL _x=0,_tmp=1; char _tc=getchar();    
  while( (_tc<'0'||_tc>'9')&&_tc!='-' ) _tc=getchar();
  if( _tc == '-' ) _tc=getchar() , _tmp = -1;
  while(_tc>='0'&&_tc<='9') _x*=10,_x+=(_tc-'0'),_tc=getchar();
  return _x*_tmp;
}
inline LL add(LL _x, LL _y, LL _mod=mod7){
  _x+=_y;
  return _x>=_mod ? _x-_mod : _x;
}
inline LL sub(LL _x, LL _y, LL _mod=mod7){
  _x-=_y;
  return _x<0 ? _x+_mod : _x;
}
inline LL mul(LL _x, LL _y ,LL _mod=mod7){
  _x*=_y;
  return _x>=_mod ? _x%_mod : _x;
}
LL mypow(LL _a, LL _x, LL _mod){
  if(_x == 0) return 1LL;
  LL _ret = mypow(mul(_a, _a, _mod), _x>>1, _mod);
  if(_x & 1) _ret=mul(_ret, _a, _mod);
  return _ret;
}
LL mymul(LL _a, LL _x, LL _mod){
  if(_x == 0) return 0LL;
  LL _ret = mymul(add(_a, _a, _mod), _x>>1, _mod);
  if(_x & 1) _ret=add(_ret, _a, _mod);
  return _ret;
}
void sleep(double sec = 1021){
  clock_t s = clock();
  while(clock() - s < CLOCKS_PER_SEC * sec);
}
#define Bye exit(0)
int __ = 1 , _cs;
/*********default*********/
const int N=2048;
void build(){

}
int n, c[N+N], a[N+N];
int pdp[2][N][N], ans;
int tg[N];
void init(){
  n=getint();
  for(int i=0; i<n+n; i++){
    char buf[8];
    scanf("%s", buf);
    a[i]=getint();
    c[i]=(buf[0]=='W');
  }
  for(int i=0; i<n+n; i++)
    for(int j=0; j<i; j++)
      if(c[i] == c[j] and a[j]>a[i])
        ans++;
  for(int i=0; i<n+n; i++){
    for(int j=1; j<=n; j++)
      tg[j]=1;
    for(int j=0; j<i; j++)
      if(c[i] != c[j])
        tg[a[j]]=0;
    for(int j=1; j<=n; j++)
      pdp[c[i]][a[i]][j]=pdp[c[i]][a[i]][j-1]+tg[j];
  }
}
int dp[N][N];
void solve(){
  for(int i=0; i<=n; i++)
    for(int j=0; j<=n; j++)
      dp[i][j]=1e9;
  dp[0][0]=0;
  for(int i=0; i<=n; i++)
    for(int j=0; j<=n; j++){
      if(i<n){
        int tdp=dp[i][j]+pdp[0][i+1][j];
        dp[i+1][j]=min(dp[i+1][j], tdp);
      }
      if(j<n){
        int tdp=dp[i][j]+pdp[1][j+1][i];
        dp[i][j+1]=min(dp[i][j+1], tdp);
      }
    }
  ans+=dp[n][n];
  cout<<ans<<endl;
}
int main(){
  build();
  //__ = getint();
  while(__ --){
    init();
    solve();
  }
}


Measured memory_bytes: 49408
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstddef>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

// clang-format off
template <typename T> T gcd(T a, T b) { return b == 0 ? a : gcd(b, a % b); }
template <typename T> T lcm(T a, T b) { return a * b / gcd(a, b); }
template <typename T> T clamp(T val, T min, T max) { return val < min ? min : (max < val ? max : val); }
template <typename T> size_t max_index(T begin, T end) { return distance(begin, max_element(begin, end)); }
template <typename T> size_t min_index(T begin, T end) { return distance(begin, min_element(begin, end)); }
// clang-format on

#define int long long
#define YES "Yes"
#define NO  "No"

using namespace std;

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

  int num = 0;

  int n; cin >> n;
  vector<int> a(n);


  
  for (int i = 0; i < n; ++i) cin >> a[i];

  vector<int> f(n);
  vector<int> g(n);
  for (int i = 0; i < n; ++i) {
    if (i == 0) {
      f[i] = a[i];
      g[n - i - 1] = a[n - i - 1];
    }
    else {
      f[i] = gcd(f[i - 1], a[i]);
      g[n - i - 1] = gcd(g[n - i], a[n - i - 1]);
    }
  }

  for (int i = 0; i < n; ++i) {
    int m = 0;
    if (i == 0) {
      m = g[i + 1];
    } else if (i == n - 1) {
      m = f[i - 1];
    } else {
      m = gcd(f[i - 1], g[i + 1]);
    }
    num = max(m, num);
  }
  
  cout << num << endl;
  
  return 0;
}


Measured memory_bytes: 2560
N = int(input())
count = 0
if N > 81:
  print("No")
elif 9 >= N >= 1:
  print("Yes")
else:
  for i in range(2, 10):
    if (N % i == 0) and (N/i <=9):
      print("Yes")
      count += 1
      break
  if count == 0:
    print("No")

Measured memory_bytes: 3060
#include<iostream>

using namespace std;

int main() {
	int A, B, C;
	cin >> A >> B >> C;
	if (A == 5 && B == 5 && C == 7 || A == 5 && B == 7 && C == 5 || A == 7 && B == 5 && C == 5) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;	
	}

	return 0;
}

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

int main() {
	int k,x;
	cin >> k >> x;
	if (500*k>=x) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256