akhauriyash/Code-Regression huggingface dataset:
from collections import defaultdict

n = int(input())


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


factors = defaultdict(int)
for i in range(1, n + 1):
    ps = prime_factorize(i)
    for p in ps:
        factors[p] += 1

count = 1
for p, m in factors.items():
    count *= (1 + m)
    count %= 1000000007

print(count)


Measured memory_bytes: 3316
import java.util.*;

public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String num_a = sc.next();
		String num_b = sc.next();
		int a_length = num_a.length();
		int b_length = num_b.length();
		String message = "";
		if(a_length > b_length) {
			message = "GREATER";
		} else if(a_length < b_length) {
			message = "LESS";
		} else {
			int i = 0;
			for(i = 0; i < a_length; i++) {
				int a = Integer.parseInt(num_a.charAt(i) + "");
				int b = Integer.parseInt(num_b.charAt(i) + "");
				if(a > b) {
					message = "GREATER";
					break;
				} else if(a < b) {
					message = "LESS";
					break;
				}
			}
			if(i == a_length) {
				message = "EQUAL";
			}
		}
		System.out.println(message);
	}
}

Measured memory_bytes: 21844
# 参考URL
# https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]


N, K, L = map(int, input().split())

uf_road = UnionFind(N)
uf_train = UnionFind(N)

for _ in range(K):
    a, b = map(int, input().split())
    uf_road.union(a-1, b-1)
    
for _ in range(L):
    a, b = map(int, input().split())
    uf_train.union(a-1, b-1)

from collections import defaultdict

d = defaultdict(int)
for i in range(N):
    d[(uf_road.find(i), uf_train.find(i))]+=1
    
ans = []
for i in range(N):
    ans.append(d[(uf_road.find(i), uf_train.find(i))])

print(' '.join(map(str, ans)))


Measured memory_bytes: 50144
#include <stdio.h>
#include <string.h>

void selectionSort(int len, double *a){
    int mini;
    double tmp;
    for (int i = 0; i < len; i++){
        mini = i;
        for (int j = i + 1; j < len; j++){
            if (a[j] < a[mini]){
                mini = j;
            }
        }
        if (mini != i){
            tmp = a[i];
            a[i] = a[mini];
            a[mini] = tmp;
        }
    }
}

int main(void){
    int N;
    scanf("%i", &N);
    double v[N];
    for (int i = 0; i < N; i++){
        scanf("%lf", &v[i]);
    }
    selectionSort(N, &v[0]);
    for (int i = 0; i < N - 1; i++){
        v[i + 1] = (v[i] + v[i + 1]) / 2.0;
    }
    printf("%f\n", v[N - 1]);
}

Measured memory_bytes: 128
n = int(input())
#dp[i] = iennの金を引き出すのにかかる操作回数の最小値
dp = [float('inf')]*(n+1)
dp[0] = 0
from math import log
for i in range(1,n+1):
    for j in range(int(log(n,6)+0.00001)+1):
        dp[i] = min(dp[i],dp[i-6**j]+1)
    for j in range(int(log(n,9)+0.00001)+1):
        dp[i] = min(dp[i],dp[i-9**j]+1)
print(dp[n])

Measured memory_bytes: 46160
import java.util.Scanner;

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

		int length = sc.nextInt();
		int width = sc.nextInt();
		int space = sc.nextInt();
		int ans = 0;

		ans = (length-space)/(width+space);

		System.out.println(ans);
	}

}


Measured memory_bytes: 23764
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <utility>

#define INF 9999999999
#define mod 1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define MOD(x) (x%(mod))
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int>pi;

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

int main(){
  int ans=-100000;
  int a=0,z=0;
  bool aa=false;
  string s;
  cin>>s;
  rep(i,s.size()){
    if(s[i]=='A'&&!aa){a=i;
      aa=true;
    }
    if(s[i]=='Z')z=i;
  }
  cout<<z-a+1<<endl;
  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define repi(i,x) for(auto i=(x).begin(),i##_fin=(x).end();i!=i##_fin;i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Yes":"No")
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int , int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
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 long long INFLL = 1LL<<60;
const int INF = 1<<30;
const double PI=acos(-1);
long long modpow(long long a, long long n, long long mod=(1LL<<62)){
    long long res = 1;
    while (n > 0){
        if (n & 1)
        res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
int main(){
    int n;
    ll ans=0LL;
    cin >>n;
    int a,b;
    int c;
    int e=1;
    VV dis(10,V(10,0LL));
    rep(i,10){
        rep(j,10){
            if(i==0 or j==0){
                continue;
            }
        
        if(i==j and i <= n){
            dis[i][j]++;
          //  clog<<"+ 1";
        }   

        c=i+j*10;
        if(c <=n){
            dis[i][j]++;
          //  clog << "+ 1";
        }
        c=(c-i)*10+i;
        e=1;
        while(c <=n){
            //c=(c-a)*10+c
            if(n >=c+10*(modpow(10,e)-1)){
                dis[i][j]+=modpow(10,e);
           //     clog<<" +"<<modpow(10,e);
            }else{
           //     clog<<" ("<<n-c<<")";
                dis[i][j]+=1+(n-c)/10;
          //      clog << " +" <<1+ (n - c ) / 10;
            }
            c = (c - i) * 10 + i;
            e++;

        }
     //   clog<<" ::"<<j<<" "<<i<<" "<<dis[i][j]<<endl;
        }
    }
    reps(i,9){
        reps(j,9){
            ans+=dis[i][j]*dis[j][i];
        }
    }
    cout<<ans<<endl;
}
/*
1, 11 ,1o1(10),1oo1 (100)
21, 2o1(10) ,2oo1(2)
*/

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

int main(){
    
    
    int x;
    cin>>x;
    
    int h = x / 3600;
    int m = (x / 60) % 60;
    int s = x % 60;
    cout<<h<<":"<<m<<":"<<s<<endl;
}


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

char s[100100];
long long cnt[32];
long long ans = 1;

signed main () {

    int n;
    scanf("%d", &n);
    scanf("%s", s );
    for ( int i = 0; i < n; i++ ) {
        cnt[s[i]-'a']++;
    }
    for ( int i = 0; i < 32; i++ ) {
        ans *= ( cnt[i] + 1 );
        ans %= 1000000007;
    }
    printf("%d\n", ans-1);

    return 0;
}

Measured memory_bytes: 384
#include <stdio.h>

int main() {

	int n;
	scanf("%d", &n);

	int arr[n];
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	int max = -1001001001;
	int min = 1001001001;
	long int sum = 0;
	for (int i = 0; i < n; i++) {
		if (arr[i] > max) max = arr[i];
		if (arr[i] < min) min = arr[i];
		sum += (long)arr[i];
	}

	printf("%d %d %ld\n", min, max, sum);

	return 0;
}




Measured memory_bytes: 2072
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using Console = System.Console;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var r = Console.ReadLine().Split().Select(int.Parse).OrderBy(x => x).ToArray();
            var startVal = r[N / 2 - 1];
            var endVal = r[N / 2];
            Console.WriteLine(endVal - startVal);
        }

    }
}

Measured memory_bytes: 21600
#include <stdio.h>
int main (void)
{
	int a,b,c,X;
	scanf("%d",&a);
	scanf("%d",&b);
	scanf("%d",&c);
	if(a > b){
		X=b;
		b=a;
		a=X;
	}
	else{}
	if(b > c){
		X=c;
		c=b;
		b=X;
	}
	else{}
	if(a > b){
		X=b;
		b=a;
		a=X;
	}
	else{}
	printf("%d %d %d\n",a,b,c);
	return 0;
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e3+10;
struct edge{int v,nxt;}e[maxn<<1];
int head[maxn],ecnt=0;
void add(int u,int v)
{
    e[++ecnt]=(edge){v,head[u]},head[u]=ecnt;
    e[++ecnt]=(edge){u,head[v]},head[v]=ecnt;
}
int n,val[maxn];
bool dfs(int u)
{
    for(int i=head[u];~i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(val[v]>=val[u])continue;
        if(!dfs(v))return true;
    }
    return false;
}
int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&val[i]);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    for(int i=1;i<=n;i++)if(dfs(i))printf("%d ",i);
}

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

int main() {
    int N; cin >> N;
    int cnt = 0;
    bool ok = false;
    for (int i = 0; i < N; ++i) {
        int d1, d2; cin >> d1 >> d2;
        if (d1 == d2) cnt++;
        else cnt = 0;
        if (cnt == 3) {
            ok = true;
            break;
        }
    }
    if (ok) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


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

using namespace std;
using ll = long long;

int main() {
  ll N;
  cin >> N;
  ll A[5];
  for (int i = 0; i < 5; ++i) {
    cin >> A[i];
  }
  ll min = A[0];
  ll a = N/A[0];
  if(N%A[0]!=0)
    a++;
  ll b = 1;
  if(A[0]>A[1] && min > A[1]){
    min = A[1];
    ll nokori = N-A[1]*(a-1);
    b = nokori/A[1];
    if(nokori%A[1]!=0)
      b++;
  }
  ll c = 1;
  if(A[1]>A[2] && min > A[2]){
    min = A[2];
    ll nokori = N-A[2]*(a-1+b-1);
    c = nokori/A[2];
    if(nokori%A[2]!=0)
      c++;
  }
  ll d = 1;
  if(A[2]>A[3] && min > A[3]){
    min = A[3];
    ll nokori = N-A[3]*(a-1+b-1+c-1);
    d = nokori/A[3];
    if(nokori%A[3]!=0)
      d++;
  }
  ll e = 1;
  if(A[3]>A[4] && min > A[4]){
    min = A[4];
    ll nokori = N-A[4]*(a-1+b-1+c-1+d-1);
    e = nokori/A[4];
    if(nokori%A[4]!=0)
      e++;
  }
  cout << a+b+c+d+e << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  
  if (n % 2 == 1) {
    cout << "No" << endl;
  }
  else {
    for (int i = 0; i < n / 2; i++) {
      if (s[i] != s[n / 2 + i]) {
        cout << "No" << endl;
        break;
      }
      if (i == n / 2 - 1) {
        cout << "Yes" << endl;
      }
    }
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const long long mod = 1e9+7;
long long power(long long a, long long b, long long m = mod) {
    if(b < 0) {
        return power(power(a, -b), mod-2);
    }
    long long x = 1;
    while(b) {
        if(b & 1) {
            x = 1ll * x * a % m;
        }
        a = 1ll * a * a % m;
        b /= 2;
    }
    return x;
}
const int N = 3e5+9;
signed main() {  
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    

    int d, n; cin >> d >> n;
    for(int i = 0; i < n; i++) {
        int foo; cin>> foo;
        d -= foo;
    }
    if(d < 0) cout << -1 << endl;
    else cout << d << "\n";


    





    return 0;
    
}


Measured memory_bytes: 3636
import java.util.Scanner;
public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		long N = sc.nextLong();
		long M = sc.nextLong();
		
		if (M % N == 0) {
			System.out.println(M / N);
			return;
		}
		
		long end = M / N;
		long ans = 0;
		for (long i = 1; i <= end; i++) {
			if ((M - i * (N-1)) % i == 0) {
				ans = i;
			}
			
			if (i * N > M) {
				break;
			}
		}
		
		System.out.println(ans);
	}
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
#define ll                      long long
#define pb                      push_back
#define rep(i,a,b,c)            for(ll i=(a);i<=(b);i+=(c))
#define repb(i,a,b,c)           for(ll i=(a);i>=(b);i-=(c))
#define MOD                     1000000007
#define inf                     3e18
#define ld                      long double
#define mp                      make_pair
#define vpll                    vector<pair<ll,ll> >
#define vll                     vector<ll>
#define vld                     vector<ld>
#define vvll                    vector<vector<ll>>
#define vvld                    vector<vector<ld>>
#define pll                     pair<ll,ll>
#define vvpll                   vector<vector<pair<ll,ll>>>
#define pqll                    priority_queue<ll>
#define mll                     map<ll,ll>
#define mlc                     map<ll,char>
#define um                      unordered_map
#define umll                    um<ll,ll>
#define umlc                    um<ll,char>
#define all(x)                  x.begin(),x.end()
#define fi                      first
#define se                      second
#define ln                      cout<<"\n";
#define endl                    "\n"
#define test                    ll T;cin>>T;while(T--)
#define isvowel(a)              (a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
#define fastIO                  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define show(w,size)            for(ll i=0;i<size;i++) cout<<w[i]<<" ";
#define prll(a)                 cout<<a<<"\n";
#define mset(dp,no)             memset(dp,no,sizeof(dp))
#define input(a,n)              rep(i,0,n-1,1) cin>>a[i];
#define countbit                __builtin_popcount                                           //Number of setbits in decimal notation
#define lb(v,cur)               lower_bound(all(v),cur)-v.begin()
#define ub(v,cur)               upper_bound(all(v),cur)-v.begin()
#define db(...)                 __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 <<'\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}
long long pows(long long a, long long b) {
  long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
ll powm(ll x,ll y,ll m=MOD){x=x%m;ll res=1;while(y){if(y&1)res=res*x;res%=m;y=y>>1;x=x*x;x%=m;}return res;}
ll modInverse(ll a, ll m=MOD){return powm(a,m-2,m);}
int main()
{
fastIO
ll n,m,i,j,k,x,y,z,t,e,f,p,q,g,l,r,o,w,h,count1=0,prod=1,a,b,c,d,index,x1,x2,y1,y2,diff,ans=0,sum=0,sum1=0,sum2=0,flag=0,flag1=0,flag2=0;
string s,s1,s2;
cin>>n;
ll maxi=0;
for(i=0;i<n;i++)
{
  cin>>a>>b;
  if(a==b)
  {
    count1++;
  }
  else
  {
    count1=0;
  }
  maxi=max(maxi,count1);
}
if(maxi>=3)
{
  cout<<"Yes";
}
else
{
  cout<<"No";
}
}


Measured memory_bytes: 3668
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

class KmpSearch:
  def __init__(self, word):
    self.word = word
    self.table = [0] * (len(word) + 1)
    self.table[0] = -1
    i, j = 0, 1
    while j < len(self.word):
      matched = self.word[i] == self.word[j]
      if not matched and i > 0:
        i = self.table[i]
      else:
        if matched:
          i += 1
        j += 1
        self.table[j] = i
  def search(self, text):
    table = self.table
    word = self.word
    i, p = 0, 0
    res = []
    while i < len(text):
      if text[i] == word[p]:
        i += 1
        p += 1
      elif p == 0:
        i += 1
      else:
        p = table[p]
      if p == len(word):
        res.append(i - p)
        p = table[p]
    return res

xa = [0] * N
xb = [0] * N
for i in range(N):
  xa[i] = a[i - 1] ^ a[i]
  xb[i] = b[i - 1] ^ b[i]

kmp = KmpSearch(xa)
res = kmp.search(xb + xb[: -1])
rres = []
for x in res: rres.append(((N - x) % N, a[0] ^ b[x]))
rres.sort(key = lambda x: (x[0], x[1]))
for r in rres: print(*r)

Measured memory_bytes: 119632
#include <cstdio>

using namespace std;

int win_count[100005];

int main()
{
	int N, K, Q;
	scanf("%d%d%d", &N, &K, &Q);
	for (int i = 0; i < Q; i++)
	{
		int win_num;
		scanf("%d", &win_num);
		win_count[win_num]++;
	}
	for (int i = 1; i <= N; i++)
	{
		if (K - Q + win_count[i] > 0)
			puts("Yes");
		else
			puts("No");
	}
	return 0;
}

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

int main(){
  int N,cnt=1;
  cin >> N;
  vector<int> H(N);
  loop(i,N)
    cin >> H.at(i);
  int highest = H.at(0);
  for(int i=1;i<N;++i){
    if(H.at(i)>=highest){
      ++cnt;
      highest = H.at(i);
    }
  }
  cout << cnt;

}


Measured memory_bytes: 256
def f_single_dot():
    # https://atcoder.jp/contests/abc168/submissions/13368489
    import sys
    from collections import deque
    input = sys.stdin.readline
    N, M = [int(i) for i in input().split()]

    X, Y = set([0]), set([0])
    A, B, C = [0] * N, [0] * N, [0] * N
    for i in range(N):
        A[i], B[i], C[i] = map(int, input().split())
        X |= {A[i], B[i]}
        Y |= {C[i]}
    D, E, F = [0] * M, [0] * M, [0] * M
    for i in range(M):
        D[i], E[i], F[i] = map(int, input().split())
        X |= {D[i]}
        Y |= {E[i], F[i]}
    X = sorted(X)
    Y = sorted(Y)
    dictx, dicty = {n: i * 2 for i, n in enumerate(X)}, {n: i * 2 for i, n in enumerate(Y)}
    LX = [X[i // 2 + 1] - X[i // 2] if i % 2 else 0 for i in range(len(X) * 2 - 1)]
    LY = [Y[i // 2 + 1] - Y[i // 2] if i % 2 else 0 for i in range(len(Y) * 2 - 1)]
    c = [[0] * (len(X) * 2 - 1) for _ in range(len(Y) * 2 - 1)]
    for i in range(N):
        y = dicty[C[i]]
        for x in range(dictx[A[i]], dictx[B[i]] + 1):
            c[y][x] = 1
    for i in range(M):
        x = dictx[D[i]]
        for y in range(dicty[E[i]], dicty[F[i]] + 1):
            c[y][x] = 1
    que = deque()
    used = [[0] * len(X) * 2 for _ in range(len(Y) * 2)]
    dy = [1, 1, -1, -1]
    dx = [1, -1, 1, -1]
    for k in range(4):
        nny, nnx = dicty[0] + dy[k], dictx[0] + dx[k]
        if 1 <= nny < len(Y) * 2 - 1 and 1 <= nnx < len(X) * 2 - 1:
            que.append((nny, nnx))
            used[nny][nnx] = 1
    ans = 0
    dy = [1, 0, -1, 0]
    dx = [0, 1, 0, -1]
    while que:
        y, x = que.popleft()
        if y % 2 and x % 2:
            ans += LY[y] * LX[x]
        for k in range(4):
            ny, nx = y + dy[k], x + dx[k]
            nny, nnx = ny + dy[k], nx + dx[k]
            if c[ny][nx] == 0:
                if nny < 0 or nny >= len(Y) * 2 - 1 or nnx < 0 or nnx >= len(X) * 2 - 1:
                    return 'INF'
                if not used[nny][nnx]:
                    que.append((nny, nnx))
                    used[nny][nnx] = 1
    return ans

print(f_single_dot())

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

int main(void) {
  string s; cin >> s;
  int n = s.length();
  bool flag = true;
  int cntC = 0;
  
  for (int i=0; i<n; i++) {  
    if (i == 0 && s[i] != 'A') {
      flag = false; break;
    }
    if ((i == 1 || i == n-1) && s[i] >= 'A' && s[i] <= 'Z') {
      flag = false; break;
    }
    if (i >= 2 && i <= n-2) {
      if (s[i] == 'C') cntC++;
      if (s[i] >= 'A' && s[i] <= 'Z' && s[i] != 'C') {
        flag = false; break;
      }
    }
  }

  if (flag && cntC == 1) {
    cout << "AC" << endl;
  } else {
    cout << "WA" << endl;
  }
  return 0;
}

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

int comp(const void* a,const void* b)
{
  return strcmp(a,b);
}

int main(void)
{
  char s[200000][11];
  long int n,i,c=1;

  scanf("%ld",&n);
  for(i=0;i<n;i++)
  {
    scanf("%s",s[i]);
  }

  qsort(s,n,sizeof(*s),comp);

  for(i=0;i<n-1;i++)
  {
    if(strcmp(s[i],s[i+1])!=0) c++;
  }

  printf("%ld\n",c);

  return 0;
}

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

int main() {
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    int minimum = min(B, D);
    int maxinum = max(A, C);
    if(minimum - maxinum > 0)
        cout << minimum - maxinum << endl;
    else
        cout << 0 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define s second
#define f first
#define pb push_back
#define endl '\n'
using namespace std;


typedef long long ll;
typedef pair<int,int> pii;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;

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

	string S;
	cin >> S;

	int ans = 0;

	for(int i = 1; i < S.size(); i++){
		if(S[i] != S[i-1]) ans++;
	}

	cout << ans << endl;

	return 0;
}


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

// 組合せを素数で割った値を求める
const int MAX = 510000;
const long long MOD = 1e9 + 7;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++){
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k) {
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n;
  cin >> n;
  
  vector<int> a(n + 1), used(n, 1e9);
  int mid; // 同じ数字の間に挟まっている数字の個数
  for(int i = 0; i < n + 1; i++){
    cin >> a.at(i);
    if(used.at(a.at(i) - 1) == 1e9) used.at(a.at(i) - 1) = i;
    else mid = i - used.at(a.at(i) - 1) - 1;
  }
  
  cout << n << '\n'; // k = 1のとき，答えはn
  
  COMinit();
  
  long long ans;
  for(int i = 2; i <= n + 1; i++){
    ans = COM(n + 1, i);
    ans += MOD * 10000000;
    ans -= COM(n + 1 - mid - 2, i - 1);
    cout << ans % MOD << '\n';
  }
}

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

int main() {
	int N;
	while (cin >> N) {
		vector<int> v(N + 1, 1);
		v.at(0) = 0;
		v.at(1) = 0;

		int r = sqrt(N);
		for (int i = 2; i <= r; i++) {
			int& p = v.at(i);
			if (p == 1) {
				for (int j = i*2; j <= N; j+=i) {
					int& p2 = v.at(j);
					if (!(j % i)) {
						p2 = 0;
					}
				}
			}
			else {
				continue;
			}
		}

		int c = count(v.begin(), v.end(), 1);
		cout << c << endl;
	}
}


Measured memory_bytes: 7200
r, c = map(int,input().split())
a = [[0 for i in range(c + 1)] for j in range(r + 1)]
for i in range(r):
    a[i] = list(map(int, input().split()))
    a[i].append(sum(a[i]))
for j in range(c + 1):
    for i in range(r):
        a[r][j] += a[i][j]
for i in range(r + 1):
    for j in range(c + 1):
        if j == c:
            print(str(a[i][j]))
        else:
            print(str(a[i][j]), end = " ")



Measured memory_bytes: 6220
#include <stdio.h>

int main(void)
{
	int N;
	int cnt = 0;
	
	while(1){
		scanf("%d", &N);
		if(N == 0) break;
		
		cnt = 0;
		for(int i = 2; i <= N; i++){
			if( (N*2) % i) continue;
			if( (N*2 / i + i) % 2 == 0) continue;
			
			if((double)N/i - i/2.0 > 0) cnt++;
		}
		printf("%d\n", cnt);
	}
	return 0;
}

Measured memory_bytes: 2692
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,A,B;cin>>N>>A>>B;
    int P[N];int a=0,b=0,c=0;
    for(int i=0;i<N;i++){
        cin>>P[i];
        if(P[i]<=A){
            a++;
        }else if(P[i]<=B){
            b++;
        }else{
            c++;
        }
    }cout<<min(min(a,b),c)<<endl;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
A = list(map(int, input().split()))

s = sum(A)



def solve():
    ans = 1
    idx = 1

    while idx * idx <= s:
        if s % idx == 0:
            if ok(s // idx):
                return s // idx
            if ok(idx):
                ans = idx
        idx += 1

    return ans


def ok(i):
    D = list(filter(lambda x: x != 0, [a % i for a in A]))
    D.sort()

    l = len(D)

    S = [0] * (l + 1)
    for j in range(l):
        S[j + 1] = S[j] + D[j]

    for j in range(l):
        if S[j] == i * (l - j) - (S[l] - S[j]) and S[j] <= K:
            return True

    return False


print(solve())


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

using namespace std;
typedef long long ll;

#define MOD (long long)(1e9+7)
#define INF (1LL<<60)
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define rep1(i,n) for(ll i = 1; i <= (n); i++)

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;
}


// 最大公約数
ll gcd(ll a, ll b)
{
  if(b == 0) return a;
  return gcd(b, a % b);
}

// mod m におけるa の逆元
ll modinv(ll a, ll m) {
  ll b = m, u = 1, v = 0;
  while (b) {
    ll t = a / b;
    a -= t * b; swap(a, b);
    u -= t * v; swap(u, v);
  }
  u %= m;
  if (u < 0) u += m;
  return u;
}

// 素因数分解
vector<pair<ll, ll>> prim;
void pf(ll n)
{
  ll s = sqrt(n);
  ll r = 0;
  for(ll i = 2; i <= s; i++) {
    if((n % i) == 0) {
      r = 0;
      do {
	r++;
	n = n / i;
      } while((n % i) == 0);
      prim.push_back({i, r});
    }
  }
  if(n > s) {
    prim.push_back({n, 1});
  }
}

ll a[100010][3];
ll dp[100010][3];

void solve()
{
  ll n; cin >> n;
  
  //  vector<vector<ll>> a(3, vector<ll>(n));
  rep(i, n) rep(j, 3)  cin >> a[i][j];
  //vector<vector<ll>> dp(3, vector<ll>(n, 0));
  rep(j, n){
    rep(i, 3) {
      dp[j][i] = 0;
    }
  }
  rep(i, 3) dp[0][i] = a[0][i];
  
  rep1(i, n - 1) {
    rep(j, 3) {
      rep1(k, 2) {
	chmax(dp[i][j], dp[i-1][(j + k) % 3] + a[i][j]);
      }
    }


  }
      
  ll ans = 0;
  rep(i, 3) {
    cerr << "n:" << n << endl;
    chmax(ans, dp[n - 1][i]);
  }
  cout << ans << endl;
}


int main(void)
{
  // ll t; cin >> t; REP(i, t)
  solve();
}


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

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SP << " " <<

LL mod = 1000000007;


template <typename M>
class lazy_segment_tree {
	using T1 = typename M::t1;
	using T2 = typename M::t2;
	const int n;
	vector<T1> data;
	vector<T2> lazy;
	int size(int n) {
		int res = 1;
		while (res < n) res <<= 1;
		return res;
	}
	void push(int node) {
		if (lazy[node] == M::id2()) return;
		if (node < n) {
			lazy[node * 2] = M::op3(lazy[node * 2], lazy[node]);
			lazy[node * 2 + 1] = M::op3(lazy[node * 2 + 1], lazy[node]);
		}
		data[node] = M::op2(data[node], lazy[node]);
		lazy[node] = M::id2();
	}
	void suc(int l, int r, int node, int lb, int ub, T2 val) {
		if (ub <= l || r <= lb) return;
		if (l <= lb && ub <= r) {
			lazy[node] = M::op3(lazy[node], val);
			return;
		}
		push(node);
		int c = (lb + ub) / 2;
		suc(l, r, node * 2, lb, c, val);
		suc(l, r, node * 2 + 1, c, ub, val);
		data[node] = M::op1(M::op2(data[node * 2], lazy[node * 2]), M::op2(data[node * 2 + 1], lazy[node * 2 + 1]));
	}
	T1 sub(int l, int r, int node, int lb, int ub) {
		if (ub <= l || r <= lb) return M::id1();
		if (l <= lb && ub <= r) return M::op2(data[node], lazy[node]);
		int c = (lb + ub) / 2;
		return M::op2(M::op1(sub(l, r, node * 2, lb, c), sub(l, r, node * 2 + 1, c, ub)), lazy[node]);
	}
public:
	lazy_segment_tree(int n_) : n(size(n_)), data(n * 2, M::id1()), lazy(n * 2, M::id2()) {}
	lazy_segment_tree(int n_, T1 v1) : n(size(n_)), data(n * 2, v1), lazy(n * 2, M::id2()) {}
	lazy_segment_tree(const vector<T1>& data_) : n(size(data_.size())), data(n * 2, M::id1()), lazy(n * 2, M::id2()) {
		init(data_);
	}
	void init() {
		for (int i = n - 1; i >= 1; i--) data[i] = M::op1(data[i * 2], data[i * 2 + 1]);
	}
	void init(const vector<T1>& data_) {
		for (int i = 0; i < (int)data_.size(); i++) data[i + n] = data_[i];
		init();
	}
	void update(int l, int r, T2 val) {
		suc(l, r + 1, 1, 0, n, val);
	}
	T1 find(int l, int r) {
		return sub(l, r + 1, 1, 0, n);
	}
};

struct RURM {
	using t1 = int;
	using t2 = int;
	static t1 id1() { return INT_MAX; }
	static t2 id2() { return -1; }
	static t1 op1(const t1& l, const t1& r) { return min(l, r); }
	static t1 op2(const t1& l, const t2& r) { return r != id2() ? r : l; }
	static t2 op3(const t2& l, const t2& r) { return r != id2() ? r : l; }
};

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  LL N,Q;
  cin >> N >> Q;

	lazy_segment_tree<RURM> seg(N);
	seg.init();

	REP(i,Q){
		LL y;
		cin >> y;
		if(y==0){
			LL s, x;
			cin >> s >> x;
			seg.update(s, s, x);
		}
		else
		{
			LL s, t;
			cin >> s >> t;
			cout << seg.find(s, t)<<endl;
		}
	}
}



Measured memory_bytes: 4856
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=2e9;
const ll INF=9e18;
typedef pair<int,int> P;
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  int n,w,val[105]={},wei[105]={},dp[105][10005]={};
  cin >> n >> w;
  for(int i=1; i<=n; i++) {
    cin >> val[i] >> wei[i];
  }
  for(int i=1; i<=n; i++) {
    for(int j=0; j<=w; j++) {
      if(j-wei[i]>=0) {
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-wei[i]]+val[i]);
      }
      else {
        dp[i][j]=dp[i-1][j];
      }
    }
  }
  cout << dp[n][w] << endl;
}


Measured memory_bytes: 7284
N,T = (input().split())
N = int(N)
T = int(T)
roads = []
for i in range(N) :
    c , t = input().split()
    t = int(t)
    if t in range (1, T + 1):
        roads.append((int(c) ,t))

if len(roads) == 0 :
    print ("TLE")
else:
    roads.sort()
    print (roads[0][0])

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vs = vector<string>;
template <typename T>
using ost = tree<T, null_type, less<T>, rb_tree_tag,
    tree_order_statistics_node_update>;
#define forn(i,n) for(int i=0; i<int(n); ++i)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define ff first
#define ss second

const ll INF = 1e10;

int main() {
    ios::sync_with_stdio(false);
    ll n, c;
    cin >> n >> c;
    vll xs(2*n);
    forn(i, n) cin>>xs[i], xs[i+n]=xs[i];
    vvll cost(n, vll(n, INF));
    forn(i, n) forn(j, n)
        cost[i][j] = min(cost[i][j?j-1:j], xs[n+i-j]);
    ll ans=n*INF;
    forn(i, n) {
        ll sum = i*c;
        forn(j, n) sum += cost[j][i];
        ans = min(ans, sum);
    }
    cout << ans << '\n';
}


Measured memory_bytes: 31616
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
	int n;
	cin >> n;
	long long p = 1;
	for (int  i = 1; i <= n; i++) {
		p = (p * i) % 1000000007;
	}
	cout << p << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main()
{
	int a, b;

	scanf("%d %d", &a, &b);

	if (a < b)
	{
		printf("a < b\n");
	}
	else if (a > b)
	{
		printf("a > b\n");
	}
	else if (a == b)
	{
		printf("a == b\n");
	}
	return 0;
}


Measured memory_bytes: 2096
#include<bits/stdc++.h>
using namespace std;
signed main(){
    int n,flag=0;
    cin>>n;
    int p1[100];
    for(int i=1;i<n;i++){
        cin>>p1[i];
        if(p1[i]!=i)
            flag++;
    }
    if(flag<=2){
        cout<<"YES"<<'\n';
    }
    else{
        cout<<"NO"<<'\n';
    }
    return(0);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define ll long long
#define maxheap priority_queue<int>
#define minheap priority_queue<int,vector<int>,greater<int>>
const  long double eps = 1e-2;
const long double pi = acos(-1.0);
using namespace std;


vector<int> z_function (string s) {
	int n = (int) s.length();
	vector<int> z (n);
	for (int i=1, l=0, r=0; i<n; ++i) {
		if (i <= r)
			z[i] = min (r-i+1, z[i-l]);
		while (i+z[i] < n && s[z[i]] == s[i+z[i]])
			++z[i];
		if (i+z[i]-1 > r)
			l = i,  r = i+z[i]-1;
	}
	return z;
}

vector <bool> get(string s){
    int n = s.length();
    vector <bool> bol(n, false);
    vector <int> z = z_function(s);
    for (int i = 1; i < n; i++){
        for (int j = 2 * i - 1; j < n; j += i){
            if (z[j - i + 1] < i) break;
            bol[j] = true;
        }
    }
    return bol;
}

void solve(){
    string s;
    cin >> s;
    bool ok = false;
    for (int i = 0; i < s.length() - 1; i++)
        if (s[i] != s[i + 1])
            ok = true;

    if (!ok){
        cout << s.length() << endl;
        cout << 1 << endl;
        return;
    }
 
    vector <bool> bol1, bol2;
    bol1 = get(s);
    reverse(s.begin(), s.end());
    bol2 = get(s);
    
    if (bol1[s.length() - 1] == false){
    
        cout << 1 << endl;
        cout << 1 << endl;
        return;
    }
    
    int ans = 0;
    for (int i = 0; i < s.length() - 1; i++){
            if (!bol1[i] && !bol2[s.length() - i - 2])  
                ans++;
    }
    cout << 2 << endl;
    cout << ans << endl;
}
int main() {
    ios::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
    cout.setf(ios::fixed), cout.precision(3);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int step;
	step = 1;
    for (int i = 1; i <= step; i++){
         solve();
    }
}


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

int main(){

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

   long long ans;
   ans=(n/(a+b))*a;
    n=n%(a+b);
    if(n<=a){
        ans+=n;
    }else if(n>a){
        ans+=a;
    }

    cout<<ans<<endl;

return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    int a,b,c;
    cin>>a>>b>>c;
    if(a>b)
    {
        int temp=a;
        a=b;
        b=temp;
    }
    if(b>c)
    {
        int temp=b;
        b=c;
        c=temp;
    }
    if(a>b)
    {
        int temp=a;
        a=b;
        b=temp;
    }

    cout<<a<<" "<<b<<" "<<c<<endl;
    return 0;
}



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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long


#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)

const int N=1e5+5;
const int mod=1e9+7;

int32_t main() {
IOS;
int a;
cin>>a;
vector<int> idx_to_value(a+4);
FOR(i,1,a){
    int x;
    cin>>x;

    idx_to_value[i]=x;
}
int cnt=1,in=1,i;
bool ok=false;
    for ( i = 0; i < a; ++i) {
        if(idx_to_value[in]==2){ok=true;break;}
        else in=idx_to_value[in],cnt++;
    }
    if(!ok)cout<<-1;
    else cout<<cnt;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

int main() {

  long long X;
  cin>>X;

  if(X <= 11*(X/11) + 6){
    if(X % 11 == 0) cout<<2 * (X / 11)<<endl;
    else cout<<2 * (X / 11) + 1<<endl;
  } else{
    cout<<2 * (X / 11) + 2<<endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define QOEINDIEDIS freesteed
#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back
#define fill(x,c) memset(x,c,sizeof(x))
#define fi first
#define se second
#define sz(A) (int)(A.size())
#define all(x) (x).begin(),(x).end()
#define caset int ___T; cin>>___T; for(int cs=1;cs<=___T;cs++)
#define get(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
const ll mod=1e9+7;
const int Max = 1e6+10;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

int main() {
	int n,m,a,b;
	scanf("%d%d",&n,&m);
	vector<VI> grid(n+1);
	vector<int> mn(n+1,n+1);
	set<int> s; 
	rep(i,0,m){
		scanf("%d%d",&a,&b);
		mn[a] = min(mn[a],b);
		grid[a].pb(b);
		s.insert(a); 
	}
	VI t(all(s)); 
	int board=n+1,ans=0;
	for(int i=sz(t)-1;i>=0;i--){
		if(mn[t[i]]<board){
			board = t[i]+1;
			ans++;
		}
	}
	printf("%d",ans);
  	return 0;
}






Measured memory_bytes: 11264
package main

import "fmt"

func solve() {
	var x, a, b int
	fmt.Scan(&x, &a, &b)

	if abs(x-a) < abs(x-b) {
		fmt.Println("A")
	} else {
		fmt.Println("B")
	}

}

func main() {
	solve()
}

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
}


Measured memory_bytes: 512
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))
INF = 10 ** 18
# -2 -1 0 1
#dp_use 見ている文字を使った dp_not_use 見ている文字を使わない
dp_use = [-INF] * 4
dp_not_use = [-INF] * 4
dp_not_use[0] = 0

for a in A:
    tmp_use = [-INF] * 4
    tmp_not_use = [-INF] * 4
    for current_diff in range(-2,2):
        if current_diff - 1 >= -2:
            tmp_use[current_diff] = dp_not_use[current_diff-1] + a
        if current_diff + 1 < 2:
            tmp_not_use[current_diff] = max(dp_use[current_diff+1],dp_not_use[current_diff+1]) 
    dp_use = tmp_use
    dp_not_use = tmp_not_use

diff = -1 + (N+1) % 2 
print(max(dp_use[diff],dp_not_use[diff]))

Measured memory_bytes: 29288
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int dp[100005];
int Frog(int *a, int i, int n, int *dp){
    if(i >= n){
        dp[i] = 0;
        return 0;
    }

    if(dp[i] != -1)
        return dp[i];
    int x = 0;
    if(i+1 < n)
        x = abs(a[i]-a[i+1]) + Frog(a, i+1, n, dp);
    int y = INT_MAX;
    if(i+2 < n)
        y = abs(a[i]-a[i+2]) + Frog(a, i+2, n, dp);
    dp[i] = min(x, y);
    return dp[i];
}
int main(){

    int n;
    cin >> n;
    for(int i =0; i < n; i++)
        cin >> a[i];
    memset(dp, -1, sizeof(dp));
    cout << Frog(a, 0, n, dp);
    return 0;
}


Measured memory_bytes: 12152
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <set>
#include <utility>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <cstdio>
#include <map>

using namespace std;

using ll = long long;
using P = pair<ll,ll>;

#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define rrep(i,x) for(ll i = ((ll)(x) - 1); i >= 0; i--)

#define _upgrade ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

//ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
//ll lcm(ll x, ll y) {return x / gcd(x, y) * y;}

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

const ll mod = 1e9 + 7;
const ll IMF = 1LL << 60;
const double PI = 3.14159265358979323846;


// ****************************************CODE***************************************//






//1
int N;
ll a[100010][3];

//2
ll dp[100010][3];

int main(){
        cin >> N;
        for(int i = 0; i < N; i++) for(int j = 0; j < 3; j++) cin >> a[i][j];

        //3,4
        

        //5
        for(int i = 0; i < N; i++){
                for(int j = 0; j < 3; j++){
                        for(int k = 0; k < 3; k++){
                                if(j==k) continue;
                                chmax(dp[i+1][k], dp[i][j] + a[i][k]);
                        }
                }
        }

        //6
        ll res = 0;
        for(int j = 0; j < 3; j++) chmax(res, dp[N][j]);
        cout << res << endl;
        return 0;
}














































Measured memory_bytes: 4992
import java.util.Scanner;

public class Main {
	public static void main(String args[]){
		 Scanner sc = new Scanner(System.in);
		 
		 int a = sc.nextInt();
		 int b = sc.nextInt();
		 int c = a*b;
		 int d = a+a+b+b;
		 System.out.println(c + " " + d);
	
	
	
	
	
	
	
	}
}

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

int main() {
    int n, m, a, b;
    cin >> n >> m;
    vector<vector<int>> path(n);
    vector<int>shortest(n, INT_MAX);
    queue<int> que;
    rep(i, m) {
        cin >> a >> b;
        path.at(a - 1).push_back(b - 1);
        path.at(b - 1).push_back(a - 1);
    }
    que.push(0);
    shortest.at(0) = 0;
    while(que.size()) {
        int temp = que.front();
        que.pop();
        for(int t : path.at(temp)) {
            if(shortest.at(t) == INT_MAX) {
                que.push(t);
                shortest.at(t) = shortest.at(temp) + 1;
            }
        }
    }
    if(shortest.at(n - 1) == 2) cout << "POSSIBLE" << endl;
    else cout << "IMPOSSIBLE" << endl;
}

Measured memory_bytes: 13168
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<math.h>
using namespace std;
#define mod (1000000000+7)
#define N (10007)
#define INF 1e16
typedef long long ll;
typedef pair<ll,ll> P;




int main(void){
    int x,y;
    int a=0,b=0,c=0;
    cin>>x>>y;
    if(x==1&&y==1)b=400000;
    if(x<=3)a=100000*(4-x);
    if(y<=3)c=100000*(4-y);
    cout<<a+b+c<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int S;
    int s, m, h;
    
    scanf("%d", &S);
    
    h = S/ 3600;
    m = (S%3600) / 60;
    s = S % 60;

    printf("%d:%d:%d\n", h,m,s);
    return 0;
}



Measured memory_bytes: 2044
#include<iostream>
#include<string>
#include<cstdlib>
#include<cmath>
using namespace std;
int main(){
  string a,b;
  cin >> a >> b;
  string s=a+b;
  int x=atoi(s.c_str());
  int y=sqrt(x);
  if(y*y==x)
    cout << "Yes\n";
  else
    cout << "No\n";
  return 0;
}


Measured memory_bytes: 256
require 'set'

class Dictionary

  def initialize
    @values = Set.new
  end

  def insert(value)
    @values << value
  end

  def find(value)
    if @values.include? value
      puts 'yes'
    else
      puts 'no'
    end
  end
end

n = gets.to_i
dictionary = Dictionary.new
n.times do
  input = gets.chomp.split(' ').map(&:to_sym)
  case input[0]
  when :insert
    dictionary.insert input[1]
  when :find
    dictionary.find input[1]
  end
end


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

bool is_prime(int k)
{
	for(int j=2;j*j<=k;j++){
		if(k%j==0) {
			return false;
		}
	}
    return true;
}

int main()
{
    stringstream ss;
    // 入力
    int X;
    cin>>X;

    int ans=1;
    for(int i=2;i<=X;i++){
    	for(int j=2;pow(i,j)<=X;j++){
    		//cout<<pow(i,j)<<endl;
    		int ans_=pow(i,j);
    		ans=max(ans,ans_);
          	//if(ans==ans_)cout<<i<<" "<<j<<endl;
    	}
    }

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

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

using namespace std;

int main(){
    int n;
    vector<int> s;
    long long int sum=0;
    cin >> n;
    int po=0;
    for(int i=0;i<n;i++){
      cin >> po;
      sum+=po;
      if(po%10!=0)s.push_back(po);
    }
    sort(s.begin(), s.end());
    if(sum%10==0 && s.size()>0)sum-=s[0];
    else if(sum%10==0)sum=0;
    cout<<sum<<endl;
    return 0;
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)     (a).begin(),(a).end()
#define VI         vector<int>
#define MOD 1000000007

using ll = long long int;
using P = pair<int,int>;

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; }

const ll INF=(ll)1e19;
//const int INF=(1<<30);

int main(){
  string s;
  cin >> s;
  int cnt0=0;
  REP(i,(int)s.size())if(s[i]=='0')cnt0++;

  cout << min(cnt0, (int)s.size()-cnt0) * 2 << endl;
}



Measured memory_bytes: 512
#include <bits/stdc++.h>
//----***やべーやつら***----
using namespace std;
#define int long long

//----***型定義***----
using ll = long long;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
typedef long double ld;
typedef pair<int,int> P;

//----***Like a Pythonista***----
#define REP(ii,jj,nn) for (ll ii=jj;ii<(nn);ii++)
#define RREP(ii,nn,jj) for (ll ii = nn; jj<ii;ii--)
#define each(i,...) for (auto&& i:__VA_ARGS__)
#define ALL(vec) (vec).begin(),(vec).end()
#define sum(...) accumulate(ALL(__VA_ARGS__),0LL)
#define dsum(...) accumulate(ALL(__VA_ARGS__),0.0L)
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
template<class T> inline auto max(const T& a){ return *max_element(ALL(a)); }
template<class T> inline auto min(const T& a){ return *min_element(ALL(a)); }
inline ll gcd(ll a,ll b){if(b == 0) return a;return  gcd(b,a%b);}
inline ll lcm(ll a,ll b){ll g = gcd(a,b);return a / g * b;}

//----***定数***----
#define MOD 1000000007
#define INF 10*60
#define EPS 1e-9

//----***パーツ***----
#define fr first
#define se second

//----***入出力***---
#define print(out) cout<< out  << "\n";
#define debug(var)  do{std::cerr << #var << " ↓ "<<"\n";view(var);}while(0);
#define dbg cerr<<"🥺🥺🥺🥺🥺🥺"<<endl;
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }

//----***初期時読み込み***----
struct initial{initial(){cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);cerr<<fixed<<setprecision(15);};}initial_;

signed main(){
  int N,l,r,n;cin>>N;
  int left=1,right=1;
  REP(i,0,N){
    cin>>l>>r;
    n=max((left+l-1)/l,(right+r-1)/r);
    left=n*l,right=n*r;
  }
  print(left+right)

}


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

using ll    = long long;
using ull   = unsigned long long;
using veci  = vector<int>;
using vecll = vector<ll>;
#define EPS (1e-7)
#define INF (1e9)
#define PI  (acos(-1))
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define REP(i,n) for(int i= 0;i<(int)(n);++i)
#define pb push_back

veci enum_div(int n){
	veci ret;
	ret.pb(1);
	for(int i=1;i*i<n;i++){
		if(n%i==0){
			ret.pb(i);
			if(i != n/i){ret.pb(n/i);}
		}
	}
	ret.pb(n);
	return ret;
}
int gcb(int a,int b){return ((b == 0)? a : gcb(b,a%b));}
int gcd(int a,int b){return (a*b) / gcb(a,b);}

int main(){
    ll x,t;
    cin >> x >> t;
    if(x-t <= 0){
        cout << 0 << endl;
        return 0;
    }
    cout << x-t << endl;
	return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<map>
#include<string>
#include<cstdio>
typedef long long ll;
const ll inf = 1e18; 
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	long double a;
	long double b;
	cin>>a>>b;
	cout<<(ll)(a*b)<<endl;
	
	return 0;
}

Measured memory_bytes: 3744
#include <iostream>

int main() {
	int x=1;
	int i=0;
	while (true){
		i++;
		std::cin>>x;
		if (x==0){
			break;
		}
		std::cout << "Case " << i << ": "<< x << std::endl;
		
	}
	return 0;
}

Measured memory_bytes: 3068