akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
class FastIO {
  static const int rdata_sz = (1 << 25), wdata_sz = (1 << 25);
  char rdata[rdata_sz], wdata[wdata_sz], *rb, *wb;
  char tmp_s[20];

public:
  FastIO() {
    fread(rdata, 1, rdata_sz, stdin);
    rb = rdata; wb = wdata;
  }
  ~FastIO() {
    fwrite(wdata, 1, wb - wdata, stdout);
  }

  template<typename T>
  inline void read_i(T &x) {
    bool neg = false;
    x = 0;
    while((*rb < '0' || *rb > '9') && *rb != '-') ++rb;
    if(*rb == '-') {
      neg = true;
      ++rb;
    }
    while('0' <= *rb && *rb <= '9') {
      x = 10 * x + (*rb - '0');
      ++rb;
    }
    if(neg) x = -x;
  }

#define pc(x) *(wb++) = x
  template<typename T>
  inline void writeln_i(T x) {
    if (x == 0) { pc('0'); pc('\n'); return; }
    if(x < 0) { pc('-'); x = -x; }
    char *t = tmp_s;
    while(x) {
      T y = x / 10;
      *(t++) = (x - y*10) + '0';
      x = y;
    }
    while(t != tmp_s) pc(*(--t));
    pc('\n');
  }
#undef pc
};
FastIO io;
vector<bool> prime_table(int n) {
  vector<bool> prime(n + 1, true);
  if(n >= 0) prime[0] = false;
  if(n >= 1) prime[1] = false;
  for(int i = 2; i * i <= n; i++) {
    if(!prime[i]) continue;
    for(int j = i + i; j <= n; j += i) {
      prime[j] = false;
    }
  }
  return prime;
}
int main() {
    int Q;
    io.read_i(Q);
    auto primes = prime_table(100000);
    vector<int> s(primes.size(), 0);
    for (int i = 1; i < s.size(); i++) {
        s[i] = s[i - 1] + (primes[i] && primes[(i + 1) / 2]);        
    }
    for (int i = 0, l, r; i < Q; i++) {
        io.read_i(l);
        io.read_i(r);
        io.writeln_i(s[r] - s[l - 1]);
    }
}


Measured memory_bytes: 3840
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef vector<pair<ll,ll>> vp;
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
#define all(v) v.begin() , v.end()
#define inputv(v,n) rep(i,n){\
    ll x;\
    cin>>x;\
    v.push_back(x);\
    }
const ll INF=99999999999999;
const ll MOD=1000000007;
 
int main() {
  string s;
  cin >> s;
  vector<string> x;
  string temp;
  temp = s[0];
  x.push_back(temp);
  ll ans = 1;
  ll n;
  string y;
  n = (ll)(s.length());
  for(ll i = 1; i<n;){
    if(i == n-2 && s[i] == s[i+1]){
      ans++;
      break;
    } 
    y = s[i];
    if((int)x[ans-1].length() == 2){
      temp = s.substr(i,1);
      x.push_back(temp);
      ans++;
      i++;
    } else {
      if(x[ans-1] == y){
      temp = s.substr(i,2);
      x.push_back(temp);
      ans++;
        i += 2;
    } else {
        temp = s.substr(i,1);
        x.push_back(temp);
        ans += 1;
        i++;
      }
    }
  }
  cout << ans;
 return 0;
}

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

int main() {
int N;
cin >> N;
if(N == 1){
    cout << 1 <<endl;
    return 0;
}
int x =2;
while(x<=N){
    x *=2;
}
cout << x/2 <<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5005,mod=1e9+7;
ll f[N],invf[N];
ll C(int n,int m)
{
    return f[n]*invf[n-m]%mod*invf[m]%mod;
}
int n,tot,rt,si[N],g[N],head[N],nex[N<<1],to[N<<1];
bool two;
void add(int u,int v){to[++tot]=v;nex[tot]=head[u];head[u]=tot;}
void getrt(int u,int p)
{
    si[u]=1;
    for(int i=head[u];i;i=nex[i])
    {
        int v=to[i];if(v==p) continue;
        getrt(v,u);
        si[u]+=si[v];
        g[u]=max(g[u],si[v]);
    }
    g[u]=max(g[u],n-si[u]);
    if(g[u]<g[rt]) rt=u,two=false;
    else if(g[u]==g[rt]) two=true;
}
void dfs(int u,int p)
{
    si[u]=1;
    for(int i=head[u];i;i=nex[i])
        if(to[i]!=p) dfs(to[i],u),si[u]+=si[to[i]];
}
int top,s[N];
ll dp[N][N];
int main()
{
    f[0]=invf[0]=f[1]=invf[1]=1;
    for(int i=2;i<N;i++) f[i]=f[i-1]*i%mod,invf[i]=(mod-mod/i)*invf[mod%i]%mod;
    for(int i=2;i<N;i++) invf[i]=invf[i]*invf[i-1]%mod;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    g[rt]=1e9;
    getrt(1,0);
    if(two)
    {
        assert(n%2==0);
        printf("%lld\n",f[n/2]*f[n/2]%mod);
        return 0;
    }
    for(int i=head[rt];i;i=nex[i])
    {
        int v=to[i];dfs(v,rt);
        s[++top]=si[v];
    }
    dp[0][0]=1;
    int sum=0;
    for(int i=0;i<top;i++)
    {
        for(int j=0;j<=sum;j++)
            for(int k=0;k<=s[i+1];k++)
                (dp[i+1][j+k]+=dp[i][j]*C(s[i+1],k)%mod*C(s[i+1],k)%mod*f[k]%mod)%=mod;
        sum+=s[i+1];
    }
    sum++;
    ll ans=0;
    for(int s=1,i=0;i<=sum;i++,s*=-1)
        (ans+=s*dp[top][i]*f[sum-i])%=mod;
    ans=(ans+mod)%mod;
    printf("%lld\n",ans);
}


Measured memory_bytes: 194176
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005,p=998244353;
int read(){
	int f=1,g=0;
	char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int n,stk[N],top;
ll a[N],b[N],c[N],g[N],ans;
bool check(int i,int j,int k){
	ll x=g[i]-c[i],y=g[j]-c[j],z=g[k]-c[k];
	return (j-i)*(z-y)-(k-j)*(y-x)>0;
}
int main(){
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	n=read();
	for (int i=1;i<=n;i++) scanf("%lld",a+i);
	for (int i=1;i<=n;i++) scanf("%lld",b+i);
	int pos=1;a[0]=a[n];b[0]=b[n];
	for (int i=1;i<=n;i++) if (a[i]>a[pos]) pos=i;
	for(int i=0;i<=n;i++) g[i]=a[(i+pos)%n];
	for(int i=0;i<=n;i++) a[i]=b[(i+pos)%n];
	
	c[0]=c[1]=0;
	for (int i=1;i<n;i++) c[i+1]=2*a[i]+2*c[i]-c[i-1];
	top=0;
	for (int i=0;i<=n;i++){
		while ((top>=2)&&check(stk[top-1],stk[top],i)) top--;
		stk[++top]=i;
	}
	for (int i=2;i<=top;i++){
		int x=stk[i-1],y=stk[i];
		ans+=(g[x]-c[x]+g[y]-c[y])*(y-x+1)-2*(g[x]-c[x]);
	}
	for (int i=1;i<=n;i++) ans+=2*c[i];
		printf("%.12Lf\n",(long double)ans/2/n);
	return 0;
}


Measured memory_bytes: 10732
import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
         
        int n = sc.nextInt();
        int[] a = new int[n];
        
        for(int i=0;i<n;i++){
        	a[i] = sc.nextInt();
        }
        
        ArrayList<Integer> div = new ArrayList<>();
        div.addAll(divisors(a[0]));
        div.addAll(divisors(a[1]));
        
        int max = 0;
        
        for(int i:div){
        	int dame = 0;
        	for(int j=0;j<n;j++){
        		if(a[j]%i!=0){
        			dame+=1;
        		}
        	}
        	if(dame<=1){
        		max = Math.max(max,i);
        	}
        }
        
        System.out.println(max);
    }
    
	 static ArrayList<Integer> divisors(int n){
		 ArrayList<Integer> l = new ArrayList<>();
		 for(int i=1;i*i<=n;i++){
			 if(n%i == 0){
				 l.add(i);
				 if(i*i!=n){
					 l.add(n/i);
				 }
			 }
		 }
		 return l;
	 }
	 
}



class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;
	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}
	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}
	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}
	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}
	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}
	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}
	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Measured memory_bytes: 22672
#include <bits/stdc++.h>
#define LL long long

const int oo = 0x3f3f3f3f;
const int H = 10 + 5;
const int W = 1e3 + 5;

int h, w, k, ans = oo;
char s[H][W];
int state, pre[H][W], cut[W];

int main() {
    scanf("%d %d %d", &h, &w, &k);
    for(int i = 1; i <= h; ++i) scanf("%s", s[i] + 1);
    for(int i = 1; i <= h; ++i)
        for(int j = 1; j <= w; ++j)
            pre[i][j] = pre[i][j - 1] + (s[i][j] - '0');
    for(int state = 0; state < 1 << h - 1; ++state) {
        // pos[i] = state & (1 << i - 1)
        int finish = 1, last = 0, now = 0, cur = 0;
        for(int j = 1; j <= w; ++j) { // 第 j 列右边切 
            for(int i = 1; i <= h; ++i) {
                now += pre[i][j] - pre[i][last];
                if(i == h || state & (1 << i - 1)) { // 第 i 行下面切 
                    if(now > k) cut[j - 1] = 1, last = j - 1;
                    now = 0;
                }
            }
        }
        last = now = 0;
        for(int j = 1; j <= w; ++j) if(cut[j]) {
            for(int i = 1; i <= h; ++i) {
                now += pre[i][j] - pre[i][last];
                if(i == h || state & (1 << i - 1)) { // 第 i 行下面切 
                    if(now > k) finish = 0;
                    now = 0;
                }
            }
            last = j;
        }
        for(int i = 1; i <= w - 1; ++i) if(cut[i]) cur++, cut[i] = 0;
        if(finish)
          ans = std::min(ans, __builtin_popcountl(state) + cur);
    }
    printf("%d", ans);
    return 0;
}
/*
4 10 4
1110010010
1000101110
0011101001
1101000111

*/

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric> // accumulate(v.begin(), v.end(), 0)

using namespace std;
#define ll long long

int A[100][25];
int B[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};

int main(){
  int N;
  cin >> N;
  for(int i=0; i<N; i++) {
    for(int j=0; j<25; j++) {
      if(i > 0)
	A[i][j] = A[i-1][j];
      int tmp = i+1;
      while(tmp % B[j] == 0) {
	tmp /= B[j];
	A[i][j]++;
      }
    }
  }

  int seventyfour = 0;
  int twentyeight = 0;
  int twentyfour = 0;
  int forteen = 0;
  int four = 0;
  int two = 0;
  for(int j=0; j<25; j++) {
    if(A[N-1][j] >= 74)
      seventyfour++;
    if(A[N-1][j] >= 28)
      twentyeight++;
    if(A[N-1][j] >= 24)
      twentyfour++;
    if(A[N-1][j] >= 14)
      forteen++;
    if(A[N-1][j] >= 4)
      four++;
    if(A[N-1][j] >= 2)
      two++;
  }

  int ans = 0;
  ans += max(four * (four-1) / 2 * (two-2), 0); // 2 * 4 * 4
  ans += max(twentyfour * (two-1), 0); // 2 * 24
  // ans += max(four * forteen - twentyeight * (twentyeight-1), 0); // 4 * 14
  ans += max(forteen * (four-1), 0); // 4 * 14
  ans += seventyfour; // 74
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
  int n, A[1001];
  cin >> n;
  for(int i=0; i<n; ++i) cin >> A[i];

  int m, B[1001];
  cin >> m;
  for(int i=0; i<m; ++i) cin >> B[i];

  /* A < B : 1, A > B : 0 */
  A[n] = B[m] = -1; // 番兵

  for(int i=0; true; ++i){
    if(A[i] == -1 && B[i] == -1){ // A = B
      cout << 0 << endl; break;
  }
    else if(A[i] < B[i]){
      cout << 1 << endl; break;
    }
    else if(A[i] > B[i]){
      cout << 0 << endl; break;
    }
  }
  return 0;
}


Measured memory_bytes: 3120
#include<bits/stdc++.h>
using namespace std;
#define next Next
#define int long long
const int mod=1e9+7;
const int N=2e6+5;
int n,ans,zero,add1[N],add2[N],a[N],sum[N],f[N];
vector<int>v[N];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
#define gc getchar
inline int read()
{
	int ret=0,f=0;char c=gc();
	while(!isdigit(c)){if(c=='-')f=1;c=gc();}
	while(isdigit(c)){ret=ret*10+c-48;c=gc();}
	if(f)return -ret;return ret;
}
signed main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=a[i-1]^read();
		v[a[i]].push_back(i);
	}
    for(int i=1;i<(1<<20);i++)
		if(v[i].size())add2[v[i][0]]++;
	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+(a[i]==0);
	for(int i=1;i<=n;i++)
        if(a[i]!=0)
		{
            f[i]=(sum[i]*add1[i]%mod+add2[i])%mod;
            int xu=upper_bound(v[a[i]].begin(),v[a[i]].end(),i)-v[a[i]].begin();
            if(xu<v[a[i]].size())
			{
                int nxt=v[a[i]][xu];
                add1[nxt]=(add1[nxt]+add1[i]+f[i])%mod;
                add2[nxt]=(add2[nxt]+add2[i]-f[i]*sum[i]%mod+mod)%mod;
            }
        }
	if(a[n]==0)
	{
		ans=0;
		int res=1;
		for(int i=1;i<n;i++)
			if(a[i]==0)res=res*2%mod;
			else ans=(ans+f[i])%mod;
		cout<<(ans+res)%mod;
	}
	else cout<<f[n];
}

Measured memory_bytes: 86384
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

type Entry struct {
	name  string
	value int
}

func main() {
	sc.Split(bufio.ScanWords)
	n, q := nextInt(), nextInt()

	queue := make([]string, n)
	m := make(map[string]int, n)
	for i := range queue {
		k := nextLine()
		queue[i] = k
		v := nextInt()
		m[k] = v
	}
	r := make([]Entry, 0, n)
	var t int
	for len(queue) != 0 {
		v := queue[0]
		sub := m[v] - q

		if sub <= 0 {
			t += m[v]
			m[v] = t
			queue = queue[1:]

			e := Entry{v, t}
			r = append(r, e)
		} else {
			t += q
			m[v] = m[v] - q
			queue = queue[1:]
			queue = append(queue, v)
		}
	}

	for _, v := range r {
		fmt.Println(v.name, v.value)
	}
}

// =================================
// I/O util
// =================================

var sc = bufio.NewScanner(os.Stdin)

// Scan required
func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

// =================================



Measured memory_bytes: 11096
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include<limits.h>
#include<iomanip>
#define rep(i, n) for(int i = 0; i < n; i++)
#define rrep(i, n) for(int i = n-1; i >= 0; i--)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define lamsort(v,p) sort(v.begin(),v.end(),[](p a, p b){return a.num < b.num;});
#define check(v) rep(i,v.size()) cout << v[i] << " ";\
cout << endl
const long long LLINF = 1LL<<60;
const int INF = 1e9;
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; }
typedef long long ll;
using namespace std;
//オーバーフローに気をつけろよおおおおおお
//確認忘れるなよおおおおおお

struct UnionFind {
    int n;
    vector<int> par; 

    UnionFind(int N) : par(N) { 
        for(int i = 0; i < N; i++) par[i] = i;
        n = N;
    }

    int root(int x) { 
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { 
        int rx = root(x); 
        int ry = root(y); 
        if (rx == ry) return;
        n--;
        par[rx] = ry; 
    }

    bool same(int x, int y) { 
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    int size() {return n;}
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    UnionFind tree(n);
    rep(i,m) {
        int u,v,z; cin >> u >> v >> z;
        u--; v--;
        tree.unite(u,v);
    }
    cout << tree.size() << endl;

    return 0;
}

Measured memory_bytes: 640
n = int(input())
t = [list(map(int,input().split())) for i in range(n)]
for x,y,h in t:
    if h > 0:
        a = [x,y,h]            # hが0でない1つの組(地面以外の部分)

for cx in range(101):
    for cy in range(101):
        flag = True
        ch = abs(a[0]-cx) + abs(a[1] - cy) + a[2]     # 高さ
        for x,y,h in t:
            if h != max(ch - abs(x - cx) - abs(y - cy),0):    # 高さが条件に合うか 
                flag = False
                break
        if flag:
            print(cx,cy,ch)
            exit()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
// type alias
typedef long long LL;
typedef pair<int,int> II;
typedef tuple<int,int,int> III;
typedef vector<int> VI;
typedef vector<string> VS;
typedef unordered_map<int,int> MAPII;
typedef unordered_set<int> SETI;
template<class T> using VV=vector<vector<T>>;
// minmax
template<class T> inline T SMIN(T& a, const T b) { return a=(a>b)?b:a; }
template<class T> inline T SMAX(T& a, const T b) { return a=(a<b)?b:a; }
// repetition
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n)  for(int i=0;i<=(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())
// collection
#define ALL(c) (c).begin(),(c).end()
// DP
#define MINUS(dp) memset(dp, -1, sizeof(dp))
#define ZERO(dp) memset(dp, 0, sizeof(dp))
// stdout
#define println(args...) fprintf(stdout, ##args),putchar('\n');
// debug cerr
template<class Iter> void __kumaerrc(Iter begin, Iter end) { for(; begin!=end; ++begin) { cerr<<*begin<<','; } cerr<<endl; }
void __kumaerr(istream_iterator<string> it) { (void)it; cerr<<endl; }
template<typename T, typename... Args> void __kumaerr(istream_iterator<string> it, T a, Args... args) { cerr<<*it<<"="<<a<<", ",__kumaerr(++it, args...); }
template<typename S, typename T> std::ostream& operator<<(std::ostream& _os, const std::pair<S,T>& _p) { return _os<<"{"<<_p.first<<','<<_p.second<<"}"; }
#define __KUMATRACE__ true
#ifdef __KUMATRACE__
#define dump(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); __kumaerr(_it, args); }
#define dumpc(ar) { cerr<<#ar<<": "; FORR(x,(ar)) { cerr << x << ','; } cerr << endl; }
#define dumpC(beg,end) { cerr<<"~"<<#end<<": "; __kumaerrc(beg,end); }
#else
#define dump(args...)
#define dumpc(ar)
#define dumpC(beg,end)
#endif
struct UF {
public:
  int N,G/* # of disjoint sets */;
  UF(int N): N(N) { init(N); }
  void init(int N) {
    par=vector<int>(N),sz=vector<int>(N,1);
    for(int i=0; i<N; ++i) par[i]=i,sz[i]=1;
    G=N;
  }
  int find(int x) { return par[x]==x?x:par[x]=find(par[x]); }
  int size(int x) { return sz[find(x)]; }
  bool sameset(int x, int y) { return find(x)==find(y); }
  int unite(int x, int y) {
    x=find(x),y=find(y);
    if(x==y) return x;
    int p=x,c=y;
    if(sz[p]<sz[c]) swap(p,c);
    G--,sz[p]=sz[c]=sz[p]+sz[c];
    par[c]=p;
    return p;
  }
private:
  vector<int> par,sz;
};
// $ cp-batch 1Or2 | diff 1Or2.out -
// $ g++ -std=c++14 -Wall -O2 -D_GLIBCXX_DEBUG -fsanitize=address 1Or2.cpp && ./a.out

/*
 
 5/19/2019
 
 5:37-
 
 */

const int MAX_N=1e6+1;
int X[MAX_N],Y[MAX_N],Z[MAX_N];
int N,M;

void solve() {
  UF uf(N);
  REP(i,M) uf.unite(X[i]-1,Y[i]-1);
  cout<<uf.G<<endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout<<setprecision(12)<<fixed;
  
  cin>>N>>M;
  REP(i,M) cin>>X[i]>>Y[i]>>Z[i];
  solve();
  
  return 0;
}


Measured memory_bytes: 9600
# include <bits/stdc++.h>
# define ll long long
using namespace std;
const int N = 4e5 + 10, M = 2e7 + 100, mod = 1e9 + 7;
short ty[N], f[N];
char c[N];
int q, rev;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string s = "";
    int q;
    cin >> s >> q;
    for(int i = 1; i <= q; i++){
        cin >> ty[i];
        if(ty[i] != 1){
            cin >> f[i] >> c[i];
        }
    }
    for(int i = 1; i <= q; i++){
        if(ty[i] == 1){
            rev ^= 1;
        }else{
            if(f[i] == 2 && rev == 0){
                s += c[i];
            }
            if(f[i] == 1 && rev == 1){
                s += c[i];
            }
        }
    }
    reverse(s.begin(), s.end());rev = 0;
    for(int i = 1; i <= q; i++){
        if(ty[i] == 1){
            rev ^= 1;
        }else{
            if(f[i] == 2 && rev == 1){
                s += c[i];
            }
            if(f[i] == 1 && rev == 0){
                s += c[i];
            }
        }
    }
    if(!rev)reverse(s.begin(), s.end());
    cout << s << endl;
}


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

#define debug(x) cout << #x << " = " << x << endl
#define fori(i, ini, lim) for(int i = int(ini); i < int(lim); i++)
#define ford(i, ini, lim) for(int i = int(ini); i >= int(lim); i--)

using namespace std;

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

int main() {
	ll n;
	scanf("%lld", &n);
	vector<int> v(n);
	ll sum = 0;
	fori(i, 0, n) {
		scanf("%d", &v[i]);
		sum += v[i];
	}

	if(sum % ((1LL * (n * (n + 1))) / 2LL) != 0) {
		puts("NO");
		return 0;
	}

	ll k = sum / ((1LL * (n * (n + 1))) / 2LL);

	bool good = true;
	fori(i, 0, n - 1) {
		int d = v[i + 1] - v[i];
		if(0 > (k - d) || (k - d) % n != 0) {
			good = false;
		}
	}

	puts(good ? "YES" : "NO");

	return 0;
}



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

int K[32] = {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};

int main()
{
    int k;
    cin >> k;
    cout << K[k-1] << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.Abc
{
    class QuestionB
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 整数の入力
            var n = long.Parse(Console.ReadLine());

            var fiveHundred = n / 500;

            var nn = n - (fiveHundred * 500);

            var five = nn / 5;

            var result = (fiveHundred * 1000) + (five * 5);

            Console.WriteLine(result);

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 13140
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
      	List<Integer> list = new ArrayList<>();
      	while(sc.hasNextLine()) {
      	    try {
        	    int a = sc.nextInt();
          	    list.add(a);
      	    } catch (NoSuchElementException e) {
      	        
      	    }     
        } 	
		
      	for (int i = 0; i < list.size(); i++) {
        	if(list.get(i) == 0) {
            	break;
            }
          	System.out.println("Case " + (i + 1) + ": " + list.get(i));
        }
	}
}


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

int main(){
    int n;
    cin >> n;
    int minus=101;
    int tot=0;
    for(int i=0; i<n; i++){
        int s;
        cin >> s;
        tot += s;
        if(s%10!=0) minus=min(minus, s);
    }
    if(tot%10!=0) cout << tot << endl;
    else{
        if(minus==101) cout << 0 << endl;
        else cout << tot - minus << endl;
    }
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define loop(i,b,e) for(int i=b;i<=e;i++)
#define loop2(i,e,b) for(int i=e;i>=b;i--)
#define io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define X real()
#define Y imag()
#define cp(a,b)	( (conj(a)*(b)).imag() )
#define length(a) (hypot((a).imag(), (a).real()))
typedef complex<double> point;
typedef long long ll;
typedef unsigned long long ull;
double PI = 3.141592653589793;
const double EPS = 1e-9;
const int N = 1e6 + 5;
const ll mod = 1e9 + 7;
const int oo = 1e9;
int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
int dy[] = { 1, -1, 0, 0, -1, 1, 1, -1 };

int n;
int t[3005];
bool d[N];

int main() {
	io;
	cin >> n;
	int ans = 0;
	loop(i, 0, n - 1) {
		cin >> t[i];
		ans += t[i] - 1;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
local n,ma,mb=io.read("n","n","n")
local n1=math.floor(n/2)
local n2=math.floor(n/2)+n%2
local a1,b1,c1={},{},{}
local a2,b2,c2={},{},{}
for i=1,n1 do
    a1[i],b1[i],c1[i]=io.read("n","n","n")
end
for i=1,n2 do
    a2[i],b2[i],c2[i]=io.read("n","n","n")
end

local bit=require("bit")
local lshift=bit.lshift
local band=bit.band

local INF=10^13
local mincost=INF

local map1={}
for bit=0,lshift(1,n1) do
    local asum=0
    local bsum=0
    local csum=0
    for i=1,n1 do
        if band(bit,lshift(1,i-1))>0 then
            asum=asum+a1[i]
            bsum=bsum+b1[i]
            csum=csum+c1[i]
        end
    end
    if csum>0 then
        map1[asum]=map1[asum] or {}
        if not map1[asum][bsum] then
            map1[asum][bsum]=csum
        else
            map1[asum][bsum]=math.min(map1[asum][bsum],csum)
        end
        if asum*mb==bsum*ma then
            mincost=math.min(mincost,csum)
        end
    end
end
local map2={}
for bit=0,lshift(1,n2) do
    local asum=0
    local bsum=0
    local csum=0
    for i=1,n2 do
        if band(bit,lshift(1,i-1))>0 then
            asum=asum+a2[i]
            bsum=bsum+b2[i]
            csum=csum+c2[i]
        end
    end
    if csum>0 then
        map2[asum]=map2[asum] or {}
        if not map2[asum][bsum] then
            map2[asum][bsum]=csum
        else
            map2[asum][bsum]=math.min(map2[asum][bsum],csum)
        end
        if asum*mb==bsum*ma then
            mincost=math.min(mincost,csum)
        end
    end
end

local m=math.max(ma,mb)
for a1,_ in pairs(map1) do
    for b1,c1 in pairs(map1[a1]) do
        for i=0,400,m do
            i=math.floor(i/m)
            local c2=(map2[i*ma-a1] and map2[i*ma-a1][i*mb-b1])
            if c2 then
                mincost=math.min(mincost,c1+c2)
            end
        end
    end
end
print(INF>mincost and mincost or -1)

Measured memory_bytes: 2864
#include<iostream>
#include<string>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
using namespace std;

string comp(string a, string b) {
  if (a.size() < b.size()) return "LESS";
  if (a.size() > b.size()) return "GREATER";
  rep(i,0,a.size()-1) {
    if (a[i] < b[i]) return "LESS";
    if (a[i] > b[i]) return "GREATER";
  }
  return "EQUAL";
}

int main() {
  string a, b;
  cin >> a >> b;
  cout << comp(a, b) << endl;
  return 0;
}


Measured memory_bytes: 256
def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b

N, K  = getMN()

height = []
for i in range(N):
    height.append(getN())

height.sort()
ans = 10000000000
for i in range(N-K+1):

    if ans > abs(height[i] - height[i+K-1]):
        ans = abs(height[i] - height[i+K-1])

print(ans)


Measured memory_bytes: 7384
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <list>
#include<map>
#include<set>
using namespace std;
int main() {
    int n, a[2][100] = {};
    cin >> n;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    int s = a[0][0], m;
    for (int i = 0; i < n; i++) {
        s += a[1][i];
    }
    m = s;
    for (int i = 0; i < n - 1; i++) {
        s += a[0][i + 1] - a[1][i];
        m = max(s, m);
    }
    cout << m << endl;
}

            


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
long long int n, m,a,b,ans=0,r,d,x;
vector<int> l;
cin>>r>>d>>x;
for(int i=0;i<10;i++){
  x=r*x-d;
  cout<<x<<endl;
}

return 0;
} 

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define mid ((l+r)>>1)
#define lc (root<<1)
#define rc (root<<1|1)
#define lowbit(x) (x&-x)
using namespace std;
const int N = 3e3+7, p = 1e9+7;
char s[N];
int f[N][N];
int main()
{
	int n, ans = 0;
    scanf("%d%s", &n, s+2);
    f[1][1] = 1;
    for(int i = 2; i <= n; i++)
    {
    	if(s[i]=='<')
    	{
    		for(int j = 1; j <= i; j++)
    		{
    			f[i][j] = (f[i-1][j-1]+f[i][j-1])%p;
    		}
    	}
    	else
    	{
    		for(int j = i; j >= 1; j--)
    		{
    			f[i][j] = (f[i-1][j]+f[i][j+1])%p;
    		}
    	}
    }
    for(int i = 1; i <= n; i++)
    {
    	ans = (ans+f[n][i])%p;
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 34176
#include <bits/stdc++.h>
using namespace std;
deque<int> dq;
int n,x;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if(n%2)
        {
            if(i%2)dq.push_front(x);
            else dq.push_back(x);
        }else
        {
            if(i%2==0)dq.push_front(x);
            else dq.push_back(x);
        }
    }
    for(int i=0;i<dq.size()-1;i++)printf("%d ",dq[i]);printf("%d\n",dq[dq.size()-1]);
    return 0;
}


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

using namespace std;


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

	map<int, int> f;
	for (int i = 0; i < n; i++)
	{
		int count = 0;
		cin >> count;
		for (int j = 0; j < count; j++)
		{
			int food;
			cin >> food;
			f[food]++;
		}
	}

	int ans = 0;
	for (const auto &e : f)
	{
		if(e.second == n) ans++;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>
using namespace std;
int		cnt;
int		ans;
int		main(void)
{
	int		A, B;
	cin >> A >> B;
	cnt = A;
	ans = 1;
	if (B <= 2)
	{
		cout << 0 << endl;
		return 0;
	}
	for (; ; )
	{
		if (cnt >= B)
			break ;
		cnt += (A - 1);
		ans++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N = int(input())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i],B[i] = map(int,input().split())

    As = sorted(A)
    Bs = sorted(B)

    if N % 2 == 1:
        Am = As[N//2]
        Bm = Bs[N//2]
    else:
        Am = As[N//2-1] + As[N//2]
        Bm = Bs[N//2-1] + Bs[N//2]

    res = Bm - Am + 1

    print(res)



main()


Measured memory_bytes: 28664
#include<bits/stdc++.h>
using namespace std;
int a[200005];
int maxn=0;
int max2;
int point;
int tf;
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		if(a[i]>maxn){
			maxn=a[i];
			point=i;
		}
	}
	for(int i=0;i<n;i++){
		if(a[i]==maxn&&i!=point){
			tf=1;
		}
	}
	if(tf==1){
		for(int i=0;i<n;i++){
			cout<<maxn<<endl;
		}
	}else{
		for(int i=0;i<n;i++){
			if(i==point){
				int max2=0;
				for(int j=0;j<n;j++){
					if(a[j]>max2&&j!=point){
						max2=a[j];
					}
				}
				cout<<max2<<endl;
			}else{
				cout<<maxn<<endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 2432
import itertools
import bisect


class TopList():
    def __init__(self, length):
        self.data = []
        self.length = length

    def update(self, num):
        num = -num
        idx = bisect.bisect(self.data, num)
        self.data.insert(idx, num)
        if len(self.data) > self.length:
            self.data.pop()

    def sum(self):
        return -sum(self.data)


patterns = list(itertools.product([1, -1], repeat=3))


N, M = map(int, input().split())
tls = [TopList(M) for _ in patterns]

for _ in range(N):
    xyz = list(map(int, input().split()))
    for i in range(len(patterns)):
        num = 0
        for a, b in zip(xyz, patterns[i]):
            num += a * b
        tls[i].update(num)

print(max([tl.sum() for tl in tls]))


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

void recursive_comb(int *indexes, int s, int rest, function<void(int *)> f) {
  if (rest == 0) {
    f(indexes);
  } else {
    if (s < 0) return;
    recursive_comb(indexes, s - 1, rest, f);
    indexes[rest - 1] = s;
    recursive_comb(indexes, s - 1, rest - 1, f);
  }
}

// nCkの組み合わせに対して処理を実行する
void foreach_comb(int n, int k, function<void(int *)> f) {
  int indexes[k];
  recursive_comb(indexes, n - 1, k, f);
}

int main() {
  // 入力
  string S;
  cin >> S;
  
  // 間の数
  int m = (int)(S.size() - 1);
  
  long sum = 0;
  for (int i = 0; i <= m; i++) { // +の数
    // mCiの組み合わせごとに処理する
    foreach_comb(m, i, [&sum, S, i](int *indexes) {
      int p = 0;
      for (int j = 0; j < i; j++) {
        int len = indexes[j] + 1 - p;
        sum += atol(S.substr(p, len).c_str());
        p = p + len;
      }
      sum += atol(S.substr(p).c_str());
    });
  }
  
  cout << sum << endl;
}


Measured memory_bytes: 3604
import java.util.*;	

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int fact = 1;
		int conbination;
		double sum = 0;
		double coord[][] = new double[n][2];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < 2; j++) {
				coord[i][j] = sc.nextDouble();
			}
		}
		for(int i = 1; i <= n; i++) {
			fact *= i; 
		}
		conbination = n * (n - 1) / 2;
		for(int i = 0; i < n - 1; i++) {
			for(int j = i + 1; j < n; j++) {
			sum += (fact * (n - 1) / conbination) * Math.sqrt(Math.pow(coord[i][0] - coord[j][0], 2) + Math.pow(coord[i][1] - coord[j][1], 2));
		    }
		}
		System.out.println(sum / fact);
	}
}

Measured memory_bytes: 24276
#include <stdio.h>

int main(void) {

  long x;
  scanf("%ld", &x);
  long answer = x/11;
  answer *= 2;
  if (x%11 > 6) {
    answer += 2;
  } else if (x%11 > 0) {
    answer++;
  }
  printf("%ld\n", answer);

  return 0;
}

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

//#define int long long
#define ll long long
#define all(v) (v).begin(), (v).end()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << end
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

signed main()
{   
    gearup;
    ll x,y; cin >> x >> y;
    ll ans = y/x;
    ll res = 1;
    while(ans >= 2){
        ans/=2;
        res++;
    }
    cout << res << endl;
}


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

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

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(15)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

int main()
{
    ll N, K;
    cin >> N >> K;
    double ans = 0;
    FOR(i, N + 1, 1)
    {
        ll n = i;
        int t = 0;
        while (n < K)
        {
            n *= 2;
            t++;
        }

        ans += 1 / ((double)pow(2, t) * (double)(N));
    }
    cout << OF64 << ans << endl;
    return 0;
}

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

using namespace std;

using ll = long long;

const long long MOD = 1e9 + 7;
const int INF = 1e9 + 7;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<pair<int, int>> v(N);
    for (int i = 0; i < N; ++i) {
        int A;
        cin >> A;
        v[i].first = A;
        v[i].second = i + 1;
    }
    sort(v.begin(), v.end());
    for (auto p : v) cout << p.second << " ";
    cout << endl;
}

Measured memory_bytes: 1664
function Main(input){
  input = input.split("\n");
  var inputVal1 = input[0].split(" ");
  var inputVal2 = input[1].split(" ");
  var maxVal = parseInt(inputVal2[0]);
  var i = 1;
  var count = 1;
  for ( i=1 ; i < inputVal2.length ; i++ ) {
    
    if (maxVal <= parseInt(inputVal2[i])) {
      
      maxVal = parseInt(inputVal2[i]);
      count = count +  1;
    }
  }
  console.log(count);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int compare_int(const void *a, const void *b)
{
    return *(int*)b - *(int*)a;
}

int main(void){
  char buf[1024] = { 0 };
  int num[128] = { 0 };
  char *tok = NULL;
  int N = 0;
  
  //入力読み込み
  fgets(buf, sizeof(buf), stdin);
  sscanf(buf, "%d", &N);
  
  fgets(buf, sizeof(buf), stdin);
  tok = strtok(buf, " ");
  int count = 0;
  while(tok != NULL && count < N){
    num[count++] = atoi(tok);
    tok = strtok(NULL,  " ");
  }
  
  qsort(num, N, sizeof(int), compare_int);
  //for(int i = 0; i < N; i++) printf("%d\n", num[i]);
  int score1 = 0;
  int score2 = 0;
  int i,j;
  for(i = 0, j = 1; i < N; i = i + 2, j = j + 2){
    score1 += num[i];
    score2 += num[j];
  }
  printf("%d\n", score1 - score2);
  return 0;
}

Measured memory_bytes: 1700
# -*- coding: utf-8 -*-


#----------
N = int(input().strip())
A_list = [int(input().strip()) for _ in range(N)]
#----------
A_dic = {}
A_set =set()

for i in A_list:
    if i not in A_set:
        A_set.add(i)
    else:
        A_set.remove(i)

print(len(A_set))


Measured memory_bytes: 13200
while gets
    xa1,ya1,xa2,ya2,xb1,yb1,xb2,yb2=$_.split(nil).map(&:to_f)
    if((xb2-xa1)*(xa2-xb1)>=0) &&((yb2-ya1)*(ya2-yb1)>=0)
        puts "YES"
    else
        puts "NO"
    end
end

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

int main() {
    string s, t;
    cin >> s >> t;
    if(s==t) {
        cout << "EQUAL" << endl;
        return 0;
    } else if(s.length()>t.length()) {
        cout << "GREATER" << endl;
        return 0;
    } else if(s.length()<t.length()) {
        cout << "LESS" << endl;
        return 0;
    }

    for(int i=0; i<s.length(); i++) {
        if(s[i]>t[i]) {
            cout << "GREATER" << endl;
            return 0;
        } else if(s[i]<t[i]) {
            cout << "LESS" << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 256
//
//  main.cpp
//  T - Permutation
//
//  Created by Thomas Guo on 2019-01-16.
//  Copyright © 2019 Thomas Guo. All rights reserved.
//

#include <iostream>
#define maxn 3002
#define MOD 1000000007
#define ll long long
using namespace std;
ll n,dp[maxn][maxn];string s;
int main(){
    cin>>n>>s;
    dp[1][1]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(s[i-2]=='<'){
                dp[i][j]=dp[i-1][j-1];
            }
            else{
                dp[i][j]=dp[i-1][i-1]-dp[i-1][j-1];dp[i][j]%=MOD;
            }
        }
        for(int j=1;j<=i;j++){
            dp[i][j]+=dp[i][j-1];dp[i][j]%=MOD;
        }
    }
    dp[n][n]+=MOD;dp[n][n]%=MOD;
    cout<<dp[n][n]<<"\n";
    return 0;
}


Measured memory_bytes: 68992
#include <iostream>
#include <cstdlib>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int i, ara[n];
    for(i=0; i<n; i++){
        cin >> ara[i];
    }
    int dp[n];
    dp[0] = 0;
    dp[1] = abs(ara[1]-ara[0]);
    for(i=2; i<n; i++){
        dp[i] = min(dp[i-1]+abs(ara[i]-ara[i-1]),
                    dp[i-2]+abs(ara[i]-ara[i-2])
                    );
    }
    cout << dp[n-1];
    return 0;
}


Measured memory_bytes: 1024
N = int(input())

A = [True]*100000
A[0],A[1]=False,False
for i in range(2,100000):
    if A[i]:
        j = 2
        while i*j<100000:
            A[i*j] = False
            j += 1
P = []
for i in range(100000):
    if A[i] and i%5==1:
        P.append(i)

print(" ".join(map(str,P[:N])))

Measured memory_bytes: 3828
#include <bits/stdc++.h>
//---------------------------
using namespace std;
//---------------------------
#define REP(i,n) for(int i = 0; i < (n); i++)
#define P(x) cout << (x) << "\n"
#define fcout cout << fixed << setprecision(18)

#define MOD 1000000007 // 1e9+7
#define PI 3.1415926535
/*
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679
*/
#define ll long long int // 10^18
#define INF 1000000001 // 1e9+1
#define LINF 1000000000000000001 // 1e18+1

int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
//---------------------------
//
const int N=1e+5, M=2e+5;

vector<pair<ll,ll>> G[N];

bool ok=true;
bool visited[N];
int weights[N];

void dfs(int v){
  visited[v]=true;
  REP(i,(int)G[v].size()){
    int to=G[v][i].first;
    int weight=G[v][i].second;
    // cout<<v<<" "<<to<<" "<<weight<<"\n";
    // cout<<visited[to]<<"\n";
    if(!visited[to]){
      weights[to]=weights[v] + weight;
      // cout<<weights[to]<<" "<<weights[v]<<"\n";
      dfs(to);
    }else{
      if(weights[to] != weights[v]+weight){
        // cout<<weights[to]<<" "<<weights[v]<<"\n";
        ok=false;
      }
    }
  }
}

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

  // ifstream in("input.txt");
  // cin.rdbuf(in.rdbuf());

  int n,m;cin>>n>>m;
  REP(i,m){
    int a,b,d;cin>>a>>b>>d;
    --a;--b;
    G[a].push_back(make_pair(b,d));
    G[b].push_back(make_pair(a,-d));
  }

  REP(i,n){
    if(!visited[i]){
      dfs(i);
    }
  }
  if(ok){
    P("Yes");
  }else{
    P("No");
  }
  return 0;
}


Measured memory_bytes: 16256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

using ll = long long;
using ull = uint64_t;
using P = pair<int, int>;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

ll c[10000005];

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

    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i){
        ++c[i];
        for(int j = i + i; j <= n; j += i){
            ++c[j];
        }
    }
    ll ans = 0;
    for(int i = 1; i <= n; ++i){
        ans += c[i] * i;
    }
    cout << ans << endl;
}

Measured memory_bytes: 81704
object Main extends App {
  val s = scala.io.StdIn.readLine

  var now = s(0)
  var b_cnt = 0
  var w_cnt = 0

  s.foreach { ch =>
    if (now != ch) {
      if (now == 'B') {
        b_cnt += 1
      } else {
        w_cnt += 1
      }
      now = ch
    }
  }
  if (now == 'B') {
    b_cnt += 1
  } else {
    w_cnt += 1
  }

  var memo: Map[(Int, Int, (Char, Char)), Int] = Map.empty

  def exec(wc: Int, bc: Int, top: (Char, Char)): Int = {
    memo.get((wc, bc, top)) match {
      case Some(ans) => ans
      case None =>

        if (wc == 0 || bc == 0) {
          return 0
        }

        var list = List[Int]()

        if (top._1 == 'W') {
          list = list.::(exec(wc - 1, bc, ('B', top._2)))
        }
        if (top._1 == 'B') {
          list = list.::(exec(wc, bc - 1, ('W', top._2)))
        }
        if (top._2 == 'W') {
          list = list.::(exec(wc - 1, bc, (top._1, 'B')))
        }
        if (top._2 == 'B') {
          list = list.::(exec(wc, bc - 1, (top._1, 'W')))
        }
        val newans = list.min + 1
        memo += ((wc, bc, top) -> newans)
        newans
    }
  }

  println(exec(w_cnt, b_cnt, (s.head, s.last)))
}


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

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

/* --- INFやMODの値が適切か確認する --- */
// const int INF = 1 << 30;
// const ll INF = 1LL << 60;
// const ll MOD = 1000000007;

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  sort(rall(a));

  int g = a[0];
  rep(i, n) g = __gcd(g, a[i]);

  cout << ((a[0] >= k && k % g == 0) ? "POSSIBLE" : "IMPOSSIBLE") << endl;
}


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

int dp[50][100][10];

int main(){
  int c,d,w,x;
  int e[50][50],f[50][50];

  while(cin >> c >> d >> w >> x, c||d||w||x){
    for(int i=0;i<c;i++)
      for(int j=0;j<d;j++)cin >> e[i][j];
    for(int i=0;i<c;i++)
      for(int j=0;j<d;j++)cin >> f[i][j];

    for(int i=0;i<=d;i++)
      for(int j=0;j<=w;j++)
	for(int k=0;k<=x;k++)dp[i][j][k] = -1;
    dp[0][0][0] = 0;

    for(int i=0;i<d;i++)
      for(int j=0;j<=w;j++)
	for(int k=0;k<=x;k++){
	  if(dp[i][j][k]<0)continue;
	  dp[i+1][j][k] = max(dp[i+1][j][k],dp[i][j][k]);
	  for(int a=0;a<c;a++){
	    if(!e[a][i])continue;
	    int st = j+f[a][i];
	    int val = dp[i][j][k]+e[a][i];
	    if(st<=w){
	      dp[i+1][st][k] = max(dp[i+1][st][k],val);
	    }
	    if(k<x){ 
	      for(int b=1;a+b<c;b++){
		if(!e[a+b][i])break;
		st += f[a+b][i];
		if(st>w)break;
		val += e[a+b][i];
		dp[i+1][st][k+1] = max(dp[i+1][st][k+1],val);
	      }
	    }
	  }
	}

    int ans = 0;
    for(int i=0;i<=w;i++)
      for(int j=0;j<=x;j++)ans = max(ans,dp[d][i][j]);

    cout << ans << endl;
  }
}
	  

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
constexpr int INF = 2e9;

unsigned int randxor() {
  static unsigned int x=123456789,y=362436069,z=521288629,w=88675123;
  unsigned int t;
  t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}




int main() {
  int D;
  cin >> D;
  vector<int> c(26);
  rep(i,26) cin >> c[i];
  vector<vector<int>> s(D + 1, vector<int>(26, 0));
  vector<vector<int>> last_day(D + 1, vector<int>(26, 0));
  vector<int> t(D);
  rep(i,D) rep(j,26) cin >> s[i + 1][j];


  int score = 0;
  int res = 0;
  auto Scoring = [&](int d, int id, int oid) {
    score += s[d][id];
  
    if (oid != -1) {
      t[d - 1] = id;
      score -= s[d][oid];
      for (int i = d; i <= D; i++) {
        if (last_day[i][oid] != d) break;
        last_day[i][oid] = last_day[i - 1][oid];
        score += c[oid] * (i - d);
        score -= c[oid] * (i - last_day[i][oid]);
      }

      for (int i = d; i <= D; i++) {
        if (last_day[i][id] == i) break;
        score += c[id] * (i - last_day[i][id]);
        last_day[i][id] = d;
        score -= c[id] * (i - last_day[i][id]);
      }
    } else {
      last_day[d][id] = d;
      for (int i = 0; i < 26; i++) {
        if (i != id) last_day[d][i] = last_day[d - 1][i];
        score -= c[i] * (d - last_day[d][i]); 
      }
    }
  };

  auto init = [&](){
    for (int i = 0; i < D; i++) {
      cin >> t[i];
      t[i]--;
    }

  };
  
  //初期解生成 
  init();
  /*
  rep(p, 40000000) {

    int d = randxor() % D;
    int change_q = randxor() % 26;    
    int old_q = t[d];
    t[d] = change_q;
    int old_res = res;
    int old_score = score;
    Scoring(d + 1, change_q);
    if (res < old_res) {
      t[d] = old_q;
      res = old_res;
      score = old_score;
    }
  }
  */
  //cout << max(int(1e6 + score), 0) << endl;
  for (int i = 0; i < D; i++) {
    Scoring(i + 1, t[i], -1);
  } 
  int m;
  cin >> m;
  while(m--) {
    int d, q;
    cin >> d >> q;
    q--;
    Scoring(d, q, t[d - 1]);
    cout << score << endl;
  }
  return 0;
} 

Measured memory_bytes: 3672