akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i, j) FOR(i, 0, j)
#define FOR(i, j, k) for(int i = j; i < k; ++i)

using namespace std;

int map[2][101][101];
// 0...cost 1...time
int main(){
  int n, m;
  while(scanf("%d%d", &n, &m) && n && m){
    rep(i, 101) rep(j, 101) rep(k, 2) map[k][j][i] = 999999999;
    int a, b, c, t;
    rep(i, n){
      scanf("%d%d%d%d", &a, &b, &c, &t);
      a--;b--;
      map[0][a][b] = map[0][b][a] = c;
      map[1][a][b] = map[1][b][a] = t;
    }
    rep(k, m) rep(i, m) rep(j, m) rep(l, 2) map[l][i][j] = min(map[l][i][j], map[l][i][k] + map[l][k][j]);

    int k, p, q, r;
    scanf("%d", &k);
    while(k--){
      scanf("%d%d%d", &p, &q, &r);
      p--;q--;
      printf("%d\n", map[r][p][q]);
    }
  }
  return 0;
}

Measured memory_bytes: 1108
#include <bits/stdc++.h>
using namespace std;
#define mod 998244353
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3fll
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
struct rhash
{
    int n;
    ll mod1=1e9+7,mod2=1e9+9;
	ll base1=1007,base2=1009;
    vector<ll> hash1,hash2,pow1,pow2;
    void init(string s)
	{
        n=s.length();
        hash1.assign(n+1,0);
        hash2.assign(n+1,0);
        pow1.assign(n+1,1);
        pow2.assign(n+1,1);
        for(int i=0;i<n;i++)
		{
            hash1[i+1]=(hash1[i]*base1+s[i])%mod1;
            hash2[i+1]=(hash2[i]*base2+s[i])%mod2;
            pow1[i+1]=(pow1[i]*base1)%mod1;
            pow2[i+1]=(pow2[i]*base2)%mod2;
        }
    }
    pair<ll,ll> getval(int l,int r)
	{
	//	cout<<l<<" "<<r<<endl;
        ll h1=((hash1[r]-hash1[l]*pow1[r-l])%mod1+mod1)%mod1;
        ll h2=((hash2[r]-hash2[l]*pow2[r-l])%mod2+mod2)%mod2;
        return make_pair(h1,h2);
    }
};
const int maxn=20e5+10;
int cnt[maxn];
vector<int> tmp;
set<int> st;
int main()
{
    string s,t;
	cin>>s>>t;
	while(s.length()<t.length())s+=s;
	int n=s.length(),m=t.length();
	s+=s;
//	cout<<s<<" "<<t<<endl;
    rhash hs,ht;
	hs.init(s),ht.init(t);
    memset(cnt,-1,sizeof(cnt));
    int ans=0;
    for(int i=0;i<n;i++)if(!~cnt[i])
    {
    	int p=i,res=0;
    	tmp.clear();
    	st.clear();
    //	cout<<i<<endl;
    	while(1)
    	{
    		if(ht.getval(0,m)!=hs.getval(p,p+m))break;
    	//	cout<<"!"<<endl;
    	//	cout<<tmp.size()<<" "<<p<<endl;
    		tmp.push_back(p);
    	//	cout<<p<<endl;
    		st.insert(p);
    		p=(p+m)%n;
    		if(!st.empty()&&st.count(p))
    		{
    			cout<<-1;
    			return 0;
			}
			if(cnt[p]!=-1)
			{
				res=cnt[p];
				break;
			}
		//	cout<<"?"<<endl;
		}
		if(tmp.empty())cnt[i]=0;
		else
		{
			for(int i=0;i<tmp.size();i++)
				cnt[tmp[tmp.size()-1-i]]=res+i+1;
		}
	}
	for(int i=0;i<n;i++)ans=max(ans,cnt[i]);
    cout<<ans;
    return 0;
}


Measured memory_bytes: 114084
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; //10^19 < 9223372036854775807
typedef unsigned long long ull; //10^20 < 18446744073709551615

#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 

#define MOD 1000000007

int main(void)
{
    ll N;
    cin >> N;

    vector<ll> D1(N);
    vector<ll> D2(N);

    int cnt = 0;
    REP (i, N) {
        cin >> D1[i] >> D2[i];
        if (D1[i] == D2[i]) {
            cnt++;
        }
        else if (cnt < 3) {
            cnt = 0;
        }
    }

    string ans = "No";
    if (cnt >= 3) {
        ans = "Yes";
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3608
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''

def main():
    N = int(input())

    A = []
    for _ in range(N):
        a = int(input())
        A.append(a)
    ii = A.index(max(A))
    m = max(A)
    A.pop(ii)
    m2 = max(A)
    
    for i in range(N):
        if i == ii:
            print(m2)
        else:
            print(m)


if __name__ == '__main__':
    main()

Measured memory_bytes: 12556
#include <stdio.h>
#include <stdlib.h>

int main(void){
    char s[10] ={};
    int leng, i;
    scanf("%s", &s);
    for(i=0; 1; i++){
        if(s[i] == '\0'){
            leng = i;
            break;
        }
    }
    if(leng == 2) printf("%s", s);
    else printf("%c%c%c", s[2], s[1], s[0]);

}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())//vectorの降順ソート
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;

typedef tuple<ll, ll, ll> T;

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;cin>>s;
    ll ans=0;
    REP(i,s.size()-1){
        if(s[i]!=s[i+1])ans++;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n; cin >> n;
	long long int a[100005], b[100005], c[100005];
	long long int bsum = 0LL;
	for(int i=0;i<n;i++){
		cin >> a[i] >> b[i];
		c[i] = a[i]+b[i];
		bsum += b[i];
	}
	sort(c,c+n);
	long long int ans = -bsum;
	for(int i=0;i<n;i++){
		if(i%2==0){
			ans += c[n-1-i];
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2560
using System;

namespace _0048
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                string input = Console.ReadLine();
                if (input == null)
                {
                    break;
                }
                double now = double.Parse(input);
                if (now <= 48)
                {
                    Console.WriteLine("light fly");
                }
                else if (now <= 51)
                {
                    Console.WriteLine("fly");
                }
                else if (now <= 54)
                {
                    Console.WriteLine("bantam");
                }
                else if (now <= 57)
                {
                    Console.WriteLine("feather");
                }
                else if (now <= 60)
                {
                    Console.WriteLine("light");
                }
                else if (now <= 64)
                {
                    Console.WriteLine("light welter");
                }
                else if (now <= 69)
                {
                    Console.WriteLine("welter");
                }
                else if (now <= 75)
                {
                    Console.WriteLine("light middle");
                }
                else if (now <= 81)
                {
                    Console.WriteLine("middle");
                }
                else if (now <= 91)
                {
                    Console.WriteLine("light heavy");
                }
                else
                {
                    Console.WriteLine("heavy");
                }
            }
        }
    }
}

Measured memory_bytes: 9072
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        sc.close();

        if (Math.max(a, b) >= 10) {
            System.out.println(-1);
        } else {
            System.out.println(a * b);
        }
    }
}


Measured memory_bytes: 23252
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
using namespace std;
typedef long long ll;
typedef pair<int, int> P; 
const int inf = 1<<21;
const ll INF = 1LL << 60;
const ll mod = 1e9+7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int k;
    cin >> k;
    ll sum = 0;
    rep(a, k)rep(b, k)rep(c, k){
        sum += gcd(gcd(a+1,b+1),c+1);
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3656
#include <cstdio>
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#define INT long long
#define PP pair<double, pair<INT, pair<INT, INT> > >
using namespace std;

int n, ans;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i = 0, l, r ; i < n ; i++ )
    {
        cin>>l>>r;
        ans += r-l+1;
    }
    cout<<ans<<endl;
    
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
char p[80];
int n, K, chk[80], Loc[40], C[40], F[150], InvF[150], Mod = 1000000007;
int D[40][40], TD[40][40]; // 한 블럭의 크기, 블럭의 개수, 쓴거의 개수

int Pow(int a, int b) {
	int r = 1;
	while (b) {
		if (b & 1)r = 1ll * r*a%Mod;
		a = 1ll * a*a%Mod; b >>= 1;
	}
	return r;
}
int Comb(int n, int r) {
	return 1ll * F[n] * InvF[r] % Mod*InvF[n - r]%Mod;
}

int DD[80][80][80][3];

int Do(int A, int B) { // R* : A, RBxx : B
	int i, c1 = 0, c2 = 0, j, k, ii, jj;
	if (!A && !B)return 1;
	for (i = 0; i < K; i++) {
		chk[i] = 0;
		if (p[i] == 'r' && c1 < B) {
			chk[i] = 1;
			c1++;
		}
		if (p[i] == 'b' && c2 < c1) {
			chk[i] = 1;
			c2++;
			Loc[c2] = i;
		}
	}
	if (c1 < B || c2 < B)return 0;
	c1 = 0;
	for (i = 0; i < K; i++) {
		if (p[i] == 'r' && !chk[i] && c1 < A) {
			chk[i] = 1;
			c1++;
		}
	}
	if (c1 < A)return 0;
	for (i = 1; i <= B; i++) {
		C[B-i+1] = 0;
		for (j = Loc[i]; j < K; j++)if (!chk[j])C[B-i+1]++;
	}
	for (i = 0; i < 40; i++)for (j = 0; j < 40; j++)D[i][j] = TD[i][j] = 0;
	D[0][0] = InvF[A];

	for (i = 0; i <= n / 2; i++) {
		for (j = 0; j < 40; j++) {
			for (k = 0; k < 40; k++) {
				if (!D[j][k])continue;
				for (ii = 0;; ii++) {
					int s = (ii*i + k);
					if (ii+j > B || s * 2 + A + B + (A + B - 1) > n || C[j+ii] < s)break;
					TD[j + ii][s] = (TD[j + ii][s] + 1ll * D[j][k] * InvF[ii]) % Mod;
				}
			}
		}
		for (j = 0; j < 40; j++)for (k = 0; k < 40; k++) {
			D[j][k] = TD[j][k];
			TD[j][k] = 0;
		}
	}
	int r = 0;
	for (i = 0; i < 40; i++) {
		int c = (A + B + A + B - 1 + i * 2);
		int t = c + B * 2 + 2;
		if (!D[B][i] || n-c < 0)continue;
		r = (r + 1ll * D[B][i] * F[A+B] % Mod * Comb(t + (n - c) - 1, (n - c)))%Mod;
	}
	return r;
}
int main() {
	int i, j, res = 0;
	F[0] = 1;
	for (i = 1; i <= 142; i++)F[i] = 1ll * F[i - 1] * i%Mod;
	for (i = 0; i <= 142; i++)InvF[i] = Pow(F[i], Mod - 2);
	scanf("%d%d", &n, &K);
	scanf("%s", p);
	for (i = 0; i <= (n+1)/2; i++) {
		for (j = 0; i + j <= (n + 1) / 2; j++) {
			res = (res + Do(i, j))%Mod;
		}
	}
	printf("%d\n", res);
}

Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include <math.h>
#include<stdio.h>
#include <climits>
#include<algorithm>
#include<string>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define LL  long long 
#define Pi 3.14159265358979;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int i = 0, j = 0;//ループ用配列

	int a,b;
	int c = 0;//繋げるための桁数
	int data = 0;
	float f_ans;
	int i_ans;
	cin >> a >> b;
	if (b / 100 == 1)c = 1000;
	else if (b / 10 >= 1)c = 100;
	else c = 10;

	data = a * c + b;
	
	f_ans = sqrt(data);
	i_ans = (int)f_ans;
	if (f_ans == i_ans)cout << "Yes" << "\n";
	else cout << "No" << "\n";
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>

template <class T>
T GCD(T m, T n){
    const T zero = static_cast<T>(0);
    T r;
    while((r=m%n) != zero){
        m = n;
        n = r;
    }
    return n;
}

template<class T>
std::pair<std::vector<T>, std::vector<T> > getPrimeFactors(const T &N){
    const T zero = static_cast<T>(0);
    const T one = static_cast<T>(1);
    const T two = static_cast<T>(2);
    std::vector<T> F; //prime factors
    std::vector<T> E; //exponents
    T tmpN = N, tmpE;
    for(T i=two; i*i<=N; ++i){
        if(tmpN%i == zero){
            F.emplace_back(i);
            tmpE = zero;
            while(tmpN%i == zero){
                tmpN /= i;
                ++tmpE;
            }
            E.emplace_back(tmpE);
        }
    }
    if(tmpN > one){
        F.emplace_back(tmpN);
        E.emplace_back(one);
    }
    return std::make_pair(F,E);
}

int main(int argc, char *argv[]){
    long long A,B;
    std::cin >> A >> B;
    long long D = GCD(A,B);
    auto FE = getPrimeFactors(D);
    std::cout << FE.first.size() + static_cast<long long>(1) << std::endl;

    return 0;
}


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

public class Program
{
    #region Standard I/O
    readonly TextReader input;
    readonly TextWriter output;

    X[] ReadLine<X>(Func<string, X> func)
    {
        return input.ReadLine().Split(' ').Select(func).ToArray();
    }

    void WriteLineOne(object obj)
    {
        output.WriteLine("{0}", obj);
    }

    void WriteLineMany(params object[] objects)
    {
        output.WriteLine(string.Join(" ", objects.Select(obj => obj.ToString())));
    }
    #endregion

    int h, w;
    int n;
    int[] xs;

    static readonly int[] dx = new[] { 1, 0, -1, 0 };
    static readonly int[] dy = new[] { 0, 1, 0, -1 };

    IEnumerable<IEnumerable<int>> Solve()
    {
        {
            {
                var l = ReadLine(int.Parse);
                h = l[0];
                w = l[1];
            }

            n = ReadLine(int.Parse)[0];

            xs = ReadLine(int.Parse);
        }

        var table = Enumerable.Range(0, h + 2).Select(_ => new int[w + 2]).ToArray();

        for (var y = 0; y < h + 2; y++)
        {
            for (var x = 0; x < w + 2; x++)
            {
                if (x == 0 || x == w + 1 || y == 0 || y == h + 1)
                {
                    table[y][x] = -1;
                }
            }
        }

        {
            var y = 1;
            var x = 1;
            var c = 0;
            var d = 0;

            for (var i = 0; i < h * w; i++)
            {
                table[y][x] = c + 1;
                xs[c]--;

                var y2 = y + dy[d];
                var x2 = x + dx[d];
                if (table[y2][x2] != 0)
                {
                    d = (d + 1) % 4;
                    y2 = y + dy[d];
                    x2 = x + dx[d];
                }

                y = y2;
                x = x2;

                if (xs[c] == 0)
                {
                    c++;
                }
            }
        }

        return table.Skip(1).Take(h).Select(row => row.Skip(1).Take(w));
    }

    public void Run()
    {
        var rows = Solve();

        foreach (var row in rows)
        {
            WriteLineOne(string.Join(" ", row));
        }
    }

    public Program(TextReader input, TextWriter output)
    {
        this.input = input;
        this.output = output;
    }

    public static void Main(string[] args)
    {
        new Program(Console.In, Console.Out).Run();
    }
}


Measured memory_bytes: 13920
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define ll long long
#define imfor(i, n) for(int i = 0; i < n; i++)
using namespace std;
ll MOD = 1000000007;

int main() {
    int n;
    int h[100010];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    bool ans = true;
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            h[i]--;
        }
        else {
            if (h[i-1] != h[i]) {
                h[i]--;
            }
        }
        
        if (i != n - 1) {
            if (h[i] > h[i+1]) {
                ans = false;
                break;
            }
        }
    }
    if (ans) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

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

int main(){
  
  int N, M, i;
  cin >> N >> M;
  vector<long long> st(N + 1, -1);
  
  st[0] = 1; st[1] = 1;
  for(i = 0; i < M; i++){
    int a;
    cin >> a;
    st[a] = 0;
  }
  
  for(i = 2; i < N + 1; i++){
    if(st[i] != 0) st[i] = (st[i - 1] + st[i - 2]) % 1000000007;
  }
  
  cout << st[N] << endl;
  return 0;
}

Measured memory_bytes: 3960
H, W = (int(i) for i in input().split())
t = []
t.append(['.']*(H+2))

for j in range(H):
	tmp = input()
	tmp = '.' + tmp + '.'
	t.append(list(tmp))

t.append(['.']*(H+2))

def CheckBlock(i,k):
	if t[i][k-1] == '#': #check up
		return 0
	elif t[i-1][k] == '#': #check left
		return 1
	elif t[i+1][k] == '#': #check right
		return 2
	elif t[i][k+1] == '#': #check down
		return 3
	else:
		return 4

for k in range(1,W+1):
	for i in range(1,H+1):
		if t[i][k] == '#':
			marker = CheckBlock(i,k)
			if marker == 4:
				print('No')
				quit()
print('Yes')

Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<map>
#include<queue>
using namespace std;
typedef pair<int,int> P;
int n;
int p[100005];
int m[100005];
/*
vector<int> v;
int dfs(int x){
  for(int i=0;i<v.size();i++) if(v[i]==x) return -2;
  v.push_back(x);
  if(p[x]==0) return (m[x]=x);
  if(m[x]!=-1) return m[x];
  return (m[x]=dfs(x+p[x]));
}
*/
int main(){
  cin >> n;
  int i,j,k;
  fill(p,p+100005,0);
  for(i=0;i<n;i++) cin >> p[i];

  /*
  fill(m,m+100005,-1);
  for(i=0;i<n;i++){
    if(m[i]==-1){
      v.clear();
      m[i]=dfs(i);
    }
  }
  */
  
  int d[100005];
  int inf = 1 << 20;
  fill(d,d+100005,inf);

  queue<P> q;
  P a;
  q.push(P(0,0));
  while(!q.empty()){
    a=q.front();q.pop();
    if(a.first<0) continue;
    //cout << a.first << ":" << a.second << endl;
    if(d[a.first]<=a.second) continue;
    d[a.first]=a.second;
    if(p[a.first]==0){
      if(a.first+6>n) {
	d[n-1]=min(d[n-1],a.second+1);
	continue;
      }
      for(i=1;i<=6;i++){
	q.push(P(a.first+i,a.second+1));
      }
    }else{
      q.push(P(a.first+p[a.first],a.second));
    }
    
  }

  cout << d[n-1] << endl;
  //for(i=1;i<=n;i++) cout << m[i] << endl;

  return 0;
}

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

int main() 
{
    string S;
    cin >> S;
    
    string rev = S; 
    reverse(rev.begin(), rev.end());
    
    int ans = 0;
    for (int i = 0; i < S.length(); i++) {
        if (S[i] != rev[i]) {
            ans++;
        }
    }
    cout << ans/2 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,a,b;
    string s;
    cin>>n>>a>>b>>s;
    int a1=0,b1=0;
    for(int i=0;i<n;i++){
      if(s[i]=='a' && a+b>a1+b1){
        cout<<"Yes"<<endl;
        a1++;
      }
      else if(s[i]=='b' && b+a>a1+b1 && b>b1){
        cout<<"Yes"<<endl;
        b1++;
      }
      else{
        cout<<"No"<<endl;
      }
    }
  return(0);
}

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

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define all(x) (x).begin(),(x).end()
#define foreach(u,v) for(auto (u) : (v))
#define pb push_back
#define mp make_pair
#define mt make_tuple

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;

const int inf = 1e9;
const ll linf = 1LL<<60;
const ll mod = 1e9 + 7;
const double eps = 1e-9;

/*
 */

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

  if(a == b) cout << c << endl;
  else if(b == c) cout << a << endl;
  else cout << b << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>

#define INF 1000000000
#define LINF 9000000000000000000
#define mod 1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<long long>vll;
typedef pair<int,int> pi;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

/*---------------------------------------------------*/

bool b[505][505];
ll lists[505];

/* ---- bitDP part ----*/
void init_bitDP(int n,int m){
  /* create bit list */
  for(int i=0;i<n;i++){
    lists[i]=0;
    for(int j=0;j<m;j++){
      if(b[i][j])lists[i]|=(1<<j);
    }
  }
}

int bitDP(int n,int m){
  vector<vector<int> >dp(n+1,vector<int>((1<<m),-1));
  for(int i=0;i<n;i++){
    for(int j=0;j<(1<<m);j++){
      dp[i][j]=-INF;
    }
  }
  
  dp[0][0]=0;
  for(int i=1;i<=n;i++){
    for(int j=0;j<(1<<m);j++){
      dp[i][j]=max(dp[i-1][j],dp[i-1][j^lists[i-1]]+1);
    }
  }
  return dp[n][0];
}


/* ---- dfs part ---- */
void init_dfs(bool used[]){
  for(int i=0;i<505;i++){
    used[i]=false;
  }
}

int dfs_calc(int n,int m,bool used[]){
  int ret=0;
  for(int i=0;i<n;i++)ret+=used[i];
  for(int i=0;i<m;i++){
    int sum=0;
    for(int j=0;j<n;j++){
      if(used[j])sum+=b[j][i];
    }
    if(sum%2)return -1;
  }
  return ret;
}

int dfs(int n,int m,int cnt,bool used[]){
  int ret=0;
  if(n==cnt){
    return dfs_calc(n,m,used);
  }
  
  used[cnt]=true;
  ret=max(ret,dfs(n,m,cnt+1,used));
  used[cnt]=false;
  ret=max(ret,dfs(n,m,cnt+1,used));  
  
  return ret;
}


/* ---- main ---- */
void solve(int n,int m){
  char c;
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      cin>>c;
      b[i][j]=c-'0';
    }
  }
  
  if(n<=m){
    bool used[505];
    init_dfs(used);
    cout<<dfs(n,m,0,used)<<endl;
  }else{
    init_bitDP(n,m);
    cout<<bitDP(n,m)<<endl;;
  }
}

int main(){
  int n,m;
  while(scanf("%d%d",&n,&m),n|m){
    solve(n,m);
  }
  return 0;
}



Measured memory_bytes: 208472
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
//#include <boost/lexical_cast.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define pb push_back
#define mp make_pair
#define endl '\n'
#define PI acos(-1)
#define bitcount(a) __builtin_popcountll(a)
#define P pair<int,int>
typedef tree<int,null_type,less_equal <int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

long mod=1e9+7;
const int N=1e5+5;
vector<int>v[N];
int a[N];
int K;
void dfs(int i,int par,int k)
{
	int idx=1;
	
	a[i]=k;
	for(auto u:v[i])
	{
		if(u!=par)
		{
			if(par==-1)
			{
				dfs(u,i,max(K-idx,(int)0));
				a[i]=((a[i]%mod)*(a[u]%mod))%mod;
				a[i]%=mod;
				++idx;
			}
			else
			{
				
					dfs(u,i,max(K-idx-1,(int)0));
					a[i]=((a[i]%mod)*(a[u]%mod))%mod;
					a[i]%=mod;
					++idx;
				
			}

		}
	}

}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n>>K;
	for(int i=0;i<n-1;i++)
	{
		int x,y;
		cin>>x>>y;
		v[x].pb(y);
		v[y].pb(x);
	}
	for(int i=0;i<N;i++)
		a[i]=1;
	dfs(1,-1,K);
	a[1]%=mod;
	cout<<a[1];
	return 0;
}

Measured memory_bytes: 11136
N,M = map(int,input().split())

def dfs(v,a,b):
    visited[v] = True
    for n in E1[v]:
        if not visited[n] and set([v,n]) != set([a,b]):
            dfs(n,a,b)


E1 = [[] for _ in range(N)]
E2 = []
Ans = 0

for i in range(M):
    a,b = map(int,input().split())
    E1[a-1].append(b-1)
    E1[b-1].append(a-1)
    E2.append((a-1,b-1))
for i in range(M):
    visited = [True]+[False]*(N-1)
    a,b = E2[i]
    dfs(0,a,b)
    if visited != [True]*N:
        Ans += 1
print(Ans)

Measured memory_bytes: 3064
#ATCoder
count = 0
ans = 0
flg = false
S = gets.chomp.to_s
for i in 0..S.length-1 do
    if S[i] == "A"|| S[i] == "C" || S[i] =="G" || S[i] =="T"
        count = count + 1
        flg = true
    else
        if ans < count
            ans = count
        end
        count = 0
        flg = false
    end
end
if flg == true && count > ans
    ans = count
end    
puts ans

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

using namespace std;

// Repetitions
#define FOR(i,a,n) for(ll i = ((ll) a); i < ((ll) n); ++i)
#define FORR(i, s, g) for(ll i = ((ll)s - 1); i >= ((ll) g); --i)
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) FORR(i, n, 0)

// Container Utils
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define SORTALL(v) sort(ALL(v))
#define SZ(a) int((a).size())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())

// For Debug
#define DMP(x)  cerr << #x << " = " << (x) << endl
#define DBG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl

// Aliases
#define PB push_back
#define MP make_pair
using ll = long long;
using ld = long double;
using str = string;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vs = vector<str>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;

// Constant variables
const ld PI = (acos(-1));
const ll MOD = 1000000007;

// I/O Asynchronizing
struct __io_async{
    __io_async(){
        cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);
    };
};

bool judge(const int n) {
    FOR(i, 2, sqrt(n) + 1) {
        if(n % i == 0) return false;
    }
    return true;
}

int next_prime(const int x) {
    int i = x - 1;
    while(true) {
        i++;
        if(i == 2 || i == 3) break;
        if(i % 6 != 1 && i % 6 != 5) continue;
        if(judge(i)) break;
    }
    return i;
}

int main() {
    int x;
    cin >> x;
    cout << next_prime(x) << endl;

    return 0;
}


Measured memory_bytes: 256
import bisect
import sys
input = sys.stdin.readline

n = int(input())
a = [int(item) for item in input().split()]
cnt = [0] * (n + 1)
for item in a:
    cnt[item] += 1
cnt.sort()
cumsum = [0] * (n + 2)
for i in range(n+1):
    cumsum[i+1] = cumsum[i] + cnt[i]

indexes = [0] * (n+1)
for i in range(n+1):
    indexes[i] = bisect.bisect_left(cnt, i) - 1

ans = []
for i in range(n):
    if cnt[i+1] == 0:
        ans.append(0)
        continue
    l = 0; r = n+1
    while r - l > 1:
        mid = (l + r) // 2
        index = indexes[mid]
        if index <= i:
            l = mid
            continue
        num = index - i
        if mid * num <= cumsum[index + 1]:
            l = mid
        else:
            r = mid
    ans.append(l)

ans.reverse()
print("\n".join([str(item) for item in ans]))

Measured memory_bytes: 122908
tree_list = []
n = 0
k = 0
tree_max = 0
tree_min = 0

n, k = input().split(' ')
n = int(n)
k = int(k)
for i in range(n):
    tree = int(input())
    tree_list.append(tree)

tree_list.sort()
diff = tree_list[n - 1]
for i in range(n - k + 1):
    tree_min = tree_list[i]
    tree_max = tree_list[i + k - 1]
    if tree_max - tree_min < diff:
        diff = tree_max - tree_min

print(diff)

Measured memory_bytes: 7384
#include<iostream>
using namespace std;
int n,s[3][105],x,ans;
int main(){
    cin>>n;
    for(int i=1;i<=2;i++)
        for(int j=1;j<=n;j++)
            cin>>x,s[i][j]=s[i][j-1]+x;
    for(int i=1;i<=n;i++)
        ans=max(ans,s[1][i]+s[2][n]-s[2][i-1]);
    cout<<ans<<endl;
    return 0;
}

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

using namespace std;

int main(){
    int n;
    cin>>n;
    int arr1[n];
    int arr2[n];
    int arr3[n-1];
    
    for(int i=0;i<n;i++){
        cin>>arr1[i];
    }
    
    for(int i=0;i<n;i++){
        cin>>arr2[i];
    }
    
    for(int i=0;i<n-1;i++){
        cin>>arr3[i];
    }
    
    int result=0;
    int x=0;
    for(int i=0;i<n;i++){
        result+=arr2[i];
    }
    
    for(int i=0;i<n;i++){
        if((arr1[i])+1==arr1[i+1]){
            x=arr1[i];
            // cout<<"x is: "<<x<<endl;
            result+=arr3[x-1];
        }
    }
    
    cout<<result;
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <algorithm>
#include <vector>

int main() {
  int a,b;
  scanf("%d",&a);
  scanf("%d",&b);
  if(a<9&&b<9) {
    printf("Yay!\n");
  } else {
    printf(":(\n");  
  }
  return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    A,V=pin()
    B,W=pin()
    T,=pin()
    c=B-A

    if W==V:
        print("NO")
        return
    if c>0:
        t=c/(V-W)
        #print(t)
        if T>=t and t>0:
            print("YES")
        else:print("NO")
    else:
        t=c/(V-W)
        t*=-1
        #print(t)
        if T>=t and t>0:
            print("YES")
        else:print("NO")
#%%submit!
resolve()

Measured memory_bytes: 9220
#pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef int_fast64_t ll;
inline void fastio(){cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15);}

int main() {
    fastio();
    ll N, M, a, b, s, t;
    bool f;
    cin >> N >> M;
    vector<vector<ll>> G(N + 1, vector<ll>(0));
    REP(i, M) {
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    s = 1;
    t = G[1][0];
    list<ll> ans = {s, t};
    vector<ll> visited(N + 1, 0);
    while(true) {
        visited[s] = visited[t] = 1;
        f = false;
        for(auto& x : G[s]) {
            if(visited[x] == 0) {
                s = x; f = true;
                ans.push_front(s);
                break;
            }
        }
        if(f) continue;
        for(auto& x : G[t]) {
            if(visited[x] == 0) {
                t = x; f = true;
                ans.push_back(t);
                break;
            }
        }
        if(f) continue;
        break;
    }
    cout << ans.size() << "\n";
    for(auto it = ans.begin(); it != ans.end(); it++) cout << *it << " ";
    cout << "\n";
	return 0;
}

Measured memory_bytes: 10240
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <iomanip>
#include <utility>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;

const ll INF = 1LL << 40;
const ll LIM = 100 * 1000;

int solve(void);

ll cnt(ll i, ll n)
{
	ll p2n = (1LL << n);
	ll n2 = p2n / 2LL;
	ll k = (i % p2n);
	return (i / p2n) * n2 + max(0LL, k - n2);
}

int main(void)
{
	while (solve())
	{
	}
	return 0;
}

int solve(void)
{
	ll A, B;
	cin >> A >> B;

	if (A == B) { cout << A << endl; return 0; }

	const ll cmax = 40;
	vector<ll> bit_cnt(cmax, 0);
	for (int i = 0; i < cmax; i++)
	{
		bit_cnt[i] = cnt(B + 1, i + 1) - cnt(A, i + 1);
	}
	ll ans = 0;
	for (int i = 0; i < cmax; i++)
	{
		if (bit_cnt[i] % 2)
		{
			ans |= (1LL << i);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define erep(e,v) for(auto && e :v)
#define all(in) in.begin(), in.end()
#define MP make_pair
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
#define EPS 0.0000000001
using namespace std;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
template<class T> void join(T &a){int t = 0;for(auto itr :a){if(t++)cout << " "; cout << itr;} cout <<endl; }
using ld  = long double;
using pii = pair<int,int>;
using piii = pair<int,pii>;
int W,H;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
signed main(){
    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    int mod = 1000000000+7;
    map<char,int>mp;
    for(auto c : s) mp[c]++;
    string alpha = "abcdefghijklmnopqrstuvwxyz";
    rep(i,n){
        auto key = s[i];
        int res = 1;
        --mp[key];
        for(auto c : alpha){
            if(c == key or mp[c] == 0)continue;
            res *= (mp[c]+1);
            res %= mod;
        }
        ans += res;
        ans %= mod;
    }
    cout << (ans)%mod << endl;
}




Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)n; i++)

int n, m;
int x[51], y[51], z[51];
int dp1[51][51][51];
int dp2[51][51][51];
const int INF = 1e9;
int cost(int a, int b, int c) {
    if (dp1[a][b][c] != -INF) return dp1[a][b][c];
    int res = -INF;
    rep(i, b + 1) rep(j, c + 1) {
        if (i == 0 && j == 0)
            res = max(res, z[a]);
        else if (i + j <= 8)
            res = max(res, i * x[a] + j * y[a]);
    }
    return dp1[a][b][c] = res;
}
int dfs(int a, int b, int c) {
    if (a == n) return 0;
    if (dp2[a][b][c] != -INF) return dp2[a][b][c];
    // int res = dfs(a + 1, b, 0) + z[a];
    int res = -INF;

    rep(i, b + 1) { res = max(res, dfs(a + 1, b - i, i) + cost(a, i, c)); }

    return dp2[a][b][c] = res;
}
int main() {
    rep(i, 51) rep(j, 51) rep(k, 51) dp1[i][j][k] = -INF;
    rep(i, 51) rep(j, 51) rep(k, 51) dp2[i][j][k] = -INF;
    cin >> n >> m;
    rep(i, n) cin >> x[i] >> y[i] >> z[i];
    cout << dfs(0, m, 0) << endl;
}

Measured memory_bytes: 4140
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner scanner = new Scanner(System.in);

		String N = scanner.next();

		
		if(N.contains("7")) {
			System.out.println("Yes");			
		}
		else {
			System.out.println("No");	
		}

		scanner.close();

	}
}

Measured memory_bytes: 26996
h,w = [int(x) for x in input().split()]
meiro = [list(input()) for _ in range(h)]
ans = [[float("INF")]*w for _ in range(h)]
mina=-1
for i in range(h):
    for j in range(w):
        if meiro[i][j]=="#":
            ans[i][j]=0
        else:
            if j!=0:
                ans[i][j]=min(ans[i][j-1]+1,ans[i][j])
for i in range(h):
    for j in range(w-1,-1,-1):
        if meiro[i][j]=="#":
            ans[i][j]=0
        else:
            if j!=w-1:
                ans[i][j]=min(ans[i][j+1]+1,ans[i][j])
for j in range(w):
    for i in range(h):
        if meiro[i][j]=="#":
            ans[i][j]=0
        else:
            if i!=0:
                ans[i][j]=min(ans[i-1][j]+1,ans[i][j])
for j in range(w):
    for i in range(h-1,-1,-1):
        if meiro[i][j]=="#":
            ans[i][j]=0
        else:
            if i!=h-1:
                ans[i][j]=min(ans[i+1][j]+1,ans[i][j])
for i in range(h):
    for j in range(w):
        mina = max(mina,ans[i][j])
print(mina)


Measured memory_bytes: 138844
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <chrono>

using namespace __gnu_pbds;
using namespace std;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)

#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define pi pair<ll,ll>
#define pii pair<ll,pi >
#define ppi pair<pi,ll>
#define ppp pair<pi,pi >
#define ex(str,a,b) str.substr((int)(a),min((int)str.size()-a,(int)(b-a+1))) 
#define all(X) X.begin(),X.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// for pair comparison function(ascending order) use return (i1.ff < i2.ff);

/* string operations :
   str.substr (x,y) : returns a substring str[x],str[x+1],...str[x+y-1]
   __builtin_popcount(n) : no. of set bits in n.
*/

const int M = (1<<20)+5;
const int md = 1e9+7;

priority_queue<ll,vector<ll >,greater<ll > > pq;

ll pwr(ll a,ll n,ll m)
{
	ll p=1;
	while(n>0)
	{
		if(n%2==1)
			p=(p*a)%m;
		a=(a*a)%m;
		n=n/2;
	}
	return p;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll a,b,c,d,k,s,h;
	cin >> a >> b >> c >> d >> k;
	s = a*60+b;
	h = c*60+d;

	if(h-s<k)
		cout << 0 << "\n";
	else
		cout << h-k-s << "\n";
}

Measured memory_bytes: 3656
import sys

def main():
  input = sys.stdin.readline
  N, T = map(int, input().split())
  C = 1010
  for _ in range(N):
    c, t = map(int, input().split())
    if t > T:
      continue
    else:
      C = min(C, c)
  
  if C == 1010:
    print('TLE')
  else:
    print(C)


if __name__ == '__main__':
  main()

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

using namespace std;

//const long long MAX = 100;
const long long MAX = 10000010;
long long cumsum[MAX] ;


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

    for(long long i=1; i< MAX; ++i){
        cumsum[i] = 1;
    }

    for(long long i=2; i<=10000010; ++i){
        for(long long j=1; j*i< MAX; ++j ){
            cumsum[i*j]++;
        }
    }

    long long ans = 0;

    for(long long i = 1; i <=N; ++i){
        ans += cumsum[i] * i;
    }

    cout << ans << endl;
}

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

#define INF 1e18
#define REP(i, n) for (int i=0; i<n; i++)
#define print(x) cout << x << endl
#define debug(x) cout << #x << " = "<< x << endl

const double PI=3.141592653589793238462643383279502884197169399375105820974944;

typedef long long ll;

using namespace std;

void solve() {
    int X, Y;
    cin >> X >> Y;

    print(X + Y/2);
}

signed main() {
    solve();
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
 
struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size, -1) { }
    bool unionSet(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }
    bool findSet(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};
 
 
int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int n,q; cin >> n >> q; 
    UnionFind uf(n+1);
    for (int i = 0; i < q;i++) {
int com,x,y; cin >> com >> x >> y;
if(com == 0){
uf.unionSet(x,y);
}
if(com == 1){
if(uf.findSet(x,y)){
cout << 1 << endl;
}else{
cout << 0 << endl;
}
}
    }
 
}

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

#define dump(...) do{print_vars(cout<<"# "<<#__VA_ARGS__<<'=',__VA_ARGS__);cout<<endl;}while(0)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vd=vector<double>;
using vvd=vector<vd>;
using vs=vector<string>;

void print_vars(ostream&){}
template<typename Car,typename... Cdr>
void print_vars(ostream& os,const Car& car,const Cdr&... cdr){
	print_vars(os<<car<<(sizeof...(cdr)?",":""),cdr...);
}

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}

template<int I,typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<int I,typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	os<<get<I>(t)<<(sizeof...(Cdr)?",":"");
	print_tuple<I+1,Cdr...>(os,t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<0,Args...>(os<<'(',t);
	return os<<')';
}

template<typename Ch,typename Tr,typename C>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

int main()
{
	#ifndef _GLIBCXX_DEBUG
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	constexpr char endl='\n';
	#endif

	for(int n;cin>>n&&n;){
		vi a(n);
		rep(i,n) cin>>a[i],a[i]--;

		int res=0;
		rep(i,n-1){
			if(a[i]==i){
				swap(a[i],a[i+1]);
				res++;
			}
		}
		if(a[n-1]==n-1){
			res++;
		}
		cout<<res<<endl;
	}
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <queue>
#include <vector>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define RREP(i, n) for (int i = n; 0 <= i; i--)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define RFOR(i, start, end) for (int i = start; end <= i; i--)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1'000'000'007
#define INF32 1'050'000'000
#define INF64 4'000'000'000'000'000'000
using ll = long long;
using namespace std;
template <class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template <class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }

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

    int N; cin >> N;
    int K; cin >> K;
    priority_queue<ll> kind[N];
    for (int i=0; i<N; ++i) {
        int t;
        ll d;
        cin >> t >> d;
        kind[t - 1].push(d);
    }

    priority_queue<ll> best, remain;
    for (int i = 0; i < N; ++i) {
        if (!kind[i].empty()) {
            best.push(kind[i].top());
            kind[i].pop();

            while (!kind[i].empty()) {
                remain.push(kind[i].top());
                kind[i].pop();
            }
        }
    }

    vector<ll> bsum = {0};
    while (!best.empty()) {
        bsum.push_back(bsum.back() + best.top());
        best.pop();
    }

    vector<ll> rsum = {0};
    while (!remain.empty()) {
        rsum.push_back(rsum.back() + remain.top());
        remain.pop();
    }

    ll ans = 0;
    for (ll x = 1; x <= K; ++x) {
        if (x >= bsum.size()) break;
        if (K - x >= rsum.size()) continue;
        ans = max(ans, bsum[x] + rsum[K - x] + x * x);
    }

    cout << ans << '\n';

    return 0;
}




Measured memory_bytes: 8820
#include<iostream>
#include<cassert>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<deque>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
typedef pair<int, int>P;
const int MOD = 1e9 + 7;
const int INF = 1e10;
const long double PI = (acos(-1));


signed main() {
	int N;
	double M;
	cin >> N >> M;
	vector<double>A(N);
	double sum = 0;
	rep(i, N) {
		cin >> A[i];
		sum += A[i];
	}
	sort(A.begin(), A.end());
	bool can = true;
	rep(i, M) {
		if (A[N - 1 - i] < sum / 4 / M)can = false;
	}
	if (can)cout << "Yes";
	else cout << "No";
}

Measured memory_bytes: 256
N, D = [int(i) for i in input().split()]
Positions = [[int(i) for i in input().split()] for j in range(N)]


def dist2(pos1, pos2):
    return sum([(p - q)**2 for p, q in zip(pos1, pos2)])


ans = 0
for i in range(N):
    for j in range(i + 1, N):
        dist = dist2(Positions[i], Positions[j])
        if int(dist**0.5)**2 == dist:
            ans += 1
print(ans)

Measured memory_bytes: 3188
# AGC079 D - Wall
h,w=map(int,input().split())
c=[list(map(int,input().split())) for i in range(10)]
a=[list(map(int,input().split())) for i in range(h)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j]=min(c[i][j],c[i][k]+c[k][j])

ans=0
for i in range(h):
    for j in range(w):
        if a[i][j]>=0:
            ans+=c[a[i][j]][1]
print(ans)



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

#define int long long 

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int a[maxn],n;
map<int,map<int,int> > f[20][20];

int dfs(int l,int r,int sl,int sr) {
    if(l==r-1) return 0;
    int &x=f[l][r][sl][sr];
    if(x) return x;x=1e18;
    for(int i=l+1;i<=r-1;i++)
        x=min(x,dfs(l,i,sl,sl+sr)+dfs(i,r,sl+sr,sr)+(sl+sr)*a[i]);
    return x;
}

signed main() {
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    write(dfs(1,n,1,1)+a[1]+a[n]);
    return 0;
}


Measured memory_bytes: 18812
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

basepoint=sum(B)
additional=0
for i in range(N-1):
    if A[i+1]==A[i]+1:
        additional += C[A[i]-1]
ans=basepoint+additional
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int maxN = 100 * 1000 + 9;
const double EPS = 1e-9;

ll w[2 * maxN];
int n, m;
int l[2 * maxN], r[2 * maxN];
vector<pair<int, ll> > g[maxN];


void read(){
  cin >> n >> m;
  for(int i = 0; i < m; i++){
    cin >> l[i] >> r[i] >> w[i];
    g[l[i]].push_back(make_pair(r[i], w[i]));
    g[r[i]].push_back(make_pair(l[i], -w[i]));
  }
}

ll d[maxN];

void dfs(int u){
  for(int i = 0, L = g[u].size(); i < L; i++){
    int v = g[u][i].first; ll w = g[u][i].second;
    if(d[v] == -INF){
      d[v] = d[u] + w;
      dfs(v);
    }
  }
}

void solv(){
  fill_n(d, maxN, -INF);
  for(int i = 1; i <= n; i++){
    if(d[i] == -INF){
      d[i] = 1;
      dfs(i);
    }
  }

  for(int i = 0; i < m; i++){
    if(d[r[i]] - d[l[i]] != w[i]){
      cout << "No\n";
      return;
    }
  }

  cout << "Yes\n";
}

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

  #ifdef DEBUG
    freopen("in.txt", "r", stdin);
  #endif

  read();
  solv();

  return 0;
}


Measured memory_bytes: 19584