akhauriyash/Code-Regression huggingface dataset:
/*ヽ｀、ヽ｀｀、ヽ｀ヽ｀、、ヽ ｀ヽ 、ヽ｀🌙｀ヽヽ｀ヽ、ヽ｀
ヽ｀、ヽ｀｀、ヽ 、｀｀、 ｀、ヽ｀ 、｀ ヽ｀ヽ、ヽ ｀、ヽ｀｀、
ヽ、｀｀、｀、ヽ｀｀、 、ヽヽ｀、｀、、ヽヽ、｀｀、 、 ヽ｀、 
ヽ｀｀、 ヽ｀ヽ｀、、ヽ ｀ヽ 、 🚶ヽ｀｀｀｀ヽヽヽ｀、、ヽ｀、、ヽ*/

// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,b,a) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
 
#define bug(x) cout<<#x<<"="<<x<<endl; 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ld pii=3.14159265359; 
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 1000001; //check the limits, dummy
 
int main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0);    
	int N;
	cin>>N;
	vi v(N);
	vi m(MX);
	F0R(x,N)
		cin>>v[x],m[v[x]]++;
	vi prms(MX);
	bool flag=true;
	FOR(x,2,MX)
	{
		int cnt=0;
		if(!prms[x])
			for(int y=x;y<MX;y+=x)
			{
				prms[y]=1;
				cnt+=m[y];
			}
		if(cnt>1)
		{
			flag=false;
			break;	
		}
	}
	if(flag)
	{
		cout<<"pairwise coprime";
		return 0;
	}
	int val=__gcd(v[0],v[1]);
	FOR(x,2,N)
	{
		val=__gcd(val,v[x]);
	}
	if(val==1)
	{
		cout<<"setwise coprime";
		return 0;
	}
	cout<<"not coprime";
	return 0;
}
 
// read the question correctly (ll vs int)
// template by bqi343

Measured memory_bytes: 15040
#include<iostream>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int x;
        cin>>x;
        if(x%2==0){
            if(!(x%3==0||x%5==0)){
                cout<<"DENIED"<<endl;
                return 0;
            }
        }
    }
    cout<<"APPROVED"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<bitset>
#include<climits>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<string>
#include<time.h>
#include<tuple>
#include<utility>
#include<vector>

using namespace std;
const long mod = 1000000007;
long gcd(long x, long y) { if (x > y) { return gcd(y, x); } long r; while (y != 0) { r = x % y; x = y; y = r; }return x; }
long lcm(long x, long y) { return(x / gcd(x, y)) * y; }

int main() {

	long res = 0;
	long N, M; cin >> N >> M;

	vector<pair<long, long>> T(N);

	long a, b; for (int i = 0; i < N; i++) { cin >> a >> b; T[i] = make_pair(a, b); }

	multiset<long> cando; //走査時に行えるタスクの集合
	vector<vector<long>> soeji(100009); //firstがiであるTのsecondの集合

	for (int i = 0; i < N; i++) soeji[T[i].first].push_back(T[i].second);

	//日付を逆から走査していく

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

		for (long e : soeji[i]) cando.insert(e); //その日までに有効な仕事をリストにぶちこむ

		if (!cando.empty()) { res += *cando.rbegin(); cando.erase(--cando.end()); }//最適な仕事をしてそれを削除
        
	}

	cout << res << endl;

}

Measured memory_bytes: 9856
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

const int MOD = 1e9 + 7;
const int iINF = 1000000000;
const long long int llINF = 1000000000000000000;

using namespace std;
using ll = long long int;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;

typedef pair<ll, ll> pll;
bool paircomp(const pll &a, const pll &b) {
  if (a.first == b.first)
    return a.second < b.second;
  return a.first < b.first;
}

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define RREP(i, n) for (ll i = (n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define AUTO(i, m) for (auto &i : m)
#define ALL(a) (a).begin(), (a).end()
#define MAX(vec) *std::max_element(vec.begin(), vec.end())
#define MIN(vec) *std::min_element(vec.begin(), vec.end())
#define ARGMAX(vec)                                                            \
  std::distance(vec.begin(), std::max_element(vec.begin(), vec.end()))
#define ARGMIN(vec)                                                            \
  std::distance(vec.begin(), std::min_element(vec.begin(), vec.end()))
#define REV(T) greater<T>()
#define PQ(T) priority_queue<T, vector<T>, greater<T>>
#define VVL(a, b, c) vector<vector<ll>>(a, vector<ll>(b, c))
#define VVVL(a, b, c, d)                                                       \
  vector<vector<vector<ll>>>(a, vector<vector<ll>>(b, vector<ll>(c, d)))
#define SP(a) setprecision(a)

ll POW(ll n, ll m) {
  if (m == 0) {
    return 1;
  } else if (m % 2 == 0) {
    ll tmp = POW(n, m / 2);
    return (tmp * tmp);
  } else {
    return (n * POW(n, m - 1));
  }
}

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  string S;
  ll g = 0;
  ll p = 0;
  ll ans = 0;
  cin >> S;
  REP(i, S.size()) {
    if (p < g) {
      if (S[i] == 'g')
        ans++;
      p++;
    } else {
      if (S[i] == 'p')
        ans--;
      g++;
    }
  }
  cout << ans << endl;

  return 0;
}


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

ll bit_size(ll a){
  for(int i=0;i<63;i++){
    if(1<<i >= a){return i;}
  }
  return 63;
}

//1-index
template<typename T>
class BIT{
private:
  vector<T> bit;
  ll size;

public:
  BIT(vector<T> t){
    size=bit_size(t.size());
    bit.resize((1<<size)+1,0);
    for(int i=1;i<=t.size();i++){
      change(i,t[i-1]);
    }
  }

  BIT(ll s){
    size=bit_size(s);
    bit.resize((1<<size)+1);
  }

  BIT(ll s,T a){
    size=bit_size(s);
    bit.resize((1<<size)+1,a);
  }

  void add(ll where,T a){
    while(where<bit.size()){
      bit[where]+=a;
      where+=where&-where;
    }
  }

  //[1,r]
  T sum(ll r){
    T ret=0;
    while(r>0){
      ret+=bit[r];
      r=r&(r-1);
    }
    return ret;
  }

  //[l,r]
  T sum(ll l,ll r){
    T ret=sum(r);
    ret-=sum(l-1);
    return ret;
  }
};




int main(){
  ll n;
  cin>>n;
  vector<ll> a;
  for(int i=0;i<n;i++){
    ll b;
    cin>>b; b++;
    a.push_back(b);
  }
  ll ans=0;
  BIT<ll> b(120,0);
  for(int i=0;i<n;i++){
    b.add(120-a[i],1);
    ans+=b.sum(120-a[i]-1);
  }
  sort(a.begin(),a.end());
  for(int i=0;i<n;i++){
    a[i]--;
    cout<<a[i];
    if(i!=n-1){cout<<" ";}
  }
  cout<<endl<<ans<<endl;







  return 0;
}



Measured memory_bytes: 3160
package main

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

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

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func scanInt() int {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return a
}

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ { res[i] = scanInt() }
	return res
}

func scanText() string {
	sc.Scan()
	return sc.Text()
}

func printInts(a ...int) {
	for i, e := range a {
		fmt.Fprint(wr, e)
		if i != len(a)-1 { fmt.Fprint(wr, " ") }
	}
	fmt.Fprintln(wr)
	wr.Flush()
}

//=====main=====

func main() {
	sc.Split(bufio.ScanWords)

	n := scanInt()

	g := make([][]edge, n)

	for i := 0; i < n-1; i++ {
		a,b := scanInt()-1, scanInt()-1
		g[a] = append(g[a], edge{b,i})
		g[b] = append(g[b], edge{a,i})
	}

	k := 0
	for _, v := range g {
		k = max(k, len(v))
	}

	ans := make([]int, n)

	q := make([]do, 0)
	q = append(q, do{0,0})
	done := make([]bool, n)

	for len(q) > 0 {
		now := q[0].next
		used := q[0].used
		done[now] = true
		c := 1
		for _, v := range g[now] {
			if done[v.to] {
				continue
			}
			
			if c == used {
				c++
			}
			ans[v.num] = c
			q = append(q, do{v.to,c})
			c++
		}
		q = q[1:]
	}

	defer wr.Flush()
	fmt.Fprintln(wr, k)

	for i := 0; i < n-1; i++ {
		fmt.Fprintln(wr, ans[i])
	}

}

type edge struct {
	to int
	num int
}

type do struct {
	next int
	used int
}

func min(a ...int) int {
	res := a[0]
	for i := 1; i < len(a); i++ {
		if res > a[i] { res = a[i] }
	}
	return res
}

func max(a ...int) int {
	res := a[0]
	for i := 1; i < len(a); i++ {
		if res < a[i] { res = a[i] }
	}
	return res
}



Measured memory_bytes: 15232
#include<iostream>
#include<stdlib.h>
using namespace std;

int N;
int** A;
int max_c = 0;

void search_tree(int i, int j, int val){
  if(i<1) search_tree(i+1,j,val+A[i][j]);
  if(j<(N-1)) search_tree(i,j+1,val+A[i][j]);
  else if(i==1 && j==(N-1) && (val+A[i][j])>max_c) max_c = val+A[i][j];
}

int main(){
  cin >> N;

  A = (int**)malloc(sizeof(int*)*2);
  for(int i=0;i<2;i++){
    A[i] = (int*)malloc(sizeof(int)*N);
  }

  for(int i=0;i<2;i++){
    for(int j=0;j<N;j++){
      cin >> A[i][j];
    }
  }

  search_tree(0,0,0);
  cout << max_c << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
inline long long solve(long long n,long long m){
   long long ans=(1LL<<62);
   for(long long i=1;i<=m;i++){
      long long a=1LL*n*i;
      long long b;
      long long c;
      if(n%2==1)
        b=1LL*(m-i)*((n+1)/2);
      else
        b=1LL*(m-i)*n/2;
      c=1LL*n*m-a-b;
      ans=std::min(ans,std::max(std::abs(a-b),std::max(std::abs(b-c),std::abs(a-c))));
      if((m-i)%2==1)
        b=1LL*((m-i+1)/2)*n;
      else
        b=1LL*((m-i)/2)*n;
      c=1LL*n*m-a-b;
      ans=std::min(ans,std::max(std::abs(a-b),std::max(std::abs(b-c),std::abs(a-c))));
   }
   return ans;
}
int main(){
    FILE*fi,*fout;
    int n,m;
    //fi=fopen("A.in" ,"r");
    //fout=fopen("A.out" ,"w");
    fi=stdin;
    fout=stdout;
    fscanf(fi,"%d%d" ,&n,&m);
    if(n%3==0||m%3==0)
      fprintf(fout,"0\n");
    else
      fprintf(fout,"%lld\n" ,std::min(solve(n,m),solve(m,n)));
    //fclose(fi);
    //fclose(fout);
}


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

int main() {
  int n;
  cin >> n;
  int a[10000] = {};
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }

  sort(a,a+n);
  long sum = 0;
  for(int i = 0; i < n; i++){
    sum += a[i];
  }

  cout << a[0] << " " << a[n-1] << " " << sum << endl;

}



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

typedef long long ll;
const ll INF = 1e18L;

int main(int argc, char const *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m; cin >> n >> m;
    int w[n];
    int v[n];
    int s = 0;
    for (int i = 0; i < n; i++){
        cin >> w[i] >> v[i];
        s+=v[i];
    }
    ll dp[s+1];
    dp[0] = 0;
    for (int i = 1; i < s+1; i++){
        dp[i] = INF;
    }
    for (int i = 0; i < n; i++){
        for (int j = s-v[i]; j >= 0; j--){
            dp[j+v[i]] = min(dp[j+v[i]],dp[j]+w[i]);
        }
    }
    int res = 0;
    for (int i = s; i >= 0 && res == 0; i--){
        if (dp[i] <= m) res = i;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 1024
import sys

n=int(input())
xyh=[[] for i in range(n)]
for i in range(n):
    x,y,h=map(int,input().split())
    xyh[i].append(x)
    xyh[i].append(y)
    xyh[i].append(h)
for i in range(101):
    for j in range(101):
        f=0
        dis=[[i] for i in range(205)]
        for q in range(n):
            x=xyh[q][0]
            y=xyh[q][1]
            h=xyh[q][2]
            d=abs(x-i)+abs(y-j)
            
            if len(dis[d])==1:
                dis[d].append(h)
            elif len(dis[d])!=1 and dis[d][1]!=h:
                f=1
        
        dis=[dis[e] for e in range(205) if len(dis[e])!=1]
        m=len(dis)
        if m==1 and f==0:
            print(i,j,dis[0][0]+dis[0][1])
            sys.exit()
            
        else:
            if all(dis[e][0]+dis[e][1]==dis[e+1][0]+dis[e+1][1] for e in range(m-1) if dis[e+1][1]!=0) and f==0:
                print(i,j,dis[0][0]+dis[0][1])
                sys.exit()



Measured memory_bytes: 75528
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <math.h>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> P;
#define rep(i,n) for (int i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
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 int INF = 1<<30;
const ll LINF = 1LL<<58;
const int mod = 1000000007;

int main(){
	string s;
	cin >> s;
	s = "###" + s;
	int n = s.size();
	ll ans = 0, bc = 0;
	for (int i = n-1; i > 1; i--) {
		if(s[i] == 'A') ans += bc;
		else if(s[i] == 'C' && s[i-1] == 'B') {
			bc++;
			i--;
		}
		else bc = 0;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 772
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
  unsigned int N;
  std::cin >> N;

  std::vector<unsigned int> A_array;
  for (unsigned int i = 0; i < N; ++i) {
    unsigned int a;
    std::cin >> a;
    A_array.push_back(a);
  }

  std::vector<unsigned int> A_array_sorted = A_array;

  std::sort(A_array_sorted.begin(), A_array_sorted.end(), std::greater<unsigned int>());

  const unsigned int first = A_array_sorted.at(0);
  const unsigned int second = A_array_sorted.at(1);

  for (unsigned int i = 0; i < N; ++i) {
    if (A_array.at(i) == first) {
      std::cout << second << std::endl;
    } else {
      std::cout << first << std::endl;
    }
  }

  return 0;
}


Measured memory_bytes: 3316
#coding:utf-8

import sys

t,x,y = 0,0,0

N = int(input())


for _ in range(N):
    t1,x1,y1=[int(__) for __ in input().split()]
    delta_t = abs(t1-t)
    delta_x = abs(x1-x)
    delta_y = abs(y1-y)

    if delta_x + delta_y > delta_t:
        print("No")
        sys.exit()

    if (delta_x + delta_y - delta_t) % 2 != 0:
        print("No")
        sys.exit()

    t,x,y = t1,x1,y1

print("Yes")


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

int main(){
    int K, X, Y;
    cin >> K >> X >> Y;

    // 1手でいける場合を先に処理
    if(abs(X) + abs(Y) == K){
        cout << "1\n" << X << " " << Y << endl;
        return 0;
    }

    // X >= Y >= 0に変換
    int xsign = 1, ysign = 1;
    bool sw = false;
    if(X < 0){
        X *= -1;
        xsign = -1;
    }
    if(Y < 0){
        Y *= -1;
        ysign = -1;
    }
    if(X < Y){
        swap(X, Y);
        sw = true;
    }

    // nがステップ数。1手で行けないので最小でも2
    int D = X+Y;
    int n = max(2, (D+K-1)/K);

    // 無駄分が奇数の場合、Kが奇数なら1ステップ増やして偶数に。Kが偶数なら無理
    if((n*K-D)%2){
        if(K%2){
            n++;
        }else{
            cout << -1 << endl;
            return 0;
        }
    }

    vector<pair<int, int>> ans;
    
    // 構築。n=3のときだけ特別
    int R = (n*K-D)/2;
    if(n == 3){
            int b = R/2;
            int a = R-b;
            for(int i=1; i<=n; i++){
            int l = i*K;
            if(l <= a){
                ans.emplace_back(-l, 0);
            }else if(l <= a+Y+b){
                l -= a;
                ans.emplace_back(-a, l);
            }else if(l <= a+Y+b+a+X){
                l -= a+Y+b;
                ans.emplace_back(l-a, b+Y);
            }else{
                l -= a+Y+b+a+X;
                ans.emplace_back(X, Y + (b-l));
            }
        }
    }else{
        int a = R;
        for(int i=1; i<=n; i++){
            int l = i*K;
            if(l <= Y+a){
                ans.emplace_back(0, l);
            }else if(l <= Y+a+X){
                l -= Y+a;
                ans.emplace_back(l, Y+a);
            }else{
                l -= Y+a+X;
                ans.emplace_back(X, Y + (a - l));
            }
        }
    }

    // 座標変換を戻して出力
    if(sw) for(int i=0; i<n; i++) swap(ans[i].first, ans[i].second);
    cout << n << endl;
    for(auto& p : ans){
        printf("%d %d\n", p.first*xsign, p.second*ysign);
    }
    
    return 0;
}


Measured memory_bytes: 3952
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL A,B,C,D;
map<LL,LL>mp;
LL solve(LL N)
{
if (N == 0) return 0;
    if (N == 1) return D;
    if (mp.count(N)) return mp[N];
    LL l2 = (N/2)*2;
    LL r2 = ((N+1)/2)*2;
    LL l3 = (N/3)*3;
    LL r3 = ((N+2)/3)*3;
    LL l5 = (N/5)*5;
    LL r5 = ((N+4)/5)*5;
 
    LL res = 1e18;
    if (N < res/D) res = N*D;
    res = min(res, llabs(l2-N)*D + A + solve(l2/2));
    res = min(res, llabs(r2-N)*D + A + solve(r2/2));
 
    res = min(res, llabs(l3-N)*D + B + solve(l3/3));
    res = min(res, llabs(r3-N)*D + B + solve(r3/3));
 
    res = min(res, llabs(l5-N)*D + C + solve(l5/5));
    res = min(res, llabs(r5-N)*D + C + solve(r5/5));
 
    mp[N] = res;
 
    return res;
}
int main()
{
ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	cin>>t;
while(t--)
{
 mp.clear();
        LL N;
        cin >> N;
        cin >> A >> B >> C >> D;
        cout << solve(N) << "\n";
}
return 0;
}


Measured memory_bytes: 4400
import Control.Monad
import Data.List
import Data.Maybe
import Data.Ord

--         )   (
data P = P Int Int deriving (Show)

instance Semigroup P where
  (P l1 r1) <> (P l2 r2)
    | r1 < l2 = P (l1 + l2 - r1) r2
    | otherwise = P l1 (r1 + r2 - l2)

instance Monoid P where
  mempty = P 0 0

parseC :: Char -> P
parseC '(' = P 0 1
parseC ')' = P 1 0

parse :: String -> P
parse = mconcat . map parseC

calc :: [P] -> Maybe ()
calc parens = do
  res <- foldM f mempty $ sortOn (\(P l _) -> l) rise
  P l r <- foldM f res . reverse $ sortOn (\(P _ r) -> r) fall
  if l == 0 && r == 0
    then Just ()
    else Nothing
  where
    (rise, fall) = partition (\(P l r) -> l < r) parens
    good (P a _) = a >= 0
    f accum x = if good accum then Just $ accum <> x else Nothing

main :: IO ()
main = do
  n <- read <$> getLine
  res <- fmap calc . sequenceA $ replicate n (fmap parse getLine)
  putStrLn $ if isJust res then "Yes" else "No"

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

using namespace std;

#define MAXN 310
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define eps (1e-6)
typedef long long LL;

int n, m, cnt[MAXN];
bool vis[MAXN];
queue<int> q[MAXN];

int main()
{
    int i, j, a, ans = INF;
    scanf("%d %d", &n, &m);
    for(i = 1; i <= n; ++i)
        for(j = 1; j <= m; ++j){
            scanf("%d", &a);
            q[i].push(a);
            if(j == 1) ++cnt[a];
        }

    for(i = 1; i <= m; ++i){
        for(j = a = 1; j <= m; ++j)
            if(cnt[j] > cnt[a]) a = j;
        ans = min(ans, cnt[a]);
        vis[a] = true;
        if(i == m) break;
        for(j = 1; j <= n; ++j){
            while(vis[q[j].front()]){
                --cnt[q[j].front()]; q[j].pop();
                ++cnt[q[j].front()];
            }
        }
    }
    printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 768
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::f64::consts::*;

#[allow(unused)]
const INF: usize = std::usize::MAX / 4;
#[allow(unused)]
const M: usize = 1000000007;

fn f(n: usize) -> usize {
    let mut d = vec![];
    let mut m = n;
    while m > 0 {
        d.push(m % 10);
        m /= 10;
    }

    let mut s = vec![];
    s.push((n, d.iter().sum::<usize>()));

    for i in 1..d.len() {
        d[i - 1] = 9;
        s.push((
            d.iter()
                .enumerate()
                .map(|(i, di)| 10usize.pow(i as u32) * di)
                .sum::<usize>(),
            d.iter().sum::<usize>(),
        ));
    }
    for i in 0..d.len() {
        if (0..d.len()).all(|j| s[i].0 * s[j].1 <= s[j].0 * s[i].1) {
            return s[i].0;
        }
    }
    return INF;
}

fn main() {
    input! {
        k: usize,
    }
    let mut n = 1;
    for _ in 0..k {
        println!("{}", n);
        n = f(n + 1);
    }
}


Measured memory_bytes: 2188
#include<iostream>
#include<iomanip>
#include<string>
#include<array>
#include<cmath>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;


int main() {
	int a, b;
	cin >> a >> b;
	if (b%a==0) {
		cout << a + b;
	}
	else {
		cout << b - a;
	}
}


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

int main() {
    char c;

    cin >> c;

    if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
        cout << "vowel";
    else
        cout << "consonant" << endl;
}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!
# 素数判定
# ふるいおとし

import sys
import math

loop = int(sys.stdin.readline())

# loop = 6

# arr = """2
# 3
# 4
# 5
# 6
# 7""".split('\n')

def is_prime(x):
    # エラトステネスのふるい
    if (x%2==0 and x!=2) or (x%3==0 and x!=3) or (x%5==0 and x!=5):
        return False
    for d in range(2, math.floor(math.sqrt(x))+1):
        if x%d==0:
            return False
    return True

count = 0
for _ in range(loop):
    x = sys.stdin.readline()
    # if is_prime(int(arr[_])):
    if is_prime(int(x)):
        count  += 1
print(count)



Measured memory_bytes: 5688
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint


def main():
    num = int(stdin.readline())

    edges = []
    for _ in xrange(num):
        ns = [int(s) for s in stdin.readline().split()]
        for i in xrange(ns[1]):
            edges.append((ns[0], ns[2*i+2], ns[2*i+3]))

    dis = [maxint] * num
    dis[0] = 0

    while 1:
        update = False
        for from_, to, cost in edges:
            if dis[from_] < maxint and dis[to] > cost + dis[from_]:
                dis[to] = cost + dis[from_]
                update = True

        if not update:
            break

    for i, d in enumerate(dis):
        print(i, d)


main()

Measured memory_bytes: 70180
#include<bits/stdc++.h>
using namespace std;
#define INF 1000000000
int main(){
  int n,m;
  int c[20];
  int dp[50001];
  cin>>n>>m;
  for(int i=0;i<m;i++){
    cin>>c[i];
  }
  for(int i=0;i<50001;i++){
    dp[i]=INF;
  }
  for(int i=0;i<m;i++){
    dp[c[i]]=1;
  }
  for(int i=1;i<50001;i++){
    for(int j=0;j<m;j++){
      if(i-c[j]>0) dp[i]=min(dp[i],dp[i-c[j]]+1);
    }
  }
  cout<<dp[n]<<endl;
  return 0;
}



Measured memory_bytes: 3320
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
int read(){
    char x;
    while((x = getchar()) > '9' || x < '0') ;
    int u = x - '0';
    while((x = getchar()) <= '9' && x >= '0') u = (u << 3) + (u << 1) + x - '0';
    return u;
}
int buf[105];  
inline void write(int i){  
    int p = 0;  
    if(i == 0) p++;  
    else while(i) {  
        buf[p++] = i % 10;  
        i /= 10;  
    }  
    for(int j = p-1; j >= 0; j--) putchar('0' + buf[j]);  
} 
int a[500005],Ans[500005],cnt[500005],ans=0,n,m,bl;
struct node{
	int l,r,id;
}q[500005]; 

inline bool cmp(const node a,const node b){
	return (a.l/bl)^(b.l/bl)?a.l<b.l:(((a.l/bl)&1)?a.r<b.r:a.r>b.r);
}

inline void del(int x){
	--cnt[a[x]];
	if(!cnt[a[x]])--ans;
}
inline void add(int x){
	if(!cnt[a[x]])++ans;
	++cnt[a[x]];
}

int main() {
	int n,m;
	n=read();m=read();
	bl=n/sqrt(m*2/3);
	for(int i=1;i<=n;++i)a[i]=read();
	
	for(int i=1;i<=m;++i){
		q[i].l=read(),q[i].r=read();
		q[i].id=i;
	}
	sort(q+1,q+1+m,cmp);
	
	int l=q[1].l,r=q[1].l-1;
	for(int i=1;i<=m;++i){
		int stdl=q[i].l,stdr=q[i].r;
		
		while(l<stdl)del(l++);
		
		while(l>stdl)add(--l);
		
		while(r<stdr)add(++r);
		
		while(r>stdr)del(r--);
		
		Ans[q[i].id]=ans;
	}
	
	for(int i=1;i<=m;++i)write(Ans[i]),printf("\n");
	return 0;
}

Measured memory_bytes: 15496
#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll; 
    int c[100000];
    ll haha(int a[], int n, int k){
        if(n <= k){
            int b[n];
            for(int i=0; i<n; i++){
                if(c[i]== -1){
                    c[i] = haha(a, i, k);
                    b[i] = abs(a[n] - a[i]) + c[i];
                }
                else{
                    b[i] = abs(a[n] - a[i]) + c[i];
                }
            }
            sort (b, b+n);
            return b[0];
        }
        int b[k];
        for(int i =1; i<=k; i++){
            if(c[n-i]==-1){
                c[n-i] = haha(a,n-i, k);
                b[i-1] = abs(a[n] - a[n-i]) + c[n-i];
            }else{
                b[i-1] = abs(a[n] - a[n-i]) + c[n-i];
            }
        }
        sort(b, b+k);
        return b[0];
    } 
    int main (){
        for(int i=0; i< 100000; i++){
            c[i] = -1;
        }
        c[0] = 0;

        int n,k; cin >> n >> k;
        int a[n];
        for(int i=0; i<n; i++){
            cin >> a[i];
        }
        cout << haha(a, n-1, k);
    }

Measured memory_bytes: 54144
n,c=map(int,input().split())
Ds = [list(map(int,input().split())) for x in range(c)]
colors = [list(map(int,input().split())) for x in range(n)]
count0,count1,count2 = [0]*c,[0]*c,[0]*c
for i in range(n):
  for j in range(n):
    if (i+j)%3 == 0:
      count0[colors[i][j]-1] += 1
    elif (i+j)%3 == 1:
      count1[colors[i][j]-1] += 1
    else:
      count2[colors[i][j]-1] += 1
total = pow(10,12)
for a in range(c):
  for b in range(c):
    for d in range(c):
      if a == b or b == d or d == a:
        continue
      tmp = 0
      for x in range(c):
        tmp += count0[x]*Ds[x][a]+count1[x]*Ds[x][b]+count2[x]*Ds[x][d]
      total = min(total,tmp)
print(total)

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

typedef long long ll;
#define MOD = 1000000007;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define ALL(a) begin(a),end(a)
#define COUNTOF(a) (sizeof(a)/sizeof(a[0]))
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
template<class T> void cout_v(const vector<T>& c)
{ for (int i = 0; i < c.size(); i++) cout << c[i] << endl; }
template<class T> void cout_h(const vector<T>& c)
{ for (int i = 0; i < c.size(); i++) cout << c[i] << (i==c.size()-1?"\n":" "); }
template<class T> inline bool chmin(T& a, T b) {return a>b?a=b,true:false;}
template<class T> inline bool chmax(T& a, T b) {return a<b?a=b,true:false;}
template<class T> inline bool is_overlap(const T& as, const T& ae, const T& bs, const T& be)
{ return bs <=ae && as <= be; }
#define SP << " " <<
#define FMT(a) #a<<":"<<a 
#define FMT2(a,b) #a<<":"<<a<<", "<<#b<<":"<<b 
#define FMT3(a,b,c) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c 
#define FMT4(a,b,c,d) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c<<", "<<#d<<":"<<d 
#define ANS(a) cout<<a<<endl
void yes(bool f){cout<<(f?"yes":"no")<<endl;}
void Yes(bool f){cout<<(f?"Yes":"No")<<endl;}
void YES(bool f){cout<<(f?"YES":"NO")<<endl;}

template<class T> void sort3d(T& a,T& b,T& c) {if (a<b) swap(a,b); if (b<c) swap(b,c); if (a<b) swap(a,b);}
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    //cout<<std::fixed<<std::setprecision(10);

    int A, B, C; cin >>A>>B>>C;

    int ans = 0;    

    sort3d(A,B,C);
    
    ans += A - B;
    ans += (B - C + 1) / 2 + (B - C) % 2;
    
    cout << ans << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
void solve(){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if(a <= c && b <= d && c <= b){
        cout << b - c << endl;
    }
    else if(a <= c && d <= b){
        cout << d - c << endl;
    }
    else if(c <= a && b <= d){
        cout << b - a << endl;
    }
    else if(c <= a && d <= b && a <= d){
        cout << d - a << endl;
    }
    else 
    cout << 0 << endl;
}
int main(){
    solve();
    return 0;
}


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

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

template <typename T>
struct RUQ //calculateはminimum
{
    int n;
    const T ex = 0; //dat 初期値(minなので)
    const T em = 0; //lazy 初期値(minなので)
    vector<T> dat, lazy; //tree本体
    RUQ(vector<T> v){
        int x = 1;
        int i;
        n = v.size();
        while(x < n) x <<= 1;
        n = x; 
        dat.resize(2*n-1, ex);
        lazy.resize(2*n-1, em);
        for(i = 0;i < v.size();++i){
            dat.at(i + n - 1) = v.at(i);
        }
        for(i = n-2;i >= 0;--i){
            dat.at(i) = calculate(dat.at(2*i+1), dat.at(2*i+2));
        }
    }
    
    T calculate(T a, T b){
        return max(a, b); //minで使う
    }
    
    void eval(int now){
        if(lazy.at(now) == em) return;
        if(now < n - 1){ //最小値なのでそのまま代入
            lazy.at(2*now + 1) = max(lazy.at(2*now + 1), lazy.at(now));
            lazy.at(2*now + 2) = max(lazy.at(2*now + 1), lazy.at(now));
        }
        dat.at(now) = max(dat.at(now), lazy.at(now));
        lazy.at(now) = em;
    }
    
    void update(int a, int b, T x, int now, int l, int r){
        eval(now);
        if(a <= l && r<= b){
            lazy.at(now) = max(lazy.at(now) ,x); //上から書き換える。最小値なので代入する
            eval(now);
        }else if(a < r && l < b){
            update(a, b, x, 2*now + 1, l, (l + r)/2);
            update(a, b, x, 2*now + 2, (l + r)/2, r);
            dat.at(now) = calculate(dat.at(2*now + 1), dat.at(2*now + 2));
        }
    }
    void update(int a, int b, T x){update(a, b, x, 0, 0, n);}
    
    T query(int a, int b){return query_sub(a, b, 0, 0, n);}
    T query_sub(int a, int b, int now, int l, int r){
        eval(now);
        if(r <= a || b <= l) return ex;
        else if(a <= l && r <= b) return dat.at(now);
        else{
            T vl = query_sub(a, b, 2*now + 1, l, (l + r)/2);
            T vr = query_sub(a, b, 2*now + 2, (l + r)/2, r);
            return calculate(vl, vr);
        }
    }
    
    inline T operator[](int a) { return query(a, a + 1); }
    void print() {
        for (int i = 0; i < 2 * n - 1; ++i) {
            cout << (*this)[i];
            if (i != n) cout << "";
        }
        cout << endl;
    }
};

int main()
{
    ll i,j;
    ll n,k;
    cin >> n >> k;
    ll INF = 300000 + 1;
    vector<ll> ini(INF, 0);
    RUQ<ll> ruq(ini);
    rep(i,n){
        ll a;
        cin >> a;
        ll tmp = ruq.query(a, a+1);
        ll left = max(a - k, 0ll);
        ll right = min(a + k + 1, INF);
        ruq.update(left, right, tmp+1);
    }
    cout << ruq.query(0, INF) << endl;

    return 0;
}

Measured memory_bytes: 24348
using System;
class Program{
    static void Main(){
        string s = Console.ReadLine();
        string[] dateParams = s.Split('/');
    
        if(int.Parse(dateParams[0]) <= 2019 
        && int.Parse(dateParams[1]) <= 4 
        && int.Parse(dateParams[2]) <= 30){
            Console.WriteLine("Heisei");    
        } else {
            Console.WriteLine("TBD");
        }
        
    }
}


Measured memory_bytes: 11092
from collections import deque
import sys
input = sys.stdin.readline #inputの際に入力が終わるまで読み続ける


##入力例1
# 3 3
# ...
# .#.
# ...
def search():
    H, W = map(int, input().split()) ##H=3,W=3
    pos = deque([])

    D = [[True] * (W + 2)]  # True True True True True
    D += [[True] + [False] * W + [True] for i in range(H)]  # True False False False True
    D.append([True] * (W + 2))  # True True True True True
    ## T T T T T
    ## T F F F T
    ## T F F F T
    ## T F F F T
    ## T T T T T

    for i in range(H):
        maze = input() #inputの際に入力が終わるまで読み続ける
        for j in range(W):
            if maze[j] == "#":
                pos.append([i + 1, j + 1, 0]) #pos = ([2, 2, 0])
                D[i + 1][j + 1] = True
    ## T T T T T
    ## T F F F T
    ## T F T F T
    ## T F F F T
    ## T T T T T

    while len(pos) > 0:
        h, w, depth = pos.popleft()
        ##上下左右の座標に同時進行で同じ操作を行う

        if not D[h + 1][w]: #([2, 2, 0])の一つ上の座標([3, 2, 0])がNot True(False)の場合
            pos.append([h + 1, w, depth + 1]) #その座標([3, 2, 1])をpopに追加
                                              #deathは黒を白に変更した回数を記録していく
            D[h + 1][w] = True #その座標([3, 2, 0])をTrueに変更

        if not D[h - 1][w]:
            pos.append([h - 1, w, depth + 1])
            D[h - 1][w] = True

        if not D[h][w + 1]:
            pos.append([h, w + 1, depth + 1])
            D[h][w + 1] = True

        if not D[h][w - 1]:
            pos.append([h, w - 1, depth + 1])
            D[h][w - 1] = True
    ##最終的なdeath(白を黒に変更した回数)を出力
    return depth


print(search())






Measured memory_bytes: 168300
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  string S;
  while (cin >> S) {
    if (S == "Sunny") {
      cout << "Cloudy" << endl;
    } else if (S == "Cloudy") {
      cout << "Rainy" << endl;
    } else {
      cout << "Sunny" << endl;
    }
  }
  return 0;
}


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

int main() {
	int N;
	cin >> N;
	int ans = N/3;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3688
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] a = new int[n];
    for(int i = 0; i < n; i++) {
      a[i] = sc.nextInt();
    }
    int[] ord = new int[1000000];
    for(int i = 0; i < 1000000; i++) {
      ord[i] = -1;
    }
    int first = 500000;
    if(n % 2 == 0) {
      int last = first + 1;
      ord[first] = 1;
      ord[last] = 0;
      for(int i = 0; i < (n - 2) / 2; i++) {
        first--;
        last++;
        ord[first] = 2 * (i + 1) + 1;
        ord[last] = 2 * (i + 1); 
      }
    } else {
      int last = first;
      ord[first] = 0;
      ord[last] = 0;
      for(int i = 0; i < (n - 1) / 2; i++) {
        first--;
        last++;
        ord[first] = 2 * (i + 1);
        ord[last] = 2 * (i + 1) - 1; 
      }
    }
    for(int i = 0; i < n; i++) {
      System.out.print(a[ord[first + i]]);
      if(i < n - 1) System.out.print(" ");
    }
  }
}

Measured memory_bytes: 95992
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void) {
    int A, B, Q;
    cin >> A >> B >> Q;
    vector<long long int> s(A);
    vector<long long int> t(B);
    for(int i=0; i<A; i++) {
        cin >> s.at(i);
    }
    for(int i=0; i<B; i++) {
        cin >> t.at(i);
    }
    for(int i=0; i<Q; i++) {
        long long int x;
        cin >> x;
        long long int s_west;
        long long int s_east;
        long long int t_west;
        long long int t_east;
        long long int s_nearest;
        long long int t_nearest;
        if(x <= s.at(0)) {
            s_west = -1000000000000000000;
            s_east = s.at(0) - x;
            s_nearest = s_east;
        } else if(x > s.at(A-1)) {
            s_west = s.at(A-1) - x;
            s_east = 1000000000000000000;
            s_nearest = s_west;
        } else {
            auto tmp = upper_bound(s.begin(), s.end(), x);
            s_west = *(tmp-1) - x;
            s_east = *tmp - x;
            if(abs(s_west) < abs(s_east)) {
                s_nearest = s_west;
            } else {
                s_nearest = s_east;
            }
        }
        if(x <= t.at(0)) {
            t_west = -1000000000000000000;
            t_east = t.at(0) - x;
            t_nearest = t_east;
        } else if(x > t.at(B-1)) {
            t_west = t.at(B-1) - x;
            t_east = 1000000000000000000;
            t_nearest = t_west;
        } else {
            auto tmp = upper_bound(t.begin(), t.end(), x);
            t_west = *(tmp-1) - x;
            t_east = *tmp - x;
            if(abs(t_west) < abs(t_east)) {
                t_nearest = t_west;
            } else {
                t_nearest = t_east;
            }
        }
        if(s_nearest * t_nearest > 0) {
            cout << max(abs(s_nearest), abs(t_nearest)) << endl;
        } else {
            long long int s_distance = abs(s_nearest);
            long long int t_distance = abs(t_nearest);
            long long int ans1 = min(s_distance, t_distance) * 2 + max(s_distance, t_distance);
            long long int ans2 = -min(s_west, t_west);
            long long int ans3 = max(s_east, t_east);
            long long int ans = min({ans1, ans2, ans3});
            cout << ans << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 2944
# nikkei2019-qualC - Different Strokes
def main():
    # player gets ai <-> point spread increases by ai + bi -> sort A by ai + bi
    # player gets Ai whose index is even / rival gets Ai whose index is odd
    N, *AB = map(int, open(0).read().split())
    A = [(i, j) for i, j in zip(*[iter(AB)] * 2)]
    A.sort(key=sum, reverse=1)
    ans = sum(i for i, j in A[::2]) - sum(j for i, j in A[1::2])
    print(ans)


if __name__ == "__main__":
    main()

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

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

    if (N % 2 == 1)
    {
        cout << 0 << endl;
        return 0;
    }

    // N % 2 == 0 のとき・・・
    long long ans = 0, mod = 10;
    while (N >= mod)
    {
        ans += N / mod;
        mod *= 5;
    }

    cout << ans << endl;
    return 0;
}

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

using namespace std;

int main(){
    ios_base::sync_with_stdio (false);
    cout << fixed;
    cout.precision(10);
    //freopen ("joke.in","r",stdin);
	//freopen ("joke.out","w",stdout);
    
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    int m = max(a, max(b, c));
    cout << ( (a + b + c - m) + (m << k) );
    return 0;
}


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

int main() {
  int64_t N, M;
  cin >> N >> M;
  int64_t total = 0LL;
  for (int64_t i = 0LL; i < M; i++) {
    int64_t x;
    cin >> x;
    total += x;
  }
  if (total > N) cout << -1 << endl;
  else {
    cout << N - total << endl;
  }
}


Measured memory_bytes: 3640
// Created by sz
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e3+5;
const long long  INF = 1e18;

struct Edge {
    int from, to, dist;
    Edge(int u, int v, int d):from(u),to(v),dist(d) {}
};

struct Bellman_ford {
    int n, m;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool inq[maxn];
    bool neg[maxn];//点的路径上是否有负环
    long long d[maxn];//s到各个点的距离
    int p[maxn];//最短路中的上一条弧
    int cnt[maxn]; //点进队列次数
    
    
    void init(int n) {
        this->n = n;
        for(int i = 0; i < n; i++) G[i].clear();
        edges.clear();
    }
    
    void AddEdge(int from, int to, int dist) {
        edges.push_back(Edge(from, to, dist));
        m = edges.size();
        G[from].push_back(m-1);
    }
    
    
    //只能判断是否含环，不能判断到某点的路径上是否含环。
    bool bellman_ford_que(int s) {
        queue<int> Q;
        memset(inq, 0, sizeof(inq));
        memset(cnt, 0, sizeof(cnt));
        for(int i = 0; i < n; i++) d[i] = INF;
        d[s] = 0;
        inq[s] = true;  //标记是否在队列中
        Q.push(s);
        while(!Q.empty()) { //松弛到不能松弛为止
            int u = Q.front(); Q.pop();
            inq[u] = false;
            for(int i = 0; i < G[u].size(); i++) {
                Edge& e = edges[G[u][i]];
                if(d[u] < INF && d[e.to] > d[u] + e.dist) {
                    d[e.to] = d[u] + e.dist;
                    p[e.to] = G[u][i];
                    if(!inq[e.to]) {
                        Q.push(e.to);
                        inq[e.to] = true;
                        if(++cnt[e.to] > n) return false;
                    }
                }
            }
        }
        return true;
    }
    
    void bellman_ford(int s) {
        for(int i = 0; i < n; i++) d[i] = INF;
        d[s] = 0;
        //如果不含环，最短路最多经过n-1个点（不包括起点）， 松弛n-1次即可
        for (int k = 0; k < n-1; k++){
            for (int i = 0; i < m; i++){
                int x = edges[i].from;
                int y = edges[i].to;
                if(d[x]<INF) d[y] = min(d[y], d[x] + edges[i].dist);
            }
        }
        
        for (int k = 0; k < n-1; k++){
            for (int i = 0; i < m; i++){
                int x = edges[i].from;
                int y = edges[i].to;
                if(d[x]<INF && d[y] > d[x] + edges[i].dist) {
                    d[y] = d[x] + edges[i].dist;
                    neg[y] = true;
                }
                if(neg[x])neg[y] = true;
            }
        }
    }
};

Bellman_ford g;



int main(){
#ifdef LOCAL
    freopen("./input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n,m;
    cin>>n>>m;
    int x,y,c;
    g.init(n);
    for (int i = 1; i <= m; i++){
        cin>>x>>y>>c;
        x--, y--;
        g.AddEdge(x, y, -c);
    }
    
    g.bellman_ford(0);
    if(!g.neg[n-1])cout<< -g.d[n-1]<<endl;
    else cout<<"inf"<<endl;
    
    
    return 0;
}



Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define rrep(i,n) for(int i=1; i<n; i++)

using namespace std;
using vi = vector<int>;

int main(){
    int x;
    cin >> x;
    if (x >= 30)cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

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

int main() {
  string s,t; cin>>s>>t;
  int maxlen=0;
  rep(i,s.size()-t.size()+1) {
    int cnt=0;
    rep(j,t.size()) {
      if(t[j]==s[i+j]) cnt++;
    }
    maxlen=max(cnt,maxlen);
  }
  cout<<t.size()-maxlen<<endl;
}


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

// エイリアス
using  ll = long signed long;
using ull = long unsigned long;
using  ld = long double;
using   P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;

// 汎用マクロ
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOREACH(i,q) for (auto &i : q)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
#define SZ(x) ((int)(x).size())
template <class T>inline bool chmin(T &a, const T b) {if (a > b) { a = b; return true;} return false;}
template <class T>inline bool chmax(T &a, const T b) {if (a < b) { a = b; return true;} return false;}
template <class T>inline void line_out(const vector<T> vec) {int n = SZ(vec); rep(i, n) { cout << vec[i]; if(i < n-1) cout << " ";}cout << endl;}
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 28;
const ll INF64 = 1ll << 62;
const int mod = 1000000007;
//const int mod = 998244353;
struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  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++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  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()
{
  int n; cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  a.insert(a.begin(), 0);
  rep(i, n) a[i+1] += a[i];
  ll ans = INF64;
  for(int i = 1; i <= n; ++i) chmin(ans, abs(a[i] - (a[n]-a[i])));
  cout << ans << endl;
}


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

using namespace std;

int main() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] != s[i + 1]) {
			ans++;
		}
	}
	if (ans == 0) {
		cout << 1;
	}
	else {
		cout << ans;
	}
	
}


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


int main()
{
  int n;
  cin >> n;
  int r = n%10;
  string ans;
  if (r == 3) {
    ans = "bon";
  } else if (r == 0 || r == 1 || r == 6 || r == 8){
    ans = "pon";
  } else {
    ans = "hon";
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3624
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int mp[10000][10000];
int main(void)
{

	int h, w, n, a[10000], big = 1, small = 1;
	cin >> h >> w >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];

	for (int i = 0; i < h; i++)
	{
		if (i%2==0)
			for (int j = 0; j < w; j++, small++)
			{
				mp[i][j] = big;
				if (small == a[big - 1]) big++, small = 0;
				
			}
		else
			for (int j = w - 1; j >= 0; j--, small++)
			{
				mp[i][j] = big;
				if (small == a[big - 1])
					big++, small = 0;
			}
	}
	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
			printf("%d ", mp[i][j]);
		printf("\n");
	}
	return false;
}

Measured memory_bytes: 2560