akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

long long knap(vector<long long> val, vector<long long> wt, int n, int W) {
  vector<vector<long long>> dp(n + 1, vector<long long>(W + 1));
  
  for (int i = 1; i <= n; ++i)
    for (int w = 1; w <= W; ++w)
      if (wt[i - 1] <= w)
        dp[i][w] = max(dp[i-1][w], dp[i-1][w - wt[i - 1]] + val[i - 1]);
  	  else
        dp[i][w] = dp[i-1][w];
  
  return dp[n][W];
}

int main() {
  int N, W;
  cin >> N >> W;
  
  vector<long long> val(N), wt(N);
  
  for (int i = 0; i < N; ++i)
    cin >> wt[i] >> val[i];
  
  cout << knap(val, wt, N, W) << endl;
  return 0;
}

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

int main(){
    int n;
    cin >> n;
    vector<double> V(n);
    rep(i,n) cin >> V.at(i);
    sort(V.begin(),V.end());
    double ans = (V.at(0) + V.at(1)) / 2;
    for(int i = 2;i < n;i++) ans = (ans + V.at(i)) / 2;
    cout << ans << endl;
}         

Measured memory_bytes: 3808
#include <cstdio>
#include <cstdlib>
#include <string>
#include <iostream>
#include <algorithm>
#include <array>
#include <string.h>
#include <vector>



int main() {
	int N;
	scanf("%d", &N);

	std::vector<int> xv;
	std::vector<int> xv2;

	int tmp;
	for (int i = 0; i < N; i++) {
		scanf("%d", &tmp);
		xv.push_back(tmp);
		xv2.push_back(tmp);
	}

	std::sort(xv.begin(), xv.end());
	int s = xv[xv.size()/2 - 1];
	int l = xv[xv.size()/2];

	for (int i = 0; i < N; i++) {
		if (xv2[i] <= s) {
			printf("%d\n", l);
		}
		else {
			printf("%d\n", s);
		}

	}




	return 0;
}

Measured memory_bytes: 3948
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <tuple>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

int n;
ll a[100100];

ll solve() {
    ll res = 1;
    long double d = 1;
    sort(a, a+n);
    for (int i = 0; i < n; i++) {
        res *= a[i];
        d *= (long double)a[i];
        if (d > 1e18) return -1;
    }
    //cerr << d << endl;
    return res;
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);

    input();
    cout << solve() << endl;
}


Measured memory_bytes: 3972
#include<bits/stdc++.h>
using namespace std;
#define INF 1000000007
#define sf second.first
#define ss second.second
typedef pair<int,int> P;
typedef pair<int,P> iP;
int par[10000], leng[10000];
int find(int x){
	while(x != par[x]) x = par[x];
	return x;
}
int main(void){
	int v, e;
	cin >> v >> e;
	iP g[e];
	for(int i = 0; i < e; i++){
		int a, b, c;
		cin >> a >> b >> c;
		g[i] = iP(c, P(a, b));
	}
	sort(g, g + e);
	int ans = 0;
	for(int i = 0; i < v; i++) par[i] = i, leng[i] = 0;
	for(int i = 0; i < e; i++){
		iP d = g[i];
		if(find(d.sf) != find(d.ss)){
			ans += d.first;
			int x = find(d.sf), y = find(d.ss);
			if(leng[x] > leng[y]) par[y] = x;
			else if(leng[x] < leng[y]) par[x] = y;
			else par[y] = x, leng[x]++;
		}
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 4384
#include <iostream>
#include <cstdlib>
#include <vector>
#include <stack>
#include <string>
#include <climits>
#include <algorithm>
#include <functional>
#include <string.h>
#include <numeric>
#include <math.h>

#define LOOP(N) for(int i=0; i<(N); ++i)
#define REP(i, N) for(int i=0; i<(N); ++i)
#define FOR(i, start, end) for(int i=(start); i<(end); ++i)
#define ALL(a) (a).begin(),(a).end()

using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using Graph = vector< vector<int> >;

const ll MOD = 1000000007;

void sayYes() {cout << "Yes" << endl;}
void sayNo() {cout << "No" << endl;}


int main() {
    ll N, K; cin >> N >> K;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];
    
    ll unit_count = 0;
    REP(i, N) {
        FOR(j, i+1, N) {
            if (A[i] > A[j]) ++unit_count;
        }
    }
    
    vector<ll> A_sorted(A);
    sort(ALL(A_sorted));
    vector<ll> over_count(N, 0);
    REP(i, N) {
        over_count[i] = A_sorted.end() - upper_bound(ALL(A_sorted), A[i]);
        // cout << i << " " << over_count[i] << endl;
    }
    
    ll result = unit_count * K % MOD;
    REP(i, N) {
        result += K*(K-1LL)/2LL % MOD * over_count[i] % MOD;
        result %= MOD;
    }
    
    cout << result;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	s := IOInitialize()
	K := Int(s)
	if K%2 == 1 {
		fmt.Println((K/2 + 1) * (K / 2))
	} else {
		fmt.Println((K / 2) * (K / 2))
	}
}

func IOInitialize() *bufio.Scanner {
	s := bufio.NewScanner(os.Stdin)
	s.Split(bufio.ScanWords)
	return s
}

func Int(s *bufio.Scanner) int {
	if !s.Scan() {
		panic("scan error")
	}

	value, err := strconv.Atoi(s.Text())
	if err != nil {
		panic("text to int error")
	}
	return value
}

func String(s *bufio.Scanner) string {
	if !s.Scan() {
		panic("scan error")
	}

	return s.Text()
}

func scanNums(s *bufio.Scanner, len int) (nums []int) {
	for i := 0; i < len; i++ {
		num := Int(s)
		nums = append(nums, num)
	}
	return
}

func scanstrings(s *bufio.Scanner, len int) (strs []string) {
	for i := 0; i < len; i++ {
		str := String(s)
		strs = append(strs, str)
	}
	return
}


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

using namespace std;

typedef double db;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

typedef pair < db, db > pdd;
typedef pair < db, ld > pdl;
typedef pair < ld, db > pld;
typedef pair < ld, ld > ldp;

typedef pair < ll, ll > pll;
typedef pair < int, ll > pil;
typedef pair < ll, int > pli;
typedef pair < int, int > pii;

#define F first
#define S second

#define en end()
#define bg begin()

#define rev reverse
#define mp make_pair
#define pb push_back

#define y1 y1234567890
#define um unordered_map

#define all(x) x.bg, x.en
#define sz(x) (int)x.size()
#define len(x) (int)strlen(x)

#define sqr(x) ((x + 0ll) * (x))
#define sqrd(x) ((x + 0.0) * (x))

#define forn(i, n) for (int i = 1; i <= n; i++)

const ll inf = (ll)1e18;
const ll mod = (ll)1e9 + 7;

const db eps = (db)1e-9;
const db pi = acos(-1.0);

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

const int N = 105;

int n, mx, a[N], cnt[N];

int main() {
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	//freopen(".err", "w", stderr);

	//srand(time(NULL));

	//cin.tie(NULL);
	//cout.tie(NULL);
	//ios_base::sync_with_stdio(false);

	//cout << setprecision(10) << fixed;
	
	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		mx = max(mx, a[i]);
		cnt[a[i]]++;
	}

	for (int i = 1; i <= n; i++) {
		if (a[i] + a[i] < mx) {
			cout << "Impossible";
			return 0;
		}
	}

	if (!(mx & 1) && cnt[mx >> 1] != 1) {
		cout << "Impossible";
		return 0;
	}

	if ((mx & 1) && cnt[(mx + 1) >> 1] != 2) {
		cout << "Impossible";
		return 0;
	}

	for (int i = mx; i >= (mx >> 1) + 1; i--) {
		if (cnt[i] < 2) {
			cout << "Impossible";
			return 0;
		}
	}

	if (mx == 1 && n > 2) {
		cout << "Impossible";
		return 0;
	}

	cout << "Possible";

	//cerr << (clock() + 0.0) / CLOCKS_PER_SEC;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
using namespace std;
typedef long long int ll;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}


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


    ll ans = b;

    if(a<=12){
        ans /= 2;
    }
    if(a<=5)ans = 0;
    
    cout << ans << endl;
    return 0;
}
 
 


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

int c[51][51];
int w, h;
int dx[8] = { 0,1,1,1,0,-1,-1,-1 };
int dy[8] = { -1,-1,0,1,1,1,0,-1 };

void dfs(int i, int j) {
  if(i < 0 || i >= h || j < 0 || j >= w || c[i][j] == 0)
    return;

  c[i][j] = 0;
  for(int k=0;k<8;k++) {
    dfs(i+dy[k], j+dx[k]);
  }
  return;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  while(true) {
    cin >> w >> h;
    if(w == 0 && h == 0)
      break;
    for(int i=0;i<h;i++) {
      for(int j=0;j<w;j++) {
        cin >> c[i][j];
      }
    }

    ll ans = 0;
    for(int i=0;i<h;i++) {
      for(int j=0;j<w;j++) {
        if(c[i][j] == 1) {
          ans++;
          dfs(i, j);
        }
      }
    }
    cout << ans << endl;

  }
}



Measured memory_bytes: 3216
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;

int main() {
    int N, W, ww = 0;
    cin >> N >> W;
    vector<int> w(N+1, 0);
    for(int i=0;i<N;++i){
        cin >> w[i];
        ww += w[i];
    }
    sort(w.rbegin(), w.rend());

    vector<vector<ll>> dp(N+1, vector<ll>(W+1, 0));
    dp[0][0] = 1;
    ll ans = 0LL;
    if(W-ww == 0) ++ans;
    for(int i=0;i<N;++i) { // i は運ばない
        ww -= w[i];

        for(int j=0;j<=W;++j) {
            if(!dp[i][j]) continue;
            dp[i+1][j] += dp[i][j];
            dp[i+1][j] %= MOD;
            if(j+w[i] <= W) {
                dp[i+1][j+w[i]] += dp[i][j];
                dp[i+1][j+w[i]] %= MOD;
            }
        }
        
        for(int j=max(0, W-ww-w[i]+1);j<=W-ww;++j) {
            ans += dp[i][j];
            ans %= MOD;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 18644
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.Abc
{
    // https://atcoder.jp/contests/abc159/tasks/abc159_a
    public class QuestionA
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 整数配列の入力
            var inputIntArray = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();

            int result = 0;

            result += (inputIntArray[0] * (inputIntArray[0] - 1)) / 2;
            result += (inputIntArray[1] * (inputIntArray[1] - 1)) / 2;

            Console.WriteLine(result);

            Console.Out.Flush();
        }
    }
}


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

int main()
{
	char s[11], s1[12], s2[12];
	scanf("%s", s);
	scanf("%s", s1);
	strcpy(s2, s1);
	s2[strlen(s2) - 1] = '\0';

	if (!strcmp(s, s2) && (strlen(s) == strlen(s2)))
	{
		printf("Yes");
	}
	else {
		printf("No");
	}
	return 0;
}

Measured memory_bytes: 1732
#include<iostream>
#include<vector>
using namespace std;
int main() {
	int a;
	cin >> a;
	if (a < 1200)cout << "ABC" << endl;
	else {
		if (a < 2800)cout << "ARC" << endl;
		else cout << "AGC" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main():
	n, m = IN()
	if abs(n-m) > 1:
		return 0
		
	(n,m) = (n,m) if n<=m else (m,n)
	pn = 1
	for i in range(1,n+1):
		pn=pn*i%mod
	if n==m:
		pn = (pn * pn * 2) % mod
	else:
		pn = (pn * pn * m) % mod
	return pn
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Measured memory_bytes: 38384
#include <stdio.h>

int main(){
int n,a,b,c,d,f;

while(scanf("%d",&n)!=EOF){
f=0;
for(a=0;a<10;a++){
for(b=0;b<10;b++){
for(c=0;c<10;c++){
for(d=0;d<10;d++){
if(a+b+c+d==n)f++;
}
}
}
}
printf("%d\n",f);
}
return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rp(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

void solve(){
    string s;
    cin >> s;
    bool ok=false;
    if(s[0]==s[1]&&s[1]==s[2]) ok=true;
    if(s[1]==s[2]&&s[2]==s[3]) ok=true;
    Yes(ok);
    return;
}
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(30);
    solve();
    return 0;
}

Measured memory_bytes: 3596
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int count = 0;
        for (int i = a; i <= b; i++) {
            int keta1 = i / 10000;
            int keta2 = i / 1000 % 10;
            int keta4 = i / 10 % 10;
            int keta5 = i % 10;
            if (keta1 == keta5 && keta2 == keta4) count++;
        }

        System.out.println(count);
    }
}

Measured memory_bytes: 21204
#include <bits/stdc++.h>
#include <cstdlib>  // abs() for integer 絶対値求めやつ
#include <cmath>    // abs() for float, and fabs()
#include <algorithm>
#include <vector>
#include <string>
#include<iomanip>//浮動小数点数を出力する制度の指定
//使い方　数値をnumとして　cout<<setprecision(n)<<num ;nは桁数
#define rep(i,n) for(int i = 0; i < (n);i++)
#define SORT(a) sort((a).begin(),(a).end())
#define REV(a) reverse((a).begin(),(a).end())
using namespace std;
using ll =long long;
#define INF 2000000000
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; }
#define che(a,string) cout<<"//"<<string <<"=="<<(a)<<"//" <<endl;
bool IsInt(double a){int b = a/1;if(a==b){return true;}else {return false;}}
/*覚えてないことメaモ
数値型から文字列に変換　to_string(number);これは簡単
文字列から数値型に変換　stoi(number)
文字列からllに変換　stoll(number)*/

//ここから書き始める

int main(){
	string s;
	cin >> s;
	int k = s.size();
	if(k==2){
		cout<<s<<endl;
	}
	else{
		cout<<s.at(2)<<s.at(1)<<s.at(0)<<endl;
	}

}


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

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
// pll pp; -> (pp.first,pp.second)
// vector<vl> pp(n,vl(2)); sort(pp.begin(),pp.end(),[](vl a,vl b){return a[0]<b[0];});

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define RREP(i,n) for(ll (i)=(n)-1;(i)>=0;(i)--)
#define FOR(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
#define FORR(i,a,b) for(ll (i)=(b)-1;(i)>=(a);(i)--)
#define DEBUG(x) cout << #x << ": " << x << endl
#define CHMAX(a,b) a=max((a),(b))
#define CHMIN(a,b) a=min((a),(b))
/*}}}*/
int main() {
  ll N,ans,check,c,k,j,cou,tf,ts,tt,tfc,tsc,ttc,si;
  vl a;
  cin >> N;
  REP(i,N){
		int x;
		cin >> x;
		a.push_back(x);
	}
  if(N%3 == 0){
    check = 0;
    REP(i,N){
      if(a[i] == 0){
        check = check + 1;
      }
    }
    if(check == 0){
      tf = a[0];
      ts = -1;
      tt = -1;
      REP(i,N){
        if(a[i] != tf){
          ts = a[i];
        }
        if(ts != -1)break;
      }
      REP(i,N){
        if(a[i] != ts && a[i] != tf){
          tt = a[i];
        }
        if(tt != -1)break;
      }
      tfc = 0;
      tsc = 0;
      ttc = 0;
      k = 0;
      REP(i,N){
        if(a[i] == tf){
          tfc = tfc + 1;
        };
        if(a[i] == ts){
          tsc = tsc + 1;
        };
        if(a[i] == tt){
          ttc = ttc + 1;
        };
      }
      if(ttc*3==N && tsc*3 == N && tfc*3 == N){
        si = tf^ts;
        if(si == tt){
          cout << "Yes" << endl;
        }else{
          cout << "No" << endl;
        }
      }else{
        cout << "No" << endl;
      }
    }else{
      if(check ==N){
        cout << "Yes" << endl;
      }else{
        if(check*3==N){
          c = 2;
          j=0;
          while(c>1){
            if(a[j] != 0){
              k= a[j];
              c = 0;
            }
            j=j+1;
          }
          cou = 0;
          REP(i,N){
            if(a[i] ==0 || a[i] == k){
              cou = cou + 1;
            }
          }
          if(cou == N){
            cout << "Yes" << endl;
          }else{
            cout << "No" << endl;
          }
        }else{
          cout << "No" << endl;
        }
      }
    }
  }else{
    check = 0;
    REP(i,N){
      if(a[i] != 0){
        check = 1;
      }
    }
    if(check == 1){
      cout << "No" <<endl;
    }else{
      cout << "Yes" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1400
N,M = map(int,input().split())
li = list(map(int,input().split()))
goukei=sum(li)
MM=goukei/(4*M)
count=0
for i in li:
  if i>=MM:
    count+=1
  else:
    pass
if count>=M:
  print("Yes")
else:
  print("No")

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

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

Measured memory_bytes: 3680
N = int(input())
a = list(map(int, input().split()))

# XOR演算子　^
# aの要素全てのXORを計算、それをSとする
S = 0
for aa in a:
    S ^= aa

# i番目の番号はaiとSのXORで表される
ans = []
for ai in a:
    ans.append(S ^ ai)

print(*ans)

Measured memory_bytes: 31632
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 100000;

int n, num, head[N + 50], deep[N + 50], rot1, rot2, f[N + 50], on[N + 50], ans1[N + 50], ans2[N + 50], cnt, nxt[N + 50], ctt, son[N + 50];

struct Node
{
    int next, to;
} edge[N * 2 + 50];

void Addedge(int u, int v)
{
    edge[++num] = (Node){head[u], v};
    head[u] = num;
    return;
}

int Dfs(int x, int fa)
{
    int maxx = 0, bh = x;
    deep[x] = deep[fa] + 1; f[x] = fa;
    for (int i = head[x]; i; i = edge[i].next)
    {
        int v = edge[i].to;
        if (v == fa) continue;
        int tmp = Dfs(v, x); 
        if (deep[tmp] > maxx) maxx = deep[tmp], bh = tmp, nxt[x] = v;
    }
    return bh;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1, u, v; i <= n - 1; i++)
    {
        scanf("%d%d", &u, &v);
        Addedge(u, v); Addedge(v, u);
    }
    rot1 = Dfs(1, 0);
    for (int i = 1; i <= n; i++) deep[i] = 0, f[i] = 0, nxt[i] = 0;
    rot2 = Dfs(rot1, 0);
    int tmp = rot1;
    while (tmp) on[tmp] = 1, tmp = nxt[tmp];
    for (int i = 1; i <= n; i++)
    {
        if (on[i]) continue;
        int flag = 0;
        for (int j = head[i]; j; j = edge[j].next)	
        {
            int v = edge[j].to;
            if (on[v]) { son[v]++; flag = 1; break; } 
        }
        if (!flag) { puts("-1"); return 0; }
    }
    for(int i = rot2; i; i = f[i])
    {
        ans1[ctt + son[i] + 1] = ++cnt;
        for (int j = 1; j <= son[i]; j++) ans1[++ctt] = ++cnt;
        ctt++;
    }
    ctt = cnt = 0;
    for (int i = rot1; i; i = nxt[i])
    {
    	ans2[ctt + son[i] + 1] = ++cnt;
    	for (int j = 1; j <= son[i]; j++) ans2[++ctt] = ++cnt;
    	ctt++;
	}
	for (int i = 1; i <= ctt; i++)
		if (ans1[i] != ans2[i])
		{
			if (ans1[i] < ans2[i]) for (int i = 1; i <= n; i++) printf("%d ", ans1[i]);
			else for (int i = 1; i <= n; i++) printf("%d ", ans2[i]);
			return 0;
		}
	for (int i = 1; i <= n; i++) printf("%d ", ans1[i]);
    return 0; 
}

Measured memory_bytes: 11776
#include <iostream>
using namespace std;
 
int main() {
    int x , y , r;
    cin >> x >> y;
    if(x < y){
        int a = y;
        y = x;
        x = a;
    }
    do{
        r = x % y;
        x = y;
        y = r;
    }while(r != 0);
    cout << x << endl;
    return 0;
}


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

int main(){
    int n, d1[110], d2[110];
    cin >> n;
    rep(i,n){
        cin >> d1[i] >> d2[i];
    }
    int temp = 0;
    bool can = false;
    rep(i,n){
        if(d1[i] == d2[i]){
            temp++;
        }else{
            temp = 0;
        }
        if(temp >= 3){
            can = true;
            break;
        }
    }
    if(can){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 3636
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll a, b, c;
    cin >> a >> b >> c;
    
    ll d = c - a - b;
    if(d>0 && d*d > 4*a*b) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
N = gets.to_i
a1s = gets.split.map(&:to_i)
a2s = gets.split.map(&:to_i)

ans = 0
(0..N-1).each do |i|
  ans = [ans, a1s[0..i].inject(:+) + a2s[(i)..N-1].inject(:+)].max
end
puts ans

Measured memory_bytes: 1788
ma = lambda :map(int,input().split())
n,m = ma()
tr = [[] for i in range(n)]
for i in range(m):
    a,b = ma()
    tr[a-1].append(b-1)
    tr[b-1].append(a-1)
f = False
for i in tr[0]:
    for s in tr[i]:
        if s==n-1:
            f =True
print("POSSIBLE") if f else print("IMPOSSIBLE")


Measured memory_bytes: 38320
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<double,int> DIP;
typedef pair<DIP,P> PP;
const ll MOD = 1000000007;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX_N = int(2e5 + 5);
const double EPS = 1e-11;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define ALL(v) (v).begin(), (v).end()

int main() {
    ll n, k, a[MAX_N], b[MAX_N], mask, ans = 0;
    cin >> n >> k;
    REP(i,n) cin >> a[i] >> b[i];
    REP(i,31){
        if(i>0){
            if(((k>>i)&1)==0)continue;
            else mask = ((k-(1LL<<i))|((1LL<<i)-1));
        }
        else mask = k;
        ll sum = 0;
        REP(j,n){
            if((a[j]|mask)<=mask)sum+=b[j];
        }
        ans = max(ans, sum);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3072
#include<iostream>
#include<vector>
#include <cmath>

using namespace std;


int main() {
	int n, m;
	int s, c;

	cin >> n >> m;
	vector<int> checker(n);
	for (int i = 0; i < n; i++) checker[i] = -1;

	for (int i = 0; i < m; i++) {
		cin >> s >> c;

		if (checker[s - 1] == -1) {
			checker[s - 1] = c;
		}
		else if (checker[s-1] != c) {
			cout << "-1" << endl;
			return 0;
		}
		else {

		}
	}

	if (n != 1) {
		if (checker[0] == 0) {
			cout << "-1" << endl;
			return 0;
		}
		if (checker[0] == -1) {
			checker[0] = 1;
		}
	}

	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (checker[i] == -1) checker[i] = 0;
		ans += checker[i] * pow(10, n - i - 1);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
from collections import deque

N = int(input())
*A, = map(int, input().split())
B = deque([])
for i, a in enumerate(A):
    if i % 2 == 0:
        B.append(a)
    else:
        B.appendleft(a)
if N % 2 == 1:
    B.reverse()
print(*B)

Measured memory_bytes: 25416
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=6010,P=998244353;
int n,s,a[MAXN],dp[MAXN],np[MAXN];
ll ans;
int main () {
	scanf("%d%d",&n,&s);
	for (int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		for (int j=s;j>=1;j--) {
			dp[j+a[i]]=(dp[j+a[i]]+dp[j])%P;
		}
		dp[a[i]]=(dp[a[i]]+i)%P;
		np[i]=dp[s];
		ans=(ans+(1ll*((np[i]-np[i-1]+P)%P)*(n-i+1)))%P;
	}
	printf("%lld\n",ans);
	return 0;
}

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

#define endl '\n'

const int max_n = 2e5 + 5;

int n, co;
int seen[max_n];
int a[max_n], b[max_n];
int A[max_n], B[max_n];
int L[max_n], R[max_n];

int r() {
	int x = (rand()%1000)*1000 + rand()%1000;
	return x%n;
}

bool FindMatch(int i) {
	for(int j = 0; j < 2000; j++) {
		int foo = r();
		if(a[i] != b[foo] && seen[foo] != co) {
			seen[foo] = co;
			if(R[foo] < 0 || FindMatch(R[foo])) {
				L[i] = foo;
				R[foo] = i;
				return true;
			}
		}
	}
	return false;
}

int BipartiteMatching() {
	memset(L, -1, sizeof L);
	memset(R, -1, sizeof R);
	for(int i=0; i<n; i++) {
		if(a[i] != b[i]) {
			L[i] = R[i] = i;
		}
	}
	for(int i = 0; i < n; i++) {
		if(L[i] == -1) {
			co = i + n;
			if(!FindMatch(i)) return 0;
		}
	}
	return 1;
}

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

	srand(time(NULL));

	cin >> n;
	for(int i=0; i<n; i++) {
		cin >> a[i];
		A[a[i]]++;
	}
	for(int i=0; i<n; i++) {
		cin >> b[i];
		B[b[i]]++;
	}

	for(int i=1; i<max_n; i++) {
		if(B[i] > n - A[i]) {
			cout << "No" << endl;
			return 0;
		}
	}

	reverse(b, b+n);
	if(BipartiteMatching()) {
		cout << "Yes" << endl;
		for(int i=0; i<n; i++) {
			cout << b[L[i]] << " ";
		}
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 23436
while tmp = gets
  n = tmp.chomp.to_i
  count = 0
  for a in 0..9
    for b in 0..9
      for c in 0..9
        for d in 0..9
          if a + b + c + d == n
            count += 1

          end
        end
      end
    end
  end
  puts count
end



Measured memory_bytes: 6864
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const string ln = "\n";
constexpr int INF = 1001001001;
constexpr int MOD = 1000000007;

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

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

  ll total = 0;
  for (int i = 0; i < n; i++) {
    total ^= a[i];
  }

  cout << (total == 0 ? "Yes" : "No") << ln;

  return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<tuple>
#include<utility>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<iomanip>
#include<map>
using namespace std;
using ll=long long int;
typedef pair<int, int> P;
const int INF = 1e9 + 7;
int dx[8] = { 1,0,-1,0,1,1,-1,-1 };
int dy[8] = { 0,1,0,-1,1,-1,1,-1 };




int main() {

	int h, w;
	cin >> h >> w;

	char map[55][55];
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {

			if (map[i][j] == '#') {
				continue;
			}

			int ans = 0;
			for (int k = 0; k < 8; k++) {
				int ny = i + dy[k];
				int nx = j + dx[k];

				if (0 <= ny && ny < h && 0 <= nx && nx < w && map[ny][nx] == '#') {
					ans++;
				}
			}

			map[i][j] = ans + '0';

		}
	}


	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cout << map[i][j];
		}
		cout << endl;
	}

}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	int i, n, m;
	int answer = -1e9;
	int input[200000];

	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		scanf("%d", &input[i]);
	}

	m = input[0];

	for (i = 1; i < n; i++) {

		if (answer < (input[i] - m)) {
			answer = input[i] - m;
		}

		if (input[i] < m) {
			m = input[i];
		}

	}

	printf("%d\n", answer);

	return 0;
}

Measured memory_bytes: 1376
/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using Pair = pair<int32_t, int32_t>;

// std::cout << std::setprecision(20) << 1.1 << endl;

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

  int32_t R, G, B, N;
  cin >> R >> G >> B >> N;
  int32_t count = 0;
  for (int32_t r = 0; r <= N / R; ++r) {
    for (int32_t g = 0; g <= N / G; ++g) {
      const int32_t b = (N - r * R - g * G) / B;
      if (b >= 0 && r * R + g * G + b * B == N) {
        ++count;
      }
    }
  }
  cout << count << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#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 all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define show(x) true
#endif

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);
	
	int N;
	cin >> N;
	int o = 0;
	rep(i,N){
		int x;
		cin >> x;
		if(i != x-1) o++;
	}
	if(o <= 2) cout << "YES" << endl;
	else cout << "NO" << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    int ans = max({a+b, a-b, a*b});
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3572
n = int(input())
m = int(input())
for _ in range(m):
	a, b = map(int, input().split())
	c = (n+1)/2
	tmp = c-max(abs(c-a), abs(c-b))
	if tmp%3==0:
		r = 3
	elif tmp%3==1:
		r = 1
	else:
		r = 2
	print(r)



Measured memory_bytes: 5624
#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <functional>
#include <string>
#include <cstring>
#include <sstream>
#include <deque>
#define fir first
#define sec second
using namespace std;

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

const int inf1=1e9+9;
const ll inf2=8e18+9;
const ll mol=1e9+7;
const int maxn=2e5+9;
const ll maxx=1e5+9;

int n,ar[maxn];
int num=0;

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&ar[i]),num^=ar[i];
    for(int i=0;i<n;i++) printf("%d ",num^ar[i]);
    printf("\n");
}


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

int main(){
    long N,K,Q;
    cin >> N >> K >> Q;
    vector<long> A(Q);
    vector<long> B(N,0);
    vector<long> C(N,K);
    for(int i=0;i<Q;++i) cin >> A[i];
    for(int i=0;i<Q;++i) ++B[A[i]-1];
    for(int i=0;i<N;++i) {
        if(C[i]-Q+B[i]>0) cout << "Yes" << endl;
        else cout << "No" << endl;   
    }
}


Measured memory_bytes: 2944
#include <bits/stdc++.h>
#include <cassert>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ok() puts(ok?"Yes":"No");
template<class T> bool chmax(T &a, const T &b) { if(a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if(a > b) { a = b; return true; } return false; }
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<int, int>;
using vvi = vector<vi>;
using vii = vector<ii>;
using gt = greater<int>;
using minq = priority_queue<int, vector<int>, gt>;
using P = pair<ll,ll>;
const ll LINF = 1e18L + 1;
const int INF = 1e9 + 1;
//clang++ -std=c++11 -stdlib=libc++ 

int n,x,t;
int main() {
  cin >>n >> x >>t;
  cout <<  ((n-1)/x + 1) * t << endl;
  return 0;
}

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

// int/long:		-2,147,483,648 - 2,147,483,648 (-2^31 <= int < 2^31)
// long/long long:	-9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

#define	INF (1<<29)
//536,870,912

// lower_bound(A.begin(), A.end(), N)
// upper_bound(...

// A.erase(unique(A.begin(), A.end()), A.end())

// bit: &/and, |/or, ^/xor, ~/not

// getline(cin, String)

// Graph
// Warshall-Floyd: Distance between each node, N^3
// Dijkstra: Distance from the start node, N^2
// DFS(Depth-First Search)

#define	MOD 1000000007

int	main() {
	int N;
	cin >>N;
	vector<vector<int>> A;
	for (int i=0; i<N; i++) {
		int AA;
		cin >>AA;
		A.push_back({AA, i});
	}
	sort(A.begin(), A.end());
	int S=0;
	for (int i=0; i<N; i+=2)
		if (1==A.at(i).at(1)%2)
			S++;
	cout <<S <<endl;
	return 0;
}



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

#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'

// n回繰り返し
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順
#define rep1(i,n) for(int i = 1; i <= ((int)(n)); i++) // 1-indexed昇順
#define rrep(i,n) for(int i = ((int)(n)-1); i >= 0; i--)  // 0-indexed降順
#define rrep1(i,n) for(int i = ((int)(n)); i >= 1; i--)   // 1-indexed降順
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vii;  // 2次元配列
typedef vector<ll> vll;
typedef pair<int, int> PII;

template<typename T>
using vec = vector<T>;
template<class T>
using maxheap = std::priority_queue<T>;
template<class T>
using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template<class T,class U> inline bool chmax(T &a, const U &b){if(a<b){a=b;return 1;}return 0;}
template<class T,class U> inline bool chmin(T &a, const U &b){if(a>b){a=b;return 1;}return 0;}

const ld Pi = std::acos(-1.0L);
const ll infll = (1LL<<62)-1;
const int inf = (1<<30)-1;
const int mod = 1000000007;
// const int mod = 998244353;

int dp[1005][1005];
/*FUNCs=================================================*/


/*MAIN==================================================*/
signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);   //cin cout 高速化
    cout << fixed << setprecision(15);

    int h,w; cin >> h >> w;
    vec<string> grid(h); rep(i,h) cin >> grid[i];
    dp[0][0] = 1;
    for(int i = 0; i < h; ++i)  {
        for(int j = 0; j < w; ++j) {
            if(j+1<w && grid[i][j+1]!='#') {
                dp[i][j+1] += dp[i][j];
                dp[i][j+1] %= mod;
            }
            if(i+1<h && grid[i+1][j]!='#') {
                dp[i+1][j] += dp[i][j];
                dp[i+1][j] %= mod;
            }
        }
    }
    cout << dp[h-1][w-1] << '\n';
}

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

int main() {
  int a;
  int b;
  int c;
  cin >> a >> b >> c;
  
  if (a==b) {
    if (a==c) {
      cout << "No" << endl;
    }
    else {
      cout << "Yes" << endl;
    }
  }
  else if (a==c) {
    cout << "Yes" << endl;
  }
  else if (b==c) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
int main()
{
    int N, M;
    cin >> N >> M;
    vector<bool> res(N, false);
    vector<int> wa(N, 0);

    int AC = 0, WA = 0;
    rep(i, M) {
        int p;
        string S;
        cin >> p >> S;
        bool flag = false;
        if (S == "AC") flag = true;

        if (!res[p - 1]) {
            if (flag) {
                res[p - 1] = true;
                AC++;
                WA += wa[p - 1];
            }
            else {
                wa[p - 1]++;
            }
        }
    }

    cout << AC << " " << WA << endl;
    return 0;
}

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

#define ll long long
#define ld long double
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long

using namespace std;
const int INF = 2e16;
const int MB = 20;
const int MOD = 2019;

void solve() {
	string s;
	cin >> s;
	cout << (s == "ABC" ? "ARC" : "ABC");
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout << fixed;
	cout.precision(12);
	//srand(time(0));
	int t = 1;
	//int t;
	//cin >> t;
	while (t--) solve();
}

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

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	string str;
	cin >> str;
	for(int i=0;i<3;i++) cout << str[i];
	cout << "\n";
	return 0;
}

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


int a;
int b;
string s;
int main() {
	cin >> a >> b;
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		if (isdigit(s[i]) && i != a)continue;
		if (i == a&&s[i] == '-')continue;
		puts("No");
		return 0;
	}
	puts("Yes");
	return 0;
}

Measured memory_bytes: 256
import numpy as np

n=int(input())
ps=list(map(float,input().split()))
lim=(n+1)//2
dp=np.zeros(lim+1,dtype=np.float64)
dp[0]=1
for p in ps:
    dp[lim]=dp[lim]+dp[lim-1]*p
    dp[1:lim]=dp[:lim-1]*p+dp[1:lim]*(1-p)
    dp[0]=dp[0]*(1-p)
print(dp[-1])

Measured memory_bytes: 14544
GC.disable

DICT = {
  'C' => 0, 'C#' => 1, 'D' => 2, 'D#' => 3, 'E' => 4, 'F' => 5,
  'F#' => 6, 'G' => 7, 'G#' => 8, 'A' => 9, 'A#' => 10, 'B' => 11,
}

def check(stairs, music, k)
  music.size.downto(1) do |i|
    return false unless 1 <= k && k <= stairs.size && k <= i * 2
    tone = music[i - 1]
    stair = stairs[k - 1]
    case (tone - stair) % 12
    when 1
      k -= 2
    when 0
      k -= 1
    when 11
      k += 1
    else
      return false
    end
  end
  k == 0
end

def work(stairs, music)
  check(stairs, music, stairs.size - 1) || check(stairs, music, stairs.size)
end

s = STDIN.gets.to_i
s.times do
  STDIN.gets
  stairs = STDIN.gets.split.map!{|x| DICT[x]}
  music = STDIN.gets.split.map!{|x| DICT[x]}
  puts work(stairs, music) ? 'Yes' : 'No'
end

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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll cnt=0;
	string s,a="";
	cin>>s;
	a=s.substr(0,1);
	for(ll i=0;i<s.length();i++){
		if(s.substr(i,1)!=a){
			cnt++;
			a=s.substr(i,1);
		}
	}
	cout<<cnt<<endl;
	return 0;
}


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

#define fio ios_base::sync_with_stdio(false); cin.tie(NULL);

typedef long long int lli;

int main()
{
	fio;
	int a[3];
	cin>>a[0]>>a[1]>>a[2];
	sort(a,a+3);
	cout<<abs(a[1]-a[0])+abs(a[2]-a[1])<<endl;
	cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s\n";
	return 0;
}

Measured memory_bytes: 256
n=gets.chomp.to_i
w_arr=gets.chomp.split(" ").map(&:to_i)

min = 100000000

(0..(n-1)).each do |t|
  abs = w_arr[0..t].inject(&:+).to_i - w_arr[(t+1)..-1].inject(&:+).to_i
  abs *= -1 if abs < 0
  min = abs if abs < min
end

puts min


Measured memory_bytes: 1788
import java.util.Scanner;

public class Main {
	//java11

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		String s = sc.next();
		String t = sc.next();

		if(s.equals(t.substring(0, s.length())) && s.length()+1 == t.length())
			System.out.println("Yes");
		else
			System.out.println("No");

	}

}


Measured memory_bytes: 35716
import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def num_divisors_table(n):
    table = [0] * (n + 1)
    
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1
    
    return table


def main():
    N = NI()
    print(sum(num_divisors_table(N-1)))

if __name__ == '__main__':
    main()

Measured memory_bytes: 17012
N = int(input())
s = []
for i in range(N):
    s.append(input())
A = 0
B = 0
BA = 0
inAB = 0
for i in range(N):
    if s[i][-1] == "A" and s[i][0] == "B":
        BA += 1
    elif s[i][-1] == "A":
        A += 1
    elif s[i][0] == "B":
        B += 1
    inAB += s[i].count("AB")

if A == B and A == 0 and BA != 0: BA -= 1
print(min(A+BA,B+BA)+inAB)

Measured memory_bytes: 3700
s,c = list(map(int, input().split()))
# 今あるSで出来る限りSCCを作る
# 余ったC（4個消費）でできる限りSCCを作る

ans = 0
if c >= 2*s:
    # Cの在庫に余力がある
    ans += s
    c -= 2*s
else:
    ans += c//2
    c = 0

ans += c//4

print(ans)

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

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

    int a,b;

    cin >> a;
    cin >> b;

    for(int i=1;i<=3;i++)
    {
    	if(a!=i && b!=i)
    	{
    		cout << i << '\n';
    		break;
    	}
    }
    return 0;
}

Measured memory_bytes: 256
S = input()
s1 = S[:2]
s2 = S[2:]

judge = [0]*4

if int(s1)<=12 and int(s1)>=1:
  if int(s2)<=12 and int(s2)>=1:
    print("AMBIGUOUS")
  else:
    print("MMYY")
else:
  if int(s2)<=12 and int(s2)>=1:
    print("YYMM")
  else:
    print("NA")

Measured memory_bytes: 3060
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools
from collections import Counter

def main():
    n = int(input())
    l = list(map(int, input().split()))
    l = Counter(l)
    if all(i == 1 for i in l.values()):
        print("YES")
    else:
        print("NO")


if __name__=="__main__":
    main()


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

using namespace std;

using i64 = int64_t;

const i64 MOD = 1e9+7;

const i64 INF = 1e18+7;


signed main(){
    int a, b, c, d, n, x, y;
    string s, t;


    auto Yes = [&](bool t){
        cout << (t ? "Yes" : "No") << endl;
    };
    auto YES = [&](bool t){
        cout << (t ? "YES" : "NO") << endl;
    };
    auto tri = [&](bool t, string a, string b){
        cout << (t ? a : b) << endl;
    };

    cin >> s;
    if(s.size() == 3)
        reverse(s.begin(), s.end());
    cout << s << endl;
}


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

long long n, m, a[100009], p[200009], v;

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) { cin >> a[i]; if (i >= 2) { v += (a[i] - a[i - 1] + m) % m; } }
	for (int i = 1; i <= n - 1; i++) {
		if ((a[i + 1] - a[i] + m) % m <= 1) continue;
		int L = a[i] + 2, R = a[i + 1] + 1; if (L > R) R += m;
		p[L]++; p[R] -= (R - L + 1); p[R + 1] += (R - L);
	}
	for (int i = 1; i <= 2 * m; i++) p[i] += p[i - 1];
	for (int i = 1; i <= 2 * m; i++) p[i] += p[i - 1];
	
	long long maxn = 0;
	for (int i = 1; i <= m; i++) maxn = max(maxn, p[i] + p[i + m]);
	cout << v - maxn << endl;
	return 0;
}

Measured memory_bytes: 2688
/*
author: shah_entrance
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    double n,k;
    cin>>n>>k;
    if(ceil(n/2)>=k)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = Integer.parseInt(sc.next());
		int b = Integer.parseInt(sc.next());
		int k = Integer.parseInt(sc.next());


		for (int i=a; i<=b; i++){
			if (i<a+k || i+k>b){
				System.out.println(i);
			}
		}
	}
}

Measured memory_bytes: 21844
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

#define rep(i, a, b) for(auto (i)=a;i<b;i++)
#define list(i, N) for(auto (i)=0;i<N;i++)

typedef long long ll;
typedef vector <ll> vi;
typedef pair <ll, ll> pi;
#define mp make_pair
#define pb push_back
#define eb emplace_back

#define int ll
#define INF 1e18+5
#define mod 1000000007

template<class T>
T max(T a, T b, T c) {
    return max(a, max(b, c));
}

int32_t main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n; cin >> n;
    string s; cin >> s;

    vi r, g, b;
    list(i,n){
        if(s[i]=='R') r.eb(i);
        else if(s[i]=='G') g.eb(i);
        else b.eb(i);
    }

    int ans = ((int)r.size()) * ((int)g.size()) * ((int)b.size());

    //find the number of triples in AP??
    int toRemove = 0;
    list(i,n){
        rep(j,i+1,n){
            if(s[i]==s[j]) continue;
            int diff = j-i;
            //now find the k with such difference
            int k = j+diff;
            if(k<n && s[k]!=s[i] && s[k]!=s[j]) toRemove++;
        }
    }

    ans -= toRemove;

    cout << ans << '\n';

    return 0;
}

Measured memory_bytes: 3712
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>


#define fs first
#define sc second

using namespace std;


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


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

    string s;
    cin >> s;

    int remain = 0;
    int res = 0;
    for(int i = 0; i < s.length()-1; i++){
        if(s[i] == s[i+1]){
            res++;
        }
        else{
            remain++;
        }
    }
    remain++;

    while(K > 0) {
        K--;
        if(remain == 1){
            break;
        }
        else if(remain == 2){
            res++;
            remain--;
        }
        else{
            remain -= 2;
            res += 2;
        }
    }

    cout << res << endl;



    return 0;
}


Measured memory_bytes: 512
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(isr);
		String buf = br.readLine();
		String[] input = buf.split(" ");
		int a = Integer.parseInt(input[0]);
		int b = Integer.parseInt(input[1]);
		int c = Integer.parseInt(input[2]);

		String result = new String();
		if(a < b && b < c){
			result = "Yes";
		}else{
			result = "No";
		}
		System.out.println(result);
	}
}

Measured memory_bytes: 24464