akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;


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

	long long a, b, n, ans, x;
	cin >> n >> a >> b;

	if ((b - a) % 2 == 0) ans = (b - a) / 2;
	else ans = n * 2;
	ans = min(ans, b - 1);
	ans = min(ans, n - a);

	if ((b - a) % 2 == 1) {
		x = a - 1 + 1 + (b - (a - 1 + 1) - 1) / 2;
		ans = min(ans, x);

		x = (n - b) + 1 + (n - (a + n - b + 1)) / 2;
		ans = min(ans, x);
	}

	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 888
/* Print a Frame */
#include <stdio.h>

int main()
{
    int H, W, i, j, n;
    for(n=0;; n++){
        scanf("%d %d", &H, &W);
        if(H ==0 && W == 0){
            break;
        }
        for(i=0; i < H; i++){
            printf("#");
            for(j=0; j < W-2; j++){
                if(i == 0 || i == H-1){
                    printf("#");
                }
                else{
                    printf(".");
                }
            }
            printf("#\n");
        }
        printf("\n");
    }
}


Measured memory_bytes: 2028
using System;
using System.Collections.Generic;
using System.Linq;

class F
{
	static void Main()
	{
		var n = int.Parse(Console.ReadLine());
		map = new int[n + 1].Select(_ => new List<int>()).ToArray();
		foreach (var r in new int[n - 1].Select(_ => Console.ReadLine().Split().Select(int.Parse).ToArray()))
		{
			map[r[0]].Add(r[1]);
			map[r[1]].Add(r[0]);
		}

		tour = new int[n + 1].Select(_ => new List<int>()).ToArray();
		Dfs(1, 0);

		Console.WriteLine((tour.Select(l => Hole(l, n - 1)).Aggregate((x, y) => x + y) / 2).V);
	}

	static List<int>[] map;
	static List<int>[] tour;
	static int c;
	static void Dfs(int p, int p0)
	{
		foreach (var x in map[p])
		{
			if (x == p0) continue;
			tour[x].Add(++c);
			Dfs(x, p);
			tour[p].Add(++c);
		}
	}

	static MInt Hole(List<int> l, int m)
	{
		if (l.Count < 2) return 0;

		MInt bSum = 0;
		for (int i = 0; i < l.Count; i++)
		{
			var c = ((l[(i + 1) % l.Count] - l[i]) / 2 + m) % m;
			bSum += ((MInt)2).Pow(c) - 1;
		}
		return 1 - 1 / ((MInt)2).Pow(m) * (1 + bSum);
	}
}

struct MInt
{
	const int M = 1000000007;
	public long V;
	public MInt(long v) { V = (v %= M) < 0 ? v + M : v; }

	public static implicit operator MInt(long v) => new MInt(v);
	public static MInt operator +(MInt x) => x;
	public static MInt operator -(MInt x) => -x.V;
	public static MInt operator +(MInt x, MInt y) => x.V + y.V;
	public static MInt operator -(MInt x, MInt y) => x.V - y.V;
	public static MInt operator *(MInt x, MInt y) => x.V * y.V;
	public static MInt operator /(MInt x, MInt y) => x * y.Inv();

	public MInt Pow(int i) => MPow(V, i);
	public MInt Inv() => MPow(V, M - 2);

	static long MPow(long b, int i)
	{
		for (var r = 1L; ; b = b * b % M)
		{
			if (i % 2 > 0) r = r * b % M;
			if ((i /= 2) < 1) return r;
		}
	}
}


Measured memory_bytes: 73508
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>
#define ll long long

using namespace std;

long long MOD = 1000000007;

struct info{
    int cost, series, y, x, prev;
};

bool operator< (const info &info1, const info &info2){
    if(info1.cost<info2.cost){
        return true;
    }else if(info1.cost>info2.cost){
        return false;
    }else if(info1.series<info2.series){
        return true;
    }else{
        return false;
    }
}
bool operator> (const info &info1, const info &info2){
    if(info1.cost>info2.cost){
        return true;
    }else if(info1.cost<info2.cost){
        return false;
    }else if(info1.series>info2.series){
        return true;
    }else{
        return false;
    }
}

struct proceed{
    int y, x, c;
};

template<typename T>
void cout_vec(vector<T> &vec){
    for(int i=0; i<vec.size(); i++){
        if (i!=0){
            cout << ' ';
        }
        cout << vec[i];
    }
    cout << endl;
}

template<typename T>
void cout_mat(vector<vector<T>  > &mat){
    for(int i=0; i<mat.size(); i++){
        vector<T> vec = mat[i];
        cout_vec(mat[i]);
    }
}


int H, W, K;
vector<proceed> move_={{1,0,0}, {-1,0,1}, {0,1,2}, {0,-1,3}};
int bfs(int sx, int sy, vector<vector<char>> &grid){
    priority_queue<info, vector<info>, greater<info>> pque;
    pque.push({0,0,sy,sx,4});
    vector<vector<vector<int>>> dist(H+2,vector<vector<int>>(W+2,vector<int>(5,MOD)));

    while((int)pque.size()>0){
        info now=pque.top();
        pque.pop();

        //cout << now.y << ' ' << now.x << ' ' << now.prev;
        if(grid[now.y][now.x]=='g'){
            //cout_mat(dist);
            return now.cost;
        }else if(dist[now.y][now.x][now.prev]<=now.cost){
            continue;
        }
        dist[now.y][now.x][now.prev]=now.cost;

        for(const auto &p: move_){
            if(grid[now.y+p.y][now.x+p.x]!='@'){
                if(p.c==now.prev && now.series<K){
                    pque.push({now.cost, now.series+1, now.y+p.y, now.x+p.x, p.c});
                }else{
                    pque.push({now.cost+1, 1, now.y+p.y, now.x+p.x, p.c});
                }
            }
        }
    }

    //cout_mat(grid);
    //cout_mat(dist);
    return -1;
}

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

    int sx, sy, gx, gy;
    cin >> sy >> sx >> gy >> gx;

    vector<vector<char>> grid(H+2,vector<char>(W+2,'@'));
    for(int i=1; i<=H; i++){
        for(int j=1; j<=W; j++){
            char c;
            cin >> c;
            grid[i][j]=c;
        }
    }
    grid[gy][gx]='g';

    cout << bfs(sx, sy, grid) << endl;
}

Measured memory_bytes: 224796
a1, a2, a3 = map(int, input().split())
elem1 = abs(a2 - a1) + abs(a3 - a2) 
elem2 = abs(a3 - a1) + abs(a2 - a3)
elem3 = abs(a1 - a2) + abs(a3 - a1)
elem4 = abs(a3 - a2) + abs(a1 - a3)
elem5 = abs(a1 - a3) + abs(a2 - a1)
elem6 = abs(a2 - a3) + abs(a1 - a2)
lst = [elem1, elem2, elem3, elem4, elem5, elem6]

print(min(lst))

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  for(int i = 1 ; i < 10 ; i++ ){
    for(int j = 1 ; j < 10 ; j++ ){
      cout << i << "x" << j << "=" << i * j << endl;
    }
  }
  return 0;
}

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

#define debug(x) (cerr << #x << " = " << x << endl;)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define FOR(it, b, e) for (typeof(b) it = (b); it != (e); ++it)
#define MSET(c, v) memset(c, v, sizeof(c))

const int INF = 0x3F3F3F3F;
const int NEGINF = 0xC0C0C0C0;
const int NULO = -1;
const double EPS = 1e-10;

inline int cmp(double x, double y = 0)
{
  if (fabs(x - y) < EPS)
    return 0;
  return x > y ? 1 : -1;
}

const int maxn = 2e5 + 100;
int a[maxn];

ll dp[maxn][2];
bool vis[maxn][2];

int n;
ll solve(int pos, int change)
{
  int mult = 1;
  if(change)
    mult = -1;

  if(pos == n - 1)
  {
    return a[pos] * mult;
  }

  ll &ans = dp[pos][change];
  if(vis[pos][change])
    return ans;
  vis[pos][change] = 1;
  ans = numeric_limits<int>::min();
  ll val = a[pos] * mult;
  ll nVal = -val;
  ans = max(ans, solve(pos + 1, 1) + nVal);
  ans = max(ans, solve(pos + 1, 0) + val);
  return ans;
}

int main()
{
  ios::sync_with_stdio(false);
  cin >> n;
  for(int i = 0; i < n ; i++)
    cin >> a[i];
  cout << solve(0, 0) << endl;
  return 0;

}

Measured memory_bytes: 10400
/*#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

#include <boost/rational.hpp>
*/
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
using ll = long long;
using ld = long double;
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define rep3(i, n) for (ll i = 1; i < (ll)(n+1); i++)
#define rep4(i, s, n) for (ll i = (s); i < (ll)(n+1); i++)
#define repr(i,n) for (ll i = (n-1); i>=0;i--)
#define repr3(i,n) for(ll i = (n);i>0;i--)
#define repr4(i,s,n) for(ll i = (n);i>=(s);i--)
#define stlen(s) ll s.size()-1
#define all(v) v.begin(), v.end()
#define cout(n) cout<<std::fixed<<std::setprecision(n)
using Graph = vector<vector<int>>;
using Graphw = vector<vector<pair<ll,ll>>>;
#define INF1  INT_MAX;
#define INF2  LLONG_MAX;
#define PI  3.14159265358979323846;
#define MOD 1000000007;
/*
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部長が32の浮動小数点数型
using Real32 = mp::number<mp::cpp_dec_float<32>>;
// 仮数部長が1024の浮動小数点数型
using Real1024 = mp::number<mp::cpp_dec_float<1024>>;
// 有理数型
using Rat = boost::rational<Bint>;
*/
const int mod = 1000000007;


int main() {
string S;
cin>>S;
int n=S.size();
int table[n];
rep(i,n){
    if((S[i]=='R')&&(S[i+1]=='L')){
        int now=1;
        rep2(j,i+1,n){
            if(S[j]=='R')break;
            if((j-i)%2==0)now++;
        }
        repr(j,i){
            if(S[j]=='L')break;
            if((i-j)%2==0)now++;
        }
        table[i]=now;
    }
    else if((S[i]=='L')&&(S[i-1]=='R')){
        int now=1;
        repr(j,i){
            if(S[j]=='L')break;
            if((i-j)%2==0)now++;
        }
        rep2(j,i+1,n){
            if(S[j]=='R')break;
            if((j-i)%2==0)now++;
        }
        table[i]=now;
    }
    else{
        table[i]=0;
    }
}
rep(i,n){
cout<<table[i]<<endl;
}
return 0;
}

Measured memory_bytes: 4136
from collections import defaultdict

N = int(input())
A = [int(i) for i in input().split()]

A.sort(reverse=True)
i = 0
ret = 0
while i < N :
    if i + 3 < N and A[i] == A[i+1] == A[i+2] == A[i+3] :
        if ret == 0 :
            ret = A[i] * A[i]
        else :
            ret *= A[i]
        break
    elif i + 1 < N and A[i] == A[i+1] :
        if ret == 0 :
            ret = A[i]
            i += 1
        else :
            ret *= A[i]
            break
    
    i += 1
    
print(ret)

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

const int mod=1e9+7;

long long dp[128][10100];
string s;
int n;
long long ans;

int main(){
	cin>>s>>n;
	for(int i=0;i<=9;i++) dp[i%n][1]++;
	dp[0][0]=1;
	int l=s.size();
	for(int i=2;i<l;++i){
		for(int j=0;j<n;++j){
			for(int k=0;k<=9;++k){
				dp[j][i]+=dp[(9*n+j-k)%n][i-1];
			}
			dp[j][i]%=mod;
		}
	}
	ans=(mod-1+dp[0][l-1])%mod;
	int cnt=0;
	for(int j=1;j<=s[0]-'0';++j) ans+=dp[(9*n-j)%n][l-1],ans%=mod;
	for(int i=l;i>=2;--i){
		cnt+=s[l-i]-'0';
		for(int j=s[l-i+1]-'0'+1;j<=9;++j)
		ans+=(mod-dp[((cnt+9)*n-cnt-j)%n][i-2]),ans%=mod;
	}
	cout<<ans<<"\n";
	return 0;
}

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

int main() {
	int n;
	cin >> n;
	
	int x,y,t;
	int x_now=0, y_now=0, t_now=0;
	for(int i=0; i<n; i++){
		cin >> t;
		cin >> x;
		cin >> y;
		
		int X=x-x_now, Y=y-y_now, T=t-t_now;
		if(X<0){X*=-1;}
		if(Y<0){Y*=-1;}
		if(X+Y<=T && (X+Y-T)%2==0){
			x_now=x; y_now=y; t_now=t;
		}else{
			cout << "No" << endl;
			return 0;
		}
	}
	
	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 256
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, Z, W = in_nn()
    A = in_nl()

    if N == 1:
        ans = abs(W - A[0])
    else:
        ans = max(abs(A[-1] - A[-2]), abs(A[-1] - W))

    print(ans)


if __name__ == '__main__':
    main()


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

public class Main {

	private static final int mod =(int)1e9+7;
	public static void main(String[] args) throws Exception  {
	      Scanner  sc=new Scanner(System.in);
	      PrintWriter out=new PrintWriter(System.out);
	  int n=sc.nextInt();
	  long k=sc.nextLong();
	  TreeMap<Integer,Long> map=new TreeMap<>();

	  for(int i=0;i<n;i++) {
	    int a=sc.nextInt();
	   int b=sc.nextInt();
	   
	   map.put(a, map.getOrDefault(a,(long) 0)+b);
	  
	     
	}
	for(int i=1;i<=100001;i++) {
	   if(map.containsKey(i)) {
	      if(map.get(i)>=k) {
	        System.out.println(i);
	  break;
	      }else {
	        k=k-map.get(i);
	      }
	   }
	  }
	}


	static boolean vis[]=new boolean[10001];
	      static long gcd(long a, long b) 
	      { 
	          if (a == 0) 
	              return b; 
	          return gcd(b % a, a); 
	      } 

static long nCr(int n,int r) {
  int dp[][]=new int[2001][2001];
  for(int i=0;i<2001;i++) {
    dp[0][i]=0;
  }
  for(int i=0;i<2001;i++) {
    dp[i][0]=1;
  }
  for(int i=1;i<2001;i++) {
    for(int j=1;j<2001;j++) {
      if(i==j) {
        dp[i][j]=1;
      }else {
        dp[i][j]=dp[i-1][j-1]+dp[i][j-1];
      }
    }
  }
  return dp[n][r];
}


      
}
class pair implements Comparable<pair>{
  int wt,val;
  pair(int wt,int val){
    this.wt=wt;
    this.val=val;
    
  }

  @Override
  public int compareTo(pair o) {
   
    return this.wt-o.wt;
  }
}

Measured memory_bytes: 65100
{-# LANGUAGE BangPatterns #-}

module Main where

import Control.Applicative
import Control.Monad
import Data.List
import Data.Maybe
import qualified Data.ByteString.Char8 as B

solve :: B.ByteString -> B.ByteString -> Bool
solve ss ts = iter [] [] (B.zip ss ts)
  where
    iter :: [Char] -> [Char] -> [(Char, Char)] -> Bool
    iter _   _   [] = True
    iter !ds !dt ((s, t):us)
        | isNothing ms && isNothing mt = iter (s:ds) (t:dt) us
        | isJust ms && isJust mt       =
            if fromJust ms == fromJust mt
            then iter ds dt us
            else False
        | otherwise                    = False
      where
        ms = s `elemIndex` ds
        mt = t `elemIndex` dt

main :: IO ()
main = do
    ss <- B.getLine
    ts <- B.getLine
    if solve ss ts
        then putStrLn "Yes"
        else putStrLn "No"

Measured memory_bytes: 1660
week = ['SUN','MON','TUE','WED','THU','FRI','SAT','SUN']
s = input()
countflg = False
day = 0
for w in week:
  if countflg == True and w == 'SUN':
    print(day)
    exit()
  if s == w:
    countflg = True
  if countflg == True:
    day += 1


Measured memory_bytes: 2940
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int mod = 1000000007;
struct mint{
	ll x;
	mint(ll x = 0):x((x%mod+mod)%mod){}
	mint operator-() const{return mint(-x);}
	mint& operator+=(const mint a){
		if((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a){
		if((x += mod-a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a){
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint a) const{
		mint res(*this);
		return res+=a;
	}
	mint operator-(const mint a) const{
		mint res(*this);
		return res-=a;
	}
	mint operator*(const mint a) const{
		mint res(*this);
		return res*=a;
	}
	mint pow(ll t) const{
		if(!t) return 1;
		mint a = pow(t>>1);
		a *= a;
		if(t&1) a *= *this;
		return a;
	}
	mint inv() const{
		return pow(mod-2);
	}
	mint& operator/=(const mint a){
		return (*this) *= a.inv();
	}
	mint operator/(const mint a) const{
		mint res(*this);
		return res/=a;
	}
	bool operator==(const mint a){
		return x == a.x;
	}
};

mint dp[100005][4];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int n = s.size();
    dp[n][3] = 1;
    dp[n][0] = dp[n][1] = dp[n][2] = 0;
    for(int i = n-1; i >= 0; --i){
        for(int j = 3; j >= 0; --j){
            dp[i][j] = dp[i+1][j] * (s[i] == '?' ? 3 : 1);
            if(j < 3 && (s[i] == '?' || s[i] == "ABC"[j])){
                dp[i][j] += dp[i+1][j+1];
            }
        }
    }
    cout << dp[0][0].x << endl;
	return 0;
}

Measured memory_bytes: 3664
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N;
ll dp[3000+5][3000+5][2];
ll arr[3000+5];

/* (i, j) -> max(A[i]+(i+1, j), A[j]+(i,j-1))
solve(i, j, c) -> c*max(arr[i] + solve(i+1, j, 1-c), arr[j] + solve(i, j-1, 1-c)) +
			(1-c)*min(-arr[i] + solve(i+1, j, 1-c), -arr[j] + solve(i, j-1, 1-c));
				
ll solve(ll i, ll j, ll c, ll X, ll Y){
	if (i > j) return X-Y;
	
	//if(dp[i][j][c] != -1) return dp[i][j][c];
	
	ll ans;
	if (c)
		ans = max(solve(i+1, j, 1-c, X+arr[i], Y), solve(i, j-1, 1-c, X+arr[j], Y));
	else
		ans = min(solve(i+1, j, 1-c, X, Y+arr[i]), solve(i, j-1, 1-c, X, Y+arr[j]));
	return ans;
}*/

ll solve(ll i, ll j, ll c){
	if (i > j) return 0;
	
	if(dp[i][j][c] != -1) return dp[i][j][c];
	ll I = solve(i+1, j, 1-c);
	ll J = solve(i, j-1, 1-c);
	dp[i][j][c] = c*max(arr[i]+I, arr[j]+J) + (1-c)*min(I-arr[i], J-arr[j]);
	return dp[i][j][c];
}
			

int main(){
	cin>>N;
	for(ll i = 0;i<N;i++)cin>>arr[i];
	
	memset(dp, -1, sizeof dp);
	
	cout<<solve(0,N-1, 1)<<endl;
}	

Measured memory_bytes: 141440
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define rev(i,s,e) for(i64 (i) = (s);(i) --> (e);)
#define all(x) x.begin(),x.end()

template<class T>
static inline std::vector<T> ndvec(size_t&& n, T val) noexcept {
  return std::vector<T>(n, std::forward<T>(val));
}

template<class... Tail>
static inline auto ndvec(size_t&& n, Tail&&... tail) noexcept {
  return std::vector<decltype(ndvec(std::forward<Tail>(tail)...))>(n, ndvec(std::forward<Tail>(tail)...));
}

int main() {
  i64 N, C;
  cin >> N >> C;
  vector<i64> X(N), V(N);
  rep(i,0,N) cin >> X[i] >> V[i];

  vector<i64> f1, f2, r1, r2;
  f1.push_back(0);
  f2.push_back(0);
  r1.push_back(0);
  r2.push_back(0);
  {
    i64 sum = 0;
    rep(i,0,N) {
      sum += V[i];
      f1.push_back(std::max(f1.back(), sum - X[i]));
      f2.push_back(std::max(f2.back(), sum - X[i] * 2));
    }
  }
  {
    i64 sum = 0;
    for(i64 i = N; i --> 0;) {
      sum += V[i];
      r1.push_back(std::max(r1.back(), sum - (C - X[i])));
      r2.push_back(std::max(r2.back(), sum - (C - X[i]) * 2));
    }
  }

  i64 MAX = 0;
  for(i64 i = 0;i <= N;i++) {
    MAX = std::max(MAX, f1[i] + r2[N - i]);
    MAX = std::max(MAX, f2[i] + r1[N - i]);
  }
  cout << MAX << endl;
}


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

int a[21];
int L;


int comp1(const void* p1, const void* p2){//??????
	char* c1=(char*)p1;
	char* c2=(char*)p2;
	return *c1-*c2;
}
int comp2(const void* p1, const void* p2){//??????
	char* c1=(char*)p1;
	char* c2=(char*)p2;
	return *c2-*c1;
}

int next(int a){
	char str[7];
	sprintf(str,"%06d",a);
	qsort(str,6,sizeof(char),comp1);
	int small=atoi(&str[6-L]);
	qsort(str,6,sizeof(char),comp2);
	str[L]=0;
	int large=atoi(&str[0]);
	return large-small;
}

void solve(){
	int i,j;
	//printf("a[0]:%d\n",a[0]);
	for(i=1;i<21;i++){
		a[i]=next(a[i-1]);
		//printf("a[%d]:%d\n",i,a[i]);
	}
	for(i=1;i<21;i++){
		for(j=0;j<i;j++){
			if(a[i]==a[j]){
				printf("%d %d %d\n",j,a[i],i-j);
				return;
			}
		}
	}
}

int main(void){
	
	while(scanf("%d %d",&a[0],&L),L){
		solve();
	}

	return 0;
}

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

int main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(0);
	long long n;
	cin >> n;
	string s;
	while (true) {
		s += --n % 26 + 'a';
		n /= 26;
		if (n == 0)
			break;
	}
	reverse(s.begin(), s.end());
	cout << s << '\n';
}



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

using namespace std;

#define all(x) x.begin(), x.end()
typedef vector <int> vi;
typedef pair<int,int> ii;
typedef long long ll;

const int mod = 1e9 + 7;
const ll inf = 3e18 + 5;

int add(int a, int b) { return (a += b) < mod ? a : a - mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }

ll dp[1000105];
int a[105], b[105], n;

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

	int w;
	cin >> n >> w;
	int mx = 0;
	for(int i = 0; i < n; i++){
		cin >> a[i] >> b[i];
		mx += b[i];
	}
	vector <ll> dp(mx + 1, inf);
	dp[0] = 0;
	for(int i = 0; i < n; i++){
		for(int j = mx - b[i]; j >= 0; j--){
			dp[j + b[i]] = min(dp[j + b[i]], dp[j] + a[i]);
		}
	}
	ll res = 0;
	for(int i = 0; i <= mx; i++){
		if(dp[i] <= w)
			res = i;
	}
	cout << res;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
const int max_n=200005;
typedef long long ll;
struct Node{
    ll x,f;
    bool operator <(Node p){
        return x==p.x?f<p.f:x<p.x;
    }
};
map<int,int> id;
int nid=0;
int gid(int x){
    if(id.count(x))return id[x];
    return id[x]=nid++;
}
vector<Node> v[max_n];
int x,d,n;
int main(){
    scanf("%d%d%d",&n,&x,&d);
    if(d<0)d=-d,x=-x;
    if(d==0){
        if(x==0)printf("1\n");
        else printf("%d\n",n+1);
    }
    else{
        //v[gid(0)].push_back({0,0});
        v[gid(0)].push_back({0,1});
        v[gid(0)].push_back({1,-1});
        for(int i=1;i<=n;i++){
            ll t=1ll*i*x;
            int r=(t%d+d)%d;
            t=(t-r)/d;
            //v[gid(r)].push_back({t+1ll*i*(i+1)/2,t+1ll*i*(i+1)/2+1ll*i*(n-i)});
            v[gid(r)].push_back({t+1ll*i*(i-1)/2,1});
            v[gid(r)].push_back({t+1ll*i*(i-1)/2+1ll*i*(n-i)+1,-1});
        }
        ll ans=0;
        for(int i=0;i<nid;i++){
            sort(v[i].begin(),v[i].end());
            ll pre;
            int cnt=0;
            for(auto p:v[i]){
                if(p.f==1){
                    if(cnt==0)pre=p.x;
                    cnt++;
                }
                else{
                    if(cnt==1)ans+=p.x-pre;
                    cnt--;
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

Measured memory_bytes: 23680
using System;
class seito{
		static int []b=new int[4];
        public	static void hito(int c,string d){
		
		if(d=="A")
			b[0]++;
		else if(d=="B")
			b[1]++;
		else if(d=="AB")
			b[2]++;
		else if(d=="O")
			b[3]++;
	}
	public static void gh(){
		Console.WriteLine(b[0]+"\n"+b[1]+"\n"+b[2]+"\n"+b[3]);
	}
}
class aoj{
	static void Main(){
		seito seito = new seito();
		while(true){
			string a=Console.ReadLine();
			if(String.IsNullOrEmpty(a))break;
			string []j=a.Split(',');
			int c=int.Parse(j[0]);
			string d=j[1];
			seito.hito(c,d);
		}
		seito.gh();
	}
}

Measured memory_bytes: 9176
import sys
from bisect import bisect_left as bi_l, bisect_right as bi_r

a, b = map(int, sys.stdin.readline().split())

def main():
    palindromic_nums = []
    for i in range(1, 10):
        for j in range(10):
            for k in range(10):
                x = [i, j, k, j, i]
                palindromic_nums.append(int(''.join(list(map(str, x)))))

    return bi_r(palindromic_nums, b) - bi_l(palindromic_nums, a)
                
if __name__ == '__main__':
    ans = main()
    print(ans)

Measured memory_bytes: 3064
#k = int(input())
a, b, h, m = map(int, input().split())
#al = list(map(int, input().split()))
#al=[list(input()) for i in range(h)]
import math
thetah = 30*h+(m/60)*30
thetam = 6*m
theta=abs(thetah-thetam)
theta=min(theta,360-theta)
ans=math.sqrt(a*a+b*b-2*a*b*math.cos(math.radians(theta)))
print('{:.11f}'.format(ans))


Measured memory_bytes: 9428
#include<iostream>
using namespace std;
#define MAX 100000

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

int main(){
    int H, i, A[MAX+1]; //1-オリジンのため+1

    cin >> H;
    for(i=1; i<=H; i++) cin >> A[i];

    for(i=1; i<=H; i++){
        cout << "node " << i << ": key = " << A[i] << ", ";
        if(parent(i) >= 1) cout << "parent key = " << A[parent(i)] << ", ";
        if(left(i) <= H) cout << "left key = " << A[left(i)] << ", ";
        if(right(i) <= H) cout << "right key = " << A[right(i)] << ", ";
        cout << endl;
    }

    return 0;
}



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

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


int main(){
ll x;
cin>>x;
ll ans=x/5.5;
if(2*x%11==0||2*(x+5)%11==0)
cout<<ans<<endl;
else
{
  cout<<ans+1<<endl;
}


  return 0;
}


Measured memory_bytes: 256
n,a,b = map(int,input().split())

k = b-a
if k %2 == 0:
    print(k//2)
else:
    p = a-1
    bb = b-(a-1)

    p += 1
    bb -= 1
    
    res = p + (bb-1)//2


    p = n-b
    aa = a+(n-b)

    p += 1
    aa += 1

    res = min(res,p + (n-aa)//2)
    print(res)


Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,i,s=0,a[200110];
    cin >> n;
    for(i=0;i<n;i++)
    {
        cin >> a[i];
    }
    sort(a,a+n);
    for(i=0;i<n;i++)
    {
        if(a[i]!=a[i+1])
        {
            s++;
        }
    }
    if(s==n)
    {
        cout << "YES" << endl;;
    }
    else
    {
        cout << "NO" << endl;
    }
    return 0;
}


Measured memory_bytes: 1792
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

LL N, L, a[112345];
bool isBroken[112345];
LL res[112345], ans;

int main()
{
	memset(isBroken, false, sizeof(isBroken));
	in >> N >> L;
	rep(i, N) { in >> a[i + 1]; }

	bool flag = true;
	while (flag)
	{
		flag = false;
		rep(i, N)
		{
			if (!isBroken[i + 1])
			{
				flag = true;
				if (a[i] < a[i + 1] && a[i + 1] > a[i + 2])
				{
					isBroken[i + 1] = true;
					res[i + 1] = (L - a[i + 1]) + std::max(res[i], res[i + 2]);
					a[i + 1] = 0;
				}
			}
		}
	}
	rep(i, N) { ans = std::max(ans, res[i + 1]); }

	out << ans << std::endl;
	return 0;
}

Measured memory_bytes: 4736
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>
#include <utility>


using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// const ll INF = 1LL <<60;
const int INF = 10000;

//最小公倍数
ll gcd(ll x, ll y) {
  ll tmp = 0;
  if (x < y){
    tmp=x;
    x=y;
    y=tmp;
  }
  while (y > 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//最大公倍数
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}

//階乗
ll kaijo(ll k){
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum *= i;
        sum%=1000000000+7;
    }
    return sum;
}

//for(int i = ; i < ; i++){}

ll lmax(ll s,ll t){
  if(s>t){
    return s;
  }
  else{
    return t;
  }
}

ll lmin(ll s,ll t){
  if(s<t){
    return s;
  }
  else{
    return t;
  }
}
// ここから開始

int main(){
  int a[3];
  cin>>a[0]>>a[1]>>a[2];
  sort(a,a+3);
  if(a[0]==a[1]+a[2]||a[0]+a[1]==a[2]) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):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; }
/*操作する→全部チェック→TLE
どうするっぺ
 */
int main(){
    int n;cin>>n;
    vector<int> a(n),v(n);
    rep(i,n){
        cin>>a[i];
        v[i]=a[i];
    }
    sort(ALL(v));
    v.erase(unique(ALL(v)),v.end());    
    int ans=v.size();
    if(ans%2==0) ans--;
    cout<<ans<<endl;
    return 0;   
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
#define ll long long int
#define pii pair<ll,ll>
#define mp make_pair
#define pb push_back
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define M 500005
#define mod 1000000007
#define inf LLONG_MAX
#include<string>
using namespace std;
ll n,dp[100008][3],a[100008],b[100008],c[100008];
ll f(ll i,ll x)
{
	if(i==n)
		return 0;
	if(dp[i][x]==-1)
	{
		dp[i][x]=0;
		ll temp=0;
		if(x==0)
		{
			temp=a[i]+f(i+1,1);
			temp=max(temp,a[i]+f(i+1,2));
		}
		else if(x==1)
		{
			temp=b[i]+f(i+1,0);
			temp=max(temp,b[i]+f(i+1,2));
		}
		else
		{
			temp=c[i]+f(i+1,1);
			temp=max(temp,c[i]+f(i+1,0));
		}
		dp[i][x]=temp;
	}
	return dp[i][x];
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll p,q,r;
	cin>>n;
	for(ll i=0;i<n;i++)
		cin>>a[i]>>b[i]>>c[i];
	memset(dp,-1,sizeof(dp));
	p=f(0,0);
	memset(dp,-1,sizeof(dp));
	q=f(0,1);
	memset(dp,-1,sizeof(dp));
	r=f(0,2);
	cout<<max(p,max(q,r))<<endl;
	return 0;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
#define INF INT_MAX
#define ll  long long
#define ull unsigned long long
#define rep(i,n) for(ll i=0; i<n; ++i)
#define FOR(i, s, e) for(ll i=s; i<e; ++i)
#define MOD 1000000007
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if(a>b) {a=b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) { if(a<b) {a=b; return true;} return false;}

int main() {
  ll N; cin >> N;
  string s, t;
  cin >> s >> t;
  ll k = 0;
  for(ll i=0; i<s.size(); ++i) {
    k = 0;
    for(ll j=0; j+i<s.size(); ++j) {
      if(s[i+j] == t[j]) {
        if(i+j == s.size()-1) {
          k = j+1;
          goto end;
        }
      } else {
        break;
      }
    }
  }
  end:
  cout << N+(N-k) << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
    int S,h,m,s;
    scanf("%d",&S);
    h=S/3600;
    m=(S-3600*h)/60;
    s=S-3600*h-60*m;
    printf("%d:%d:%d\n",h,m,s);
    return 0;
}

Measured memory_bytes: 592
s=str(input())
ans=0
for i in range(1<<(len(s)-1)):
  st=s[0]
  for j in range(len(s)-1):
    if ((i >> j) & 1) == 1:
      st+="+"+s[j+1]
    else:
      st+=s[j+1]
  ans+=eval(st)
print(ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define sz(arr) (int)arr.size()
#define all(arr) arr.begin(), arr.end()

using namespace std;
typedef long long ll;

void _cin() {}
template <class Head, class... Tail>
void _cin(Head&& head, Tail&&... tail) {
  cin >> head;
  _cin(forward<Tail>(tail)...);
}

#define Cin(T, ...) \
  T __VA_ARGS__;    \
  _cin(__VA_ARGS__)

int main() {
  Cin(string, s);

  sort(all(s));

  bool dup = false;
  for (int i = 0; i < sz(s) - 1; ++i) {
    if (s[i] == s[i + 1]) dup = true;
  }

  puts(!dup ? "yes" : "no");

  return 0;
}

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

int main() {
    int M;
    cin >> M;
    ll S = 0, D = 0;
    rep(i, M) {
        ll d, c;
        cin >> d >> c;
        D += c;
        S += d * c;
    }
    cout << (D-1) + (S - 1)/9 << endl;
}


Measured memory_bytes: 256
N = int(input())
s = []
ans = 0
mydict = {}
for i in range(N):
    s = "".join(sorted(list(input())))
    if (s in mydict.keys()):
        ans += mydict[s]
        mydict[s] += 1
    else:
        mydict[s] = 1
print(ans)

Measured memory_bytes: 17808
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
ab = [inpl() for i in range(m)]

ab.sort(key=lambda x:x[1])
ab.sort()
res = 0
now = 0
l = 0
r = 0
for i in range(m):
    if ab[i][0] == now:
        continue
    if ab[i][0] >= r:
        res += 1
        r = ab[i][1]
    elif ab[i][1] < r:
        r = ab[i][1]
    l = ab[i][0]
    now = l
print(res)

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

int main()
{
    int n;
    cin >> n;
    
    vector<int> vec(n);
    for (int i = 0; i < n; ++i) cin >> vec[i];
    
    int counter = 0;
    
    for (int i = 0; i < n; i += 2) {
        if (vec[i] % 2 == 1) ++counter;
        else continue;
    }
    
    cout << counter << "\n";
    
    return 0;
}


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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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




void solve() {
    int W, H, N; cin >> W >> H >> N;
    int x1=0, x2=W, y1=0, y2=H;
    rep(i, N){
        int x, y, a; cin >> x >> y >> a;
        if(a == 1){
            x1 = max(x1, x);
        }else if(a == 2){
            x2 = min(x2, x);
        }else if(a == 3){
            y1 = max(y1, y);
        }else{
            y2 = min(y2, y);
        }
    }
    int x = x2-x1;
    int y = y2-y1;
    int res = 0;
    if(x>0 && y>0) res = x*y;
    cout << res << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


Measured memory_bytes: 4352
import sys
readline = sys.stdin.readline
write = sys.stdout.write
sys.setrecursionlimit(10**5)
def solve():
    N, M = map(int, readline().split())
    G = [[] for i in range(N)]
    for i in range(N-1):
        a, b, c = map(int, readline().split())
        G[a-1].append((b-1, c))
        G[b-1].append((a-1, c))
    *C, = map(int, readline().split())
    def dfs(v, p, s, A):
        m = 0
        for w, d in G[v]:
            if w == p:
                continue
            r = dfs(w, v, s, A) + s*d
            if m < r:
                m, r = r, m
            if r > 0:
                A.append(r)
        return m
    A = []
    for i in range(N):
        r = dfs(i, -1, C[i], A)
        if r > 0:
            A.append(r)
    A.sort(reverse=1)
    write("%d\n" % sum(A[:M]))
solve()


Measured memory_bytes: 196056
h, w, d = map(int, input().split())
x = []
z = [None for i in range(h * w)]
for i in range(h):
    x.append(list(map(int, input().split())))
    for j in range(w):
        z[x[i][j] - 1] = [i + 1, j + 1]

s = [None for _ in range(d)]
for i in range(min(d, h * w - d + 1)):
    a = z[max(0, i - 1)]
    b = z[d + i - 1]
    s[i] = [abs(a[0] - b[0]) + abs(a[1] - b[1])]
    j = 1
    while(True):
        if d * (j + 1) + i <= h * w:
            a = z[d * j + i - 1]
            b = z[d * (j + 1) + i - 1]
            s[i].append(s[i][-1] + abs(a[0] - b[0]) + abs(a[1] - b[1]))
            j += 1
        else:
            break

Q = int(input())
ans = [None for _ in range(Q)]
for i in range(Q):
    L, R = map(int, input().split())
    if L == R:
        ans[i] = 0
    elif L // d - 1 < 0:
        ans[i] = s[R % d][R // d - 1]
    else:
        ans[i] = s[R % d][R // d - 1] - s[L % d][L // d - 1]
for i in range(Q):
    print(ans[i])

Measured memory_bytes: 25372
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cassert>
#include <functional>
#include <string>
using namespace std;

int main(){
  int N; cin >> N;
  vector<long long> L(N+1);
  L[0] = 2;
  L[1] = 1;
  for(int i = 2; i <= N; i++) L[i] = L[i - 1] + L[i - 2];
  cout << L[N] << endl;
}


Measured memory_bytes: 256
// #include {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}

const int N = 303;
int H , W;
char s[N][N];
int cost[N][N] , f[N][N];

int solve(string&s,string&t){
  int n = sz(s);
  rep(i,0,n+1) rep(j,0,n+1) {
    if(i == 0 || j == 0)
      cost[i][j] = f[i][j] = 0;
    else
      cost[i][j] = cost[i-1][j-1] + (s[i-1] == t[j-1]) ,
        f[i][j] = min(f[i-1][j] , f[i][j-1]) + cost[i][j];
  }
  return f[n][n];
}

int main(){
  scanf("%d%d",&H,&W);
  rep(i,0,H) scanf("%s",s[i]);
  int ans = 0;
  rep(i,1,W) {
    string A = "" , B = "";
    rep(j,0,H) A += s[j][i-1] , B += s[j][i];
    ans += solve(A , B);
  }
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Linq;

namespace easy_Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] AB = Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
            Console.WriteLine(AB[0]>8 ||AB[1]>8?":(":"Yay!");
        }   
            // float[] ABN = Array.ConvertAll(Console.ReadLine().Split(),float.Parse);
            // long[] NK = Array.ConvertAll(Console.ReadLine().Split(),long.Parse);
            // long N = NK[0];
            // long K = NK[1];
            // long K = long.Parse(Console.ReadLine());
            // int[] abc = Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
            // string S = Console.ReadLine();
            // int x = int.Parse(Console.ReadLine());
            // int b = int.Parse(Console.ReadLine());
            // int N = int.Parse(Console.ReadLine());
            // float N = float.Parse(Console.ReadLine());
            // string c = Console.ReadLine();
            // string B = Console.ReadLine();
            // string[] s = Console.ReadLine().Split();
            // var s = (new string[] { Console.ReadLine(), Console.ReadLine(), Console.ReadLine() }).Select(float.Parse);
            // float[] a = Array.ConvertAll(Console.ReadLine().Split(),float.Parse);
            // var X = Console.ReadLine();
            // int[,] abcd = new int[NMQ[2],4];
            // int[] A = new int[NMQ[0]];
            // int[] A_num = new int[NMQ[0]];
            // long[] s=Array.ConvertAll(Console.ReadLine().Split(),long.Parse);
            // var hs=new Dictionary<long,long>();
            // for(int i=0;i<s[0];i++){
            //     long[] q=Array.ConvertAll(Console.ReadLine().Split(),long.Parse);
            //     if(hs.ContainsKey(q[0])){hs[q[0]]+=q[1];}
            //     else{hs.Add(q[0],q[1]);}
            // }
        
        // //最小公倍数
        // static long Lcm(long a, long b)
        // {
        //     return a/Gcd(a,b)*b;
        // }

        // //最大公約数
        // static long Gcd(long m, long n)
        // {
        //     if(n==0)return m;
        //     return Gcd(n,m%n);
        // }
    }
}


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

int n;
int a[100000][4];
int dp[100000][4];

int solve(int i, int flag)
{
	if (i == n)
	{
		return 0;
	}

	if (dp[i][flag] != -1)
	{
		return dp[i][flag];
	}

	int value = 0;
	if (flag == 0)
	{
		value = max(max(value, a[i][1] + solve(i + 1, 1)), max(a[i][2] + solve(i + 1, 2), a[i][3] + solve(i + 1, 3)));
	}
	else if (flag == 1)
	{
		value = max(value, max(a[i][2] + solve(i + 1, 2), a[i][3] + solve(i + 1, 3)));
	}
	else if (flag == 2)
	{
		value = max(value, max(a[i][1] + solve(i + 1, 1), a[i][3] + solve(i + 1, 3)));
	}
	else
	{
		value = max(value, max(a[i][1] + solve(i + 1, 1), a[i][2] + solve(i + 1, 2)));
	}
	return dp[i][flag] = value;
}

int main()
{
	cin >> n;
	//int a[n], b[n], c[n];
	for (int i = 0; i < n; i++)
	{
		cin >> a[i][1] >> a[i][2] >> a[i][3];
	}
	memset(dp, -1, sizeof(dp));
	cout << solve(0, 0);
	return 0;
}

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

int main(){
    int a,b,c;
    cin>>a>>b>>c;
    cout<<c-min(c,a-b);
    return 0;
}

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

vector<string> action;
int N;
int ans;

int main(void){
  while(true){
    cin >> N;
    if(N == 0) break;
    ans = 0;
    action.clear();
    for(int i = 0; i < N; i++){
      string tmp;
      cin >> tmp;
      action.push_back(tmp);
    }

    for(int i = 0; i < N - 1; i += 2){
      if(action[i] == "lu" && action[i+1] == "ru") ans++;
      else if(action[i] == "ru" && action[i+1] == "lu") ans++;
      else if(action[i] == "ld" && action[i+1] == "rd") ans++;
      else if(action[i] == "rd" && action[i+1] == "ld") ans++;
    }
    
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define MOD (int)(1e9+7)
#define ceil(x, y) (x%y==0? (x/y) : (x/y+1))
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define FOR1(i, N) for(int i = 1; i <= N; ++i)
#define vi vector <int>
#define pii pair <int, int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define mset(a, v) memset(a, v, sizeof(a))
#define all(v) (v).begin(), (v).end()
#define INF 2e9
#define EPS 1e-9
#define PI 3.141592653589793238
#define int long long
/*#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef cc_hash_table<int, int, hash<int>> ht; // while using, comment #define int long long  */

void __print(int x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
using namespace std;
#define MAX 200000
multiset<int> kind[MAX+1]; // kind[i] has multiset representing kg i
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
    	freopen("in2.txt", "r", stdin);
    	freopen("out.txt", "w", stdout);
    #endif

	int T=1;
	//cin >> T;
	FOR1(tp, T)
	{
		//cout << "Case #" << tp << ": ";
		int a, b, c, d; cin >> a >> b >> c >> d;
		// 0-Taka, 1-Aoki
		int p = 0;
		while(a > 0 and c > 0){
			if(p == 0) c -= b;
			else a -= d;
			p = p^1;
		}
		if(p == 1) cout << "Yes";
		else cout << "No";
		cout << '\n';
	}
	return 0;
}


Measured memory_bytes: 13028
#include <stdio.h>

int main()
{
    int n,arr[200001]={},i,j,p;
    scanf("%d",&n);
    for(i=1;i<=n-1;i++) {
        scanf("%d",&p);
        arr[p]++;
    }
    for(j=1;j<=n;j++) {
        printf("%d\n",arr[j]);
    }

    return 0;
}

Measured memory_bytes: 2516
#![allow(unused_parens)]
#![allow(unused_imports)]
#![allow(non_upper_case_globals)]
#![allow(non_snake_case)]
#![allow(unused_mut)]
#![allow(unused_variables)]
#![allow(dead_code)]

use itertools::Itertools;
use proconio::input;
use proconio::marker::{Chars, Usize1};

#[allow(unused_macros)]
#[cfg(debug_assertions)]
macro_rules! mydbg {
    //($arg:expr) => (dbg!($arg))
    //($arg:expr) => (println!("{:?}",$arg));
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
      }
}
#[cfg(not(debug_assertions))]
macro_rules! mydbg {
    ($($arg:expr),*) => {};
}

macro_rules! echo {
    ($($a:expr),*) => {
          $(println!("{}",$a))*
      }
}

use std::cmp::*;
use std::collections::*;
use std::ops::{Add, Div, Mul, Sub};

#[allow(dead_code)]
static INF_I64: i64 = 92233720368547758;
#[allow(dead_code)]
static INF_I32: i32 = 21474836;
#[allow(dead_code)]
static INF_USIZE: usize = 18446744073709551;
#[allow(dead_code)]
static M_O_D: usize = 1000000007;
#[allow(dead_code)]
static PAI: f64 = 3.1415926535897932;

trait IteratorExt: Iterator {
    fn toVec(self) -> Vec<Self::Item>;
}

impl<T: Iterator> IteratorExt for T {
    fn toVec(self) -> Vec<Self::Item> {
        self.collect()
    }
}

trait CharExt {
    fn toNum(&self) -> usize;
    fn toAlphabetIndex(&self) -> usize;
    fn toNumIndex(&self) -> usize;
}
impl CharExt for char {
    fn toNum(&self) -> usize {
        return *self as usize;
    }
    fn toAlphabetIndex(&self) -> usize {
        return self.toNum() - 'a' as usize;
    }
    fn toNumIndex(&self) -> usize {
        return self.toNum() - '0' as usize;
    }
}

trait VectorExt {
    fn joinToString(&self, s: &str) -> String;
}
impl<T: ToString> VectorExt for Vec<T> {
    fn joinToString(&self, s: &str) -> String {
        return self
            .iter()
            .map(|x| x.to_string())
            .collect::<Vec<_>>()
            .join(s);
    }
}

trait StringExt {
    fn get_reverse(&self) -> String;
}
impl StringExt for String {
    fn get_reverse(&self) -> String {
        self.chars().rev().collect::<String>()
    }
}

trait UsizeExt {
    fn pow(&self, n: usize) -> usize;
}
impl UsizeExt for usize {
    fn pow(&self, n: usize) -> usize {
        return ((*self as u64).pow(n as u32)) as usize;
    }
}

fn main() {
    input! {
       N: usize,
    }

    let mut a = vec![];
    for _ in 0..N {
        input! {
            c:usize,
            d:usize,
        }
        if c == d {
            a.push(true);
        } else {
            a.push(false);
        }
    }

    for i in 0..N - 2 {
        if a[i] && a[i + 1] && a[i + 2] {
            echo!("Yes");
            return;
        }
    }

    echo!("No");
}


Measured memory_bytes: 2192