akhauriyash/Code-Regression huggingface dataset:
<?php

$n = trim(fgets(STDIN));

$ns = [$n];
$i = 2;
while(true){
  if ($n%2 == 0){
  	$nn = $n/2;
  } else {
    $nn = $n*3+1;
  }
  if (in_array($nn, $ns)) break;
  array_push($ns, $nn);
  $n = $nn;
  $i++;
}
echo $i;

?>

Measured memory_bytes: 4604
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int v[] = new int[n];
    int c[] = new int[n];
    int answer =0;
    for(int i=0;i<n;i++){
      v[i]=sc.nextInt();
    }
    for(int i=0;i<n;i++){
      c[i]=sc.nextInt();
    }
    for(int i=0;i<n;i++){
      if(v[i]>c[i]){
        answer = answer+v[i]-c[i];
      }
    }
    System.out.println(answer);
    
  }
  

  
}

Measured memory_bytes: 23764
#include<cstdio>
#include<iostream>
#include<string>

using namespace std;

int main(void){

	string TARO,HANAKO;
	int n;
	int Tsco=0,Hsco=0;
	cin>>n;

	for(int i=0;i<n;i++){
		cin>>TARO>>HANAKO;
		if(TARO>HANAKO) Tsco+=3;
		if(TARO==HANAKO) Tsco++,Hsco++;
		if(TARO<HANAKO) Hsco+=3;
	}

	cout<<Tsco<<" "<<Hsco<<endl;

	return 0;
}

Measured memory_bytes: 1208
# -*- coding: utf-8 -*-
import sys
'import math'
while(1):
    n,m=input().split()
    if n=='0' and m=='0':
        sys.exit()
    n=int(n)+1
    m=int(m)
    cnt=0
    for a in range(1,n):
        for b in range(a+1,n):
            for c in range (b+1,n):
                if a+b+c==m:
                    cnt+=1
    print(cnt)

Measured memory_bytes: 7672
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
 
void solve() {
	int a,b,h,m;
	cin>>a>>b>>h>>m;
	double hd,md;
	double pi=4*atan(1.0);
	hd=(double)((h*60+m)%720)/720*2*pi;
	md=(double)m/60*2*pi;
	double ddeg=abs(hd-md);
	double c=a*a+b*b-2*a*b*cos(ddeg);
	c=sqrt(c);
	cout<<setprecision(16)<<c<<"\n";
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}

Measured memory_bytes: 4184
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;
#define REP(i, n) for (ll i = 0; i < (int)(n); i++)
#define RREP(i, n) for (ll i = (int)(n)-1; i > -1 ; i--)
#define IN(T, x) T x;cin >> x;
#define AIN(T, a, n) vector<T> a(n);REP(i, n){cin >> a[i];}
#define A2IN(T1, a, T2, b, n) vector<T1> a(n);vector<T2> b(n);REP(i, n){cin >> a[i] >> b[i];}
#define ALL(a) (a).begin(),(a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) SORT(a);reverse(ALL(a))
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
#define OUT(x) cout << x << endl
#define BOUT(b) if(b){OUT("Yes");}else{OUT("No");}
const ll INF = 100000007;

int main() {
  IN(ll, H);
  IN(ll, W);
  AIN(string, map, H);
  vector<vector<ll>> d(H, vector<ll>(W, INF));
  queue<P> que;
  ll count = 0;
  REP(i, H){
    REP(j, W){
      if(map.at(i).at(j) == '#')
        count++;
    }
  }
  ll ans = H * W - count;
  vector<ll> dx = {1, 0, -1, 0};
  vector<ll> dy = {0, 1, 0, -1};
  que.push(P(0,0));
  d.at(0).at(0) = 0;
  while(que.size()){
    P p = que.front();
    que.pop();
    if(p.first == H-1 && p.second == W-1)
      break;
    for(ll i = 0; i < 4; i++){
      ll ny = p.first + dy.at(i);
      ll nx = p.second + dx.at(i);
      if(0 <= nx && nx < W && 0 <= ny && ny < H && map.at(ny).at(nx) != '#' && d.at(ny).at(nx) == INF){
        que.push(P(ny,nx));
        d.at(ny).at(nx) = d.at(p.first).at(p.second) + 1;
      }
    }
  }
  ans -= d.at(H-1).at(W-1) + 1;
  if(ans < 0)
    ans = -1;
  OUT(ans);
}




Measured memory_bytes: 256
#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//#include <stdbool.h>
//#include <limits.h>
//#include <math.h>

int main() {
  int n;
  scanf("%d", &n);
  char s[n+1];
  scanf("%s", s);
  if (n%2 == 1) {
    printf("No\n");
    return 0;
  }
  for (int i=0; i<n/2; i++) {
    if (s[i] != s[i+n/2]) {
      printf("No\n");
      return 0;
    }
  }
  printf("Yes\n");
  return 0;
}


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

int main(){
int n;
cin >> n;
int a[n+10], b[n+10];
for(int i=0; i<n; ++i) cin >> a[i];

int m=0, l=0;
for(int i=0; i<n; i++){
    if(a[i]>m){
        m=a[i];//最大
        l=i;//番号
    }
}
int m2 = 0;
for(int i=0; i<n; i++){
if(a[i]>m2 && i!=l){
    m2 = a[i]; //二番目に大きいやつ？
}

}
for(int i=0; i<n; i++) b[i] = m; //各回の最大値を入れる

b[l] = m2; //最大が除外された時の二番目の最大をセット
for(int i=0; i<n; i++){
    cout << b[i] << endl; //出力
}



/*int ans=0;
for(int j=0; j<n; ++j){
    if(ans > a[j]) goto fini;
    ans = 0;
    for(int k=0; k<n; ++k){

        if(j==k) continue;
        if(ans<a[k]) ans = a[k];
    }
    fini:
    cout << ans << endl;
    
}*/


}

Measured memory_bytes: 3200
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, 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")
    };
}
 
//
// # Examples
//
// # integers
// input! { n: usize, m: usize, ... }
//
// # array
// input! { n: usize, v: [u64; n], }
//
// # matrix
// input! { n: usize, m: usize, mat: [[]] }
//
// # string
// input! { s: chars }
//
// 3 4
// ####
// #..#
// .#.#
//
// input!{
//     h: usize,
//     w: usize,
//     board: [chars; h],
// }
 
// https://practice.contest.atcoder.jp/tasks/practice_1

use std::collections::BinaryHeap;
use std::collections::HashSet;

fn main() {
    input! {
        x: usize, y: usize, z: usize, k:usize,
        mut a: [u64; x], 
        mut b: [u64; y],
        mut c: [u64; z]
    }
    a.sort(); a.reverse();
    b.sort(); b.reverse();
    c.sort(); c.reverse();
    let mut bh = BinaryHeap::new();
    let mut used = HashSet::new();
    bh.push((a[0]+b[0]+c[0],(0,0,0)));
    let mut cnt = 0;
    while cnt < k {
        let (ans, (i, j, k)) = bh.pop().unwrap();
        if used.contains(&(i,j,k)) { continue; }
        used.insert((i, j, k));
        //println!("{}, {:?}", ans, (i,j,k));
        println!("{}", ans);

        if i+1 < x {
            bh.push((a[i+1]+b[j]+c[k], (i+1,j,k)));
        }
        if j+1 < y {
            bh.push((a[i]+b[j+1]+c[k], (i,j+1,k)));
        }
        if k+1 < z {
            bh.push((a[i]+b[j]+c[k+1], (i,j,k+1)));
        }
        cnt += 1;
    }
}

Measured memory_bytes: 4352
import math
a,b,C=map(float,input().split())
θ=math.radians(C)
h=b*math.sin(θ)
S=(a*h)/2
c=math.sqrt(a**2+b**2-2*a*b*math.cos(θ))
L=a+b+c
print(S,L,h,sep="\n")


Measured memory_bytes: 5760
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
using namespace std;
#define INF 110000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,int> P;


struct UnionFind{
  //親の番号を格納する。親だった場合はその集合のサイズ
  vector<int> Parent;

  //作る時はParentの値を全て-1にする
  //こうすると全てバラバラになる
  UnionFind(int N){
    Parent=vector<int>(N,-1);
  }
  //Aがどのグループに属しているかを調べる
  int root(int A){
    if(Parent[A]<0) return A;
    return Parent[A]=root(Parent[A]);
  }

  //自分のいるグループの頂点数を調べる
  int size(int A){
    return -Parent[root(A)];
  }

  //AとBを結合する
  bool connect(int A,int B){
    //AとBを直接つなぐのではなく、root(A)にroot(B)を結合する
    A=root(A);
    B=root(B);
    if(A==B){
      return false;
    }
    //大きい方(A)に小さい方(B)を結合したい
    //大小が逆ならひっくり返す
    if(size(A) < size(B)) swap(A,B);

    //Aのサイズを更新する
    Parent[A]+=Parent[B];
    Parent[B]=A;
    return true;
  }
};


int main(){
  ll N,M;
  cin>>N>>M;
  vector<int> A(M),B(M);
  for(int i=0;i<M;i++){
    cin>>A[i]>>B[i];
    A[i]--; B[i]--;
  }
  vector<ll> ans(M);
  ans[M-1]=N*(N-1)/2;

  UnionFind Uni(N);

  for(int i=M-1;i>=1;i--){
    if(Uni.root(A[i])!=Uni.root(B[i])){
      ans[i-1]=ans[i]-(ll)Uni.size(A[i])*Uni.size(B[i]);
      Uni.connect(A[i],B[i]);
    }else ans[i-1]=ans[i];
  }

  for(int i=0;i<M;i++){
    cout<<ans[i]<<endl;
  }
}


Measured memory_bytes: 3328
#include <stdio.h>
int main()
{
  int kai,min,max,a,b,c,d,e,sum,i;
  while(1){
    scanf("%d",&kai);
    if(kai==0)break;
    sum=0;
    min=500;
    max=0;
    for(i=0;i<kai;i++){
      scanf("%d %d %d %d %d",&a,&b,&c,&d,&e);
      sum=a+b+c+d+e;
      if(sum>max)max=sum;
      if(sum<min)min=sum;
    }
    printf("%d %d\n",max,min);
  }
  return 0;
}

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


int main(){
	int cnt[9],a,n;
	for(int i=0;i<9;i++)cnt[i]=0;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a;
		if(a<3200){
			cnt[a/400]++;
		}
		else cnt[8]++;
	}
	int ans=0;
	for(int i=0;i<8;i++){
		if(cnt[i]>0)ans++;
	}
	cout<<max(1,ans)<<" ";
	ans+=cnt[8];
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long a[5],sum,n,p,i,b[4]={0,0,1,3};
main(){
	cin>>n;
	for(i=0;i<n;i++){cin>>a[i];sum+=a[i];}sort(a,a+n);
	if(n<4){p=b[n];}
	if(n==4){
		if(sum<9){p=4;}
		else if(a[0]<3){p=5;}
		else{p=6;}
	}
	if(n==5){
		if(sum<12){p=6;}
		else if(a[1]<3){p=7;}
		else if(a[0]<3||a[3]<4){p=8;}
		else if(a[0]<4){p=9;}
		else{p=10;}
	}
	cout<<sum-p<<endl;
}

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

using namespace std;


int gcd(int a, int b){
    int r,tmp;

  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
 
  /* ユークリッドの互除法 */
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
 
  /* 最大公約数を出力 */
    return b;

}

int gcds(int a, int b, int c){
    int d = gcd(c,b);
    return gcd(a,d);
}

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

    long long res = 0;

    for(int i = 1;i<K+1;i++){
        for(int j = i;j<K+1;j++){
            for(int k=j;k<K+1;k++){
                int coef = 1;
                if(i == k || i == j || k == j){
                    if(i == k && i == j && k == j){
                        //全て同じ
                        coef = 1;
                    }
                    else{
                        //１組同じ
                        coef = 3;
                    }
                }
                else{
                    //全て違う
                    coef = 6;
                }
                res += gcds(i,j,k) * coef;
            }
        }
    }


    cout << res << endl;

}


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

int main(){
    int n;
    scanf("%d",&n);
    int i,a;
    int ki=0,gu=0;
    for(i=0;i<=n-1;i++){
        scanf("%d",&a);
        if(a%2==0)gu++;
        else ki++;
    }
    
    if(ki%2==0)printf("YES");
    else printf("NO");
    
    
    
    return 0;
}


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

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    for(int i = a; i <= a*b; i+=a){
        if(i % b == c){
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
}


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

int max(int a,int b){
	if(a>b)return a;
	return b;
}

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

int compare_char(char *a,char *b){
	return strcmp(a,b);
}

int intsort(const void *a, const void *b){
	return *(int*)b - *(int*)a;
	/*qsort(a,aの配列数,sizeof(int),intsort);*/
}

int longsort(const void *a, const void *b){
	long *A=(long *)a;
	long *B=(long *)b;
	if(*A>*B) return -1;
	if(*A<*B) return 1;
	return 0;
}

int main(){
  int i,N,K=0,a[200000],b[200000];
  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d",&a[i]);
  }
  for(i=0;i<N;i++){
    scanf("%d",&b[i]);
  }

  for(i=0;i<N;i++){
    if(a[i]-b[i]>0)K+=a[i]-b[i];
  }
  printf("%d\n",K);
  return 0;
}

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


// typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>  ordered_set;
#define ll long long
 
#define fr(i,a,b) for (ll i = (a), _b = (b); i <= _b; i++)
#define frr(i,a,b) for (ll i = (a), _b = (b); i >= _b; i--)
#define rep(i,n) for (ll i = 0, _n = (n); i < _n; i++)
#define repr(i,n) for (ll i = n - 1; i >= 0; i--)
#define fill(ar,val) memset(ar, val, sizeof(ar))
#define fill0(ar) fill((ar), 0)
#define debug(x) cout<<#x<<": "<<x<<endl
 
#define ld long double
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<ii> vii;
typedef vector<int> vi;
ll n;
ll dp[3005][3005];
ll ar[3005];
#define INF 1000000000000000000
ll fun(ll a,ll b,ll c)
{
    if(a==b)
    {
        if(c)
        return dp[a][b]=ar[a];
        else
        return dp[a][b]=-ar[a];
    }
    if(dp[a][b]!=-INF)
    {
        return dp[a][b];
    }
    if(c)
    {
        // debug("Ads");
        // debug(a);
        // debug(b);
        return dp[a][b]=max(ar[a]+fun(a+1,b,0),ar[b]+fun(a,b-1,0));
    }
    else
    {
        // debug(a);
        // debug(b);
        return dp[a][b]=min(-ar[a]+fun(a+1,b,1),-ar[b]+fun(a,b-1,1));
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout<<setprecision(11);
    
    long double pi= 3.14159265358979323846;

    cin>>n;
    rep(i,3005)
    {
        rep(j,3005)
        dp[i][j]=-INF;
    }
    rep(i,n)
    {
        cin>>ar[i];
    }
    cout<<fun(0,n-1,1)<<endl;
    
    return 0;
}

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

const double PI = acos(-1.0);
const int N = 200001;
const int MOD = 1e9 + 7;
typedef long long ll;



int main()
{
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
    int a, b;
    cin>>a>>b;

    if(a == b)
    {
        cout<<"Draw\n";
    }
    else if(a == 1)
    {
        cout<<"Alice\n";
    }
    else if(b == 1)
    {
        cout<<"Bob\n";
    }
    else
    {
        if(a > b)
            cout<<"Alice\n";
        else
            cout<<"Bob\n";
    }




}





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

using namespace std;

int n,m,k,a,b,c;
int dis[105][100005];
vector<int>adj[105];
int E[105][105];

int main(){
	while(scanf("%d%d%d",&n,&m,&k) == 3){
		if( n==0 && m==0 && k==0)break;
		for(int i=0;i<n;i++)
			adj[i].clear();
		for(int i=0;i<n;i++)
			for(int j=0;j<=k;j++)
				dis[i][j] = 100005;
		for(int i=0;i<m;i++){
			scanf("%d%d%d",&a,&b,&c);
			a--;b--;
			adj[a].push_back(b);
			E[a][b] = c;
		}	
		deque<pair<int,int> >Q;
		dis[0][0] = 0;
		Q.push_front(make_pair(0,0));
		int ans = 100005;
		while(!Q.empty()){
			pair<int,int>q = Q.front();
			Q.pop_front();
			if(dis[q.first][q.second] >= ans)continue;
			if(q.first == n-1){
				ans = min(ans,dis[q.first][q.second]);
			}
			
			int u = q.first;
			for(int i=0;i<adj[u].size();i++){
				int v = adj[u][i];
				if(E[u][v] + q.second <= k && dis[v][q.second + E[u][v]] > dis[q.first][q.second]){
					Q.push_front(make_pair(v,q.second+E[u][v]));
					dis[v][q.second + E[u][v]] = dis[q.first][q.second];
				}
				if(dis[v][q.second] > dis[q.first][q.second]+1){
					Q.push_back(make_pair(v,q.second));
					dis[v][q.second] = dis[q.first][q.second] + 1;
				}
			}
			
		}
		cout<<ans<<"\n";
		
	}
}

Measured memory_bytes: 47584
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000007
using namespace std;

int h,w,k;
int ww[10],hh[10];
int ans = 0;
string c[10];
void wid(int wi){
  if(wi==w){
    int count = 0;
    rep(i,h){
      rep(j,w){
        if(c[i][j]=='#' && ww[j]==0 && hh[i]==0)count++;
      }
    }
    if(count==k)ans++;
  }else{
    ww[wi] = 1;
    wid(wi+1);
    ww[wi] = 0;
    wid(wi+1);
  }
}

void hei(int hi){
  if(hi==h)wid(0);
  else{
    hh[hi] = 1;
    hei(hi+1);
    hh[hi] = 0;
    hei(hi+1);
  }
}

int main(){
  cin >> h >> w >> k;
  rep(i,h)cin >> c[i];
  hei(0);
  cout << ans << endl;
  return 0;
}

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

#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define RFOR(i, a, b) for(int i=(a); i>=(b); i--)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) RFOR(i, n, 0)
#define dump(x)  cout << #x << " = " << (x) << endl;

typedef long long ll;
typedef pair<int, int> ii;
const int mod = 1e9+7;
const ll INF = 1e18;
const int inf = 1e9;

bool compare_by_second(pair<int,int> a, pair<int,int> b)
{
  if (a.second != b.second) {
    return a.second < b.second;
  }
  return a.first < b.first;
}

void solve()
{
  int n; cin>>n;
  vector<ii> job;
  for (int i=0; i<n; i++) {
    ll a,b; cin>>a>>b;
    job.push_back(make_pair(a,b));
  }
  sort(job.begin(),job.end(), compare_by_second);
  int sum=0;
  bool flg = true;
  for (int i=0; i<n; i++) {
    sum += job[i].first;
    if (sum > job[i].second) {
      flg = false;
      break;
    }
  }
  if (flg) cout << "Yes" << endl;
  else cout << "No" << endl;
}

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


Measured memory_bytes: 2420
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
#define _CRT_SECURE_NO_WARNINGS

#include <bits/stdc++.h>

//LIFE IS NOT A PROBLEM TO BE SOLVED

#define rep(i,a,b) for( int i = (int) a; i < (int) b; i++ )
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define debug(a) cout << #a << " = " << a << endl;
#define debug2(a,b) cout << #a << " = " << a << " --- " << #b << " = " << b << endl;
#define debugP(a) cout << a.F << " " << a.S << endl;
#define debugM(mat,n,m) rep( i, 0, n ){ rep( j, 0, m ) cout << mat[i][j] << " "; cout << endl; }

using namespace std;

typedef long long int ll;
typedef pair <int, int> ii;
typedef pair <ii, int> iii;

int H, W, black;
char mat[55][55];
int vis[55][55];

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

bool go(int x, int y){
	return x>=0 && y>=0 && x<H && y<W && !vis[x][y] && mat[x][y]=='.';
}

void solve(){
	queue <iii> q; q.push(iii(ii(0, 0), 1));
	vis[0][0] = 1;
	while(!q.empty()){
		iii u = q.front(); q.pop();
		if(u.F.F==H-1 && u.F.S==W-1){
			cout << H*W-u.S-black << "\n";
			return;
		}
		rep(i, 0, 4){
			int x=u.F.F+dx[i], y=u.F.S+dy[i];
			if(!go(x, y)) continue;
			vis[x][y] = 1;
			q.push(iii(ii(x, y), u.S+1));
		}
	}
	puts("-1");
}
int main(){
	
	cin >> H >> W;
	rep(i, 0, H) rep(j, 0, W){
		cin >> mat[i][j];
		if(mat[i][j]=='#') black++;
	}
	
	solve();
	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
  int A,B;
  cin >>A>>B;
  int ans=0;
  int count=1;
  rep(i,20){
    if(count>=B){
      cout<<ans<<endl;
      return 0;
    }
    else {
      ans++;
      count += A-1;
    }
  }
  return 0;
}


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

void Main()
{
    int h, n;
    cin >> h >> n;
    vector<int> a(n), b(n);
    vector<pair<double, int>> c;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i] >> b[i];
        c.push_back(make_pair((double)b[i]/a[i], i));
    }
    vector<long> dp(h+1, 1e13); //ダメージiを与えるために必要な最小のMP消費量
    dp[0] = 0;
    for (int i = 1; i <= h; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if(i >= a[j]) {
                dp[i] = min(dp[i], dp[i-a[j]] + b[j]);
            }else{
                dp[i] = min(dp[i], (long)b[j]);
            }
        }
    }
    cout << dp[h] << endl;
    
}

int main(int argc, char **argv)
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    Main();
    return 0;
}


Measured memory_bytes: 3772
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

public class Main {

  static int d;
  static int[] array_c;
  static int[][] array_s;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    d = sc.nextInt();
    array_c = new int[27];
    array_s = new int[d + 1][27];
    int[] schedule = new int[d + 1];
    ArrayList<Integer> list = new ArrayList<>();

    for (int i = 1; i <= 26; i++) {
      array_c[i] = sc.nextInt();
      if(array_c[i] >= 75){
        list.add(i);
      }
    }

    for (int i = 1; i <= d; i++) {
      for (int j = 1; j <= 26; j++) {
        array_s[i][j] = sc.nextInt();
      }
    }

    for (int i = 1; i <= d; i++) {
      int maxc = 1;
      for (int j = 2; j <= 26; j++) {
        if (array_s[i][maxc] < array_s[i][j]) {
          maxc = j;
        }
      }
      schedule[i] = maxc;
    }


    for(Integer i : list){
      int tempScore = calcScore(schedule);
      int[] schedule2 = new int[d + 1];
      System.arraycopy( schedule, 0, schedule2, 0, schedule.length);
      int dx = 10;
      int ii = 1;
      while(dx * ii < d){
        schedule2[dx * ii] = i;
        ii++;
      }
      if(tempScore < calcScore(schedule2)){
        System.arraycopy( schedule2, 0, schedule, 0, schedule.length);
      }
    }

    // 最終OUTPUT
    for (int i = 1; i <= d; i++) {
      System.out.println(schedule[i]);
    }
  }

  static int calcScore(int[] schedule) {
    int m = 0;
    HashMap<Integer, Integer> last = new HashMap<>();
    for (int i = 1; i <= d; i++) {
      last.put(schedule[i], i);
      m += array_s[i][schedule[i]];
      for (int j = 1; j <= 26; j++) {
        int lastday = last.get(j) == null ? 0 : last.get(j);
        m -= (i - lastday) * array_c[j];
      }
    }
    return m;
  }
}

Measured memory_bytes: 46616
k = int(input())
ary = [1,9,30,76,141,267,400,624,885,1249,1590,2208,2689,3411,4248,5248,6081,7485,8530,10248,11889,13687,15228,17988,20053,22569,25242,28588,31053,35463,38284,42540,46581,50893,55362,61824,65857,71247,76884,84388,89349,97881,103342,111528,120141,128047,134580,146316,154177,164817,174438,185836,194157,207927,218812,233268,245277,257857,268182,288216,299257,313635,330204,347836,362973,383709,397042,416448,434025,456967,471948,499740,515581,536073,559758,583960,604833,633651,652216,683712,709065,734233,754734,793188,818917,846603,874512,909496,933081,977145,1006126,1041504,1073385,1106467,1138536,1187112,1215145,1255101,1295142,1342852,1373253,1422195,1453816,1502376,1553361,1595437,1629570,1691292,1726717,1782111,1827492,1887772,1925853,1986837,2033674,2089776,2145333,2197483,2246640,2332104,2379085,2434833,2490534,2554600,2609625,2693919,2742052,2813988,2875245,2952085,3003306,3096024,3157249,3224511,3306240,3388576,3444609,3533637,3591322,3693924,3767085,3842623,3912324,4027884,4102093,4181949,4270422,4361548,4427853,4548003,4616104,4718640,4812789,4918561,5003286,5131848,5205481,5299011,5392008,5521384,5610705,5739009,5818390,5930196,6052893,6156139,6239472,6402720,6493681,6623853,6741078,6864016,6953457,7094451,7215016,7359936,7475145,7593865,7689630,7886244,7984165,8130747,8253888,8403448,8523897,8684853,8802826,8949612,9105537,9267595,9376656,9574704,9686065,9827097,9997134,10174780,10290813,10493367,10611772,10813692]
print(ary[k-1])

Measured memory_bytes: 9320
N = input()
A = map(int, raw_input().split())
d = 0
ans = 0
for i in xrange(N-1):
    dd = A[i+1] - A[i]
    if dd * d < 0:
        ans += 1
        d = 0
    else:
        if abs(dd) > 0:
            d = dd
print ans + 1


Measured memory_bytes: 11320
/// author: Mr.Hakimov

#include <bits/stdc++.h>
#include <chrono>

#define fi first
#define se second
#define pb push_back
#define pf push_front
#define Pb pop_back
#define Pf pop_front
#define all(x) (x).begin(), (x).end()
#define fin(s) freopen(s, "r", stdin);
#define fout(s) freopen(s, "w", stdout);

using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

typedef long long ll;
typedef long double ld;

int TN = 1;

void solve() {
	int n;
	int m;
	cin >> n >> m;
	
	int x;
	cin >> x;
	
	vector<int> c(n);
	vector<vector<int>> a(n, vector<int> (m));
	for (int i = 0; i < n; ++i) {
		cin >> c[i];
		
		for (int j = 0; j < m; ++j) {
			cin >> a[i][j];
		}
	}
	
	int answer = INT_MAX;
	for (int i = 0; i < (1 << n); ++i) {
		vector<int> e(n);
		
		int cpI = i;
		for (int j = 0; j < n; ++j) {
			if (i % 2 == 1) {
				e[j] = 1;
			}
			
			i /= 2;
		}
		
		i = cpI;
		
		vector<int> d(m);
		int cur = 0;
		for (int k = 0; k < n; ++k) {
			if (e[k]) {
				for (int j = 0; j < m; ++j) {
					d[j] += a[k][j];
				}
				
				cur += c[k];
			}
		}
		
		bool f = true;
		for (int k = 0; k < m; ++k) {
			if (d[k] < x) {
				f = false;
				
				break;
			}
		}
		
		if (f) {
			answer = min(answer, cur);
		}
	}
	
	if (answer == INT_MAX) {
		cout << -1;
	} else {
		cout << answer;
	}
}

int main() {
    auto start = chrono::steady_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    /// =========================================
    /// fin("input.txt"); fout("output.txt");
    /// fin("file.in"); fout("file.out");
    /// cin >> TN;
    /// =========================================

    while (TN--) {
        solve();
    }

    auto finish = chrono::steady_clock::now();
    auto elapsed_ms = chrono::duration_cast<chrono::milliseconds>(finish - start);
    cerr << endl << "Time: " << elapsed_ms.count() << " ms\n";

    return 0;
}


Measured memory_bytes: 3664
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

const double pi = acos(-1.0);

double theta(int a) {
	return a / 180.0 * pi;
}
int main() {
	int d, a, pre_a = 0;
	double x, y;
	x = 0.0; y = 0.0;
	
	while (1) {
		scanf("%d,%d", &d, &a);
		if (d == 0 && a == 0) break;
		x += d * sin(theta(pre_a));
		y += d * cos(theta(pre_a));
		pre_a += a;
	}
	cout << (int)x << endl;
	cout << (int)y << endl;
}


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

def solve(X: int, Y: int, Z: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    def next_state(s):
        def _next_state(i, j, k):
            return -sum([A[i], B[j], C[k]]), (i, j, k)
        _, (i, j, k) = s
        if i+1 < len(A):
            yield _next_state(i+1, j, k)
        if j+1 < len(B):
            yield _next_state(i, j+1, k)
        if k+1 < len(C):
            yield _next_state(i, j, k+1)

    ans = set()
    A = tuple(sorted(A, reverse=True))
    B = tuple(sorted(B, reverse=True))
    C = tuple(sorted(C, reverse=True))
    q = [(-sum([A[0], B[0], C[0]]), (0, 0, 0))]
    ans.add(q[0])
    for _ in range(K):
        s = heapq.heappop(q)
        for ns in next_state(s):
            if ns in ans:
                continue
            ans.add(ns)
            heapq.heappush(q, ns)
    return sorted((-v for v, _ in ans), reverse=True)[:K]


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

if __name__ == '__main__':
    main()


Measured memory_bytes: 5360
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("YES")
#define p_no() p("NO")

template < typename T >
void vprint(T &V){
	for(auto v : V){
    	cout << v << " ";
	}
	cout << endl;
}

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

const ll mod = 1e9 + 7;
const ll inf = 1e18;

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

    // input
    double T, X;
    cin >> T >> X;

    cout << setprecision(15);
    p(T/X);
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;
int main()
{
	int a, b, c = 0;
	cin >> a >> b;
	if (a > b) {
		c += a;
		a--;
	}
	else {
		c += b;
		b--;
	}
	if (a > b) {
		c += a;
		a--;
	}
	else {
		c += b;
		b--;
	}
	cout << c;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

P f(int x){
  int a = x%10;
  int b = a;
  while ( x > 0 ){
    b = x%10;
    x /= 10;
  }
  return P(a,b);
}

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

  map<P,int> map;
  rep(i,n){
    P p = f(i+1);
    map[p]++;
  }
  int ans = 0;
  rep(i,n){
    P p = f(i+1);
    ans += map[P(p.second,p.first)];
  }
  cout << ans << endl;
}


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

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;

ll fexp(ll n, ll p) {
	ll ans = 1;
	while (p) {
		if (p & 1) ans = (ans * n) % MOD;
		n = (n * n) % MOD;
		p >>= 1;
	}
	return ans % MOD;
}

ll fat(ll n) {
	ll ans = 1;
	for (int i = 1; i <= n; i++) {
		ans = (ans * i) % MOD;
	}
	return ans;
}

ll inverse(ll n) {
	return fexp(n, MOD - 2);
}

ll comb(ll n, ll k) {
	if (k < 0 || k > n) return 0;
	ll x = (inverse(fat(k)) * inverse(fat(n - k))) % MOD;
	return (fat(n) * x) % MOD;
}

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

	long long x, y;
	cin >> x >> y;
	if ((x + y) % 3 != 0) {
		cout << "0\n";
		return 0;
	}
	long long n = (2 * y - x) / 3;
	long long m = (2 * x - y) / 3;

	cout << comb(n + m, n) << '\n';
	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {

        ModScanner ms = new ModScanner();
        OutputStream outputStream = System.out;
        PrintWriter out = new PrintWriter(outputStream);
        int n = ms.nextInt();
        int[] heights = new int[n];
        for (int i = 0; i < n; i++) {
            heights[i] = ms.nextInt();
        }
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        out.println(findTotalJumpCost(heights, 0, dp));
        out.close();
    }

    private static int findTotalJumpCost(int[] heights, int ind, int[] dp) {
        if (ind >= heights.length) {
            return 0;
        }
        if (dp[ind] != Integer.MAX_VALUE) {
            return dp[ind];
        }
        int next = findTotalJumpCost(heights, ind+1, dp);
        if (ind + 1 < heights.length) {
            dp[ind] = Math.min(next + Math.abs(heights[ind] - heights[ind+1]), dp[ind]);
        }
        int next_to_next = findTotalJumpCost(heights, ind+2, dp);
        if (ind + 2 < heights.length) {
            dp[ind] = Math.min(next_to_next + Math.abs(heights[ind] - heights[ind+2]), dp[ind]);
        }

        return dp[ind] != Integer.MAX_VALUE ? dp[ind] : 0;
    }

}

class ModScanner {

    BufferedReader br;
    StringTokenizer st;

    public ModScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String nextToken() throws Exception {
        while (st == null || !st.hasMoreElements()) {
            st = new StringTokenizer(br.readLine());

        }
        return st.nextToken();
    }

    String nextString() throws Exception {
        return br.readLine();
    }


    int nextInt() throws Exception, Exception {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }

}


Measured memory_bytes: 55528
S,T=(0..2).map{(?0+gets).chars.map{|c|$.-=~c.count(?A)}};puts$<.map{|l|a,b,c,d=l.split.map &:to_i;(S[b]-S[a-1]-T[d]+T[c-1])%3<1?:YES: :NO}

Measured memory_bytes: 23532
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

int main()
{
    string s; cin>>s;
    int n=s.size();
    vector<int> a(n+1);
    for(int i=0; i<n; ++i) {
        while (i<n and s[i]=='<') {
            a[i+1]=a[i]+1;
            ++i;
        }
    }
    for(int i=n-1; i>=0; --i) {
        while (i>=0 and s[i]=='>') {
            a[i]=max(a[i], a[i+1]+1);
            --i;
        }
    }
    cout<<accumulate(begin(a), end(a), 0LL)<<endl;
}


Measured memory_bytes: 2820
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define mrep(i,j,n) for(int i = j; i < n; i++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define rrep(i,n) for(int i = n-1; i >= 0; i--)
#define mreps(i,j,n) for(int i = j; i <= n; i++)
#define rreps(i,n) for(int i = n; i >= 1; i--)
#define co(x) cout << x <<endl
#define cs(x) cout << x <<" "
#define el cout << endl
#define sp(x) cout << setprecision(x);
#define cer(x) cerr << x <<endl
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(ALL(x), val), x.end())
#define vi vector<int> 
#define vvi vector<vector<int>> 
#define vpii vector<pair<int,int>> 
#define vl vector<ll> 
#define vvl vector<vector<ll>> 
#define vb vector<bool> 
#define vvb vector<vector<bool>>
#define vs vector<string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll mod = 1e9 + 7;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a * b / g; }
bool is_prime(ll x) { for (ll i = 2; i * i <= x; i++) { if (x % i == 0)return false; } return true; }

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	string s; cin >> s;
	int ans = 0;
	rep(i, sz(s))if (s[i] == '2')ans++;
	co(ans);
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<endl;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b){ a = b; return 1; } return 0; }

int n;
vector<pll> G[100010];
vector<int> ans(100010);

void dfs(int now , int parent ,ll dep){
  ans[now]=dep%2;
  for(auto p:G[now]){
    if (p.fi == parent) continue;
    dfs(p.fi, now, dep + p.se);
  }
}


int main(int argc, char const *argv[]) {
  cin >> n;
  rep(i, n - 1) {
    ll u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    G[u].pb({v, w});
    G[v].pb({u, w});
  }
  dfs(0, -1, 0);
  rep(i,n) cout << ans[i] << endl;
  return 0;
}

Measured memory_bytes: 9856
#include <bits/stdc++.h>
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define PP pair<P,P>
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define mkt make_tuple
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;
template<class T> inline void chmax(T& a, T b) { a = max(a, b); }
template<class T> inline void chmin(T& a, T b) { a = min(a, b); }

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return x != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}
int get_rand(int MIN, int MAX) {
	random_device rnd;
	mt19937_64 mt64(rnd());
	uniform_int_distribution<int>engine(MIN, MAX);
	return engine(mt64);
}
/*--------Library Zone!--------*/



int n, a[114514];
P p[114514];
set<int>stle, stri;
int le[114514], ri[114514];
int le2[114514], ri2[114514];
signed main() {
	cin >> n;
	rep(i, n) {
		cin >> a[i];
		p[i] = { a[i],i };
	}
	sort(p, p + n, greater<>());
	stle.insert(-1); stri.insert(n);
	rep(i, n) {
		auto it = stle.lower_bound(p[i].second); it--;
		le[p[i].second] = *it;
		if (it == stle.begin())le2[p[i].second] = -1;
		else {
			it--; le2[p[i].second] = *it;
		}
		it = stri.lower_bound(p[i].second);
		ri[p[i].second] = *it;
		it++;
		if (it == stri.end())ri2[p[i].second] = n;
		else ri2[p[i].second] = *it;
		stle.insert(p[i].second);
		stri.insert(p[i].second);
	}
	int ans = 0;
	rep(i, n) {
		int le_ = le[i], le2_ = le2[i];
		int ri_ = ri[i], ri2_ = ri2[i];
		int all = (i - le2_) * (ri2_ - i) - 1;
		int ma = (le_ - le2_) * (ri2_ - ri_);
		ma += (i - le_) * (ri_ - i) - 1;
		all -= ma;
		ans += a[i] * all;
	}
	cout << ans << endl;
}

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



int main() {
#ifdef HOME
    assert(freopen("in", "r", stdin));
#endif


    int n, m;
    while (scanf("%d%d", &n, &m) == 2) {
        vector<vector<int> > a(n, vector<int>(m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%d", &a[i][j]);
                a[i][j]--;
            }
        }

        int l = 0, r = n + 1;
        while (r - l > 1) {
            int x = (l + r) >> 1;

            vector<vector<int> > b(m);
            vector<int> ptr(n, 0);
            for (int i = 0; i < n; i++) b[a[i][0]].push_back(i);
            vector<char> banned(m);

            int cnt = 0;
            while (cnt < m) {
                int k = -1;
                for (int i = 0; i < m; i++) if (!banned[i] && (int)b[i].size() > x) k = i;

                if (k == -1) break;
                cnt++;
                if (cnt == m) break;

                banned[k] = 1;
                for (int id : b[k]) {
                    while (banned[a[id][ptr[id]]]) {
                        ptr[id]++;
                    }
                    b[a[id][ptr[id]]].push_back(id);
                }
                b[k].clear();
            }
            if (cnt == m) l = x;
            else r = x;
        }
        printf("%d\n", r);
    }


#ifdef HOME
    cerr << "time: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
#endif
    return 0;
}

Measured memory_bytes: 1272
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
    int D,N,ts[210],mins[210],maxs[210];
    scanf("%d%d",&D,&N);
    for(int i=0;i<D;i++){
        scanf("%d",&ts[i]);
        mins[i]=200;
        maxs[i]=-1;
    }
    for(int i=0;i<N;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        for(int j=0;j<D;j++){
            if(a<=ts[j] && ts[j]<=b){
                mins[j]=min(mins[j],c);
                maxs[j]=max(maxs[j],c);
            }
        }
    }
    int dp[210][2];
    dp[0][0]=dp[0][1]=0;
    for(int i=1;i<D;i++){
        dp[i][0]=max(dp[i-1][0]+abs(mins[i-1]-mins[i]),dp[i-1][1]+abs(maxs[i-1]-mins[i]));
        dp[i][1]=max(dp[i-1][0]+abs(mins[i-1]-maxs[i]),dp[i-1][1]+abs(maxs[i-1]-maxs[i]));
    }
    printf("%d\n",max(dp[D-1][0],dp[D-1][1]));
}

Measured memory_bytes: 1016
s = gets.chomp.split("")
t = gets.chomp.split("")
ans = "No"
n = s.length

n.times do
    u = Array.new
    if s == t
        ans = "Yes"
    end
    u[0] = s[n-1]
    for i in 0..n-2 do
        u[i+1] = s[i]
    end
    s = u
end

puts ans

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

using ll = long long;
using vi = vector<int>;
using vll = vector<long long>;

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

constexpr long long mod = 1000000007;

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

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

    string s;
    cin >> s;

    vi a(26, 0);
    rep(i, s.size()) {
        a[s[i] - 'a']++;
    }

    string ss = s;

    reverse(ss.begin(), ss.end());

    if (s == ss) {
        cout << 0 << endl;
    } else {
        string s2;

        rep(i, s.size()) {
            if (s[i] != 'x') {
                s2 += s[i];
            }
        }

        string ss2 = s2;
        reverse(ss2.begin(), ss2.end());

        if (s2 == ss2) {
            int ans = 0;

            vi c(ss2.size() + 1, 0);
            int idx = 0;

            rep(i, s.size()) {
                if (s[i] == 'x') {
                    c[idx]++;
                } else if (s[i] == s2[idx]) {
                    idx++;
                }
            }

            for (int i = 0; i < c.size() / 2; i++) {
                int t1, t2;
                t1 = c[i];
                t2 = c[c.size() - 1 - i];

                ans += max(t1, t2) - min(t1, t2);
            }

            cout << ans << endl;

        } else {
            cout << -1 << endl;
        }
    }
}

Measured memory_bytes: 976
n = int(input())
s = input()
 
count = {"R":0,"G":0,"B":0}
for c in s:
    count[c] += 1
 
r,g,b = count.values()
ans = r*g*b
for i in range(1,(n-1)//2+1): #1から
    for rgb in zip(s,s[i:],s[i*2:]):  #rgbに連続した三つのリストの要素を入れ込む
        if len(set(rgb)) == 3:  #リストrgbをセットにまとめ、長さが
            ans -=1
print(ans)

Measured memory_bytes: 75532
package main

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

var n int
var num []int
var dp = make(map[int]map[bool]int)

func main() {
	s := readBytes()
	n = len(s)

	num = make([]int, n)
	for i := range s {
		num[i], _ = strconv.Atoi(string(s[i]))
	}

	dp[-1] = make(map[bool]int)
	dp[-1][true] = 1
	for i := range num {
		dp[i] = make(map[bool]int)

		dp[i][true] = min(
			dp[i-1][true]+(10-num[i]-1),
			dp[i-1][false]+num[i]+1)

		dp[i][false] = min(
			dp[i-1][true]+(10-num[i]),
			dp[i-1][false]+num[i])
	}

	fmt.Println(dp[n-1][false])

	// fmt.Println(min(dfs(0, true)+1, dfs(0, false)))
}

// TLE
func dfs(i int, ten bool) int {
	if v, ok := dp[i][ten]; ok {
		return v
	}

	if _, ok := dp[i]; !ok {
		dp[i] = make(map[bool]int)
	}

	if i == n-1 {
		if ten {
			dp[i][ten] = 10 - num[i]
		} else {
			dp[i][ten] = num[i]
		}
		// fmt.Println("end:", i, ten, dp[i][ten])
		return dp[i][ten]
	}

	ans := 0
	if ten {
		ans = dfs(i+1, true) + (10 - num[i] - 1)
		// fmt.Println(1, i, ten, ans)
		ans = min(ans, dfs(i+1, false)+(10-num[i]))
		// fmt.Println(2, i, ten, dfs(i+1, false)+(10-num[i]))
	} else {
		ans = dfs(i+1, true) + num[i] + 1
		// fmt.Println(3, i, ten, ans)
		ans = min(ans, dfs(i+1, false)+num[i])
		// fmt.Println(4, i, ten, dfs(i+1, false)+num[i])
	}

	dp[i][ten] = ans
	return dp[i][ten]
}

// sort ------------------------------------------------------------

type xxx struct {
	x int
}

type sortArray []xxx

func (s sortArray) Len() int           { return len(s) }
func (s sortArray) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
func (s sortArray) Less(i, j int) bool { return s[i].x < s[j].x }

// -----------------------------------------------------------------

var (
	readString func() string
	readBytes  func() []byte
)

func init() {
	log.SetFlags(log.Lshortfile)
	readString, readBytes = newReadString(os.Stdin)
}

func newReadString(ior io.Reader) (func() string, func() []byte) {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	f1 := func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
	f2 := func() []byte {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Bytes()
	}
	return f1, f2
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 10, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readFloat64() float64 {
	f, err := strconv.ParseFloat(readString(), 64)
	if err != nil {
		panic(err.Error())
	}
	return f
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func sum(a []int) int {
	var ret int
	for i := range a {
		ret += a[i]
	}
	return ret
}

func sumFloat64(a []float64) float64 {
	var ret float64
	for i := range a {
		ret += a[i]
	}
	return ret
}

func gcd(m, n int) int {
	for m%n != 0 {
		m, n = n, m%n
	}
	return n
}

func lcm(m, n int) int {
	return m / gcd(m, n) * n
}


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

using namespace std;

int main()
{
    int n , m ;
    cin>>n>>m ;
    set<int>p[n+1] ;
    pair<int , int> arr[m+1];
    for(int i = 0 ; i < m ; ++i)
    {
        int x , y ;
        cin>>arr[i].first>>arr[i].second;
        x = arr[i].first , y = arr[i].second;
        p[x].insert(y);
    }
    map<int , int>mp ;
    map< pair<int , int> , int>id ;
    for(int i = 0 ; i < m ; ++i)
    {
        int x = arr[i].first , y = arr[i].second;
        if(mp[x])
            continue;
        mp[x] = 1;
        int cnt = 0 ;
        for(auto &i : p[x])
            id[{x , i}] = ++cnt ;
    }
    for(int i = 0 ; i < m ; ++i)
    {
        int x = arr[i].first , y = arr[i].second;
        string s = to_string(x) , s2 = to_string(id[{x , y}]);
        for(int j = 0 ; j < 6-s.size() ; ++j)
            cout<<0;
        cout<<s;
        for(int j = 0 ; j < 6-s2.size() ; ++j)
            cout<<0;
        cout<<s2<<"\n";
    }
    return 0 ;
}


Measured memory_bytes: 22528
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)

string encode(int x) {
	string res;
	res.resize(4);
	REP(i, 4) res[3 - i] = ((x >> i) & 1) + '0';
	return res;
}

int decode16(char c) {
	if (c >= '0' && c <= '9') return c - '0';
	else return c - 'a' + 10;
}

int decode(string str) {
	int res = 0;
	REP(i, str.size()) {
		res += (str[i] - '0') << (str.size() - 1 - i);
	}
	return res;
}

int decodeF(string str) {
	int res = 0, tmp = 1000000000;
	REP(i, str.size()) {
		tmp /= 2;
		if (str[i] == '1') res += tmp;
	}
	
	if (res > 0) {
		int keta = log10(res) + 1;
		FOR(i, keta, 9) putchar('0');
	}
	while (res > 0 && res % 10 == 0) res /= 10;
	
	return res;
}

int main() {
	int Q;
	cin >> Q;
	while (Q--) {
		string str;
		cin >> str;
		
		string d = "";
		REP(i, 8) d += encode(decode16(str[i]));
		
		string B = d[0] == '1' ? "-" : "";
		string I = d.substr(1, 24);
		string F = d.substr(25, 7);
		cout << B << decode(I) << ".";
		cout << decodeF(F) << endl;
		
	}
	return 0;
}

Measured memory_bytes: 3412