akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include <sstream>
#include <iostream>
#include <cstdlib>
#include <string.h>

using namespace std;

#define BUF_SIZE 1024

int count = 0;

void insertionSort(int array[],int n,int g){
	int v,j;
	for(int i = g;i < n; i++){
		v = array[i];
		j = i - g;
		while(j >= 0 && array[j] > v){
			array[j+g] = array[j];	//??°??????????????§???????????????
			j = j - g;
			count++;
		}
		array[j+g] = v;
	}
}

void shellSort(int array[],int n){
	int m = 0;
	int s = 1;

	while((n/s) > 0){
		s *= 2;
		m++;	//2^(mult-1)?????§?????????????????¨???????¨?
	}

	int G[20];

	for(int k = 0,t = 1; k < m; k++){
		G[k] = n/t;
		t *= 2;
	}

	for(int i = 0; i < m;i++){
		insertionSort(array,n,G[i]);
	}

	printf("%d\n",m);
	for(int i = 0; i < m; i++){
		if(i != m-1){
			printf("%d ",G[i]);
		}else{
			printf("%d\n",G[i]);
		}
	}
	printf("%d\n",count);
	for(int i = 0; i < n; i++){
		printf("%d\n",array[i]);
	}

}

int main(int argc,char* argv[]){
	char buf[BUF_SIZE];
	int n = atoi(fgets(buf,BUF_SIZE,stdin));
	int array[1000000];

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

	shellSort(array,n);

}



Measured memory_bytes: 6992
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;
const ll C = 1e9+7;

int main(){
    string S, T;
    cin >> S >> T;
    int ns = S.size();
    int nt = T.size();
    vector<string> V;
    bool flg;
    string ss;
    for(int i=0; i<ns-nt+1; i++) {
        flg = true;
        for(int j=0; j<nt; j++) {
            if(S[i+j] != T[j] && S[i+j] != '?') {
                flg = false;
            }
        }
        cout << endl;
        if (flg) {
            ss = S;
            ss.replace(i, nt, T);
        }
    }

    if(ss == "") {
        cout << "UNRESTORABLE" << endl;
        return 0;
    }

    for(int i=0; i<ss.size(); i++) {
        if(ss[i] == '?') {
            cout << 'a';
        }
        else {
            cout << ss[i];
        }
    }
}

Measured memory_bytes: 3628
n = int(input())
S = [int(c == 'W') for c in list(input())]
L = [0]
for i in range(n):
    L.append(L[-1]+S[i])
R = [0]
for i in range(n-1, 0, -1):
    R.append(R[-1]+1-S[i])
R.reverse()
print(min([L[i]+R[i] for i in range(n)]))


Measured memory_bytes: 42832
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define krep(i,k,n,m) for(int i=k;i<n;i+=m)
#define erep(i,k,n) for(int i=k;i<n;i++)
#define mod 1000000007;
//最大公約数
int gcd(int s,int b){
    if(b==0)return s;
    return gcd(b,s%b);
}
signed main(){
    int a,b;
    cin>>a>>b;
    cout<<a*b/gcd(a,b)<<endl;
}


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

int main()
{


	int sec;
	int h, m, s = 0;


	cin >> sec;

	h = sec / 3600;
	m = (sec - h*3600) / 60;
	s = sec % 60;

	cout << h << ":" << m << ":" << s << endl;

	return 0;
}

Measured memory_bytes: 1164
import java.util.*;                                                                                  

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] l = line.split(" ");
        int a = Integer.parseInt(l[0]);
        int b = Integer.parseInt(l[1]);
        int c = Integer.parseInt(l[2]);

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

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

int fn(vector<int>& A, vector<int>& B, vector<int>& C) {
    int diff = 0;
    for (auto a: A)
        for (auto b: B) {
            if ((a + b) % 2 == 1)
                continue;
            auto it = find(C.begin(), C.end(), (a + b) / 2);
            if (it != C.end())
                diff += 1;
        }
    return diff;
}

int main () {
    int N;
    string S;
    cin >> N;
    cin >> S;
    vector<int> R;
    vector<int> G;
    vector<int> B;

    for (int i = 0; i < N; i++){
        if (S.at(i) == 'R')
            R.push_back(i);
        if (S.at(i) == 'G')
            G.push_back(i);
        if (S.at(i) == 'B')
            B.push_back(i);
    }

    long long ans = R.size() * G.size() * B.size();
    ans -= fn(R, G, B);
    ans -= fn(R, B, G);
    ans -= fn(B, G, R);
    cout << ans << endl;
}

Measured memory_bytes: 3616
#include <iostream>
#include <sstream>
using namespace std;
#include <bits/stdc++.h>
#include<utility>
#include <algorithm>
#include<iterator>
#define  go return 0
#define rep(i,n) for(int i=0;i<n;++i)
#define rep(j,m) for(int j=0;j<m;++j)
#define REP(i,n) for(int i=1;i<=n;++i)
#define all(v)   ((v).begin()), ((v).end())
#define len(s)   ((int)s.size())
#define F first
#define S second
#define pb push_back
#define pf push_front
#define mp make_pair
typedef long long ll;
typedef double db;
typedef vector<int> ve;
typedef vector< vector < int> > vee;
typedef vector<pair<ll,ll> > vepa;
typedef set<char>se;
typedef map<ll,ll> mpp;
const ll N=1e5+5;
ll arr[N],A[N],cnt[N];
bool visited[N];
bool f,ff;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
   ll n,m,sum=0;
   cin>>n>>m;
   rep(i,m&&cin>>arr[i])
  {
      sum+=arr[i];
  }
  ll ans=n-sum;
  if(ans<0)
    cout<<"-1";
  else
    cout<<ans;

go;
}


Measured memory_bytes: 3632
def main():
    sum_prise = 0
    sum_number = 0
    count = 0
    while True:
        try:
            prise,number = map(int,input().split(","))
            sum_prise += prise*number
            sum_number += number
        except EOFError:
            break
        count += 1
    print(sum_prise)
    print(int(sum_number/count+0.5))
if __name__ == '__main__':
    main()


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

int main(){
  int N,C; cin>>N>>C;
  vector<vector<ll>> d(C+1,vector<ll>(C+1));
  for(int i=1;i<=C;i++){
    for(int j=1;j<=C;j++){
      cin>>d[i][j];
    }
  }
  vector<vector<ll>> c(3,vector<ll>(C+1,0));
  for(int i=1;i<=N;i++){
    for(int j=1;j<=N;j++){
      ll x; cin>>x;
      c[(i+j)%3][x]++;
    }
  }
  ll ans=1000000010;
  for(int i=1;i<=C;i++){//rest 0
    for(int j=1;j<=C;j++){//rest 1
      if(i==j) continue;
      for(int k=1;k<=C;k++){//rest 2
        if(i==k || j==k) continue;
        ll sum=0;
        for(int l=1;l<=C;l++) sum+=c[0][l]*d[l][i];
        for(int l=1;l<=C;l++) sum+=c[1][l]*d[l][j];
        for(int l=1;l<=C;l++) sum+=c[2][l]*d[l][k];
        ans=min(ans,sum);
      }
    }
  }
  cout<<ans<<endl;
}

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

#define ULL unsigned long long
#define LL long long

#define P pair<int, int>

#define pb push_back
//#define mp make_pair
#define pp pop_back

#define lson root << 1
#define rson root << 1 | 1

#define INF32 (int)1e9 + 7
#define INF64 (long long)1e18

#define sc(x) scanf("%d", &x)
#define pr(x) printf("%d\n", x)

#define mem(arry, in) memset(arry, in, sizeof(arry))

#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define BEGIN() int T; sc(T); while(T--)

#define rep(i, aa, bb) for (int i = aa; i < bb; ++i)
#define Rep(i, aa, bb) for (int i = aa; i <= bb; ++i)

#define Size(x) (int)(x).size()
#define Range(x) (x).begin(), (x).end()

#define PI acos(-1)

using namespace std;

/*
namespace fastIO {
    #define BUF_SIZE 100000
    bool IOerror = 0;
    inline char nc() {
        static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
        if(p1 == pend) {
            p1 = buf;
            pend = buf + fread(buf, 1, BUF_SIZE, stdin);
            if(pend == p1) {
                IOerror = 1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
    }
    inline void read(int &x) {
        char ch;
        while(blank(ch = nc()));
        if(IOerror) return;
        for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
    }
    #undef BUF_SIZE
};
using namespace fastIO;
*/
/*
void print64mul(LL x, LL y) {
#if __SIZEOF_INT128__ == 16
  __int128 res = __int128(x) * y;
  char ch[64];
  int ptr = 0;
  if (res == 0) {
    puts("0");
    return;
  }
  while (res) {
    ch[ptr] = (res % 10) + '0';
    ptr++;
    res /= 10;
  }
  while (ptr)
    putchar(ch[--ptr]);
  putchar('\n');
#else
  constexpr LL limit = 1000000000;
  LL dig[4] = {0};
  dig[0] = x % limit;
  dig[1] = x / limit;
  dig[0] *= y;
  dig[1] *= y;
  dig[1] += dig[0] / limit;
  dig[0] %= limit;
  dig[2] += dig[1] / limit;
  dig[1] %= limit;
  int pos = 2;
  while (pos > 0) {
    if (dig[pos]) break;
    pos--;
  }
  printf("%d", dig[pos]);
  while (pos > 0) {
    pos--;
    printf("%09d", dig[pos]);
  }
  puts("");
#endif
}
*/

const int N = 100005;

int n, m;
int c[N];
vector<int> a[N];

char A[10];

string change(int x) {
    int cnt = 0;
    string op = "";
    while(x) {
        op += A[x % 10];
        x /= 10;
        cnt++;
    }
    string tp = "";
    for (int i = op.size() - 1; ~i; --i) tp += op[i];

    string sp = "";
    rep(i, 0, 6 - cnt) sp += '0';
    return (sp + tp);
}

string ans[N];

map<int, int> id;

int main()
{
    char tt = '0';
    rep(i, 0, 10) A[i] = tt++;

    cin >> n >> m;
    Rep(i, 1, m) {
        int x, y;
        cin >> x >> y;
        a[x].pb(y);
        c[i] = y;
    }
    Rep(i, 1, n) sort(Range(a[i]));


    int cnt = 0;
    Rep(i, 1, n) {
        string op = change(i);

        Rep(j, 1, Size(a[i])) {
            id[a[i][j - 1]] = ++cnt;
            ans[cnt] = op + change(j);
        }

    }

    Rep(i, 1, m) cout << ans[id[c[i]]] << endl;
    return 0;
}


Measured memory_bytes: 17536
#include <string>
#include <iostream>
#include <cstdio>

using namespace std;

int A[1000000], n;

int binarySearch(int key) {
	int left = 0;
	int right = n;
	int mid;

	while (left < right) {
		mid = (left + right) / 2;
		if (key == A[mid]) return 1;
		else if (key > A[mid]) left = mid + 1;
		else right = mid;
	}
	return 0;
}

int main() {

	int i, T, q, C = 0;

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

	cin >> q;
	for (i = 0; i < q; i++) {
		cin >> T;
		if (binarySearch(T)) C++;
	}

	cout << C << endl;

	return 0;

}

Measured memory_bytes: 1548
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

int main()
{
    while(true){
        string S;
        cin >> S;
        if( S == "-" ){
            break;
        }
        int m{0};
        cin >> m;
        int h;
        for(int i=0; i<m ;++i){
            cin >> h;
            string sub;
            sub = S.substr(0, h);
            S.erase(0,h);
            S = S+sub;
        }

        cout << S << endl;
    }

    return 0;
}


Measured memory_bytes: 3220
#include<bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long LL;
typedef pair<int,int> PII;
#define X first
#define Y second
inline int read()
{
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-'0';c=getchar();}
	return x*f;
}
const int MOD=1000000007;
int n;
LL a[200010],sum,ans,pro; 
LL quickpow(LL a,int N,int mod)
{
    LL res=1,tmp=a;
    while(N)
    {
        if(N&1)res=(res*tmp)%mod;
        tmp=(tmp*tmp)%mod;
        N>>=1;
    }
    return res;
} 
LL Inv(LL a){return quickpow(a,MOD-2,MOD);}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)a[i]=read(),sum=(sum+a[i])%MOD,pro=(pro+(a[i]*a[i])%MOD)%MOD;
	printf("%lld\n",(sum*sum%MOD-pro+MOD)*Inv(2)%MOD);
	return 0;
}
/*

*/


Measured memory_bytes: 5304
#include <bits/stdc++.h>
using namespace std;
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;
}
typedef long long int ll;
    
#define EPS (1e-7)
#define INF (1<<30)
#define LLINF (1LL<<60)
#define PI (acos(-1))
#define MOD (1000000007)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//-------------------------------------

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s,t;
    cin>>s>>t;
    int ans=0;
    for(int i=0;i<3;i++){
        if(s[i]==t[i]){
            ans++;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
A = [i for i in input()]
B = [i for i in input()]
C = [i for i in input()]
Acount = 0
Bcount = 0
Ccount = 0
turn = "a"
while True:
    if Acount>len(A):
        print("A")
        break
    if Bcount>len(B):
        print("B")
        break
    if Ccount>len(C):
        print("C")
        break
    if turn == "a":
        turn = A[Acount-1]
        Acount+=1
    elif turn == "b":
        turn = B[Bcount-1]
        Bcount+=1
    else:
        turn = C[Ccount-1]
        Ccount+=1

Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
using namespace std;
const long INF = 1e9;
const long MOD = 1e9 + 7;
#define repi(i, n, init) for (int i = init; i < int(n); i++)

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    cout << (a <= c && c <= b ? "Yes" : "No") << endl;
    return 0;
}

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

using namespace std;

int main() 
{
    string S;
    cin>>S;

    bool dance=true;

    for (int i = 0; i < S.size(); i++)
    {
        char s = S.at(i);
        if(i%2==0)
        {
            if(s=='L')
            {
                dance=false;
                break;
            }
        }
        else
        {
            if(s=='R')
            {
                dance=false;
                break;
            }
        }
    }
    
    
    dance?cout<<"Yes"<<endl:cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 3628
#include <stdio.h>
#include <string.h>
#include <math.h>

int main(void)
{
    int A, B;

    scanf("%d%d",&A,&B);
    if (A<=8 && B <=8) {
        printf("Yay!\n");
    } else {
        printf(":(\n");
    }
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxm=2e5+5;
int a[maxm];
int b[maxm];
int n;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    multiset<int>s;
    s.insert(a[1]);
    for(int i=2;i<=n;i++){
        auto it=s.lower_bound(a[i]);//>=a[i]
        if(it==s.begin()){//最小的都>=a[i],新建一个LIS链
            s.insert(a[i]);
        }else{
            it--;
            s.erase(it);
            s.insert(a[i]);
        }
    }
    cout<<s.size()<<endl;
    return 0;
}
/*

*/


Measured memory_bytes: 8896
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = LLONG_MAX;

int main()
{
    int n, a;
    cin >> n >> a;
    if (n < a)
        cout << 0;
    else
        cout << 10 << endl;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

  public static void main(String[] args) {
    new Main().run();
  }

  public void run() {

    try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

      String t = br.readLine();
      String p = br.readLine();

      if(t.length() < p.length()) return;
      
      boolean soloChar = true;
      char pHead = p.charAt(0);
      for (char c : p.toCharArray()) {
        if(c != pHead) {
          soloChar = false;
          break;
        }
      }

      StringBuilder result = new StringBuilder();
      if(soloChar)
        searchStrSoloChar(t, p, result);
      else
        searchStr(t, p, result);

      System.out.print(result);

    } catch (IOException e) {
      System.err.println(e);
    }
  }

  private void searchStr(String txt, String key, StringBuilder buf) {

    Pattern ptn = Pattern.compile(key);
    Matcher mch = ptn.matcher(txt);

    for (int i = 0; mch.find(i); i++) {
      i = mch.start();
      buf.append(i).append("\n");
    }
  }
  private void searchStrSoloChar(String txt, String key, StringBuilder buf) {

    int max = txt.length() - key.length();
    char kHead = key.charAt(0);
    int first = txt.indexOf(key);
    buf.append(first).append("\n");
    for (int i = first+1;i <= max; i++) {
      if(txt.charAt(i+key.length()-1) == kHead ) {
        buf.append(i).append("\n");
      }
      else {
        i = txt.indexOf(key,i);
        if(i == -1) break;
        else
          buf.append(i).append("\n");
      }
    }
  }
}


Measured memory_bytes: 75220
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007


int main() {
  int N, M;
  cin >> N >> M;
  bool f[100005];
  rep(i, M) {
    int a; cin >> a;
    f[a] = true;
  }

  ll dp[100005] = {};
  dp[0] = 1;
  dp[1] = (!f[1] ? 1 : 0);

  rep(i, N - 1) {
    ll a = (!f[i] ? dp[i] : 0);
    ll b = (!f[i + 1] ? dp[i + 1] : 0);
    dp[i + 2] = (a + b) % MOD;
  }

  cout << dp[N] << endl;

}





Measured memory_bytes: 1152
# 以下カンニング
n = int( input() )
a = list( map( int, input().split() ) )

max_a = max( a )

c = {} # c[ a_i ] = aに含まれるa_iの個数
d = {} # d[ a_i ] = aにa_iの約数( < a_i )があるか(bool)
for a_i in a:
    try:
        c[ a_i ] += 1
    except KeyError:
        c[ a_i ] = 1
        d[ a_i ] = False # 初期値

for a_i in a:
    if c[ a_i ] > 0:
        tmp = 2 * a_i
        while tmp <= max_a:
            d[ tmp ] = True
            tmp += a_i

ans = 0
for a_i in a:
    if c[ a_i ] == 1 and d[ a_i ] == False:
        ans += 1

print( ans )


Measured memory_bytes: 101004
flag = [0 for i in range(8)]
cnt = 0
N = int(input())
A = list(map(int,input().split()))
for i in range(N):
    if A[i] >= 3200:
        cnt += 1
    elif A[i] >= 2800:
        flag[0] = 1
    elif A[i] >= 2400:
        flag[1] = 1
    elif A[i] >= 2000:
        flag[2] = 1
    elif A[i] >= 1600:
        flag[3] = 1
    elif A[i] >= 1200:
        flag[4] = 1
    elif A[i] >= 800:
        flag[5] = 1
    elif A[i] >= 400:
        flag[6] = 1
    else:
        flag[7] = 1
SUM = sum(flag)
print(*[max(SUM, 1), SUM + cnt])

Measured memory_bytes: 3064
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###


import math
N, K = mi()

#各i(1~N→-0~N-1)に何回2を掛けるとk以上になるか
ans = 0
for i in range(N):
  ans += 1 / (2 ** max(0, math.ceil(math.log2(K/(i+1)))))

print(ans / N)



Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d",&x);
#define scs(x) scanf("%s",x);
#define scl(x) scanf("%lld",&x);
#define rep(i,s,e) for(int i=s; i<=e; ++i)
#define dep(i,s,e) for(int i=s; i>=e; --i)
typedef long long ll;
using namespace std;
const ll mod=998244353;
int main()
{
	int n;
	sc(n);
	while(n){
		if(n%10==7){
			pf("Yes\n");return 0;
		}n/=10;
	}pf("No\n");
}


Measured memory_bytes: 3764
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

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

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;



int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, a;
    cin >> n >> a;
    int a_min = a;
    int a_max = a;
    REP(i, n - 1){
        cin >> a;
        a_min = min(a_min, a);
        a_max = max(a_max, a);
    }

    cout << a_max - a_min << "\n";


    return 0;
}


Measured memory_bytes: 256
#include<iostream>                                              
#include<string>                                                
#define N 100000                                                
using namespace std;                                            
                                                                
int main() {                                                    
  while(true){                                                  
    int m, n;                                                   
    char x[N], y[N], xy[N];                                     
    cin >> n;                                                   
    if (n==0) {                                                 
      break;                                                    
    }                                                           
    for (int j=0; j<n; j++) {                                   
      cin >> x[j] >> y[j];                                      
    }                                                           
    cin >> m;                                                   
    for (int i=0; i<m; i++) {                                   
      cin>>xy[i];                                               
      for (int j=0;j<n;j++) {                                   
        if (xy[i]==x[j]) {                                      
          xy[i] = y[j];                                         
          break;                                                
        }                                                       
      }                                                         
    }                                                           
    for (int i=0; i<m; i++) {                                   
      cout << xy[i] << flush;                                   
    }                                                           
    cout<<endl;                                                 
  }                                                             
  return 0;                                                     
}                                                               
                               

Measured memory_bytes: 3164
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B

main=do
    [n,x]<-map read.words<$>getLine
    print =<< f x 0.unfoldr (B.readInt.B.dropWhile(==' '))<$>B.getLine

f x i [a,b] = max 0 (i+(a+b)-x)
f x i (a:b:as)
    | a+b <= x = f x i (b:as)
    | a > x    = f x (i+a-x+b) (0:as)
    | True     = f x (i+a+b-x) ((x-a):as)


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

int main(){
    int tmp,fgo[114514];
    int n;
    scanf("%d",&n);
    int i;
    for(i=0;i<114514;i++) fgo[i] = 0;
    for(i=0;i<n;i++){
        scanf("%d",&tmp);
        if(tmp!=0) fgo[tmp-1] ++;
        if(tmp!=(n-1)) fgo[tmp+1] ++;
        fgo[tmp] ++;
    }
    int mak=0;
    for(i=0;i<114514;i++){
        if(fgo[i]>mak) mak = fgo[i];
    }
    printf("%d\n",mak);
}

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

int main()
{
   int n, cnt=0;
   //vector<int>v;
   cin>>n;
   for(int i=1;i<=n;i++)
   {
       int p;
       cin>>p;

       if(i%2 != 0 and p%2 != 0)
       {
           cnt++;
       }
   }
    cout<<cnt<<endl;
    return 0;
}


Measured memory_bytes: 3632
#include <cstdio>
using namespace std;
const int NN = 1e5 + 5, NM = 1e5 + 5;
int N, M;
struct E {
	int v, nxt, fx;
	E(int _v=0, int _nxt=0, int _fx=0) : v(_v), nxt(_nxt), fx(_fx) {}
};
struct Graph {
	int head[NN], totE;
	E edge[NM<<1];
	void AddE(int u, int v, int fx) {
		edge[++totE] = E(v, head[u], fx);
		head[u] = totE;
	}
} G;
int col[NN];
bool vis[NN];
int ys[] = {1, 2, 0};
int fanys[] = {2, 0, 1};
//0->1
//1->2
//2->0
int cnt[3], egnum = 0, cc;
bool Dfs(int u) {
	vis[u] = 1;
	cnt[col[u]] += 1;
	int hoho = 0;
	bool ret = 1;
	for (int p = G.head[u]; p; p = G.edge[p].nxt) {
		int v = G.edge[p].v;
		++hoho;
		if (vis[v]) {
			if (G.edge[p].fx == 1 && col[v] != ys[col[u]]) {
				ret = 0;
			}
			if (G.edge[p].fx == -1 && col[v] != fanys[col[u]]) {
				//注意第一个 G.edge[p].fx == -1的条件
				//以后限制能多写就多写 
				ret = 0;
			}
			continue ;
		}
		if (G.edge[p].fx == 1)
			col[v] = ys[col[u]];
		else col[v] = fanys[col[u]];
		if (!Dfs(v)) //记得这句话 
			ret = 0;
	}
	egnum += hoho;
	return ret;
}
int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= M; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		G.AddE(u, v, 1);
		G.AddE(v, u, -1);
	}
	long long ans = 0;
	for (int i = 1; i <= N; ++i) {
		if (!vis[i]) {
			cnt[0] = cnt[1] = cnt[2] = 0;
			egnum = 0; //初始化！ 
			bool jd = Dfs(i);
			int sum = cnt[0] + cnt[1] + cnt[2];
			//这里得 dfs完 cnt[0] cnt[1] cnt[2]才准确 
			if (!jd) ans += (long long)sum * sum;
			else if (!cnt[0] || !cnt[1] || !cnt[2]) ans += egnum / 2;
			else ans += (long long)cnt[0] * cnt[1] +
						(long long)cnt[1] * cnt[2] +
						(long long)cnt[2] * cnt[0];
		}
	}
	printf("%lld\n", ans);
	return 0;
}
/*
5 4
1 2
2 3
4 5
5 5
*/

Measured memory_bytes: 12664
#!/usr/bin/perl

my ($k) = map {$_ - 0} split(/\s+/o,<STDIN>);

my $a = $k + ( $k % 2 == 1 ? 1 : 0);

my $ki = $a / 2;
my $gu = int($k/2);

my $ans = $ki * $gu;
print "$ans\n";



Measured memory_bytes: 640
# -*- coding: utf-8 -*-

from collections import deque

N, M = map(int, input().split())
Ms = {i:set() for i in range(1, N + 1)}
for _ in range(M):
    a, b = map(int, input().split())
    Ms[a].add(b)
    Ms[b].add(a)

all = set(range(1, N + 1))
q = deque()
q.append((1, [1]))

ans = 0
while q:
    n, v = q.popleft()
    if set(v) == all:
        ans += 1
        continue
    for to in Ms[n]:
        if not to in v:
            q.append((to, v + [to]))

print(ans)


Measured memory_bytes: 4340
#include<stdio.h>
int main(){
  int n;
  int h[100];
  int i;
  scanf("%d",&n);
  for(i=0;i<n;i++) scanf("%d",&h[i]);
  int c=0;
  int t=0;
  for(i=0;i<n;i++){
    if(h[i]>t || h[i]==t){
      t=h[i];
      c++;
    }
  }
  printf("%d",c);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main()
{
	map<int, int> cnt;
	int t;
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		int m;
		cin >> m;
		cnt[m]++;
	}
	int ans = 0;

	for (auto u : cnt)
	{
		if (u.second >= u.first)
			ans += (u.second - u.first);
		else
			ans += u.second;
	}
	cout << ans << endl;

	return 0;
}
//8
//2 7 1 8 2 8 1 8

Measured memory_bytes: 8120
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define PF push_front
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double
#define pii pair<int,int>
#define pll pair<LL,LL>
#define vi vector<int>
#define vl vector<LL>
#define vii vector<vi>
#define vll vector<vl>

const double pi = 3.14159265358979323846264;
const int mod=1000000007;
LL ans,cnt,N,M,Q;

void f(vi& a,vi& b,vi& c,vi& d,vi& v,int nw){
    if(nw==N){
        cnt++;
        LL t=0;
        FOR(i,0,Q){
            if(v[b[i]]-v[a[i]]==c[i]){
                t+=d[i];
            }
        }
        if(ans<t){
            ans=t;
        }
        return;
    }
    int bf=1;
    if(nw!=0){
        bf=v[nw-1];
    }
    FOR(i,bf,M+1){
        v[nw]=i;
        f(a,b,c,d,v,nw+1);
    }
    return;
}

int main(){
	int n,m,q;
    ans=0;cnt=0;
    cin>>n>>m>>q;N=n;M=m;Q=q;
    vi a(q),b(q),c(q),d(q);
    FOR(i,0,q){
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        a[i]--;
        b[i]--;
    }
    vector<int> v(n,0);
    f(a,b,c,d,v,0);
    cerr<<cnt<<endl;
    cout<<ans<<endl;
}


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

int main(void){

    int A , B , C , D;
    cin >> A >> B >> C >> D;
    
    while(1){
        C -=B;
        if(C<=0){
            cout << "Yes";
            break;
        }
        A -= D;
         if(A<=0){
            cout << "No";
            break;
        }
    }

    return 0;
}

Measured memory_bytes: 3644
#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1e9
#define N 200005
using namespace std;
const ll mod=1000000007;
const ll INF=0x3f3f3f3f;
ll an[100005],x=1,ans=0,flag=0,n,i,len,a,b;
int main()
{
    while(scanf("%lld %lld %lld",&x,&a,&b)!=EOF)
    {
        if(b <= a+1)
            puts("delicious");
            else if(b <= a+x)
                puts("safe");
                else
                    puts("dangerous");
                }
    return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>

using namespace std;
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(),(x).end()
// int DP[MEM_SIZE][MEM_SIZE] = {0};
// int GMEM[MEM_SIZE][MEM_SIZE] = {0};
template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e << std::endl;}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class X> void DEBUG(X d, T e){if(DEBUG_OUT == false)return;std::cout <<d<<" ";DEBUG(e);};
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
template< typename T > using matrix = vector< vector< T > >;

//FUNCTION  

map< int, int > prime_factor(int n) {
  map< int, int > ret;
  for(int i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

void solve(void)
{
  int N;
  cin>>N;
  map<int,int> mp,mpp;
  for (int i = 2; i <= N; i++)
  {
    mpp = prime_factor(i);
    auto itr = mpp.begin();
    for (int i = 0; i < mpp.size(); i++)
    {
      mp[itr->first] += itr->second;
      itr++;
    }
  }
  int ANS = 1;
  for (int i = 0; i < mp.size(); i++)
  {
    static auto itr = mp.begin();
    ANS *= itr->second+1;
    ANS %= MOD;
    itr++;
    // DEBUG(ANS);
  }
  cout<<ANS<<endl;
  
  
  

  return;
}
int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(9);
  solve();

  return 0;
}


Measured memory_bytes: 256
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    ans=0
    n=int(input())
    l=list(map(int,input().split()))
    ans+=l[0]+l[-1]
    for i in range(n-2):
        ans+=min(l[i],l[i+1])
    print(ans)
resolve()

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

int main() {
string S,T;
cin >> S >> T;
  if(S.size() == T.size()-1){
    for (int i = 0; i < S.size(); i++){
            if(S.at(i) != T.at(i)){
                cout << "No" << endl;
                break;
            }
            else if (i == S.size()-1){
                cout << "Yes" << endl;
        }
    }
  }
  else {
    cout << "No" << endl;
  }
}


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

using namespace std;

int main() {
	double N = 0;
	double s = 0;
	int a = 0;
	double ans = 0;
	cin >> N;
	a = N;
	while (a > 0) {
		a = a - 2;
		s++;
	}
	cout << s / N;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std; 
typedef long long int ll;
typedef unsigned long long int ull;
const long long int m=pow(10,9)+7;

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll k;
    cin>>k;
    if (k%2==0||k%10==5){
        cout<<-1;
        return 0;
    }
    ll ans=1, r=7%k;
    while (r!=0){
        ans++;
        r=(r*10+7)%k;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
  int N, M;
  cin >> N >> M;
  ll x[N], y[N], z[N];
  for(int i=0; i<N; i++) cin >> x[i] >> y[i] >> z[i];
  
  ll ans = 0;
  ll S[N]; //0:正, 1:負
  
  
  for(ll k = 1; k>=-1; k-=2){
    for(ll l = 1; l>=-1; l-=2){
      for(ll m = 1; m>=-1; m-=2){
        for(ll i=0; i<N; i++) S[i] = k*x[i]+l*y[i]+m*z[i];
        sort(S, S+N, greater<ll>());
        ll tmpans = 0;
        for(int i=0; i<M; i++) tmpans += S[i];
//        cout << k << ", " << l << ", " << m << ": " << tmpans << endl;
        ans = max(ans, tmpans);
      }
    }
  }
  cout << ans << endl;
}

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

using namespace std;
using ll = long long;

using Field = vector<vector<int>>;
using Graph = vector<vector<int>>;
using VI = vector<int>;
using VC = vector<char>;
using PI = pair<int, int>;

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

const long long INF = 1LL<<60;
const int mod = 1000000007;

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; }

int N;
vector<ll> a;
vector<vector<ll>> dp;

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

    cin >> N;
    a.resize(N);
    REP(i, N) cin >> a.at(i);
    dp.assign(N+1, vector<ll>(N+1, 0));

    REP(i, N) dp.at(i).at(i) = 0;

    for (int len = 1; len <= N; len++) {
        for (int l = 0; l + len <= N; l++) {
            int r = l + len;
            if ((N - len) % 2 == 0) {
                dp.at(l).at(r) = max(dp.at(l + 1).at(r) + a.at(l), dp.at(l).at(r - 1) + a.at(r - 1));
            } else {
                dp.at(l).at(r) = min(dp.at(l + 1).at(r) - a.at(l), dp.at(l).at(r - 1) - a.at(r - 1));
            }
        }
    }

    cout << dp.at(0).at(N) << endl;

    return 0;
}

Measured memory_bytes: 72832
#include<cstdio>
int main()
{
	int x,a,b;
	b=0;
	a=0;
	scanf("%d",&x);
	a=x/500;
	x%=500;
	b=x/5;
	x=(a*1000)+(b*5);
	printf("%d\n",x);
	return 0;
}


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

int main(){
  int N, K, A, B, C;
  cin >> A >> B >> C;
/*
  vector<char> S(N);
  for(int i = 0; i < N; i++)
    cin >> S.at(i);
*/
  if(A+B>=C) cout << B+C << endl;
  else cout << B*2+A+1<< endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	string s;
	int a,b;
	cin>>a>>b;
	cin>>s;
	if(s[a]!='-')
	{
		cout<<"No"<<endl;
		return 0;
	}
	for(int i=0;i<s.size();i++)
	{
	   if(i==a)
	   	continue;
       if(s[i]>='0'&&s[i]<='9')
       {

       }
       else
       {
       	cout<<"No"<<endl;
		return 0;
       }
	}
	cout<<"Yes"<<endl;
	return 0;
}

Measured memory_bytes: 256
n = gets.to_i
a = gets.split.map(&:to_i)
h = Hash.new(0)
a.sort!.reverse!

ans = 0
a.each{|t|
  r = 1<<t.bit_length
  if h[t]>0
    h[t]-=1
    ans+=1
  else
    h[r-t]+=1
  end
}

p ans


Measured memory_bytes: 28900
from operator import mul
from functools import reduce

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

def cmb(n,r,mod):
  if r==0 or n==r:return 1
  r = min(n-r,r)
  ue = reduce(mul, range(n, n-r, -1))
  shita = reduce(mul, range(1,r+1))
  return (ue//shita)%mod

for i in range(1,k+1):
  try:print(cmb(n-k+1,i,mod)*cmb(k-1,k-i,mod)%mod)
  except:print(0)

Measured memory_bytes: 3944
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    int N, W;
    cin >> N >> W;
    vector<int> v( N ), w( N );
    REP( i, N )
    {
        cin >> v[ i ] >> w[ i ];
    }
    vector<vector<int>> dp( N + 1, vector<int>( W + 1 ) );
    dp[ 0 ][ 0 ] = 0;
    for( int i = 1; i <= N; i++ )
    {
        for( int j = 0; j <= W; j++ )
        {
            if( j - w[ i - 1 ] >= 0 )
            {
                dp[ i ][ j ] = max( dp[ i - 1 ][ j ], dp[ i - 1 ][ j - w[ i - 1 ] ] + v[ i - 1 ] );
            }
            else
            {
                dp[ i ][ j ] = dp[ i - 1 ][ j ];
            }
        }
    }
    cout << dp[ N ][ W ] << endl;
    return 0;
}

Measured memory_bytes: 6756
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int A, B;

    cin >> A >> B;

    //cout << "input is " << A << " and " << B << " ddd " << endl;
    int p, m, x;
    p = A + B;
    m = A-B;
    x = A*B;

    //cout << p << " " << m << " " << x << endl;
    
    int ans = max({p, m, x});
    
    cout<< ans << endl;



    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <complex>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const double EPS = 1e-8;
const double INF = 1e12;
#define EQ(n,m) (abs((n)-(m)) < EPS)
#define X real()
#define Y imag()
const double sqrt3 = sqrt(3);

typedef complex<double> P;
typedef vector<P> VP;
double dot(P a, P b){
    return (conj(a)*b).X;
}
double cross(P a, P b){
    return (conj(a)*b).Y;
}

P dleft(sqrt3, -1);
P dright(sqrt3, 1);
bool compBottom(const P& a, const P& b){
    return a.Y < b.Y;
}
bool compLeft(const P& a, const P& b){
    return sqrt3*a.X -a.Y < sqrt3*b.X -b.Y;
}
bool compRight(const P& a, const P& b){
    return sqrt3*a.X +a.Y < sqrt3*b.X +b.Y;
}
double get_trilength(const P &b, const P &l, const P &r){
    return 3 *( (r.Y +l.Y -2*b.Y)/sqrt3 +(r.X -l.X) );
}

int main(){
    while(1){
        int n;
        cin >> n;
        if(n==0) break;

        int k;
        cin >> k;
        VP pleft(n);
        for(int i=0; i<n; i++){
            double x,y;
            cin >> x >> y;
            pleft[i] = P(x, y);
        }
        VP pright = pleft;
        VP pbottom = pleft;
        sort(pleft.begin(), pleft.end(), compLeft);
        sort(pright.begin(), pright.end(), compRight);
        sort(pbottom.begin(), pbottom.end(), compBottom);

        double ans = INF;
        //下辺を決め打ち
        for(int b=0; b<=k; b++){
            int sum = 0;
            //左からちょうどn-k個入るようにl,rを初期化
            int r;
            for(r=0; r<n; r++){
                if(pright[r].Y +EPS > pbottom[b].Y){
                    sum++;
                }
                if(sum == n-k) break;
            }
            int l;
            for(l=0; l<n; l++){
                if(dot(pleft[l] -pright[r], dright) < EPS
                    && pleft[l].Y +EPS > pbottom[b].Y){
                    break;
                }
            }

            //右辺・左辺を順に右に動かして尺取り(逆だと取りこぼす)
            //左辺・右辺に点は1つしか乗らない!!!!
            for(; r<n; ){
                if(sum != n-k) break;
                ans = min(ans, get_trilength(pbottom[b], pleft[l], pright[r]));
                for(r++; r<n; r++){
                    if(dot(pright[r] -pleft[l], dleft) > -EPS
                        && pright[r].Y +EPS > pbottom[b].Y){
                        sum++;
                        break;
                    }
                }
                if(sum == n-k) break;
                for(l++; l<=k; l++){
                    if(dot(pleft[l] -pright[r], dright) < EPS
                        && pleft[l].Y +EPS > pbottom[b].Y){
                        sum--;
                        break;
                    }
                }
            }
        }
        cout << fixed << setprecision(10);
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 3596
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <chrono>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    cout << n - k + 1 << endl;
    return 0;
}


Measured memory_bytes: 256
import sys, math
from time import sleep
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from fractions import gcd
e = enumerate

sys.setrecursionlimit(10**7)
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [[float('inf')]*(H+1) for _ in range(N+1)]


for i, ab in e(AB):
    a, b = ab[0], ab[1]
    for j in range(H+1):

        if j==0:
            newval = b
        elif j%a==0:
            newval = j//a * b
        else:
            newval = (j//a+1) * b

        if j>=a:
            newval2 = dp[i][j-a] + b
        else:
            newval2 = float('inf')

        if j>=a:
            newval3 = dp[i+1][j-a] + b
        else:
            newval3 = float('inf')

        dp[i+1][j] = min(dp[i][j], newval, newval2, newval3)


print(dp[N][H])


Measured memory_bytes: 184560
#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<string>
#include<iostream>
#include<vector>
#include<cstdlib>
#include<stdio.h>
#include<cmath>
#include<limits>
#include<iomanip>

using namespace std;

template <class T> using V = vector<T>;

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;
}

const long long INF = 1LL << 60;

using ll = long long;
using db = long double;
using st = string;
using ch = char;
using bl = bool;
using vll = V<ll>;
using vpll =V<pair<ll,ll>>;
using vst = V<st>;
using vdb = V<db>;
using vch = V<ch>;
using vbl = V<bl>;
using graph = V<V<int>>;
using pq = priority_queue<ll>;



#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>=(b);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define M(a,b) max(a,b)
#define rM(a,b) min(a,b)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define co(a) cout<<a<<endl;
#define pb(a) push_back(a);



ll Sum(ll n) {
ll m=0;
  while(n){
    m+=n%10;
    n/=10;
  }
  return m;
}



const int MAX = 510000;
const int MOD = 1000000007;
 
long long fac[MAX], finv[MAX], inv[MAX];
 
void Comuse() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}


#define comuse Comuse()

ll combi(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll perm(int n,int k){
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] % MOD) % MOD;
}


ll lcm(ll a,ll b){
  ll n;
  n=a/gcd(a,b)*b;
  return n;
}


vll div(ll n){
  vll ret;
  for(ll i=1;i*i<=n;i++){
    if(n%i==0){
      ret.push_back(i);
      if(i*i!=n){
        ret.push_back(n/i);
      }
    }
  }
  SORT(ret);
  return (ret);
}

ll modpow(ll a,ll n,ll mod){
  ll ans=1;
  while(n>0){
    if(n&1){
      ans=ans*a%mod;
    }

    a=a*a%mod;
    
    n>>=1;
  }

  return ans;
}

void Solve();


const int MAX_N = 131072;
//segment tree 
int NN;
int seg[MAX_N*2-1];
void seguse(){
  for(int i=0;i<2*NN-1;i++){
    seg[i]=INT_MAX;
  }
}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(20)<<fixed;
  Solve();
}


/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/
//segtreeの葉の先頭の添え字はn-1
void Solve(){
  ll x;
  	cin>>x;
  FOR(i,x,INF){
    bool b=true;
    FOR(j,2,x){
      if(i%j==0){
        b=false;
        break;
      }
    }
    if(b){
      cout<<i<<"\n";
      return;
    }
  }
}

Measured memory_bytes: 256
# D
n = int(input())
a_list = list(map(int, input().split()))
L = 1000000007

inv_list = [0]
for i in range(1, n+2):
    inv_list.append(pow(i, L-2, L))

# find which duplicated
a_dict = dict()
for i in range(1, n+1):
    a_dict[i] = []
for i in range(n+1):
    a_dict[a_list[i]].append(i)
    if len(a_dict[a_list[i]]) == 2:
        dup = a_dict[a_list[i]]

res_list = [n]
k = (n + 1) - (dup[1] - dup[0] + 1)
ncr = n + 1
kcr = 1
for r in range(2, n+2):
    ncr *= (n+1) - (r-1)
    ncr = ncr % L
    ncr *= inv_list[r]
    ncr = ncr % L
    if k >= r-1:
        kcr *= k - (r-2)
        kcr = kcr % L
        kcr *= inv_list[r-1]
        kcr = kcr % L
    else:
        kcr = 0
    res_list.append((ncr-kcr) % L)
    
for r in range(n+1):
    print(res_list[r])

Measured memory_bytes: 39564
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<ld> com;
constexpr int inf = 1000010;
constexpr ll INF = 1000000000000000010;
constexpr ld eps = 1e-12;
constexpr ld pi = 3.141592653589793238;
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }

void GaussJordan(vector<vector<int>> &mat) {
	int n = mat.size();
	int m = mat[0].size();
	int st = 0;
	rep(j, m) {
		int idx = -1;
		for (int i = st; i < n; i++) {
			if (mat[i][j]) {
				if (idx == -1) {
					idx = i;
					continue;
				}
				rep(k, m) {
					mat[i][k] ^= mat[idx][k];
				}
			}
		}
		for (int i = st - 1; i >= 0; i--) {
			if (mat[i][j]) {
				if (idx == -1) continue;
				rep(k, m) {
					mat[i][k] ^= mat[idx][k];
				}
			}
		}
		if (idx != -1) {
			rep(k, m) {
				swap(mat[idx][k], mat[st][k]);
			}
			st++;
		}
	}
}

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

	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<ll> a(n);
		rep(i, n) cin >> a[i];
		string s;
		cin >> s;
		vector<vector<int>> mat(0, vector<int>(62));
		bool flag = false;
		for (int i = n - 1; i >= 0; i--) {
			if (s[i] == '0') {
				vector<int> v(62);
				rep(j, 62) v[j] = (a[i] >> j) & 1;
				reverse(all(v));
				mat.pb(v); 
				GaussJordan(mat);
			}
			else {
				vector<ll> base(mat.size());
				rep(j, mat.size()) {
					vector<int> v = mat[j];
					reverse(all(v));
					rep(k, 62) {
						base[j] |= (ll)v[k] << k;
					}
				}
				rep(j, mat.size()) {
					rep(k, 62) {
						if (mat[j][k]) {
							if ((a[i] >> (61 - k)) & 1) a[i] ^= base[j];
							break;
						}
					}
				}
				if (a[i]) {
					cout << "1\n";
					flag = true;
					break;
				}
			}
		}
		if (!flag) cout << "0\n";
	}
}

Measured memory_bytes: 3664