akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;
string O;
string E;
int main()
{
    int i,j;
    char ch[100];
    getline(cin,O);
    getline(cin,E);
    int x=O.size()+E.size();
    for(i = 0,j=0;i<x; i+=2,j++)
    {
        ch[i]=O[j];ch[i+1]=E[j];
    }
    ch[i]='\0';
    cout<<ch;
}


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

typedef long long ll;
//const int INF = 2e9;
//const ll INF = 9e18;
const int MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> D(N);
    for (int i=0;i<N;i++){
        cin >> D[i];
    }
    if (D[0] != 0) {
        cout << 0 << "\n";
        return 0;
    }
    for (int i=1;i<N;i++){
        if (D[i] <= 0) {
            cout << 0 << "\n";
            return 0;
        }
    }
    vector<int> num(N);
    int mx = 0;
    for (int i=0;i<N;i++) {
        num[D[i]]++;
        if (D[i] > mx) mx = D[i];
    }
    ll ans = 1;
    for (int i=1;i<=mx;i++){
        for (int j=0;j<num[i];j++){
            ans *= num[i-1];
            ans %= MOD;
        }
    }
    cout << ans << "\n";
}

Measured memory_bytes: 1024
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}

int sx,sy,tx,ty;
string ans;

void concat(char a, int n){
  rep(i,n){
    ans += a;
  }
}

int main(){
  cin >> sx >> sy >> tx >> ty;
  
  //1週目
  concat('R',tx - sx);
  concat('U',ty - sy);
  concat('L',tx - sx);
  concat('D',ty - sy);
  
  //2週目
  concat('L',1);
  concat('U',ty - sy + 1);
  concat('R',tx - sx + 1);
  concat('D',1);
  concat('R',1);
  concat('D',ty - sy + 1);
  concat('L',tx - sx + 1);
  concat('U',1);
  
  cout << ans;
  return 0;
}

Measured memory_bytes: 256
abc = input().split()
a = int(abc[0])
b = int(abc[1])
c = int(abc[2])
i = 1 
yakusu_ko = 0
for i in range(1,c+1):
    amari = c % i
    if amari ==0 and a <= i <= b:
        yakusu_ko +=1
print(yakusu_ko)




Measured memory_bytes: 5596
#pragma once
#include <stdio.h>
#include <sstream>
#include <string>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <limits>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define bit(x,v) ((ll)x << v)

const ll INF = 1000000007;
const int MAX = 210000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	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;
	}
}

// 二項係数計算
long long COM(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 gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int pr[100010];
void uini(int n) {
	for (size_t i = 0; i <= n; i++)
	{
		pr[i] = i;
	}
}

int parent(int x) {
	if (x == pr[x]) return x;
	return pr[x] = parent(pr[x]);
}

bool unit(int x, int y) {
	int px = parent(x);
	int py = parent(y);

	if (px == py) return false;
	if (px < py) {
		pr[py] = px;
	}
	else {
		pr[px] = py;
	}
	return true;
}

// res[i][c] := i 文字目以降で最初に文字 c が登場する index (存在しないときは n)
vector<vector<int> > calcNext(const string& S) {
	int n = (int)S.size();
	vector<vector<int> > res(n + 1, vector<int>(26, n));
	for (int i = n - 1; i >= 0; --i) {
		for (int j = 0; j < 26; ++j) res[i][j] = res[i + 1][j];
		res[i][S[i] - 'a'] = i;
	}
	return res;
}

void solv() {
	
	ll k, s;
	cin >> k >> s;
	s /= 1000;
	for (ll x = 0; x <= k; x++)
	{
		for (ll y = 0; y <= k; y++)
		{
			ll v = s - x * 10 - y * 5;
			if (v >= 0 && v + x + y == k) {
				cout << x << " " << y << " " << v << endl;
				return;
			}
		}
	}
	cout << -1 << " " << -1 << " " << -1 << endl;

}

int main() {
	//COMinit();
	solv();

	return 0;
}
 

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

using namespace std;
using ll = long long;

ll A[200006];
int N, K;

bool f(ll x) {
  int cnt = 0;
  for (int i= 0; i < N; i++) {
    if (A[i] <= x) continue;
    cnt += (int)ceil(1.0 * A[i] / x) - 1;
  }
  return cnt <= K;
}

int main() {
  cin >> N >> K;
  for (int i = 0; i < N; i++) cin >> A[i];
  ll ub = 1LL << 60;
  ll lb = 0;
  while (ub - lb > 1) {
    ll mid = (ub + lb) / 2;
    if (f(mid)) ub = mid;
    else lb = mid;
  }
  cout << ub << endl;
}

Measured memory_bytes: 5072
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        int[][] map = new int[h][w];
        int num = 0;
        for(int i=0; i<h; i++){
            String tmp = sc.next();
            for(int j=0; j<w; j++){
                if(tmp.charAt(j) == '.'){
                    map[i][j] = 0;
                    num++;
                }else{
                    map[i][j] = -1;
                }
            }
        }

        int dx[] = new int[]{1, 0, -1, 0};
        int dy[] = new int[]{0, 1, 0, -1};
        int[] pos = new int[3];
        Queue<int[]> next = new ArrayDeque<int[]>();
        pos[0] = 0;
        pos[1] = 0;
        map[0][0] = 1;
        next.add(pos);

        while(!next.isEmpty()){
            int[] mpos = next.poll();
            int mx = mpos[0];
            int my = mpos[1];
            
            for(int i=0; i<4; i++){
                int nx = mx+dx[i];
                int ny = my+dy[i];
                if(nx >= 0 && nx < h && ny >= 0 && ny < w){
                    if(map[nx][ny] == 0){
                        map[nx][ny] = map[mx][my] + 1;
                        next.add(new int[]{nx, ny});
                    }
                }
            }
        }

        if(map[h-1][w-1] == 0){
            System.out.println(-1);
        }else{
            System.out.println(num - map[h-1][w-1]);
        }
    }   
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, int> PILL;
typedef pair<ll, ll> PLL;

const int MAX_N = 2e5+5;
const int M = 1e6;
const ll INF = (ll)(1e18);
const int inf = 1e9;
const ll MOD = 1000000007LL;

void solve() {

}



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

    ll a, b, k;
    cin >> a >> b >> k;

    ll tmp = min(a, k);
    a -= tmp;
    k -= tmp;

    b -= k;
    b = max(0LL, b);

    cout << a << " " << b;








    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <tuple>
#include <set>
#include <functional>

using namespace std;

typedef long long ll;

class Nums {
public:
    int a, b, c;
    Nums(){}
    Nums(ll _a, ll _b, ll _c) {
        a = _a;
        b = _b;
        c = _c;
    }
    bool operator<(const Nums& o) const {
        if (a != o.a) return a < o.a;
        if (b != o.b) return b < o.b;
        return c < o.c;
    }
};

int main() {
    ll k;
    ll x, y, z;
    cin >> x >> y >> z >> k;

    vector<ll> A(x), B(y), C(z);

    for (int i = 0; i < x; i++)
        cin >> A[i];
    for (int i = 0; i < y; i++)
        cin >> B[i];
    for (int i = 0; i < z; i++)
        cin >> C[i];

    sort(A.begin(), A.end(), greater<ll>());
    sort(B.begin(), B.end(), greater<ll>());
    sort(C.begin(), C.end(), greater<ll>());

    priority_queue<pair<ll, Nums>> Q;
    Q.push(make_pair(A[0] + B[0] + C[0], Nums(0, 0, 0)));

    set<Nums> memo;

    vector<ll> ans;

    while (ans.size() != k) {
        auto now = Q.top(); Q.pop();
        ll aa = now.second.a, bb = now.second.b, cc = now.second.c;
        ans.push_back(now.first);

        if (aa != x - 1) {
            ll a = aa + 1;
            ll b = bb;
            ll c = cc;
            if (memo.find(Nums(a, b, c)) == memo.end()) {
                Q.push(make_pair(A[a] + B[b] + C[c], Nums(a, b, c)));
                memo.insert(Nums(a, b, c));
            }
        }
        if (bb != y - 1) {
            ll a = aa;
            ll b = bb + 1;
            ll c = cc;
            if (memo.find(Nums(a, b, c)) == memo.end()) {
                Q.push(make_pair(A[a] + B[b] + C[c], Nums(a, b, c)));
                memo.insert(Nums(a, b, c));
            }
        }
        if (cc != z - 1) {
            ll a = aa;
            ll b = bb;
            ll c = cc + 1;
            if (memo.find(Nums(a, b, c)) == memo.end()) {
                Q.push(make_pair(A[a] + B[b] + C[c], Nums(a, b, c)));
                memo.insert(Nums(a, b, c));
            }
        }
    }
    for (int i = 0; i < k; i++) {
        cout << ans[i] << endl;
    }


    return 0;
}


Measured memory_bytes: 896
#include<stdio.h>
int main()
{
  int x,y,temp;
  scanf("%d%d",&x,&y);
  while(1)
    {
      temp=x%y;
      x=y;
      y=temp;
      if(temp==0)break;
      
    }
  printf("%d\n",x);
  return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
#define PI 3.14159265358979323846264338327
#define NUM 1000000007
#define ss second
#define ff first
using namespace std;
struct x{
	int id, p;
	string s;
	bool operator<(const x& b) const{
		if (s != b.s)
			return s < b.s;
		return p > b.p;
	}
} r[101];
int n;
int main(){
	ios::sync_with_stdio(0);
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> ws >> r[i].s >> r[i].p;
		r[i].id = i + 1;
	}
	sort(r, r + n);	
	for (int i = 0; i < n; i++)
		cout << r[i].id << "\n";
	return 0;
}


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

using namespace std;

#define ar array
#define ll long long

const int MAX_N = 1e5 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;



void solve() {
    int n; cin >> n;
    ar<int,2> a[n];
    for (int i = 0; i < n; i++) cin >> a[i][0] >> a[i][1];
    for (int i = 0; i < n; i++) {
        bool ok = true;
        for (int j = i; j < i + 3; j++) {
            ok &= (a[j][0] == a[j][1]);
        }
        if (ok) {
            cout << "Yes";
            return;
        }
    }
    cout << "No";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int tc; tc = 1;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t  << ": ";
        solve();
    }
}

Measured memory_bytes: 3648
import math
import itertools
N = int(input())
cities = [tuple(map(int, input().split())) for _ in range(N)]
# print(cities)


def dist(ci, cj):
    return ((ci[0]-cj[0])**2+(ci[1]-cj[1])**2)**0.5


ans = 0
for p in itertools.permutations(range(N), N):
    for i in range(N-1):
        ans += dist(cities[p[i]], cities[p[i+1]])
print(ans/math.factorial(N))


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

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

    int a, b;
    cin >> a >> b;

    bool ans = true;
    if (a < 1 || a > 9 || b < 1 || b > 9)
        ans = false;

    if (ans) cout << a * b << '\n';
    else cout << -1 << '\n';
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
int n;
int a[100'001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    long long ans = 0;
    for(int i = 1; i+1 <= n; i++) {
        if(a[i] == i && a[i+1] == i+1) {
            swap(a[i], a[i+1]);
            ans++;
        }
    }
    for(int i = 1; i <= n; i++) {
        if(a[i] == i) {
            swap(a[i], i == 1 ? a[i+1] : a[i-1]);
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
import java.io.IOException;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		new Main().run();
	}

	private void run() throws IOException {
		Scanner scanner = new Scanner(System.in);
		while (true) {
			m = scanner.nextInt();
			n = scanner.nextInt();
			if ((m | n) == 0)
				break;
			M = new HashMap<Integer, Integer>();
			h = 1;
			a = new int[n][m];
			Y = new int[24];
			X = new int[24];
			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++) {
					int t = scanner.nextInt();
					if (t == 0) {
						a[i][j] = -1;
					} else if (t == 1) {
						Y[h] = i;
						X[h] = j;
						a[i][j] = h++;
					} else {
						Y[0] = i;
						X[0] = j;
						a[i][j] = 0;
					}
				}
			System.out.println(slove(0, 1));
		}
	}

	private int slove(int cur, int bit) {
		int k = cur << 24 | bit;
		if (M.containsKey(k))
			return M.get(k);
		int res = 0;
		for (int[] mo : move) {
			int y = Y[cur];
			int x = X[cur];
			while (true) {
				y += mo[0];
				x += mo[1];
				if (!isOK(y, x))
					break;
				if (a[y][x] == 0)
					if (Integer.bitCount(bit) == h) {
						return res + 1;
					}
				if (a[y][x] >= 1) {
					if ((bit >> a[y][x] & 1) == 1)
						continue;
					res += slove(a[y][x], bit | 1 << a[y][x]);
					break;
				}
			}
		}
		M.put(k, res);
		return res;
	}

	private boolean isOK(int y, int x) {
		if (0 <= y && y < n && 0 <= x && x < m)
			return true;
		return false;
	}

	int m, n, h;
	int[] Y, X;
	int[][] a;
	int[][] move = { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };
	Map<Integer, Integer> M;
}

Measured memory_bytes: 180660
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
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 (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll n, k;
    cin >> n >> k;
    ll ans = 0;
    if (k == 0) {
        ans = n*n;
    } else {
        for (ll b = k+1; b <= n; ++b) {
            ans += ((n + 1) / b) * (b - k) + max(0LL, (n + 1) % b - k);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
while 1:
    n,r = map(int,input().split())
    if n==0: break
    a = [n-i for i in range(n)]
    for i in range(r):
        p,c = map(int,input().split())
        a = a[p-1:p-1+c] + a[:p-1] + a[p-1+c:]
    print(a[0])
    


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

int main(void){
  int n;
  cin >> n;
  char s, HinaArare[4] = {};
  for(int i = 0; i < n; i++){
    cin >> s;
    if(s == 'P') HinaArare[0] = 1;
    if(s == 'W') HinaArare[1] = 1;
    if(s == 'G') HinaArare[2] = 1;
    if(s == 'Y') HinaArare[3] = 1;
  }
  if(HinaArare[3]) cout << "Four" << endl;
  else cout << "Three" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	long long int haiba;
	char k;
	long long int pro=0,proplus=0;
	scanf("%lld",&haiba);
	for(int i=1;i<=haiba;i++)
	{
		cin>>k;
		if(k=='I')
		{
			proplus+=1;
		}
		else
		if(k=='D')
		{
			proplus-=1;
		}
		pro=max(proplus,pro);
		
	}
	printf("%lld\n",pro);
	return 0;
}

Measured memory_bytes: 256
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<climits>

/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/

using namespace std;

#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007


signed main(){
    int X,A;
    cin>>X>>A;
    cout<<(X>=A?10:0)<<endl;
}


Measured memory_bytes: 3188
import java.math.BigInteger;
import java.util.Scanner;

public class Main
{
	public static void main(String[] args)
	{
		Scanner in=new Scanner(System.in);
		String s=in.next();
		char a[]=s.toCharArray();
		int b[]=new int[5];
		for(int i=0;i<4;i++)
			b[i]=a[i]-'0';
		boolean flag=true;
		for(int i=0;i<=1 && flag;i++)
			for(int j=0;j<=1 && flag;j++)
				for(int k=0;k<=1 && flag;k++)
				{
					int res=b[0];
					if(i==0)res+=b[1];
					if(i==1)res-=b[1];
					if(j==0)res+=b[2];
					if(j==1)res-=b[2];
					if(k==0)res+=b[3];
					if(k==1)res-=b[3];
					if(res==7)
					{
						System.out.print(b[0]);
						if(i==0)System.out.print("+");
						else System.out.print("-");
						System.out.print(b[1]);
						if(j==0)System.out.print("+");
						else System.out.print("-");
						System.out.print(b[2]);
						if(k==0)System.out.print("+");
						else System.out.print("-");
						System.out.print(b[3]);
						flag=false;
					}
				}
		System.out.print("=7");
		System.out.println();
	}
}

Measured memory_bytes: 24916
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
typedef vector<string> vs;
typedef vector<int> vi;

int N;
vector<char> cvec;
vs str;

// 0 -> ??????, 1 -> ??£?§£, -1 -> ??????
int check()
{
	rep(i, 0, N) if (str[i][0] == '0' && str[i].length() != 1) return -1;

	int up = 0;
	rep(j, 0, str[N - 1].length())
	{
		int left = up;
		rep(i, 0, N-1)
		{
			int jj = str[i].length() - 1 - j;
			if (jj < 0) continue;
			if ('0' <= str[i][jj] && str[i][jj] <= '9')
				left += str[i][jj] - '0';
			else
				return 0;
		}

		int jj = str[N - 1].length() - 1 - j;
		if (!('0' <= str[N - 1][jj] && str[N - 1][jj] <= '9')) return 0;
		
		up = left / 10;
		left %= 10;

		if (left != str[N - 1][jj] - '0') return -1;
	}

	if (up == 0)
	{
		//cout << " [ ";
		//rep(i, 0, N) cout << str[i] << " ";
		//cout << " ]" << endl;
		return 1;
	}
	else
		return -1;
}

int dfs(int depth, int mask)
{
	int cret = check();

	//rep(i, 0, N) cout << str[i] << " |";
	//cout << " ->" << cret << endl;


	if (cret < 0) return 0;
	if (cret == 1) return 1;

	int ret = 0;
	rep(i, 0, 10)
	{
		if (mask & (1 << i)) continue;
		rep(j, 0, N) rep(k, 0, str[j].length()) if (str[j][k] == cvec[depth]) str[j][k] = '0' + i;
		ret += dfs(depth + 1, mask + (1 << i));
		rep(j, 0, N) rep(k, 0, str[j].length()) if (str[j][k] == '0' + i) str[j][k] = cvec[depth];
	}
	return ret;
}

int solve()
{
	cvec.clear();
	str.clear();

	rep(i, 0, N) { string s; cin >> s; str.push_back(s); }
	rep(i, 0, N - 1) if (str[N - 1].length() < str[i].length()) return 0;

	rep(j, 0, str[N-1].length()) rep(i, 0, N)
	{
		int jj = str[i].length() - 1 - j;
		if (jj < 0) continue;
		if (find(cvec.begin(), cvec.end(), str[i][jj]) == cvec.end()) cvec.push_back(str[i][jj]);
	}
	return dfs(0, 0);
}

int main()
{
	while (1)
	{
		cin >> N;
		if (N == 0) return 0;
		cout << solve() << endl;
	}
}

Measured memory_bytes: 3104
#include<iostream>
#include<algorithm>
#include<cmath>
#define MAX 100100
typedef unsigned long long LL;
const LL Max = LL(1e18);
using namespace std;
LL a[MAX], ans = 1;
int main() {
	int n;
	cin >> n;
	int flag = 1;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (a[i] == 0)
			flag = 0;
	}
	if (!flag) {
		cout << "0" << endl;
	}
	else {
		ans = 1;
		for (int i = 1; i <= n; i++) {
			if (ans*a[i] > Max || Max / ans < a[i]) {
				flag = 0;
				break;
			}
			ans *= a[i];
		}
		if (flag)
			cout << ans << endl;
		else
			cout << "-1" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 4336
#include <cstdio>
using namespace std;
long long int gcd(long long int m,long long int n)
{
	if (n == 0)
		return m;
	return gcd(n,m % n);
}

int main()
{
	long long int a, b;
	while (scanf("%lld %lld",&a,&b) != EOF) {
		if (a >= b)
			printf("%lld %lld\n",gcd(a, b),a*b/ gcd(a, b));
		else
			printf("%lld %lld\n", gcd(b, a), a*b / gcd(b, a));
	}
	return 0;
}

Measured memory_bytes: 1024
from collections import deque

def bfs(maze,dist,sy,sx):
    #キューオブジェクトの生成
    queue = deque([[sy,sx]])
    #スタート地点のdistを0にする
    dist[sy][sx] = 0
    #mdを初期化
    md = 0
    while queue:
        #先頭から要素を一つ削除する
        y,x = queue.popleft()
        for j, k in ([1,0],[-1,0],[0,1],[0,-1]):
            new_y, new_x = y+j, x+k
            #迷路内に収まっているか確かめる
            if 0 <= new_y < H and 0 <= new_x < W:
                #new_y,new_xが道かどうか確かめる
                #またnew_y,new_xが初めて通る道かを確かめる
                if maze[new_y][new_x] == "." and dist[new_y][new_x] == -1:
                    dist[new_y][new_x] = dist[y][x] + 1
                    queue.append([new_y, new_x])
                    md = max(dist[new_y][new_x],md)
    return md
H, W = map(int,input().split())
maze = [input() for i in range(H)]

ans = 0
for i in range(H):
    for j in range(W):
        dist = [[-1]*W for k in range(H)]
        #i,jをスタートの位置としているから壁じゃないか確認
        if maze[i][j] != "#":
            a = bfs(maze,dist,i,j)
            ans = max(a,ans)
print(ans)

Measured memory_bytes: 3316
H,W=map(int,input().split())
lst=[[] for f in range(H)]
ans=[[0 for e in range(W)] for f in range(H)]
for i in range(H):
 lst[i]=[(d) for d in input()]
for i in range(1,H):
 if lst[i][0]!=lst[i-1][0]:
  ans[i][0]=ans[i-1][0]+1
 else:
  ans[i][0]=ans[i-1][0]
for j in range(1,W):
 if lst[0][j]!=lst[0][j-1]:
  ans[0][j]=ans[0][j-1]+1
 else:
  ans[0][j]=ans[0][j-1]
for i in range(1,H):
 for j in range(1,W):
  if lst[i][j]==lst[i][j-1]:
   a=0
  else:
   a=1
  if lst[i][j]==lst[i-1][j]:
   b=0
  else:
   b=1
  ans[i][j]=min(ans[i][j-1]+a,ans[i-1][j]+b)
if lst[0][0]=="."and lst[H-1][W-1]==".":
 print((ans[H-1][W-1])//2)
elif lst[0][0]=="#"and lst[H-1][W-1]=="#":
 print((ans[H-1][W-1]+2)//2)
else:
 print((ans[H-1][W-1]+1)//2)

Measured memory_bytes: 42352
import qualified Data.Vector.Unboxed as V
import Data.Array.IArray (listArray, accumArray, (!))
import Data.Array.MArray
import Data.Array.ST (STUArray, runSTUArray)
import Data.Array.Unboxed (UArray)
import Data.List (sortOn, sortBy, unfoldr, partition)
import Data.Char (isSpace)
import Control.Monad.ST (ST)
import Control.Monad.Trans.State (StateT(..))
import qualified Data.ByteString.Char8 as B

-- utility functions

--   Input functions
readInt = B.readInt . B.dropWhile isSpace

readInts :: Int -> B.ByteString -> [Int]
readInts n = take n . unfoldr readInt

readIntsV :: Int -> B.ByteString -> V.Vector Int
readIntsV n = V.unfoldrN n readInt

readIntsA :: Int -> B.ByteString -> UArray Int Int
readIntsA n bs = runSTUArray $ do
  arr <- newArray_ (0,n-1)
  go arr 0 bs
  return arr
  where
    go :: STUArray s Int Int -> Int -> B.ByteString -> ST s ()
    go arr i bs
      | i==n = return ()
      | otherwise = do
        let Just (x,bs') = readInt bs
        writeArray arr i x
        go arr (i+1) bs'

readTsV :: Int -> B.ByteString -> V.Vector (Int,Int)
readTsV n = V.unfoldrN n $ runStateT ((,) <$> StateT readInt <*> StateT readInt)

readTs :: Int -> B.ByteString -> [(Int,Int)]
readTs n = take n . unfoldr readT where
  readT = runStateT ((,) <$> StateT readInt <*> StateT readInt)

-- main

main = do
  xs <- map read . words <$> getContents
  let ys = take 5 xs
  let k = xs !! 5
  if maximum ys - minimum ys <= k then
    putStrLn "Yay!"
  else
    putStrLn ":("


Measured memory_bytes: 508
#include <stdio.h>

int F[45];
int fib(int);

main() {
  int n, i;

  F[0] = 1;
  F[1] = 1;

  scanf("%d", &n);

  for(i = 2; i < 45; i++) {
    F[i] = 0;
  }

  for(i = 2; i <= n; i++) {
    F[i] = fib(i);
  }

  printf("%d\n", F[n]);
  return 0;
}

int fib(int n) {
  if(n == 0 || n == 1) {
    return 1;
  }
  else {
    return F[n - 1] + F[n - 2];
  }
}

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

int main() {
	int S, A[4]; cin >> S;
	A[3]=S%10;
	A[2]=(S%100)/10;
	A[1]=(S%1000)/100;
	A[0]=S/1000;
	int e[3];
	for(int i=0; i<8; ++i){
	    e[0]=i%2;
	    e[1]=(i%4)/2;
	    e[2]=i/4;
	    int su=A[0];
	    for(int j=0; j<3; ++j){
	     if(e[j]) su += A[j+1];
	     else su -= A[j+1];
	    }
	    if(su==7) break;
	}
	cout << A[0];
	for(int i=0; i<3; ++i){
	    if(e[i]) cout << '+' << A[i+1];
	    else cout << '-' << A[i+1];
	}
	cout << "=7" << endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        int[] dp = new int[N+1];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= N ; i++) {

            if(i==2){
                dp[i]=dp[i-1] + Math.abs(arr[i-1]-arr[i-2]);
            }else{
                dp[i]= Math.min(
                        dp[i-1] + Math.abs(arr[i-1]-arr[i-2]),
                        dp[i-2] + Math.abs(arr[i-1]-arr[i-3])
                );
            }

        }
        System.out.println(dp[N]);


    }
}

Measured memory_bytes: 53304
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<algorithm>
#include<cstdio>
#include<stdio.h>

#define pi 3.14159265358979323846
#define max max_element
#define min min_element
using namespace std;

template<typename T>
T gcd(T a, T b) {
	return b ? gcd(b, a % b) : a;
}
template<typename T>
T lcm(T a, T b) {
	return a * b / gcd(a, b);
}


/*char r[4];
char op[3];
int sum = 0;
scanf("%s", r);
for (int i = 0;i < 4;i++) {
	yaju[i] = r[i] - '0';
}
*/

int main() {
	int N, M,k,ans=0;
	cin >> N >> M;
	vector<vector<int>> A(N);
	for (int i = 0;i < N;i++) {
		cin >> k;
		A[i].resize(M);
		for (int j = 0;j < k;j++) {
			cin >> A[i][j];
		}
	}
	for (int j = 1;j <= M;j++) {
		bool ok = false;
		for (int a = 0;a < N;a++) {
			for (int t = 0;t<A[a].size();t++) {
				if (j == A[a][t]) ok = true;
			}
			if (!ok) break;
			ok = false;
			if (a == N - 1) ans++;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
#include <math.h> 


int main(){
    string S;
    //vector<int> vec(N);
    cin >> S;
    
    
    if(S[2] == S[3] && S[4]==S[5]){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }


    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); ++(i))
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
typedef complex<double> xy_t;
typedef vector<lint> poly;
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T>bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}

const lint mod = 1e9+7;
const lint INF = mod*mod;
const int MAX =100010;

int n, a[MAX];
vector<int> G[MAX];

int dfs(int v){
    vector<int> d;
    for(int nv: G[v]) d.push_back(dfs(nv));
    sort(d.begin(), d.end(), greater<>());
    int ret=0;
    rep(i, G[v].size()) chmax(ret, d[i]+i+1);
    return ret;
}

int main(){
    scanf("%d", &n);
    For(i, 1, n){
        scanf("%d", &a[i]);
        --a[i];
        G[a[i]].push_back(i);
    }
    printf("%d\n", dfs(0));
}

Measured memory_bytes: 15488
#include <iostream>
#include <string>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    int a[n];
    for(int i=0;i<n;++i){
        cin>>a[i];
    }
    for(int i=2;i<=m;++i){
        for(int j=0;j+1<n;++j){
            if(a[j]%i>a[j+1]%i){
                int b=a[j];
                a[j]=a[j+1];
                a[j+1]=b;
            }
        }
    }
    for(int i=0;i<n;++i){
        cout<<a[i]<<endl;
    }
}



Measured memory_bytes: 3132
s = list(map(len,input().split("T")))
x = s[::2]
y = s[1::2]
gx,gy = map(int,input().split())
if sum(x) < abs(gx) or sum(y) < abs(gy):
  print("No")
  exit(0)
dpx = [0]*(len(x)+1)
dpy = [0]*(len(y)+1)
dpx[0] = set([0])
dpy[0] = set([0])
for i in range(1,len(x)+1):
  s1 = set([v + x[i-1] for v in dpx[i-1]])
  s2 = set([v - x[i-1] for v in dpx[i-1]])
  if i == 1:
    dpx[i] = s1
  else:
    dpx[i] = s1|s2
for i in range(1,len(y)+1):
  s1 = set([v + y[i-1] for v in dpy[i-1]])
  s2 = set([v - y[i-1] for v in dpy[i-1]])
  dpy[i] = s1|s2
if gx in dpx[-1] and gy in dpy[-1]:
  print("Yes")
else:
  print("No")


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

int main() {
  int n;
  string s;
  cin >> n >> s;

  int min_v = 0;
  int cur = 0;
  rep(i, n) {
    cur += (s[i] == '(' ? +1 : -1);
    min_v = min(min_v, cur);
  }

  string ss1, ss2;
  rep(i, -min_v) ss1.push_back('(');
  rep(i, cur - min_v) ss2.push_back(')');
  s = ss1 + s + ss2;
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 3604
#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 <unordered_map>
#include <unordered_set>
# define ll int64_t
# define rep(i,n) for(ll i=0;i<n;i++)
# define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define mod 1000000007
# define PI 3.141592653589793
# define vec vector
#define dump(x) cerr<<#x<<"="<<x<<endl
using namespace std;

bool compare_by_b(pair<string,ll> a,pair<string,ll> b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

bool my_compare(pair<string,ll> a,pair<string,ll> b){
    if(a.first != b.first) return a.first<b.first;
    if(a.second != b.second) return a.second>b.second;
    else return true;
}

ll factorial(ll n){
    ll x=1;
    rrep(i,n) (x*=i)%=mod;
    return x;
}

ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b,a%b));
}

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

const ll limit=50;
ll n,m,a[limit],b[limit];

bool graph[limit][limit],visited[limit];

void dfs(ll v){
    visited[v]=true;
    rep(v2,n){
        if(graph[v][v2]==false) continue;
        if(visited[v2]==true) continue;
        dfs(v2);
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin>>n>>m;
    
    rep(i,m){
        cin>>a[i]>>b[i]; a[i]--; b[i]--;
        graph[a[i]][b[i]]=graph[b[i]][a[i]]=true;
    }
    ll ans=0;
    
    rep(i,m){
        graph[a[i]][b[i]]=graph[b[i]][a[i]]=false;
        rep(j,n) visited[j]=false;
        dfs(0);
        
        bool bridge=false;
        rep(j,n) if(visited[j]==false) bridge=true;
        if(bridge) ans++;
        graph[a[i]][b[i]]=graph[b[i]][a[i]]=true;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
long long int power(int a,int b)
{
    if(b==0)
        return 1;
    long long int k=power(a,b/2);
    if(b%2==0)
        return ((k%M)*(k%M))%M;
    else
        return ((k%M)*(k%M)*(a%M))%M;
}
long long int fact(long long int n)
{
    if(n==1 || n==0)
        return 1;
    else
        return ((n%M)*(fact(n-1)%M))%M;

}
int div(int n)
{  int c=0;
    for(int i=1;i<sqrt(n);i++)
    {
        if(n%i==0)
        {
          c++;
        }
    }
    c=c*2;
    if(pow(sqrt(n),2)==(sqrt(n)*sqrt(n)))
        c++;
    return  c;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     #ifndef ONLINE_JUDGE
 
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
   #endif
   int x,y,z;
   cin>>x>>y>>z;
   int n=(x-z)/(z+y);
   cout<<n;



 return 0;
}








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

using namespace std;


int main()
{
    long N, T, A, min = LONG_MAX, tmp, index;

    cin >> N >> T >> A;

    for (int i = 1; i < N+1; i++) {
        cin >> tmp;
        if (min > abs(A*1000 - (T*1000-tmp*6))) {
            min = abs(A*1000 - (T*1000-tmp*6));
            index = i;
        }
    }

    cout << index << endl;
    
    return 0;   
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;
constexpr char name[5]{'A', 'B', 'C', 'D', 'E'};

int main() {
    while (true) {
        int n_max = 0, name_idx;
        for (int i = 0; i < 5; ++i) {
            int a, p;
            cin >> a >> p;
            const int sum = a + p;
            if (sum == 0)
                exit(0);
            else if (sum > n_max) {
                n_max = sum;
                name_idx = i;
            }
        }
        cout << name[name_idx] << ' ' << n_max << endl;
    }
}


Measured memory_bytes: 2984
#include<stdio.h>
#include<cstdio>
#include<cmath>
using namespace std;

int main() {
  int N;
  scanf("%d", &N);
  int t[N+1], x[N+1], y[N+1];
  t[0] = 0; x[0] = 0; y[0] = 0;
  for (int i=1 ; i<N+1 ; i++) {
    scanf("%d %d %d", &t[i], &x[i], &y[i]);
  }
  int dt, dx, dy;
  for (int i=0 ; i<N ; i++ ) {
    dt = t[i+1] - t[i];
    dx = abs(x[i+1] - x[i]);
    dy = abs(y[i+1] - y[i]);
    if (dt < dx + dy || dt%2 != (dx+dy)%2) {
      printf("No\n");
      return 0;
    }
  }
  printf("Yes\n");
}

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

int main(){
	string S;
	cin >> S;
	int l=S.size()/2-1;
	for(;l>0;l--){
		bool flag=true;
		for(int i=0;i<l;i++)if(S[i]!=S[i+l])flag=false;
		if(flag){
			cout << l*2 << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
  
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
  
using namespace std;
  
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
  
const int INF=1<<29;
const double EPS=1e-9;
  
const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};

const int mod = 1e9 + 7;


int main() {
  int N;
  cin >> N;
  vector<vector<ll>> A(N, vector<ll>(N, 0));
  ll ans = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cin >> A[i][j];
    }
  }

  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      ans += A[i][j];
      for (int k = 0; k < N; k++) {
        if (i == k || j == k) continue;
        if (A[i][k] + A[k][j] < A[i][j]) {
          cout << "-1" << endl;
          return 0;
        }
      }
    }
  }
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      for (int k = 0; k < N; k++) {
        if (i == k || j == k) continue;
        if (A[i][k] + A[k][j] == A[i][j]) {
          ans -= A[i][j];
          break;
        }
      }
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<ll> vi;
typedef vector<ll> vl;
typedef pair<ll,ll> pii;
typedef pair<ll,ll> pll;
typedef map<ll,ll> mii;
typedef map<ll,ll> mll;
typedef vector<pii> vii;
typedef vector<pll> vll;
#define fi first
#define se second
#define pi 3.141592653589793
#define ld long double
#define mod 998244353ll
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.begin(), v.end(), greater<ll>()
#define tc ll t;cin>>t;while(t--)
#define pqmax priority_queue<ll>
#define pqmin priority_queue<ll,vi,greater<ll>>
#define fio ios_base::sync_with_stdio(0), cin.tie(NULL)
#define tc_g ll tt;cin>>tt;for(ll ti=1;ti<=tt;ti++)#define case_g "Case #"<<ti<<": "
#define Debug(x) cout << x << "\n"
using namespace std;
vl graph[100005];
vector<bool> visited(100005);
void dfs(ll root) {
    for(auto x: graph[root]) {
        if(!visited[x]) {
            visited[x] = true;
            dfs(x);
        }
    }
    return;
}
int main() {
    ll n, m, from, to;
    cin >> n >> m;
    for(int i = 0; i < m; ++i) {
        cin >> from >> to;
        graph[from].pb(to);
        graph[to].pb(from);
    }
    ll ans = 0;
    for(int i = 1; i <= n; ++i) {
        if(!visited[i]) {
            visited[i] = true;
            dfs(i);
            ++ans;
        }
    }
    cout << ans - 1;
}


Measured memory_bytes: 10736
/*
これを入れて実行
g++ code.cpp
./a.out
 */

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <tuple>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef long double ld;

int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};

const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;

bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}

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

ll nCm(ll n, ll m){
    if(m == 0 || m == n){
        return 1;
    } else if(m == 1){
        return n;
    }
    return (nCm(n - 1, m) + nCm(n - 1, m - 1));
}

//-----------------------ここから-----------

int main(void){
    int n, k;
    cin >> n >> k;
    vector<int> x(n);
    for(int i = 0; i < n; i++){
        cin >> x[i];
    }

    int ans = 0;
    for(int i = 0; i < n; i++){
        ans += min(x[i], abs(k - x[i])) * 2;
    }

    cout << ans << endl;
}

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

template<long long mod>
class modint{
private:
  long long a;
public:
  constexpr modint(const long long x = 0) noexcept : a(x%mod) {}
  constexpr long long& value() noexcept { return a; }
  constexpr const long long& value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint& operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if(a >= mod) a -= mod;
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if(a < rhs.a) a += mod;
    a -= rhs.a;
    return *this;
  }
  constexpr modint& operator*=(const modint rhs) noexcept {
    a = a*rhs.a%mod;
    return *this;
  }
  constexpr modint& operator/=(modint rhs) noexcept {
    long long k = mod-2;
    while(k > 0){
      if(k&1){
        *this *= rhs;
      }
      rhs *= rhs;
      k /= 2;
    }
    return *this;
  }
  friend ostream& operator<<(ostream &os, const modint &X){
    return os << X.a;
  }
  friend istream& operator>>(istream &is, modint &X){
    is >> X.a;
    X.a %= mod;
    if(X.a < 0) X.a += mod;
    return is;
  }
};

template<typename T>
struct CumSum{
private:
  size_t size;
  vector<T> data;
public:
  CumSum(vector<T> dat){
    size = dat.size();
    data.resize(size+1,0);
    for(size_t i = 0; i < size; ++i)
      data[i+1] = data[i] + dat[i];
  }
  T getsum(size_t l, size_t r){//0-indexed, [l,r)
    return data[r] - data[l];
  }
  T getsum(size_t r){//0-indexed, [0,r)
    return data[r];
  }
};

int main(){
  using mint = modint<998244353>;
  string s;
  int K;
  cin >> s >> K;
  vector<int> A;
  int t = 0;
  for(auto c : s){
    if(c == '1') ++t;
    else{
      A.push_back(t);
      t = 0;
    }
  }
  if(t) A.push_back(t);
  // for(auto e : A)
  //   cerr << e << " ";
  // cerr << endl;

  int m = A.size(), n = s.length();
  vector dp(n+1,vector(n+1,mint(0)));
  reverse(A.begin(), A.end());
  dp[0][0] = 1;
  for(int i = 0; i < m; ++i){
    vector dp_(n+1,vector(n+1,mint(0)));
    for(int j = 0; j <= n; ++j){ // -1 を何回使ったか
      mint s = 0;
      for(int k = 0; k <= n; ++k){ // +1 を何回使ったか
        if(k > j) break;
        // use -1
        dp_[j][k] += s;
        s += dp[j][k];
      }
    }
    for(int k = 0; k <= n; ++k){
      vector<mint> t(n+1);
      for(int j = 0; j <= n; ++j){
        t[j] = dp[j][k];
      }
      CumSum cs(t);
      for(int j = 0; j <= n; ++j){
        if(k > j) continue;
        dp_[j][k] += cs.getsum(max(0,j-A[i]),j+1);
      }
    }
    swap(dp,dp_);
  }
  mint ans = 0;
  for(int i = 0; i <= n; ++i){
    if(i > K) break;
    ans += dp[i][i];
  }
  cout << ans << endl;
}


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

#define fi first
#define se second
#define pb push_back
 
#define limit (int) (1e6 + 5)

#define maxn (long long int) (2147483647);

using namespace std;
using lli = long long int;
using ulli = unsigned long long int;
using ld = long double;


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

    if (n%7 == 0)
    {
        n /= 7;
    }

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

    int cr = 1,sr = 1,ans = -1;

    for (int i = 1; i <= n; ++i)
    {
        // cout << cr << "\n"
        cr *= 10;
        cr %= n;

        sr += cr;
        sr %= n;

        if (sr == 0)
        {
            ans = i+1;
            break;
        }
    }

    cout << ans;
    return 0;
}


















Measured memory_bytes: 3596
#include<cstdio>
#include<algorithm>
using namespace std;
static const int MAX_N = 50;
static const int INF = 1 << 30;

int N;
int L[MAX_N];
int sum[MAX_N + 1];
int memo[MAX_N + 1];

int main(){
	scanf("%d", &N);
	for(int i = 0; i < N; i++){
		scanf("%d", &L[i]);
		sum[i + 1] = sum[i] + L[i];
	}
	int res = INF;
	for(int i = 0; i <= N; i++){
		for(int j = 0; j < i; j++){
			int min_l = sum[i] - sum[j];
			fill(memo, memo + N + 1, INF);
			memo[j] = 0;
			for(int k = j - 1; k >= 0; k--){
				for(int l = j; l > k; l--){
					if(memo[l] != INF && sum[l] - sum[k] >= min_l) memo[k] = min(memo[k], max(memo[l], sum[l] - sum[k]));
				}
			}
			memo[i] = 0;
			for(int k = i + 1; k < N + 1; k++){
				for(int l = i; l < k; l++){
					if(memo[l] != INF && sum[k] - sum[l] >= min_l) memo[k] = min(memo[k], max(memo[l], sum[k] - sum[l]));
				}
			}
			if(memo[0] == INF || memo[N] == INF) continue;
			if(max(memo[0], memo[N]) - min_l < 0) continue;
			res = min(res, max(memo[0], memo[N]) - min_l);
		}
	}
	printf("%d\n", res);
	return 0;
}



Measured memory_bytes: 2756
#include <bits/stdc++.h>
#define exrep(i, a, b) for(long long i = a; i <= b; i++)
#define rep(i,n)for(long long i=0;i<(long long)(n);i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vector<ll> > vvl;
typedef vector<vector<P> > vvp;
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; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const int MAX=510000;
const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false); 
  
  int n;
  cin >> n;
  
  vector<int> c(n);
  rep(i,n) cin >> c[i];
  
  map<int,int> mp;
  vector<int> prev(n,-1);
  
  rep(i,n){
    if(mp.count(c[i])){
      prev[i] = mp[c[i]];
    }
    mp[c[i]]=i;
  }
  
  vector<ll> dp(n+1,0);
  dp[0] = dp[1] = 1;
  
  for(int i=1;i<n; i++){
    dp[i+1] = dp[i];
    dp[i+1] %= MOD;
    if(prev[i] == -1) continue;
    if(i-prev[i] == 1 ) continue;
    dp[i+1] += dp[prev[i]+1];
    dp[i+1] %=MOD;
  }
  
  cout << dp[n] << endl;
  return 0;     
}


Measured memory_bytes: 12800
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  int A[N];
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  
  int count = 0;
  bool flag = true;
  while (flag) {
    for (int i = 0; i < N; i++) {
      if ((A[i] % 2) == 0) {
        A[i] /= 2;
      }
      else {
        flag = false;
        break;
      }
    }
    if (flag) count++;
    else break;
  }
  cout << count << endl;
}


Measured memory_bytes: 256
// SumOfNumbers.cc
// 与えられた数の各桁の和を計算するプログラムを作成して下さい。
// 【入力】
// 複数のデータセットが入力として与えられます。
// 各データセットは１つの整数 x を含む１行で与えられます。
// x は 1000 桁以下の整数です。
// x が 0 のとき入力の終わりとします。このデータセットに対する出力を行ってはいけません。
// 【出力】
// 各データセットに対して、x の各桁の和を１行に出力して下さい。
// 【例】
// 入力：
// 123
// 55
// 1000
// 0
// 出力：
// 6
// 10
// 1
#include<cstdio>
#include<cstring>

int main( void) {
  char X[1001];

  while( true) {
    scanf( "%s", X);
    if ( strcmp( X, "0") == 0) break;

    int len = strlen( X);
    int sum = 0;
    for ( int i = 0; i < len; i++) {
      sum += (int)( X[i] - '0');
    }
    printf( "%d\n", sum);
  }

  return 0;
}



Measured memory_bytes: 2716
//
//  main.cpp
//  C
//
//  Created by 黄道煜 on 2018/7/15.
//  Copyright © 2018年 黄道煜. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#define LL long long
using namespace std;

int n, l1, l2;
char s[40], temp1[20], temp2[20];
LL ans;

map<pair<LL, LL>, LL> mmp;

LL Hash(char *temp)
{
    LL sum=1, len=strlen(temp);
    for(int i=0; i<len; i++)
    {
        sum*=131;
        sum+=temp[i]-'a';
    }
    return sum;
}

void dfs1(int x)
{
    if(x==n)
    {
        mmp[make_pair(Hash(temp1), Hash(temp2))]++;
        return;
    }
    temp1[l1++]=s[x];
    dfs1(x+1);
    temp1[--l1]=0;
    temp2[l2++]=s[x];
    dfs1(x+1);
    temp2[--l2]=0;
}

void dfs2(int x)
{
    if(x==n)
    {
        ans+=mmp[make_pair(Hash(temp1), Hash(temp2))];
        return;
    }
    temp1[l1++]=s[n*2-1-x];
    dfs2(x+1);
    temp1[--l1]=0;
    temp2[l2++]=s[n*2-1-x];
    dfs2(x+1);
    temp2[--l2]=0;
}

int main()
{
    scanf("%d", &n);
    scanf("%s", s);
    memset(temp1, 0, sizeof(temp1));
    memset(temp2, 0, sizeof(temp2));
    dfs1(0);
    l1=l2=0;
    memset(temp1, 0, sizeof(temp1));
    memset(temp2, 0, sizeof(temp2));
    dfs2(0);
    printf("%lld\n", ans);
}

Measured memory_bytes: 33024