akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define INF 2e9
#define MOD 1000000007
#define MOD9 998244353
#define intMAX 51000;
#define PI 3.14159265359
using namespace std;
typedef long long llong;
// typedef long double ldouble;

using Graph = vector<vector<int>>;

// int ctoi(const char c){
//   if('0' <= c && c <= '9') return (c-'0');
//   return -1;
// }

// int gcd(int a, int b){
//   int ma = max(a,b);
//   int mi = min(a,b);
//   if(mi == 0) return ma;

//   return gcd(mi, ma%mi);
// }

// llong POW(llong a, llong b){
//   if(b == 0) return 1;
//   else{
//     if(b%2 == 0) return POW(a * a % MOD, b / 2) % MOD;
//     else return a * POW(a * a % MOD, b / 2) % MOD;
//   }
// }

int main(){
  int A, B, C;
  cin >> A >> B >> C;
  if(B-A == C-B) cout << "YES" << endl;
  else cout << "NO" << endl;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		Restaurant restaurants[] = new Restaurant[n];
		for(int i = 0; i < n; i++){
			String city = sc.next();
			int score = sc.nextInt();

			restaurants[i] = new Restaurant(i + 1, city, score);

		}

		Arrays.sort(restaurants);

		for(int i = 0; i < n; i++){
			System.out.println(restaurants[i].id);
		}
	}

}

class Restaurant implements Comparable<Restaurant>{
	int id;
	String city;
	int score;

	public Restaurant(int id, String city, int score) {
		// TODO 自動生成されたコンストラクター・スタブ
		this.id = id;
		this.city = city;
		this.score = score;
	}

	@Override
	public int compareTo(Restaurant r1) {
		// TODO 自動生成されたメソッド・スタブ
		return this.city.equals(r1.city) ? r1.score - this.score : this.city.compareTo(r1.city);
	}

}

Measured memory_bytes: 23760
# -*- coding: utf-8 -*-

n, m = list(map(int, input().split()))
h = list(map(int, input().split()))
to = [[] for i in range(n)]

for i in range(m):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

ans = 0

for i in range(n):
    ok = True
    for j in to[i]:
        if(h[i] <= h[j]):
            ok = False
    if(ok):
        ans += 1

print(ans)


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

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    if((a==5 && b==5 && c==7) || (a==5 && b==7 && c==5) || (a==7 && b==5 && c==5)){
        cout << "YES" << endl;
    }else{cout << "NO" << endl;}
    return 0;
}

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

int main() {
	int H, W; cin >> H >> W;
	vector<vector<int> > a(H, vector<int>(W));
	vector<vector<int> > b(H, vector<int>(W));
	vector<vector<int> > c(H, vector<int>(W));
	for (int h = 0; h < H; ++h)
	{
		for (int w = 0; w < W; ++w)
		{
			cin >> a[h][w];
		}
	}
	for (int h = 0; h < H; ++h)
	{
		for (int w = 0; w < W; ++w)
		{
			cin >> b[h][w];
		}
	}
	for (int h = 0; h < H; ++h)
	{
		for (int w = 0; w < W; ++w)
		{
			c[h][w] = abs(a[h][w] - b[h][w]);
			//cout << c[h][w] << endl;
		}
	}

	vector<vector<vector<bool> > > s(H, vector<vector<bool> >(W, vector<bool>(14401, false)));
	s[0][0][c[0][0]] = true;
	for (int h = 0; h < H; ++h)
	{
		for (int w = 0; w < W; ++w)
		{
			for (int x = 0; x < 14401; ++x)
			{
				if (!s[h][w][x]) continue;
				if (h < H-1) {
					s[h+1][w][x + c[h+1][w]] = true;
					s[h+1][w][abs(x - c[h+1][w])] = true;
				}
				if (w < W-1) {
					s[h][w+1][x + c[h][w+1]] = true;
					s[h][w+1][abs(x - c[h][w+1])] = true;
				}

			}
		}
	}

	int ans = 1000000;
	for (int x = 0; x < 14401; ++x) {
		if (s[H-1][W-1][x]) ans = min(ans, abs(x));
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 14208
#include <bits/stdc++.h>
#define ll long long
#define ALL(x) x.begin(),x.end()
#define MOD (1000000000+7)
using namespace std;
#define PI 3.14159265359
#define tMOD 998244353
#define mkpr(x,y) make_pair(x,y)


int main(){
ll N;
ll K;
cin>>N>>K;
vector<ll> A(N);
  ll tp=0;

for(ll i=0;i<N;i++)cin>>A[i];

for(ll ii=0;ii<K;ii++){
int tmp1[2002013]={0};
 if(ii>50){
 
 tp=1;
 break;;
 }
for(ll i=0;i<N;i++){
    ll lef = 0;
    if(i-A[i]>0){
        lef = i-A[i];
    }
    ll ri = i+A[i];
    tmp1[lef]++;
    tmp1[ri+1]--;
}
ll rui = tmp1[0];
for(ll i=0;i<N;i++){
    A[i] = rui;
    rui = tmp1[i+1]+rui;
}

}
if(tp==1){
for(ll i=0;i<N;i++){
    cout<<N<<' ';
}
  return 0;
}
  
for(ll i=0;i<N;i++){
    cout<<A[i]<<' ';
}
cout<<endl;
}









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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll N;
    ll ans = 0;
    vector<vector<ll>> num(10, vector<ll>(10));
    cin >> N;
    repi2(i, 1, N) {
        ll temp = i;
        vector<ll> digits;
        while(temp) {
            digits.push_back(temp % 10);
            temp /= 10;
        }
        if(!digits.front() || !digits.back()) continue;
        num[digits.front()][digits.back()]++;
    }
    rep2(i, 1, 10) rep2(j, 1, 10) ans += num[i][j] * num[j][i];
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
def function(S):
    S = S[::-1]
    mods = [0]*2019 # mod 2019の余り0~2018の数
    mods[0] += 1 # 自身が割れる場合
    # MEMO : int(c) * 10^n % 2019 をまともに計算するとTLE
    # １つ前の桁のmodを利用する
    num = 0
    digit = 1
    for c in S:
        num = (int(c) * digit + num) % 2019
        digit = (digit * 10) % 2019
        mods[num] += 1
    
    result = 0
    for m in mods:
        result +=  m * (m-1) // 2

    return str(result)

if __name__ == '__main__':
    print(function(input()))


Measured memory_bytes: 9372
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
 long long gcd(long long a, long long b){
     if(b==0) return a;
     return gcd(b,a%b);
 }

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

    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll e = c*d/gcd(c, d);
    a--;
    ll ans = b - a;
    ans -= b / c + b / d - b / e - a / c - a / d + a / e;
    cout << ans << endl;
}

Measured memory_bytes: 256
n = int(input())
d = dict()

for _ in range(n):
    s = input()
    if s in d:
        d[s] += 1
    else:
        d[s] = 1

tmp = sorted(d.items())
ans = sorted(tmp, key=lambda x:x[1], reverse=True)

max = ans[0][1]
for i in ans:
    if i[1] < max:
        break
    print(i[0])

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

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define debug(x) cerr << #x << ": " << x << "\n"
typedef long long ll;

#define M 1046527
#define NIL (-1)
#define L 14

using namespace std;

char H[M][L];

int getChar(char ch)
{
    if (ch == 'A')
        return 1;
    else if (ch == 'C')
        return 2;
    else if (ch == 'G')
        return 3;
    else if (ch == 'T')
        return 4;
    else
        return 0;
}

ll getKey(char str[])
{
    ll sum = 0, p = 1;
    REP(i, strlen(str))
    {
        sum += p * (getChar(str[i]));
        p *= 5;
    }
    return sum;
}

int h1(int key) {return key % M;}
int h2(int key) { return 1 + (key % (M - 1)); }

int find(char str[])
{
    ll key, i, h;
    key = getKey(str);
    for (i = 0;;++i)
    {
        h = (h1(key) + i * h2(key)) % M;
        if (strcmp(H[h], str) == 0)
            return 1;
        else if ( strlen(H[h]) == 0)
            return 0;
    }
    return 0;
}

int insert(char *str)
{
    ll key, i, h;
    key = getKey(str);
    for (i = 0;;++i)
    {
        h = (h1(key) + i * h2(key)) % M;
        if (strcmp(H[h], str) == 0)
            return 1;
        else if ( strlen(H[h]) == 0) 
        {
            strcpy(H[h], str);
            return 0;
        }
    }
    return 0;
}


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

    int n;
    char str[L], com[9];
    REP(i, M) { H[i][0] = '\0'; }
    scanf("%d", &n);
    REP(i, n)
    {
        scanf("%s %s", com, str);

        if (com[0] == 'i')
        {
            insert(str);
        }
        else
        {
            if (find(str))
            {
                cout << "yes\n";
            }
            else
            {
                cout << "no\n";
            }
        }        
    }
}


Measured memory_bytes: 17592
N = gets.chomp.to_i
M = 2*N
S = gets.chomp
mod = 10**9 + 7

answer = 1
x = 0
y = 0
i = 0
while i < M
    if i%2 == 0
        if S[i] == "B"
            y += 1
        else
            answer *= (y-x)
            answer %= mod
            x += 1
        end
    else
        if S[i] == "W"
            y += 1
        else
            answer *= (y-x)
            answer %= mod
            x += 1
        end
    end
    i += 1
end

if x == y
    i = 1
    while i <= N
        answer *= i
        answer %= mod
        i += 1
    end
    puts answer
else
    puts 0
end

Measured memory_bytes: 2172
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
import numpy as np

K, N = MAP()
A = LIST()
A.append(A[0]+K)

B = np.zeros(N)
for i in range(N):
  		B[i] = A[i+1] - A[i]

print(int(K - max(B)))

Measured memory_bytes: 35140
#include <algorithm>
#include <functional>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <climits>

#define all(c) (c).begin(), (c).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
#define fr first
#define sc second

const int INF=100000000;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
using namespace std;
typedef pair<int ,int > P;
typedef long long ll;

#define MAX 500000
#define SENTINEL 2000000000
int L[MAX/2+2],R[MAX/2+2];

ll merge(int *a,int n, int l,int mid,int r) {
    ll cnt=0;
    int n1=mid-l;
    int n2=r-mid;
    rep(i,n1) L[i]=a[l+i];
    rep(i,n2) R[i]=a[mid+i];
    L[n1]=R[n2]=SENTINEL;
    int i,j;
    i=j=0;
    for(int k=l;k<r;k++) {
        if(L[i]<=R[j]) a[k]=L[i++];
        else a[k]=R[j++],cnt+=n1-i;
    }
    return cnt;
}
ll merge_sort(int *a,int n,int l,int r) {
    ll v1,v2,v3;
    if(l+1<r) {
        int mid=(l+r)/2;
        v1=merge_sort(a,n,l,mid);
        v2=merge_sort(a,n,mid,r);
        v3=merge(a,n,l,mid,r);
        return v1+v2+v3;
    }
    else return 0;
}

int a[MAX];
int main() {
    int n;
    cin>>n;
    rep(i,n) cin>>a[i];

    ll ans = merge_sort(a,n,0,n);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 2728
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, W = map(int, input().split())
    goods = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[1])
    max_value = 1
    for i in range(n):
        max_value += goods[i][1]

    dp = [[f_inf for _ in range(max_value)] for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 0

    for j in range(1, max_value):
        for i in range(1, n + 1):
            w, v = goods[i - 1]
            if j - v >= 0:
                dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v] + w)
            else:
                dp[i][j] = dp[i - 1][j]

    res = 0
    for k in range(max_value):
        if dp[-1][k] <= W:
            res = k

    print(res)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 387128
#include<iostream>
using namespace std;
long dp[21][100];
main()
{
	int n;cin>>n;
	int a[100];for(int i=0;i<n;i++)cin>>a[i];
	dp[a[0]][0]=1;
	for(int i=1;i<n-1;i++)
	{
		for(int j=0;j<=20;j++)
		{
			if(j-a[i]>=0)dp[j-a[i]][i]+=dp[j][i-1];
			if(j+a[i]<=20)dp[j+a[i]][i]+=dp[j][i-1];
		}
	}
	cout<<dp[a[n-1]][n-2]<<endl;
}

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



int main() {
    int N;
    cin>>N;
    int K;
    cin>>K;
    string S;
    cin>>S;
    
    K = K - 1;
    
    if(S.at(K) == 'A'){
        S.at(K) = 'a';
    }
    else if(S.at(K) == 'B'){
        S.at(K) = 'b';
    }
    else{
        S.at(K) = 'c';
    }
    
    cout<<S<<endl;
    return 0;
}


Measured memory_bytes: 256
n=int(input())
a={}
for i in range(n):
    tmp=input()
    if not tmp in a:
        a[tmp] = 1
    else:
        a[tmp] += 1
M=max(a.values())
ans=[]
for k, v in a.items():
    if v == M:
        ans.append(k)
ans.sort()
for i in range(len(ans)):
    print(ans[i])

Measured memory_bytes: 32096
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>
#include <iomanip>

using namespace std;
using ll = long long;

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

#include <iostream>

int main()
{
	int A, B, C ;

	cin >> A >> B >> C;

	cout << C-min(A - B, C) << endl;

}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int a = N / 100;
		int b = (N / 10) % 10;
		int c = N % 10;
		int ans = 0;
		if(a >= b && a >= c) {
			ans = a * 100 + a * 10 + a;
		} else {
			ans = (a + 1) * 100 + (a + 1) * 10 + a + 1;
		}
		System.out.println(ans);
	}

}


Measured memory_bytes: 21716
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>

using namespace std;

vector< vector<int> > cnt(26);

int main(){
  int N, ans = 0; cin >> N;
  string S; cin >> S;

  for(int i = 0; i < S.length(); i++){
    cnt[S[i] - 'a'].push_back(i);
  }

  for(int i = 0; i < 26; i++){
    int cnt_size = cnt[i].size();
    int left;

    for(int j = 0; j < cnt_size; j++){
      left = cnt[i][j];
      for(int k = cnt_size - 1, right = cnt[i][k]; k > j  && right - left > ans ; k--, right = cnt[i][k]){
        if(N - right <= ans) continue;
        int t = 0;
        for(int m = 0; left + m < right; m++){
          if(S[left+m] == S[right+m]) t++;
          else break;
        }
        if(t > ans) ans = t;

      }
    }
  }
  cout << ans << endl;
}


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

int main(){
    int N;
    cin >> N;
    cout << 0 << endl;
    string S;
    cin >> S;
    string S0 = S;
    if(S == "Vacant") return 0;
    int l=1,r=N;

    while(true){
        int mid = (l+r) / 2;
        cout << mid << endl;
        cin >> S;
        if(S == "Vacant") return 0;
        if(mid % 2 == 0 && S == S0){
            l = mid;
        }else if(mid % 2 == 1 && S != S0){
            l = mid;
        }else{
            r = mid;
        }
    }

    return 0;
}

Measured memory_bytes: 852
#include<bits/stdc++.h>
#define ll long long
#define iof ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pi 3.1415926535897
#define mod 1000000007
#define inf (1ll<<60)
#include <fstream>
using namespace std;


int main()
{
    iof;
    ll n; cin>>n;
    ll arr[n];
    for(ll i=0;i<n;i++)
        cin>>arr[i];
    ll dp[n+1]={0};
    dp[0]=0;
    dp[1]=abs(arr[1]-arr[0]);
    for(ll i=2;i<n;i++)
    {
     dp[i]=min(abs(arr[i]-arr[i-2]) +dp[i-2],abs(arr[i]-arr[i-1])+dp[i-1]);
    }
    cout<<dp[n-1]<<endl;

}


Measured memory_bytes: 1792
#include <algorithm>
#include <iostream>

int main() {
  long long a[3];
  for (int i = 0; i < 3; ++i)
    std::cin >> a[i];
  std::cout << *std::min_element(a, a + 3) << " " << *std::max_element(a, a + 3)
            << std::endl;
}



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

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

  if((a.at(a.size()-1) ==  b.at(0))&&(b.at(b.size()-1) ==  c.at(0)))
     cout << "YES" << endl;
  else cout << "NO" << endl;
}

Measured memory_bytes: 256
class BigCombination(object):
    __slots__ = ["mod", "factorial", "inverse"]

    def __init__(self, mod: int = 10**9+7, max_n: int = 10**6):
        fac, inv = [1], []
        fac_append, inv_append = fac.append, inv.append

        for i in range(1, max_n+1):
            fac_append(fac[-1] * i % mod)

        inv_append(pow(fac[-1], mod-2, mod))

        for i in range(max_n, 0, -1):
            inv_append(inv[-1] * i % mod)

        self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

    def get_combination(self, n, r):
        return self.factorial[n] * self.inverse[r] * self.inverse[n-r] % self.mod

    def get_permutation(self, n, r):
        return self.factorial[n] * self.inverse[n-r] % self.mod



import math
Big = BigCombination()
s = 0
m = 10**9+7


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

res =0
for i in range(N-1):
  res += (i+1)*(N-i-1)*(M**2)
for i in range(M-1):
  res += (i+1)*(M-i-1)*(N**2)
if K>2:
  anp = Big.get_combination(N*M-2,K-2)
else:anp = 1
print((res*anp)%m)

Measured memory_bytes: 116764
d = input().split(" ")
h = int(d[0])
w = int(d[1])
l = []
for i in range(h):
	s = input()
	l.append(list(s))
f = 0
p = l[0][0]
a = [[201] * w for i in range(h)]
a[0][0] = 0
for i in range(1, h):
	if p == l[i][0]:
		a[i][0] = a[i-1][0]
	else:
		a[i][0] = a[i-1][0] + 1
	p = l[i][0]
p = l[0][0]
for i in range(1, w):
	if p == l[0][i]:
		a[0][i] = a[0][i-1]
	else:
		a[0][i] = a[0][i-1] + 1
	p = l[0][i]
for i in range(1, h):
	for j in range(1, w):
		x = a[i-1][j]
		y = a[i][j-1]
		if l[i-1][j] != l[i][j]:
			x += 1
		if l[i][j-1] != l[i][j]:
			y += 1
		a[i][j] = min(x, y)
if l[0][0] == "." and l[h-1][w-1] == ".":
	print(int(a[h-1][w-1]/2))
elif l[0][0] == "." and l[h-1][w-1] == "#":
	print(int((a[h-1][w-1]+1)/2))
elif l[0][0] == "#" and l[h-1][w-1] == ".":
	print(int((a[h-1][w-1]+1)/2))
elif l[0][0] == "#" and l[h-1][w-1] == "#":
	print(int((a[h-1][w-1]/2) + 1))

Measured memory_bytes: 3316
using System;
using System.Linq;

namespace es
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] A = Console.ReadLine().Split().Select(x => Convert.ToInt32(x)).ToArray();
            if(A[1] == 1)
            {
                Console.WriteLine("0");
                return;
            }
            for(int i = 0; i <= 20; ++i)
                if((A[0] - 1) * i + A[0] >= A[1])
                {
                    Console.WriteLine(i + 1);
                    return;
                }
        }
    }
}


Measured memory_bytes: 13396
s = input()
al = len(s) + 1
m = ''
n = 0
su = 0
li = []
sl = []
for c in s:
    if m == '':
        m = c
    if m != c:
        li.append(n)
        m = c
        n = 0
    if c == '>': 
        n += 1
    else:
        n -= 1
li.append(n)
ni = 0
for ll in li:
    if ll < 0:
        ni = abs(ll)
        continue
    else:
        if ni != 0:
            if len(sl) == 0:
                sl.append(0)
            for nii in range(ni):
                sl.append(nii + 1)
            if ni < ll:
                sl.pop(-1)
            else:
                ll -= 1
        for lll in range(ll, -1, -1):
            sl.append(lll)
        ni = 0
if ni != 0:
    for nii in range(ni):
        sl.append(nii + 1)

#print(li)
#print(al)
#print(sl)
#print(len(sl))
print(sum(sl))


Measured memory_bytes: 78664
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using Graph = vector<vi>;  // vi <=> vl
using P = pair<int, int>;  // int <=> ll
const int MOD = 1e9+7;
const double EPS = 1e-9;

int main() {
  int n; cin >> n;
  Graph path(n, vi(n));
  rep(i,n) rep(j,n) cin >> path[i][j];

  vector<vector<bool>> exist(n, vector<bool>(n, true));
  rep(i,n) {
    rep(j,i) {
      rep(k,j) {
        if (path[j][k] > path[i][j] + path[i][k] || path[j][k] < abs(path[i][j] - path[i][k])) {
          cout << -1 << endl;
          return 0;
        }

        if (path[j][k] == path[i][j] + path[i][k]) {
          exist[j][k] = exist[k][j] = false;
          continue;
        }

        if (path[j][k] == abs(path[i][j] - path[i][k])) {
          if (path[i][j] > path[i][k]) exist[i][j] = exist[j][i] = false;
          else exist[i][k] = exist[k][i] = false;
        }
      }
    }
  }

  ll ans = 0;
  rep(i,n) rep(j,i) if (exist[i][j]) ans += path[i][j];
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	bool has_snuck[100] = {false};
	int n, k;
	cin >> n >> k;
	for(int i = 0; i < k; ++i) {
		int d;
		cin >> d;
		for(int j = 0; j < d; ++j) {
			int p;
			cin >> p;
			has_snuck[p - 1] = true;
		}
	}
	int cnt = 0;
	for(int i = 0; i < n; ++i) {
		if(!has_snuck[i]) ++cnt;
	}
	cout << cnt << '\n';
	return 0;
}

Measured memory_bytes: 3652
#include<iostream>

#define MOD 1000000007
using namespace std;
string s[2];
int main( )
{
	int n;
	cin >> n;
	cin >> s[0];
	cin >> s[1];
	int num[60],size_num = 0;
	for(int j = 0; j < n; j++){
		if(s[0][j] == s[1][j])
			num[size_num++] = 1;
		else
			num[size_num++] = 2,j++;
	}
	/*for(int j = 0; j < size_num; j++)
		cout << num[j] << " ";
	cout << endl;*/
	long long ans = (num[0] == 1 ? 3 : 6);
	for(int j = 1; j < size_num; j++){
		if(num[j - 1] == 1)
			ans = (ans*2)%MOD;
		else if(num[j] == 2)
			ans = (ans*3)%MOD;
	}
	cout <<ans << endl;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char a = 'A';
        while (sc.hasNext()) {
            char[] list = sc.nextLine().toCharArray();
            char p1 = list[0];
            char p2 = list[2];
            if (p1 == a) {
                a = p2;
            } else if (p2 == a) {
                a = p1;
            }
        }
        System.out.println(a);
    }
}


Measured memory_bytes: 26196
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
#define int      long long int
#define MOD      1000000007
#define pb       push_back
#define pf		 push_front
#define vi       vector<int>
#define mi  	 map<int,int>
#define umi		 unordered_map<int,int>
#define pii      pair<int,int>
#define ff 		 first
#define ss 		 second
#define inf		 1e18
#define case	int t;cin>>t;while(t--)
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
void pre()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
string s;
int d;
int dp[10007][2][103] = {0};
int fn(int id = 0, int tgt = 1, int sm = 0)
{	if (id == s.size())
		return sm == 0;

	if (dp[id][tgt][sm] != -1)
		return dp[id][tgt][sm];
	if (tgt == 1)
	{	int rs = 0;
		for (int i = 0; i <= s[id] - '0'; i++)
		{	rs += fn(id + 1, i == (s[id] - '0'), (sm + i) % d);
			rs %= MOD;
		}
		dp[id][tgt][sm] = rs;
		return rs;
	}
	else
	{	int rs = 0;
		for (int i = 0; i <= 9; i++)
		{	rs += fn(id + 1, 0, (sm + i) % d);
			rs %= MOD;
		}
		dp[id][tgt][sm] = rs;
		return rs;
	}
}
int32_t main()
{	pre();
//case
	{	cin >> s >> d;
		memset(dp, -1, sizeof(dp));
		int a1 = fn();
		cout << (a1 - 1 + MOD) % MOD << endl;
	}
	return 0;
}

Measured memory_bytes: 17152
// ABC154_D
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <tuple>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stack>
#include <queue>
#include <algorithm>
#include <functional>  // std::greater<T>()
#include <utility>  // std::swap()
#include <numeric>  // accumulate(ALL(vec), 0)  0 は初期値
#include <bitset>  // static_cast<std::bitset<8>>
#include <sstream>  // std::stringstream
#include <cmath>
#include <cstring>  // std::memset
#include <climits>  // INT_MIN
#include <cctype>  // std::isdigit()
#include <iomanip>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> pll;
#define rep(i, n) for (ll i=0; i < n; i++)  // 0 ~ n-1
#define rep1(i, n) for (ll i=1; i <= n; i++)  // 1 ~ n
#define repr(i, n) for (ll i=n-1; i >= 0; i++)  // n-1 ~ 0
#define all(vec) (vec).begin(), (vec).end()
#define sum(vec) accumulate(all(vec), 0LL)  // 0 は初期値
#define min_vec(vec) min_element(all(vec))  // iterator: * を先頭につける
#define max_vec(vec) max_element(all(vec))  // iterator: * を先頭につける
#define idx(vec, element_iter) distance((vec).begin(), element_iter)
const ll INF = 1LL<<60;  // 10^18（const int inf = 1<<29;）
const double PI = acos(-1);

double sum_suretu(ll n) {
    // 初項 1, 公差 1, 項数 n の等差数列の和
    return ((double)n/2)*((double)(1+n));
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    // input(sunippets: inpv, inpn, inps)
    ll N, K;
    cin >> N >> K;
    vector<double> vec(N);
    rep(i, N) cin >> vec[i];
    
    // calculation
    vector<double> ex(N);
    rep(i, N) ex[i] = sum_suretu(vec[i])/vec[i];
    
    double partial_sum = 0;
    rep(i, K) partial_sum += ex[i];  // 部分和の初期値
    double res = partial_sum;
    
    for (ll i = 1; i < N-K+1; ++i) {
        partial_sum = partial_sum - ex[i-1] + ex[i+K-1];
        res = max(res, partial_sum);
    }
    cout << res << "\n";
    
    return 0;
}



Measured memory_bytes: 3328
#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repl(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define rep2l(i, s, n) for (ll i = (ll)(s); i < (ll)n; i++)

int main() {
    ll N;
    string S;
    cin >> N >> S;
    vector<ll> count(26, 0);
    rep(i, N) {
        char s = S[i];
        int num = (int)(s-'a');
        count[num]++;
    }
    ll ans = 1;
    rep(i, 26) {
        ans *= (count[i]+1);
        ans %= 1000000007;
    }
    if (ans == 0) {
        cout << 1000000006 << endl;
    }
    else {
        cout << ans-1 << endl;
    }
}

Measured memory_bytes: 512
n, m = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(n)]
c = [list(map(int, input().split())) for _ in range(m)]


def dist(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])


for i in range(n):
    x = min(c, key=lambda x: dist(p[i], x))
    num = c.index(x) + 1
    print(num)


Measured memory_bytes: 9168
#include <bits/stdc++.h>
#define SZ(x) ((int)(x).size())
typedef long long ll;
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout.setf(ios::fixed); cout.precision(20);
    int n, m; cin >> n >> m;
    vector<int> pa(n + 10);
    iota(pa.begin(), pa.end(), 0);
    vector<int> sz(n + 10, 1);
    ll res = (ll) n * (ll) (n - 1) / 2ll;
    auto root = [&](int x) {
        while (pa[x] != x) {
            x = pa[x] = pa[pa[x]];
        }
        return x;
    };
    auto unite = [&](int x, int y) {
        x = root(x), y = root(y);
        if (x == y) {
            return false;
        }
        if (sz[x] < sz[y]) {
            swap(x, y);
        }
        sz[x] += sz[y];
        pa[y] = x;
        return true;
    };
    vector<pair<int, int>> a;
    for (int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;
        a.emplace_back(x, y);
    }
    reverse(a.begin(), a.end());
    vector<ll> ans;
    for (int i = 0; i < m; i++) {
        ans.push_back(res);
        int x = a[i].first, y = a[i].second;
        ll sz1 = sz[root(x)], sz2 = sz[root(y)];
        if (unite(x, y)) {
            res -= sz1 * sz2;
        }
    }
    for (int i = m - 1; i >= 0; i--) {
        cout << ans[i] << "\n";
    }
}


Measured memory_bytes: 3828
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		ArrayList<Integer> index = new ArrayList<Integer>();
		ArrayList<Integer> search = new ArrayList<Integer>();
		for(int i=2; i<=110000; i++) search.add(i);
		index.add(2);
		while(index.get(index.size()-1) < Math.sqrt(110000)) {
			int now =  search.get(0);
			if(now != 2) index.add(now);
			int limit = search.size();
			for(int i=limit-1; i>=0; i--) if(search.get(i) % now == 0) search.remove(i);
		}
		for(int i=0; i<search.size()-1; i++) {
			index.add(search.get(i));
		}
		while(in.hasNext()) {
			int n = in.nextInt();
			if(n == 0) break;
			int sum = 0;
			for(int i=0; i<n; i++) {
				sum += index.get(i);
			}
			System.out.println(sum);
		}
	}
}

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

#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define sz(a) int((a).size())
#define endl '\n'

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef long long ll;

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//#ifndef ONLINE_JUDGE
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	//#endif
	string s;
	cin>>s;
	int n=sz(s),ans=0;
	for(int i=0,j=n-1;i<n/2;++i,--j){
		if(s[i]!=s[j])
			++ans;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
count [] _ = 0
count (c:cs) '0'
  | c == '0' = count cs '1'
  | c == '1' = 1 + count cs '1'
count (c:cs) '1'
  | c == '1' = count cs '0'
  | c == '0' = 1 + count cs '0'


ret s = min (count s '0') (count s '1')


main = do
  s <- getLine
  putStrLn $ show $ ret s


Measured memory_bytes: 7548
#include <iostream>
#include <stdio.h>
#include <string>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <limits.h>
#include <map>
#include <numeric>
 
namespace test {
  std::string to_string(char val) {
    return std::string(1, val);
    // return std::string{val};
  }
}
 
using namespace std;
 
 
 
int main(void) {
  string s; cin >> s;
 
  int n = s.size();
 
  int count_1 = 0, count_0 = 0;
 
  for(int i = 0; i < n ; i++){
    if(s[i] == '1'){
      count_1++;
    } else if(s[i] == '0'){
      count_0++;
    }
  }
 
  int result = min(count_1, count_0) * 2;
 
  cout << result << endl;
 
  return 0;
}

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

using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
#define REP(i,n) for(ll i = 0;i < (ll)n;i++)
#define REPD(i,n) for(ll i = (ll)n - 1;i >= 0;i--)
#define ALL(x) (x).begin(),(x).end()
#define FILLl(n,first_dimension_size,value) fill((ll*)n,(ll*)(n+first_dimension_size),value)
#define FILL(n,first_dimension_size,value) fill((int*)n,(int*)(n+first_dimension_size),value)
#define INF (1 << 29)
#define MOD 1000000007
//int dx[4] = {1,0,0,-1};
//int dy[4] = {0,1,-1,0};


int main(){

  int r,d,x2000;
  cin >> r >> d >> x2000;
  REP(i,10){
    x2000 = x2000*r - d;
    cout << x2000 << endl;
  }  
  



  return 0;
}


Measured memory_bytes: 256
"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_c

C - Vaction
"""
INF = 100000007
import collections

def solve(troikas):
    dp = collections.defaultdict(lambda: -INF)
    for act in range(3):
        dp[(0, act)] = troikas[0][act]

    for i in range(1, N):
        for act in range(3):
            dp[(i, act)] = max(
                dp[(i - 1, prev_act)] + troikas[i][act]
                for prev_act in range(3)
                if prev_act != act
            )
    return max(dp[(N - 1, act)] for act in range(3))

N = int(input())
troikas = [[int(s) for s in input().split()] for _ in range(N)]
res = solve(troikas)
print(res)


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

using namespace std;

int main() 
{   
        string s;
        int a=0,b=0;
        cin>>s;
        for (int i=0;i<s.length();i++)
        {
            if (s[i] == 'A') a++;
            if (s[i] == 'B') b++;
        }
        if (a==0 || b==0) cout<<"No"<<endl;
        else    cout<<"Yes"<<endl;
        return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(ll 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 Per(i,sta,n) for(int i=n-1;i>=sta;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++)
typedef long double ld;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

ll n,k;

void solve(){
  cin >> n >> k;
  if(k>(n+1)/2){
    cout << -1 << endl;
    return;
  }
  if(n%2==0){
    ll m=n/2;
    rep(i,m+1){
      cout << k+2*i << " " << k+4*m-1-i << " " << k+5*m+i-1 << endl;
    }
    rep(i,m-1){
      if(i==m-2)cout << k+1+2*i << " " << k+3*m-3-i << " " << k+4*m+i << endl;
      else cout << k+1+2*i << " " << k+3*m-2-i << " " << k+4*m+i << endl;
    }
  }
  else{
    ll m=(n+1)/2;
    rep(i,m){
      cout << k+2*i << " " << k+4*m-3-i << " " << k+5*m-3+i << endl;
    }
    rep(i,m-1){
      cout << k+2*i+1 << " " << k+3*m-3-i << " " << k+4*m-2+i << endl;
    }
  }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(50);
    solve();
}

Measured memory_bytes: 2304
#include<cstdio>
#define mo 1000000007ll
using namespace std;
long long fac[2000100],nifac[2000100];
int x1,x2,x3,x4,x5,x6,y1,y2,y3,y4,y5,y6;
long long getmi(long long a,long long x)
{
	long long ans=1;
	while (x)
	{
		if (x&1) ans=ans*a%mo;
		a=a*a%mo;
		x>>=1;
	}
	return ans;
}
long long W(int n,int m){n++;m++;return fac[n+m]*nifac[n]%mo*nifac[m]%mo;}
long long work(int x3,int y3,int x4,int y4)
{
	return (W(x3-x1,y3-y1)-W(x3-x1,y3-y2)-W(x3-x2,y3-y1)+W(x3-x2,y3-y2))*
		   (W(x6-x4,y6-y4)-W(x5-x4,y6-y4)-W(x6-x4,y5-y4)+W(x5-x4,y5-y4))%mo;
}
int main()
{
	fac[0]=1;for (int i=1;i<=2000000;i++) fac[i]=fac[i-1]*i%mo;
	nifac[2000000]=getmi(fac[2000000],mo-2);for (int i=1999999;i>=0;i--) nifac[i]=nifac[i+1]*(i+1)%mo;
	long long ans=0;
	scanf("%d%d%d%d%d%d%d%d%d%d%d%d",&x1,&x2,&x3,&x4,&x5,&x6,&y1,&y2,&y3,&y4,&y5,&y6);
	x2++;y2++;x5--;y5--;
	for (int i=x3;i<=x4;i++) ans+=work(i,y4,i,y4+1)*(y4+i+1)%mo-work(i,y3-1,i,y3)*(y3+i)%mo;
	for (int i=y3;i<=y4;i++) ans+=work(x4,i,x4+1,i)*(x4+i+1)%mo-work(x3-1,i,x3,i)*(x3+i)%mo;
	printf("%lld\n",(ans%mo+mo)%mo);
}


Measured memory_bytes: 31360
#include<stdio.h>
#include<string.h>
int main()
{
  int i,j,k,count=0;
  char s[100],p[100],a;
  scanf("%s",s);
  scanf("%s",p);
  int lens=strlen(s);
  int lenp=strlen(p);
  for(i=0;i<=lens;i++){
    a=s[0];
    for(j=0;j<=lens;j++){
      s[j]=s[j+1];
    }
    s[lens-1]=a;
    if(s[0]==p[0]){
      for(k=0;k<lenp;k++){
	if(s[k]==p[k]){
	  count++;
	}
      }
    }
    if(count==lenp)break;
    count=0;
  }
  if(count==lenp)printf("Yes\n");
  else printf("No\n");
  return 0;
}

Measured memory_bytes: 944
n,k = map(int,input().split())
a = [int(i) for i in input().split() ]

d = {}
for i in a:
  if i in d:
    d[i] += 1
  else:
    d[i] = 1
    
    
d = sorted(d.values())
if len(d) > k:
  ans = 0
  for i in range(len(d)-k):
    ans += d[i]
  print(ans)
else:
  print(0)
  

Measured memory_bytes: 32264
import java.util.*;
public class Main {
	
	public static void main(String... args) {
		Scanner sc = new Scanner(System.in);
		
		long N = sc.nextLong();
		long P = sc.nextLong();
		long baseP = P;
		
		if (N == 1) {
			System.out.println(P);
			return;
		}
		
		long ans = 1;
		for (long i = 2; i * i <= baseP; i++) {
			int count = 0;
			while(P % i == 0) {
				count++;
				P /= i;
			}
			
			if (count >= N) {
				ans = ans * (long)Math.pow(i, (count / N));
			}
		}
		
		System.out.println(ans);
	}
}



Measured memory_bytes: 22868
#include<stdio.h>
int main(void)
{
	int a,b;

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

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

	return 0;
}


Measured memory_bytes: 2136
import sys

line_size, row_size = map(int, input().split())
mapmap = []#地図初期化

for i in range(line_size):
    mapmap.append(list(input()))

#探索
def Start_check(mapmap, px, py):
    start_flg = False
    move_x = [1, -1, 0, 0]
    move_y = [0, 0, 1, -1]
    for i in range(4):#動ける範囲で探索
        nx = px + move_x[i]
        ny = py + move_y[i]
        if 0 <= nx and nx < line_size and 0 <= ny and ny < row_size:
            if mapmap[nx][ny] == '#':#もし黒塗りなら
                start_flg = True
    
    if start_flg == False:
        print('No')
        sys.exit()

#Main
count = 0#探索回数（塗り絵した回数）
for i in range(line_size):
    for j in range(row_size):
        if mapmap[i][j] == '#':
            Start_check(mapmap, i, j)
            count += 1

#何もしなかった場合
print('Yes')

Measured memory_bytes: 3064
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#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=5e18;
typedef pair<int,int> P;
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  int n,a;
  cin >> n;
  int dp[n]={};
  for(int i=0; i<n; i++) {
    dp[i]=inf;
  }
  for(int i=0; i<n; i++) {
    cin >> a;
    *lower_bound(dp,dp+n,a)=a;
  }
  cout << lower_bound(dp,dp+n,inf)-dp << endl;
}



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

int main() {
  int n,k;cin>>n>>k;
  int pn[n];rep(i,n)cin>>pn[i];
  sort(pn,pn+n);
  int s=0;
  rep(i,k)s+=pn[i];
  cout<<s;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {
 /* #ifndef ONLINE_JUDGE
      // for getting input from input.txt
      freopen("input.txt", "r", stdin);
      // for writing output to output.txt
      freopen("output.txt", "w", stdout);
  #endif*/
fast();
//ll  t;cin>>t;while(t--)
{
  int a,b,c;
  cin>>a>>b>>c;
  if(c<=b&&c>=a)
  {
    Yes
  }
  else
  {
    No
  }

}
return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep2(i, s, n) for(int i=s; i<(n); ++i)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;

template<typename T>
using priority_queue_rev = priority_queue<T, vector<T>, greater<T> >;

static const int INTINF = (2147483647 >> 1); // 10^9 + 5000
static const ll LLINF = (9223372036854775807 >> 1);
static const int MAX = 1e5+1;
static const ll MOD = 1e9+7;

namespace Kunitaka{
    template<
        typename TYPE,
        std::size_t SIZE
    >
    std::size_t array_length(const TYPE (&array)[SIZE])
    {
        return SIZE;
    }

    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; }
}
using namespace Kunitaka;
namespace Printer{
    void br(){
        cout << endl;
    }

    void loop_cnt(int i){
        cout << "i = " << i << endl;
    }

    void loop_cnt(int i, int j){
        cout << "i = " << i << ", " << "j = " << j << endl;
    }

    template<class T>
    void print(T x){
        cout << x << endl;
    }

    template<class T, class S>
    void print(T x, S y){
        cout << x << "," << y << endl;
    }

    template<class T, class S, class U>
    void print(T x, S y, U z){
        cout << x << "," << y << "," << z << endl;
    }

    template<class T, class S>
    void print(pair<T, S> p){
        cout << p.first << ", " << p.second << endl;
    }

    template<
        typename TYPE,
        std::size_t SIZE
    >
    void print(const TYPE (&array)[SIZE]){
        int lim = array_length(array);
        for(int i=0; i<lim; i++){
            if(i) cout << " ";
            cout << array[i];
        }
        cout << endl;
    }

    template<class S>
    void print(vector<S> v){
        for(int i=0; i<v.size(); i++){
            if(i) cout << " ";
            cout<< v[i];
        }
        cout << endl;
    }

    template<class S>
    void print(vector<vector<S> > vv){
        for(int i=0; i<vv.size(); i++){
            for(int j=0; j<vv[i].size(); j++){
                if(j) cout << " ";
                cout << vv[i][j];
            }
            cout << endl;
        }
    }

    void yesno(bool x){
        if(x) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
};
using namespace Printer;

int main(int argc, const char * argv[]) {
    //提出時、消す----//
    //--------------//


    // input
    cout << fixed << setprecision(10);
    int a, b; cin >> a >> b;
    int tmp = a + b;
    if(tmp % 2 == 0){
        cout << tmp /2 << endl;
        return 0;
    }

    cout << "IMPOSSIBLE" << endl;

    
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int findSumOfDigits(int n)
{
  int sum = 0;
  while (n > 0)
  { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}
main()
{
  int N;
  cin >> N;
  int sum = findSumOfDigits(N);
  if (N%sum == 0)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>

using namespace std;

int main(){
  int n; cin >> n;
  string s; cin >> s;
  if(n % 2){
    cout << "No" << endl;
    return 0;
  }
  for(int i = 0; i < n/2; i++){
    if(s[i] != s[i+n/2]){
      cout << "No" <<endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}


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

using namespace std;
using ll = long long;

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

    map<ll, ll> l;
    map<ll, ll> r;
    for (int i = 1; i <= N; i++) {
        ll a;
        cin >> a;
        l[a + i]++;
        r[i - a]++;
    }

    ll output = 0;
    for (auto e : l) {
        output += r[e.first] * e.second;
    }
    cout << output << endl;

    return 0;
}


Measured memory_bytes: 37912
B1 = 97
B2 = 101
DIV = 1 << 32

def init(r)
  f = Array.new(r){ Array.new }
  r.times do |i|
    f[i] = gets.chomp.split("").map(&:ord)
  end
  f
end

def calc(f, r, c)
  tmp = Array.new(r){ Array.new(c, 0) }
  t1 = 1
  $c.times{ t1 = t1 * B1 % DIV }
  r.times do |i|
    e = 0
    $c.times do |j|
      e = e*B1 + f[i][j]
    end
    (0..c-$c).each do |j|
      tmp[i][j] = e
      e = (e*B1 - t1*f[i][j] + f[i][j+$c] + DIV) % DIV if j < c - $c
    end
  end

  t2 = 1
  $r.times{ t2 = t2 * B2 % DIV }
  (0..c-$c).each do |j|
    e = 0
    $r.times{ |i| e = e*B2 + tmp[i][j] }
    (0..r-$r).each do |i|
      $hash[i][j] = e
      e = (e*B2 - t2*tmp[i][j] + tmp[i+$r][j] + DIV) % DIV if i < r - $r
    end
  end
end

h, w = gets.split.map(&:to_i)
f1 = init(h)
$r, $c = gets.split.map(&:to_i)
f2 = init($r)
if h >= $r && w >= $c
  $hash = Array.new(h){ Array.new(w, 0) }
  calc(f2,$r,$c)
  key = $hash[0][0]
  calc(f1,h,w)
  h.times do |i|
    w.times do |j|
      puts "#{i} #{j}" if $hash[i][j] % DIV == key % DIV
    end
  end
end

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

int main()
{
	string S;
	while (cin >> S) {
		int n = S.size();
		int a = 0, b = 0;
		for (int i = 0; i + 3 <= n; i++) {
			if (S.substr(i, 3) == "JOI") {
				a++;
			}
		}
		cout << a << endl;
		for (int i = 0; i + 3 <= n; i++) {
			if (S.substr(i, 3) == "IOI") {
				b++;
			}
		}
		cout << b << endl;
	}
	return 0;
}



Measured memory_bytes: 3208
#define _USE_MATH_DEFINES
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;


int main()
{
	int c = 0;
	cin >> c;
	for (int i = 0; i < c; ++i)
	{
		cout << "ACL";
	}
}


Measured memory_bytes: 3040
#include<stdio.h>

int main()
{
  int N, A, B;
  int x, y;

  scanf("%d", &N);
  scanf("%d", &A);
  scanf("%d", &B);

  x = N*A;
  y = B;

  if(x<=y){
    printf("%d", x);
  } else {
    printf("%d", y);
  }

  return 0;

}

Measured memory_bytes: 128
s = str(input())
i = 0
count = 0
while(i < len(s)):
    if((i+1)%2 == 0 and s[i] == 'R'):
        count += 1
    if((i+1)%2 == 1 and s[i] == 'L'):
        count += 1
    i += 1
if(count == 0):
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3060
S = input()
newS = S.replace("BC","D")
A_count = 0
ans = 0
for i in range(len(newS)):
    if newS[i] == "A":
        A_count += 1
    elif newS[i] == "D":
        ans += A_count
    else:
        A_count = 0
print(ans)

Measured memory_bytes: 42480