akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <functional>
using namespace std;
#define int long long
#define All(v) (v).begin(),(v).end()
const int mod = 1000000007;
const int inf = mod*mod;
const int d5 = 100100;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a,b,k;
    cin>>a>>b>>k;
    if(a>=k){
        a-=k;
        cout<<a<<' '<<b<<endl;
        return 0;
    }
    else{
        b-=k-a;
        cout<<0<<' '<<max(0ll,b)<<endl;
    }
}

Measured memory_bytes: 256
process.stdin.resume();
process.stdin.setEncoding('utf8');

var lines = []
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});

reader.on('line', (line) => {
  lines.push(line);
});

reader.on('close', () => {
 var ab = lines[0].split(' ');
 var a = Number(ab[0]);
 var b = Number(ab[1]);
var outlet = 1;
var ans = 0;

while(outlet < b){
  outlet--;
  outlet += a;
  ans++;
}


console.log(ans);
 
});

Measured memory_bytes: 7628
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> 	pii;
typedef long long 		ll;
typedef vector<int> 	vi;
#define PI 				3.14159265
#define int				long long
#define f 				first
#define s 				second
#define umap 			unordered_map
#define pb 				push_back
#define eb 				emplace_back
#define ins 			insert
#define all(a) 			a.begin(),a.end()
#define mtup 			make_tuple
#define nl 				'\n'
#define FLASH 			ios_base::sync_with_stdio(false);cin.tie(NULL);
#define maxheap 		priority_queue<ll>
#define minheap 		priority_queue<ll,vector<ll> ,greater<ll>>
#define rep(i,s,e)		for (int i = s; i <= e; i++)
#define repr(i,s,e) 	for (int i = s; i >= e; i--)
#define mem0(a)			memset(a, 0, sizeof(a))
#define mem1(a)			memset(a, -1, sizeof(a))
#define beg(a)			a.begin()
#define sz(x) 			((int)(x.size()))
#define len(str)		((int)(str.length()))
const ll inf = 1e18 + 1;
const int mod = 998244353;
const int maxn = 3e5;
ll modpow(ll a,ll b,int mod = inf) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int gcd(int a,int b) {return __gcd(a,b);}
int n, h[maxn], mincost = LLONG_MAX, dp[maxn];

int solve(int i){
	if (i == 1) return dp[i] = 0;
	if (dp[i] != inf) return dp[i];
	if (i - 1 >= 1) dp[i] = min(solve(i - 1) + abs(h[i - 1] - h[i]), dp[i]);
	if (i - 2 >= 1) dp[i] = min(solve(i - 2) + abs(h[i - 2] - h[i]), dp[i]);
	return dp[i];
}

signed main(){
	FLASH
	cin>>n;
	rep(i,1,n) cin>>h[i];
	rep(i,1,200000) dp[i] = inf;
	cout<<solve(n);
	return 0;
}


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

void count_num(ll n, unordered_map<ll, ll> &count, unordered_map<ll, ll> &over_count) {
  if (over_count.count(n)) over_count[n]++;
  else {
    count[n]++;
    if (count[n] > 1) over_count[n] = count[n];
  }
}

int main() {
  ll MAX = 1000000;
  vector<ll> min_div(MAX + 1, 1);
  for (int i = 2; i <= MAX; ++i) {
    if (min_div[i] == 1) {
      for (int j = i; j <= MAX; j+= i) {
        min_div[j] = i;
      }
    }
  }

  IN(ll, N);
  vector<ll> A(N);
  unordered_map<ll, ll> count;
  unordered_map<ll, ll> over_count;
  REP(i, N) {
    IN(ll, A);
    ll tmp_div = 1;
    while(A != 1) {
      if (tmp_div != min_div[A]) {
        tmp_div = min_div[A];
        count_num(tmp_div, count, over_count);
      }
      A /= tmp_div;
    }
  }

  if (over_count.size() == 0) {
    cout << "pairwise coprime" << endl;
    return 0;
  }
  bool is_pairwise = true;
  for (auto itr = over_count.begin(), itr_end = over_count.end(); itr != itr_end; ++itr) {
    if (itr->second == N) {
      cout << "not coprime" << endl;
      return 0;
    }
  }
  cout << "setwise coprime" << endl;

  return 0;
}


Measured memory_bytes: 23988
#include <stdio.h>
#include <string.h>

int main(){
  int k;
  char s[105];
  scanf("%d %s", &k, s);

  if(strlen(s) <= k){
    printf("%s\n", s);
  }else{
    for(int i=0; i<k; i++)
      printf("%c", s[i]);
    printf("...\n");
  }

  return 0;
}


Measured memory_bytes: 1616
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <unordered_map>
constexpr int MOD = 1000000000 + 7;
constexpr int INF = 2000000000;
using namespace std;
using LL = long long;

int C[100001];

int main() {
	int n;
	cin >> n;
	int a;
	for (int i = 0; i < n; i++) {
		cin >> a;
		C[a]++;
	}
	LL ans = 1;
	if (n % 2 == 0) {
		bool isok = true;
		for (int i = 1; i < n; i += 2) {
			if (C[i] != 2)isok = false;
		}
		if (isok) {
			for (int i = 0; i < n / 2; i++) {
				ans = ans * 2 % MOD;
			}
			cout << ans << endl;
		}
		else {
			cout << 0 << endl;
		}
	}
	else {
		bool isok = true;
		if (C[0] != 1)isok = false;
		for (int i = 2; i < n; i += 2) {
			if (C[i] != 2)isok = false;
		}
		if (isok) {
			for (int i = 0; i < n / 2; i++) {
				ans = ans * 2 % MOD;
			}
			cout << ans << endl;
		}
		else {
			cout << 0 << endl;
		}
	}
}

Measured memory_bytes: 640
#include<iostream>
#include<cmath>
#include<vector>
#define ll long long 



using namespace std;

// ll dp[102][100005];
ll mod = 1e9 + 7;


vector<vector<ll>> multiply(vector<vector<ll>> A, vector<vector<ll>> B){

	int n = A.size();

	vector<vector<ll>> res(n, vector<ll>(n, 0));

	for(int i = 0; i < n; i++){
		for(int j = 0; j <n ; j++){

			for(int x = 0; x < n; x++){
				res[i][j] = (res[i][j]+ A[i][x] * B[x][j]) % mod;
			}
		}
	}
	return res;

}



vector<vector<ll>> power(vector<vector<ll>> mat, ll exp){

	if (exp == 1)
		return mat;

	vector<vector<ll>> res = power(mat, exp/2);

	if(exp & 1){
		return multiply(multiply(mat, res ), res);
	}
	else return multiply(res, res);

}

ll solve(vector<vector<ll>>& adj, int n, ll k)
{
	
	vector<vector<ll>> ak = power(adj, k);

	ll ans = 0;
	for(int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			ans = (ans + ak[i][j]) % mod;
		}
	}
	
	return ans;

}


int main(){

	int n;
	ll k;

	cin >> n >> k;
	
	vector<vector<ll>> adj(n, vector<ll>(n));

	for(int i = 0; i< n; i++){
		for(int j = 0; j< n; j++){
			cin >> adj[i][j];
		}
	}

	cout << solve(adj, n, k) << endl;
	return 0;
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll d,n;
    cin>>d>>n;
    ll sum=0;
    for(int i=0;i<n;i++){
        ll x;
        cin>>x;
        sum+=x;
    }
    cout<<max(-1LL,d-sum)<<endl;
    return 0;
}


Measured memory_bytes: 3632
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);

	static void solve() {
		int max = 0;
		int[] cnt = new int[200];
		while (in.hasNext()) {
			max = Math.max(++cnt[in.nextInt()], max);
		}
		for (int i=0; i<101; i++) {
			if (cnt[i] == max) out.println(i);
		}
	}

	public static void main(String[] args) {
		long start = System.currentTimeMillis();

		solve();
		out.flush();

		long end = System.currentTimeMillis();
		//trace(end-start + "ms");
		in.close();
		out.close();
	}

	static void trace(Object... o) { System.out.println(Arrays.deepToString(o));}
}

Measured memory_bytes: 26540
#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>

using namespace std;

constexpr int M_MAX = 100;
constexpr int N_MAX = 20;
constexpr int INF = 1e8;

int main()
{
  int n,m,a,b,c,d,s,g,V,P,reward;
  struct edge {
    edge(int t, int c)
      : to_(t), cost_(c) {};
    int to_;
    int cost_;
  };
  vector<edge>G[M_MAX];
  typedef pair<int,int> PII;
  vector<int> q(N_MAX);
  priority_queue<PII,vector<PII>,greater<PII>> que;

  cin >> n;
  cin >> m;
  for (int i=0;i<m;++i) {
    scanf("%d,%d,%d,%d",&a,&b,&c,&d);
    G[a].push_back(edge(b,c));
    G[b].push_back(edge(a,d));
  }
  scanf("%d,%d,%d,%d",&s,&g,&V,&P);

  reward = V-P;

fill(q.begin(),q.end(),INF);
  que.push(PII(s,0));
  q[s] = 0;

  while(!que.empty()){
    PII k  = que.top();
    que.pop();
    int l = k.first;

    for(int i=0;i<G[l].size();i++){
      edge r = G[l][i];
      if(q[r.to_] > q[l] + r.cost_){
        q[r.to_] = q[l] + r.cost_;
        que.push(PII(r.to_, q[r.to_]));
      }
    }
  }

  reward = reward - q[g];

fill(q.begin(),q.end(),INF);
  que.push(PII(g,0));
  q[g] = 0;

  while(!que.empty()){
    PII e = que.top();
    que.pop();
    int l = e.first;

    for(int i=0;i<G[l].size();i++){
      edge w = G[l][i];
      if(q[w.to_] > q[l] + w.cost_){
        q[w.to_] = q[l] + w.cost_;
        que.push(PII(w.to_, q[w.to_]));
      }
    }
  }

  reward = reward - q[s];

  cout << reward << endl;

  return 0;
}

Measured memory_bytes: 3124
#include<map>
#include<set>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<chrono>
#include<stack>
#include<fstream>
#include<list>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define SIZE(a) ll(a.size())
#define vll vector<ll> 
#define MEMSET(a, n, m) for(ll i=0;i<=n;i++) a[i] = m
#define BIT(n) (ll(1)<<n)
#define UNIQUE(v) v.erase(unique(v.begin(),v.end()),v.end()) 
#define UNIQUE_ARRAY(a,x) unique(a + 1, a + x + 1) - a - 1
#define SORT(a,n) sort(a+1,a+n+1)
#define SORT_O(a,n,order) sort(a+1,a+n+1,order)
#define PER(i,y,x) for(ll i=y;i>=x;i--)
typedef long long ll;
using namespace std;

struct rect {
	ll hei; ll pos;
};
ll const MAX = 1e5 + 5;
ll frm[MAX] = {};
vll G[MAX];
vll K[MAX];
vll topsort;
ll color[MAX] = {};

void f(ll i) {
	topsort.push_back(i);
	for (auto x : G[i]) {
		frm[x]--;
		if (frm[x] == 0) {
			color[x] = 1;
			f(x);
		}
	}
}

ll dp[MAX] = {};

int main(){
	ll n, m;
	cin >> n >> m;
	REP(i, 1, m) {
		ll x; ll y;
		cin >> x >> y;
		G[x].push_back(y);
		K[y].push_back(x);
		frm[y]++;
	}
	REP(i, 1, n) {
		if (frm[i] == 0 && color[i] == 0) {	
			color[i] = 1;
			f(i);
		}
	}
	ll ans = 0;
	for (auto cur : topsort) {
		dp[cur] = 0;
		for (auto bef : K[cur]) {
			dp[cur] = max(dp[cur], dp[bef] + 1);
			ans = max(ans, dp[cur]);
		}
	}
	cout << ans << endl;
	
}

Measured memory_bytes: 19064
n,m = map(int,input().split())
lis = [list(map(int,input().split()))[1:] for i in range(n)]
j = 0
l = 0
for i in range(1,31):
    for n in lis:
        if i in n:
            j += 1
        if n == lis[-1]:
            if j==len(lis):
                l += 1
            j = 0
print(l)

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

using lli = long long int;

using namespace std;


//10^5 = 100000

int main() {
    lli N, K;

    cin >> N >> K;

    double ans = 0.0;

    for (lli n = 1; n <= N; n++) {
        lli p = 0;

        lli tmp = n;
        while (tmp < K) {
            p++;
            tmp *= 2;
        }
        
        ans += static_cast<double>(std::pow(0.5, p)) / static_cast<double>(N);
    }

    std::cout << std::fixed << std::setprecision(20) << ans << endl;

    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int max(int a,int b){
    if(a>=b)return a;
    else return b;
}
int main(){
  int n,taros=0,hanakos=0;
  string taro,hanako;
  cin>>n;
  for(int i=0;i<n;i++){
      cin>>taro>>hanako;
      int length=max((int)taro.size(),(int)hanako.size());
      for(int j=0;j<length;j++){
        if(taro[j]>hanako[j]){
          taros+=3;
          break;
        }
        else if(taro[j]<hanako[j]){
          hanakos+=3;
          break;
        }
        else if(j==length-1){
            taros++;
            hanakos++;
        }
      }
  }
  cout<<taros<<" "<<hanakos<<endl;
  return 0;
}


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

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define BIT(X,i) ((X>>i)&1)
#define REP(i,a,b) for(int i = (a); i < (b); ++i)
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(rall(a))
#define ina(x,n) rep(x_i,n) cin>>x[x_i]
#define outa(x,n) rep(x_i,n) cerr<<x[x_i]<<" \n"[x_i==n-1]

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vll;

const int mod = 1e9+7;
const int inf = (1<<28);
const ll infl = (1LL<<60);

int main() {
  int N; cin >> N;
  vector<int> X(N); ina(X, N);
  int MIN_VAL = inf;
  for (int P = 1; P < 101; P++) {
    int sum = 0;
    for (int i = 0; i < N; i++) {
      sum += pow((X[i] - P), 2);
    }
    if (sum < MIN_VAL) {
      MIN_VAL = sum;
    }
  }
  cout << MIN_VAL << endl;
  return 0;
}


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

using namespace std;

const int MOD=1000000007;
int V;
vector<int> G[1000],rG[1000];
vector<int> vs;
bool used[1000];
int cmp[1000];

set<int> D[1000];

void add_edge(int from,int to){
  G[from].push_back(to);
  rG[to].push_back(from);
}

void dfs(int v){
  used[v]=true;
  for(int i=0;i<G[v].size();i++){
    if(!used[G[v][i]]){
      dfs(G[v][i]);
    }
  }
  vs.push_back(v);
}

void rdfs(int v,int k){
  used[v]=true;
  cmp[v]=k;
  for(int i=0;i<rG[v].size();i++){
    int n=rG[v][i];
    if(used[n]){
      if(cmp[n]!=k){
	D[k].insert(cmp[n]);
      }
    }else{
      rdfs(n,k);
    }
  }
}

long long sdfs(int v){
  used[v]=true;
  long long r=1;
  for(auto e:D[v]){
    r=(r*sdfs(e))%MOD;
  }
  return (r+1)%MOD;
}

int main(){
  int N,M;
  cin>>N>>M;
  V=N;
  while(M--){
    int s,d;
    cin>>s>>d;
    add_edge(s-1,d-1);
  }
  fill(begin(used),end(used),false);
  for(int v=0;v<V;v++){
    if(!used[v]){
      dfs(v);
    }
  }
  fill(begin(used),end(used),false);
  int k=0;
  for(int i=vs.size()-1;i>=0;i--){
    if(!used[vs[i]]){
      rdfs(vs[i],k++);
    }
  }
  fill(begin(used),end(used),false);
  long long a=1;
  for(int i=k-1;i>=0;i--){
    if(!used[i]){
      a=(a*sdfs(i))%MOD;
    }
  }
  cout<<a<<endl;
}

Measured memory_bytes: 1412
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int64_t MOD=1000000007;
const long long INF = 1LL<<60;

int main() {
  int64_t A,B,N;
  cin>>A>>B>>N;
  auto k=min(B-1,N);
  cout<<floor(A*k/B)-A*floor(k/B);
}


Measured memory_bytes: 3724
#pragma gcc optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, q; cin >> n >> q;
    vector<int> c(n), la(n, -1), ans(q), S(n << 1);
    for (int i = 0; i < n; ++i) cin >> c[i], --c[i];
    vector<vector<pair<int, int>>> Q(n);
    for (int i = 0; i < q; ++i) {
        int l, r; cin >> l >> r, --l, --r;
        Q[r].emplace_back(l, i);
    }
    auto upd = [&] (int i, int v) {
        for (S[i += n] = v; i >>= 1;) S[i] = S[i << 1] + S[i << 1 | 1];
    };
    auto query = [&] (int l, int r) {
        int res = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res += S[l++];
            if (r & 1) res += S[--r];
        }
        return res;
    };
    for (int i = 0; i < n; ++i) {
        if (la[c[i]] > -1) upd(la[c[i]], 0);
        la[c[i]] = i;
        upd(i, 1);
        for (auto& o : Q[i]) {
            auto& [l, id] = o;
            ans[id] = query(l, i + 1);
        }
    }
    for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
}

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

def solve(N: int, D: int, X: "List[int]", Y: "List[int]"):
    count = 0
    for i in range(N):
        if math.sqrt(X[i]**2 + Y[i]**2) <=D:
            count += 1
    print(count)
    return


# Generated by 1.1.7.1 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()
    N = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    X = [int()] * (N)  # type: "List[int]"
    Y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        X[i] = int(next(tokens))
        Y[i] = int(next(tokens))
    solve(N, D, X, Y)

if __name__ == '__main__':
    main()


Measured memory_bytes: 24600
#include <bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mii map <int, int>
#define mll map <ll, ll>
#define pii pair <int, int>
#define pll pair <ll, ll>
#define vi vector <int>
#define vd vector <double>
#define vll vector <ll>
#define fi first
#define se second
#define si set <int>
#define sll set <ll>
#define spii set <pii>
#define vs vector <string>
#define vpii vector <pair <int,int> >
#define vpll vector <pair <long long,long long> >
#define vvi vector <vector <int> >
#define vvpii vector <vector <pii > >
#define forn(i, n) for (int i = 0; i < (n); i++)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define for1(i, n) for (int i = 1; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()


using namespace std;
const ll INFLL = 1e18;
const int MAXN = 1e6+100;
const ll INF = 1e9;
const ll mod1=1e9+7;
const ll mod2=2e9+11;
int par[MAXN],ranks[MAXN],kol[MAXN];
vvi g;
void make_set(int s )
{
    ranks[s]=0;
    par[s]=s;
    kol[s]=1;
}
int find_set(int s)
{
    if (par[s]==s)
        return s;
    return par[s]=find_set(par[s]);
}
void union_sets(int a,int b)
{
    a=find_set(a);
    b=find_set(b);
    if (a!=b)
    {
        if (ranks[a]<ranks[b])
            swap(a,b);
        par[b]=a;
        kol[a]+=kol[b];
        if (ranks[a]==ranks[b])
            ranks[a]++;
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifdef LOCAL
    freopen("a.in","r",stdin);
#endif
    int n,m,k;
    cin>>n>>m>>k;
    g=vvi(n);
    rep(i,n)
    make_set(i);
    vector <int> kool(n,0);
    for (int i=0;i<m;i++)
    {
        int u,v;
        cin>>u>>v;
        u--,v--;
        union_sets(u,v);
        kool[u]++;
        kool[v]++;
    }
    for (int i=0;i<k;i++)
    {
        int u,v;
        cin>>u>>v;
        u--,v--;
        g[u].pb(v);
        g[v].pb(u);
    }
    for (int i=0;i<n;i++)
    {
        int ans=kol[find_set(i)];
        for (auto to:g[i])
        {
            if (find_set(i)==find_set(to))
                ans--;
        }
        ans-=kool[i]+1;
        cout<<ans<<" ";
    }




}

Measured memory_bytes: 14976
#include<cstdio>
typedef long long ll;
ll l,r;
ll calc(ll n){
	switch(n&3){
		case 0:return n;
		case 1:return 1;
		case 2:return n+1;
		case 3:return 0;
	}
}
int main(){
	scanf("%lld%lld",&l,&r);
	printf("%lld\n",calc(r)^calc(l-1));
	return 0;
}

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

using namespace std;

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define P 998244353
#define M 300010
int F[M], IF[M];

void gcd(int a,int b,int &x,int &y) {
  if(b==0){x=1,y=0;return;}
  gcd(b,a%b,y,x),y-=a/b*x;
}
int inv(int n) {
  int x,y;gcd(n,P,x,y);
  if(x<0)x+=P;return x;
}
int C(int n, int k) {
	if (k < 0 || n < k) return 0;
	return (ll)F[n]*IF[k]%P*IF[n-k]%P;
}
int gg(int u, int v, int m) {
	if (u == 0 && v == 0 && m == 0) return 1;
	return C(u+v+m-1, m-1);
}

#define N 100010
int n, m;
string a, b, c, d;
int f[N], lu[N], lv[N];

int ff() {
	memset(f, 0, sizeof f);
	memset(lu, 0, sizeof lu);
	memset(lv, 0, sizeof lv);
	int le = 0;
	int ri = 0;
	for (int i = 0; i < m; i ++) {
		if (c[i] == '1') le ++;
		if (d[i] == '1') ri ++;
	}
	
	int u = 0, v = 0;
	//cout << n << " " << m << " " << a.length() << " " << b.length() << " " << c.length() << " " << d.length() << endl;
	//cout << le << " " << ri << endl;
	
	for (int i = 0; i < n; i ++) {
		int w = 0;
		if (a[i] == '1') w++;
		if (b[i] == '1') w++;
		f[i] = (ll)gg(u, v, le)*w%P;
		lu[i] = u;
		lv[i] = v;
		if (a[i] == '1') u++;
		if (b[i] == '1') v++;
	}
	
	for (int i = 0; i < n-1; i ++) {
		if (a[i+1] == '1' && b[i+1] == '1')
			(f[i+1] += (ll)f[i]*2%P) %= P;
		else
			(f[i+1] += f[i]) %= P;
	}
	
	int S = 0;
	u = v = 0;
	for (int i = n-1; i >= 0; i--) {
		int w = 0;
		if (a[i] == '1') w++;
		if (b[i] == '1') w++;
		if (w >= 1) S = (S + (ll)f[i]*gg(u, v, ri)%P)%P;
		if (a[i] == '1') u++;
		if (b[i] == '1') v++;
	}
	
	return S;
}

int main() {
	F[0]=1;for(int i=1;i<M;i++)F[i]=(ll)F[i-1]*i%P;
	IF[M-1]=inv(F[M-1]);for(int i=M-1;i;i--)IF[i-1]=(ll)IF[i]*i%P;
	cin >> n >> m;
	cin >> a >> b >> c >> d;
	if (a == string(n, '0') && a == string(n, '0') && c == string(m, '0') && d == string(m, '0')) {
		puts ("1");
		return 0;
	}
	int S = 0;
	S += ff();
	swap(a, c);
	swap(b, d);
	swap(n, m);
	(S += ff()) %= P;
	cout << S << endl;
	return 0;
}

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

int main(){
    int k,a,b;
    cin>>k>>a>>b;
    
    int d=b/k*k;
    
    if(d>=a)
        cout<<"OK\n";
    else
        cout<<"NG\n";
        
    return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <math.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    int ai;
    int ap = -1;
    int ans = 0;
    int count = 0;
    for(int i=0; i<n; i++){
        cin >> ai;
        if(ai<=ap){
            count += 1;
            ap = ai;
        }else{
            ans = max(ans, count);
            count = 0;
            ap = ai;
        }
    }
    ans = max(ans, count);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int t, i,a[1005];
    scanf("%d", &t);
    for (i = 0; i < t;i++)
   {
        scanf("%d", &a[i]);
    }
    int m = 0;
    for (int j = 0; j < t; j++)
    {
        for (int k =j+ 1; k < t; k++)
            m += a[j] * a[k];
    }
    printf("%d\n", m);
    return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<algorithm>    
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<stack>
#include<queue>
#include<tuple>
#include<cassert>
#include<set>
#define int long long
#define mod(int)(1000000007)
using namespace std;
int test[213456];
int ok[213456];
int par[213456];//親
int depth[213456];//木の深さ
//n要素で初期化
void init(int n) {
	for (int i = 0; i < n; i++) {
		par[i] = i;
		depth[i] = 0;
	}
}
//木の根を求める
int find(int x) {
	if (par[x] == x) {
		return x;
	}
	else {
		return par[x] = find(par[x]);
	}
}
//xとyの属する集合を併合
void unite(int x, int y) {
	x = find(x); y = find(y);
	if (x == y) { return; }
	if (depth[x] < depth[y]) {
		par[x] = y;
	}
	else {
		par[y] = x;
		if (depth[x] == depth[y])depth[x]++;
	}
}
//xとyが同じ集合に属するか否か
bool same(int x, int y) {
	return find(x) == find(y);
}
signed main() {
	int n, m, a, b, z, ans = 0; cin >> n >> m;
	init(n);
	for (int h = 0; h < m; h++) {
		cin >> a >> b >> z;
		unite(a, b);
	}
	for (int h = 1; h <= n; h++) {
		if (ok[find(h)] == 1) { continue; }
		ok[find(h)] = 1; ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 5504
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>


using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int N, K;
    cin >> N >> K;

    int cnt = 0;
    while(N > 0) {
        N /= K;
        cnt++;
    }

    cout << cnt << endl;
    
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int n,p[100][11],f[100][10];
main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<10;j++)cin>>f[i][j];
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<=10;j++)cin>>p[i][j];
	}
	int ans;
	for(int i=1;i<1<<10;i++)
	{
		int now=0;
		for(int j=0;j<n;j++)
		{
			int cnt=0;
			for(int k=0;k<10;k++)f[j][k]&&(i&(1<<k))&&cnt++;
			now+=p[j][cnt];
		}
		if(i==1)ans=now;
		else ans=max(ans,now);
	}
	cout<<ans<<endl;
}


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

using namespace std;

const int MAXN=1e6+7;

typedef long long int lld;

int main(){

    lld N;
    scanf("%lld",&N);

    vector<lld> factorcnt;
    lld curval=N;
    for(lld i=2;i*i<=N;i++){
        if (curval%i) continue;
        factorcnt.push_back(0);
        while(curval%i==0){
            factorcnt.back()++;
            curval/=i;
        }
    }

    if (curval!=1) factorcnt.push_back(1);

    lld ans=0;
    for(auto cnt:factorcnt){
        lld c=0;
        for(lld i=1,sum=1;sum<=cnt;i++,sum+=i)
            c++;
        ans+=c;
    }

    printf("%lld\n",ans);
    return 0;
}

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

int main(){
    ll n;
    cin >> n;
    vector <ll> a(n);
    rep(i,n){
        cin >> a[i];
    }

    vector <ll> ans;
    
    ans.push_back(1001001001001001);
    ans.push_back(a[0]);
    
    ll r,l,m;

    rep(i,n){
        if(i!=0){
            r=ans.size();
            if(a[i]<=ans[r-1]){
                ans.push_back(a[i]);
                //sort(ans.begin(),ans.end());
            }
            else{
                r=ans.size()-1;
                l=0;
                while((r-l)>1){
                    m=(r+l)/2;
                    if(ans[m]<a[i]){
                        r=m;
                    }
                    else{
                        l=m;
                    }
                }
                ans[r]=a[i];   
            }
        }
    }

    cout << ans.size()-1 << endl;
    

    return 0;
}

Measured memory_bytes: 5024
/*
Though leaves are many , the root is one.
Through all the lying days of my youth
I swayed my leaves and flowers in the sun.
Now I may wither into the truth.
	  	  	- William Butler Yeats
*/
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
#include<bits/stdc++.h>
#pragma comment("-Wl,--stack=1024000000")
//#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
const double eps=1e-6;
const int mod=1000000007;
typedef long long ll;
#ifndef LOCAL
#define cerr if(0)cout
#define eprintf(...) 0
#else
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#endif
inline string getstr(string &s,int l,int r){string ret="";for(int i=l;i<=r;i++)ret.push_back(s[i]);return ret;}
int modpow(int x,int y,int md=mod){int ret=1;do{if(y&1)ret=(ll)ret*x%md;x=(ll)x*x%md;}while(y>>=1);return ret;}
inline int Rand(){return rand()*32768+rand();}
int get_id(char c){
	if(c>='a'&&c<='z')return c-'a';
	if(c>='A'&&c<='Z')return c-'A'+26;
	return c-'0'+52;
}
char rev(int x){
	if(x<26)return 'a'+x;
	if(x<52)return 'A'+x-26;
	return '0'+x-52;
}
int cnt[66],func[66],n;
int ask(string s){
	cout<<"? "<<s<<endl;
	fflush(stdout);int x;cin>>x;return x;
}
int Get(string ret,string s,int pos,char c){
	int tot=ret.size()+1+s.size()-pos;
	string ss=ret+c+getstr(s,pos,s.size()-1);
	tot=ss.size();
	return n-tot==ask(ss);
}
int id[66];
string merge_sort(int l,int r){
	if(l==r){
		string ret="";
		for(int i=0;i<cnt[id[l]];i++)ret.push_back(rev(id[l]));
		return ret;
	}
	int mid=(l+r)/2;
	string s1=merge_sort(l,mid);
	string s2=merge_sort(mid+1,r);
	int pos=0;
	string ret="";
	if(s1.size()<s2.size())swap(s1,s2);
	for(int i=0;i<s1.size();i++){
		while(pos<s2.size()&&Get(ret,s2,pos,s1[i])==0)
		ret.push_back(s2[pos]),pos++;
		ret.push_back(s1[i]);
	}
	while(pos<s2.size())ret.push_back(s2[pos++]);
	return ret;
}
int main(){
	for(int i=0;i<62;i++){
		string s="";s.push_back(rev(i));
		for(int i=0;i<7;i++)s=s+s;
		int got=ask(s);
		cnt[i]=128-got;
	}
	for(int i=0;i<62;i++)n+=cnt[i];
	for(int i=0;i<62;i++)id[i]=i;
	random_shuffle(id,id+62);
	string s=merge_sort(0,61);
	cout<<"! "<<s<<endl;
	fflush(stdout);
	return 0;
}


Measured memory_bytes: 3740
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
const int N = 505;

int x[N][N];
struct Node {
    int a, b, c, d;
    Node(int _a, int _b, int _c, int _d) : a(_a), b(_b), c(_c), d(_d) {}
};
vector<Node> vc;
int main() {
    int h, w;
    while (~scanf("%d %d", &h, &w)) {
        vc.clear();
        for (int i = 1; i <= h; ++i) {
            for (int j = 1; j <= w; ++j) {
                scanf("%d", &x[i][j]);
            }
        }
        for (int i = 1; i <= h; ++i) {
            int fr = 1;
            int to = w;
            int add = 1;
            if (i % 2 == 0) {
                swap(fr, to);
                add = -1;
            }
            for (int j = fr;; j += add) {
                if (x[i][j] % 2) {
                    int t1 = i;
                    int t2 = j;
                    if ((j == 1 && add == -1) || (j == w && add == 1)) {
                        t1++;
                    } else
                        t2 += add;
                    if (t1 <= h) {
                        vc.push_back(Node(i, j, t1, t2));
                        x[i][j]--;
                        x[t1][t2]++;
                    }
                }
                if (j == to) break;
            }
        }
        printf("%d\n", (int) vc.size());
        for (auto &v : vc) {
            printf("%d %d %d %d\n", v.a, v.b, v.c, v.d);
        }
    }
    return 0;
}

Measured memory_bytes: 5232
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;

ll n, table[100][100];

int main(){
	while (cin >> n&&n){
		REP(i, n){
			REP(j, n){
				cin >> table[i][j];
			}
		}
		REP(i, n){
			REP(j, n){
				table[i][n] += table[i][j];
			}
		}
		REP(i, n){
			REP(j, n + 1){
				table[n][j] += table[i][j];
			}
		}
		REP(i, n + 1){
			REP(j, n + 1){
				printf("%5d", table[i][j]);
				table[i][j] = 0;
			}
			cout << endl;
		}
	}
}

Measured memory_bytes: 1204
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
using namespace std;

int main() {

    char str[5];

    scanf("%s", str);

    if(str[0] == str[1] || str[1] == str[2] || str[2] == str[3]) printf("Bad");
    else printf("Good");


    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) (x).begin(),(x).end()
const long long MOD=1e9+7;
// const long long MOD=998244353;
const int INF=1e9;
const long long IINF=1e18;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
const char dir[4]={'D','R','U','L'};
#define LOCAL

template<typename T>
istream &operator>>(istream &is,vector<T> &v){
    for (T &x:v) is >> x;
    return is;
}
template<typename T>
ostream &operator<<(ostream &os,const vector<T> &v){
    for (int i=0;i<v.size();++i){
        os << v[i] << (i+1==v.size()?"": " ");
    }
    return os;
}
template<typename T,typename U>
ostream &operator<<(ostream &os,const pair<T,U> &p){
    cout << '(' << p.first << ',' << p.second << ')';
    return os;
}

void debug_out(){cerr << '\n';}
template<class Head,class... Tail>
void debug_out(Head&& head,Tail&&... tail){
    cerr << head;
    if (sizeof...(Tail)>0) cerr << ", ";
    debug_out(move(tail)...);
}
#ifdef LOCAL
#define debug(...) cerr << " ";\
cerr << #__VA_ARGS__ << " :[" << __LINE__ << ":" << __FUNCTION__ << "]" << '\n';\
cerr << " ";\
debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

template<class T1,class T2> inline bool chmin(T1 &a,T2 b){
    if (a>b){a=b; return true;} return false;
}
template<class T1,class T2> inline bool chmax(T1 &a,T2 b){
    if (a<b){a=b; return true;} return false;
}

template<typename T>
struct Dijkstra{
    const T inf=numeric_limits<T>::max();
    using P=pair<T,int>;
    int n;
    vector<vector<pair<int,T>>> G;
    vector<int> pre;
    vector<T> d;
    Dijkstra(int n):pre(n),n(n),G(n),d(n){}
    void add_edge(int u,int v,T w){
        G[u].emplace_back(v,w);
    }
    vector<T> build(int s){
        fill(d.begin(),d.end(),inf);
        d[s]=0;
        priority_queue<P,vector<P>,greater<P>> pq;
        pq.emplace(d[s],s);
        while(!pq.empty()){
            P p=pq.top(); pq.pop();
            int v=p.second;
            if (d[v]<p.first) continue;
            for (auto &e:G[v]){
                int u=e.first; T c=e.second;
                if (d[v]+c<d[u]){
                    d[u]=d[v]+c;
                    pre[u]=v;
                    pq.emplace(d[u],u);
                }
            }
        }
        return d;
    }
};


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M; cin >> N >> M;
    Dijkstra<int> D(N);
    for (int i=0;i<M;++i){
        int u,v; cin >> u >> v; --u,--v;
        D.add_edge(u,v,1); D.add_edge(v,u,1);
    }
    vector<int> a=D.build(0);
    vector<int> ans=D.pre;
    cout << "Yes" << '\n';
    for (int i=1;i<N;++i) cout << ans[i]+1 << '\n';
}

Measured memory_bytes: 13636
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<queue>
#define FAST ios::sync_with_stdio(false)
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = (int)1e9 + 9;
const int maxn = (int)1e4 + 5;
using namespace std;

stack<int> st;

int main()
{
	int n; scanf("%d", &n);
	int x; scanf("%d", &x); st.push(x);
	int ans = 0;
	for(int i = 2; i <= n; i++){
		scanf("%d", &x);
		if(x == st.top()) ans++, st.push(inf);
		else st.push(x);
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (ll i=0; i<(n); ++i)
#define rep1(i,n) for (ll i=1; i<=(n); ++i)
typedef long long ll;
bool debug=false;
string yes = "Yes";
string no = "No";
ll mod = 998244353;

int main(){
  ll h,w,k; cin >> h >> w >> k;
  vector<string> s(h);
  rep(i,h){
    cin >> s[i];
  }
  ll ans = w-1+h-1;
  for(ll d=0; d<(1<<h-1); d++){
    bool nextcut = false;
    // dの末尾からi番目のビットが1のとき、上からiのブロックのすぐ下に切れ込み
    vector<ll> cut;
    for(ll i=0; i<h-1; i++){
      if(d & (1<<i)){
        cut.push_back(i);
      }
    }
    cut.push_back(h-1);
    if(debug){
      for(auto e:cut){
        cout << e << " ";
      }
      cout << endl;
    }
    vector<ll> summ(cut.size(),0);
    ll cutsum=cut.size()-1;
    for(ll t=0; t<w; t++){
      bool colcut=false;
      vector<ll> col_white(cut.size(),0);
      ll previ = 0;
      for(ll c=0; c<cut.size(); c++){
        ll i = cut[c];
        for(ll u=previ; u<=i; u++){
          if(s[u][t]=='1') col_white[c]++;
        }
        previ = i+1;
        if(col_white[c]>k){nextcut=true;break;}
        if(d<=2&&debug){
          cout << summ[c] << ',' << col_white[c] << endl;
        }
        if(summ[c]+col_white[c]>k){
          colcut=true;
        }
      }
      if(nextcut) break;
      if(colcut){
        cutsum++;
        rep(i,cut.size()){
          summ[i]=col_white[i];
        }
      }else{
        rep(i,cut.size()){
          summ[i]+=col_white[i];
        }       
      }
    }
    if(nextcut) continue;
    ans = min(ans, cutsum);
  }
  cout << ans;
  return 0;
}

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

int main() {
    //ll N; cin >> N;
    //ll N,M; cin >> N >> M;
    //string S; cin >> S;
    ll H,W; cin >> H >> W;
    char m[H][W];
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cin >> m[i][j];
        }
    }
    int a[H][W]={};
    int b[H][W]={};
    int c[H][W]={};
    int d[H][W]={};
    for(int i=0;i<H;i++){
        a[i][0]=0;
        for(int j=1;j<W;j++){
            if(m[i][j-1]=='#')a[i][j]=0;
            else a[i][j]=a[i][j-1]+1;
        }
    }
    for(int i=0;i<H;i++){
        b[i][W-1]=0;
        for(int j=W-2;j>=0;j--){
            if(m[i][j+1]=='#')b[i][j]=0;
            else b[i][j]=b[i][j+1]+1;
        }
    }
    for(int i=0;i<W;i++){
        c[0][i]=0;
        for(int j=1;j<H;j++){
            if(m[j-1][i]=='#')c[j][i]=0;
            else c[j][i]=c[j-1][i]+1;
        }
    }
    for(int i=0;i<W;i++){
        d[H-1][i]=0;
        for(int j=H-2;j>=0;j--){
            if(m[j+1][i]=='#')d[j][i]=0;
            else d[j][i]=d[j+1][i]+1;
        }
    }
    int max=0;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(a[i][j]+b[i][j]+c[i][j]+d[i][j]>max && m[i][j]=='.'){
              max=a[i][j]+b[i][j]+c[i][j]+d[i][j];
            }
        }
    }
    cout << max+1 << endl;
}

/*



 */



Measured memory_bytes: 66688
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <queue>

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1000000;

using namespace std;

typedef int Weight;
struct Edge {
    int src, dst;
    Weight weight;
    Edge(int src, int dst, Weight weight) :
        src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
    return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
        e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void shortestPath(const Graph &g, int s,
        vector<Weight> &dist, vector<int> &prev) {
    int n = g.size();
    dist.assign(n, INF); dist[s] = 0;
    prev.assign(n, -1);
    priority_queue<Edge> Q; // "e < f" <=> "e.weight > f.weight"
    for (Q.push(Edge(-2, s, 0)); !Q.empty(); ) {
        Edge e = Q.top();
        Q.pop();
        if (prev[e.dst] != -1) continue;
        prev[e.dst] = e.src;
        FOR(f,g[e.dst]) {
            if (dist[f->dst] > e.weight+f->weight) {
                dist[f->dst] = e.weight+f->weight;
                Q.push(Edge(f->src, f->dst, e.weight+f->weight));
            }
        }
    }
}

int main(){
    int n;
    while(true){
        cin >> n;
        if(!n) break;
        Graph g(10);
        int num = 0;
        for(int i=0;i<n;++i) {
            int a,b,c;
            cin >> a >> b >> c;
            g[a].push_back(Edge(a, b, c));
            g[b].push_back(Edge(b, a, c));
            if(num < max(a,b)) num = max(a,b);
        }
        int min_index = 0;
        int min_elem = INF;
        for(int i=0;i<num;++i) {
            vector<int> dist;
            vector<int> prev;
            shortestPath(g,i,dist,prev);
            int sum = 0;
            for(int j=0;j<dist.size();++j){
                if(dist[j] < INF) sum += dist[j];
            }
            if(sum < min_elem) {
                min_elem = sum;
                min_index = i;
            }
        }
        cout << min_index << " " << min_elem << endl;
    }
}

Measured memory_bytes: 1196
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>

using namespace std;

int main()
{
    int n;

    cin >> n;

    string s[n];
    int cnt[n][26] = {};
    string ans;
    int min = 100010;

    for (int i = 0; i < n; i++) {
        cin >> s[i];
        for (int j = 0; j < s[i].size(); j++) {
            cnt[i][s[i][j]-'a']++;
        }
    }

    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < n; j++) {
            if (cnt[j][i] == 0) {
                min = 0;
                break;
            }
            else {
                if (min > cnt[j][i]) {
                    min = cnt[j][i];
                }
            }
        }
        for (int k = 0; k < min; k++) {
            ans += 'a' + i;
        }
        min = 100010;
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    
    int x;
    int y;
    
    for(int i=0;i<3000;i++){
        cin>>x>>y;
          if(x==0&&y==0){
            break;
        }
        else if(x>y){
            cout<<y<<" "<<x<<endl;
        }
        else {
            cout<<x<<" "<<y<<endl;
        }
      
    }
    
}



Measured memory_bytes: 3072
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, m, n) for(int i=(m); i<(n); ++i)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define Cout(x) cout << (x) << endl
#define Cout2(x, y) cout << (x) << " " << (y) << endl
#define dump(x) cout << #x << " = " << (x) << endl;
#define forauto(i, a) for(auto i : a)cout << i << " "; puts("");
typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
const int inf = 1e9;
const double pi = acos(-1.0);

int main() {
	int n;
	while (cin >> n && n) {
		VI m(n), a(n), b(n);
		rep(i, n)cin >> m[i] >> a[i] >> b[i];

		vector<PII> data;
		rep(i, n) {
			data.pb(mp(a[i], m[i]));
			data.pb(mp(b[i], -m[i]));
		}
		sort(all(data));

		int sum = 0; bool flag = false;
		rep(i, n * 2) {
			sum += data[i].second;
			if (sum > 150)flag = true;
		}
		puts(flag ? "NG" : "OK");
	}
}


Measured memory_bytes: 2940
#include<iostream>
using namespace std;
int selectionSort(int A[], int N){
  int i,j,sw=0,minj;
  for(i = 0; i < N;i++){
    minj = i;
    for(j = i; j < N;j++){
      if(A[j] < A[minj])minj = j;
    }
    swap(A[i],A[minj]);
    if(i != minj)sw++;
  }
  return sw;
}
int main(){
  int A[100],N,i,sw;

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

  sw = selectionSort(A,N);
  for(i = 0; i < N; i++){
    if(i)cout << " ";
    cout << A[i];
  }
  cout << endl;
  cout << sw << endl;
  return 0;
}




Measured memory_bytes: 3124
N, K = map(int, input().split())
MOD = 10**9 + 7

sq = 0
while (sq + 1) * (sq + 1) <= N:
    sq += 1

num = [0 for i in range(2 * sq + 1)]
for i in range(1, sq + 1):
    num[i] = 1
for i in range(1, sq + 1):
    lo = max(sq + 1, (N + i + 1) // (i + 1))
    hi = N // i
    num[2 * sq + 1 - i] = hi - lo + 1

dp = [[0 for j in range(2 * sq + 2)] for i in range(K + 1)]
dp[0][1] = 1
for i in range(K):
    for j in range(1, 2 * sq + 1):
        ways = dp[i][j] * num[j] % MOD
        dp[i + 1][1] += ways
        dp[i + 1][2 * sq + 2 - j] -= ways
    for j in range(1, 2 * sq + 1):
        dp[i + 1][j] += dp[i + 1][j - 1]

ans = 0
for j in range(1, 2 * sq + 1):
    ans += dp[K][j] * num[j]
print(ans % MOD)


Measured memory_bytes: 122908
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
const ll INF = 1LL<<61;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll jou(ll N, ll P){if(P==0) return 1;
  if(P%2==0){ll t = jou(N, P/2);return t*t % mod;
  }return (N * jou(N, P-1)) % mod;}  //jou(n,mod-2)で逆元
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる



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

  vector<ll> p(n);
  rep(i,n){
    cin>>p[i];
  }

  sort(all(p));

  int cnt=1;
  ll sum=p[0];
  repo(i,n){
    if(sum*2>=p[i]) cnt++;
    else cnt=1;
    sum+=p[i];
  }

  cout << cnt << endl;

}


Measured memory_bytes: 1024
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

template <class It> string join(It i1, It i2)
{
    ostringstream ss;
    for (auto it = i1; it != i2; ++it)
        ss << ((it == i1) ? "" : ", ") << (*it);
    return ss.str();
}

#ifdef DEBUG
#define Dump(x) cerr << #x << " = " << x << endl;
#define Dumps(x) cerr << #x << " : { " << join(x.begin(), x.end()) << " }" << endl;
#else
#define Dump(x)
#define Dumps(x)
#endif


using ull_t = unsigned long long;
using ll_t = long long;

struct robot_t { long x, d; };
ostream& operator << (ostream &os, const robot_t &x)
{
    os << "(" << x.x << ", " << x.d << ")";
    return os;
}

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

    vector<robot_t> R(N);
    for (int i = 0; i < N; ++i)
        cin >> R[i].x >> R[i].d;
    sort(R.begin(), R.end(), [](const robot_t &x, const robot_t &y) { return x.x < y.x; });
    Dumps(R);

    vector<int> C(N, 0);
    for (int i = N - 2; i >= 0; --i)
    {
        long y = R[i].x + R[i].d;
        for (int j = i + 1; j < N; ++j)
        {
            if (R[j].x >= y) break;
            C[i] = max(C[i], (j - i) + C[j]);
            if (y <= R[j].x + R[j].d)
                break;
        }
    }
    Dumps(C);

    ull_t K = 998244353;
    vector<ull_t> S(N + 1, 1); // i 以降の組み合わせ数
    for (int i = N - 1; i >= 0; --i)
    {
        S[i] = (S[i + 1] + S[i + 1 + C[i]]) % K;
    }
    cout << S[0] << endl;
}


Measured memory_bytes: 5760
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define mod 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)

int main(){
    int h,w;
    cin >> h >> w;
    vector<vector<int> > s(h,vector<int>(w)); 
    int a,b;
    cin >> a >> b;
    rep(i,h){
        if(i<b){
            rep(j,w){
                if(j<a){
                    s[i][j] = 0;
                }else{
                    s[i][j] = 1;
                }
            }
        }else{
            rep(j,w){
                if(j<a){
                    s[i][j] = 1;
                }else{
                    s[i][j] = 0;
                }
            }
        }
    }
    rep(i,h){
        rep(j,w){
            cout << s[i][j];
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 5248