akhauriyash/Code-Regression huggingface dataset:
import java.util.*; 

class Main{
public static void main(String[] args){
	Scanner sc=new Scanner(System.in);
        int k=sc.nextInt();
        long a=0;
		for(long c=1;c<=k;c++){
    		for(long d=1;d<=k;d++){
            for(long e=1;e<=k;e++){
            a+=gcd(c,gcd(d,e));
            }
            }
    	}
    
    	System.out.println(a);
    }
  private static long gcd(long a,long b){
   if(b==0){
   	return a;
   }
	return gcd(b, a%b);
}
}


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

int main(){

    string s;
    cin >> s;
    int res = 0;
    for(int i=0; i<s.length(); i++){
        if(s[i] == '1'){
            res ++;
        }
    }

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i, n) FOR(i,0,n)

int main(void){
    ll N;
    cin >> N;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];
    ll ans = 0;
    FOR(i,1,N){
        if(A[i-1] > A[i]){
            ans += A[i-1] - A[i];
            A[i] += A[i-1] - A[i];
        }
    }
    cout << ans << endl;

    return 0;
}

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

int main(){
	int N;
	long long M;
	cin >> N >> M;
	vector<int> A(N);
	for(auto &i:A)cin >> i;
	
	sort(A.begin(),A.end(),greater<int>());
	
	vector<long long> sum(N+1,0LL);
	for(int i=0;i<N;i++)sum[i+1]=sum[i]+A[i];
	
	vector<int> count(200001,0);	//count[x]:Ai>=xなるiの個数
	for(auto i:A)count[i]++;
	for(int i=99999;i>=0;i--)count[i]+=count[i+1];
	
	int ok=2,ng=200001;
	while(abs(ok-ng)>1){
		int mid=(ok+ng)/2;
		long long c=0;
		for(int i=0;i<N;i++)c+=count[max(0,mid-A[i])];
		if(c>=M)ok=mid;
		else ng=mid;
	}
	
	long long ans=0;
	long long used=0;
	for(int i=0;i<N;i++){
		int C=count[max(0,ok-A[i])];
		ans+=(long long)A[i]*C+sum[C];
		used+=C;
	}
	ans-=(long long)ok*(used-M);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2176
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <string>
#include <iostream>
#include <climits>
#include <list>
#include <queue>

using namespace std;

static const int INFTY = -1;

int H;
int A[101];
int NodeNum[101];
int IndexInA[100];


int parent(int i) {
	return i / 2;
}

int left(int i) {
	return 2 * i;
}

int right(int i) {
	return 2 * i + 1;
}

void minHeapify(int i) {
	int l = left(i);
	int r = right(i);
	int smallest = i;
	if (l <= H && A[l] < A[i]) {
		smallest = l;
	}
	if (r <= H && A[r] < A[smallest]) {
		smallest = r;
	}
	if (smallest != i) {
		int temp = A[i];
		A[i] = A[smallest];
		A[smallest] = temp;
		temp = NodeNum[i];
		NodeNum[i] = NodeNum[smallest];
		NodeNum[smallest] = temp;
		IndexInA[NodeNum[i]] = i;
		IndexInA[NodeNum[smallest]] = smallest;

		minHeapify(smallest);
	}
}

void insert(int d, int nodeNum) {
	int i = ++H;
	A[i] = d;
	NodeNum[i] = nodeNum;
	IndexInA[nodeNum] = i;
	int p = parent(i);
	while (i > 1 && A[p] > A[i]) {
		int temp = A[p];
		A[p] = A[i];
		A[i] = temp;
		temp = NodeNum[p];
		NodeNum[p] = NodeNum[i];
		NodeNum[i] = temp;
		IndexInA[NodeNum[p]] = p;
		IndexInA[NodeNum[i]] = i;
		i = p;
		p = parent(i);
	}
}

int heapExtractMinNodeNum() {
	int minNodeNum = NodeNum[1];
	A[1] = A[H];
	NodeNum[1] = NodeNum[H];
	IndexInA[NodeNum[1]] = 1;
	H--;
	minHeapify(1);

	return minNodeNum;
}

void decrese(int i, int value) {
	A[i] = value;
	int p = parent(i);
	while (i > 1 && A[p] > A[i]) {
		int temp = A[p];
		A[p] = A[i];
		A[i] = temp;
		temp = NodeNum[p];
		NodeNum[p] = NodeNum[i];
		NodeNum[i] = temp;
		IndexInA[NodeNum[p]] = p;
		IndexInA[NodeNum[i]] = i;
		i = p;
		p = parent(i);
	}
}

int main() {
	int Dist[100];
	int AdjacenceyList[100][100];
	int AdjacenceyWeightList[100][100];
	int Degree[100];
	int i, j;
	int N;
	int W;
	//int Deg;
	//int MinTotalWeight = 0;
	int u, v;
	int k;
	bool inT[100];

	cin >> N;

	//for (i = 0; i < N; i++) {
	//	inT[i] = false;
	//	Dist[i] = INFTY;
	//	Deg = -1;
	//	for (j = 0; j < N; j++) {
	//		cin >> W;
	//		if (W != -1) {
	//			AdjacenceyList[i][++Deg] = j;
	//			AdjacenceyWeightList[i][Deg] = W;
	//		}
	//	}
	//	Degree[i] = Deg + 1;
	//}

	for (i = 0; i < N; i++) {
		inT[i] = false;
		Dist[i] = INFTY;
		cin >> u >> k;
		Degree[u] = k;
		for (j = 0; j < k; j++) {
			cin >> AdjacenceyList[u][j] >> AdjacenceyWeightList[u][j];
		}
	}


	H = 0;
	u = 0;
	inT[u] = true;
	Dist[u] = 0;
	for (i = 1; i <= N - 1; i++) {
		for (j = 0; j < Degree[u]; j++) {
			v = AdjacenceyList[u][j];
			if (inT[v] == false) {
				W = AdjacenceyWeightList[u][j];
				if (Dist[v] == INFTY) {
					//Dist[v] = W;
					//insert(W, v);
					Dist[v] = Dist[u] + W;
					insert(Dist[v], v);
				}
				//else if (W < Dist[v]) {
				else if(W + Dist[u] < Dist[v]){
					//Dist[v] = W;
					//decrese(IndexInA[v], W);
					Dist[v] = W + Dist[u];
					decrese(IndexInA[v], Dist[v]);
				}
			}
		}

		int minNodeNum = heapExtractMinNodeNum();
		inT[minNodeNum] = true;
		//MinTotalWeight += Dist[minNodeNum];
		u = minNodeNum;

	}

	//printf("%d\n", MinTotalWeight);

	for (i = 0; i < N; i++) {
		printf("%d %d\n", i, Dist[i]);
	}

	return 0;
}

Measured memory_bytes: 1224
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n=scan.nextInt();
		int m=scan.nextInt();
		int a[][]=new int[n][m];
		int b[]=new int[m];
		int c[]=new int[n];

		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				a[i][j]=scan.nextInt();
			}
		}
		for(int i=0;i<m;i++) {
			b[i]=scan.nextInt();
		}

		for(int i=0;i<n;i++) {
			c[i]=0;
			for(int j=0;j<m;j++) {
				c[i]+=a[i][j]*b[j];
			}
			System.out.println(c[i]);
		}
		scan.close();
	}

}


Measured memory_bytes: 40876
#include<bits/stdc++.h>
using namespace std;
vector<int>x_move;
vector<int>y_move;
int pos_x[17000];
int pos_y[17000];
bool f_x(int make){
	for(int i=0; i<x_move.size(); i++){
		int move = x_move[i];
		vector<int>arr;
		for(int j=0; j<=16000; j++){	
			if(pos_x[j]==i+1) arr.push_back(j);
		}
		for(int j=0; j<arr.size(); j++){
			pos_x[arr[j]+move] = i+2;
			pos_x[arr[j]-move] = i+2;
		}
	}
	return (pos_x[make]==x_move.size()+1);
}
bool f_y(int make){
	for(int i=0; i<y_move.size(); i++){
		int move = y_move[i];
		vector<int>arr;
		for(int j=0; j<=16000; j++){
			if(pos_y[j]==i+1) arr.push_back(j);
		}
		for(int j=0; j<arr.size(); j++){
			pos_y[arr[j]+move] = i+2;
			pos_y[arr[j]-move] = i+2;
		}
	}
	return (pos_y[make]==y_move.size()+1);
}
int main(){
	
	string s;
	cin>>s;
	int x=0,y=0;
	int dx,dy;
	cin>>dx>>dy;
	bool x_dir = true;
	
	queue<char>q;
	for(int i=0; s[i]; i++) q.push(s[i]);
	while(!q.empty() && q.front()=='F'){
		q.pop();
		x++;
	}
	int counter = 0;
	while(!q.empty()){
		if(q.front()=='F') counter++;
		else{
			if(counter){
				if(x_dir) x_move.push_back(counter);
				else y_move.push_back(counter);
			}
			counter = 0;
			x_dir = !x_dir;
		}
		q.pop();
	}
	if(counter){
		if(x_dir) x_move.push_back(counter);
		else y_move.push_back(counter);
	}
	pos_x[8000+x] = 1;
	pos_y[8000] = 1;
	if(f_y(dy+8000) && f_x(dx+8000)) cout<<"Yes";
	else cout<<"No";
}

Measured memory_bytes: 3692
#include<cstdio>
#include<functional>
#include<algorithm>
using namespace std;
int main(void)
{
	int i,flg,n,y,n1,y1,a,b;
	scanf("%d %d",&n,&y);
	flg=0;
	y=y/1000;
	for(i=0;i<=2000;i++)	{
		n1=n-i;	y1=y-10*i;
		if(5*n1-y1>=0 && (5*n1-y1)%4==0 && y1-n1>=0 && (y1-n1)%4==0)	{
			flg=1;
			a=(5*n1-y1)/4;
			b=(y1-n1)/4;
			break;
		}
	}
	if(flg==1)	printf("%d %d %d\n",i,b,a);
	else printf("-1 -1 -1\n");
	return 0;
}

Measured memory_bytes: 128
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();
     int ar[]=new int[a+2];
      for(int i=0;i<b;i++){
       	int l=sc.nextInt();
        int r=sc.nextInt();
        ar[l]++;
        ar[r+1]--;
      }
      int cnt=0;
      for(int i=1;i<=a;i++){
       	ar[i]+=ar[i-1];
        if(ar[i]==b)
          cnt++;
      }
      System.out.println(cnt);
    }
}

Measured memory_bytes: 65240
package main

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

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024*1024), bufio.MaxScanTokenSize)
}

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

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

func main() {
	N := nextInt()
	S := make([]int, N)
	for i := 0; i < N; i++ {
		n := nextInt()
		S[i] = n
	}
	if IsAsc(S) {
		fmt.Println("YES")
		return
	}
	for i := 0; i < N-1; i++ {
		for j := i + 1; j < N; j++ {
			swp := swap(i, j, S)
			if IsAsc(swp) {
				fmt.Println("YES")
				return
			}
		}
	}
	fmt.Println("NO")
	return
}

func IsAsc(S []int) bool {
	for i := 0; i < len(S)-1; i++ {
		if S[i] > S[i+1] {
			return false
		}
	}
	return true
}

func swap(a, b int, S []int) []int {
	ret := make([]int, len(S))
	for i := 0; i < len(S); i++ {
		ret[i] = S[i]
		if i == a {
			ret[i] = S[b]
		} else if i == b {
			ret[i] = S[a]
		}
	}
	return ret
}


Measured memory_bytes: 2332
#include<stdio.h>
#include<stdlib.h>
typedef struct Node {
  struct Node *parent;
  struct Node *left;
  struct Node *right;
  int key;
} node;
void preOrder(node *);
void inOrder(node *);
void insert(int);
node *root;
int n;
int main() {
  int i, j, key;
  char command[7];
 
  scanf("%d", &n);
  for (i = 0; i < n; i++) {    
    scanf("%s", command);
    if ('i' == command[0]) {
      scanf("%d", &key);
      insert(key);
    } else {
      inOrder(root);
      printf("\n");
      preOrder(root);
      printf("\n"); 
    }
  }
  return 0;
}
void inOrder(node *u) {
  if (u == NULL) {
    return ;
  }
  if (u->left != NULL) inOrder(u->left);
  printf(" %d",u->key);
  if (u->right != NULL) inOrder(u->right);
  return ;
}
void preOrder(node *u) {
  if (u == NULL) {
    return ;
  }
  printf(" %d",u->key);
  if (u->left != NULL) preOrder(u->left);
  if (u->right != NULL) preOrder(u->right);
  return ;
}
void insert(int key) {
  node *y = NULL;
  node *x = root;
  node *z;
 
  z = (node*) malloc(sizeof(node));
  z->left = NULL;
  z->right = NULL;
  z->key = key;
 
  while (x != NULL) {
    y = x;
    if (key < x->key) {
      x = x->left;
    } else {
      x = x->right;
    }
  }
  
  z->parent = y;
  if ( y==NULL ) {
    root = z;
  } else if (z->key < y->key) {
    y->left = z;
  } else {
    y->right = z;
  }
  return ;
}



Measured memory_bytes: 25132
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctype.h>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <unistd.h>
using namespace std;

#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i, n) REP(i, 1, n)
#define lengthof(x) (sizeof(x) / sizeof(*(x)))
#define FILL(ptr, value) FILL_((ptr), sizeof(ptr)/sizeof(value), (value))
template <typename T>
void FILL_(void * ptr, size_t size, T value){
  std::fill((T*)ptr, (T*)ptr+size, value);
}
//4方向ベクトル→↑←↓
const int dx[] ={1,0,-1,0};
const int dy[] ={0,-1,0,1};
int w,h;
char board[55][55];
int WS,BS;
bool white[55][55];
bool black[55][55];
void dfsw(int y,int x){
  if(white[y][x]||board[y][x] != '.')
    return;
  white[y][x] =true;
  for(int k = 0;k < 4;k++){
    int nx = x +dx[k];
    int ny = y +dy[k];
    if(nx <=0||nx >w||ny <=0||ny >h)
      continue;
    else
      dfsw(ny,nx); 
  }
}
void dfsb(int y,int x){
  if(black[y][x]||board[y][x] != '.')
    return;
  black[y][x] =true;
  for(int k = 0;k < 4;k++){
    int nx = x +dx[k];
    int ny = y +dy[k];
    if(nx <=0||nx >w||ny <=0||ny >h)
      continue;
    else
      dfsb(ny,nx); 
  }
}
int main()
{
  while(cin>>w>>h,w||h){
    for(int i = 1;i <=h;i++){
      for(int j = 1;j <=w;j++){
	cin>>board[i][j];
	white[i][j] = false;
	black[i][j] = false;
      }
    }
    for(int i = 1;i <=h;i++){
      for(int j = 1;j <=w;j++){
	if(board[i][j] =='W'){
	  for(int k = 0;k < 4;k++){
	    int nx = j +dx[k];
	    int ny = i +dy[k];
	    if(nx <=0||nx >w||ny <=0||ny >h)
	      continue;
	    else
	      dfsw(ny,nx);
	}
      }
	if(board[i][j] =='B'){
	  for(int k = 0;k < 4;k++){
	    int nx = j +dx[k];
	    int ny = i +dy[k];
	    if(nx <=0||nx >w||ny <=0||ny >h)
	      continue;
	    else
	      dfsb(ny,nx);
	  }
	}
      }
    }
    WS = 0;
    BS = 0;
    for(int i = 1;i <=h;i++){
      for(int j = 1;j <=w;j++){
	if(board[i][j] !='.'||(white[i][j]&&black[i][j])||
	   (!white[i][j]&&!black[i][j]))
	  continue;
	if(white[i][j])
	  WS++;
	else
	  BS++;
      }
    }
    cout <<BS<<" "<<WS<<endl;
  }
  usleep(500000);
  return 0;
}

Measured memory_bytes: 1208
#include <iostream>  
#include <algorithm>  
#include <functional>  
#include <vector>  
#include <map>
#include <string>
#include <queue>
#include <deque> 
#include <cmath>
#include <math.h>
using namespace std;
	double pi=acos(-1);
	#define mod 1000000007
	long long int modexp(long long int a, int b){ 
	long long int t=1;
	while( b != 0){
		if( b%2 == 1)
			t = (t*a)%mod ;
		a = (a*a)%mod;
		b /= 2;
	}
	return t%mod;
}
int main(){
	//freopen("input.txt", "r", stdin);   
 	//freopen("output.txt", "w", stdout);
 	int n=1,m=1;
 	scanf("%d %d",&n,&m);
 	if(n>m){
 		int te=m;
 		m=n;
 		n=te;
 	}
 	long long int ans=1;
 	long long int f=2;
 	int i;
 	for(i=1;i<=n;i++) ans=(ans*i)%mod;
 	long long int ans2=1;
 	for(i=1;i<=m;i++) ans2=(ans2*i)%mod;
 	ans2=(ans*m)%mod;
 	if(m-n>=2) printf("0\n");
 	else if(m-n==1) printf("%lld\n",(ans*ans2%mod)%mod );
 	else if(m==n) printf("%lld\n", (f*(ans*ans)%mod)%mod );
	return 0;
}

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

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

using ll = long long int;
const ll MOD = 1e9 + 7;

void dfs(int N, std::string s, char maxch) {
  if(s.length() == N) {
    std::cout << s << '\n';
    return;
  }

  for(char c = 'a'; c <= maxch; ++c) {
    char new_maxch = std::max(char(c + 1), maxch);
    dfs(N, s + c, new_maxch);
  }
}

int main() {
  int N;
  std::cin >> N;
  dfs(N, "", 'a');
}


Measured memory_bytes: 1536
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define vvll vector<vll>
#define all(v) v.begin(),v.end()
#define itr(r,v) for(auto r=v.begin();r!=v.end();r++)
#define W while
#define FOR(i,n) for(ll i=0;i<n;i++)
#define ffor(i,a,b) for(ll i=a;i<=b;i++)
#define rfor(i,a,b) for(ll i=a;i>=b;i--)
#define space cout<<"\n\n";
#define endl "\n"
#define pqmx priority_queue<ll>
#define pqmn priority_queue<ll,vll,greater<ll>>
#define fps(x,y) fixed<<setprecision(y)<<x
#define merg(a,b,c) set_union(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.begin()))
#define set_ar(arr,v) memset(arr,v,sizeof(arr))
#define ctime auto start = high_resolution_clock::now()
#define etime auto stop = high_resolution_clock::now()
#define ptime auto z1z = duration_cast<microseconds>(stop-start); cout<<"Time elapsed : "<<z1z.count()<<" microseconds\n"
#define go_t ll testcases; cin>>testcases; while(testcases--)
#define dbg1(x)             cout <<#x<<": "<<x<<'\n';
#define dbg2(x, y)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<'\n';
#define dbg3(x, y, z)       cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<'\n';
#define dbg4(a, b, c, d)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<'\n';
#define dbg5(a, b, c, d, e) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<<": "<<e<<'\n';
using namespace std;
using namespace std::chrono;

const ll MOD = 1e9 + 7;
const ll N = 1e6 + 6;
const ll maxN = 2e5 + 5;
const ll MAX_SIZE = 1e8 + 8;
const double PI = 3.14159265359;

ll powerM(ll x, ll y, ll M = MOD) // default argument
{ll v = 1; x = x % M; while (y > 0) {if (y & 1)v = (v * x) % M; y = y >> 1; x = (x * x) % M;} return v;}

ll power(ll x, ll y)
{ll v = 1; while (y > 0) {if (y & 1)v = v * x; y = y >> 1; x = x * x;} return v;}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input1.txt", "r", stdin);
	freopen("output1.txt", "w", stdout);
#endif
	// WHILE(!(SUCCEED == TRY()));
	// BEFORE WRITING MAKE SURE YOU HAVE ANALYSED THE CONSTRAINTS
	// AND THINK THROUGH THE LOGIC ONCE MORE
	FIO
	ll n; cin >> n;
	ll ans = n + (n * n) + (n * n * n);
	cout << ans;
	return 0;
}


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

double X1, X2, X3, Y1, Y2, Y3; //coor
double r1, r2, r3;             //radii
double e1, e2, e3;             //edge
double a1, a2, a3;             //angle
double r;

void calc()
{
	e1 = sqrt(pow(X2 - X3, 2) + pow(Y2 - Y3, 2));
	e2 = sqrt(pow(X1 - X3, 2) + pow(Y1 - Y3, 2));
	e3 = sqrt(pow(X1 - X2, 2) + pow(Y1 - Y2, 2));
	a1 = acos((e2 * e2 + e3 * e3 - e1 * e1) / (2 * e2 * e3));
	a2 = acos((e3 * e3 + e1 * e1 - e2 * e2) / (2 * e1 * e3));
	a3 = acos((e1 * e1 + e2 * e2 - e3 * e3) / (2 * e1 * e2));
	r = e2 * e3 * sin(a1) / (e1 + e2 + e3);
	r1 = r * ((1 + tan(a2 / 4)) * (1 + tan(a3 / 4))) / (2 * (1 + tan(a1 / 4)));
	r2 = r * ((1 + tan(a1 / 4)) * (1 + tan(a3 / 4))) / (2 * (1 + tan(a2 / 4)));
	r3 = r * ((1 + tan(a1 / 4)) * (1 + tan(a2 / 4))) / (2 * (1 + tan(a3 / 4)));
}

int main()
{
	while (1)
	{
		scanf("%lf %lf %lf %lf %lf %lf", &X1, &Y1, &X2, &Y2, &X3, &Y3);
		if (X1 == 0 && X2 == 0 && X3 == 0 && Y1 == 0 && Y2 == 0 && Y3 == 0)
			break;
		calc();
		printf("%lf %lf %lf\n", r1, r2, r3);
	}
}


Measured memory_bytes: 2132
#include <stdio.h>

int ans[100001];

int min(int a, int b) {
  return a < b ? a : b;
}

void build_table(int a) {
  for (int i = 1; i <= a; i++) {
    ans[i] = 1000000;

    for (int x = 1; x <= i; x *= 9) {
      ans[i] = min(ans[i], ans[i - x] + 1);
    }

    for (int x = 1; x <= i; x *= 6) {
      ans[i] = min(ans[i], ans[i - x] + 1);
    }
  }
}

int main() {
  int a;
  scanf("%d", &a);
  build_table(a);
  printf("%d\n", ans[a]);
  return 0;
}


Measured memory_bytes: 512
#include<iostream>

using namespace std;

int main(){
  int s; cin >> s;
  if( s == 1 || s == 2){cout << 4; return 0;}
  else { 
           
  
  int ans = 1; int cnt = 0;//2回目の4が出たらそこで終了
  while( cnt < 2){
    if( s == 4){ s /=2; cnt++; ans++;}
    else if( s % 2 == 0){ s /= 2; ans++;}
    else{ s = 3 * s + 1;ans++;}}
  
  cout << ans - 1 << endl; //2回目の4が出てきた後、ansをまた一つ増やしてしまうので、補正
  
  return 0;}
}

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

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

  int a,b;cin>>a>>b;
  if(a>8 || b > 8){
    cout<<":("<<endl;
  }else{
    cout<<"Yay!"<<endl;

  }

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cctype>
using namespace std;
int main(){
  string s;
  cin >> s;
  int cnt=0;
  int b=0;
  if(s[0]=='A'){
    for(int i=2;i<s.size()-1;i++){
      if(s[i]=='C') cnt++;
    }
    if(cnt==1){
      for(int i=0;i<s.size();i++){
	if(isupper(s[i])) b++;
      }
      if(b==2) cout << "AC" << "\n";
      else cout << "WA" << "\n";
    }
    else cout << "WA" << "\n";
  }
  else cout << "WA" << "\n";

  
  return 0;
}
	  


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

using namespace std;

using ll= long long;

#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);


void solve(){
	int n,m;
	cin>>n>>m;
	int h[n],bad[n];
	for(int i=0;i<n;i++){
		cin>>h[i];
		bad[i]=0;
	}
	int good = 0;
	int a,b;
	for(int i=0;i<m;i++){
		cin>>a>>b;
		a--;b--;
		if(h[a] >h[b]){
			bad[b]=1;
		}else if(h[a]==h[b]){
			bad[a]=1;
			bad[b]=1;
		}else{
			bad[a]=1;
		}	
	}
	for(int i=0;i<n;i++){
		if(!bad[i])good++;
	}
	cout<<good<<endl;
}

int32_t main(){
	IOS

	int t;
	t=1;
	while(t--){
		solve();
	}
	return 0;
}

/*
   check for overflows int long long
   correct size of array
*/

Measured memory_bytes: 4432
// GCD on Blackboard - atcoder.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int GCD(int x , int y) {
	if (y > x)
		swap(x,y);

	int c = x % y;

	while (c != 0) {
		x = y;
		y = c;
		c = x % y;
	}
	return y;

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

	vector <int> elements(n);
	vector<int> prefix(n);
	vector<int> suffix(n);
	for (int i = 0; i < n; i++) {
		cin >> elements[i];
	}
	prefix[0] = elements[0];
	for (int i = 1; i < n; i++) {
		prefix[i] = GCD(prefix[i - 1], elements[i]);
	}
	suffix[n - 1] = elements[n - 1];
	for (int i = n-2; i >= 0; i--) {
		suffix[i] = GCD(suffix[i + 1], elements[i]);
	}

	int m = max(prefix[n-2] ,suffix[1]);
	for (int i = 1; i < n - 1; i++) {
		m = max(m,GCD(prefix[i-1] , suffix[i+1]));
	}

	cout << m;
}


Measured memory_bytes: 1408
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String {
            bytes
                .by_ref()
                .map(|r| r.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
    input!{
        n: usize,
        a: [usize1; n],
        b: [usize; n],
        c: [usize; n - 1],
    }
    let mut ans: usize = b.iter().sum();
    for i in 0..n - 1 {
        if a[i] + 1 == a[i + 1] {
            ans += c[a[i]];
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
N = gets.to_i
As = gets.split.map(&:to_i)

require 'prime'

ul = 10**6
ps = Prime.each(ul).to_a
h = As.tally; h.default = 0
s = ps.map{|p| p.step(ul, p).inject(0){|r, q| r + h[q]}}.max
puts (s <= 1 ? 'pairwise' : s == N ? 'not' : 'setwise') + ' coprime'

Measured memory_bytes: 147560
#include <iostream>
#include <vector>

class Combination {
private:
  const int max;
  const int mod;
  std::vector<long long> fac;  // fac[k] = k! in Fp
  std::vector<long long> finv; // finv[k] = (k!)^-1 in Fp
public:
  Combination(int max, int mod)
      : max(max), mod(mod), fac(max, -1), finv(max, -1) {
    std::vector<long long> inv(max, -1); // inv[k] = k^-1 in Fp
    fac[0] = fac[1] = 1;
    inv[1] = 1;
    finv[0] = finv[1] = 1;
    for (int i = 2; i < max; ++i) {
      fac[i] = fac[i - 1] * i % mod;
      inv[i] = mod - inv[mod % i] * (mod / i) % mod;
      finv[i] = finv[i - 1] * inv[i] % mod;
    }
  }
  long long operator()(int n, int k) const {
    if (n < k || n < 0 || k < 0)
      return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
  }
};

int main() {
  int n, k;
  std::cin >> n >> k;

  const int MAX = 510000;
  const int MOD = 1000000007;
  Combination comb(MAX, MOD);

  long long res = 0;
  for (int i = 0; i <= std::min(n, k); ++i)
    res = (res + comb(n, i) * comb(n - 1, n - i - 1) % MOD) % MOD;

  std::cout << res << std::endl;
}


Measured memory_bytes: 12160
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
typedef long long ll;
int main()
{
	fast;
	char st[100];
	int i,l;
	cin >> st; int flag = 0;
	///cout << st;

	l = strlen(st);
	int mid = (l-1)/2;
	int cid = (l+1)/2;

	int j,k;

	if(l%2!=0)
	{
		for(i=0; i<l; i++)
		{
			if(st[i] != st[l-i-1])
			{
				flag = 1; break;
			}
		}
		for(j=0; j<mid; j++)
		{
			if(st[j] != st[mid-j-1])
			{
				flag = 1; break;
			}
		}
		for(k=cid,i=0; k<l; k++,i++)
		{
			if(st[k] != st[l-i-1])
			{
				flag = 1; break;
			}
		}

	}
	if(flag == 0) cout << "Yes" << endl;
	else cout<< "No" << endl;
	return 0;
}


Measured memory_bytes: 256
a = gets.to_i
b = gets.split.map(&:to_i)
c = 0
d = 0
for i in 0..30
  d = 0
  for j in 0..(a - 1)
    if b[j] % 2 == 0
     d = 1
     b[j] = b[j] / 2
    else
     b[j] =1
     puts c
     exit
    end
    #puts b[j]
    #puts "#{j}です"
  end
 # puts d
  #puts "dd"
  if d == 1
    c = c + 1
    #puts c
  end
  i = i
end
#puts a
#puts b
puts c

Measured memory_bytes: 1788
fun main(args: Array<String>) {
    val x = readInt()
    val ans = when (x) {
        in 400..599 -> 8
        in 600..799 -> 7
        in 800..999 -> 6
        in 1000..1199 -> 5
        in 1200..1399 -> 4
        in 1400..1599 -> 3
        in 1600..1799 -> 2
        in 1800..1999 -> 1
        else -> 0
    }
    println(ans)
}

// Tools
fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()

Measured memory_bytes: 34536
package main

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

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}
func fSum(a []float64) float64 {
	x := 0.
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	s := Scan()
	a, ab, abc, p := 0, 0, 0, 1
	for _, r := range s {
		if string(r) == "A" {
			a += p
		} else if string(r) == "B" {
			ab += a
		} else if string(r) == "C" {
			abc += ab
		} else {
			abc = abc*3 + ab
			ab = ab*3 + a
			a = a*3 + p
			p *= 3
			p %= mod
		}
		a %= mod
		ab %= mod
		abc %= mod
	}
	fmt.Println(abc)
}
func repeatPow(x, y, d int) int {
	if y == 0 {
		return 1
	} else if y == 1 {
		return x
	} else {
		z := repeatPow(x, y/2, d)
		if y%2 == 0 {
			return z * z % d
		} else {
			return z * z % d * x % d
		}
	}
}


Measured memory_bytes: 2156
import math
# 基本データのインプット
x1, y1, x2, y2 = [float(i) for i in input().split()]
# print(x1)
# print(y2)

# 直角三角形の斜辺を求める計算式 X の差分の2乗　＋　y の差分の　2乗　を　平方根にする
temp = ((x2 - x1) ** 2) + ((y2 - y1) ** 2)
shahen = math.sqrt(temp)

print(shahen)


Measured memory_bytes: 5664
#include <iostream>
#include <set>
#include <vector>
#define rep(S, L) for (int i = S; i < L; ++i)
using namespace std;

int main() {
  int n;
  string w[100] = {};
  set<string> st;

  cin >> n;
  bool ok = true;
  for (int i = 0; i < n; ++i) {
    cin >> w[i];

    if (i == 0) {
      st.insert(w[i]);
      continue;
    }

    string p = w[i - 1];
    if (p[p.size() - 1] != w[i][0]) {
      ok = false;
      break;
    }

    set<string>::iterator it = st.find(w[i]);
    if (it != st.end()) {
      ok = false;
      break;
    }

    st.insert(w[i]);
  }
  if (ok) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 3132
import java.util.*;

public class Main {
    static long MOD = 1000000007;
    
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        long[] array = new long[n];
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }
        n--;
        long[] x = new long[n];
        for (int i = 0; i < n; i++) {
            x[i] = array[i+1] - array[i];
        }
        
        array = new long[m];
        for (int i = 0; i < m; i++) {
            array[i] = sc.nextInt();
        }
        m--;
        long[] y = new long[m];
        for (int i = 0; i < m; i++) {
            y[i] = array[i+1] - array[i];
        }
        
        long ans_x = f(x);
        long ans_y = f(y);
        long ans = (ans_x * ans_y) % MOD;
        System.out.println(ans);
    }
    
    public static long f(long[] x) {
        int n = x.length;
        long[] sumx = new long[n+1];
        for (int i = 0; i < n; i++) {
            sumx[i+1] = sumx[i] + x[i];
            sumx[i+1] %= MOD;
        }
        // System.out.println(Arrays.toString(sumx));
        long sum_x = 0;
        for (long num : sumx) {
            sum_x += num;
            sum_x %= MOD;
        }
        
        long ans_x = 0;
        for (int i = 0; i < n; i++) {
            ans_x += sum_x;
            ans_x %= MOD;
            
            sum_x -= x[i] * (n-i);
            sum_x %= MOD;
            if (sum_x < 0) sum_x += MOD;
        }
        // System.out.println(ans_x);
        
        return ans_x;
    }
}


Measured memory_bytes: 65436
n, k = map(int, input().split())
mod = 10 ** 9 + 7

cum = [0] * (n + 2)
cum[1] = 1
for i in range(2, n + 2):
    cum[i] = i + cum[i - 1]

ans = 0
for j in range(k, n + 2):
    small = cum[j]
    big = cum[n + 1] - cum[n - j + 1]
    ans += big - small + 1
    ans %= mod

print(ans % mod)


Measured memory_bytes: 19040
module RegExp : sig
  type t
  val empty_set : t
  val empty_str : t
  val char : Char.t -> t
  val app : t -> t -> t
  val union : t -> t -> t
  val star : t -> t

  val matches : t -> Char.t list -> bool
end = struct
  type t =
    { sort : sort;
      is_nullable : bool;
      derive : char -> t }
  and sort =
    | EmptySet
    | EmptyStr
    | Star
    | Other

  let rec empty_set =
    { sort = EmptySet;
      is_nullable = false;
      derive = fun _ -> empty_set }

  let empty_str =
    { sort = EmptyStr;
      is_nullable = true;
      derive = fun _ -> empty_set }

  let char c =
    { sort = Other;
      is_nullable = false;
      derive = fun c' -> if c = c' then empty_str else empty_set }

  let rec union re1 re2 =
    match re1, re2 with
    | { sort = EmptySet }, _ -> re2
    | _, { sort = EmptySet } -> re1
    | _, _ ->
        { sort = Other;
          is_nullable = re1.is_nullable || re2.is_nullable;
          derive = fun c -> union (re1.derive c) (re2.derive c) }

  let rec app re1 re2 =
    match re1, re2 with
    | { sort = EmptySet }, _ -> empty_set
    | _, { sort = EmptySet } -> empty_set
    | { sort = EmptyStr }, _ -> re2
    | _, { sort = EmptyStr } -> re1
    | _, _ ->
        { sort = Other;
          is_nullable = re1.is_nullable && re2.is_nullable;
          derive = fun c ->
            union
              (if re1.is_nullable then re2.derive c else empty_set)
              (app (re1.derive c) re2) }

  let star = function
    | { sort = EmptySet }
    | { sort = EmptyStr } -> empty_str
    | { sort = Star } as re -> re
    | re0 ->
        let rec re =
          { sort = Star;
            is_nullable = true;
            derive = fun c -> app (re0.derive c) re } in re

  let matches re s =
    (List.fold_left (fun re -> re.derive) re s).is_nullable
end

let () =
  let s = read_line () in
  print_endline @@
  if
    let open RegExp in
    matches
      (* ((dream(er)?)|(erase(r)?))* *)
      (star @@
        union
          (app (char 'd') @@ app (char 'r') @@ app (char 'e') @@ app (char 'a') @@ app (char 'm') @@
            union empty_str @@ app (char 'e') @@ char 'r')
          (app (char 'e') @@ app (char 'r') @@ app (char 'a') @@ app (char 's') @@ app (char 'e') @@
            (union empty_str @@ char 'r'))) @@
      Array.to_list @@ Array.init (String.length s) (String.get s)
  then "YES"
  else "NO"


Measured memory_bytes: 6400
double n,p[333][333][333];
c[4];
double f(i,j,k,I){I=i+j+k;return~i&~j&~k?p[i][j][k]?:(p[i][j][k]=(i*f(i-1,j,k)+j*f(i+1,j-1,k)+k*f(i,j+1,k-1)+n)/I):0;}
main(a)
{
	for(***p=1;~scanf("%d",&a);)!n?n=a:c[a]++;
	printf("%.9f",f(c[1],c[2],c[3])-1);
}

Measured memory_bytes: 260096
#include <bits/stdc++.h>
using namespace std;
#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 ALL(v) v.begin(), v.end()
#define downque(que) priority_queue<ll> que;
#define upque(que) priority_queue<ll, vector<int>, greater<int>> que;
typedef long long ll;
typedef vector<vector<int>> Matrix;
const int MOD = 1e9 + 7;

//calculate distance between an point to another point
double calc_dis(double x1, double y1, double x2, double y2)
{
    double dis = pow(x1 - x2, 2.0) + pow(y1 - y2, 2.0);
    dis = pow(dis, 0.5);
    return dis;
}

int main(void)
{
    int n, count = 0;
    double all_dis = 0;
    cin >> n;

    //xy retains coordinates of points
    vector<vector<double>> xy(n, vector<double>(2));
    vector<int> array(n);

    REP(i, n)
    {
        array[i] = i;
        cin >> xy[i][0] >> xy[i][1];
    }

    do
    {
        REP(i, n - 1)
        {
            //add distance between town[array[i]] and town[array[i+1]] to all_dis
            all_dis += calc_dis(xy[array[i]][0], xy[array[i]][1], xy[array[i + 1]][0], xy[array[i + 1]][1]);
        }
        count++;
    } while (next_permutation(array.begin(), array.end()));

    printf("%.8lf\n", all_dis / count);
    return 0;
}


Measured memory_bytes: 4224
#include <array>
#include <cstdint>
#include <iostream>

using namespace std;

int32_t main() {
  while (true) {
    uint32_t n;
    cin >> n;

    if (n == 0) break;

    array<char, 27> arr;
    for (uint32_t i = 0; i < arr.size(); i++) {
      arr[i] = 0;
    }

    uint32_t top = 26;
    uint32_t second = 26;
    int32_t decided = -1;
    for (int32_t i = 0; i < n; i++) {
      char c;
      cin >> c;
      uint32_t index = c - 'A';
      arr[index]++;
      if (arr[top] < arr[index]) {
        if (top != index) {
          second = top;
        }
        top = index;
      } else if (top != index && arr[second] < arr[index]) {
        second = index;
      }

      if (decided < 0 && arr[second] + n - i - 1 < arr[top]) {
        decided = i;
      }
    }

    if (decided == -1) {
      cout << "TIE" << endl;
    } else {
      cout << (char)(top + 'A') << " " << decided + 1 << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 3088
// Aizu Vol-5 0513: Shuffle The Cards
// 2017.8.30 bal4u@uu

#include <stdio.h>

int a[202], b[202], c[202];

int main()
{
	int n, m, k;
	int i, j;

	scanf("%d", &n); n *= 2;
	for (i = 1; i <= n; i++) c[i] = i;
	scanf("%d", &m); while (m-- > 0) {
		scanf("%d", &k);
		if (k == 0) {
			for (i = 1; i <= n/2; i++)    a[i] = c[i];
			for (j = 1; i <= n; j++, i++) b[j] = c[i];
			for (k = i = j = 1; k <= n; i++, j++) c[k++] = a[i], c[k++] = b[i];
		} else {	// cut
			for (i = 1; i <= k; i++)      a[i] = c[i];
			for (j = 1; i <= n; j++, i++) b[j] = c[i];
			for (i = 1; i <= n - k; i++)  c[i] = b[i];
			for (j = 1; i <= n; j++, i++) c[i] = a[j];
		}
	}
	for (i = 1; i <= n; i++) printf("%d\n", c[i]);
	return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

#define endl            "\n"
#define forn(i,x,n)     for(int i=x; i<n; i++)
#define forit(it, m)    for(decltype(m)::iterator it = m.begin(); it!=m.end(); ++it)
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());


void zeus()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

int ans[10001] = {0};

int32_t main() {

    zeus();

    int n; cin >> n;

    forn(i, 1, 101) {
        forn(j, 1, 101) {
            forn(k, 1, 101) {
                int x = i * i + j * j + k * k + i * j + j * k + k * i;
                if (x <= 10000) {
                    ans[x]++;
                }
            }
        }
    }

    forn(i, 1, n + 1) {
        cout << ans[i] << endl;
    }

}

Measured memory_bytes: 3728
//#include <bits/stdc++.h>
#include "bits/stdc++.h"
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> VI;
typedef vector<VI> VVI;//例: VVI dp(10, vector<int>(10, INF);
typedef priority_queue<int, vector<int>, less<int> > QUE_int;
const int INF = pow(10, 5) + 1;//+1しないとREになる(out of rangeになるんかな?? )

vector<int> dx = { -1, 0, 1, 0, -1, -1, 1, 1 };
vector<int> dy = { 0, -1, 0, 1, -1, 1, -1, 1 };

int main(void) {
	int N, M;
	cin >> N >> M;
	vector<P> 	wish(M);
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		wish[i] = P(b, a);
	}
	sort(wish.begin(), wish.end());
	vector<bool> bridge(N - 1, true);

	int ans = 0;
	for (int i = 0; i < M; i++) {
		int b = wish[i].first;
		int a = wish[i].second;
		bool is_connected = true;
		for (int j = a; j < b; j++) {
			if (bridge[j] == false) {
				is_connected = false;
				break;
			}
		}
		if (is_connected == false) continue;
		bridge[b-1] = false;
		ans++;
	}

	cout << ans << endl;
}


Measured memory_bytes: 1024
program cc
  implicit none
  integer :: s,flag1,flag2
  flag1 = 0
  flag2 = 0
  read *, s
  if (0<mod(s,100) .and. mod(s,100)<13) flag1 = 1
  if (0<s/100 .and. s/100<13) flag2 = 1
  if (flag1 == 1 .and. flag2 == 1) then
    print '(a)', "AMBIGUOUS"
  else if (flag1 == 1) then
    print '(a)', "YYMM"
  else if (flag2 == 1) then
    print '(a)', "MMYY"
  else
    print '(a)', "NA"
  end if
  stop
end program cc


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

#define MIN_INT -2147483648
#define MAX_INT 2147483647
#define MIN_LONG -9223372036854775808L
#define MAX_LONG 9223372036854775807L

#define long long long int

using namespace std;

// @author: pashka

int main() {
    ios::sync_with_stdio(false);

    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if (i % 2 == 0 && s[i] == 'L' || i % 2 == 1 && s[i] == 'R') {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";

    return 0;
}

Measured memory_bytes: 256
# include<bits/stdc++.h>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-8
# define MOD 1000000007
# define INF 100000000
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(register int i=a; i<=n; ++i)
# define FDR(i,a,n) for(register int i=a; i>=n; --i)
# define bug puts("H");
# define lch p<<1,l,mid
# define rch p<<1|1,mid+1,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
inline char nc(){
    static char buf[1000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int Scan(){
    char ch=nc();int sum=0, f=1;
    if (ch=='-') f=-1, ch=nc();
    while(!(ch>='0'&&ch<='9'))ch=nc();
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
    return sum*f;
}
const int N=100005;

char s[N];

int main ()
{
    scanf("%s",s+1);
    int len=strlen(s+1);
    if (len&1) {
        int ans=len/2+1;
        FOR(i,1,len-len/2-1) {
            if (s[i+len/2+1]==s[len/2+1]&&s[len/2+1-i]==s[len/2+1]) ++ans;
            else break;
        }
        printf("%d\n",ans);
    }
    else {
        int ans=len/2;
        FOR(i,1,len-len/2) {
            if (s[len/2+i]==s[len/2-i+1]&&s[len/2+i]==s[len/2+i-1]) ++ans;
            else break;
        }
        printf("%d\n",ans);
    }
    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define For(i,x,y) for (register int i=(x);i<=(y);i++)
#define FOR(i,x,y) for (register int i=(x);i<(y);i++)
#define Dow(i,x,y) for (register int i=(x);i>=(y);i--)
#define Debug(v) for (auto i:v) printf("%lld ",i);puts("")
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ep emplace_back
#define siz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define fil(a,b) memset((a),(b),sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pa;
typedef pair<ll,ll> PA;
typedef vector<int> poly;
inline ll read(){
    ll x=0,f=1;char c=getchar();
    while ((c<'0'||c>'9')&&(c!='-')) c=getchar();
    if (c=='-') f=-1,c=getchar();
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}

const int N = 2e5+10;
int n,cnt,T,c[N],cntc,cntd;
pa d[N];
ll dp[N][50];

inline ll calc(pa a,pa b){
	return 1ll*a.se*b.fi+b.se+b.fi;
}

int main(){
	n=read(),T=read();
	For(i,1,n){
		int x=read(),y=read();
		if (x==0) c[++cntc]=y;
			else d[++cntd]=mp(x+1,y);
	}
	sort(c+1,c+1+cntc),sort(d+1,d+1+cntd,[=](pa a,pa b){
		return calc(a,b)<calc(b,a);
	});
	For(i,1,30) dp[0][i]=-1;
	For(i,1,cntd){
		dp[i][0]=0;
		For(j,1,30){
			dp[i][j]=dp[i-1][j];
			if (dp[i-1][j-1]!=-1){
				ll tmp=1ll*(dp[i-1][j-1]+1)*d[i].fi+d[i].se;
				if (tmp>T) continue;
				if (dp[i][j]==-1) dp[i][j]=tmp;
					else dp[i][j]=min(dp[i][j],tmp);
			}
		}
	}
	//For(j,1,30) if (dp[cntd][j]!=-1) printf("%d %lld\n",j,dp[cntd][j]);
	int ans=0;
	ll s=0;
	For(i,0,cntc){
		s+=c[i];
		if (s+i>T) break;
		ans=max(ans,i);
		For(j,1,30) if (dp[cntd][j]!=-1){
			if (dp[cntd][j]+s+i<=T) ans=max(ans,i+j);
		}
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 83400
#include<bits/stdc++.h>
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define lli long long int
#define rep(i,n) for(lli i=0; i<n; i++)
#define loop(i, j, n) for(lli i=j; i<n; i++)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
constexpr int INF  = 0x3f3f3f3f;
const long long mod=1e9+7;
//Function
lli combi(lli n, lli r)
{
	if(r==0 || r==n) return 1;
	else return combi(n-1,r) + combi(n-1,r-1);
}
lli sigma1(lli n){return n*(n+1)/2;}
lli sigma2(lli s, lli n){return sigma1(n) - sigma1(s -1);}
using namespace std;
// }}} End Header

int main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << Min(a, b)+Min(c, d) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    int N;
    cin >> N;
    int d = 1000;
    int p = (N + d - 1) / d;
    cout << d * p - N << '\n';
}


Measured memory_bytes: 3624
import java.io.*;
import java.util.*;

public class Main {

	final static long MOD = 1000000007L;
	public static String[] Ws = null;
	public static int wsIndx = 0;
	public static BufferedReader in = null;
	public static ArrayList<int[]> list = new ArrayList<>();
	public static void main(String[] args) throws Exception {

		int N = nextInt();
		int[] a = nextInts();
		int sum=0;
		for(int i=0;i<N;i++){
			sum+=a[i];
		}
		int ave=sum/N;
		long ans = Integer.MAX_VALUE;
		for(int x=ave-1;x<=ave+1;x++){
			long tmp=0;
			for(int i=0;i<N;i++){
				tmp+=(a[i]-x)*(a[i]-x);
			}
			ans=Math.min(ans, tmp);
		}


		System.out.println(ans);
	}



	public static String[] toStringArray(String s) {
		String[] tmp = new String[s.length()];
		char[] c = s.toCharArray();
		for (int i = 0; i < tmp.length; i++) {
			tmp[i] = String.valueOf(c[i]);
		}
		return tmp;
	}

	public static String concatStringArray(String[] s){
		StringBuffer sb = new StringBuffer();
		for(String x:s){
			sb.append(x);
		}
		return sb.toString();
	}

	public static void check() throws Exception{
		if(in == null){
			in = new BufferedReader(new InputStreamReader(System.in));
		}
		if(Ws==null || Ws.length<=wsIndx){
			Ws = in.readLine().split(" ");
			wsIndx=0;
		}
	}
	public static int nextInt()throws Exception{
		check();
		return Integer.parseInt(Ws[wsIndx++]);
	}

	public static long nextLong()throws Exception{
		check();
		return Long.parseLong(Ws[wsIndx++]);
	}

	public static String nextString()throws Exception{
		check();
		return Ws[wsIndx++];
	}

	public static int[] nextInts()throws Exception{
		check();
		int[] tmp = new int[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Integer.parseInt(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static long[] nextLongs()throws Exception{
		check();
		long[] tmp = new long[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Long.parseLong(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static String[] nextStrings()throws Exception{
		check();
		wsIndx=Ws.length;
		return Ws;
	}


}

Measured memory_bytes: 21332
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1005;
vector<int>w[MAXN];
int n,k,a[MAXN][2];
int vis[MAXN],ma[MAXN];
int dfs(int u)
{
    for(int i=0;i<int(w[u].size());i++)
    {
        int v=w[u][i];
        if(vis[v])
            continue;
        vis[v]=1;
        if(ma[v]==0||dfs(ma[v]))
        {
            ma[v]=u;
            ma[u]=v;
            return 1;
        }
    }
    return 0;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d %d",&a[i][0],&a[i][1]);
	for(int i=1;i<=n;i++)
	{
		int b1,b2;
		scanf("%d %d",&b1,&b2);
		for(int j=1;j<=n;j++)
		{
			if(b1>a[j][0]&&b2>a[j][1])
			{
				w[i+n].push_back(j);
				w[j].push_back(i+n);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(!ma[i])
		{
			memset(vis,0,sizeof(vis));
			if(dfs(i))
				ans++;
		}
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 256