akhauriyash/Code-Regression huggingface dataset:
# 全部違う要素なら、k個から成る部分列の数は単純に (n+1) C kである
# ここである2つが同じ数であった場合、それに寄って同一視される条件はなにか?
# 同じ数を1つだけ含む かつ 2つの間の数を含まない である。
# 2つの外側にある要素の数をjとすると 、j個の中からk-1個を選ぶから j C (k-1)である。
# j < k-1の場合は、同一視されるものは無いので0と見なせばよい。

n = int(input())
nums = list(map(int, input().split()))

max_len = n+5  # 適宜変更する
mod = 10**9 + 7

# 二項係数の左側の数字の最大値を max_len　とする。nとかだと他の変数と被りそうなので。
# factori_table = [1, 1, 2, 6, 24, 120, ...] 要は factori_table[n] = n!
# 計算時間はO(max_len * log(mod))
modinv_table = [-1] * (max_len + 1)
modinv_table[0] = None  # 万が一使っていたときにできるだけ早期に原因特定できるようにしたいので、Noneにしておく。
factori_table = [1] * (max_len + 1)
factori_inv_table = [1] * (max_len + 1)
for i in range(1, max_len + 1):
    factori_table[i] = factori_table[i-1] * (i) % mod

modinv_table[1] = 1
for i in range(2, max_len + 1):
    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod
    factori_inv_table[i] = factori_inv_table[i-1] * modinv_table[i] % mod


def binomial_coefficients(n, k):
    '''
    n! / (k! * (n-k)! )
    0 <= k <= nを満たさないときは変な値を返してしまうので、先にNoneを返すことにする。
    場合によっては0のほうが適切かもしれない。
    '''
    if not 0 <= k <= n:
        return None
    return (factori_table[n] * factori_inv_table[k] * factori_inv_table[n-k]) % mod

# 重複要素を探索
appearance = [-1] * (n+1)
for idx, num in enumerate(nums):
    if appearance[num] == -1:
        appearance[num] = idx
    else:
        dup = [appearance[num], idx]
        break

j = n+1 - (dup[1] - dup[0] + 1)

for k in range(1, n+1+1):
    if k-1 > j:
        print(binomial_coefficients(n+1, k))
    else:
        print((binomial_coefficients(n+1, k) - binomial_coefficients(j, k-1)) % mod)


Measured memory_bytes: 29012
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(p,a,b)    for(int p=a;i<b;i++)
#define INF 0x3f3f3f3f


int main()
{
    #ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("o2.txt", "w", stdout);
    #endif

    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if((c+b-1)/b<=(a+d-1)/d)cout<<"Yes";
    else cout<<"No";
    return 0;
}

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

vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0;
        while (N % a == 0) {
            ++ex;
            N /= a;
        }
        res.push_back({a, ex});
    }
    if (N != 1) res.push_back({N, 1});
    return res;
}

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

    const int MOD = 1000000007;
    vector<long long> ex(N+1, 0); // exp[p] := p の指数
    for (long long n = 2; n <= N; ++n) {
        const auto &res = prime_factorize(n); // n の素因数分解
        for (auto p : res) ex[p.first] += p.second;
    }
    long long res = 1;
    for (int p = 2; p <= N; ++p) {
        res *= ex[p] + 1; // 約数の個数は (exp + 1) の積
        res %= MOD;
    }
    cout << res << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    // Your code here!
    int N;
    int A,B;
    scanf("%d", &N);
    if(N == 1)
        printf("Hello World");
    else if(N == 2){
        scanf("%d", &A);
        scanf("%d", &B);
        printf("%d", A + B);
    }
    return 0;
}


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

using namespace std;

int main(){
	int N, x, ans = 0; cin >> N >> x;
	vector<int> a(N);
	for(int i = 0; i < N; ++i) cin >> a[i];
	sort(a.begin(), a.end());
	int count = 0;
	for(int i = 0; i < N; ++i){
		if(x >= a[i]){
			if(i != N - 1 || a[i] == x){
				x -= a[i];
				count++;
			}else{
				break;
			}
		}else{
			break;
		}
	}
	ans = max(ans, count);
	cout << ans << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define ff               first
#define ss               second
#define pb               push_back
#define all(x)           (x).begin(), (x).end()
#define mem0(x)          memset(x, 0, sizeof (x))
#define mem1(x)          memset(x, -1, sizeof (x))

typedef long long ll;
typedef vector <int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector <ii> vii;
typedef vector<vii> vvii;
typedef vector <ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;

const int MAXN = 1e6+1;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T, n;
    cin >> n;
    vi A(n);
    vi F(MAXN, 0);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
        F[A[i]]++;
    }
    int gcd = __gcd(A[0], A[1]);
    for (int j = 2; j < n; ++j) {
        gcd = __gcd(gcd, A[j]);
    }
    if (gcd != 1){
        cout << "not coprime\n";
        return 0;
    }
    for (int k = 2; k < MAXN; ++k) {
        int fq = 0;
        for (int i = k; i < MAXN; i += k) {
            fq += F[i];
        }
        if (fq > 1){
            cout << "setwise coprime\n";
            return 0;
        }
    }
    cout << "pairwise coprime\n";
}

Measured memory_bytes: 11068
#include<bits/stdc++.h>
using namespace std;
int main(){
        int a,b,n,s,f;
        int cnt=0;
        scanf("%d %d %d",&a,&b,&n);
        for(int i=0;i<n;++i){
                scanf("%d %d",&s,&f);
                cnt+=((s<a&&a<f)||(s<b&&b<f)||(s<=a&&b<=f)||(a<=s&&f<=b));
        }
        printf("%d\n",!(!cnt));
        return 0;
}

Measured memory_bytes: 3220
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
 
using namespace std;
 
const int MAXN = 2000 + 100;
 
int n, m;
int ans = 0;
char s[MAXN][MAXN];
int bad[MAXN][MAXN], cnt[MAXN][MAXN];
 
void solve(int cnt[])
{
	static int lef[MAXN], rig[MAXN];
	stack<int> sta1, sta2;
	for(int i = 1; i <= m - 1; i++)
	{
		while(!sta1.empty() && cnt[sta1.top()] >= cnt[i])
			sta1.pop();
		lef[i] = sta1.empty() ? 0 : sta1.top();
		sta1.push(i);
	}
	for(int i = m - 1; i >= 1; i--)
	{
		while(!sta2.empty() && cnt[sta2.top()] >= cnt[i])
			sta2.pop();
		rig[i] = sta2.empty() ? m : sta2.top();
		sta2.push(i);
	}
	for(int i = 1; i <= m - 1; i++)
		ans = max(ans, (cnt[i] + 1) * (rig[i] - lef[i] - 1 + 1));
	// for(int i = 1; i <= m - 1; i++)
	// 	cerr << lef[i] << ' ' << rig[i] << " / ";
	// cerr << endl;
}
 
int main()
{
	ios::sync_with_stdio(false);
//	 freopen("1.in", "r", stdin);
	// freopen("1.out", "w", stdout);
 
	cin >> n >> m;
	for(int i = 0; i < n; i++)
		cin >> s[i];
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			s[i][j] = (s[i][j] == '#' ? 1 : 0);
	for(int i = 1; i <= n - 1; i++)
		for(int j = 1; j <= m - 1; j++)
			bad[i][j] = (s[i - 1][j - 1] + s[i - 1][j] + s[i][j - 1] + s[i][j]) & 1;
	for(int i = 1; i <= n - 1; i++)
		for(int j = 1; j <= m - 1; j++)
			cnt[i][j] = (bad[i][j] ? 0 : cnt[i - 1][j] + 1);
	// for(int i = 1; i <= n - 1; i++)
	// {
	// 	for(int j = 1; j <= m - 1; j++)
	// 		cerr << cnt[i][j] << ' ';
	// 	cerr << endl;
	// }
	ans = max(n, m);
	for(int i = 1; i <= n - 1; i++)
		solve(cnt[i]);
	cout << ans << endl;
 
	return 0;
}


Measured memory_bytes: 38784
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define SORT(v) sort(v.begin(),v.end())
#define fori(i,a,b) for(ll i=a;i<b;i++)
#define M 1000000007
#define deb(x) cout<< #x << " " << x << endl;

double pi=3.14159265358979323846;

typedef pair<int,int> pii;
typedef pair<long long int, long long int>pll;
typedef vector<int>vi;
typedef vector<long long int>vl;
#define MAXN 10000001
 
ll h(vl w,vl v,vector<vl> &dp,ll wl,ll i){
	if(wl<=0||i>=w.size())return 0;
	if(dp[i][wl]!=-1)return dp[i][wl];
	else{
		if(w[i]<=wl)
		return dp[i][wl]=max(v[i]+h(w,v,dp,wl-w[i],i+1),h(w,v,dp,wl,i+1));
		else return dp[i][wl]=h(w,v,dp,wl,i+1);
	}
} 
int main ()
{
    ll T;
   T=1;
   //cin>>T;
    while(T--)
    {	
    ll n,wl;
    cin>>n>>wl;
    vl w(n),v(n);
    fori(i,0,n)cin>>w[i]>>v[i];
    vector<vl> dp(n+1,vector<ll>(wl+1,-1) ) ;
    
    ll ans=h(w,v,dp,wl,0);
    cout<<ans<<endl;
    }
    return 0;
}


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

int cnt = 0;
int R, G, B, N;

int main() {
  cin >> R >> G >> B >> N;

  for (int a = 0; a <= 3000; a++) {
    for (int b = 0; b <= 3000; b++) {
      int tmp = R * a + G * b;
      if (tmp > N) continue;
      if (tmp == N) {
        cnt++;
        continue;
      }
      if ((N - tmp) % B == 0) {
        // aa
        cnt++;
      }
    }
  }

  cout << cnt << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(a) begin(a),end(a)
typedef long long ll;
typedef pair<int,int> P;
const int inf=1e+9;
const ll mod=1000000007;
const double PI=3.14159265358979323846;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
ll gcd(ll a, ll b){
  if (b==0) return a;
  else return gcd(b,a%b);
}
int cans(bool f){
  if(f) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}




int main() {
  string s,t,u;
  int ns,nt;
  cin >> s >> t >> ns >> nt >> u;
  if(u == s) ns--;
  if(u == t) nt--;
  cout << ns <<" " <<nt << endl;
  return 0;
}


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

using namespace std;

using ll = long long;

int main(){
	int k;
	int x;

	cin >> k;
	cin >> x;
	
	for (int i = x-k+1; i < x+k; ++i) {
		cout << i << " ";
	}
	cout << endl;
	
	return 0;
}

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



int main() {
	string S;
	int d[100] = {};
	cin >> S;
	for (int i = 0; i < S.size(); i++) {
		d[S[i]-'a']++;
		if (d[S[i]-'a'] == 2) {
			cout << "no" << endl;
			return 0;
		}
	}
	cout << "yes" << endl;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
flag = True
for i in range(N):
    if A[i] % 2 == 0:
        if A[i] % 3 == 0 or A[i] % 5 == 0:
            continue
        else:
            flag = False
            break
    else:
        continue
if flag:
    print("APPROVED")
else:
    print("DENIED")


Measured memory_bytes: 2940
n, x = map(int, input().split())
L = list(map(int, input().split()))
dist = 0
res = 0
for i, l in enumerate(L, 1):
    dist += l
    if dist > x:
        print(i)
        exit()
    elif dist == x:
        print(i + 1)
        exit()
print(n + 1)


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

int main(){
    int N;
    long long K;
    cin >> N >> K;
    vector<int> A(N,0);
    vector<int> p(N,0),q(N,-1);
    p[0]=1; q[0]=0;
    for (int i=0;i<N;i++) cin >> A[i];
    
    int n=0;
    long long second=0,first=K;
    for(long long i=0;i<K;i++){
        n=A[n]-1;
        if(p[n]==0){
            p[n]=1;
            q[i+1]=n;
        }else if(p[n]==1){
            second=i+1;
            break;
        }
    }
    for(int j=0;j<second;j++){
        if (q[j]==n){
            first=j;
            break;
        }
    }
    cout << q[first+(K-first)%(second-first)]+1;
}


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

#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i < b; i++)
#define out(x) cout << x << endl
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<bool> > vvb;
typedef vector<vector<double> > vvd;
typedef vector<vector<string> > vvs;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

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;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
//以降 cin の入力元が 'input.txt' になる
//std::ifstream in("input.txt");
//std::cin.rdbuf(in.rdbuf());


signed main()
{
    gearup;
    set<int> s;
    rep(i,3){
        int a; cin >> a;
        s.insert(a);
    }
    out(s.size());
}

Measured memory_bytes: 3584
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace CsharpSpiral {
    partial class Program {
        static void Main(string[] args) {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = true };
            Console.SetOut(sw);
            new Program().Solve(new ConsoleInput(Console.In, ' '));
            Console.Out.Flush();
        }
        public void Solve(ConsoleInput cin) {
            var S = cin.Read;
            var R = new LinkedList<char>(S);
            var Q = cin.ReadInt;
            var flip = false;
            for(int i = 0; i < Q; i++) {
                var query = cin.ReadInt;
                if(query == 1) {
                    flip ^= true;
                }
                else {
                    var F = cin.ReadInt;
                    var C = cin.Read[0];
                    if((F == 1) ^ (flip))
                        R.AddFirst(C);
                    else
                        R.AddLast(C);
                }
            }
            Console.WriteLine(string.Join("", flip ? R.Reverse() : R));
        }


    }

    static class ExtendClass {
        public static void Swap<T>(this T[] X, int i, int j) {
            T tmp = X[i];
            X[i] = X[j];
            X[j] = tmp;
        }
        public static string Join<T>(this T[] X, string separator = " ") => string.Join(separator, X);
        public static S[] Clone<S>(this S[] src) where S : struct {
            var res = new S[src.Length];
            Array.Copy(src, res, src.Length);
            return res;
        }
    }

    class ConsoleInput {
        private readonly TextReader _stream;
        private readonly char _separator = ' ';
        private readonly Queue<string> inputStream;
        public ConsoleInput(TextReader stream, char separator = ' ') {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read {
            get {
                if(inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for(int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N) {
            var ret = new string[N];
            for(long i = 0; i < N; ++i)
                ret[i] = Read;
            return ret;
        }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for(long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for(long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
    }
}


Measured memory_bytes: 36628
#include <stdio.h>
#include <queue>
#include <vector>

struct str{
	int x0;
	int y0;
	int level;
};
bool operator<(str a, str b)
{
	return a.level>b.level;
}
std::priority_queue<str> Q;

char x[1010][1010];
int check[1010][1010];
int direX[5]={1,0,-1,0}, direY[5] = {0,1,0,-1};

int main()
{
	int a,b,c,d,e,f;
	scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
	
	for(int i=2;i<=a+1;i++) scanf("%s",x[i]+2);
	for(int i=0;i<=a+3;i++)
	{
		for(int j=0;j<=b+3;j++)
		{
			if(2<=i&&i<=a+1&&2<=j&&j<=b+1) continue;
			x[i][j] = '#';
		}
	}
	
	Q.push({c+1,d+1,1});
	while(!Q.empty())
	{
		int x0 = Q.top().x0;
		int y0 = Q.top().y0;
		int level = Q.top().level;
		
		Q.pop();
		if(check[x0][y0]) continue;
		
		check[x0][y0] = level;
		for(int i=0;i<4;i++)
		{
			if(x[x0+direX[i]][y0+direY[i]]=='#') continue;
			Q.push({x0+direX[i],y0+direY[i],level});
		}
		
		for(int i=-2;i<=2;i++)
		{
			for(int j=-2;j<=2;j++)
			{
				if(x[x0+i][y0+j]=='#') continue;
				Q.push({x0+i,y0+j,level+1});
			}
		}
	}
	
	if(check[e+1][f+1]==0) printf("-1");
	else printf("%d",check[e+1][f+1]-1);
}

Measured memory_bytes: 9968
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/* clang-format off */
#define MOD 1000000007
#define INF 1000000000
#define REP(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(a) (a).begin(), (a).end()
#define __DEBUG__
#ifdef __DEBUG__
#define CH_P(a) cout <<"check_point("<<#a<<")" << "\n";
#define DEBUG(x) cout<<#x<<":"<<x<<"\n"
#define DEBUGS(v) cout << #v << ":";for(auto x:v){cout<<x<<" ";}cout<<"\n"
#endif
#ifndef __DEBUG__
#define CH_P(a) 
#define DEBUG(x) 
#define DEBUGS(v) 
#endif
/* clang-format on */

int main() {
  ll a, b, c;
  cin >> a >> b >> c;
  if (a % 2 == 1 || b % 2 == 1 || c % 2 == 1) {
    cout << 0 << endl;
    return 0;
  }
  if (a == b && b == c) {
    cout << -1 << endl;
    return 0;
  }
  ll cnt = 0;
  while (a % 2 == 0 && b % 2 == 0 && c % 2 == 0) {
    cnt++;
    ll t1, t2, t3;
    t1 = a / 2;
    t2 = b / 2;
    t3 = c / 2;
    a = t2 + t3;
    b = t1 + t3;
    c = t1 + t2;
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 3632
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define mid ((l+r)>>1)

const int N=190;
char str[N][N];
int n,m,tmp,sum[N][N],dp[N][N][N][18];

bool check(int lx,int rx,int ly,int ry) {
	int res=sum[rx][ry]-sum[lx-1][ry]-sum[rx][ly-1]+sum[lx-1][ly-1];
	if(res==0||res==(rx-lx+1)*(ry-ly+1)) return true;
	return false;
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%s",str[i]+1);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(bool)(str[i][j]=='.');
	for(int x=1;x<=n;++x)
		for(int L=1;L<=m+1;++L)
			for(int k=0;k<18;++k) dp[x][L][L-1][k]=1<<30;
	for(int x=1;x<=n;++x)
		for(int L=1;L<=m;++L) for(int R=L;R<=m;++R) {
			int l=x,r=n,ans=l-1;
			while(l<=r) check(x,mid,L,R)?ans=mid,l=mid+1:r=mid-1;
			dp[x][L][R][0]=ans;
		}
	for(tmp=1;dp[1][1][m][tmp-1]<n;++tmp) {
		for(int x=1;x<=n;++x)
			for(int L=1;L<=m;++L)
				for(int R=L;R<=m;++R)
					dp[x][L][R][tmp]=dp[dp[x][L][R][tmp-1]+1][L][R][tmp-1];
		for(int x=1;x<=n;++x)
			for(int L=1;L<=m;++L)
				for(int R=L,res=L;R<=m;++R) {
					while(res<R&&
						min(dp[x][L][res][tmp-1],dp[x][res+1][R][tmp-1])<=
						min(dp[x][L][res+1][tmp-1],dp[x][res+2][R][tmp-1])) ++res;
					dp[x][L][R][tmp]=
						max(dp[x][L][R][tmp],min(dp[x][L][res][tmp-1],dp[x][res+1][R][tmp-1]));
				}
	}
	printf("%d\n",tmp-1);
	return 0;
}

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

int main() {
int K,N;
  cin>>K>>N;
  vector<int> Ai(N);
  for(int i=0;i<N;i++){
    cin>>Ai[i]; 
    //cout<<Ai[i]<<endl;
  }
  int Asa;
  int ma=K-Ai[N-1]+Ai[0];
  for(int i=0;i<N-1;i++){
    //cout<<ma<<endl;
    Asa=Ai[i+1]-Ai[i];
    ma=max(ma,Asa);
  }
  cout<<K-ma;
}

Measured memory_bytes: 3964
#include <cmath>
#include <iostream>
#include <string>
#include <vector> 
#include <algorithm>
#include <numeric>

#define FOR(i,a,b) for(i=(a);i<(b);++i) 
#define FORR(i,a,b) for(i=(a);i>(b);--i)
#define REP(i,n) for(i=0;i<(n);++i)
#define REPR(i,n) for(i=(n);i>0;--i)
#define ll long long
#define INT_MAX 2147483647
#define LL_MAX 9223372036854775807

using namespace std;

long long GCD(long long a, long long b) {
	if (a < b)
		swap(a, b);
	if (b == 0) return a;
	else return GCD(b, a % b);
}
bool sosuu_check(int num) {
	int i;
	for (i = 2; i <= sqrt(num); ++i) {
		if (num%i == 0)
			return false;
	}
	return (num < 2) ? false : true;
}
int main() {
	int N, K, b, p, r;
	ll ans = 0;
	cin >> N >> K;
	FOR(b, 1, N + 1) {
		p = N / b;
		r = N % b;
		ans += p * max(0, b - K) + max(0, r - K + 1);
	}
	ans = K == 0 ? ans - N : ans;
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long lli;
void solve();
int main()
{
	int t = 1;
//	cin >> t;
	for(int i=1; i <= t; i++)
	{
		solve();
		cout << '\n';
	}
	return 0;
}

void solve()
{
	int a, b; cin >> a >> b;
	int arr[a + 50];
	for(int i=0; i<a; i++)
		cin >> arr[i];
	sort(arr, arr + a);
	int res = 0;
	for(int i=0; i<b; i++)
		res += arr[i];
	cout << res << '\n';
}

Measured memory_bytes: 3600
#include <iostream>
using namespace std;
int main()
{
	int n;
	bool flag=true;
	cin >> n;
	int a[100005];
	for (int i=0; i<n; i++)
	{
		cin >> a[i];
	}
	for (int i=1; i<n-1; i++)
	{
		if (a[i-1]<a[i])
		{
			a[i]--;
		}
		if (a[i]>a[i+1])
		{
			flag=false;
			break;
		}
	}
	if (flag)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()   //reverse
#define strall(v) (v).cbegin(),(v).cend() //const_itterator
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}
const int INF = 1e8;

int main() {
  string s;
  cin >> s;
  map<ll,ll> mp;
  mp[0] =1;
  reverse(all(s));
  ll now = 0,ten=1;
  for(auto & e:s){
    now = (now + (e-'0') * ten) %2019;
    ten*=10;
    ten %=2019;
    mp[now]++;
  }
  ll ans = 0;
  for(auto &e:mp){
    ans += e.second*(e.second-1) / 2;
  }
  cout << ans << "\n";

}


Measured memory_bytes: 3708
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(long long i=0; i<(int)n; i++)
#define rep2(i,a,n) for(long long i=(a); i<(int)(n); i++)
#define all(vec) vec.begin(),vec.end()
using ll = long long;
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using psi = pair<string, int>;
const int dx[4] = {1, 0,-1, 0};
const int dy[4] = {0, 1, 0,-1};
const ll mod = 1e9+7;
int gcd(int a, int b){if(a%b == 0){return(b);}else{return(gcd(b, a%b));}}
int lcm(int a, int b){return a * b / gcd(a, b);}

ll N, M, K, H, W, L, R, X;
string S, T;

int main(){
  cin >> N >> K;
  double ans = 0;
  rep2(i,1,N+1){
    int score = i;
    double tans = 1;
    while(score<K){
      score *= 2;
      tans /=2;
    }
    ans += tans;
  }
  ans /= N;
  cout << fixed << setprecision(15);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3792
#include<cstring>
#include<cstdio>
#include<algorithm>
#define fo(i,a,b)for(int i=a,E=b;i<=E;i++)
#define abs(x)(x>0?x:-(x))
#define ll long long
using namespace std;
const int N=2e5+5;
int n,a[N],aa;
ll an;
int main(){
	scanf("%d",&n);
	fo(i,1,n)scanf("%d",&a[i]),a[i]-=i;
	sort(a+1,a+n+1);aa=a[(1+n)>>1];
	fo(i,1,n)an+=abs(a[i]-aa);
	printf("%lld",an);
}

Measured memory_bytes: 896
import java.util.*;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Node u[] = new Node[n];
		for(int i=0; i<n; i++){
			int id = sc.nextInt();
			u[id] = new Node();
			u[id].id = id;
			u[id].k = sc.nextInt();
			u[id].p = -1;
			u[id].type = "leaf";
			if(u[id].k > 0){
				int c[] = new int[u[id].k];
				for(int k=0; k<u[id].k; k++){
					c[k] = sc.nextInt();
				}
				u[id].c = c;
				u[id].type = "internal node";
			}
		}

		for(int i=0; i<n; i++){
			for(int k=0; k<u[i].k; k++){
				u[u[i].c[k]].p = u[i].id;
			}
		}

		for(int i=0; i<n; i++){
			if(u[i].p == -1){
				u[i].type = "root";
				for(int k=0; k<u[i].k; k++){
					setD(u, u[i].c[k], 1);
				}
				break;
			}
		}

		StringBuilder sb = new StringBuilder();
		for(int i=0; i<n; i++){
			sb.append("node "+u[i].id+": parent = "+u[i].p+", depth = "+u[i].d+", "+u[i].type+", [");
			for(int k=0; k<u[i].k; k++){
				if(k==0) sb.append(u[i].c[k]);
				else     sb.append(", "+u[i].c[k]);
			}
			sb.append("]\n");
		}
		System.out.print(sb.toString());
	}
	static void setD(Node u[], int c, int d){
		u[c].d = d;
		d++;
		for(int k=0; k<u[c].k; k++){
			setD(u, u[c].c[k], d);
		}
	}
}
class Node{
	int id;
	int k;
	int c[];
	int p;
	int d;
	String type;
}

Measured memory_bytes: 192640
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<set>
#include<cstring>
#include<iomanip> //cout << fixed << setprecision(15) << x << endl;

using namespace std;
typedef long long ll;
const ll INF = 1e9 + 6;
const ll MOD = 1e9 + 7;
const ll LLINF = 1LL<<60;
#define P pair<int, int>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
/* -- template -- */

int main() {
    int n; cin >> n;
    int a[3 * n];
    priority_queue<int, vector<int>, greater<>> F;
    deque<int> M;
    priority_queue<int> B;
    ll sumF[n + 1], sumB[n + 1];
    sumF[0] = 0;
    sumB[n] = 0;
    rep(i, 3 * n) {
        cin >> a[i];
        if(i < n)
            F.push(a[i]), sumF[0] += a[i];
        else if(2 * n <= i)
            B.push(a[i]), sumB[n] += a[i];
    }
    ll ans = -1 * LLINF;
    rep(i, n) {
        if(a[n + i] > F.top()) {
            sumF[i + 1] = sumF[i] - F.top();
            sumF[i + 1] += a[n + i];
            F.pop();
            F.push(a[n + i]);
        }else {
            sumF[i + 1] = sumF[i];
        }
    }
    rep(i, n) {
        if(a[2 * n - 1 - i] < B.top()) {
            sumB[n - 1 - i] = sumB[n - i] - B.top();
            sumB[n - 1 - i] += a[2 * n - 1 - i];
            B.pop();
            B.push(a[2 * n - 1 - i]);
        }else {
            sumB[n - 1 - i] = sumB[n - i];
        }
    }
    rep(i, n + 1) {
        //cout << sumF[i] << ' ';
        ans = max(ans, sumF[i] - sumB[i]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 3832
#include <stdio.h>


int main(){
	
	int a,b,i,n=1;
	scanf("%d %d",&a,&b);
	
	for(i=0;i<a;i++){
		if(n<b)n=n*2;
		else n=n+b;
	}
	
	printf("%d\n",n);
	
	return 0;
}


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

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

  ll a;
  string b;
  cin >> a >> b;

  ll c = (b[0] - '0') * 100 + (b[2] - '0') * 10 + (b[3] - '0');

  cout << a * c / 100 << '\n';

  return (0);
}


Measured memory_bytes: 3660
n, m = list(map(int, input().split()))
a = [input() for _ in range(n)]
b = [input() for _ in range(m)]

ans = False
for y in range(n-m+1):
    for x in range(n-m+1):
        sol = True
        for h in range(m):
            if a[y+h][x:x+m] != b[h]:
                sol = False
                break

        if sol:
            ans = True
            break
    if ans:
        break

print("Yes" if ans else "No")

Measured memory_bytes: 9116
# 解説放送解答
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))

# 手持ちのカード、交換カードを全部ごちゃまぜにして heapq に入れる
# heapq には tuple(書かれた数字, 枚数) の形で入れる
cards = []
heapq.heapify(cards)
for a in A:
    heapq.heappush(cards, (-a, 1))

for m in range(M):
    B, C = map(int, input().split())
    heapq.heappush(cards, (-C, B))

ans = 0
for i in range(N):
    x = heapq.heappop(cards)
    ans += x[0] * (-1)
    # まだ残っている場合は枚数を減らして再追加する
    if x[1] > 1:
        heapq.heappush(cards, (x[0], x[1]-1))

print(ans)


Measured memory_bytes: 31964
#include <stdio.h>

int main()
{
	long long a,b;
	scanf ("%lld %lld",&a,&b);
	if (a == 1 && b == 1) puts("1");
	else if (a == 1) printf ("%lld\n",b-2);
	else if (b == 1) printf ("%lld\n",a-2);
	else{
		printf ("%lld\n",(a-2)*(b-2));
	}
	return 0;
}

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


int main(){
  
 int a,b;
  cin>>a>>b;
  
  int ans=0;
  
  if(a>=13)
      ans=b;
  else if(a>=6 and a<=12)
      ans=b/2;
  else
     ans=0;
  
  cout<<ans<<endl;
  
  
  return 0;
}

Measured memory_bytes: 256
# abc129_b.py
# https://atcoder.jp/contests/abc129/tasks/abc129_b

# B - Balance /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 200点

# 問題文
# 1から N の番号がついた N 個の重りがあり、番号 i の重りの重さは Wiです。
# ある整数 1≤T<Nに対してこれらの重りを、番号が T 以下の重り と 番号が T より大きい重りの 2 グループに分けることを考え、
# それぞれのグループの重さの和を S1,S2とします。
# このような分け方全てを考えた時、S1と S2の差の絶対値の最小値を求めてください。

# 制約
#     2≤N≤100
#     1≤Wi≤100
#     入力は全て整数である

# 入力
# 入力は以下の形式で標準入力から与えられる。
# N
# W1 W2 ... WN−1 WN

# 出力
# S1と S2の差の絶対値の最小値を出力せよ。

# 入力例 1
# 3
# 1 2 3

# 出力例 1
# 0

# T=2としたとき、S1=1+2=3,S2=3 となり、差の絶対値は 0となります。

# 入力例 2
# 4
# 1 3 1 1

# 出力例 2
# 2

# T=2としたとき、S1=1+3=4,S2=1+1=2 となり、差の絶対値は 2です。これより差の絶対値を小さくすることは出来ません。

# 入力例 3
# 8
# 27 23 76 2 3 5 62 52

# 出力例 3
# 2


global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    # FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    # S = lines[0]
    N = int(lines[0])
    # N, M = list(map(int, lines[0].split()))
    values = list(map(int, lines[1].split()))
    # values_p = list(map(int, lines[M+1].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i]))
    # valueses = list()
    # for i in range(M):
    #     valueses.append(list(map(int, lines[i+1].split())))

    mi = None

    for n in range(N):
        a = sum(values[:n])
        b = sum(values[n:])
        dif = abs(a-b)
        if mi is None:
            mi = dif
        elif mi > dif:
            mi = dif

    return [mi]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['3', '1 2 3']
        lines_export = [0]
    if pattern == 2:
        lines_input = ['4', '1 3 1 1']
        lines_export = [2]
    if pattern == 3:
        lines_input = ['8', '27 23 76 2 3 5 62 52']
        lines_export = [2]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(2)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()


Measured memory_bytes: 9292
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <functional>
#include <assert.h>
using ll=long long;
#define int ll
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define SZ(x) ((int)x.size())
#define fi first
#define se second
const int INF = 1e15;
using namespace std;

template<class T> using vc=vector<T>;
template<class T> using vvc=vc<vc<T>>;

using pi=pair<int,int>;
using vi=vc<int>;

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

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

    int N; cin >> N;
    int A[N];
    rep(i,N) cin >> A[i];
    int ans[N];
    ans[0]=0;
    rep(i,N){
        if(i%2==0) ans[0]+=A[i];
        else ans[0]-=A[i];
    }
    rep(i,N-1){
        ans[i+1]=2*A[i]-ans[i];
    }
    rep(i,N) cout << ans[i] << " ";
    cout << endl;
}

Measured memory_bytes: 2944
function Main(input) {
  var nums = input.split('\n');

  if (nums[0]==='1' && nums[1]==='2'){
    console.log('3');
  } else if (nums[0]==='1' && nums[1]==='3'){
    console.log('2');
  } else if (nums[0]==='2' && nums[1]==='1'){
    console.log('3')
  } else if (nums[0]==='2' && nums[1]==='3'){
    console.log('1')
  } else if (nums[0]==='3' && nums[1]==='1'){
    console.log('2')
  } else {
    console.log('1')
  }
  
}
Main(require('fs').readFileSync('/dev/stdin', 'utf8'));

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

int main(){
    int X, n;
    cin >> X;
    
    for(int i=X; i>0; i--){
        for(int j=X; j>0; j--){
            n = j;
            for(int k=0; k<5; k++){
                n = n * j;
                if(n == i){
                    cout << i << endl;
                    return 0;
                }
            }
        }
    }
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
   int n,w[100],i,j,s,t,m;
    
   scanf("%d",&n);
   for (s=i=0;i<n;i++) {
      scanf("%d",&w[i]);
      s+=w[i];
   }
   t=0;m=s;
   for (i=0;i<n;i++) {
      s-=w[i];t+=w[i];
      if (s>t) j=s-t;
      else     j=t-s;
      if (j<m) m=j;
   }
   printf("%d\n",m);
   return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include "vector"
#include "queue"
#include "map"
#include "math.h"
#include "algorithm"
using namespace std;
typedef long long ll ;
typedef vector<ll> ve ;
typedef pair <int , int> pr ;
#define F first
#define S second
#define pb push_back
#define MP make_pair
#define MAX INT_MAX
#define MIN (-1 * INT_MAX)
#define rep(i,a,b) for(int i = a ; i< b ; ++i)
#define loop(i , arr)  for(auto i : arr)
#define endll '\n'
ve    vec2  , vec3  , vec4;
int t , n , k , sum , cnt;
priority_queue<ll> pq ;
int arr[100001] ;
map<char , ll> mp ;
const int mod = 1e9+7 ;
int gcd (int a  , int b){
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
bool isPrime(int n){
    for(int i = 2; i <= sqrt(n); i++){
        if(n%i == 0)
            return false;
    }
    return true;
}
int main () {
#ifndef ONLINE_JUDGE
 freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    char c;
    cin >> c ;
    if(c>= 'A' && c <= 'Z')
    {
        printf("A");
    }
    else
    {
        printf("a");
    }
 return 0 ;
}











Measured memory_bytes: 3024
#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < n; i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
typedef long long ll;

int main() {
    ll H, W; cin >> H >> W;
    if (H % 3 == 0 || W % 3 == 0) {
        cout << 0 << endl;
        return 0;
    }

    ll ans = 1LL << 60;
    REP(i, 1, H) {
        if (W % 2 == 0 || (H - i) % 2 == 0) {
            ans = min(ans, abs((i * W) - (H - i) * W / 2));
        } else {
            ll b, c;
            b = (H - i) / 2 * W; c = (H - i - (H - i) / 2) * W;
            ans = min(ans, abs(max((i * W), c) - min((i * W), b)));

            b = W / 2 * (H - i); c = (W - W / 2) * (H - i);
            ans = min(ans, abs(max((i * W), c) - min((i * W), b)));
        }
    }
    REP(i, 1, W) {
        if (H % 2 == 0 || (W - i) % 2 == 0) {
            ans = min(ans, abs((i * H) - (W - i) * H / 2));
        } else {
            ll b, c;
            b = (W - i) / 2 * H; c = (W - i) / 2 * H + H;
            ans = min(ans, abs(max((i * H), c) - min((i * H), b)));

            b = H / 2 * (W - i); c = H / 2 * (W - i) + (W - i);
            ans = min(ans, abs(max((i * H), c) - min((i * H), b)));
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

char a[51], b[51];

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

	for (int i = 0; i < 50; i++){
		if (a[i] != 0){
			cout << a[i];
		}
		else{
			break;
		}

		if (b[i] != 0){
			cout << b[i];
		}
		else{
			break;
		}
	}

	cout << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,s,n) for(int i = (s); i < (n); i++)
#define all(v) v.begin(), v.end()

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int h, w;
  cin >> h >> w;
  
  vector<vector<char>> a(h, vector<char>(w));
  rep(i, 0, h) {
    rep(j, 0, w) {
      cin >> a.at(i).at(j);
    }
  }
  vector<bool> hh(h, false);
  vector<bool> ww(w, false);
  
  rep(i, 0, h) {
    rep(j, 0, w) {
      if(a.at(i).at(j) == '#') {
        hh.at(i) = true;
        ww.at(j) = true;
      }        
    }
  }
  
  rep(i, 0, h) {
    if(hh.at(i)) {
      rep(j, 0, w) {
        if(ww.at(j))
          cout << a.at(i).at(j);
      }
      cout << "\n";
    }
  }

}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String args[]){
		Scanner in = new Scanner(System.in);
		int a = in.nextInt();
		int b = in.nextInt();
		if(a < b){
			System.out.println("a < b");
		}else if(a > b){
			System.out.println("a > b");
		}else {
			System.out.println("a == b");
		}
	}
}

Measured memory_bytes: 17172
#import <Foundation/Foundation.h>
BOOL addition = NO;
int f(int n){
	int result;
	if(n%3==0){
		result = n/3*2;
	}else if(n%3==1){
		result = (n-1)/3*2+1;
		addition = NO;
	}else{
		result = (n-2)/3*2+1;
		if(addition){
			result++;
			addition = NO;
		}else{
			addition = YES;
		}
	}
	return result;
}
int main() {
	char prev='\0', c;
	int ans = 0, current = 0;
	while((c=getchar())!='\n'){
		if(c==prev){
			current++;
		}else{
			if(current>0) ans += f(current);
			current = 1;
		}
		prev = c;
	}
	ans += f(current);
	printf("%d\n",ans);
}

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

using ll = long long;
#define ALL(c) (c).begin(), (c).end()
const int MOD = 1000000007;

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

    for (int i = 1; i <= 3500; i++) {
        for (int j = 1; j <= 3500; j++) {
            if (4 * i * j - i * n - j * n < 1) {
                continue;
            }
            if ((n * i * j) % (4 * i * j - i * n - j * n) == 0 && (n * i * j) / (4 * i * j - i * n - j * n) > 0) {
                cout << i << " " << j << " " << (n * i * j) / (4 * i * j - i * n - j * n) << endl;
                return 0;
            }
        }
    }
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    m = sum(v)
    dp = [[float("inf")] * (m+1) for _ in range(N + 1)]
    dp[0][0] = 0

    for n in range(N):
        for kati in range(m+1):
            if kati - v[n] >= 0:
                dp[n+1][kati] = min(dp[n+1][kati], dp[n][kati-v[n]] + w[n])
            dp[n+1][kati] = min(dp[n+1][kati], dp[n][kati])

    ans = 0
    for i in range(m+1):
        if dp[-1][i] <= W:
            ans = i

    print(ans)


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)


if __name__ == '__main__':
    main()


Measured memory_bytes: 309840
#include <bits/stdc++.h>
using namespace std;
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define mp make_pair
#define MOD 1000000007 //10^9+7
#define fi first
#define sc second
using ll=long long;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
using vstr=vector<string>;
void yes(bool c) { if (c)print("Yes"); else print("No"); };

int H,W,a[101][101],ans[101][101];
int chars[26];

void solve() {
    cin >> H >> W;
    rep(i,H){
        string s; cin >> s;
        for(int c:s){
            chars[c-97]++;
        }
    }
    // rep(i,26) cout << chars[i] << endl;
    int cnt2=0,cnt1=0;
    rep(i,26) chars[i] = chars[i]%4;
    rep(i,26) {
        cnt2+=chars[i]/2;
        chars[i] = chars[i]%2;
    }
    rep(i,26) cnt1 += chars[i];
    bool ok = true;
    if(H%2 && W%2){//どちらも奇数
        if(cnt1 != 1 || cnt2 > (H/2+W/2)) ok = false;
    }else if(H%2){//Hが奇数
        if(cnt2 > W/2) ok = false;
        if(cnt1 > 0) ok = false;
    }else if(W%2){
        if(cnt2 > H/2) ok = false;
        if(cnt1 > 0) ok = false;
    }else{
        if(cnt1 > 0 || cnt2 > 0) ok = false;
    }
    yes(ok);
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
	cout<<fixed<<setprecision(20);
    //int q; cin >> q;
	//while (q--)
		solve();
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
int main(){
	 int x,y,p,q;
	 bool switching=true;
	 std::cin>>x>>y;
	 if(x>=y){
		while(true){
			if(switching){
				p=y;
				q=x%y;
				switching=false;
				if(q==0){
					std::cout<<y<<"\n";
					return 0;
				}
			}
			else{
			     x=q;
				 y=p%q;
				 switching=true;
				 if(y==0){
				     std::cout<<q<<"\n";
					 return 0;
				 }	
			 }
		 }
	 }
	 if(x<y){
		while(true){
			if(switching){
				p=x;
				q=y%x;
				switching=false;
				if(q==0){
					std::cout<<x<<"\n";
					return 0;
				}
			}
			else{
			     y=p;
				 x=q%p;
				 switching=true;
				 if(y==0){
				     std::cout<<p<<"\n";
					 return 0;
				 }	
			 }
		 }
	 }
	 return 0;
 }

Measured memory_bytes: 3092
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;
#define mp  std::make_pair
#define ll long long int
#define abs(n) ((n>0)?(n):((n)*(-1)))
#define CEIL(a,b) (((a) + ((b)-1)) / (b))
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define VREP_ll(v) for(std::vector<ll>::iterator itr = (v).begin(); itr != (v).end();itr++)
#define VREP_int(v) for(std::vector<int>::iterator itr = (v).begin(); itr != (v).end();itr++)
#define VALL(v) ((v).begin(),(v).end())
#define errln(v) cerr << (v) << endl;
#define println(v) cout << (v) << endl;

int main(int argc, const char * argv[]) {
	int n ;
	cin >> n;
	int l=0,r,ret=0;
	ll h[n];
	REP(i,n) cin >> h[i];
	FOR(i,1,n-1){
		if(h[i-1] < h[i]){
			r = i-1;
			ret = max(r-l,ret);
//			cerr << l << " " << r << endl;
			l = i;
		}
	}
	ret = max(n-1-l,ret);
	println(ret);
	return 0;
}


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

#define REP(i,n) for(int i=0;i<n;i++)

using namespace std;
typedef unsigned long ul;
typedef pair<ul, ul> P;

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

    string s, t, u;
    int a, b;
    cin >> s >> t;
    cin >> a >> b >> u;

    if (u == s) {
        a -= 1;
    } else {
        b -= 1;
    }

    cout << a << ' ' << b << '\n';


    return 0;
}


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)
#define rep2(i,m,n) for (int i = m; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }
void debug_out() { cout << "\n"; }
template <class T, class... Args>
void debug_out(const T &x, const Args &... args) { cout << x << " "; debug_out(args...);}
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  int n;
  ll k;
  cin >> n >> k;
  vector<ll> A(n), F(n);
  rep(i,n) cin >> A[i];
  rep(i,n) cin >> F[i];
  sort(all(A), greater<ll>());
  sort(all(F));

  auto f = [&](ll x) {
    bool ok = true;
    ll sum = 0;
    rep(i,n) {
      ll maxi = x / F[i];
      if (A[i] > maxi) sum += A[i] - maxi;
      if (sum > k) {
        ok = false; break;
      }
    }
    return ok;
  };
  ll ok = 1LL<<50, ng = -1;
  while(ok - ng > 1) {
    ll mid = (ok + ng) / 2;
    if (f(mid)) ok = mid;
    else ng = mid;
  }
  cout << ok << endl;
  return 0;
}

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

int main(){
  int N,K;
  cin >> N >> K;
  int A = 1;
  for(int i = 0; i < N; i++){
    if(A <= K){
      A = A * 2;
    }
    else{
      A = A + K;
    }
  }
  cout << A << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>

#define FOR(i,b,n) for(int i=b;i<n;i++)
#define RFOR(i,b,n) for(int i=n-1;i>=b;i--)
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define NCLR(mat) memset(mat, -1, sizeof(mat))
#define LIMIT 10000002
using namespace std;

static const double EPS = 1e-9;
typedef long long ll;
typedef pair<int, int> paii;


bool prm[LIMIT]; 

int n, m, r;

void init()
{
	CLR(prm);
	
	FOR(i, 3, LIMIT)
	{
		if(i%2==0)
			prm[i] = true;
		else if( !prm[i] )
		{
			for(int j = 3; i*j < LIMIT; j+=2)
			{
				prm[i*j] = true;
			}
		}
	}
	
	return;
}
			
int solve(int k)
{
	RFOR(i,12,k+1)
	{
		if(!prm[i] && !prm[i-2] && !prm[i-6] && !prm[i-8])
		{
			return i;
		}
	}
	
	return 0;
}

int main()
{
	init();
	
	while(cin >> n, n)
	{
		cout << solve(n) << endl;
	}
	
	return 0;
}

Measured memory_bytes: 10932
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define pb push_back
#define all(v) v.begin(),v.end()
#define fi first
#define se second
#define bigger (char)toupper
#define smaller (char)tolower
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef vector<char> vc;
typedef long long ll;
typedef unsigned long long ull;

int main() {
    int N,M;
    cin>>N>>M;
    vi X(M);
    rep(i,M) cin>>X[i];
    sort(all(X));
    vi v;
    rep(i,M-1) {
        v.pb(abs(X[i+1]-X[i]));
    }
    if(N>=M) cout<<0<<endl;
    else {
        int answer=0;
        sort(all(v));
        rep(i,M-N) answer+=v[i];
        cout<<answer<<endl;
    }
}

Measured memory_bytes: 1276