akhauriyash/Code-Regression huggingface dataset:
// #pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define N 1000000007
#define N2 998244353
#define Nmax 1000009
#define INF (ll)1e18
#define pll pair<ll,ll>
#define mp make_pair
#define fi first
#define se second
#define vv vector
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(ll i=m;i<(n);i++)
#define repr(i,n) repr2(i,n,0)
#define repr2(i,m,n) for(ll i=m;i>=(n);i--)
#define get(n) ll (n); scanf("%lld",&(n));
#define get2(n,k) ll (n),(k); scanf("%lld%lld",&(n),&(k));
#define get3(n,m,k) ll (n),(m),(k); scanf("%lld%lld%lld",&(n),&(m),&(k));
#define gets(s) string (s); cin >> (s);
#define ALL(c) (c).begin(),(c).end()
#define fill_nums(A,n) vector<ll> A((n)); for(ll i=0;i<n;i++) scanf("%lld",&A[i]);
#define fill_edges(adj,m) for(ll i=0;i<m;i++) {ll a, b; scanf("%lld %lld",&a,&b); adj[a-1].pb(b-1); adj[b-1].pb(a-1);}
#define fill_direct(adj,m) for(ll i=0;i<m;i++) {ll a, b; scanf("%lld %lld",&a,&b); adj[a-1].pb(b-1);}
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); //cout.tie(0);
#define pi 3.1415926535897
#define db double
#define noop
#define flu fflush(stdout)
#define imp {cout<<"No\n"; return 0;}
#define debug_vec(vec,n) {rep(idxi,n) cout<<vec[idxi]<<" "; cout<<"\n";}
#define debug_pvec(vec,n) {rep(idxi,n) cout<<vec[idxi].fi<<"-"<<vec[idxi].se<<"  "; cout<<"\n";}
#define debug_set(seta) {cout<<seta.size()<<"\n"; for(auto idxi:seta) cout<<idxi<<" "; cout<<"\n";}
#define debug_map(mappa) {cout<<mappa.size()<<"\n";for(auto idxi:mappa) cout<<idxi.fi<<"-"<<idxi.se<<"  "; cout<<"\n";}
#define debug_vecvec(vec,n) {rep(idxi,n) {for(auto idxi2:vec[idxi]) cout<<idxi2<<" "; cout<<"\n";}}
 
// LOOK AT THESE BEFORE SUBMISSION
// LOOK AT THESE BEFORE SUBMISSION
// ============================================================
// Nmax value and is index access offset taking it beyond Nmax.
// Precision error in case of real numbers.
// N vs N2 chosen correctly.
// Modulo applied everywhere.
// Flush in case of interactive.
// Don't erase value in multiset.
// Check for array indices out of bound (in pre or suff sums).
// Correct return value for functions.
// Confirm the letter case of yes and no.
// ============================================================

int main() {
        
    get2(H,n);
    ll sum = 0;
    rep(i,n) {
        get(a);
        sum += a;
    }

    if(sum<H) imp;
    printf("Yes\n");

    return 0;  
}   

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

using namespace std;
#define inputInt(a) int a; cin >> a; 
#define inputInt2(a,b) int a; int b; cin >> a >> b; 
#define inputInt3(a,b,c) int a; int b; int c; cin >> a >> b >> c;
#define inputLong(a) long a;cin >> a; 
#define inputIntArray(a,N) int a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputLongArray(a,N) long a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputIntArray2(a,b,N) int a[N]; int b[N]; for(int i=0;i<N;i++){cin >> a[i] >> b[i];}
#define output(answer) cout << answer << endl;
#define fN(i,N)    for(int i=0; i<N; i++)
#define fSE(i,s,e) for(int i=s; i<=e; i++)
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const ll MOD2 = 998244353;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

void solve(){
  string S; ll K; cin >> S >> K;
  
  for(ll i=0; i<min((ll)S.length(),K); i++){
    if(S[i] != '1'){ cout << S[i] << endl; return; } 
  }
  cout << '1' << endl; return;
}

int main()
{
  //input
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  
  //main
  
  
  // output
  solve();

  return 0;
}

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

map<ll,ll>f;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,s=0;
    cin>>n;
    ll l1[n+1];
    for(int i=1;i<=n;i++){
        cin>>l1[i];
        s^=l1[i];
    }
    for(int i=1;i<=n;i++){
        cout<<(s^l1[i])<<" ";
    }
}


Measured memory_bytes: 5172
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int t[] = new int[n];
        int x[] = new int[n];
        int y[] = new int[n];
        for (int i = 0; i < n; i++) {
            t[i] = in.nextInt();
            x[i] = in.nextInt();
            y[i] = in.nextInt();
        }

        int ct = 0, cx = 0, cy = 0;
        for (int i = 0; i < n; i++) {
            int time = t[i] - ct;
            int diffX = Math.abs(x[i] - cx);
            int diffY = Math.abs(y[i] - cy);

            if (diffX + diffY > time) {
                System.out.println("No");
                return;
            }

            if (time % 2 != (diffX + diffY) % 2) {
                System.out.println("No");
                return;
            }

            ct = t[i];
            cx = x[i];
            cy = y[i];
        }

        System.out.println("Yes");
    }
}

Measured memory_bytes: 60876
#include <iostream>
#include <cstdint>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpii;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<ll>> vvll;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rrep(i, n) for (ll i = 1; i <= (n); ++i)
#define irep(it, stl) for (auto it = stl.begin(); it != stl.end(); it++)
#define drep(i, n) for (ll i = (n)-1; i >= 0; --i)
#define mes(a) cout << (a) << endl
#define dmes(a, b) cout << (a) << " " << (b) << endl
#define re0 return 0
#define mp(p, q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define rSort(a) sort(a.rbegin(), a.rend())
#define Rev(a) reverse(a.begin(), a.end())
#define MATHPI acos(-1)
#define itn int
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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;
}
struct io
{
    io()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
};
const int INF = INT_MAX;
const ll LLINF = 1LL << 60;
const ll MOD = 1000000007;
const double EPS = 1e-19;



template<typename T>
vector<T> smallest_prime_factors(T n) {

    vector<T> spf(n + 1);
    for (int i = 0; i <= n; i++) spf[i] = i;


    for (T i = 2; i * i <= n; i++) {

        // 素数だったら
        if (spf[i] == i) {

            for (T j = i * i; j <= n; j += i) {

                // iを持つ整数かつまだ素数が決まっていないなら
                if (spf[j] == j) {
                    spf[j] = i;
                }
            }
        }
    }

    return spf;
}

template<typename T>
vector<T> factolization(T x, vector<T> &spf) {
    vector<T> ret;
    while (x != 1) {
        ret.push_back(spf[x]);
        x /= spf[x];
    }
    sort(ret.begin(), ret.end());
    return ret;
}



ll gcd(ll a, ll b) {
    return b ? gcd(b, a%b) : a;
}

signed main() {
    ll a, b;
    cin >> a >> b;
    mes(ceil((double)(a+b)/2));
    

    
    
    
    
    
    
    
    
}

Measured memory_bytes: 3740
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <numeric>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

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

    cout << a * b << endl;
}


Measured memory_bytes: 3632
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;

int main(){

  int x,y;
  int a[100][100];
  int w[100][100];

  while(true){
    cin >> x >> y;
    if(!x && !y) break;

    memset(w,0,sizeof(w));
    int ans = 0;

    for(int i=0;i<y;i++){
      for(int j=0;j<x;j++) cin >> a[i][j];
    }

    for(int i=0;i<x;i++){
      if(a[0][i] == 0) w[0][i] = 1;
    }

    for(int i=1;i<y;i++){
      for(int j=0;j<x;j++){

	if(i-2 >= 0 && a[i-2][j] == 2) w[i][j] += w[i-2][j];

	if(j-1 >= 0 && !a[i-1][j-1] && !a[i][j]) w[i][j] += w[i-1][j-1];
	if(j+1 < x && !a[i-1][j+1] && !a[i][j]) w[i][j] += w[i-1][j+1];

	if(a[i][j] != 1 && a[i-1][j] != 2) w[i][j] += w[i-1][j];

	if(a[i][j] == 1) w[i][j] = 0;
      }
    }

    for(int i=0;i<x;i++){
      if(a[y-2][i] == 2) ans += w[y-2][i];
      if(a[y-1][i] == 2) ans += w[y-1][i];
    }

    for(int i=0;i<x;i++){
      if(a[y-1][i] == 0) ans += w[y-1][i];
    }

    cout << ans << endl;
  }
}

Measured memory_bytes: 1216
#include <iostream>
#include <stdlib.h>
#include <iomanip>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    
    int num[n-1];

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

    for (int i = 0; i < n; ++i)
    {
        if (i) cout << " ";
        cout << num[n-1-i];
    }
    cout << endl;
}

Measured memory_bytes: 1160
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

int main(void)
{
    int X;
    while(cin>>X){
        int low = 1, high = 45000, mid;
        int ans = 1;
        while(low <= high) {
            mid = (low + high) / 2;
            if(mid * (mid + 1) / 2 >= X) {
                ans = mid;
                high = mid - 1;
            }else {
                low = mid + 1;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}


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

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<int, int> P;

const int MOD = 1000000007;
const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];
    multiset<int> s;
    int ans = 0;
    rep(i, N)
    {
        auto it = s.lower_bound(A[i]);
        if (it == s.begin()) {
            s.insert(A[i]);
            // cout << "i: " << i << endl;
            // cout << A[i] << endl;
            ans++;
        } else {
            auto p = prev(it);
            s.erase(p);
            s.insert(A[i]);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 8284
#include<iostream>
using namespace std;
int main() {
	int sx, sy, tx, ty;
	cin >> sx >> sy >> tx >> ty;
	for (int i = 0; i < ty - sy; ++i) {
		cout << 'U';
	}
	for (int i = 0; i < tx - sx; ++i) {
		cout << 'R';
	}
	for (int i = 0; i < ty - sy; ++i) {
		cout << 'D';
	}
	for (int i = 0; i < tx - sx; ++i) {
		cout << 'L';
	}
	cout << 'L';
	for (int i = 0; i <= ty - sy; ++i) {
		cout << 'U';
	}
	for (int i = 0; i <= tx - sx; ++i) {
		cout << 'R';
	}
	cout << 'D' << 'R';
	for (int i = 0; i <= ty - sy; ++i) {
		cout << 'D';
	}
	for (int i = 0; i <= tx - sx; ++i) {
		cout << 'L';
	}
	cout << 'U';
	return 0;
}

Measured memory_bytes: 256
N=int(input())
A=[int(i) for i in input().split()]
dp=[0 for i in range(N)]
AL=A[0]
AR=A[0]
flag0=0
for i in range(1,N):
    AL=AL^A[i]
    AR=AR+A[i]
    if AL!=AR:
        dp[0]=i
        AL=A[i]^AL
        AR-=A[i]
        flag0=1
        break
if flag0==0:
    dp[0]=N
for i in range(1,N):
    AL=AL^A[i-1]
    AR=AR-A[i-1]
    flag=0
    for j in range(dp[i-1],N):
        AL=AL^A[j]
        AR=AR+A[j]
        if AL!=AR:
            dp[i]=j
            AL=A[j]^AL
            AR-=A[j]
            flag=1
            break
    if flag==0:
        dp[i]=N
print(sum(dp)-(N*(N-1))//2)


Measured memory_bytes: 86860
#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int n;
char s[N][N];
bitset<N>a[N],dp[N],tmp;
int main(){
	scanf("%d",&n);
	for(int i=2;i<=n;i++){
		scanf("%s",s[i]+1);
		for(int j=1;j<i;j++){
			int t=s[i][j]-'0';
			a[i][j]=t;
			a[j][i]=a[i][j]^1;
		}
	}
	for(int i=1;i<=n;i++)dp[i][i]=1;
	for(int k=2;k<=n;k++)
		for(int i=1;i+k-1<=n;i++){
			int j=i+k-1;
			tmp=a[i]&dp[j]&dp[i+1];
			dp[j][i]=(tmp._Find_next(i)<=j);
			tmp=a[j]&dp[j-1]&dp[i];
			dp[i][j]=(tmp._Find_next(i-1)<j);
		}
	printf("%d\n",(dp[1]&dp[n]).count());
	return 0;
}

Measured memory_bytes: 5120
#[allow(unused_macros)]
macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; let mut next = || { iter . next ( ) . unwrap ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let mut bytes = std :: io :: Read :: bytes ( std :: io :: BufReader :: new ( stdin . lock ( ) ) ) ; let mut next = move || -> String { bytes . by_ref ( ) . map ( | r | r . unwrap ( ) as char ) . skip_while ( | c | c . is_whitespace ( ) ) . take_while ( | c |! c . is_whitespace ( ) ) . collect ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules ! input_inner { ( $ next : expr ) => { } ; ( $ next : expr , ) => { } ; ( $ next : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ next , $ t ) ; input_inner ! { $ next $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules ! read_value { ( $ next : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ next , $ t ) ) ,* ) } ; ( $ next : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ next , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ next : expr , chars ) => { read_value ! ( $ next , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ next : expr , usize1 ) => { read_value ! ( $ next , usize ) - 1 } ; ( $ next : expr , $ t : ty ) => { $ next ( ) . parse ::<$ t > ( ) . expect ( "Parse error" ) } ; }

fn main() {
    input! {
        s: chars
    }

    println!("{}",
        if (s.len() % 2 == 0) ^ (s[0] == s[s.len()-1]) {"Second"}
        else {"First"}
    )
}


Measured memory_bytes: 4352
/*
オーダー
10**6	余裕を持って間に合う	
10**7	おそらく間に合う	余裕を持って間に合う
10**8	非常にシンプルな処理でない限り厳しい	おそらく間に合う
10**9		非常にシンプルな処理でない限り厳しい
logn	:OK
n		:10^7
nlogn	:10^6
n**2	:10^4
n**3	:300
2**n	:20
n!		:10



// 各桁の和を計算する関数
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

sort(a, a + N, greater<int>());  // a[0:N] を大きい順にソート

int num[110] = {0};  // バケット
for (int i = 0; i < N; ++i) {
    num[d[i]]++;  // d[i] が 1 個増える
}

map<string, int> mp; // 連想配列 map<キー型, 値型> オブジェクト名
for (int i = 0; i < N; ++i) {
    auto itr = mp.find(s[i]);        // s[i] が設定されているか？
    if(itr != mp.end() ) {
         mp[s[i]] += 1;
    }
    else {
         mp[s[i]] += 1 ;
    }
}
stack<int> s;	//intをデータとするスタックを用意
s.push(1);		//{} -> {1}
printf("%d\n", s.top());	// 3
s.pop();

queue<int> que;	//intをデータとするキューを用意
que.push(1);		//{} -> {1}
printf("%d\n", que.front());	// 1
que.pop();
*/

#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <string.h>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(long long i = 0; i < (long long)(n); i++)
#define pb push_back // vectorに要素追加
#define INF (ll)1e18
// int 
// // 各桁の和を計算する関数
// int findSumOfDigits(int n) {
//   int amari = 0;
//   int keta = 0;
//   while (n > 0) { // n が 0 になるまで
//     amari += n % 2;
//     if (keta%2==0)
//     n /= 10;
//   }
//   return sum;
// }
 
ll gcd(ll a, ll b) {
	if(b == 0) return a;
	return gcd(b, a % b);
}

// const ll MAX_N = 1e5;
// ll N;
// ll h[MAX_N];
// ll dp[MAX_N+1]; // メモ化テーブル
 
// // i番目以降の品物から重さの総和がj以下になるように選ぶ
// void rec(ll i){
// 	if (i==0) dp[i] = 0;
// 	else if (i==1) dp[i] = abs(h[1]-h[0]);
// 	else dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
// 	return;
// }
 
 
int main() {
	// 入力
	ll N,A,B;
	cin >> N>>A>>B;
	
	// 解法
	ll ans = (B*(N-1)+A) - (A*(N-1)+B)+1;
	ans = max(ll(0), ans);
	
	//出力
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <unordered_set>

using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  if (a == b && b == c) {
    cout << 0 << endl;
    return 0;
  }
  queue<vector<int>> q;
  unordered_set<string> strs;
  int v[6][3] = {{1,1,0}, {1,0,1}, {0,1,1}, {2,0,0},{0,2,0},{0,0,2}};
  q.push({a, b, c});
  strs.insert(to_string(a) + " " + to_string(b) + " " + to_string(c));
  int steps = 1;
  while (!q.empty()) {
      int sz = q.size();
      while (sz--) {
            auto p = q.front();
      
            q.pop();
            for (int i = 0; i < 6; ++i) {
                vector<int> np({p[0] + v[i][0], p[1] + v[i][1], p[2] + v[i][2]});
                if (np[0] == np[1] && np[1] == np[2]) {
                    cout << steps << endl;
                    return 0;
                }
                string s = to_string(np[0]) + " " + to_string(np[1]) + " " + to_string(np[2]);
                if (strs.count(s)) continue;
                q.push(np);
                strs.insert(s);
            }
      }
      steps++;
  }
  return 0;
}


Measured memory_bytes: 8100
import std.stdio,std.string,std.conv;
void main(){
	auto n = to!int(readln().chomp());
	for( int i=0; i<n ; i++ ){
		auto arr = readln().chomp().split();
		double[] arr2;
		arr2.length = arr.length;
		for( int j=0; j<arr.length ; j++ ){
			arr2[j] = to!double( arr[j] );
		}
		if( (arr2[3]-arr2[1])/(arr2[2]-arr2[0]) == (arr2[7]-arr2[5])/(arr2[6]-arr2[4]) ){
			writeln("YES");
		}else{
			writeln("NO");
		}
	}
}

Measured memory_bytes: 1072
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <set>
#include <queue>

using namespace std;
using PII = pair<int, int>;

vector<set<int>> graph;
vector<PII> ans;

int main() {
	int n, m, x, y;
	cin >> n >> m;

	graph.assign(n, {});

	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		x--;
		y--;

		graph[x].insert(y);
		graph[y].insert(x);
	}

	if (m % 2 == 1) {
		cout << -1 << endl;
		return 0;
	}

	priority_queue<PII, vector<PII>, greater<PII>> que;
	for (int i = 0; i < n; i++) {
		que.push(make_pair(graph[i].size(), i));
	}

	vector<int> n_out(n, 0);

	while (!que.empty() && ans.size() < m) {
		auto p = que.top();
		que.pop();
		int node = p.second;

		// printf("p: node %d, first %d, size %lu\n", node, x, graph[x].size());
		if (graph[node].empty()) {
			continue;
		}

		// if (graph[node].size() == 1) {
			int from = node;
			int to = *graph[from].begin();
			// printf("x1: from %d, to %d\n", from, to);

			if (n_out[from] % 2 == 0) {
				ans.emplace_back(make_pair(to, from));
				n_out[to]++;
			} else {
				ans.emplace_back(make_pair(from, to));
				n_out[from]++;
			}

			graph[from].erase(to);
			graph[to].erase(from);

			que.push(make_pair(graph[from].size(), from));
			que.push(make_pair(graph[to].size(), to));
		// } else {
		// 	int from = node;
		// 	int to1 = *graph[from].begin();
		// 	int to2 = *graph[from].rbegin();
		// 	// printf("x2: from %d, to %d %d: size %lu %lu %lu\n", from, to1, to2, graph[from].size(), graph[to1].size(), graph[to2].size());
		// 	ans.emplace_back(make_pair(from, to1));
		// 	ans.emplace_back(make_pair(from, to2));
		// 	n_out[from] += 2;

		// 	graph[from].erase(to1);
		// 	graph[from].erase(to2);
		// 	graph[to1].erase(from);
		// 	graph[to2].erase(from);

		// 	que.push(make_pair(graph[from].size(), from));
		// 	que.push(make_pair(graph[to1].size(), to1));
		// 	que.push(make_pair(graph[to2].size(), to2));
			// printf("x3: from %d, to %d %d: size %lu %lu %lu\n", from, to1, to2, graph[from].size(), graph[to1].size(), graph[to2].size());
		// }
	}

	for (auto p: ans) {
		cout << p.first+1 << " " << p.second+1 << endl;
	}
	return 0;
}


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

int main(){
int a;
int b;

//tap
cin >> a;
//kuti
cin >> b;
int tap = 1;

int ans;

while(tap < b ){
    tap += a-1;
    ans ++;
}

cout << ans << endl;

}

Measured memory_bytes: 256
<?php


fscanf(STDIN, "%d", $n);

$array = explode(" ",trim(fgets(STDIN)));

while(count($array ) >1 ){

    sort($array);
    $array[] = ($array[0] + $array[1]) /2;
    unset($array[0]);
    unset($array[1]);
}

sort($array);
echo $array[0];



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

int main(){
  int ans=0;
  vector<int> x(5,0),y(5,0);
  REP(i,5){
    cin>>x.at(i);
    ans+=((x.at(i)-1)/10+1)*10;
    y.at(i)=(x.at(i)-1)%10;
  }
  sort(y.begin(),y.end());
  ans-=(9-y.at(0));
  cout<<ans;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using ll = long long;
namespace mp = boost::multiprecision;
using mpint = mp::cpp_int; // 多倍長整数（任意精度）

/*
 * 定数
 */
const long double PI = (acos(-1));
const long double EPS = 1e-10;
const long long INF = 1e18;

/*
 * データ変換 
 */
/* char -> int */
int ctoi(char c) { return (int)(c - '0'); }

/*
 * 数学的な計算
 */
/* 階乗 */
int factorial(int n){ int ret = 1; for(int i = 1; i < n + 1; ++i) { ret = ret * i; } return ret; }

/* 最大公約数 */
template <typename T>T gcd(T x, T y){ return x % y == 0 ? y : gcd(y, x % y); }

/* 最小公倍数 */
template <typename T>T lcm(T a, T b) { return a * b / gcd(a, b); }

/* n個の整数の最小公倍数 */
template <typename T>T lcm_n(vector<T> &numbers) { T l; l = numbers[0]; for(int i = 1; i < numbers.size(); ++i) { l = lcm(l, numbers[i]); } return l; }

/*
 * DP向け
 */
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

/*
 * グラフ
 */
class Graph {
   public:
    vector<vector<int>> G;
    vector<int> Trans;
    vector<int> inDeg;
    int numV;
 
    Graph(int numV) {
        this->numV = numV;
        inDeg.assign(numV, 0);
        Trans.assign(numV, 0);
        G.assign(numV, vector<int>());
    }
 
    int topologicalSort(int v, vector<int> &dp) {
        if (dp[v] != -1) {
            return dp[v];
        }
 
        int res = 0;
 
        for (auto to : G[v]) {
            chmax(res, topologicalSort(to, dp) + 1);
        }
 
        return dp[v] = res;
    }
};



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

  if( N % 2 == 0){
    ll d = 5;
    ll ans = 0;
    N /= 2;
    for(int i = 1; i < 26; ++i){
      ans += N / d;
      d *= 5;
    }
    cout << ans << endl;
  } else{
    cout << 0 << endl;
  }

  return 0;
}


Measured memory_bytes: 256
//#pragma GCC optimize "trapv"
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ld;
#define S 1000001
#define M 1000000007
#define nl cout<<"\n";
#define er  cout<<"\n***********\n";
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define test lli t;  cin>>t; while(t--)
#define f0(s,a,b) for(lli s=a;s<b;s++)
#define f1(s,a,b) for(lli s=a;s<=b;s++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define print(x) cout<< #x <<"=" <<x<<"\n";
#define out(x) cout<<x;
#define  Y cout<<"YES\n";
#define N cout<<"NO\n";

int main()
{
    lli n,k;
    cin>>n>>k;
    if(n>k)
    cout<<"safe";
    else
    cout<<"unsafe";
    nl

}
//a+b=a⊕b+2∗(a &b)
//__builtin_popcount(number)
//cout<<fixed<<setpricision(8)<<output<<"\n";

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;

constexpr int P = 1000000007;

int inv(int n) {
    int m = P, y = 0, v = 1;
    while (1) {
        int q = m / n;
        int r = m % n;
        if (r == 0) return v < 0 ? v + P : v;
        y -= v * q;
        swap(y, v);
        m = n;
        n = r;
    }
}

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

    int n;
    cin >> n;

    int i0, i1;
    vector<int> b(n, -1);
    for (int i = 0; i <= n; i++) {
        int a;
        cin >> a;
        a--;

        if (b[a] < 0) {
            b[a] = i;
        } else {
            i0 = b[a];
            i1 = i;
            break;
        }
    }

    int m = n + 1, l = m - (i1 - i0 + 1);
    int64_t c0 = 1, c1 = 1;
    for (int i = 1; i <= m; i++) {
        int j = inv(i);
        c0 = c0 * (m + 1 - i) % P;
        c0 = c0 * j % P;

        int64_t r = c0 - c1;
        r %= P;
        if (r < 0) r += P;
        cout << r << '\n';

        // 0になったらそのあとずっと0
        c1 = c1 * (l + 1 - i) % P;
        c1 = c1 * j % P;
    }

    return 0;
}

Measured memory_bytes: 1664
n, k = map(int, input().split())
mod = 10 ** 9 + 7

ans = 0
for i in range(k, n+2):
    x = (i - 1) * i // 2
    y = (2 * n - i + 1) * i // 2
    ans = (ans + y - x + 1) % mod

print(ans)

Measured memory_bytes: 9188
N,A = map(int, input().split())
x = list(map(int,input().split()))

INF = 2500

y = [i-A for i in x]
y.sort()

y1 = [abs(x) for x in y if x < 0]
y2 = [x for x in y if x > 0]

y3 = [x for x in y if x == 0]


def p(y,A):
      dp=[[0 for i in range(A+1)] for j in range(N+1)]
      dp[0][0]=1
      N1 = len(y)
      #DP
      for i in range(N1):
          for j in range(A+1):
              if y[i]<=j: #i+1番目の数字a[i]を足せるかも
                  dp[i+1][j]=dp[i][j-y[i]]+ dp[i][j]
              else: #入る可能性はない
                  dp[i+1][j]=dp[i][j]
      return dp[N1]


dp1 = p(y1,INF)
dp1[0] = 0
dp2 = p(y2,INF)

n = min(len(dp1),len(dp2))

ans = 2 ** len(y3) - 1
for i in range(INF):
    ans += dp1[i] * dp2[i] * (2 ** len(y3))

print(ans)

Measured memory_bytes: 4468
// C - Cat Snuke and a Voyage
#include <bits/stdc++.h>
using namespace std;

int main(){
	int N,M; cin>>N>>M;
	vector<bool> P(N);
	while(M--){
		int a,b; cin>>a>>b;
		if(a==1){
			if(P[b-1]) break;
			P[b-1] = true;
		}
		if(b==N){
			if(P[a-1]) break;
			P[a-1] = true;
		}
	}
	cout<< (M<0? "IMPOSSIBLE":"POSSIBLE") <<endl;
}

Measured memory_bytes: 256
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,l = map(int, input().split())
    a = []
    for i in range(n):
        a.append(l+i)
    b = 10**10
    for i in range(n):
        if b>abs(a[i]):
            b = abs(a[i])
            c = a[i]
    print(sum(a)-c)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3316
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>

using namespace std;
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REPR(i,n) for(int i=(n)-1;i>=0;i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define PAU system("pause")

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 28);
const ll LINF = 1e18;
const double PI = acos(-1);

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	string S;
	cin >> S;
	string key = "keyence";
	bool ans = false;
	REP(i, SZ(S)) {
		if (i > SZ(key))break;
		int rest = SZ(key) - i;
		int keyind = 0;
		REP(j, SZ(S)) {
			if (i > j) {
				if (S[j] != key[keyind]) {
					break;
				}
				keyind++;
			}
			else if (j < SZ(S) - rest) {
				continue;
			}
			else {
				if (S[j] != key[keyind]) {
					break;
				}
				keyind++;
			}
			if (j == SZ(S) - 1) {
				ans = true;
				break;
			}
		}
	}
	if (ans)cout << "YES" << endl;
	else cout << "NO" << endl;
	PAU;
	return 0;
}


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

using namespace std;

void get_elem(int A[], int n);
bool binary_search(int A[], int n, int key);

#define MAX 100000
int main()
{
	int S[MAX];
	int n, m, sum = 0;
 	cin >> n;
 	get_elem(S, n);

	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int key;
		cin >> key;
		if (binary_search(S, n, key)) sum++;
	}
 	cout << sum << endl;
	return 0;
	
}



void get_elem(int A[], int n)
{
	for (int i = 0; i < n; i++)
	{
		cin >> A[i];
	}
}

bool binary_search(int A[], int n, int key)
{
	int low = 0, high = n, mid;
	while (low < high)
	{	mid = (low + high)/2;
		if (A[mid] == key) return true;
		else if(key < A[mid]) high = mid;
		else low = mid + 1;
	}
	return false;
}


Measured memory_bytes: 3384
#include <cstdio>
#include <algorithm>

using namespace std;

bool p[1000001];
int cnt[1000001];
int main()
{
	p[2] = true;
	
	for (int i = 3; i <= 1000000; i += 2) p[i] = true;
	
	for (int i = 3; i <= 1000000; i += 2){
		if (p[i]){
			for (int j = 3 * i; j <= 1000000; j += 2 * i)
				p[j] = false;
		}
	}
	
	for (int i = 1; i <= 1000000; i++){
		cnt[i] = cnt[i - 1] + p[i];
	}

	int n;
	
	while (scanf("%d", &n) && n){
		int ans, a, b;
		ans = 0;
		for (int i = 0; i < n; i++){
			scanf("%d %d", &a, &b);
			ans += cnt[min(1000000, a + b)] - cnt[max(0, a - b - 1)] - 1;
		}
		printf("%d\n", ans);
	}
	
	return (0);
}

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

#define MOD 1000000007

int n;
int dp[52][2];
string a, b, c;

int main(){
  while(cin >> a >> b >> c){
    n = a.size();

    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;

    for(int i = 0; i < n; i++){
      for(int j = 0; j < 2; j++){
        if(dp[i][j] == 0) continue;

        int idx = n - i - 1;

        for(int ai = 0; ai < 10; ai++){
          if(a[idx] != '?' && a[idx] - '0' != ai) continue;
          if(idx == 0 && ai == 0) continue;

          for(int bi = 0; bi < 10; bi++){
            if(b[idx] != '?' && b[idx] - '0' != bi) continue;
            if(idx == 0 && bi == 0) continue;

            for(int ci = 0; ci < 10; ci++){
              if(c[idx] != '?' && c[idx] - '0' != ci) continue;
              if(idx == 0 && ci == 0) continue;
              if((ai + bi + j) % 10 != ci) continue;

              int nj = (ai + bi + j) / 10;

              dp[i + 1][nj] += dp[i][j];
              dp[i + 1][nj] %= MOD;
            }
          }
        }
      }
    }

    cout << dp[n][0] << endl;
  }
}

Measured memory_bytes: 1180
#include<stdio.h>
#include<iostream>
#include<string>
#include<algorithm>
#include <vector>

using namespace std;

int main()
{
    int dis[3];
    cin >> dis[0] >> dis[1] >> dis[2];
    sort(dis, dis + 3);
    cout << dis[0] + dis[1];
    return 0;
}

Measured memory_bytes: 256
bingo=[]
for i in range(3):
  a=list(map(int,input().split()))
  bingo.append(a)
  
n=int(input())
for i in range(n):
  b=int(input())
  for j in range(3):
    if b in bingo[j]:
      bingo[j][bingo[j].index(b)]=0
      
def hantei(l):
  for i in range(3):
    if all([l[i][j]==0 for j in range(3)]):
      return 'Yes'
    
    elif all([l[j][i]==0 for j in range(3)]):
      return 'Yes'
    
    elif l[0][0]==0 and l[1][1]==0 and l[2][2]==0:
      return 'Yes'
    
    elif l[0][2]==0 and l[1][1]==0 and l[2][0]==0:
      return 'Yes'
    
    else:
      continue
      
  return 'No'
    
#print(bingo)
print(hantei(bingo))

Measured memory_bytes: 9252
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	cin >> n;
	int a[1000];
	int sum = 0;
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	int min=1111;
	for(int i=0;i<n;i++)
	{	
		sum=0;	
		while(a[i]%2==0){
			a[i]/=2;
			sum++;
		}
	//	printf("%d\n",a[i]);
		//printf("%d\n",sum);
		if(sum<min)
		{
			min=sum;
		}
	}
	printf("%d\n",min);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#define MOD 1000000007
#define mkp make_pair
typedef long long ll;
using namespace std;

ll N,K;

ll dp[2][100010];

ll r[100010];
ll p[100010];

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

  int cnt=1;
  for(ll i=1;i<=N;){
      int x=N/i;
      int a=N/x;
      int b=N/(x+1)+1;
      if(i==1) b=1;

      r[cnt]=a-b+1;
      i+=(a-b+1);
      cnt++;
  }

  cnt--;
  for(int i=0;i<=cnt;i++) dp[0][i]=1;

  int t=0;
  for(int i=1;i<=K;i++){
      for(int j=1;j<=cnt;j++){
          dp[(t+1)%2][j]=dp[t][cnt-j+1]*r[j]%MOD;
      }

      t^=1;
      for(int j=2;j<=cnt;j++) dp[t][j]=(dp[t][j]+dp[t][j-1])%MOD;
  }

  ll ans=dp[t][cnt];

  cout<<ans<<endl;


  return 0;
}


Measured memory_bytes: 1792
import itertools


a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

# a<b<c<d<e を利用
max_distance = e - a

if max_distance <= k:
    print('Yay!')
else:
    print(':(')

# 全組み合わせの探索
# combs = itertools.combinations([a, b, c, d, e], 2)
# 
# can_connects = [abs(x[0] - x[1]) <= k for x in combs]
# 
# if all(can_connects):
#     print('Yay!')
# else:
#     print(':(')




Measured memory_bytes: 3060
n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
bc=[]
for i in range(q):
    bc.append([int(x) for x in input().split()])

a_cnt=[0]*(10**5+1)

for i in range(len(a)):
	a_cnt[a[i]]+=1

a_goukei=sum(a)

for gyou in range(q):
	a_goukei+=(bc[gyou][1]-bc[gyou][0])*a_cnt[bc[gyou][0]]
	print(a_goukei)
	a_cnt[bc[gyou][1]]+=a_cnt[bc[gyou][0]]
	a_cnt[bc[gyou][0]]=0

Measured memory_bytes: 31148
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int mod = 1e9 + 7;

int main(void)
{
    int n;
    cin >> n;
    int a[110], b[110];
    for (int i = 0; i < n;i++){
        cin >> a[i];
    }
    for (int i = 0; i < n;i++){
        cin >> b[i];
    }
    int ans = 0;
    for (int i = 0; i < n;i++){
        int sum = 0;
        for (int j = 0; j <= i;j++){
            sum += a[j];
        }
        for (int k = i; k < n;k++){
            sum += b[k];
        }
        ans = max(ans, sum);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
 
public class Main {
  public static void main(String[] args ){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    String S = sc.next();
    int count =0;
    
   S = S.replace("ABC","");
    count = (N - S.length())/3;
    System.out.println(count);
}
}

Measured memory_bytes: 25172
// <string.cpp> - Sat Mar 25 20:06:07 2017
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
template<typename T>
inline void gg(T &res){
    res=0;T fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    res*=fh;
}
inline int gi(){int x;gg(x);return x;}
inline lol gl(){lol x;gg(x);return x;}
const int MAXN=500010;
const int K=21;
const int INF=1e9;
char s[MAXN];
int a[MAXN][27],b[K][MAXN];
int main(){
    scanf("%s",s+1);
    int n=strlen(s+1);
    for(int i=n;i;i--){
        a[i][s[i]-'a']=i+1;
        for(int j=s[i]-'a'+1;j<=26;j++)a[i][j]=a[a[i][j-1]][j-1];
        for(int j=0;j<s[i]-'a';j++)a[i][j]=a[a[i][26]][j];
    }
    for(int i=1;i<=n;i++)b[0][i]=a[i][26];
    for(int j=1;j<K;j++)
        for(int i=1;i<=n;i++)b[j][i]=b[j-1][b[j-1][i]];
    int q=gi();
    while(q--){
        int l=gi(),r=gi()+1;
        for(int i=K-1;i>=0;i--)
            if(b[i][l]&&b[i][l]<=r)l=b[i][l];
        puts(l==r?"Yes":"No");
    }
    return 0;
}

Measured memory_bytes: 94848
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define lli long long int
#define llu long long unsigned int
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define FOR(i,s,e) for(i=s; i<e; i++)
#define F first
#define S second
#define plli pair<lli,lli>
#define pqlli priority_queue<lli>
#define test(t) cin>>t; while(t--)
#define MX 5003
using namespace std;

int main() 
{
	IOS;
	string s;
	cin>>s;
	int flag = 1;
	int n = s.length();
	for(int i = 0; i<n; i++)
	if(s[i] != s[n-1-i])
	flag = 0;

	for(int i = 0; i<n/2; i++)
	{
		if(s[i] != s[n/2-1-i])
		flag = 0;
	}

	for(int i = n/2+1; i<n; i++)
	{
		if(s[i] != s[n-(i-n/2)])
		flag = 0;
	}
	if(flag)
	cout<<"Yes\n";
	else
	cout<<"No\n";
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
ans1,ans2 = 0,0
sum1,sum2 = 0,0
for i in range(n):
    sum1 += a[i]
    if i%2 == 1 and sum1 >= 0:
        ans1 += sum1 + 1
        sum1 = -1
    elif i%2 == 0 and sum1 <= 0:
        ans1 += -sum1 + 1
        sum1 = 1
for i in range(n):
    sum2 += a[i]
    if i%2 == 0 and sum2 >= 0:
        ans2 += sum2 + 1
        sum2 = -1
    elif i%2 == 1 and sum2 <= 0:
        ans2 += -sum2 + 1
        sum2 = 1
print(min(ans1,ans2))

Measured memory_bytes: 14468
n, a = map(int, input().split())
X = list(map(int, input().split()))
dp = [ [[0]*(n*a+1) for j in range(i+1)] for i in range(n+1) ]
for i in range(n+1):
  dp[i][0][0] = 1
for i in range(n):
  for j in range(i+1):
    for k in range(n*a+1):
      if X[i] > k:
        if i > j:
          dp[i+1][j+1][k] = dp[i][j+1][k]
      else:
        if i > j:
          dp[i+1][j+1][k] = dp[i][j+1][k] + dp[i][j][k-X[i]]
        else:
          dp[i+1][j+1][k] = dp[i][j][k-X[i]]
ans = 0
for i in range(1, n+1):
  ans += dp[n][i][a*i]
print(ans)

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


template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

#define INF 100000000000000009
#define MAX_V 100000

struct edge {
    ll to;
    ll cost;
};


ll V;
vector<edge> G[MAX_V];
ll d[MAX_V];

void dijkstra(ll s) {
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d, d+V, INF);
    d[s] = 0;
    que.push(make_pair(0, s));

    while (!que.empty()) {
        P p = que.top();
        que.pop();
        ll v = p.second;
        if (d[v] < p.first) continue;

        for (ll i=0; i<G[v].size(); ++i) {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(make_pair(d[e.to], e.to));
            }
        }
    }
}

int main(){
    cin>>V;
    rep(i,V-1){
        ll a,b,c;
        cin>>a>>b>>c;
        --a;--b;
        edge e={b,c};
        edge f={a,c};
        G[a].push_back(e);
        G[b].push_back(f);
    }

    ll q,k;
    cin>>q>>k;
    dijkstra(--k);
    rep(i,q){
        ll a,b;
        cin>>a>>b;
        cout<<d[--a]+d[--b]<<endl;
    }
}


Measured memory_bytes: 11120
#include <iostream> 
#include<string.h>
using namespace std; 
typedef long long int ll;


int minimumChar(string S1, string S2) 
{ 
	ll n = S1.size();
	ll m = S2.size(); 

	ll ans = 10000; 

	
	for (int i = 0; i < m - n + 1; i++)
	 { 
		ll  minRemovedChar = 0; 

		for (int j = 0; j < n; j++) { 
			if (S1[j] != S2[i + j]) { 
				minRemovedChar++; 
			} 
		} 

		
		ans = min(minRemovedChar, ans); 
	} 

	return ans; 
} 

// Driver Code 
int main() 
{ 
   string S1,S2;
    cin>>S1>>S2;

	cout << minimumChar(S2, S1); 
} 


Measured memory_bytes: 3628
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
int main(){
int i,j,m,n,flag[50][3]={0},ans=50*50,king=0,qween=0,jack=0,l;
char habdsv[101];
cin>>n>>m;
for(i=0;i<n;i++){
	scanf("%s",habdsv);
	for(j=0;j<m;j++){
		if(habdsv[j]!='W')flag[i][0]++;
		if(habdsv[j]!='B')flag[i][1]++;
		if(habdsv[j]!='R')flag[i][2]++;
	}
}
for(i=0;i<n-2;i++){
	king+=flag[i][0];
	for(j=i+1;j<n-1;j++){
		qween+=flag[j][1];
		for(l=j+1;l<n;l++){
			jack+=flag[l][2];
		}
		ans=min(ans,king+qween+jack);
		jack=0;
	}
	qween=0;
}
cout<<ans<<endl;
return 0;
}



Measured memory_bytes: 3128
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i < (n); i++)
#define lower(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
using namespace std;
using ll = long long;
int INF = 1001001001;

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

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

int main()
{
	int n;
	bool p[50001] = {false, false};
	
	for (int i = 2; i * i < 50001; i++){
		for (int j = i * i; j < 50001; j += i){
			p[j] = true;
		}
	}
	while (cin >> n, n){
		int c = 0;
		for (int i = 2; i <= n / 2; i++){
			if (!p[i] && !p[n - i]){
				c++;
			}
		}
		cout << c << endl;
	}
	return (0);
}

Measured memory_bytes: 1216
h, w = map(int, input().split())

g = []
for _ in range(10):
    a = list(map(int, input().split()))
    g.append(a)

for k in range(10):
    for i in range(10):
        for j in range(10):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

ans = 0
for i in range(h):
    ans += sum(map(lambda x: g[x][1],
                   filter(lambda x: x != -1, map(int, input().split()))))
print(ans)


Measured memory_bytes: 9148
n=int(input())
l=list(map(int,input().split()))
l.sort()

cnt=0

for i in range(len(l)):
    for j in range(len(l)):
        for k in range(len(l)):
            if l[i]<l[j]<l[k]:
                if l[k]<l[i]+l[j]:
                    cnt+=1


print(cnt)


Measured memory_bytes: 9192
N = int(input())
h = list(map(int, input().split()))
 
suml = [1e5 for i in range(N)]
suml[0] = 0
suml[1] = abs(h[1] - h[0])
 
for e in range(2, N):
    suml[e] = min(
        abs(h[e]-h[e-1]) + suml[e-1],
        abs(h[e]-h[e-2]) + suml[e-2],
    )
 
# print(suml)
print(suml[N-1])

Measured memory_bytes: 13928
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read() {
    ll x=0,f=1; char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())
        if(ch=='-')f=-f;
    for(;ch>='0'&&ch<='9';ch=getchar())
        x=x*10+ch-'0';
    return x*f;
}
inline void chkmin( int &a,int b ) { if(a>b) a=b; }
inline void chkmax( int &a,int b ) { if(a<b) a=b; }
#define _ read()
#define ln endl
int main() {	
	int k=_,x=_;
	for( int i=x-k+1;i<=x;i++ ) cout<<i<<" ";
	for( int i=x+1;i<=x+k-1;i++ ) cout<<i<<" ";
}	

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

ll powfive(ll x){
    return x*x*x*x*x;
}

int main(){
    ll x; cin>>x;
    for(ll i=1; i*i<=x; i++){
        if(x%i!=0) continue;
        ll j = x/i;
        for(ll b = -1000; b<=1000; b++){
            if((powfive(b+i) - powfive(b) == x)){
                cout << b+i << ' ' << b << endl;
                return 0;
            }
            if((powfive(b+j) - powfive(b) == x)){
                cout << b+j << ' ' << b << endl;
                return 0;
            }
            
        }
    }
    return 0;
}

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

int main() {
	int A, B;
  	cin >> A >> B;
    int C = 0;
  	for(int i = A; i <= B; i++){
    	if(i / 10000 == i % 10){
        	if(i % 10000 / 1000 == i % 10000 % 1000 % 100 / 10){
            	C += 1;
            }
        }
    }
  	cout << C << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; i++)
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
int main(){
    string x;
    cin >> x;
    int l = x.length();
    int sum = 0;
    rep(i,l){
        int c = ctoi(x[i]);
        sum += c;
    }
    if (sum % 9 == 0){
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 3752
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define MOD (int) (1e9+7)
#define INF (int) 2e9

int main(){
    int n;
    cin >> n;
    int a[n], b[n-1];
    rep(i, n-1){
        cin >> b[i];
    }

    int sum =0 ;
    rep(i, n){
        if(i==0){
            a[i] = b[i];
        }else if(i==n-1){
            a[i] = b[n-2];
        }else {
            a[i] = min(b[i], b[i-1]);
        }
        sum += a[i];
    }
    cout << sum << endl;
    // printf("%d\n", N);
    return 0;
}

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

int main(){
	char num1[5], num2[5];
	int hit, blow;
	while(1){
		cin >> num1 >> num2;
		if(num1[0] == '0' && num2[0] == '0') break;
		
		hit = blow = 0;
		for(int n1 = 0;n1 < 4;n1++){
			for(int n2 = 0;n2 < 4;n2++){
				if(n1 == n2 && num1[n1] == num2[n2]) hit++;
				else if(num1[n1] == num2[n2]) blow++;
			}
		}
		cout << hit << ' ' << blow << endl;
	}
	
	return 0;
}

Measured memory_bytes: 860
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
using namespace std;
int main(void){
    int A,B,K;
    cin>>A>>B>>K;
    vector<int> ans;
    for(int i=1;i <= min(A,B);i++){
        if(A % i == 0 && B % i == 0){
            ans.push_back(i);
        }
    }
    sort(ans.begin(),ans.end(),greater<>());
    cout << ans[K-1] << endl;
    
}


Measured memory_bytes: 3172
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;


int main(){
  ll n,k; cin >> n >> k; vl count(n,0); vl counta(0);
  
  for(ll i=0; i < n; i++){
    ll x; cin >> x; count[x-1]++;
  }
  
  for(ll i=0; i < n; i++){
    if(count[i] != 0) counta.push_back(count[i]);
  }
  
  sort(all(counta));
  
  ll delsum = 0; 
  for(ll i=0; i < ll(counta.size())-k; i++) delsum += counta[i];
  
  cout << delsum << endl;
}

Measured memory_bytes: 3956
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define puts(i) cout << i << endl
#define INF INT_MAX;
#define INFL LLONG_MAX;
typedef long long ll;
using namespace std;

int main(){
  int n;
  cin >> n;
  int a[3]={0};
  rep(i,n){
    ll x; cin >> x;
    if(x%4==0) a[2]++;
    else if(x%2==0) a[1]++;
    else a[0]++;
  }

  bool ok = true;

  if(a[1]==0){
    if(a[0]>a[2]+1) ok=false;
  }else{
    if(a[0]>a[2]) ok=false;
  }

  if(ok) puts("Yes");
  else puts("No");
}


Measured memory_bytes: 256