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

int main()
{
    int N;
    cin >> N;
    string S;
    cin >> S;
    long long r = 0, g = 0, b = 0;
    for (int i = 0; i < S.length(); i++) {
        if (S[i] == 'R') r++;
        else if (S[i] == 'G') g++;
        else b++;
    }
    long long minus = 0;
    for (int i = 0; i < N - 2; i++) {
        for (int j = i + 1; j < N - 1; j++) {
            if (S[i] == S[j]) continue;
            int k = j * 2 - i;
            if (k >= N || S[i] == S[k] || S[j] == S[k]) continue;
            minus++;
        }
    }
    cout << r * g * b - minus << endl;
    return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    if(n>=2100){
        cout << 1<<endl;
        return 0;
    }
    int maki;
    for(int a=0;a<=21;a++){
        for(int b=0;b<=21;b++){
            for(int c=0;c<=21;c++){
                for(int d=0;d<=21;d++){
                    for(int e=0;e<=21;e++){
                        maki=a*100+b*101+c*102+d*103+e*104;
                        if(maki<=n && (n-maki)%105==0){
                            cout<< 1<<endl;
                            return 0;
                        }
                    }
                }
            }
        }
    }
    cout <<0<<endl;
    return 0;
}


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



int main() {
  string S; cin >> S;
  int i = S.size();
  if(S[i-1] == 's') cout << S << "es" << endl;
  else cout << S << 's'<<endl;

	return 0;
}



Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define all(V) V.begin(),V.end()
#define ll long long
#define MOD 998244353

ll ans;
string T;

void setting() {
	cin >> ans;
	T = to_string(ans);
}

char judge(ll N) {
	string S = to_string(N);
	if (S <= T && N <= ans)return 'Y';
	if (S > T&& N > ans)return 'Y';
	return 'N';
}

bool ask(ll N) {
	cout << "? " << N << endl;
	char X;
	cin >> X;
	if (X == 'Y')return 1;
	else return 0;
}

int main() {

	ll lv = 9999999999, rv = 99999999999, mid;
	while (rv - lv > 1) {
		mid = (lv + rv) / 2;
		if (ask(mid)) {
			rv = mid;
		}
		else {
			lv = mid;
		}
	}
	ll X = rv;
	while (X % 10 == 0) {
		if (!ask(X + 1)) {
			cout << "! " << X * 10 << endl;
			return 0;
		}
		X /= 10;
	}
	if (X % 10 == 9) {
		if (ask((X - 1) * 10)) {
			cout << "! " << X * 10 << endl;
		}
		else {
			cout << "! " << X << endl;
		}
	}
	else {
		if (ask(X + 1)) {
			cout << "! " << X << endl;
		}
		else {
			cout << "! " << X * 10 << endl;
		}
	}
	
}

Measured memory_bytes: 596
n = gets.to_s.to_i

a = Array.new(n+1){|i| i }
c = Array.new(10){ Array.new(10){ 0 } }

ans = 0
1.upto(n) do |i|
  
  f = i.to_s[0].to_i
  e = i.to_s[-1].to_i
  
  ans += c[e][f] * 2
  c[f][e] += 1
  ans += 1 if e == f
end

puts ans

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

using namespace std;

int max3(int a,int b,int c){
	return max(a,max(b,c));
}

int main(){
	

	int a,b;
	cin>>a>>b;

	cout<<max3(a+b,a-b,a*b)<<endl;


	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <cstdio>

using namespace std;

const long long INF = 100000000;
const long long MOD = 1000000007;


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

int main()
{
  long long N, M;
  cin >> N >> M;
  vector<pair<long long, long long>> v;
  for (int i = 0; i < N; i++)
  {
    long long a = 0;
    cin >> a;
    v.push_back(make_pair(a,1));
  }

  for (int i = 0; i < M;i++){
    long long b, c;
    cin >> b >> c;
    v.push_back(make_pair(c, b));
  }
  sort(v.begin(), v.end(), greater<pair<long long, long long>>());
  long long i = 0;
  long long ans = 0;
  while (N >= 0)
  {
    ans += v[i].first * min(N, v[i].second);
    N -= v[i].second;
    i++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 6128
#include "bits/stdc++.h"

using namespace std;


#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()

#define int long long

#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second

#define mod 1000000007

template <typename T>
void print(T x)
{
	std::cout << x <<" " ;
}


template <typename T>
void println(T x)
{
	std::cout << x << "\n";
}


signed main(void) {
	int N,M;
	cin >> N>>M;
	vector<int>b(N+1, 0);
	vector<int>ans(N+1, 0);
	int tmp;
	rep(i, M) {
		cin >> tmp;
		b[tmp] = 1;
	}

	ans[0] = 1;
	if (b[1] == 0)ans[1] = 1;
	else if (b[1] == 1)ans[1] = 0;

	FOR(i,2,N+1) {
		if (b[i] == 0)ans[i] = (ans[i - 1] + ans[i - 2])%mod;
		else ans[i] = 0;
	}
	print(ans[N] % mod);
}

Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<tuple>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<deque>
#include<cmath>
#include<stack>
#include<string.h>
#include <iomanip>
#define rep(i,n) for(int i = 0;i<n;i++)
#define _GLIBCXX_DEBUG
using ll = long long; 
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
	int n,k;
	cin >> n >> k;
	vector<int>h(n);
	rep(i,n) cin >> h[i];
	sort(h.begin(),h.end());
	int ans = 1000000000;
	for(int i = 0;i+k-1<n;i++) {
		ans = min(ans,h[i+k-1]-h[i]);
	}
	cout << ans << endl;
}

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

#define max_n 200001

int main(void){
    ll n,k; cin >> n >> k;
    vector<ll>num(max_n,0);
    for(int i=0;i<n;i++){
        ll tmp; cin >> tmp;
        num[tmp]++;
    }

    ll kind=0;
    for(int i=0;i<max_n;i++){
        if(num[i]!=0) kind++;
    }
    sort(num.begin(),num.end());

    // for(int i=0;i<n;i++){
    //     cout << num[i] << ' ';
    // }
    // cout << endl;

    kind -= k;
    // cout << kind;
    ll i=0,cnt=0;
    while(0<kind){
        if(num[i]!=0) cnt+=num[i],kind--;
        i++;
    }

    cout << cnt << endl;
    

    
    
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n; scanf("%d", &n);
  vector<long long> a(n);
  for(int i = 0; i < n; i++) {
    scanf("%lld", &a[i]);
  }
  for(int i = 1; i < n; i++) {
    a[i] += a[i-1];
  }
  long long ans = 9e18;
  for(int i = 0; i+1 < n; i++) {
    ans = min(ans, abs((a.back() - a[i]) - a[i]));
  }
  printf("%lld\n", ans);
  return 0;
}

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

using P = std::pair<int64_t, int64_t>;

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

    std::vector<P> plus;
    std::vector<P> minus;

    int64_t i = 0;
    while (true) {
        const int64_t f = std::pow(i, 5);
        if (f > 100000000000000000) {
            break;
        }

        plus.push_back({i, f});        
        minus.push_back({-i, -f});        
        ++i;
    }

    for (const auto& a : plus) {
        for (const auto& b : plus) {
            if ((a.second - b.second) == X) {
                std::printf("%ld %ld\n", a.first, b.first);
                return 0;
            }
        }
    }

    for (const auto& a : plus) {
        for (const auto& b : minus) {
            if ((a.second - b.second) == X) {
                std::printf("%ld %ld\n", a.first, b.first);
                return 0;
            }
        }
    }
        
    return 0;
}


Measured memory_bytes: 4428
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();

        String[] days = new String[] {
            "SUN",
            "MON",
            "TUE",
            "WED",
            "THU",
            "FRI",
            "SAT"
        };

        for (int i = 0; i < days.length; i++) {
            if (days[i].equals(S)) {
                System.out.println(7 - i);
                System.exit(0);
            }
        }
    }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, Q;
  cin >> N >> Q;
  vector<ll> S(N), T(N), X(N);
  set<pair<ll, pair<int, ll>>> se;
  rep(i, N) {
    cin >> S[i] >> T[i] >> X[i];
    se.emplace(S[i]-X[i], make_pair(1, X[i]));
    se.emplace(T[i]-X[i], make_pair(-1, X[i]));
  }
  vector<pair<ll, int>> D(Q);
  rep(i, Q) {
    cin >> D[i].first;
    D[i].second = i;
  }
  sort(all(D));
  vector<ll> ans(Q, longinf);
  auto itr = se.begin();
  set<ll> se2; se2.insert(longinf);
  int cur = 0;
  while(true) {
    if(cur == Q) break;
    while(itr != se.end() && itr->first <= D[cur].first) {
      if(itr->second.first == 1) {
        se2.insert(itr->second.second);
      } else {
        se2.erase(itr->second.second);
      }
      itr++;
    }
    if(itr == se.end()) break;
    ans[D[cur].second] = *se2.begin();
    cur++;
  }
  rep(i, Q) cout << (ans[i]==longinf ? -1 : ans[i]) << "\n";
  return 0;
}


Measured memory_bytes: 46896
x,k,d=map(int,input().split())

if abs(x)//d < k:
  #最小までいく。
  if (k-abs(x)//d)%2==0:
    if x>=0:
      print(abs(x-(x//d)*d))
    else:
      print(abs(x+(abs(x)//d)*d))
  else:
    if x>=0:
      print(abs(x-(x//d)*d-d))
    else:
      print(abs(x+(abs(x)//d)*d+d))
else:
  if x>=0:
    print(abs(x-k*d))
  else:
    print(abs(x+k*d))

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

int main() {
    int k, a, b;
    cin >> k >> a >> b;
    for(int i=a; i<=b; i++) {
        if(i%k == 0) {
            cout << "OK" << endl;
            return 0;
        }
    }
    cout << "NG" << endl;
}

Measured memory_bytes: 3592
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long lint;

struct unionfind_t {
  int n;
  vector<int> parent, rank;
  unionfind_t(int _n): n(_n), parent(n), rank(n, 0) {
    iota(parent.begin(), parent.end(), 0);
  }
  int find(int v) {
    if (v == parent[v]) return v;
    return parent[v] = find(parent[v]);
  }
  int join(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return a;
    if (rank[a] > rank[b]) swap(a, b);
    parent[a] = b;
    if (rank[a] == rank[b]) ++rank[b];
    return b;
  }
};

int main() {
  int n, m;
  scanf("%d %d", &n, &m);

  struct node_t {
    lint min_stand, cost;
  };
  lint cost_sum = 0LL;
  vector<node_t> nodes(n);
  for (int i = 0; i < n; ++i) {
    scanf("%lld %lld", &nodes[i].min_stand, &nodes[i].cost);
    cost_sum += nodes[i].cost;
  }

  vector<vector<int>> adj(n);
  for (int i = 0; i < m; ++i) {
    int a, b;
    scanf("%d %d", &a, &b), --a, --b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  struct dp_t {
    lint total;
    lint worst_state;
  };

  vector<dp_t> dp(n);
  unionfind_t uf(n);

  vector<int> sorted_by_min_stand(n);
  iota(sorted_by_min_stand.begin(), sorted_by_min_stand.end(), 0);
  sort(sorted_by_min_stand.begin(), sorted_by_min_stand.end(),
       [&nodes](int a, int b) {
         return nodes[a].min_stand - nodes[a].cost <
           nodes[b].min_stand - nodes[b].cost;
       });
  vector<bool> mark(n, false);
  for (int v : sorted_by_min_stand) {
    static vector<int> cnts; cnts.clear();
    mark[v] = true;
    for (int u : adj[v])
      if (mark[u]) {
        cnts.push_back(uf.find(u));
      }
    sort(cnts.begin(), cnts.end());
    cnts.resize(unique(cnts.begin(), cnts.end()) - cnts.begin());

    lint cnts_total = 0LL;
    for (int cnt : cnts)
      cnts_total += dp[cnt].total;

    dp_t result;
    result.total = cnts_total + nodes[v].cost;
    result.worst_state = -cnts_total - nodes[v].min_stand;

    for (int cnt : cnts) {
      lint others_total = cnts_total - dp[cnt].total;

      result.worst_state =
        max(result.worst_state,
            min({-others_total - nodes[v].cost + dp[cnt].worst_state,
                 -others_total - nodes[v].min_stand}));
    }

    int joined_cnt = v;
    for (int cnt : cnts) joined_cnt = uf.join(joined_cnt, cnt);
    dp[joined_cnt] = result;
  }
  printf("%lld\n", max(cost_sum, -dp[uf.find(0)].worst_state));
  return 0;
}


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

// UnionFind
// coding: https://youtu.be/TdR816rqc3s?t=726
// comment: https://youtu.be/TdR816rqc3s?t=6822
struct UnionFind {
  vector<int> d;
  UnionFind(int n=0): d(n,-1) {}
  int find(int x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y);}
  int size(int x) { return -d[find(x)];}
};

int main() {
    ll N,M;
    cin >> N >>M;
    vector<ll> p(N);
    for(int i=0;i<N;i++){
        ll a;
        cin >> a;
        --a;
        p[i] = a;
    }
    UnionFind uf = UnionFind(N);
    for(int i=0;i<M;i++){
        ll x,y;
        cin >> x >> y;
        --x;--y;
        uf.unite(x,y);
    }
    ll ans = 0;
    for(int i=0;i<N;i++){
        if(uf.same(i,p[i])){
            ans++;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1408
#include<stdio.h>
int main(){
  int n;
  scanf("%d",&n);
  int a[n];
  int i,j;
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  int x;
  int cont=0;
  int flag=1;
  while(flag){
    flag=0;
    for(j=n-1;j>0;j--){
      if(a[j]<a[j-1]){
	x=a[j];
	a[j]=a[j-1];
	a[j-1]=x;
	cont++;
	flag=1;
      }
    }
  }
  for(i=0;i<n-1;i++)printf("%d ",a[i]);
  printf("%d\n%d\n",a[n-1],cont);
  return 0;
}



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

#define rep(i, n)    for(int i = 0; i < n;i++)
#define repwi(i, ini, n) for(int i = ini; i < n;i++)

int main()
{
    int N;
    string S;
    cin >> N >> S;
    int sum = 0;
    for (int i = 0; i < N - 2;i++){
        if(S[i] == 'A' && S[i + 1] == 'B' && S[i + 2] == 'C'){
            sum++;
        }
    }

    cout << sum << endl;
}

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

int main(void){
    int N;
    int s[100];
    cin >> N;

    for(int i=0 ;i <N;i++){
      cin >> s[i];
    }
    int cnt=0;
    for(int i=0 ;i < (N-1);i++){
      //cout<<i<<endl;
      if(s[i]==s[i+1]){
        cnt++; i++;
      }

    }
    cout<<cnt;
    // cout<<<<endl;
    // printf("%d");
    // vector<int> data(N);
    // sort(data.begin(),data.end());//昇順ソート


    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;
inline int getInt() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MX = 200005;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
//---------------------------------------------------------------
#define fastio std::ios::sync_with_stdio(false);
#define myio ifstream iofi; if(argc>1){iofi.open(argv[1]); std::cin.rdbuf(iofi.rdbuf());}
//--------------------------------------------------------------


int main(int argc,char** argv){ fastio; myio;
  int n;
  cin>>n;
  bool f[n][10];
  rep(i,n) rep(j,10) cin>>f[i][j];
  ll p[n][11];
  rep(i,n) rep(j,11) cin>>p[i][j];
  priority_queue<ll> q;
  srep(i,1,1024){
    bitset<10> op(i);
    int c[n];
    rep(i,n) c[i]=0;
    rep(j,10){
      rep(k,n){
        if( op[j] and f[k][j] ) c[k]++;
      }
    }
    ll prof=0;
    rep(k,n){
      prof += p[k][c[k]];
    }
    q.push(prof);
  }
    cout<<q.top();
}

Measured memory_bytes: 256
N = int(input())
A = [int(a) for a in input().split()]

A.sort()
B = [abs(a-b) for a,b in zip(range(N-1,-1,-1),range(N))]
B.sort()

if A==B:
    print(pow(2,N//2,10**9+7))
else:
    print(0)


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

int main(){
    int H, W, i, j;
    for( i = 0;; i++){
        cin >> H >> W;
        if( H == 0 && W == 0) break;
        for( i = 0; i < W; i++) cout << "#";
        cout << endl;
        for( i = 1; i < H - 1; i++){
            for( j = 0; j < W; j++){
                if( j == 0 || j == W - 1){
                    cout << "#";
                }else cout << ".";
            }
            cout << endl;
        }
        for( i = 0; i < W; i++){
            cout << "#";
            if( i == W - 1) cout << endl;
        }
        if( i != H - 2) cout << endl;
    }
}


Measured memory_bytes: 3088
H, W = map(int, input().split())
S, U = [], []
for _ in range(H):
    s = list(input())
    if "#" in s: S.append(s)
T = list(zip(*S))
for i in range(W):
    if "#" in T[i]: U.append(T[i])
res = []
for t in zip(*U):
    res.append("".join(t))
print("\n".join(res))

Measured memory_bytes: 62956
#include <bits/stdc++.h>
#include"atcoder/all"

using namespace std;
using namespace atcoder;

int main() {
    int n, q;
    cin >> n >> q;
    dsu d(n);
    for (int i = 0; i < q; ++i) {
        int t, u, v;
        cin >> t >> u >> v;
        if (t == 0) {
            d.merge(u, v);
        } else if (t == 1) {
            if (d.same(u, v)) {
                printf("1\n");
            } else {
                printf("0\n");
            }
        }

    }
    return 0;
}


Measured memory_bytes: 3900
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>//小数点以下表示
#include<map>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)

int main(){
    map<int64_t,int64_t> kazu;
    int64_t n;
    cin>>n;
    vector<int64_t> vec(n);
    rep(i,n){
        int64_t a;
        cin>>a;
        kazu[a]++;
        vec.at(i)=a;
    }
    int64_t Max=0;
    auto begin=kazu.begin(),end=kazu.end();
    for(auto iter=begin;iter!=end;iter++){
        Max+=(iter->second)*((iter->second)-1)/2;
    }
    rep(i,n){
        cout<<Max-(kazu[vec.at(i)]-1)<<endl;
    }
}


Measured memory_bytes: 12288
#include<iostream>
#include<algorithm>
#include<cmath>
#include<complex>
#include<vector>
/*
自分のコードは定数倍落ち
AC記録用コピペコード
*/

#include<map>
#include<queue>
 
using namespace std;
 
typedef pair< int, int > Pi;
 
int p, q, a, n;
 
int rec( int bunbo, int bunsi, int cnt, int idx){ //rec(分母, 分子, 個数, 今のidx)
  if(cnt > n) return 0;
  if(bunbo * p == bunsi * q) return 1;
  if(bunbo * p < bunsi * q) return 0;
  int ret = 0;
  for(int i = idx; i * bunbo <= a; i++){
    ret += rec( bunbo * i, bunsi * i + bunbo, cnt + 1, i);
  }
  return ret;
}
 
int main(){
  while(cin >> p >> q >> a >> n, p||q||a||n){
    cout << rec( 1, 0, 0, 1) << endl;
  }
}


Measured memory_bytes: 2972
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define mod 998244353LL
#define eps 1e-13
// #define PI 3.141592653589793238L
#define INF 1000000011
#define INFLL 1000000000000000011LL
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define fo(i,a,n) for(i = (a); i < (n); i++)
#define gtl(x) getline(cin, (x))
#define flsh fflush(stdout)
#define sws ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define gcd __gcd
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)((a).size())
#define io_file freopen("D:/Coding Problems/Contest/input_file.in", "r", stdin); freopen("D:/Coding Problems/Contest/output_file.out", "w", stdout)

ll modx(ll Base, ll exponent)
{
	ll ans = 1;
	if(Base == 1)
		return Base;
	while(exponent)
	{
		if(exponent & 1)
			ans = (ans * Base)%mod;
		Base = (Base * Base)%mod;
		exponent = exponent >> 1;
	}
	return ans;
}

ll inmodx(ll num)
{
	return (modx(num, mod-2LL));
}

bool cmp(pair < pii, int > a, pair < pii, int > b)//true for a before b
{
	if(a.F.F/300 < b.F.F/300)
		return 1;
	if(a.F.F/300 > b.F.F/300)
		return 0;
	if(a.F.S < b.F.S)
		return 1;
	if(a.F.S > b.F.S)
		return 0;
	if(a.F <= b.F)
		return 1;
	return 0;
}

const int N = (2e5) + 9;
const int M = (N<<2) + 9;
const int LOGN = ((int)log2(N)) + 3;
const int LOGM = ((int)log2(M)) + 3;
const int BUCK = 2*550;
const int SQRT = BUCK+9;

int ht[N];
map < pii, bool > obs;
vi col[N];

void solve()
{
	int h, w, n, i, x, y, ans;
	bool flag = 0;
	cin >> h >> w >> n;
	ans = h;
	fo(i,1,n+1)
	{
		cin >> x >> y;
		obs[{x,y}] = 1;
		col[y].pb(x);
	}
	x = 1;
	fo(y,1,w+1)
	{
		ht[y] = x;
		while(x <= h)
		{
			x++;
			if(obs[{x,y}])
			{
				flag = 1;
				break;
			}
			if(!obs[{x,y+1}])
				break;
		}
		if(flag)
			break;
		if(x > h)
			break;
	}
	fo(y,1,w+1)
	{
		if(ht[y] == 0)
			break;
		sort(all(col[y]));
		for(auto z : col[y])
			if(z > ht[y])
			{
				ans = min(ans, z-1);
				break;
			}
	}
	cout << ans << '\n';
	return;
}

int main()
{
	sws;
	clock_t clk;
	clk = clock();
	// io_file;
	// srand (time(NULL));

	//Code here
	int t = 1, cs;
	cout << fixed << setprecision(9);
	// cin >> t;
	fo(cs,1,t+1)
	{
		// cout << "Case #" << cs << ": ";
		solve();
	}
	// Code ends here

	clk = clock() - clk;
	cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << "\n";
	return 0;
}

Measured memory_bytes: 42240
n=input()
l=len(n)
c=0
if l%2==0:
  for i in range(1,l,2):
    c+=9*(10**(i-1))
  print(c)
else:
  m=int(n)
  d=m-(10**(l-1))+1
  c+=d
  for i in range(1,l-1,2):
    c+=9*(10**(i-1))
  print(c)

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


def solve(K: int, N: int, A: "List[int]"):
    m = 0
    for i in range(N):
        d = A[i] if i == 0 else A[i] - A[i - 1]
        m = max(m, d)
        if i == N - 1:
            m = max(m, K + A[0] - A[i])
    print(K - m)

    return


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

if __name__ == '__main__':
    main()


Measured memory_bytes: 26228
#include<bits/stdc++.h>
#define int long long
const int mod = 1e9+7;
const int MAX = 3005;
using namespace std;
int dp[MAX][MAX];
int32_t main()
{
	int n;
	cin>>n;
	string str;
	cin>>str;
	memset(dp, 0, sizeof(dp));
	int pre[n+3];
	memset(pre, 0, sizeof(pre));
	if(str[0] == '<'){
		dp[1][2] = 1;
		pre[2] = 1;
	}
	else{
		dp[1][1] = 1;
		pre[1] = 1;
		pre[2] = 1;
	}

	auto add_self = [&] (int &x, int y)
	{
		x = (x+y)%mod;
		return x;
	};
	for(int i=2;i<n;i++)
	{
		if(str[i-1] == '<')
			dp[i][i+1] = pre[i];

		for(int j=1;j<=i;j++)
		{
			if(str[i-1] == '<')
				dp[i][j] = pre[j-1];
			
			else
				dp[i][j] = (pre[i]-pre[j-1]+mod)%mod;
			
		}
		for(int j=1;j<=n;j++)
			pre[j] = (pre[j-1] + dp[i][j])%mod;
	}
	int ans = 0;
	for(int i=1;i<=n;i++)
		add_self(ans, dp[n-1][i]); 
	
	cout<<ans;
}

Measured memory_bytes: 70784
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < n; ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
#define FORV(i, v) for (auto i = v.begin(); i != v.end(); i++)
using namespace std;

using ll = long long;

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; }
const int INF = 1001001001;
const long long INFLL = LLONG_MAX / 3;
const double eps = (1e-9);

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

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

  int n;
  cin >> n;
  vector<string> s(2);
  rep(i, 2) cin >> s[i];

  int idx = 0;
  int prev = 0;
  mint ans;
  while (idx < n) {
    if (s[0][idx] == s[1][idx]) {
      if (prev == 0) ans = 3;
      else if (prev == 1) ans *= 2;
      else ans *= 1;
      prev = 1;
      idx++;
    } else {
      if (prev == 0) ans = 6;
      else if (prev == 1) ans *= 2;
      else ans *= 3;
      prev = 2;
      idx += 2;
    }
  }

  cout << ans.x << endl;

  return 0;
}


Measured memory_bytes: 256
S = input()
S = list(S)
count = 0
while count == 0:
  if 'N' in S:
    if'S' in S:
      count += 1
    else:
      print('No')
      break
  if 'S' in S:
    if'N' in S:
      count += 1
    else:
      print('No')
      break
  if 'E' in S:
    if'W' in S:
      count += 1
    else:
      print('No')
      break
  if 'W' in S:
    if'E' in S:
      count += 1 
    else:
      print('No')
      break
else:
  print('Yes')

Measured memory_bytes: 9048
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstdlib>
#include <cmath>
#include<stdio.h>
#include<queue>
#include<stack>
#include<set>
#define ll long long
#define MAX 1000000000000000000LL
ll inf=100000000000007;
using namespace std;

int main(){
    int n;cin>>n;
    vector<int> v;
    int a;
    for(int i=0; i<n; i++){
        cin>>a;
        v.push_back(a);
    }
    sort(v.begin(),v.end());
    int type=1;
    for(int i=1; i<n; i++){
        if(v[i-1]!=v[i])type++;
    }
    int ans;
    if(type%2==0)ans=type-1;
    else ans=type;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 892
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<ll, ll>;
#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 all(x) (x).begin(), (x).end()
const ll INF = ll(1e18)+1;

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

    ll n;
    cin >> n;
    vector<ll> ai(n);
    rep(i,n) cin >> ai[i];

    sort(all(ai),greater<int>());
    ll result = 0;

    vector<ll> check;
    check.push_back(ai[0]);

    rep(i,n-1){
        result += check[i];
        check.push_back(ai[i+1]);
        check.push_back(ai[i+1]);
    }

    cout << result;
}

Measured memory_bytes: 8980
N,M = map(int,input().split())
L = []
R = []
for i in range(M):
    l,r = map(int,input().split())
    L.append(l)
    R.append(r)

L_max = max(L)
R_min = min(R)

result = R_min - L_max + 1

if result < 0:
    print(0)
else:
    print(result)

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

#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fst first
#define scd second

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

inline int read(){
	int f=1,x=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline ll readll(){
	ll f=1,x=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int MAXN=105,MOD=1e9+7;
inline int pow_mod(int x,int i){int y=1;while(i){if(i&1)y=(ll)y*x%MOD;x=(ll)x*x%MOD;i>>=1;}return y;}
int n,h[MAXN];
vector<int>vec,w[MAXN];
int solve1(int l,int r,int k,int low){
	//cout<<"dp1 "<<l<<" "<<r<<" "<<k<<endl;
	int mx=0,mn=2e9;
	for(int i=l;i<=r;++i)mx=max(mx,h[i]),mn=min(mn,h[i]);
	if(mn>k)return solve1(l,r,mn,low);
	if(mx==k&&mx==mn)return pow_mod(2,vec[k]-low);
	
	int ans=1,st=lob(w[k].begin(),w[k].end(),l)-w[k].begin(),ed=lob(w[k].begin(),w[k].end(),r)-w[k].begin();
	ed=min(ed,(int)w[k].size()-1);
	if(w[k][ed]>r)ed--;
	int lst=l;
	for(int i=st;i<=ed;++i){
		assert(w[k][i]>=l&&w[k][i]<=r);
		if(lst<=w[k][i]-1)ans=(ll)ans*solve1(lst,w[k][i]-1,k+1,vec[k])%MOD;
		lst=w[k][i]+1;
	}
	if(lst<=r)ans=(ll)ans*solve1(lst,r,k+1,vec[k])%MOD;
	ans=(ll)ans*pow_mod(2,vec[k]-low)%MOD;
	return ans;
}
int solve2(int l,int r,int k,int low){
	//cout<<l<<" "<<r<<" "<<k<<endl;
	int mx=0,mn=2e9;
	for(int i=l;i<=r;++i)mx=max(mx,h[i]),mn=min(mn,h[i]);
	if(mn>k)return solve2(l,r,mn,low);
	if(mx==k&&mx==mn)return (pow_mod(2,r-l+1)-2+pow_mod(2,vec[k]-low))%MOD;
	
	int st=lob(w[k].begin(),w[k].end(),l)-w[k].begin(),ed=lob(w[k].begin(),w[k].end(),r)-w[k].begin();
	ed=min(ed,(int)w[k].size()-1);
	if(w[k][ed]>r)ed--;
	vector<int>dp1,dp2;
	int lst=l,t=0;
	for(int i=st;i<=ed;++i){
		assert(w[k][i]>=l&&w[k][i]<=r);
		t++;
		if(lst<=w[k][i]-1)dp1.pb(solve1(lst,w[k][i]-1,k+1,vec[k])),dp2.pb(solve2(lst,w[k][i]-1,k+1,vec[k]));
		lst=w[k][i]+1;
	}
	if(lst<=r)dp1.pb(solve1(lst,r,k+1,vec[k])),dp2.pb(solve2(lst,r,k+1,vec[k]));
	int ans1=1,ans2=1;
	for(int i=0;i<(int)dp1.size();++i)ans1=(ll)ans1*(dp1[i]+dp2[i])%MOD,ans2=(ll)ans2*dp1[i]%MOD;
	ans1=(ll)ans1*pow_mod(2,t)%MOD;
	ans2=(ll)ans2*(pow_mod(2,vec[k]-low)-2)%MOD;
	return (ans1+ans2)%MOD;
}
int main() {
	n=read();
	for(int i=1;i<=n;++i)h[i]=read(),vec.pb(h[i]);
	vec.pb(0);
	sort(vec.begin(),vec.end());
	vec.erase(unique(vec.begin(),vec.end()),vec.end());
	for(int i=1;i<=n;++i)h[i]=lob(vec.begin(),vec.end(),h[i])-vec.begin(),w[h[i]].pb(i);
	cout<<solve2(1,n,1,0)<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,w[32],i=31;
	cin>>n;
	if(n==0) cout<<0;
	while(n!=0)
	{
		w[i]=n%(-2);
		n/=-2;
		if(w[i]<0){
			n++;
			w[i]-=-2;
		}
		i--;
	}
	for(int j=i+1;j<=31;j++) cout<<w[j];
} 

Measured memory_bytes: 256
//チェビシェフの定理
#include <iostream>
#include <math.h>

using namespace std;

int main(){
	int loader;//ローダー
	bool isprime = false;//素数判定用
	int primecount = 0;//素数の数

	while (1){
		cin >> loader;
		if (loader == 0)break;

		//素数チェック
		if (loader <= 2){//1,2なら1個(2 or 3)のみ
			cout << 1 << endl;
			continue;
		}

		//それ以外
		primecount = 0;
		for (int i = loader + 1; i <= loader * 2; ++i){
			isprime = true;
			if (i % 2 == 0){
				isprime = false;
			} else{
				for (int j = 3; j <= sqrt(i); j += 2){
					if (i % j == 0){
						isprime = false;
						break;
					}
				}
			}
			if (isprime)++primecount;
		}
		cout << primecount << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
N, M = map(int, input().split())
s = []
for i in range(0, N):
  x, y = map(int, input().split())
  s.append([x, y])
ch = []
for i in range(0, M):
  x, y = map(int, input().split())
  ch.append([x, y])
  
for x,y in s:
  dist_min = 10000000000
  min_n = 0
  n = 0
  for c, d in ch:
    n += 1
    dist = abs(x-c)+ abs(y-d)
    if dist_min > dist:
      dist_min = dist
      min_n = n
  print(min_n)

Measured memory_bytes: 3064
using System;

public class Sum
{
    private static void Main()
    {
        string[] abc = Console.ReadLine().Split(' ');
        int a = int.Parse(abc[0]);
        int b = int.Parse(abc[1]);
        int c = int.Parse(abc[2]);

        int tmp = 0;

        while (!(a <= b && b <= c))
        {
            if (a > b)
            {
                tmp = a;
                a = b;
                b = tmp;
            }
            if (b > c)
            {
                tmp = b;
                b = c;
                c = tmp;
            }
        }
        Console.WriteLine("{0} {1} {2}", a, b, c);
    }
}

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

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

  if (a % 2 == 0 || b % 2 == 0) {
    cout << "Even" << endl;
  }
 
  else {
    cout << "Odd" << endl;
  }
}


Measured memory_bytes: 380
#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>*/
 
#define pb push_back
#define mp make_pair
#define sz(s) ((int)(s.size()))
#define all(s) s.begin(), s.end()
#define rep(i, a, n) for (int i = a; i <= n; ++i)
#define per(i, n, a) for (int i = n; i >= a; --i)
#define onlycin ios_base::sync_with_stdio(false); cin.tie(0) 
using namespace std;
// using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
/*typedef tree<
pair < int, int >,
null_type,
less< pair < int, int > >,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;*/
// find_by_order() order_of_key()
const int MAXN = (int)5e5+228;
const char nxtl = '\n';
const int mod = (int)1e9+7;
const double eps = (double)1e-7;
template<typename T> inline bool updmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<typename T> inline bool updmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}

int n, res[MAXN];

inline int ask(int x) {
	if(res[x] > 0) return res[x];
	cout << x << endl;
	string s; cin >> s;
	if(s == "Vacant") exit(0);
	if(s == "Male") return res[x] = 1;
	return res[x] = 2;
}
inline bool ok(int l, int r) {
	int len = r - l + 1;
	int val1 = ask(l), val2 = ask(r);
	if(len % 2 == 1 && val1 == val2) return 0;
	if(len % 2 == 0 && val1 != val2) return 0;
	return 1;
}

int main() {
	#ifdef accepted
		// freopen(".in", "r", stdin);
		// freopen(".out", "w", stdout);
	#endif
	// onlycin;
	cin >> n;
	ask(0); ask(n-1);
	int l = 0, r = n-1;
	while(r - l > 1) {
		int mid = l + r >> 1;
		if(ok(0, mid)) r = mid;
		else l = mid+1;
	}
	rep(i, l, r) ask(i);
	assert(0);
	
	return 0;
}

Measured memory_bytes: 852
#include<bits/stdc++.h>
using namespace std;
#define all(a)  (a).begin(),(a).end()
typedef long long ll;
ll mod=1000000007;
string s;

bool sort2(tuple<int, string, int>&a, tuple<int, string, int>& b) {
  if (get<1>(a) < get<1>(b)) {
    return true;
  } else if(get<1>(a) == get<1>(b)) {
    if(get<2>(a) > get<2>(b)){
      return true;
    } else {
      return false;
    }
  } else {
    return false;
  }
}

int main() {
  int n;cin >> n;
  vector<tuple<int, string, int>> vt;
  int id =1;
  for(int i =0;i<n;++i){
    string c;int p;
    cin >> c >> p;
    vt.push_back(make_tuple(id,c,p));
    ++id;
  }
  sort(vt.begin(),vt.end(), sort2);
  std::vector<int> v(n);
  id =0;
  for (auto itr = vt.begin();itr !=vt.end();++itr){
    v[id] = get<0>(*itr);
    ++id;
  }
  for(int k = 0; k<n;++k){
    cout << v[k] << endl;
  }
  return 0;
}


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

template<class T> inline void chmin(T& a, const T& b) { if(b < a) a = b; }

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

	for(int c; cin >> c, c;) {
		vector<int> t(c);
		for(int i = 0; i < c; ++i)
			cin >> t[i];

		int n;
		cin >> n;

		vector<int> get_up(100, 24);
		for(int i = 0; i < n; ++i) {
			int d, m;
			cin >> d >> m;
			chmin(get_up[d - 1], m);
		}

		vector<int> dp(c, 101);
		dp[0] = 0;
		for(int i = 0; i < 100; ++i) {
			vector<int> tmp(c, 101);
			for(int j = 0; j < c; ++j) {
				chmin(tmp[1], dp[j] + 1);
				if(t[j] <= get_up[i])
					chmin(tmp[(j + 1) % c], dp[j]);
			}

			dp.swap(tmp);
		}

		cout << *min_element(dp.begin(), dp.end()) << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1200
//Daniel Grzegorzewski
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

#define MP make_pair
#define PB push_back
#define ST first
#define ND second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef long long LL;

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

const int N = 2*(int)1e5 + 5;
const int MOD = (int)1e9 + 7;

int h, w, n, sil[N], inv[N], dp[N];
PII a[N];
bool vis[N];

int fpow(int x, int y) {
  if (y == 0)
    return 1;
  if (y&1)
    return (x*fpow(x, y-1))%MOD;
  int res = fpow(x, y/2);
  return (res*res)%MOD;
}

int ne(int i, int j) {
  if (i < j)
    return 0;
  int res = sil[i]*inv[j]%MOD;
  return res*inv[i-j]%MOD;
}

bool git(PII x, PII y) {
  if (x.ST > y.ST || x.ND > y.ND)
    return false;
  return true;
}

int ile(PII x, PII y) {
  if (!git(x, y))
    return 0;
  return ne(y.ST-x.ST+y.ND-x.ND, y.ST-x.ST);
}

void licz(int nr) {
  vis[nr] = true;
  int res = ile({1, 1}, a[nr]);
  for (int i = 1; i <= n; ++i) {
    if (i == nr || !git(a[i], a[nr]))
      continue;
    if (!vis[i])
      licz(i);
    res -= dp[i]*ile(a[i], a[nr])%MOD;
    if (res < 0)
      res += MOD;
  }
  dp[nr] = res;
  return;
}

signed main() {
  init_ios();
  sil[0] = 1;
  for (int i = 1; i < N; ++i)
    sil[i] = i*sil[i-1]%MOD;
  inv[N-1] = fpow(sil[N-1], MOD-2);
  for (int i = N-2; i >= 0; --i)
    inv[i] = (i+1)*inv[i+1]%MOD;
  cin >> h >> w >> n;
  for (int i = 1; i <= n; ++i)
    cin >> a[i].ST >> a[i].ND;
  for (int i = 1; i <= n; ++i)
    if (!vis[i])
      licz(i);
  int wyn = ile({1, 1}, {h, w});
  for (int i = 1; i <= n; ++i) {
    wyn -= dp[i]*ile(a[i], {h, w})%MOD;
    if (wyn < 0)
      wyn += MOD;
  }
  cout<<wyn<<"\n";
}

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

using namespace std;
#define MOD 1e9
typedef long long ll;

int a, b, c, k;

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

  cin>>a>>b>>c>>k;

  if(k <= a) cout<<k;
  else if(k <= a + b) cout<<a;
  else cout<<(a - (k - a - b));

  return 0;
}


Measured memory_bytes: 3612
#include"bits/stdc++.h"
#include"math.h"
using namespace std;

using ll = long long int;
using ld = long double;
using pii = pair<int,int>;

#define REP(i,m,n) for(ll i = m; i < (ll)(n);++i)
#define rep(i,n) REP(i,0,n)
#define all(v) v.begin(),v.end()

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

Measured memory_bytes: 256
object Main {
    def main(args:Array[String]) = {
        val sc = new java.util.Scanner(System.in)
        while(sc.hasNext){
	        val n = sc.nextInt
	        val list = for(a <- 0 to 9; b <- 0 to 9; c <- 0 to 9; d <- 0 to 9 if a+b+c+d == n) yield 1
	        println(list.size)
    	}
    }
}

Measured memory_bytes: 76892
class node:
    def __init__(self):
        self.p = -1
        self.l = -1
        self.r = -1

def preParse(u):
    if u == -1:
        return
    print(" " + str(u), end = '')
    preParse(T[u].l)
    preParse(T[u].r)

def inParse(u):
    if u == -1:
        return
    inParse(T[u].l)
    print(" " + str(u), end = '')
    inParse(T[u].r)

def postParse(u):
    if u == -1:
        return
    postParse(T[u].l)
    postParse(T[u].r)
    print(" " + str(u), end = '')

root = -1
def insert(T, z):
    global root
    parent = -1
    u = root
    while u != -1:
        parent = u
        if z < u:
            u = T[u].l
        else:
            u = T[u].r
    T[z].p = parent
    if parent == -1:
        root = z
    elif z < parent:
        T[parent].l = z
    else:
        T[parent].r = z


n = int(input())
cmdList = [input() for _ in range(n)]
T = {int(cmd[7:]): node() for cmd in cmdList if cmd[0] == "i"}

for cmd in cmdList:
    if cmd[0] == "p":
        inParse(root)
        print("")
        preParse(root)
        print("")
    else:
        insert(T, int(cmd[7:]))


Measured memory_bytes: 177104
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define gcd __gcd
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define gcd __gcd
//SUNEET KUMAR -->  ਸੁਨੀਤ  
int power(int a,int n)//binary expo
{
    int r;
    if(n==0)
        return 1;
    else if(n==1)
        return a;
    else
        r=power(a,n/2);
    if(n%2==0)
        return ((r)%mod)*((r)%mod)%mod;
    else
        return ((((r)%mod)*((r)%mod))%mod*((a)%mod))%mod;
}
int max(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}
signed main()
{ 
     int n;
     cin>>n;
     int a[n+4];
     int dp[n+2];

     for(int i=1;i<=n;i++)
     {
         cin>>a[i];
     
     }
     dp[1]=0;
     dp[2]=abs(a[2]-a[1]);
     for(int i=3;i<=n;i++)
     {
         dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
     }
     cout<<dp[n]<<endl;

}

Measured memory_bytes: 1792
// ?????¬???????????¬??????

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int

template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}

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

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
constexpr ll INF = 1001001001001001LL;
constexpr ll MOD = 1000000007LL;

// ?????°??¶????????????????????¶????????????
// ?????? v_i ??§?????? w_i ???????????? m_i ???????????¶?????§
// ????????¶??? W ??????????????¶???????????????????????§???

// dp[i] := (index, weight) -> value
int dp[10010];
int v[110], w[110], m[110];

void solve() {
    int N, W; cin >> N >> W;
    rep(i,0,N) cin >> v[i] >> w[i] >> m[i];

    rep(i,0,N) {
        int rest = m[i], k = 0;
        while(rest > 0) {
            int take = min(rest, 1LL << k++);
            rest -= take;

            repr(j,W,0) {
                if(j-take*w[i] < 0) continue;
                chmax(dp[j], dp[j-take*w[i]] + take*v[i]);
            }
        }
    }
    cout << *max_element(dp, dp+W+1) << endl;
}

signed main() {
    solve();
    return 0;
}

Measured memory_bytes: 3176
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;

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

const ll mod=1e9+7;

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n);
    ll val=-1;
    ll pos=-1;
    ll sg=-1;
    rep(i,n){
        cin >> a[i];
        if(val<abs(a[i])){
            val=abs(a[i]);
            pos=i;
            if(a[i]>=0){
                sg=1;
            }
            else{
                sg=0;
            }
        }
    }
    cout << 2*n-2 << endl;
    rep(i,n){
        if(i==pos) continue;
        a[i]+=a[pos];
        cout << pos+1 << " " << i+1 << endl;
    }
    if(sg){
        rep(i,n-1){
            cout << i+1 << " " << i+2 << endl;
        }
    }
    else{
        rep(i,n-1){
            cout << n-i << " " << n-i-1 << endl;
        }
    }
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = (int)1e5 +10;
const int MOD = 1e9 + 7;
 
ll qpow(ll a, ll n)
{
    ll re = 1;
    while(n)
    {
        if(a&1) re = (re*a)%13;
        n = n>>1;
        a = (a*a)%13;
    }
    return re;
 
}
 
int mod[maxn][10];//第i位值为j的数对13取余的值
ll dp[maxn][20];//第i位对j取余的个数
void init()
{
    ll num = 1;
    for(int i = 1; i < maxn; i++)
    {
        for(int j = 0; j < 10; j++)
            mod[i][j] = j * num % 13;
        num = num * 10 % 13;
    }
}
int main()
{
//    while(1)
//    {
        string s;
        cin>>s;
        reverse(s.begin(),s.end());
        init();
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        for(int i = 0; i < s.length(); i++)
        {
            if(isdigit(s[i]))
            {
                for(int j = 0; j < 13; j++)
                {
                    dp[i+1][(mod[i+1][s[i] - '0'] + j)%13] = dp[i][j];
                }
            }
            else
            {
                for(int j = 0; j < 10; j++)
                {
                    for(int k = 0; k < 13; k++)
                    {
                        ll x = (mod[i+1][j] + k)%13;
                        dp[i+1][x] = (dp[i+1][x] +dp[i][k])%MOD;
                    }
                }
            }
        }
        cout<<dp[s.length()][5]<<endl;
//    }
 
 
 
    return 0;
}


Measured memory_bytes: 20096