akhauriyash/Code-Regression huggingface dataset:
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <math.h> // sqrt
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <iomanip> // setprecision
#include <bitset> // bitset
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<long long>;
using pii = pair<int, int>;
using psi = pair<string, int>;

string p = "pairwise coprime";
string s = "setwise coprime";
string n = "not coprime";

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

int main() {
    int N;
    cin >> N;
    vi data(N);
    for (int i = 0; i < N; i++) {
        cin >> data[i];
    }
    bool check = true;
    vi num(1000000, 0);
    for (int i = 0; i < N; i++) {
        int n = data[i];
        for (int a = 2; a * a <= n; a++) {
            if (n % a == 0) {
                num[a]++;
            }
            if (num[a] > 1) {
                check = false;
                break;
            }
            while (n % a == 0) {
                n /= a;
            }
        }
        if (n != 1) {
            num[n]++;
        }
        if (num[n] > 1) {
            check = false;
        }
        if (!check) {
            break;
        }
    }
    if (check) {
        cout << p << endl;
        return 0;
    }
    int ans = data[0];
    for (int i = 1; i < N; i++) {
        ans = gcd(ans, data[i]);
    }
    if (ans == 1) {
        cout << s << endl;
    }
    else {
        cout << n << endl;
    }
}


Measured memory_bytes: 11092
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int a[4],i;
	for(i=0;i<4;i++)
		cin>>a[i];
	sort(a,a+4);
	if(a[0]==1&&a[1]==4&&a[2]==7&&a[3]==9)
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;
} 

Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include<vector>
using namespace std;
int max1 = 1000100;
vector<int> a(max1);
vector<int> c(max1);
bool gcdback(int x)
{
	int g = 0;
	for (int i = 0; i < x; i++)
	{
		g = __gcd(g, a[i]);
	}
	if (g == 1)
	{
		return true;
	}
	return false;
}
bool  solveitabdo(int x)
{
	for (int i = 2; i < max1; i++)
	{
		int counter = 0;
		for (int j = i ; j < max1; j += i)
		{

			counter += c[j];
		}
		if (counter > 1)
		{
			return false;
		}
	}
	return true;
}
int main()
{
    int x;
	cin >> x ;
	for (int i = 0; i < x; i++)
	{
		cin >> a[i];
		c[a[i]]++;
	}
	if (solveitabdo(x))
	{
		cout << "pairwise coprime" << endl;
	}
	else if (gcdback(x))
	{
		cout << "setwise coprime" << endl;
	}
	else
	{
		cout << "not coprime" << endl;
	}
}


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

typedef long long ll;
const int maxn = 300, maxm = 1 << 5;
int n, c, m, s, a[maxn + 3], p[maxn + 3];
ll dp[maxn + 3][maxm + 3];

ll solve() {
	memset(dp, 0, sizeof(dp));
	dp[s * n][0] = 1;
	for (int i = 1; i <= m; i++) {
		int id = p[(i - 1) % n + 1];
		for (int j = i; j <= m + 1; j++) {
			for (int msk = 0; msk < 1 << n; msk++) {
				if (~msk >> (id - 1) & 1) {
					dp[min(m + 1, max(i + a[id] * n, j))][msk | (1 << (id - 1))] += dp[j][msk];
				}
			}
		}
	}
	return dp[m + 1][(1 << n) - 1];
}

int main() {
	scanf("%d %d", &n, &c);;
	for (int i = 0; i <= n - 1; i++) {
		scanf("%d", &a[i]);
	}
	sort(a, a + n), reverse(a, a + n);
	s = a[0], n--, m = n * c;
	for (int i = 1; i <= n; i++) {
		p[i] = i;
	}
	ll res = 0, cnt = 0;
	do {
		res += solve();
		cnt++;
	} while (next_permutation(p + 1, p + n + 1));
	for (int i = 1; i <= n; i++) {
		cnt *= c;
	}
	printf("%.16lf\n", 1. * res / cnt);
	return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<deque>


using namespace std;

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

    deque<long> dec(N);

    for(auto &x:dec){
        cin>>x;
    }

    long i=1;
    long tmp=1;

    long ans=0;
    while(1){
        if(i==2){
            cout<<ans<<endl;
            return 0;
        }else if(i==1e9+7){
            cout<<-1<<endl;
            return 0;

        }else{
            ans++;
            tmp=i;
            i=dec[i-1];
            dec[tmp-1]=1e9+7;
        }


    }



}

Measured memory_bytes: 1024
#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>
#include <bitset>

#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))

using namespace std;

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

int r, c;
bitset<10000> plate[10];

int solve()
{
	int res = 0;
	bitset<10000> tmp[10];
	
	FOR(k, 0, 1<<r)
	{
		FOR(i, 0, r)
			tmp[i] = plate[i];
		
		FOR(i, 0, r)
		{
			if(k & (1<<i))
				tmp[i].flip();
		}
		
		int zsum = 0;
		
		FOR(i, 0, c)
		{
			int zeros = 0;
			
			FOR(j, 0, r)
			{
				if(tmp[j][i] == false)
					zeros++;
			}
			
			zeros = max(r-zeros,zeros);
			zsum += zeros;
		}
		
		res = max(res, zsum);
	}
	
	return res;
}

int main()
{
	while(cin >> r >> c, (r||c))
	{
		int b;
		CLR(plate);
		
		FOR(j, 0, r)
			FOR(i, 0, c)
			{
				cin >> b;
				plate[j][i] = (b >= 1)? true : false;
			}
		
		cout << solve() << endl;
	}
	
	return 0;	
}

Measured memory_bytes: 1188
N = int(raw_input())
A, A2 = [], []
for i in range(N):
    a = raw_input().split()
    A.append([a[0], int(a[1])])
    A2.append([a[0], int(a[1])])

def partition(A):
    i = 0
    r = A[-1][1]
    for j in range(0, len(A)):
        if A[j][1] <= r:
            A[i], A[j] = A[j], A[i]
            i += 1
    return i-1, A

def quickSort(A):
    if len(A) < 2:
        return A
    
    q, A = partition(A)
    left = A[:q]
    right = A[q+1:]
    
    A[:q] = quickSort(left)
    A[q+1:] = quickSort(right)
    return A

def merge(left, right):
    global count
    sorted_list = []
    l_index = 0
    r_index = 0

    while l_index < len(left) and r_index < len(right):
        if left[l_index][1] <= right[r_index][1]:
            sorted_list.append(left[l_index])
            l_index += 1
        else:
            sorted_list.append(right[r_index])
            r_index += 1

    if len(left) != l_index:
        sorted_list.extend(left[l_index:])
    if len(right) != r_index:
        sorted_list.extend(right[r_index:])

    return sorted_list 

def mergeSort(A):
    
    if len(A) <= 1:
        return A

    mid = len(A) // 2
    left = A[:mid]
    right = A[mid:]

    left = mergeSort(left)
    right = mergeSort(right)

    return list(merge(left, right))

A = quickSort(A)
if A == mergeSort(A2):
    print "Stable"
else:
    print "Not stable"
for w, i in A:
    print w,i

Measured memory_bytes: 39680
fun main(args: Array<String>) {
    val (n, m) = readInputLine().split(" ").map { it.toInt() }
    val aarr = readInputLine().split(" ").map { it.toInt() }.toIntArray()

    val sum = aarr.sum()
    val border = sum / 4 / m + if (sum % (4 * m) != 0) 1 else 0

    var cnt = 0

    for (a in aarr) {
        if (a >= border) {
            cnt++
        }
    }

    if (cnt >= m) {
        println("Yes")
    } else {
        println("No")
    }
}

fun readInputLine(): String {
    return readLine()!!
}


Measured memory_bytes: 36028
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <math.h>
#include <map>
#include <functional>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <typeinfo>
#define PI 3.14159265359
#define INF 99999999
#define rep(i, n) for(int i=0; i<n; i++)
#define REP(n) rep(i, n)
#define EPS 1e-10
#define pb push_back
#define mp make_pair
typedef long long ll;
using namespace std;
typedef pair<int, int> P;

string getReverse(string str);
bool isLeap(int y);
ll gcd(ll a, ll b);
ll lcm(ll a, ll b);
double distanceAB(double xa, double ya, double xb, double yb);
void trace(int A[], int N);

/*
class Target
{
public:
	vector <string> draw(int n)
	{

	}
};
*/


int mcxiToInt(string str)
{
	map<char, int> tbl;
	int ret = 0;
	
	tbl['m'] = 1000;
	tbl['c'] = 100;
	tbl['x'] = 10;
	tbl['i'] = 1;
	
	rep(i, str.length())
	{
		if (isdigit(str[i]))
		{
			ret += (str[i] - '0') * tbl[str[i + 1]];
			i++;
		} else {
			ret += tbl[str[i]];
		}
	}
	
	return ret;
}

string getMcxi(int num)
{
	string ret = "";
	char temp[1000];
	
	if (num / 1000 >= 2)
	{
		sprintf(temp, "%dm", num / 1000);
		ret = temp;
	} else if (num / 1000 == 1) {
		ret += "m";
	}
	
	num %= 1000;
	
	if (num / 100 >= 2)
	{
		sprintf(temp, "%dc", num / 100);
		ret += temp;
	} else if (num / 100 == 1) {
		ret += "c";
	}
	
	num %= 100;
	
	if (num / 10 >= 2)
	{
		sprintf(temp, "%dx", num / 10);
		ret += temp;
	} else if (num / 10 == 1) {
		ret += "x";
	}
	
	num %= 10;
	
	if (num / 1 >= 2)
	{
		sprintf(temp, "%di", num / 1);
		ret += temp;
	} else if (num / 1 == 1) {
		ret += "i";
	}
	
	return ret;
}


int main()
{
	int n;
	string inp1, inp2;
	
	cin >> n;
	rep(i, n)
	{
		cin >> inp1 >> inp2;
		cout << getMcxi(mcxiToInt(inp1) + mcxiToInt(inp2)) << endl;
	}
	
	return 0;
}


string getReverse(string str)
{
	string ret = "";
	for (int i=str.length()-1; i>=0; i--)
	{
		ret += str.substr(i, 1);
	}
	return ret;
}

bool isLeap(int y)
{
	return y % 400 == 0
						? true : y % 100 == 0
						? false : y % 4 == 0
						? true : false;
}

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

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

void trace(int A[], int N)
{
	REP(N)
	{
		if (i > 0) cout << " ";
		cout << A[i];
	}
	cout << endl;
}

double distanceAB(double xa, double ya, double xb, double yb)
{
	return sqrt((xb-xa)*(xb-xa) + (yb-ya)*(yb-ya));
}

Measured memory_bytes: 1244
using System;
using System.Collections.Generic;
using System.Linq;

namespace ABC167A
{
    class Program
    {
        static void Main(string[] args)
        {
            var S = Console.ReadLine();
            var T = Console.ReadLine();

            int l = S.Length;
            if (T.Substring(0, l) == S) Console.WriteLine("Yes");
            else Console.WriteLine("No");



            Console.ReadKey();
        }

        static int[] ReadInt()
        {
            int[] ret = Console.ReadLine().Split().Select(int.Parse).ToArray();
            return ret;
        }
        static long[] ReadLong()
        {
            long[] ret = Console.ReadLine().Split().Select(long.Parse).ToArray();
            return ret;
        }
    }
}


Measured memory_bytes: 17424
s = list(input())
flag = True
odd = ["R", "U", "D"]
even = ["L", "U", "D"]
for i in range(len(s)):
    if (i+1) % 2 == 1:
        if not(s[i] in odd):
            flag = False
    else:
        if not (s[i] in even):
            flag = False

if flag:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3060
while (tmp = gets) != nil
  (a,b) = tmp.chomp.split.map(&:to_i)
  break if  a == nil || b == nil
  c = a.to_i + b.to_i
  count = 1

  while(c / 10) >= 1
    c /= 10
    count += 1
  end

  puts count
end



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

int main() {
	int X;
	cin >> X;
	int ans = 1;
	for (int i = 2, check = i * i;check <= X;++ i, check = i * i) {
		while (check <= X) {
			ans = max(check, ans);
			check *= i;
		}
	}
	cout << ans;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

bを固定すると、Xを超えない範囲でpを決め打ちできる
よって後はb全探索
*/

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

using namespace std;

int main() {
	int N, M;
	cin >> N >> M;
	vector<int>start;
	vector<int>end;
	for (int i = 0; i < M; i++) {
		int s, e;
		cin >> s >> e;
		start.push_back(s);
		end.push_back(e);
	}
	vector<int>ballNum(N + 1,1);
	vector<int>isRed(N+1,0);
	isRed[1] = 1;
	for (int i = 0; i < M; i++) {
		int st = start[i];
		int en = end[i];
		if (isRed[st] == 1) {
			if (ballNum[st] == 1) {
				isRed[st] = 0;
			}
			isRed[en] = 1;
		}
		ballNum[st]--;
		ballNum[en]++;
	}
	int ans = 0;
	for (int i = 1; i < N+1; i++) {
		if (isRed[i] == 1)ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2036
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author cherrypi59
 */

#pragma GCC optimize ("O2")
#pragma GCC optimize ("tree-vectorize")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define FFOR(i, a, b) FOR(i, a, b+1)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) FOR(i, 1, n+1)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define LEN(x) (int)(x).size()
#define DUMP(x) cerr<<__LINE__<<' '<<#x<<"="<<(x)<<endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair

using namespace std;
using lint = long long;
using pii =  pair<int, int>;
using pll =  pair<lint, lint>;
template <typename T> using vc = vector<T>;
template <typename T> using vvc = vector<vector<T>>;
template <typename T> inline bool chmax(T &a, T b){if(a<b){a = b; return true;} return false;}
template <typename T> inline bool chmin(T &a, T b){if(a>b){a = b; return true;} return false;}

constexpr lint ten(int n) {return n==0 ? 1 : ten(n-1)*10;}

class BRedOrBlue {
public:
    void solve(std::istream& in, std::ostream& out){
        ios_base::sync_with_stdio(false);
        in.tie(nullptr), out.tie(nullptr);
        int N;
        in>>N;
        string S;
        in>>S;
        int r = 0;
        for(auto& s : S) if(s=='R') ++r;
        if(2*r>N) out<<"Yes\n";
        else out<<"No\n";
    }
};


int main() {
	BRedOrBlue solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

int main() {
  
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  int minus=0;
  for (int i = 0; i < N; i++) {
    if(A.at(i)<0){
      minus++;
    }
  }
  long ans=0;
  int ch=A.at(0);
  if(minus%2==0){
    for (int i = 0; i < N; i++) {
      ans+=abs(A.at(i));
    }
  }
  
  else{
    for (int i = 1; i < N; i++) {
      ans+=abs(A.at(i));
      if(abs(ch)>abs(A.at(i))){
        ans+=abs(ch);
        
        ch=A.at(i);
        ans-=abs(ch);
      }
    }
    ans-=abs(ch);  
  } 
  cout<<ans<<endl;
}

Measured memory_bytes: 640
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
#define maxn 101000

int a[maxn],b[maxn];
int mymin(int x,int y) {return (x<y)?x:y;}
int main()
{
	int n,i,x,a1,a2,a3,a4,c1,c2,c3,c4;
	scanf("%d",&n);
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	c1=c2=c3=c4=a1=a2=a3=a4=0;
	for (i=1;i<=n;i++) 
	{
		scanf("%d",&x);
		if (i&1) 
		{
			a[x]++;
			if (a[x]>c1)
			{
				if (x==a1) c1=a[x];
				else {a3=a1;c3=c1;a1=x;c1=a[x];}
			}else if (a[x]>c3)
			{
				if (x==a3) c3=a[x];
				else {a3=x;c3=a[x];}
			}
			
		}
		else {
			b[x]++;
			if (b[x]>c2)
			{
				if (x==a2) c2=b[x];
				else {a4=a2;c4=c2;a2=x;c2=b[x];}
			}else if (b[x]>c4)
			{
				if (x==a4) c4=b[x];
				else {a4=x;c4=b[x];}
			}
		}
		//printf("%d %d %d %d\n",c1,c2,c3,c4);
	}
	//printf("%d %d %d %d\n",c1,c2,c3,c4);
	if (a1!=a2) printf("%d\n",n-c1-c2);
	else printf("%d\n",mymin(n-c1-c4,n-c2-c3));
	return 0;
}


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

int main() {
    int n, a, b;
    int p[100002] = {};
    int res = 0;
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> a >> b;
        p[a]++;
        p[b+1]--;
    }
    for (int i=1; i<100002; i++) {
        p[i] += p[i-1];
    }
    res = 1;
    for (int i=1; i<100002; i++) {
        if (p[i] >= i-1) {
            res = i;
        }
    }
    res--;
    cout << res << endl;
    return 0;
}

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

int main(){
    int n,x,l;
    int c=0;
    int d=0;
    cin>>n>>x;

    if(d<x)c++;
    for(int i=0;i<n;i++){
        cin>>l;
        d=d+l;
        //cout <<d<<endl;
        if(d<=x){
            c++;
        }

    }
    cout <<c;

    return 0;


}

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

int main() {
  int N, fN, i;
  cin >> N;
  fN = 0;
  for (i = 1 ; N / i > 0 ; i *= 10) {
    fN += (N - N / (i * 10) * (i * 10)) / i;
  }
  //cout << fN << endl;
  if (N % fN == 0) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


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

using namespace std;

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

int N,K;
int A[100005],B[100005];

int main(){

cin.tie(0);
ios::sync_with_stdio(false);

cin>>N>>K;

for(int i=0; i<N; i++) cin>>A[i]; 
sort(A,A+N);

if(A[N-1]<K){
  cout<<"IMPOSSIBLE"<<endl;
  return 0;
}

int P=A[0];
for(int i=0; i<N; i++){
  B[i]=A[i]-K;
  P=gcd(P,A[i]);
}

for(int i=0; i<N; i++){
  if(B[i]>=0){
    if(B[i]%P==0){
      cout<<"POSSIBLE"<<endl;
      return 0;
    }
  }
}

cout<<"IMPOSSIBLE"<<endl;
return 0;

}


Measured memory_bytes: 1024
#include <cstdio>
using namespace std;

int H, W;
char ch[120][120];

int main(){
	scanf("%d %d", &H, &W);
	for (int i = 0; i < H; i++) {
		scanf("%s", ch[i]);
	}
	for (int i = 0; i < H; i++) {
		int p = -1;
		if (ch[i][0] == 'c') {
			printf("0");
			p = 0;
		}
		else {
			printf("-1");
		}
		for (int j = 1; j < W; j++) {
			if (p == -1 && ch[i][j] != 'c') {
				printf(" -1");
			}
			else if(ch[i][j] == 'c') {
				printf(" 0");
				p = j;
			}
			else {
				printf(" %d", j - p);
			}
		}
		printf("\n");
	}
	
	return 0;
}

Measured memory_bytes: 2732
#!/usr/bin/python3.7
# -*- coding: utf-8 -*-

#ABC168A


n = input()

if n[-1] == '3':
	print('bon')
elif n[-1] == '0' or n[-1] == '1' or n[-1] == '6' or n[-1] == '8':
	print('pon')
else:
	print('hon')

Measured memory_bytes: 9040
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
  cin>>N;
  vector<int> A(N);
  for(int i=0;i<N;i++){
  cin>>A[i];
  }
  sort(A.begin(),A.end());
    reverse(A.begin(),A.end());
    int a=0;
    a+=A[0]/2;
    for(int i=1;i<N;i++){
    a+=A[i];
    }
  cout<<a<<endl;

}


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

int table[1001];

int main(){
  int C;
  for(int i=1; cin>>C, C; ++i)
  {
    for (int k = 0; k < 1001; ++k) table[k] = -1e9;
    table[0] = 0;

    int n; cin >> n;
    for(;n--;) {
      int v, w; char comma;
      cin >> v >> comma >> w;
      for (int k = 1000 - w; k >=0; --k) { // table の上から更新
        table[k+w] = max<int>(table[k+w], table[k] + v);
      }
    }

    int W, V=table[0];
    for (int k = 0; k <= C; ++k) { // 最小のインデクスを答える必要
      if (V < table[k]) {
        V = table[k];
        W = k;
      }
    }

    printf("Case %d:\n%d\n%d\n", i, V, W);
  }
}

Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ll long long
#define inf (1LL<<61)
const ll MOD=1000000000+7;
const ll N=2e5+5;
template<typename T> T gcd(T a,T b) { if(a==0) return b; return gcd(b%a,a); }
template<typename T> T pow(T a,T b, long long m){T ans=1; while(b>0){ if(b%2==1) ans=(ans*a)%m; b/=2; a=(a*a)%m; } return ans%m; }
long double a[3000];
long double cache[3000][3000];
ll n;
ll vis[3000][3000];
long double dp(ll index,ll counthead)
{
	if(index==n)
	{
		if(counthead>n-counthead)
			return 1;
		else
			return 0;
	}
	long double &ans=cache[index][counthead];
	if(vis[index][counthead])
	    return ans;
	vis[index][counthead]=1;
	ans=dp(index+1,counthead+1)*a[index]+dp(index+1,counthead)*(1-a[index]);
	return ans;

}
int main()
{
    IOS;
    cin>>n;
    for(ll i=0;i<n;i++)
    	cin>>a[i];
    long double ans=dp(0,0);
    cout<<fixed<<setprecision(12)<<ans<<endl;
    return 0;
}


Measured memory_bytes: 209920
using System;

namespace MyProgram{
    class AtCoder{
        static void Main(string[] args){
            int[] input = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
            int N = input[0];
            int Q = input[1];
            string S = Console.ReadLine();
            int[] count = new int[N];
            int[] l = new int[Q];
            int[] r = new int[Q]; 
            for(var i=0;i<Q;i++){
                int[] temp = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
                l[i] = temp[0];
                r[i] = temp[1];
            }
            int tmp = 0;
            for(var j=1;j<N;j++){
                if(S[j-1]=='A'&&S[j]=='C'){
                    tmp++;
                }
                count[j] = tmp;
            }
            count[0] = 0;
            for(var i=0;i<Q;i++){
                Console.WriteLine(count[r[i]-1]-count[l[i]-1]);
            }
        }
    }
}

Measured memory_bytes: 19264
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
#include <map>
#include <sstream>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <stdexcept>
#include <utility>
using namespace std;
// #include <bits/stdc++.h>
#define ll long long
#define ld long double
#define rep(i,h) for(int i = 0; i < h; ++i)
#define rep1(i,h) for(int i = 0; i <= h; ++i)
#define rep2(i,n,h) for(int i = n; i < h; ++i)
#define rep3(l,n,h) for(int l = n; l <= h; ++l)
typedef pair<int,int> int_pair;


int main() {
    int x;
    cin >> x;;
    rep(i,x) {
        if(100 * i <= x && x <= 105 * i) {
            cout << "1" << endl;
            return 0;
        }
    }
    cout << "0" << endl;
     return 0;
    }


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int x[3];
  cin >> x[0] >> x[1] >> x[2];
  int ans = 0;
  while (true) {
    if (x[0] == x[1] && x[0] == x[2]) break;
    sort(x, x + 3);
    if (x[0] == x[1]) {
      x[0]++, x[1]++;
    } else {
      x[0] += 2;
    }
    ans++;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k = int(input())
print(l[k - 1])

Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;
#define Would
#define you
#define all(n)  n.begin(),n.end()
#define rall(n) n.rbegin(),n.rend()
typedef long long ll;
const ll INF = 1e9;
const ll MOD = 1234567;
const double EPS = 1e-10;
const double pi = acos(-1);//3.1415926535897932384626433832795028...
const ll SIZE = 2000005;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, alp[30];
ll fac[SIZE], finv[SIZE], inv[SIZE];
vector<ll>dij;
struct edge { ll to, cost; };
vector<vector<edge> >G;
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; }

ll mod_pow(ll a, ll b) {
	ll res = 1, mul = a;
	for (int i = 0; i < 31; ++i) {
		if (b >> i & 1) {
			res *= mul;
			res %= MOD;
		}
		mul = (mul * mul) % MOD;
	}
	return res;
}

void addedge(int from, int to, int cost) {
	G[from].push_back({ to,cost });
	G[to].push_back({ from,cost });
}

template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T & t, const V & v) { t = v; }

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T & t, const V & v) {
	for (auto& e : t) fill_v(e, v);
}

template<typename T>
void outp(vector<T>v) {
	for (int i = 0; i < v.size(); ++i) {
		cout << v[i];
		if (i != v.size() - 1) { cout << " "; }
	}
}

double add(double a, double b) {
	if (abs(a + b) < EPS * (abs(a) + abs(b))) { return 0; }
	return a + b;
}

double len(int a, int b, int c, int d) {
	return (double)sqrt((a - c) * (a - c) + (b - d) * (b - d));
}

ll a, b, ans;
int main() {
	cin >> a >> b;
	ans += max(0ll, 4 - a) * 100000 + max(0ll, 4 - b) * 100000;
	if (a == 1 && b == 1) { ans += 400000; }

	cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

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

        int a=0;
        int b=0;
        for(int i=-200; i<200; i++) {
            for(int j=0; j<200; j++) {
                if(Math.pow(j,5)-Math.pow(i, 5)==X) {
                    a=j;
                    b=i;
                    break;
                }
            }
        }
        System.out.println(a+" "+b);

    }

}


Measured memory_bytes: 38536
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		int c = scan.nextInt();
		int d = 0;
		for (int i = 1; i <= b; i++) {
			d = a*i % b;
			if (d == c) {
				System.out.println("YES");
				return;
			}
		}
		System.out.println("NO");
	}
}


Measured memory_bytes: 21972
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
using ll = long long;
int main() {
	int A, B, C;
	cin >> A >> B >> C;
	int m = 0;
	m = max(m, A);
	m = max(m, B);
	m = max(m, C);
	if (3 * m % 2 == (A + B + C) % 2)
		cout << (3 * m - A - B - C) / 2 << endl;
	else
		cout << (3 * m - A - B - C + 1) / 2 + 1 << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int t[101][3];
int d[200][3];
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++)for(int j=0;j<3;j++){scanf("%d",&d[i][j]);t[d[i][j]][j]++;}
	for(int i=0;i<a;i++){
		int ret=0;
		if(t[d[i][0]][0]==1)ret+=d[i][0];
		if(t[d[i][1]][1]==1)ret+=d[i][1];
		if(t[d[i][2]][2]==1)ret+=d[i][2];
		printf("%d\n",ret);
	}
}

Measured memory_bytes: 1028
#include <bits/stdc++.h>
#define rp(i,n) for(int i=0; i < n; i++)
using namespace std;
int main(){
  int n,m,c;
  cin >> n >> m >> c;
  int b[m];
  rp(i,m) cin >> b[i];
  int a[n][m];
  rp(i,n){
    for(int j=0; j < m; j++){
      cin >> a[i][j];
    }
  }
  int ans = 0;
  rp(i,n){
    int x = c;
    	for(int j=0; j < m; j++){
      		x += a[i][j]*b[j];
        }
    if(x > 0) ans++;
  }
  cout << ans <<endl;
}
	

Measured memory_bytes: 256
#include <iostream>
#include<string>
#include<set>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<iomanip>
#include<cmath>
#include<stack>
#include <cctype>
#include <cstdio>
#define endl '\n'
#define Bedoazim ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

const long long N = 1e5 + 5, mod = 1e9 + 7;


int main() {

    Bedoazim

        int bagsize, n;

    cin >> n;

    int stones[N];

    for (int i = 1; i <= n; i++) {

        cin >> stones[i];
    }

    int total = 0;

    int dp[N] = {};

    for (int i = 1; i <= n; i++) {

        long long a = 1e9, b = 1e9;

        if (i -1  > 0)
            a = abs(stones[i] - stones[i - 1])+dp[i-1];

        if (i - 2 > 0)
            b = abs(stones[i] - stones[i - 2])+dp[i-2];

        if (a == 1e9 && b == 1e9)
            continue;

        if (a <= b) {

            dp[i] = a;

        }
        //6
          //  30 10 60 10 60 50

        else if (a > b) {

            dp[i] = b;

         
        }


    }

    
        cout << dp[n] ;


}

Measured memory_bytes: 1024
N=int(input())
if N ==3:
    print(2)
    print("1 3")
    print("2 3")

else:
    if N%2==0:
        if N == 4:print(4)
        else:
            print(N // 2 * 4)
        for i in range(1, N // 2):
            x = i
            y = N + 1 - x
            nx = x + 1
            ny = y - 1
            print(str(x) + ' ' + str(nx))
            print(str(x) + ' ' + str(ny))
            print(str(y) + ' ' + str(nx))
            print(str(y) + ' ' + str(ny))
        if N > 4:
            print(str(N) + ' ' + str(N//2))
            print(str(N) + ' ' + str(N//2 + 1))
            print(str(1) + ' ' + str(N//2))
            print(str(1) + ' ' + str(N//2 + 1))
    else:
        N -= 1
        print(N // 2 * 4)
        for i in range(1, N // 2):
            x = i
            y = N + 1 - x
            nx = x + 1
            ny = y - 1
            print(str(x) + ' ' + str(nx))
            print(str(x) + ' ' + str(ny))
            print(str(y) + ' ' + str(nx))
            print(str(y) + ' ' + str(ny))
        N += 1
        if N > 3:
            print(str(N) + ' ' + str(N//2))
            print(str(N) + ' ' + str(N//2 + 1))
            print(str(N) + ' ' + str(N - 1))
            print(str(N) + ' ' + str(1))

Measured memory_bytes: 3188
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){

  while(x->left != NIL)
    x = x->left;
  return x;

}

Node treeMaximum(Node x){

  

}

Node treeSearch(int k){

 Node x=root;
  int tt=0;
  while(x!=NIL)
{
    if(x->key==k) tt=1;
    if(k<x->key) x = x->left;
    else x = x->right;
  }
if(tt)printf("yes\n");
  else printf("no\n");
   

}

Node treeSuccessor(Node x){
    

}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y



}



void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

   if(x==NIL) root=z;
   else
     {
       while(x != NIL)
         {
           if(x->key >= k) y= x->left;

           else y= x->right;

      if(y!=NIL) y->parent=x;
      else
        {
          if(x->key >=k) x->left = z;
          else x->right = z;
        }
      x=y;  
             
         }
     }


}

void inorder(Node u){


if(u == NIL)return;

inorder(u->left);
printf(" %d",u->key);
inorder(u->right);

}
void preorder(Node u){


if(u == NIL)return;
      
  printf(" %d",u->key);
preorder(u->left);
preorder(u->right);


}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      treeSearch(x);
}
      else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }

  return 0;
}


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

int main(){
    int parts[300];
    int temp[1000][3];
    int tlen;
    int a,b,c,n;
    int torf;
    int N;
    int i;
    cin >> a >> b >> c;
    while(a||b||c){
        tlen = 0;
        n = a+b+c;
        for(i=0;i<n;i++){
            parts[i] = 2;
        }
        cin >> N;
        for(i=0;i<N;i++){
            cin >> a >> b >> c >> torf;
            a -= 1;
            b -= 1;
            c -= 1;
            if(torf){
                parts[a] = 1;
                parts[b] = 1;
                parts[c] = 1;
            }else{
                temp[tlen][0] = a;
                temp[tlen][1] = b;
                temp[tlen][2] = c;
                tlen++;
            }
        }
        for(i=0;i<tlen;i++){ 
            a = temp[i][0];
            b = temp[i][1];
            c = temp[i][2];
            if(parts[a] == 1 && parts[b] == 1){
                parts[c] = 0;
            }else if(parts[b] == 1 && parts[c] == 1){
                parts[a] = 0;
            }else if(parts[c] == 1 && parts[a] == 1){
                parts[b] = 0;
            }
        }
        for(i=0;i<n;i++){
            cout << parts[i] << endl;
        }
        cin >> a >> b >> c;
    }
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

int main() {
    int n, x;
    long long s = 0;
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        std::cin >> x;
        s += x;
    }
    s -= n;
    std::cout << s;
    return 0;
}


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

int main(){
    int i, M, N, n=0, l;
    cin >> N >> M;
    for(i=0; i<M; i++){
        cin >> l;
        n += l;
    }
    if(n>N){
        cout << "-1" << endl;
    } else{
        cout << N - n << endl;
    }
    return 0; 
}

Measured memory_bytes: 3624
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;

int abs(int x) {
	if (x >= 0) return x;
	else return -x;
}

int main() {
	int N;
	cin >> N;
	vector<int> a(N);
	REP(i, N) cin >> a[i];
	int res = 0;
	REP(i, N) {
		REP(j, N) {
			if (res < abs(a[i] - a[j])) res = abs(a[i] - a[j]);
		}
	}
	cout << res << endl;
	return 0;
}


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

int main(){
    int n;
    cin >> n;
    vector<int> h(n);
    rep(i, n) cin >> h[i];
    h.push_back(0);
    int ans = 0;
    for(int i = 1; i < n + 1; i++){
        if(h[i] < h[i - 1]) ans += h[i-1] - h[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>



using namespace std;
using ll = long long;
using ull = unsigned long long;

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

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















int main(){
    ll n;
    cin >> n;
    vector<ll> w(n);
    REP(i, n){
        cin >> w[i];
    }
    ll ans = INF;
    for(ll i = 0; i < n - 1; i++){
        ll sum1 = 0;
        for(ll j = 0; j <= i; j++){
            sum1 += w[j];
        }
        ll sum2 = 0;
        for(ll j = i + 1; j < n; j++){
            sum2 += w[j];
        }
        ans = min(ans, abs(sum2 - sum1));
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using std::max;
const int N=100005;
int a[N],b[N],c[N],dp[N][3],n;
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
	for (int i=1;i<=n;i++){
		dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i];
		dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i];
		dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i];
	}
	printf("%d",max(dp[n][0],max(dp[n][1],dp[n][2])));
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // std::ifstream in("input.txt");
    // std::cin.rdbuf(in.rdbuf());
    ll n, m;
    cin >> n >> m;
    if (n <= m) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    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 __gnu_pbds;
using namespace std;
#define Go_ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long int
#define llu long long unsigned int
#define pf printf
#define sf scanf
#define f first
#define s second
#define pb push_back
#define mk make_pair
#define pii pair<int ,int>
#define PII pair<ll ,ll>

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

typedef tree<pair<int,int>,null_type,less<pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
int Set(int N,int pos){return N=N | (1<<pos);}
int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}
const int Max=1e9+100;
const ll  MAX=1e18+500;
const int sz=1e6+100;


const ll mod=1e9+7;

ll dp[sz][2][2];
ll n;

ll cholo(ll id, bool bl1, bool bl2)
{
   if(id==n){
      if(bl1 && bl2) return 1;
      else return 0;
   }

   ll &ret=dp[id][bl1][bl2];
   if(~ret) return ret;

   ll sum=0;
   for(ll i=0;i<=9;i++){
      bool tb1=bl1;
      bool tb2=bl2;
      if(i==0) tb1=true;
      if(i==9) tb2=true;

      sum=(sum + cholo(id+1,tb1,tb2))%mod;
   }

   return (ret=sum);
}

int main()
{
    Go_
    int a,b,c,i,j,k,q,p,x,y,ct,ct1,m,l,r,x1,y1,mn,h,sum1,in,z,mid,mx;
    char ch;
    double d;
    string str1,str2,str;
    bool bl,bl1;
    int t,cs=1;
    
    cin>>n;
    memset(dp, -1 ,sizeof dp);
    ll ans=cholo(0, false,false);
    cout<<ans<<endl;
}


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

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 4e5 + 5;

typedef pair<int,int>   ii;

int p[N], a[N];
int t[N], v[N];

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

    int n;  cin >> n;
    ll  k;  cin >> k;

    memset(p,-1,sizeof p);

    for(int i = 0 ; i < n ; ++i)    cin >> a[i];
    for(int i = 0 ; i < n + n ; ++i)    {
        if (i >= n)
            a[i] = a[i - n];

        if (p[a[i]] >= 0)
            t[p[a[i]]] = i + 1;

        p[a[i]] = i;
    }

    ll  L = 0;
    ll  C = 0;
    int s = 0;

    do  {
        v[s] = 1;
        L += t[s] - s;
        s  = t[s] % n;
    }   while (v[s] < 1);

    do  {
        v[s] = 2;
        C += t[s] - s;
        s  = t[s] % n;
    }   while (v[s] < 2);

    L -= C;

    if (k * n >= L)
        L = (k * n - L) % C;
    else    {
        s = 0;
        L = k * n;
    }

    while (1)   {
        if (L >= t[s] - s)
            L -= t[s] - s,
            s  = t[s] % n;
        else
            break;
    }

    memset(p,0,sizeof p);

    vector<int> res;

    for(int i = 0 ; i < L ; ++i, s = (s + 1) % n)   {
        if(!p[a[s]])    {
            p[a[s]] = 1;
            res.pb(a[s]);
            continue;
        }
        while (p[a[s]])
            p[res.back()] = 0,
            res.pop_back();
    }
    for(int x : res)
        cout << x << " ";
}

Measured memory_bytes: 7924
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();
		if(B % A == 0) {
			System.out.println(A + B);
		} else {
			System.out.println(B - A);
		}
	}
}


Measured memory_bytes: 22740
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    int a;
    cin >> a;
    if(a == 1)cout << "Hello World" << endl;
    else {
        int b,c;
        cin >> b >> c;
        cout << b + c << endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
#include<math.h>
#include<bitset>
#include<iomanip>
using namespace std;

typedef stack<int> IntStack;
typedef queue<int> IntQueue;

const double pi = 3.141592653589793;


//文字0~9をint型0~9に変換
int char_to_int(char c)
{
	if (c == '0') return 0;
	if (c == '1') return 1;
	if (c == '2') return 2;
	if (c == '3') return 3;
	if (c == '4') return 4;
	if (c == '5') return 5;
	if (c == '6') return 6;
	if (c == '7') return 7;
	if (c == '8') return 8;
	if (c == '9') return 9;
	else return -1;
}
//a^b mod MODを計算
long long int ModPower(long long int a, long long int b, long long int MOD)
{
	if (b == 0) return 1;
	else if (b % 2 == 0)
	{
		long long int d = ModPower(a, b / 2, MOD);
		return (d*d) % MOD;
	}
	else
	{
		return (a*ModPower(a, b - 1, MOD)) % MOD;
	}
}
//nCr mod MODを計算
long long int ModCombi(long long int n, long long int r, long long int MOD)
{
	if (n == 0 || r == 0) return 1;

	long long int Kn=1, Kr=1, Knr=1;

	long long int temp = 1;
	for (long long int i = 1; i <= n; i++)
	{
		temp *= i;
		temp %= MOD;
		if (i == n) Kn = temp;
		if (i == r) Kr = temp;
		if (i == n - r) Knr = temp;
	}

	long long int x = ModPower(Kr, MOD - 2, MOD);
	long long int y = ModPower(Knr, MOD - 2, MOD);

	long long int ans;
	ans = Kn * x;
	ans %= MOD;
	ans *= y;
	ans %= MOD;

	return ans;
}


/*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*/

long long int N, M;
long long int a[100005];
long long int c[100005];
long long int p[100005];
long int mod = 1000000007;

int main()
{
	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> a[i];
		c[a[i]] = 1;
	}

	p[0] = 1;
	if (c[1] == 0) p[1] = 1;

	for (int i = 2; i <= N; i++)
	{
		if (c[i] == 0)
		{
			p[i] = p[i - 1] + p[i - 2];
			p[i] %= mod;
		}

	}

	cout << p[N];

	return 0;
}

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

#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false

int main()
{
   int a,b;
   cin>>a>>b;
   if(a%3==0||b%3==0||(a+b)%3==0){
       cout<<"Possible"<<endl;
   }else{
       cout<<"Impossible"<<endl;
   }
   return 0;
}

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

int main(){
    ll n,k;
    cin >> n >> k;
    ll a[n];
    for(ll i=0;i<n;i++) cin >> a[i];
    vector<ll> dp(n,1e12);
    dp[0]=0;
    for(ll i=1;i<n;i++){
        for(ll j=1;j<=k;j++){
            if(i-j<0) break;
            dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));
        }
    }
    cout << dp[n-1] << endl;
    return 0;
}


Measured memory_bytes: 4804
/*
    -ensure correct output format
    -ensure printing required output
    -reread the problem statement
  */

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pll;
typedef pair<ll,pair<ll,ll>>plll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define vll(v) v.begin(),v.end()
#define all(x) x.rbegin(),x.rend()
#define min3(a, b, c)   min(a, min(b, c))
#define max3(a, b, c)   max(a, max(b, c))
#define F first
#define S second
#define in  freopen("input.txt", "r", stdin)
#define out  freopen("output.txt", "w", stdout)
#define minheap int,vector<int>,greater<int>
#define pb push_back
#define eb emplace_back
#define ischar(x)  (('a' <= x && x <= 'z') || ('A' <= x && x <= 'Z'))
#define isvowel(ch) ((ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')||(ch=='A'|| ch=='E' || ch=='I'|| ch=='O'|| ch=='U'))
#define bug cout<<"BUG"<<endl;
const int Max = 2e6 + 10;
const int Mod = 1e9 + 7;
const double PI  =3.141592653589793238463;
bool compare(const pair<ll,ll> &a, const pair<ll,ll> &b)
{
       return (a.first > b.first);
}
ll lcm(ll a,ll b)
{
    if(a==0 || b==0)return 0;

    return a/__gcd(a,b)*b;
}

void input(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)cin>>ara[i];
}
void print(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)
        cout<<ara[i]<<" ";
    cout<<endl;
}


int main()
{

   fastread();

   ll i,j,n,m,p,a,sum=0,k,t,b,c,d,cnt=0,q,l,r,ans=0;

      bool flag=false;

      string str;

      cin>>n>>k;

      l=n-2;

      sum=(l*(l+1))/2;

      if(sum<k)
      {
          cout<<-1<<endl;

          return 0;
      }



        vector<pll>v;

        for(i=2; i<=n; i++)
        {
            v.eb(1,i);
        }

        k=sum-k;


          for(i=2; i<=n; i++)
          {
              for(j=i+1; j<=n && k; j++)
              {
                  v.eb(i,j);
                  k--;
              }
          }

        cout<<v.size()<<endl;

        for(auto x : v)
            cout<<x.F<<" "<<x.S<<endl;
}



Measured memory_bytes: 3756
import numpy as np

h, w, k = map(int, input().split())

c = []

for _ in range(h):
    s = input()
    yoko = [0 if i=='.' else 1 for i in s]
    c.append(yoko)

c = np.array(c)

ans = 0

# for i in range(h):
#     arr = np.copy(c)
#     arr[i,:] = 0 
#     if arr.sum() == k:
#         ans += 1
#         print(arr)

# for j in range(w):
#     arr = np.copy(c)
#     arr[:,j] = 0
#     if arr.sum() == k:
#         ans += 1
#         print(arr)

# ç¸¦
for i in range(2**h):
    arr = np.copy(c)
 
    s = str(bin(i))
    condition = s[2:].zfill(h)

    for i_h in range(h):
        if condition[i_h] == '0':
            arr[i_h] = 0

    # æ¨ª
    for j in range(2**w):
        arr2 = np.copy(arr)

        s = str(bin(j))
        condition = s[2:].zfill(w)

        for j_w in range(w):
                
            if condition[j_w] == '0':
                arr2[:,j_w] = 0

        if arr2.sum() == k:
            ans += 1

print(ans)

Measured memory_bytes: 27072
#include <iostream>
#include <map>
#include <vector>
#include <cstring>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <string>
#include <stack>
#include <set>
#include <deque>
#define mp make_pair
using namespace std;
int n,a[200005],b[500005];
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for (int i=0;i<n;i++) cin>>a[i];
	int s=250005,e=250004;
	for (int i=0;i<n;i++){
		if (i%2==0){
			e++;
			b[e]=a[i];
		}else{
			s--;
			b[s]=a[i];
		}
	}
	if (n%2==0){
		for (int i=s;i<=e;i++) cout<<b[i]<<' ';
	}else{
		for (int i=e;i>=s;i--) cout<<b[i]<<' ';
	}
	return 0;
}

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

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    string ans = "No";
    while(a > 0 && b > 0){
        c -= b;
        if(!(c > 0)){
            ans = "Yes";
            break;
        }
        a -= d;
        if(!(a > 0)){
            ans = "No";
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int h, a;
    cin >> h >> a;
    cout << (h+a-1)/a << "\n";
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(n);++i)
const int INF =1001001001;
using ll=long long;
using P = pair<int,int>;
using Graph =vector<string>;
Graph field;
queue<P> q;

int main() {
  ll n;
  ll sum=0;
  cin>>n;
  vector<ll> a(100001,0);
  rep(i,n){
    ll ab;
    cin>>ab;
    a[ab]++;
    sum+=ab;
  }
  ll q;
  queue<ll> que;
  cin>>q;
  rep(i,q){
    ll b,c;
    cin>>b>>c;
    a[c]+=a[b];
    sum+=(c-b)*a[b];
    a[b]=0;
    que.push(sum);
  }
  while(!que.empty()){
    cout<<que.front()<<endl;
    que.pop();
  }
}


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

typedef int in;
#define int long long
int MAX=1e9;
int MAXEST=1e18;
int MOD=1e9+7;

int n,w;
int v[105],s[105];
int dp[2][100005];

in main()
{
    int tc=1;
//    cin>>tc;
    while(tc--)
    {
        cin>>n>>w;
        for(int i=1;i<=n;i++){
            cin>>s[i]>>v[i];
        }
        for(int i=1;i<=n;i++){
            for(int j=0;j<=w;j++){
                dp[i&1][j]=dp[(i-1)&1][j];
                if(j>=s[i])
                    dp[i&1][j]=max(dp[i&1][j],dp[(i-1)&1][j-s[i]]+v[i]);
            }
        }
        cout<<dp[n&1][w]<<endl;
    }
    return 0;
}


Measured memory_bytes: 5168