akhauriyash/Code-Regression huggingface dataset:
/*
~Like a small boat
~On the ocean
~Sending big waves
~Into motion
!Like how a single word
!Can make a heart open
!I might only have one match
!But I can make an explosion
#And all those things I didn't say
#Wrecking balls inside my brain
#I will scream them loud tonight
#Can you hear my voice this time?
@This is my fight song
@Take back my life song
@Prove I'm alright song
@My power's turned on
$Starting right now I'll be strong
$I'll play my fight song
$And I don't really care if nobody else believes
$'Cause I've still got a lot of fight left in me!!!
*/

#include "bits/stdc++.h"
using namespace std;

#define  F  first
#define  S  second
#define  mp make_pair
#define  pb push_back
typedef long long int ll;
const int N = 2e5+5,mod = 1e9+7;
ll Arr[N],T[2*N],n;

void updt( int idx )
{
    while(idx<=N)
    {
        T[idx] += 1;
        idx += (idx&-idx);
    }
}

ll qry( int idx )
{
    ll Ret = 0;
    while(idx>0)
    {
        Ret += T[idx];
        idx -= (idx&-idx);
    }
    return Ret;
}

bool Ok( ll x )
{
    ll now = 0,cur = n,total = (n*(n+1))/2;
    memset( T,0,sizeof T );
    updt(cur);
    for(int i=1;i<=n;i++)
    {
        if( Arr[i]>=x )++cur;
        else --cur;
        now += qry(cur);
        updt(cur);
    }
    return 2*now>=total;
}

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

    cin>>n;
    int Brr[n+2];
    Brr[0] = 0;
    for(int i=1;i<=n;i++)
    {
        cin>>Arr[i];
        Brr[i] = Arr[i];
    }
    sort(Brr+1,Brr+n+1);
    *Brr = unique(Brr+1,Brr+n+1)-Brr-1;
    int lo = 1,hi = *Brr,mid,now = 0;
    while(lo<=hi)
    {
        mid = (lo+hi)>>1;
        //cout<<mid<< "*\n";
        if( Ok(Brr[mid]) )lo = mid+1,now = mid;
        else hi = mid-1;
    }
    cout<<Brr[now]<< "\n";










    return 0;
}



Measured memory_bytes: 4736
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

double dp[304][304][304];
int a[4];
int main(){
    int n,ai;
    cin>>n;
    rep(i,n){
        cin>>ai;
        ++a[ai-1];
    }
    rep(i,n+1)rep(j,n+1)rep(k,n+1){
        int c=i+j+k;
        if(c==0) continue;
        if(k!=0) dp[k][j][i]+=dp[k-1][j][i]*k;
        if(j!=0) dp[k][j][i]+=dp[k+1][j-1][i]*j;
        if(i!=0) dp[k][j][i]+=dp[k][j+1][i-1]*i;
        dp[k][j][i]+=n;
        dp[k][j][i]/=c;
    }
    cout<<setprecision(10)<<fixed<<dp[a[0]][a[1]][a[2]]<<endl;
    return 0;
}


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

class Program
{
    static void Main()
    {
        FastScanner sc = new FastScanner(Console.OpenStandardInput());
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] A = sc.intArray(N);
        Array.Sort(A);
        Array.Reverse(A);
        int accum = A.Sum();
        Console.WriteLine((accum + 4 * M - 1) / (4 * M) <= A[M - 1] ? "Yes" : "No");
        return;
    }
}

// FastScanner start
public class FastScanner
{
    public readonly Stream str;
    private readonly byte[] buf = new byte[1024];
    private int len, ptr;
    public bool isEof = false;
    public FastScanner(Stream stream)
    {
        str = stream;
    }
    private T[] enumerate<T>(int n, Func<T> f)
    {
        var a = new T[n];
        for (int i = 0; i < n; ++i) a[i] = f();
        return a;
    }
    public char nextChar()
    {
        byte b = 0;
        do
        {
            b = read();
        }
        while ((b < 33 || 126 < b) && !isEof);
        return (char)b;
    }
    public int nextInt()
    {
        return (isEof) ? int.MinValue : (int)nextLong();
    }
    public long nextLong()
    {
        if (isEof)
        {
            return long.MinValue;
        }
        long ret = 0;
        byte b = 0;
        var ng = false;
        do
        {
            b = read();
        }
        while (b != '-' && (b < '0' || '9' < b));
        if (b == '-')
        {
            ng = true;
            b = read();
        }
        for (; true; b = read())
        {
            if (b < '0' || '9' < b)
            {
                return ng ? -ret : ret;
            }
            else ret = ret * 10 + b - '0';
        }
    }
    public int[] intArray(int n)
    {
        return enumerate(n, nextInt);
    }
    public long[] longArray(int n)
    {
        return enumerate(n, nextLong);
    }
    public char[] charArray(int n)
    {
        return enumerate(n, nextChar);
    }
    public string Scan()
    {
        var sb = new StringBuilder();
        for (var b = nextChar(); b >= 33 && b <= 126; b = (char)read())
        {
            sb.Append(b);
        }
        return sb.ToString();
    }
    private byte read()
    {
        if (isEof)
        {
            return 0;
        }
        if (ptr >= len)
        {
            ptr = 0;
            if ((len = str.Read(buf, 0, 1024)) <= 0)
            {
                isEof = true;
                return 0;
            }
        }
        return buf[ptr++];
    }
}
// FastScanner end

Measured memory_bytes: 26156
#include <bits/stdc++.h>
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define foreach(i,n) for(auto &&i:n)
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort(all(x))
#define REV(x) reverse(all(x))
#define MAX(x) *max_element(all(x))
#define MIN(x) *min_element(all(x))
#define LOWitr(x, n) lower_bound(all(x), n)
#define UPRitr(x, n) upper_bound(all(x), n)
#define cii(x) int x;cin >> x
#define cill(x) LL x;cin >> x
#define cis(x) string x;cin >> x
#define co(x) cout << x << endl
#define dump(x)  cout << #x << " = " << (x) << endl
#define truecheck assert
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef long long int64;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
template<class T,class U>bool chmax(T &a, const U &b){if (a<b){a=b;return true;}return false;}
template<class T,class U>bool chmin(T &a, const U &b){if (b<a){a=b;return true;}return false;}
template<class T,class U>void vcin(T &v, U n){rep(i, n){typename T::value_type a;cin >> a;v.pb(a);}}
const int INF = 1e9, MOD = 1e9 + 7;
const LL LLINF = 1e16;

const double PI=3.14159265358979323846;
int main() {
    fastcin();
    cout << fixed << setprecision(10);
    cill(n);
    cill(m);
    VI vi;
    rep(i, m){
        cill(a);
        n -= a;
    }
    LL ans = (n >= 0)?n:-1;
    co(ans);

    return 0;
}

Measured memory_bytes: 3652
<?php                                                                                                                                                                                                                                                                                                                          
                                                                                                                                                                                                                                                                                                                               
function fget_array() {                                                                                                                                                                                                                                                                                                        
    return explode(' ', trim(fgets(STDIN)));                                                                                                                                                                                                                                                                                   
}                                                                                                                                                                                                                                                                                                                              
                                                                                                                                                                                                                                                                                                                               
$n = fget_array()[0];                                                                                                                                                                                                                                                                                                          
echo pow($n, 3);                                                                                                                                                                                                                                                                                                               
?>

Measured memory_bytes: 4856
fun main(args : Array<String>) {
    val (n, a, b) = readLine()!!.split(" ").map { it.toLong() }
    val xx = readLine()!!.split(" ").map { it.toLong() }
    val dp = LongArray(n.toInt()) { 0L }

    for (i in 0..n.toInt()-2) {
        dp[i+1] = dp[i] + Math.min((xx[i+1]-xx[i])*a, b)
    }

    println(dp[n.toInt()-1])
}

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

int main()
{ ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin>>s;
    int i;
    for(i=1;i<=s.length();i++)
     if(i&1)
     cout<<s[i-1];
	return 0;
	
}

Measured memory_bytes: 592
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

void selsort(string  a[], int n){
  for(int i = 0; i < n; i++){
    int minj = i;
    for(int j = i; j < n; j++)
      if(a[j][1] < a[minj][1]) minj = j;
    swap(a[i], a[minj]);
  }
}

void bsort(string  A[],int n){
  bool flag = 1;
  while(flag){
    flag = 0;
    for(int j = n-1; j >= 1; j--){
      if(A[j][1] < A[j-1][1]){
	swap(A[j],A[j-1]);
	flag = 1;
      }
    }
  }
}

int main(){
  string card[36],s[36],b[36];
  
  int n,c=0;
  cin>>n;
  for(int i = 0; i < n; i++){
    cin>>card[i];
    s[i]=card[i];
    b[i]=card[i];
  }
  
  bsort(b,n);
  selsort(s,n);
  
  for(int i = 0; i < n-1; i++)cout<<b[i]<<" ";
  cout<<b[n-1]<<endl<<"Stable"<<endl;
  for(int i = 0; i < n-1; i++)cout<<s[i]<<" ";
  cout<<s[n-1]<<endl;
  for(int i = 0; i < n; i++)if(b[i]==s[i])c++;
  if(c==n)cout << "Stable" << endl;
  else cout << "Not stable" << endl;
  return 0;
}



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

struct Node {
    std::vector<int> neighbors;
    std::vector<int *> edges;
};

int depth_first_search(const int node, const int parent, const int used_color, std::vector<Node> &nodes) {
    auto current_node = nodes[node];
    int color = 1;
    int max_color = current_node.neighbors.size();

    for(uint32_t i = 0; i < current_node.neighbors.size(); ++i) {
        const auto neighbor = current_node.neighbors[i];
        const auto p_edge = current_node.edges[i];

        if(neighbor == parent) {
            continue;
        }
        if(used_color == color) {
            ++color;
        }

        *p_edge = color;

        max_color = std::max(max_color, depth_first_search(neighbor, node, color, nodes));

        ++color;
    }

    return max_color;
}

int main() {
    int64_t n;
    std::cin >> n;

    auto nodes = std::vector<Node>(n, Node());
    auto edges = std::vector<int>(n - 1, 0);

    for(int i = 0; i < n - 1; ++i) {
        int a, b;
        std::cin >> a >> b;
        --a;
        --b;
        nodes[a].neighbors.push_back(b);
        nodes[a].edges.push_back(&edges[i]);
        nodes[b].neighbors.push_back(a);
        nodes[b].edges.push_back(&edges[i]);
    }

    const int max_color = depth_first_search(0, 0, 0, nodes);

    std::cout << max_color << std::endl;
    for(const auto e: edges) {
        std::cout << e << std::endl;
    }

    return 0;
}


Measured memory_bytes: 17920
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;

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

    vector<int64_t> a(n);
    vector<bool> f(n);
    int64_t prev = -1;
    for (auto&& aa : a) {
        cin >> aa;

        if (aa == prev + 1) {
            f[prev - 1] = true;
        }

        prev = aa;
    }

    int64_t ans = 0;
    for (auto i : irange(0L, n)) {
        int64_t b;
        cin >> b;
        ans += b;
    }

    for (auto i : irange(0L, n - 1)) {
        int64_t c;
        cin >> c;
        if (f[i]) {
            ans += c;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
 
int AA(int,int);
 
int A[20],n;
main(){
  int i,j,q,x,m[200];
   
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&m[i]);
  }
  for(i=0;i<q;i++){
    x= AA(0,m[i]);
   if(x==1){
     printf("yes\n");
     x=0;
   }
   else{
     printf("no\n");
   }
  }
  return 0;
}
 
int AA(int i,int m){
  int bb;
  if(m==0){
    return 1;
  }
  else if(i>n){
    return 0;
  }
  else{
    bb = AA(i+1,m)||AA(i+1,m-A[i]);
    return bb;
  }
}

Measured memory_bytes: 580
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;


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

	long long n, i, j, k, ans, MOD = 1000000007;
	cin >> n;
	vector<long long> a(n), v(n), ct(n + 1, 0);
	ans = 1;
	for (i = 0; i < n; i++) {
		cin >> a[i];

		if (a[i] == 0) v[i] = 3 - ct[0];
		else v[i] = ct[a[i] - 1] - ct[a[i]];
		ct[a[i]]++;

		ans = (ans * v[i]) % MOD;
	}
	cout << ans << "\n";
		
	return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using i64 = long long;

bool isPrime(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int n;
    std::cin >> n;
    for (int i = 11, j = 0; j < n; i += 10) if (isPrime(i) && ++j) std::cout << i << ' ';
    std::cout << std::endl;
    
    return 0;
}

Measured memory_bytes: 256
import java.io.InputStream;
import java.io.PrintStream;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        solve(System.in, System.out);
    }

    static void solve(InputStream is, PrintStream os) {
        // Your code here!
        Scanner scan = new Scanner(is);
        int A = scan.nextInt();
        int B = scan.nextInt();

        if(A <= 9 && A >= 1 && B <= 9 && 1 <= B)
            os.println(A*B);
        else
            os.println(-1);
    }
}

Measured memory_bytes: 22996
N, X = [int(a) for a in input().split(" ")]
numt = [1]*51
nump = [0]*51
for i in range(1,51):
    numt[i]=2*numt[i-1]+3
    nump[i]=2*nump[i-1]+1

def rec(n, i):
    if n==0:
        return 1
    if i==0:
        return 0
    elif i==numt[n]-1:
        return 2*nump[n]+1
    mid = numt[n]//2
    if i==mid:
        return 1+nump[n]
    elif i>mid:
        return rec(n-1, i-mid-1)+nump[n]+1
    else:
        return rec(n-1, i-1)
    
print(rec(N, X-1))

Measured memory_bytes: 38384
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int H = sc.nextInt();
    int N = sc.nextInt();
    int[] A = new int[N+1];
    int total =0;
    for (int i=1; i<=N; i++) {
      A[i] = sc.nextInt();
      total += A[i];
    }
    if (total >= H) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }
}
    

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

public class hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var d = int.Parse(line[0]);
        var n = int.Parse(line[1]);
        var dp = new int[d, n];
        var temp = new int[d];
        for (int i = 0; i < d; i++)
            temp[i] = int.Parse(Console.ReadLine().Trim());
        var hade = new int[n];
        for (int i = 0; i < n; i++)
        {
            string[] line2 = Console.ReadLine().Trim().Split(' ');
            var a = int.Parse(line2[0]);
            var b = int.Parse(line2[1]);
            hade[i] = int.Parse(line2[2]);
            for (int j = 0; j < d; j++)
            {
                if (a <= temp[j] && b >= temp[j]  ) dp[j, i] = -1;
                else dp[j, i] = -99;
            }
        }
        for (int i = 1; i < d; i++)
            for (int j = 0; j < n; j++)
            {
                if (dp[i,j] == -1)
                {
                    var telist = new List<int>();
                    for (int k = 0; k < n; k++)
                    {
                        if (dp[i - 1, k] != -99) telist.Add(DP(dp, i - 1, k) + Math.Abs(hade[j] - hade[k]));
                    }
                    if (telist.Count() != 0) dp[i, j] = telist.Max();
                    else dp[i, j] = 0;
                }
            }
        var anslist = new List<int>();
        for (int i = 0; i < n; i++) anslist.Add(dp[d - 1, i]);
        Console.WriteLine(anslist.Max());
    }
    public static int DP (int[,] dp ,int i ,int j)
    {
        if (dp[i, j] == -1) return 0;
        else return dp[i, j];
    }
}

Measured memory_bytes: 9732
n, t = map(int, input().split())
route = [list(map(int, input().split())) for _ in range(n)]
ans = float("inf")
for r in route:
	if r[1] <= t:
		ans = min(ans, r[0])

if ans == float("inf"):
	print("TLE")
else:
	print(ans)

Measured memory_bytes: 38256
n, y = map(int, input().split())
forend = 0
for i in range(n+1):
 for j in range(n+1-i):
  if y-10000*i-5000*j == 1000*(n-i-j):
   print(i, j, n-i-j)
   forend = 1
   break
 if forend==1: break
 if i==n: print("-1 -1 -1")

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+5;
const int mod=1e9+7;
inline int read(){
	char c=getchar();int t=0,f=1;
	while((!isdigit(c))&&(c!=EOF)){if(c=='-')f=-1;c=getchar();}
	while((isdigit(c))&&(c!=EOF)){t=(t<<3)+(t<<1)+(c^48);c=getchar();}
	return t*f;
}
int n;
vector<int> g[maxn];
inline void add(int a,int b){
	g[a].push_back(b);
	g[b].push_back(a);
}
int sz[maxn],rec[maxn],inv[maxn];
inline int ksm(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;b>>=1;
	}
	return ans;
}
inline int C(int n,int m){
	return rec[n]*inv[m]%mod*inv[n-m]%mod;
}
int f[maxn];
vector<int> o[maxn];
bool cmp(int a,int b){
	return sz[a]<sz[b];
}
void dfs(int u,int fa){
	sz[u]=0;f[u]=1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa)continue;
		dfs(v,u);
	}
	sort(g[u].begin(),g[u].end(),cmp);
	for(int i=0;i<g[u].size();i++){
		int tmp=0;o[u].push_back(1);
		int v=g[u][i];
		if(v==fa)continue;
		sz[u]+=sz[v];
		f[u]=f[u]*C(sz[u],sz[v])%mod*f[v]%mod;
		if(i>0&&(sz[v]==sz[g[u][i-1]])&&(g[u][i-1]!=fa)){
			o[u][i]=o[u][i-1]*ksm(f[v],mod-2)%mod*f[g[u][i-1]]%mod;
			continue;
		}
		for(int j=0;j<g[u].size();j++){
			if(i==j)continue;
			int v=g[u][j];
			if(v==fa)continue;
			tmp+=sz[v];
			o[u][i]=o[u][i]*C(tmp,sz[v])%mod*f[v]%mod;
		}
	//	printf("%lld %lld %lld\n",u,g[u][i],o[u][i]);
	}
	sz[u]++;
}
int ans[maxn],e[maxn];
void dp(int u,int fa){
	//printf("%lld %lld %lld %lld\n",u,fa,f[u],e[fa]);
	ans[u]=f[u]*C(n-1,n-sz[u])%mod*e[fa]%mod;
	int tmp=0;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa)continue;
		e[u]=C(n-sz[v]-1,n-sz[u])*e[fa]%mod*o[u][i]%mod;
		dp(v,u);
	}
}
signed main(){
	rec[0]=inv[0]=1;
	n=read();
	for(int i=1;i<=n;i++)rec[i]=rec[i-1]*i%mod;
	inv[n]=ksm(rec[n],mod-2);
	for(int i=n-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%mod;
	for(int i=1;i<n;i++){
		int a=read(),b=read();
		add(a,b);
	}
	/*dfs(1,0);
	for(int i=1;i<=n;i++)printf("%lld ",f[i]);
	puts("");
	for(int u=1;u<=n;u++){ans[u]=f[u]*C(n-1,n-sz[u])%mod;printf("%lld\n",ans[u]);}*/
	/*for(int i=1;i<=n;i++){
		dfs(i,0);
		printf("%lld\n",f[i]);
	}*/
	dfs(1,0);
	for(int i=0;i<=n;i++)e[i]=1;
	dp(1,0);
	for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
	return 0;
}


Measured memory_bytes: 36720
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
#define pq_pair_tB priority_queue <pair<ll,ll>, vector<pair<ll,ll> > , greater<pair<ll,ll> > >
#define pq_pair_ts priority_queue <pair<ll,ll> > //第二成分の大きさが関係ない
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}

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

    ll N, K;
    cin >> N >> K;

    ll ti = 0;
    ll ha = 0;

    for(ll i = 1; i <= N; i++){
        if(i % K == 0) ti ++;
        if( K%2==0 && i%K==K/2) ha ++;
    }

    cout << ti * ti * ti + ha * ha * ha << endl;

    cerr << ti << " " << ha << endl;

	//cout << fixed << setprecision(16) << ans << endl;
	return 0;
}
//35897 932 114191


Measured memory_bytes: 256
//Author rahuliitkgp
/*A thing of beauty is a joy forever,
Its loveliness increases,
it will never pass into nothingness.*/
//Men at Work :)
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;

#define ff              first
#define ss              second
#define SZ(x)           ((int)(x).size())
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define mod             1000000007
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

void cpp() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}

int main() {
	cpp();
	ll n, w;
	cin >> n >> w;
	vector<ll> wei(n);
	vector<ll> val(n);
	for (ll i = 0; i < n; i++) {
		cin >> wei[i] >> val[i];
	}
	vector<vector<ll> > dp(n + 1, vector<ll>(w + 1, 0));
	for (ll j = 1; j <= w; j++) {
		for (ll i = 1; i <= n; i++) {
			dp[i][j] = dp[i - 1][j];
			if (wei[i - 1] <= j) {
				dp[i][j] = max(dp[i][j], (val[i - 1] + dp[i - 1][j - wei[i - 1]]));
			}
		}
	}
	cout << dp[n][w] << endl;
	return 0;
}




Measured memory_bytes: 80256
def check(st) : 
  
   
    n = len(st) 
    digitSum = 0
      
    for i in range(0,n) : 
        digitSum = digitSum + (int)(st[i]) 
  
    return (digitSum % 9 == 0) 
  

st = input()
  
if(check(st)) : 
    print("Yes") 
else :  
    print("No") 
      

Measured memory_bytes: 9160
#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
int N;
int P[20];
int main(){
  int i, res=0;
  rd(N);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=0;Lj4PdHRW<N;Lj4PdHRW++){
      rd(P[Lj4PdHRW]);
    }
  }
  for(i=1;i<N-1;i++){
    if(P[i-1] < P[i]  &&  P[i] < P[i+1]){
      res++;
    }
    if(P[i-1] > P[i]  &&  P[i] > P[i+1]){
      res++;
    }
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20190626-1

// --- original code ---
// int N, P[20];
// {
//   int i, res = 0;
//   rd(N,P(N));
//   rep(i,1,N-1){
//     if(P[i-1] < P[i] < P[i+1]) res++;
//     if(P[i-1] > P[i] > P[i+1]) res++;
//   }
//   wt(res);
// }


Measured memory_bytes: 256
/*author: hyperion_1724
  date: 
*/

//Required Libraries

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

//Required namespaces

using namespace std;
using namespace __gnu_pbds;

//Required defines

#define endl '\n'

#define READ(X) cin>>X;
#define READV(X) long long X; cin>>X;
#define READAR(A,N) long long A[N]; for(long long i=0;i<N;i++) {cin>>A[i];}
#define rz(A,N) A.resize(N);
#define sz(X) (long long)(X.size())
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define trav(x,A) for(auto &x:A)
#define veci vector<int>
#define vecl vector<long long>
#define FORI(a,b,c) for(long long a=b;a<c;a++)
#define FORD(a,b,c) for(long long a=b;a>c;a--)

//Required typedefs

typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<long long,null_type,greater<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set1;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<long,long> pll;

//Required Constants

const long long inf=(long long)1e18;
const long long MOD=(long long)(1e9+7);
const long long INIT=(long long)(1e6+1);

//Required Functions

ll power(ll x,ll y) 
{ 
    if (y == 0) 
        return 1; 
    ll p = power(x, y/2) % MOD; 
    p = (p * p) % MOD; 
  
    return (y%2 == 0)? p : (x * p) % MOD; 
}
ll modInverse(ll a) 
{ 
   return power(a,MOD-2); 
   
}

//Work

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

	READV(N);
	READAR(A,N);
	ll prev=inf;
	FORD(i,N-1,-1)
	{
		if (prev>=A[i])
		{
			prev=A[i];
		}
		else
		{
			A[i]--;
			prev=A[i];
		}
	}
	bool flag=true;
	FORI(i,1,N)
	{
		if (A[i]<A[i-1])
		{
			flag=false;
		}
	}
	if (flag)
	{
		cout<<"Yes"<<endl;
	}
	else
	{
		cout<<"No"<<endl;
	}

	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <functional>
#include <bitset>
#include <utility>
#include <sstream>
#include <fstream>
#include <stack>
#include <cstdlib>
#include <complex>
#include <set>

using namespace std;

#define INF 1070000000LL
#define pb push_back
#define irep(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) irep(i,0,n)

typedef long long lint;
typedef pair<int, int> pint;
struct Edge{
    int to,weight;
};
typedef vector<vector<Edge> > Graph;


int main(){
    int a,b;
    cin >> a >> b;
    if(a > b)cout << a*2-1 << endl;
    else if(a == b)cout << a*2 << endl;
    else cout << b*2-1 << endl;
    return 0;
}


Measured memory_bytes: 888
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;
import java.awt.Point;

public class Main {
    // static int INF = (1 << 30) - 1;
    // static long L_INF = (1L << 62) - 1;
    // static long MOD = (long) 1e9 + 7;

    static class Solver {
        int X, Y;
        // int[] A;

        // write your code
        void solve(InputReader in, PrintWriter out) {
            X = in.nextInt();
            Y = in.nextInt();
            // A = new int[N];
            // for (int i = 0; i < N; i++) {
            // A[i] = in.nextInt();
            // }

            boolean ans = false;
            for (int i = 0; i <= X; i++) {
                int j = X - i;
                int leg = 2 * i + 4 * j;
                if (Y == leg) {
                    ans = true;
                    break;
                }
            }
            if (ans) {
                out.println("Yes");
            } else {
                out.println("No");
            }
        }

        void debug(Object... os) {
            System.err.println(Arrays.deepToString(os));
        }
    }

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Solver solver = new Solver();
        solver.solve(in, out);
        out.close();
    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}


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

#define ll long long
using namespace std;

vector<vector<ll>> sticks;
vector<ll> ans;

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

ll solve(int x) {
    if (x == 0) return 1;
    x--;
    ll l = solve(sticks[x][2]);
    ll r = solve(sticks[x][3]);
    ll GCD = gcd(l * sticks[x][0], r * sticks[x][1]);
    ll min_power = l * sticks[x][0] * r * sticks[x][1] / GCD;
    ans[x] = min_power / sticks[x][0] + min_power / sticks[x][1];
    return min_power / sticks[x][0] + min_power / sticks[x][1];
}

int main() {
    while(true){
        int n;
        cin >> n;
        if(n == 0) break;
        
        vector<bool> hanged(n + 1);
        sticks = vector<vector<ll>>(n, vector<ll>(4));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 4; j++)cin >> sticks[i][j];
            hanged[sticks[i][2]] = true;
            hanged[sticks[i][3]] = true;
        }
    
        ans = vector<ll>(n);
        for (int i = 1; i <= n; i++) {
           if (!hanged[i])cout << solve(i) << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3124
using System;

class Program
{
    static void Main(string[] args)
    {
        int result = 0;
        Console.ReadLine();
        foreach(var item in Console.ReadLine().Split(' '))
        {
            var num = int.Parse(item);
            while (0 == num % 2)
            {
                ++result;
                num /= 2;
            }
        }
        Console.WriteLine(result.ToString());
    }
}


Measured memory_bytes: 13792
#include<bits/stdc++.h>
using namespace std;
 
void __print(int x) {cout << x;}
void __print(long x) {cout << x;}
void __print(long long x) {cout << x;}
void __print(unsigned x) {cout << x;}
void __print(unsigned long x) {cout << x;}
void __print(unsigned long long x) {cout << x;}
void __print(float x) {cout << x;}
void __print(double x) {cout << x;}
void __print(long double x) {cout << x;}
void __print(char x) {cout << '\'' << x << '\'';}
void __print(const char *x) {cout << '\"' << x << '\"';}
void __print(const string &x) {cout << '\"' << x << '\"';}
void __print(bool x) {cout << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cout << '{'; __print(x.first); cout << ','; __print(x.second); cout << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}
void _print() {cout << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cout << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
#define int long long int
#define fi first
#define se second
#define FIO {ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);}
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define all(x) (x).begin(), (x).end()
#define pow10(n) stoll("1"+string(n,'0'))
//fill(all(arr),1)
//if(map.count(key)){}
//bitset<20>(n);
//int mini=min({a,b,c,d,e});
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef long double ld;

int32_t main(){
	FIO
	string s,t;
	cin>>s>>t;
	int fl=1;
	forn(i,s.size())
	{
		if(s[i]==t[i])fl*=1;
		else fl*=0;
	}
	if(fl)cout<<"Yes";
	else cout<<"No";
	
	return 0;
}

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


int main(){
  ll n,m;
  cin >> n >> m;
  vector<ll> x(m);
  rep(i,m) cin >> x.at(i);
  sort(x.begin(),x.end());
  vector<ll> dif;
  for(int i=1;i<m;i++){
    dif.push_back(abs(x.at(i)-x.at(i-1)));
  }
  sort(dif.begin(),dif.end());
  
  if( n >= m ){
    cout << 0 << endl;
    return 0;
  }
  ll num = m-n;
  ll ans = 0;
  rep(i,num){
    ans += dif.at(i);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 2168
// you should probably see at the bottom ..
#include<bits/stdc++.h>

#ifdef LOCAL
#include "prabh.hpp"
#endif

#define int long long
#define pb push_back
#define range(v) v.begin(),v.end()
#define rrange(v) v.rbegin(), v.rend()
#define mod (int)(1e9 + 7)
#define inf (int)(1e15)
#define N (int)(2e5 + 10)

using namespace std;

void solve() {
	int n; cin >> n;
	vector<int> a(n);
	for (int &i : a) cin >> i;
	int ans = 0;
	int pref = 0;
	for (int &i : a) {
		ans += (pref * i) % mod, ans %= mod;
		pref += i, pref %= mod;
	}

	cout << ans << endl;
}

int32_t main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cin.tie(nullptr);
	int t_c = 1;
//	cin >> t_c;
	while (t_c--)
		solve();
}

/*
 * COME ON DUDE .... DONT GET UP UNTIL U GET THE SOLUTION
 * GIVING UP NOT GONNA HELP .. JUST GET YOUR ASS TO WORK ALREADY ..
 * AND FOR FUCKING SAKE ... DONT PANIC !!
*/


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

int main(void)
{
	int n;
	std::cin>>n;
	int tx = n, c2 = 0;
	while(tx)
	{
		if((tx % 10) == 2)
		c2++;
		tx /= 10;	
	}
	std::cout<<c2<<"\n";
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using ull=unsigned long long int;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
const ll mod=1000000007;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
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 (a>b) { a=b; return 1; } return 0; }
vector<bool> prime;
void make(int num){
    prime.resize(num,true);
    prime[0]=false;
    for(int i=0;i*i<num;i++){
        if(prime[i]){
            for(int j=2;(i+1)*j<=num;j++){
                prime[(i+1)*j-1]=false;
            }
        }
    }
}
int main(){
make(1300000);
V<ll> prim;
for(int i=1;i<1300000;i++)if(prime[i])prim.emplace_back(i+1);
int m=prim.size();
while(1){
  ll n;
  cin>>n;
  if(n==0)return 0;
  if(prime[n-1]){
    cout<<0<<"\n";
    continue;
  }
  int ind=lower_bound(all(prim),n)-prim.begin();
  cout<<prim[ind]-prim[ind-1]<<"\n";
}
}


Measured memory_bytes: 3904
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int main()
{
    long long a, b, c, d, e, f;
    scanf("%lld %lld", &a,&b);
    /*if (a>b)
{
    e=a;
    a=b;
    b=e;
}
if (c>d)
{
    e=c;
    c=d;
    d=e;
}

//if (c%2==0)
printf("%lld",a+c);
//else*/
c=(a-1)*(b-1);
if (a==0 || b==0)c=0;

    printf("%lld", c);
}


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

int h(int x){
    int ans=0;
    while(x){
        ans+=x%10;
        x/=10;
    }
    return ans;
}

int main(){
    int N;
    cin>>N;
    if(N%h(N)==0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    return 0;
}

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

using namespace std;

int main(){
	string a;
	string b;
	cin>>a>>b;
	int top =0;
	for(int i = 0;i<a.size();i++){
		if(a[i]==b[i]){
			top++;
		}
	}
	cout<<top;
}


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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N,M;
int H[100];

vint calc(vpint a){
    vector<int>dp(100000+1,INT_MAX);
    dp[0]=0;
    for(int i=0;i<a.size();i++){
        for(int j=0;j<=100000;j++){
            chmin(dp[min(100000ll,j+a[i].se)],dp[j]+a[i].fi);
        }
    }

    for(int i=100000;i>0;i--)chmin(dp[i-1],dp[i]);
    return dp;
}

void solve(){
    rep(i,N)cin>>H[i];
    cin>>M;

    vector<pint>s,a;

    rep(i,M){
        string str;
        int m,d;
        cin>>str>>m>>str>>d;
        if(str=="Single")s.pb({m,d});
        else a.pb({m,d});
    }

    vector<int>ss,aa;
    ss=calc(s);
    aa=calc(a);

    int ans=LLONG_MAX;
    for(int i=0;i<=100000;i++){
        int sum=0;
        sum+=aa[i];
        for(int j=0;j<N;j++){
            if(H[j]>i)sum+=ss[H[j]-i];
        }
        chmin(ans,sum);
    }
    cout<<ans<<endl;
}

signed main(){
    while(cin>>N,N)solve();
    return 0;
}

Measured memory_bytes: 4364
/*  Isn't it lovely, all alone?             */
/*  Heart made of glass, my mind of stone   */
/*  Tear me to pieces, skin to bone         */
/*  Hello, welcome home                     */

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag,
             tree_order_statistics_node_update>
    indexed_set;
ll mod=1000000007;


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

ll t=1;
//cin>>t;
while(t--)
{

ll n;
cin>>n;

ll k=ceil(n/1000.0);

cout<<(ll)(k*1000-n)<<endl;
}
return 0;
}
















Measured memory_bytes: 3764
#include <bits/stdc++.h>
#define N 200010
#define int long long
#define lson l,mid,o<<1
#define rson mid+1,r,o<<1|1
#define Ls(o) t[o].ls
#define Rs(o) t[o].rs
#define For(i,x,y) for(int i=(x);i<=(y);++i)
#define Rof(i,x,y) for(int i=(x);i>=(y);--i)
#define mcpy(x,y) memcpy(x,y,sizeof(x))
#define mset(x,y) memset(x,y,sizeof(x))
#define pii pair<int,int>
#define mp make_pair 
#define fr first
#define sd second 
using namespace std;
int a[N],b[N];
priority_queue< pii > q;
main(){
	int n,ans=0;
	scanf("%d",&n);
	For(i,0,n-1) scanf("%lld",&a[i]);
	For(i,0,n-1) scanf("%lld",&b[i]),q.push(mp(b[i],i));
	while(!q.empty()){
		pii x=q.top();q.pop();
		if(b[x.sd]==a[x.sd]) continue;
		int tmp=b[(x.sd+1)%n]+b[(x.sd-1+n)%n];
		if(b[x.sd]-tmp<a[x.sd]) return puts("-1"),0;
		ans+=(b[x.sd]-a[x.sd])/tmp;
		b[x.sd]-=1ll*(b[x.sd]-a[x.sd])/tmp*tmp;
		if(b[x.sd]!=a[x.sd]) q.push(mp(b[x.sd],x.sd));
	} printf("%lld\n",ans);
}


Measured memory_bytes: 9072
#include <iostream>
using std::endl;
using std::cout;
using std::cin;

int main() {
    int x;
    int i = 1;
    while (1) {
        cin >> x;
        if (x == 0)
            break;
        // printf("Case %d: %d\n", i, x);
        cout << "Case " << i << ": " << x << endl;
        ++i;
        if (i > 10000)
            break;
    }
    
    return 0;
}


Measured memory_bytes: 3112
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i < n; i++)
#define repd(i, n) for (int i = n-1; i > -1; i--)
#define repran(i, a,b) for (int i = a; i<b;i++)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> P;

// Sieve of Eratosthenes
// https://youtu.be/UTVg7wzMWQc?t=2774
struct Sieve {
  int n;
  vector<int> f, primes;
  Sieve(int n=1):n(n), f(n+1) {
    f[0] = f[1] = -1;
    for (ll i = 2; i <= n; ++i) {
      if (f[i]) continue;
      primes.push_back(i);
      f[i] = i;
      for (ll j = i*i; j <= n; j += i) {
        if (!f[j]) f[j] = i;
      }
    }
  }
  bool isPrime(int x) { return f[x] == x;}
  vector<int> factorList(int x) {
    vector<int> res;
    while (x != 1) {
      res.push_back(f[x]);
      x /= f[x];
    }
    return res;
  }
  vector<P> factor(int x) {
    vector<int> fl = factorList(x);
    if (fl.size() == 0) return {};
    vector<P> res(1, P(fl[0], 0));
    for (int p : fl) {
      if (res.back().first == p) {
        res.back().second++;
      } else {
        res.emplace_back(p, 1);
      }
    }
    return res;
  }
  vector<pair<ll,int>> factor(ll x) {
    vector<pair<ll,int>> res;
    for (int p : primes) {
      int y = 0;
      while (x%p == 0) x /= p, ++y;
      if (y != 0) res.emplace_back(p,y);
    }
    if (x != 1) res.emplace_back(x,1);
    return res;
  }
};


int main()
{
    int n;
    cin >> n;
    vector<int> a(n); // setだとgcdを正しく評価できていない。
    int gcd = 0;
    int m = 0;
    rep(i, n){
        cin >> a[i];
        gcd = __gcd(gcd, a[i]);
        m = max(m, a[i]);
    }
    Sieve s(m);
    vector<int> cnt(m+1);
    for (int x: a){
        auto p = s.factor(x);
        for (auto v: p){
            cnt[v.first]++;
        }
    }
    int mcnt = 0;
    repran(i, 2, m+1){
        mcnt = max(mcnt, cnt[i]);
    }
    if (mcnt == n){
        cout << "not coprime" << endl;
    }
    else if (mcnt > 1){
        cout << "setwise coprime" << endl;
    }
    else cout << "pairwise coprime" << endl;

}


Measured memory_bytes: 15288
V = [10,2,1]
N = Array.new(3,0)
for i in 0...3
  N[i] = gets.to_i
end
X = gets.to_i/50
ans = Array.new(X+1,0)
ans[0] = 1
for i in 0...3
  ans_ = ans.dup
  for j in 0...(X+1)
    for k in 1...(N[i]+1)
      if (j+(V[i]*k) > X)
        break
      end
      ans_[j+V[i]*k] += ans[j]
    end
  end
  ans = ans_.dup
  print("\n")
end

puts(ans[X])

Measured memory_bytes: 3836
#include<stdio.h>

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

int main(void){
  int n,m,i,ans;
  scanf("%d %d",&n,&m);
  ans=m;
  for(i=0;i<n;i++){
    scanf("%d",&m);
    ans=gcd(ans,m);
    //printf("%d->",ans);
  }
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int n;
vector <string> str;
string mem[15][15];
typedef pair <string,int> P;

string con(string a,string b){
  int K=0;
  for(int i=0;i<a.size();i++){
    int j=i,k=0;
    while(a[j]&&b[k]&&a[j]==b[k]) j++,k++;
    if(!a[j]||!b[k])K=max(K,k);
  }
  return b.substr(K,b.size());
}

string solve(){
  string dp[1<<14][14];
  for(int i=0;i<n;i++) dp[1<<i][i]=str[i];
  
  for(int i=0;i<(1<<n);i++)
    for(int k=0;k<n;k++){
      if(dp[i][k]=="")continue;
      for(int j=0;j<n;j++){
	if((i&(1<<j)))continue;
	string nx=dp[i][k]+mem[k][j];
	int ni=i|1<<j;
	string &ndp=dp[ni][j];
	if(!ndp.size()||
	   nx.size()<ndp.size()||
	   (nx.size()==ndp.size()&&ndp>nx))ndp=nx;
      }
    }

  string res=dp[(1<<n)-1][0];
  for(int i=1;i<n;i++) {
    string a=dp[(1<<n)-1][i];
    if(res.size()>a.size()||(a.size()==res.size()&&res>a)) res=a;
  }
  return res;
}

int main(){
  
  while(cin>>n,n){
    str.resize(n);
    for(int i=0;i<n;i++)cin>>str[i];

    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
	if(i!=j&&con(str[i],str[j])==""){
	  str.erase(str.begin()+j);
	  n--;
	  i=-1;
	  break;
	}
    
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)mem[i][j]=con(str[i],str[j]);

    cout<<solve()<<endl;
  }

  return 0;
}

Measured memory_bytes: 3444
#include<stdio.h>
int main()
{
    int a,b,c,d,e,k;
    scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&k);
    if(a-b>k||b-a>k||a-c>k||c-a>k||a-d>k||d-a>k||a-e>k||e-a>k||b-c>k||c-b>k||b-d>k||d-b>k||b-e>k||e-b>k||c-d>k||d-c>k||c-e>k||e-c>k||d-e>k||e-d>k)
        printf(":(");
    else
        printf("Yay!");
    return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

//#define DEBUG
#ifdef DEBUG
#define debug_printf printf
#else
#define debug_printf 1 ? 0 : printf
#endif

using namespace std;
typedef long long int ll;
typedef vector<ll> Vl;
typedef vector<int> Vi;
typedef pair<int, int> Pi;

#define INF   (1e9 + 7)
#define MAX_N (100000)

int N, M;
Vi G[MAX_N];

void solve() {
  set<int> used;
  Vi path[2];
  used.insert(0);
  for (int d = 0; d < 2; d++) {
    path[d].push_back(0);
    while (true) {
      int v = path[d].back();
      bool brk = true;
      for (int i = 0; i < G[v].size(); i++) {
        int u = G[v][i];
        if (used.find(u) == used.end()) {
          brk = false;
          used.insert(u);
          path[d].push_back(u);
          break;
        }
      }
      if (brk) break;
    }
  }

  printf("%lu\n", used.size());
  for (int i = path[1].size() - 1; i > 0; i--) {
    printf("%d ", path[1][i] + 1);
  }
  for (int i = 0; i < path[0].size(); i++) {
    printf("%d ", path[0][i] + 1);
  }
  printf("\n");
}

int main() {
  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    u--; v--;
    G[u].push_back(v);
    G[v].push_back(u);
  }

  solve();

  return 0;
}


Measured memory_bytes: 11384
def btaketolist(btake, N):
    li = []
    for i in range(N):
        t = btake % 4
        li.append(t)
        btake = btake // 4
    return list(reversed(li))


if __name__ == "__main__":
    N, a, b, c = [int(i) for i in input().split()]
    targets = [a, b, c]
    l = [int(input()) for i in range(N)]
    btake = 0
    take = btaketolist(btake, N)

    minimal_cost = 10e9

    for i in range(4 ** N):
        nums = [0, 0, 0]
        lengths = [0, 0, 0]
        for index, t in enumerate(take):
            if t == 3:
                continue
            nums[t] += 1
            lengths[t] += l[index]
        if 0 in nums:
            btake += 1
            take = btaketolist(btake, N)
            continue
        cost = 10 * (sum(nums) - 3) + sum([abs(lengths[i] - targets[i]) for i in range(3)])
        if cost < minimal_cost:
            minimal_cost = cost
        btake += 1
        take = btaketolist(btake, N)
    print(minimal_cost)


    


Measured memory_bytes: 3064
N = gets.to_i
C = []; S = []; F = []

(N - 1).times do |i|
  C[i], S[i], F[i] = gets.split.map(&:to_i)
end

(N - 1).times do |i|
  t = 0

  i.upto(N - 2) do |j|
    t = S[j] < t ? S[j] + ((t.to_f - S[j]) / F[j]).ceil * F[j] + C[j] : S[j] + C[j]
  end

  puts t.to_i
end

puts 0

Measured memory_bytes: 1788