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

#define stirng string
#define vvi vector<vector<int>>
#define vi vector<int>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

const int inf = 1e9 + 7;

int main() {
  int a, b, k;
  cin >> a >> b >> k;
  for (int i = a; i <= min(b, a + k - 1); i++) {
    cout << i << endl;
  }
  for (int i = max(b - k + 1, a + k); i <= b; i++) {
    cout << i << endl;
  }
  return 0;
}


Measured memory_bytes: 256
n = int(input())
s = input()

num = []
first = s[0]
end = s[-1]
pre = first
count = 0
for c in s:
    if c == pre:
        count += 1
    else:
        num.append(count)
        count = 1
        pre = c
num.append(count)

if len(num) == 1:
    print(0)
else:
    b = 0
    w = n
    offset = 0
    if first == '#':
        offset = 1
    w = sum(num[offset::2])
    minlist = [b + w]
    for i in range(len(num)):
        if i % 2 == offset:
            w -= num[i]
        else:
            b += num[i]
        minlist.append(b + w)
    print(min(minlist))

Measured memory_bytes: 13400
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <stack> // s.top()
#include <bitset>
#include <queue> // s.front()
using namespace std;

typedef long long Int;
typedef pair<Int,Int> P;
#define print(x) cout<<(x)<<endl

#define INF10 10000000000
#define INF5 100000
#define EPS 1e-10
#define MOD 1000000007



int main() {
	vector <int>v;
	for (int i = 0; i < 3; i++) {
		int ipts;
		cin >> ipts;
		v.push_back(ipts);
	}
	sort(v.begin(), v.end());
	print(v[0] + v[1]);






	return 0;
}

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

#define lb(x) x & -x
const int _ = 3e5 + 7; int N , arr[_];
void add(int x){while(x <= N){++arr[x]; x += lb(x);}}
int qry(int x){int sum = 0; while(x){sum += arr[x]; x -= lb(x);} return sum;}

#define ll long long
ll c(vector < int > p){
	ll sum = 0; memset(arr , 0 , sizeof(arr)); while(!p.empty()){sum += qry(p.back()); add(p.back()); p.pop_back();} return sum;
}

int main(){
	bool flg = 1; vector < int > p1 , p2 , p3; cin >> N;
	for(int x , i = 1 ; i <= N ; ++i){cin >> x; p1.push_back(x); (i & 1 ? p2 : p3).push_back(x); flg &= !((i ^ x) & 1);}
	puts(flg & (c(p1) == 3 * (c(p2) + c(p3))) ? "Yes" : "No"); return 0;
}


Measured memory_bytes: 7156
fun main() {
    readLine()!!.toInt()
    val list: MutableList<String> = readLine()!!.split("").filter { it != "" } as MutableList<String>
    var flagForward = 0
    var flagBack = list.size - 1
    var count = 0
    loop@ while (true) {
        if (flagBack <= flagForward ) break
        if (list[flagForward] == "R") {
            flagForward++
        } else {
            while (list[flagBack] != "R") {
                flagBack--
                if (flagForward == flagBack) break@loop
            }
            list[flagForward] = "R"
            list[flagBack] = "W"
            count++
            flagForward++
            flagBack--
        }
    }
    println(count)
}

Measured memory_bytes: 67852
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
	int N, M;
	
	public int[] numToM = {-1,2,5,5,4,5,6,3,7,6};
	public int[] mToNum = {-1,-1,-1,-1,-1,-1,-1,-1};
	
	List<Integer> mList = new ArrayList<Integer>();
	
	public void read() {
		Scanner in = new Scanner(System.in);
		N = in.nextInt();
		M = in.nextInt();
		
		for (int i=0; i<M; i++) {
			int num = in.nextInt();
			if (mToNum[numToM[num]] == -1) {
				mToNum[numToM[num]] = num;
			} else if (mToNum[numToM[num]] < num) {
				mToNum[numToM[num]] = num;
			}
		}
		in.close();
	}
	
	public void prepare() {
		for (int i=1; i<=7; i++) {
			if (mToNum[i] != -1) {
				mList.add(i);
			}
		}
		mList.sort(null);
	}
	
	private String create(int[] nums) {
		List<String> ret = new LinkedList<String>();
		for (int i=0; i<nums.length; i++) {
			ret.addAll(Collections.nCopies(nums[i], Integer.toString(mToNum[mList.get(i)])));
		}
		ret.sort(null);
		Collections.reverse(ret);
		return String.join("", ret);
	}
	
	public String solve() {
		int[] start = new int[mList.size()];
		Arrays.fill(start, 0);
		List<int[]> result = sub(N, 0, start, 0);
		
		List<String> ret = new LinkedList<String>();
		for (int[] ns : result) {
			ret.add(create(ns));
		}
		ret.sort(null);
		return ret.get(ret.size()-1);
	}
	
	private List<int[]> sub(int left, int next, int[] nums, int sum) {
		LinkedList<int[]> ret = new LinkedList<int[]>();
		long digit = -1;
		if (next >= mList.size()) {
			return null;
		}
		int m = mList.get(next);
		
		int start = left / m;
		for (int i=start; i>=0; i--) {
			nums[next] = i;
			int total = sum + i;
			int nextLeft = left - (m*i);
			if (nextLeft == 0) {
				if (digit == -1) {
					digit = total;
				} else if (digit > total) {
					break;
				}
				ret.add(nums.clone());
			} else {
				List<int[]> subStr = sub(nextLeft, next+1, nums, total);
				if (subStr != null && subStr.size() > 0) {
					boolean onlySmall = true;
					for (int[] ns : subStr) {
						if (digit == -1) {
							digit = sum(ns);
						} else if (digit > sum(ns)) {
							continue;
						}
						ret.add(ns);
						onlySmall = false;
					}

					if (onlySmall) {
						break;
					}
				}
			}
		}

		return ret;
	}
	
	private long sum(int[] nums) {
		long sum = 0;
		for (int i=0; i<nums.length; i++) {
			sum += nums[i];
		}
		return sum;
	}
	
	public static void main(String[] args) {
		Main main = new Main();
		main.read();
		main.prepare();
		System.out.println(main.solve());
	}
}


Measured memory_bytes: 22608
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>

#define INF (2 << 28)
#define fr first
#define sc second
using namespace std;

typedef long long ll;
typedef pair<int, int> iP;

int main(){
  
  int n, len;
  string s;
  
  while(cin >> n, n){
    cin >> len >> s;
    
    int ans = 0;
    for(int i = 0; i < len; i++){
      if(s[i] == 'I'){
        int cnt = 0;
        for(; i < len; i += 2){
          if(s[i + 1] == 'O' && s[i + 2] == 'I')
            cnt++;
          else break;
        }
        ans += max(0, cnt - n + 1);
      }
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 2104
import java.util.*;

public class Main {
	public static void main(String... args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int x = sc.nextInt();
		sc.close();

		if (a<=x && a+b>=x) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}

Measured memory_bytes: 23764
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		@SuppressWarnings("resource")
		Scanner scan = new Scanner(System.in);
		int[] cost = new int[3];
		cost[0] = scan.nextInt();
		cost[1] = scan.nextInt();
		cost[2] = scan.nextInt();
		Arrays.sort(cost);

		System.out.println(cost[0] + cost[1]);
	}

}


Measured memory_bytes: 21716
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/adaptor/indexed.hpp>

using namespace std;
using namespace boost::adaptors;
using namespace std::string_literals;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;
using boost::irange;

int main()
{
  string s;
  cin>>s;
  if(s=="AAA" || s=="BBB"){
    cout<<"No"<<endl;
  }else{
    cout<<"Yes"<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli mod=1000000007;
typedef pair<lli,pair<lli,lli>> ppi;
lli zero_x[]={-1,0,1,0};
lli zero_y[]={0,-1,0,1};
lli one_x[]={-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2};
lli one_y[]={-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2};
int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    lli h,w;
    cin>>h>>w;
    lli ch,cw,dh,dw;
    cin>>ch>>cw>>dh>>dw;
    string mat[h];
    for(lli i=0;i<h;++i)
        cin>>mat[i];
    priority_queue<ppi,vector<ppi>,greater<ppi>> q;
    q.push({0,{ch-1,cw-1}});
    lli vis[h][w]; 
    vis[ch-1][cw-1]=1;
    lli cost[h][w];
    cost[ch-1][cw-1]=0;
    for(lli i=0;i<h;++i)
        for(lli j=0;j<w;++j)
            cost[i][j]=LLONG_MAX;
    while(!q.empty()){
        lli curr=q.top().first;
        lli r=q.top().second.first;
        lli c=q.top().second.second;
        //cout<<r<<" "<<c<<" "<<curr<<endl;
        q.pop();
        for(lli i=0;i<4;++i){
            lli next_r=r+zero_x[i];
            lli next_c=c+zero_y[i];
            if(next_r>=0&&next_r<h&&next_c>=0&&next_c<w&&(cost[next_r][next_c]>curr)&&mat[next_r][next_c]=='.'){
                cost[next_r][next_c]=curr;
                q.push({curr,{next_r,next_c}});
            }
        }
        for(lli i=0;i<24;++i){
            lli next_r=r+one_x[i];
            lli next_c=c+one_y[i];
            if(next_r>=0&&next_r<h&&next_c>=0&&next_c<w&&(cost[next_r][next_c]>(curr+1))&&mat[next_r][next_c]=='.'){
                cost[next_r][next_c]=curr+1;
                q.push({curr+1,{next_r,next_c}});
            }
        }
    }
    if(cost[dh-1][dw-1]==LLONG_MAX)
        cout<<-1<<endl;
    else
        cout<<cost[dh-1][dw-1]<<endl;


}


Measured memory_bytes: 12764
mod = 10**9+7
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%mod
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], mod -2, mod)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % mod
    return frac, fraci
frac, fraci = frac(341398)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%mod
def inv(x):
    if x == 0:
        return inv(100)
    return pow(x, mod-2, mod)

N, A, B, C = map(int, input().split())

pa = A*inv(A+B) %mod
pb = B*inv(A+B) %mod

ans = 0
for i in range(N):
    ans += (N+i)*comb(N-1+i, i)*pow(pa, N, mod)*pow(pb, i, mod)
    ans += (N+i)*comb(N-1+i, i)*pow(pb, N, mod)*pow(pa, i, mod)
    ans %= mod
print(ans*100*inv(100-C)%mod)

Measured memory_bytes: 53812
#include<iostream>
#include<sstream>
#include<vector>
#include<algorithm>
#include<string>
#include<stdexcept>
#include<stdio.h>
#include<queue>
#include <cmath>
//for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<n;i++) cin >> x[i];
#define pi pair<int,int> 
using namespace std;
using ll = long long;
 int main(){
    int n,m;
    cin >> n >> m;
    int l[m],r[m];
    for(int i=0;i<m;i++){
        cin >> l[i] >> r[i];
    }
    int maxl=l[0],minr=r[0];
    for(int i=0;i<m;i++){
        maxl=max(maxl,l[i]);
        minr=min(minr,r[i]);
    }
    if(maxl>minr) cout << '0';
    else cout << minr-maxl+1;

    return 0;
 }

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N; cin>>N;
  string S; string T;
  cin>>S>>T;
  for(int i=0; i<N; i++){
    cout<<S.at(i);
    cout<<T.at(i);
  }
  cout<<endl;
}


Measured memory_bytes: 3572
import java.io.*;
import java.util.*;


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

		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n =Integer.parseInt(br.readLine());
		
		
		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;
		long sum = 0;
		String[] cut = br.readLine().split(" ");
		
		for (int i=0;i<n;i++) {
			int r =Integer.parseInt(cut[i]);
			if(max<r){
				max=r;
			}
			if(min>r){
				min=r;
			}
			sum+=r;
		}	
		System.out.println(min+" "+max+" "+sum);
	
		

	}
}

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

using namespace std;

using ll = long long;

// 最大公約数を計算
ll gcd(ll a, ll b) {
  if (b == 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}

// 最小公倍数を計算
ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

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

  ll result = lcm(a, b);
  cout << result << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
using llong = long long;
#define inv(X) ((X) == '1' ? '0' : '1')

llong n;
string x;

llong bitcnt(llong a) {
    llong ret = 0;
    while (a > 0) {
        if (a & 1) ret++;
        a >>= 1;
    }
    return ret;
}

llong f(llong x) {
    llong cnt = 0;
    while (bitcnt(x) > 0) {
        x %= bitcnt(x);
        cnt++;
    }
    return cnt;
}

llong to_int(string &s, llong mod) {
    llong ret = 0;
    for (auto ch : s) {
        ret *= 2;
        if (ch == '1') ret |= 1;
        ret %= mod;
    }
    return ret;
}

llong pow_mod(llong n, llong m, llong mod) {
    llong ret = 1;
    while (m > 0) {
        if (m & 1) {
            ret *= n;
            ret %= mod;
        }
        n *= n;
        n %= mod;
        m >>= 1;
    }
    return ret;
}

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

    llong cnt = count(x.begin(), x.end(), '1');
    llong x1 = to_int(x, cnt + 1);
    llong x2;
    if (cnt > 1) x2 = to_int(x, cnt - 1);

    for (int i = 0; i < n; i++) {
        if (x[i] == '0') {
            llong s = x1 + pow_mod(2, n - i - 1, cnt + 1);
            s %= cnt + 1;
            cout << f(s) + 1 << '\n';
        }
        else {
            if (cnt - 1 == 0) {
                cout << 0 << '\n';
                continue;
            }
            llong s = x2 - pow_mod(2, n - i - 1, cnt - 1);
            s %= cnt - 1;
            s += cnt - 1;
            s %= cnt - 1;
            cout << f(s) + 1 << '\n';
        }
    }
}

Measured memory_bytes: 3764
#include<cstdio>
#include<cstring>

#define N 200010
#define ll long long

using namespace std;

struct data
{
	ll len,a[30];
	data()
	{
		len=0;
		memset(a,0,sizeof(a));
	}
}f[100];

data operator + (data a,data b)
{
	data c;
	c.len=a.len+b.len;
	for(int i=0;i<26;i++)
		c.a[i]=a.a[i]+b.a[i];
	return c;
}

data operator - (data a,data b)
{
	data c;
	c.len=a.len-b.len;
	for(int i=0;i<26;i++)
		c.a[i]=a.a[i]-b.a[i];
	return c;
}

int n,maxn;
int cut,kmp[N];
char s[N],ss[N];
ll ql,qr;

data query(int k,ll x)
{
	if(x==f[k].len) return f[k];
	if(!k)
	{
		data c;
		c.len=x;
		for(int i=cut+1;i<=cut+x;i++)
			c.a[s[i]-'a']++;
		return c;
	}
	if(k==1)
	{
		data c;
		c.len=x;
		for(int i=1;i<=x;i++)
			c.a[s[i]-'a']++;
		return c;
	}
	if(x<=f[k-1].len) return query(k-1,x);
	return f[k-1]+query(k-2,x-f[k-1].len);
}

int main()
{
	scanf("%s%lld%lld",s+1,&ql,&qr);
	n=strlen(s+1);
	for(int i=1;i<=n/2;i++)
		ss[n/2-i+1]=s[i];
	for(int i=2,j=0;i<=n/2;i++)
	{
		while(j&&ss[j+1]!=ss[i]) j=kmp[j];
		if(ss[j+1]==ss[i]) j++;
		kmp[i]=j;
	}
	int cut=n/2-kmp[n/2];
	for(int i=cut+1;i<=n/2;i++)
	{
		f[0].len++;
		f[0].a[s[i]-'a']++;
	}
	for(int i=1;i<=cut;i++)
	{
		f[1].len++;
		f[1].a[s[i]-'a']++;
	}
	for(int i=2;;i++)
	{
		f[i].len=f[i-1].len+f[i-2].len;
		for(int j=0;j<26;j++)
			f[i].a[j]=f[i-1].a[j]+f[i-2].a[j];
		if(f[i].len>qr)
		{
			maxn=i;
			break;
		}
	}
	data ans=query(maxn,qr)-query(maxn,ql-1);
	for(int i=0;i<26;i++)
		printf("%lld ",ans.a[i]);
	return 0;
}
/*
87167725689669676 0 0 0 0 0 282080685775825810 0 0 0 87167725689669676 0 87167725689669676 0 0 87167725689669676 0 0 0 0 87167725689669676 141040342887912905 0 141040342887912905 0 0
87167725689669676 0 0 0 0 0 282080685775825810 0 0 0 87167725689669676 0 87167725689669676 0 0 87167725689669676 0 0 0 0 87167725689669676 141040342887912905 0 141040342887912905 0 0
*/

Measured memory_bytes: 3988
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=ja
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

const int MAX_N = 100;
const int MAX_W = 10000;

const char wall = '#';
vector<vector<ll>> dp(MAX_N+1, vector<ll>(MAX_W+1, 0));
vector<vector<bool>> used;
vector<vector<ll>> dist;
const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {1, 0, -1, 0};

ll N, W;
vector<ll> w, v;

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

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

  cin >> N >> W;
  // 何も入れないとき用に 行、列ともに +1 にする
  w.resize(N);
  v.resize(N);
  rep(i, N) {
    cin >> v[i] >> w[i];
  }

  rep(i, N) {
    rep(j, W+1) {
      if (j < w[i]) {
        // 重さ j より重い場合はその品物を入れず、今の値を継続
        dp[i+1][j] = dp[i][j];
      }
      else {
        // 入る余地がある場合は入れたほうが価値が上がるか判断
        dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]] + v[i]);
      }
    }
  }
  //rep(i, N+1) {
  //  rep(j, W+1) {
  //    printf("%lld ", dp[i][j]);
  //  }
  //  printf("\n");
  //}
  cout << dp[N][W] << endl;

  return 0;
}



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

int main() {
  string s;
  cin >> s;
  vector<char> t(s.size());
  
  for(int i=0;i<s.size();i++){
    t.at(i) = s.at(i);
  } 
  reverse(s.begin(), s.end());
  int count=0;

  for(int i=0;i<s.size();i++){
    if(t.at(i) != s.at(i)) count++;
  } 
  cout << count/2 <<endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] s = sc.next().toCharArray();
		int len = 0;
		for(int i=0;i<s.length;i++) {
			if (len % 2 == 0 && s[i] == 'A' || len % 2 == 1 && s[i] == 'Z') {
				len++;
			}
		}
		len /= 2;
		if (len == 0) {
			System.out.println(-1);
		}else{
			StringBuilder sb = new StringBuilder();
			for(int i=0;i<len;i++) {
				sb.append("AZ");
			}
			System.out.println(sb.toString());
		}
	}

}

Measured memory_bytes: 17320
#include <bits/stdc++.h>
#define foi(i,k,n) for(int i = (int)k; i < (int)n; ++i)
using namespace std;
typedef long long ll;
const int MAXN = 5 + 3000;
int N;
double p[MAXN], memo[MAXN][MAXN];

double dp(int h, int t) {
    int i = h + t;
    if(i == N) {
        if(h > t) {
            return 1.0;
        } else {
            return 0.0;
        }
    }
    double& ans = memo[h][t];
    if(ans < 0) {
        ans = (p[i] * dp(1 + h, t)) + ((1.0 - p[i]) * dp(h, 1 + t));
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N;
    foi(i,0,N) {
        cin >> p[i];
    }
    foi(i,0,MAXN) {
        foi(j,0,MAXN) {
            memo[i][j] = -1.0;
        }
    }
    cout << fixed << setprecision(10) << dp(0,0) << '\n';
    return 0;
}


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

int main(){
	ios_base::sync_with_stdio(0);
	
	int n;	string s;
	cin >> n >> s;

	if(n>=3200){
		cout << s << '\n';
	}
	else if(n<3200){
		cout << "red\n";	
	}
	
}


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

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

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

int main() {
	int a, b;
	cin >> a >> b;
	
	if ((a == 1 && b == 2) || (a == 2 && b == 1)) {
		cout << 3 << endl;
	} else if ((a == 1 && b == 3) || (a == 3 && b == 1)) {
		cout << 2 << endl;
	} else {
		cout << 1 << endl;
	}	
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <chrono>
using namespace std::chrono;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define pb push_back
#define int long long
#define ios std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define fill(x, v) memset(x, v, sizeof(x))
const ll mod = 1000000007;
const double pi = 3.14159265359; // PI
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1)
{
    cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args)
{
    const char *comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " : " << arg1 << " | ";
    __f(comma + 1, args...);
}
/*
std::cout << std::setprecision(9) << f << '\n';//3.141590000;
map<char,int>::reverse_iterator rit;
for(rit = mp.rbegin(); rit!=mp.rend(); rit++)
    auto start = high_resolution_clock::now();
    // Call the function, here
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<milliseconds>(stop - start);
    cout << "Time taken by function: "<< duration.count() << " milliseconds" << endl;
*/

int32_t main()
{
    // int n;
    // cin >> n;
    // unsigned int mul = 1;
    // bool f = 0, z = 0;
    // long long psum = 0;
    // for (int i = 0; i < n; i++)
    // {
    //     unsigned int h;
    //     cin >> h;
    //     if (h != 0)
    //         psum += (log(h) / log(10));
    //     if (h == 0)
    //         z = 1;
    //     mul *= h;
    //     if (mul > 1000000000000000000 || psum > 18)
    //         f = 1;
    //     }
    // if (z)
    //     cout << 0;
    // else if (f)
    //     cout << -1;
    // else
    //     cout << mul;
    // return 0;
    unsigned long long a, c = 0;
    string b;
    cin >> a;
    cin >> b;
    for (int i = 0; i < b.size(); i++)
    {
        if (b[i] != '.')
        {
            c = c * 10 + (b[i] - '0');
        }
    }
    c = a * c;
    cout << c / 100 << endl;
}


Measured memory_bytes: 3628
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include <cctype>
#include<math.h>
#include <iomanip>  
using namespace std;
int main() {
	int n, t[50], ans = 0;
	string s[50], x;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> s[i] >> t[i];
	}
	cin >> x;
	for (int i = n-1; i>-1; --i) {
		if (s[i] == x)break;
		ans = ans + t[i];
	}
	cout << ans << endl;

}

Measured memory_bytes: 256
N,P = map(int,input().split())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

import collections
A = prime_factorize(P)
B = collections.Counter(A)

ans = 1
for i in set(A):
    ans *= i**(B[i]//N)
print(ans)

Measured memory_bytes: 9404
/*2019/09/13 */
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define MOD 1000000007
#define MIN 999999999
#define MAX -999999999
typedef long long int ll;
typedef unsigned long long int ull;
void llswap(ll *x,ll *y){ll temp;temp=*x;*x=*y;*y=temp;}
void swap(int *x,int *y){int tmp;tmp=*x;*x=*y;*y=tmp;}
int rmax(int x,int y){return x>y?x:y;}
int rmin(int x,int y){return x>y?y:x;}
ll llrmax(ll x,ll y){return x>y?x:y;}
ll llrmin(ll x,ll y){return x>y?y:x;}
int asc(const void *a,const void *b){return *(int*)a-*(int*)b;}
int desc(const void *a,const void *b){return *(int*)b-*(int*)a;}
int llasc(const void *a,const void *b){return *(ll*)a-*(ll*)b;}
int lldesc(const void *a,const void *b){return *(ll*)b-*(ll*)a;}
int gcd(int x,int y){if(y==0)return x;return gcd(y,x%y);}
/*
int asc_t(const void *a,const void *b){return ((struct_t*)a)->member - ((struct_t*)b)->member;}
int desc_t(const void *a,const void *b){return ((struct_t*)b)->member - ((struct_t*)a)->member;}
*/

int main(){
    int n,p[200000];
    scanf("%d",&n);
    int cnt1,cnt2;
    cnt1=cnt2=0;
    int p1[200000],p2[200000];
    for(int i=0;i<n;i++){
        scanf("%d",&p[i]);
        p1[i]=p[i];
        p2[i]=p[i];
    }
    for(int i=0;i<n-1;i++){
        if(p1[i]==i+1){
            cnt1++;
            swap(&p1[i],&p1[i+1]);
        }
    }
    if(p1[n-1]==n){
        cnt1++;
        swap(&p1[n-2],&p1[n-1]);
    }
    printf("%d\n",cnt1);
    return 0;
}

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

int main(){
int N;
cin >> N;
int ans = 1000 - N%1000;
if(ans==1000) ans=0;
cout << ans << endl;

return 0;
}

Measured memory_bytes: 3632
MOD = 10**9+7
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
sums = [[0]*(M+2) for i in range(N+2)]
dp = [[0]*(M+1) for i in range(N+1)]
dp[0][0] = 1
for i in range(N+1):
    for j in range(M+1):
        if i-1>=0 and j-1>=0 and S[i-1] == T[j-1]:
            dp[i][j] = sums[i][j]
        sums[i+1][j+1] = sums[i][j+1]+sums[i+1][j]-sums[i][j]+dp[i][j]
        sums[i+1][j+1] %= MOD
print(sums[N+1][M+1])


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

for i in range(1, N):
    print(" ".join(map(str, A)))
    for j in range(i-1, -1, -1):
        if A[j] < A[j+1]:
            break
        A[j], A[j+1] = A[j+1], A[j]
print(" ".join(map(str, A)))



Measured memory_bytes: 5600
#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,n) for (int (i)=0;(i)<(n);(i)++)
typedef long long ll;

int main(){
    int A,B,ans;
    cin >> A >> B;
    ans = A - 2*B;
    if (ans < 0) ans = 0;
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>  // clang-format off
using Int = long long;
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef _MY_DEBUG
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Sat Apr  4 21:00:24 JST 2020
 **/

signed main() {
    Int n;
    std::cin >> n;
    std::set<Int> s;
    for (Int x = 1; x * x <= n - 1; x++) {
        if ((n - 1) % x) continue;
        Int y = (n - 1) / x;
        if (n % x == 1) s.insert(x);
        if (n % y == 1) s.insert(y);
    }

    for (Int x = 1; x * x <= n; x++) {
        if (n % x) continue;
        Int y = n / x;
        for (Int z : {x, y}) {
            if (z == 1) continue;
            Int tmp = n;
            while (1) {
                if (tmp % z == 0) {
                    tmp /= z;
                } else if (tmp % z == 1) {
                    s.insert(z);
                    break;
                } else {
                    break;
                }
            }
        }
    }
    dump(s);

    std::cout << s.size() << std::endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define OUT(x) cout << (x) << endl;
#define OUTA(a, n) \
    REP(i, n) { cout << (a[i]) << (i == n - 1 ? "\n" : " "); }
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) \
    SORT(a);     \
    reverse(ALL(a))

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

int main()
{
    ll T, X;
    cin >> T >> X;

    double ans = 1. * T / X;
    OUT(ans)
}

Measured memory_bytes: 256
#include <cstdio>
using namespace std;
int main() {
    long long n,k;
    scanf("%lld%lld",&n,&k);
    if(k==1)
        printf("%lld\n",n*n*n);
    else{
        long long s=0;
        s+=(n/k)*(n/k)*(n/k);
        if(k%2==0)
            s+=((n+k/2)/k)*((n+k/2)/k)*((n+k/2)/k);
        printf("%lld\n",s);
    }
    return 0;
}


Measured memory_bytes: 128
N = int(input())
task = []
for i in range(N):
    task.append(list(map(int, input().split())))
task.sort(key = lambda t: t[1])
ok = True

time = 0
for x in task:
    time += x[0]
    if time > x[1]:
        ok = False
        break
if ok:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 53724
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>



#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;cin>>n;
  char c;
  int x=0;
  int res=0;
  rep(i,n){
    cin>>c;
    if(c=='I')x++;
    else x--;
    chmax(res,x);
  }
  cout<<res<<endl;

  return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(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;
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;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1000000007;
constexpr lint INF = mod * mod;
constexpr int MAX = 100010;

map<char, int> pri;

bool is_op(char c){
    return c == '+' || c == '-' || c == '*';
}

lint calc(lint lhs, lint rhs, char op){
    if(op == '+') return lhs + rhs;
    else if(op == '-') return lhs - rhs;
    else return lhs * rhs;
}

lint expr(string &s, int &i);
lint hoge(string &s, int &i);
lint fuga(string &s, int &i);
lint tapi(string &s, int &i);
lint number(string &s, int &i);

lint expr(string &s, int &i){
    lint ret = hoge(s, i);
    while(i < (int)s.size() && is_op(s[i]) && pri[s[i]] == 0){
        char op = s[i];
        ++i;
        ret = calc(ret, hoge(s, i), op);
    }
    return ret;
}

lint hoge(string &s, int &i){
    lint ret = fuga(s, i);
    while(i < (int)s.size() && is_op(s[i]) && pri[s[i]] == 1){
        char op = s[i];
        ++i;
        ret = calc(ret, fuga(s, i), op);
    }
    return ret;
}

lint fuga(string &s, int &i){
    lint ret = tapi(s, i);
    while(i < (int)s.size() && is_op(s[i]) && pri[s[i]] == 2){
        char op = s[i];
        ++i;
        ret = calc(ret, tapi(s, i), op);
    }
    return ret;
}

lint tapi(string &s, int &i){
    if(s[i] == '('){
        ++i;
        lint ret = expr(s, i);
        ++i;
        return ret;
    }
    return number(s, i);
}

lint number(string &s, int &i){
    lint ret = 0;
    while(i < (int)s.size() && isdigit(s[i])){
        ret = ret * 10 + s[i]-'0';
        ++i;
    }
    return ret;
}

int main(){
    string s;
    cin >> s;
    lint ans = LLONG_MIN;
    rep(S, 27){
        pri['+'] = S % 3;
        pri['-'] = S/3 % 3;
        pri['*'] = S/3/3 % 3;
        int i = 0;
        chmax(ans, expr(s, i));
    }
    printf("%lld\n", ans);
}


Measured memory_bytes: 3348
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>

using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define pb(x) push_back(x)
#define int long long


signed main(void) {
  string str = "Good";
  string S;
  cin >> S;

  for(int i=1; i<4; i++) {
  	if (S[i] == S[i-1]) {
  		str = "Bad";
  	}
  }

  cout << str << endl;
  return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
const long long MOD = (long long)1e9 + 7;

string s;
int n, q, l, r, sum[100009];
int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q >> s;
	for (int i = 1; i < n; i++) {
		if (s.substr(i - 1, 2) == "AC") {
			sum[i] = sum[i - 1] + 1;
		}
		else {
			sum[i] = sum[i - 1];
		}
	}
	while (q--) {
		cin >> l >> r;
		l--; r--;
		cout << sum[r] - sum[l] << "\n";
	}
	//system("pause");
	return 0;
}

Measured memory_bytes: 1488
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

vector<int> divisor(int n){
    vector<int> d;
    for(int i=1; i*i<=n; ++i){
        if(n%i==0){
            d.pb(i);
            if(i != n/i) d.pb(n/i);
        }
    }
    sort(all(d), greater<int>());
    return d;
}

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

    int sa = 0;
    vector<int> a(n);
    rep(i,n){
        cin >>a[i];
        sa += a[i];
    }

    for(int d:divisor(sa)){
        int sr = 0;
        vector<int> r(n);
        rep(i,n){
            r[i] = a[i]%d;
            sr += r[i];
        }
        sort(all(r));

        int num = sr/d;
        int ct = 0;
        rep(i,n-num) ct += r[i];

        if(ct<=k){
            cout << d << "\n";
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <cmath>
#include <cstdio>
#include <limits>
#include <tuple>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <numeric>
#include <string>
#include <array>
#include <iomanip>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rrep(i, n) for (int i = n-1; i >= 0; --i)
#define REP(i, s, n) for (int i = s; i< (int)(n); ++i)
#define all(x) x.begin(), x.end()

using namespace std;
using ll = long long;
ll inf = ll(1e9);
using ll1d = vector<ll>;
using ll2d = vector<ll1d>;
using ll3d = vector<ll2d>;

bool judge(vector<ll> h, const ll &k, const ll &a, const ll &b) {
  ll cnt = 0;
  rep(i, h.size()) {
    h[i] -= k * b;
    if (h[i] > 0)
      cnt += (h[i] +a - b -1)/ (a - b);
  }
  return k >= cnt;
}

void solve(istream &ccin = cin, ostream &ccout = cout) {
  ll n, a, b;
  ccin >> n >> a >> b;

  vector<ll> h(n);
  rep(i, n) ccin >> h[i];

  ll lower = -1;
  ll higher = inf;
  while (higher - lower > 1) {
    ll mid = (higher + lower) / 2;
    if (judge(h, mid, a, b)) {
      higher = mid;
    } else {
      lower = mid;
    }
  }

  ccout << higher << endl;
}

int main() {
  ios::sync_with_stdio(false);
  solve();
  return 0;
}

Measured memory_bytes: 1792
#include<iostream>
using namespace std;
int main(){
  int a[4],b[4];
  while(cin >>a[0]>>a[1]>>a[2]>>a[3]>>b[0]>>b[1]>>b[2]>>b[3]){
    bool fa[4] = {false};
    bool fb[4] = {false};
    int ans[2] = {0};
    for(int i=0; i<4; i++){
      if(a[i] == b[i]){
	fa[i] = true;
	fb[i] = true;
	ans[0]++;
      }
    }
    for(int i=0; i<4; i++){
      if(!fb[i]){
	for(int j=0; j<4; j++){
	  if(!fa[j] && a[j] == b[i]){
	    fa[j] = true;
	    fb[i] = true;
	    ans[1]++;
	    break;
	  }
	}
      }
    }
    cout <<ans[0]<<" "<<ans[1]<<endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <stdio.h>
int main(void)
{
  int n, r=1<<29;
  for (scanf("%d",&n); n--;) {
    int a, c = 0;
    for (scanf("%d",&a); a%2<1; a/=2) ++c;
    r = r>c?c:r;
  }
  printf("%d\n", r);
  return 0;
}


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

int main() {
	// your code goes here
	char c; cin >> c;
	if(c=='a'||c=='i'||c=='u'||c=='e'||c=='o') cout << "vowel" << endl;
	else cout << "consonant" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << endl;
#define CFYN(n) cout << ( (n) ? "YES":"NO") << endl;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;

int main(void)
{
    IOS
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(n), c(m), d(m);
    REP(i,n) {
        cin >> a[i] >> b[i];
    }
    REP(i,m) {
        cin >> c[i] >> d[i];
    }
    vector<int> ans(m);
    REP(i,n) {
        int mindist = 1 << 30;
        int point = -1;
        REP(j,m) {
            int dist = abs(a[i]-c[j]) + abs(b[i]-d[j]);
            if (dist < mindist) {
                mindist = dist;
                point = j;
            }
        }
        cout << point +1 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
  int num;
  int a, b, c;
  int i;
  
  scanf("%d", &num);
  for (i=0;i<num;i++)
    {
      scanf("%d %d %d", &a, &b, &c);
      a = a*a;
      b = b*b;
      c = c*c;
      if (a + b == c)
	printf("YES\n");
      else if (a + c == b)
	printf("YES\n");
      else if (b + c == a)
	printf("YES\n");
      else
	printf("NO\n");
    }

  return 0;
}

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

const ll mod = 1e9 + 7;

int main(){
    int n;
    string s;
    cin >> n >> s;
    map<char, int> mp;
    rep(i, n){
        mp[s[i]]++;
    }
    ll ans = 1;
    rep(i, mp.size()){
        if (mp[i] > 0){
            ans *= mp[i] + 1;
            ans %= mod;
        }
    }

    cout << ans - 1 << endl;
    return 0;
}

Measured memory_bytes: 512
import java.util.Scanner;
public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		long sum = 0;
		for(int i = 1; i <= n-1 ;i++ ) {
			sum += i;
		}
		System.out.println(sum);

	}

}


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

using namespace std;

#define DB( x ) cout << #x << " = " << x << endl;
#define LEFT(n) (2 * (n))
#define RIGHT(n) (2 * (n) + 1)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> node;
//typedef vector <vector <ll>> matrix;

const ll INF = 1e16;
const double EPS = 1e-9;
const ll MOD = (ll)(1e9 + 7);
const ll MAXV = (ll)(2e5 + 10);
const ll MAXE = (ll)(1e6 + 10);


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

	string a, b;

	cin >> a >> b;

	int ans = 0;

	for(int i = 0;i < 3;i ++)
		if(a[i] == b[i])
			ans ++;

	cout << ans << " \n";

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long int
#define ld long double
#define pii 3.14
#define mod (ll)(1e9 + 7)
#define inf (ll)(1e18)
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ordered_set tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
#define pi pair<int,int>
#define N (ll)(5e5+5)

void solve()
{
    ll a;
    string s;
    cin>>a>>s;

    ll c = 100*(s[0]-'0') + 10*(s[2]-'0') + (s[3]-'0');
    a *= c;
    a /= 100;
    cout<<a<<"\n";
}

int main()
{
    fio;
    ll tc = 1;
    //cin>>tc;
    while(tc--)
    {
        solve();
    }
}


Measured memory_bytes: 3620
#include <algorithm>
#include <array>
#include <iostream>
#include <limits>
#include <vector>

using namespace std;

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

    vector<int> v;
    for (int i = 0; i < m; ++i) {
        int c;
        cin >> c;
        v.push_back(c);
    }

    vector<int> dp(50001, numeric_limits<int>::max());
    dp[0] = 0;

    for (int i : v) {
        for (int j = 0; j + i < dp.size(); ++j) {
            dp[j + i] = min(dp[j + i], dp[j] + 1);
        }
    }
    cout << dp[n] << endl;
}

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

const long double PI = acos(-1);
constexpr long double EPS = 1e-15;
constexpr int inf = 2e9;
constexpr ll INF = 2e18;
constexpr ll MOD = 1e9+7;
constexpr ll MOD1 = 998244353;
typedef pair<ll,ll> P;

//#define all(v) (v).begin(), (v).end()
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
//#define mp make_pair

int dp[1010][1010];

int main(){
    int n;
    while (cin >> n, n) {
        int ans = 0;
        char maze[n][n];
        REP(i,n) {
            cin >> maze[i];
        }
        REP(i,1010) {
            memset(dp[i],0,sizeof(dp[i]));
        }
        REP(i,n) {
            REP(j,n) {
                if (maze[i][j] == '*') continue;
                dp[i+1][j+1] = min({dp[i][j],dp[i+1][j],dp[i][j+1]}) + 1;
                ans = max(ans, dp[i+1][j+1]);
            }
        }
        cout << ans << endl;
    }

}


Measured memory_bytes: 7964
#include <stdio.h>

int isprime(int num){
	int i;

	for(i = 3;i*i <= num;i += 2){
		if(num%i == 0){
			return 0;
		}
	}

	return 1;
}

int main(){
	int n,cnt,num,sum;

	while(1){
		scanf("%d",&n);
		if(n == 0){
			break;
		}

		cnt = 1;
		sum = 2;
		num = 3;
		while(cnt != n){
			if(isprime(num)){
				sum += num;
				cnt++;
			}
			num += 2;
		}

		printf("%d\n",sum);
	}

	return 0;
}

Measured memory_bytes: 600
//#pragma GCC optimize("O3", "no-stack-protector")
//#pragma GCC target("sse4", "avx", "popcnt", "lzcnt", "sse3", "sse4.1", "sse4.2", "sse2", "tune=native")
//#pragma GCC optimize ("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using old = long double;

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, w, h;
    cin >> n >> w >> h;
    cout << (n - w + 1) * (n - h + 1);
    return 0;
}

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

int main()
{
	ull n;
	cin >> n;
	const int Max = pow(10,5);
	vector<int> cnt(Max+1);
	ull ans = 0;
	for(int i=0;i<n;i++){
		ull tmp;
		cin >> tmp;
		if(tmp>Max)
			ans++;
		else
			cnt[tmp]++;
	}
	for(int i=1;i<=Max;i++){
		ans += (cnt[i]>=i)?(cnt[i]-i):cnt[i];
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
const main = lines => {
  console.log(solve(lines));
};

const solve = (lines: string[]): string => {
  const [A, B] = parseLines(lines);
  return Math.max(A + B, A - B, A * B).toString();
};

const parseLines = (lines: string[]) => {
  const obj = lines[0].split(' ').map(n => +n);
  debug(obj);
  return obj;
};

const debug = (message?: any, ...optionalParams: any[]) => {
  if (!!process.env.LOCAL_DEBUG) console.log(message, ...optionalParams);
};

if (!process.env.LOCAL_DEBUG) {
  const { stdin: input, stdout: output } = process;
  input.resume();
  input.setEncoding('utf8');
  const lines = [];
  require('readline')
    .createInterface({ input, output })
    .on('line', line => lines.push(line))
    .on('close', () => main(lines));
}

export default solve;


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

using namespace std;
using llong = long long;
using ldbl = long double;
using lpair = pair<llong, llong>;

#define ALL(x) x.begin(), x.end()

template<typename T>
constexpr T inf = static_cast<T>(pow(10, static_cast<int>(log10(numeric_limits<T>::max())))) + 7;
constexpr llong mod = 1e9+7;

int H, W, K;
vector<string> area;
vector<vector<int>> rui;

int get(int sh, int sw, int th, int tw) {
  th++;
  tw++;
  return rui[th][tw] - rui[th][sw] - rui[sh][tw] + rui[sh][sw];
}

int main() {
  cin >> H >> W >> K;
  area.resize(H);
  for (auto &in: area) {
    cin >> in;
  }

  rui.resize(H+1, vector<int>(W+1, 0));
  for(int h = 0; h < H; ++h) {
    for (int w = 0; w < W; ++w) {
      rui[h+1][w+1] += area[h][w] == '1';
    }
  }

  for (int h = 1; h <= H; ++h) {
    for (int w = 1; w <= W; ++w) {
      rui[h][w] += rui[h][w-1] + rui[h-1][w] - rui[h-1][w-1];
    }
  }

  int ans = inf<int>;
  for (int i = 0; i < 1<<(H-1); ++i) {
    int res = __builtin_popcount(i);
    int left = 0;
    for (int w = 0; w < W; ++w) {
      int maxi = 0;
      int many = 0;
      for (int h = 0; h < H; ++h) {
        many += get(h, left, h, w);
        if (((i>>h)&1) || h == H-1) {
          maxi = max(maxi, many);
          many = 0;
        }
      }

      if (maxi > K) {
        if (left - w == 0) {
          res = inf<int>;
          break;
        }
        else {
          res++;
          left = w;
          w--;
        }
      }
    }
    ans = min(ans, res);
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int ufd[101010];
int Find(int a)
{
    if(a==ufd[a]) return a;
    return ufd[a] = Find(ufd[a]);
}
void Union(int a, int b)
{
    ufd[Find(a)] = Find(b);
}
int N, M;
int a[101010];
vector<pair<int, int> > V;
priority_queue<int> Q[101010];
int main()
{
    scanf("%d%d", &N, &M);
    long long ans = 0;
    for(int i=0; i<N; ++i)
    {
        scanf("%d", a+i);
        V.emplace_back(a[i], i);
        ans += a[i];
        ufd[i] = i;
    }
    sort(V.rbegin(), V.rend());
    for(int i=0; i<M; ++i)
    {
        int x, y; scanf("%d%d", &x, &y);
        Union(x, y);
    }
    if(N==M+1){ puts("0"); return 0;}
    if(N>2*M+2){puts("Impossible"); return 0;}
    int torm = 2*M+2-N;
    for(int i=0; i<N; ++i)
        Q[Find(i)].push(a[i]);
    for(auto x: V)
    {
        if(torm == 0) break;
        if(Q[Find(x.second)].size() > 1)
        {
            //printf("%d %d\n", Q[Find(x.second)].top(), Find(x.second));
            ans -= Q[Find(x.second)].top(); Q[Find(x.second)].pop();
            --torm;
        }
    }
    printf("%lld\n", ans);
}





























Measured memory_bytes: 6644
#include <stdio.h>

int main(){
  int N, K;
  
  scanf("%d %d", &N, &K);
  char S[N];
  scanf("%s", &S);

  S[K-1] = S[K-1] - ('A'-'a');
  
  printf("%s", S);
  
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mk make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pii pair<ll,ll>
#define vvll vector< vector<ll> >
#define pb push_back
#define inf 1e16
#define M 1000000007
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define mx 100010

int main(){
	IOS;
	ll a,b;cin>>a>>b;
	if((a+b)%2==0)cout<<(a+b)/2;
	else cout<<"IMPOSSIBLE";
	return 0;
}



Measured memory_bytes: 256
fn read<T: std::str::FromStr>(
    stdin_lock: &mut std::io::StdinLock,
    buf: &mut Vec<u8>,
    delimiter: u8,
) -> T {
    buf.clear();
    let l = std::io::BufRead::read_until(stdin_lock, delimiter, buf).unwrap();
    buf.truncate(l - 1); // remove delimiter
    let s = unsafe { std::str::from_utf8_unchecked(&buf) };
    s.parse().unwrap_or_else(|_| panic!("read"))
}

fn main() {
    let stdin = std::io::stdin();
    let mut stdin_lock = stdin.lock();
    let mut buf: Vec<u8> = Vec::new();
    let n: i32 = read(&mut stdin_lock, &mut buf, b'\n');
    let mut ans = false;
    for x in 0..(n / 7 + 1) {
        let n4 = n - 7 * x;
        for y in 0..(n4 / 4 + 1) {
            if n4 - 4 * y == 0 {
                ans = true;
                break;
            }
        }
        if ans {
            break;
        }
    }
    println!("{}", if ans { "Yes" } else { "No" });
}


Measured memory_bytes: 4352