akhauriyash/Code-Regression huggingface dataset:
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 = new int[n+1][3];
        int[][] dp = new int[n+1][3];
        for (int i=0; i<n; i++) {
            for (int j=0; j<3; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        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;
                    dp[i+1][k] = Math.max(dp[i+1][k], dp[i][j] + a[i][k]);
                }
            }
        }
        int ans = 0;
        for (int j=0; j<3; j++) {
            ans = Math.max(ans, dp[n][j]);
        }
        System.out.println(ans);
    }
}


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

#define LL long long
#define DD long double

#define M 1000000007
#define INF 1e18

void setIO(string s = "") { 
  cin.sync_with_stdio(0); cin.tie(0);
  if (s.size()) s += ".in", freopen(s.c_str(), "r", stdin);
}

int tt = 1;
void solve() {
  string s;
  cin >> s;
  int n = s.size();
  while (n--) cout << "x";
  cout << endl;
}

int main() {
  setIO();
  while (tt--) {
    solve();
  }
  return 0;
}

Measured memory_bytes: 3564
f(a,b,x,p,q){for(p=q=1;x&p|~(a^b)&p?p<<=1:x&q|p==q?q<<=1:0;);~x?f(a,a^q,x^p),f(a^p^q,b,x^p):printf("%d ",a);}main(n,a,b){scanf("%d%d%d",&n,&a,&b);__builtin_popcount(a^b)%2?puts("YES"),f(a,b,-1<<n):puts("NO");}

Measured memory_bytes: 896
#include<stdio.h>

int n, p[100], q[100];

void swap(int swap1, int swap2) {
    for (int i=0; i<n; i++) {
        if (i == swap1) {
            q[i] = p[swap2];
        } else if (i == swap2) {
            q[i] = p[swap1];
        } else {
            q[i] = p[i];
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        scanf("%d", &p[i]);
    }
    int result = 1;
    for (int i=0; i<n; i++) {
        for (int j=i; j<n; j++) {
            swap(i, j);
            result = 1;
            for (int k=0; k<n-1; k++) {
                if (result == 1 && q[k] > q[k+1]) {
                    result = 0;
                }
            }
            if (result == 1) {
                break;
            }
        }
        if (result == 1) {
            break;
        }
    }
    if (result == 1) {
        printf("YES");
    } else {
        printf("NO");
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 128
def main():
    N = int(input())
    A = list(map(int,input().split()))

    if 0 in A:
        print(0)
        return

    prod = 1
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return

    print(prod)


main()


Measured memory_bytes: 21664
x,y,a,b,c=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))

p.sort(reverse=1)
q.sort(reverse=1)
r.sort(reverse=1)

m=p[:x]+q[:y]+r
m.sort(reverse=1)

print(sum(m[:(x+y)]))

Measured memory_bytes: 112236
#include <algorithm>
#include <iostream>
#include <limits.h>
#include <stdlib.h>
#include <string>
#include <vector>

#define el endl
#define fd fixed
#define INF INT_MAX/2-1

using namespace std;

int main() {
  int n, q, m, tmp, max, res;
  while (cin >> n >> q, n | q) {
    vector<int> day(100, 0);
    while (n--) {
      cin >> m;
      while (m--) {
        cin >> tmp;
        day[tmp]++;
      }
    }
    max = 0;
    for (int i = 0; i < 100; i++) {
      if (max < day[i]) {
        max = day[i];
        res = i;
      }
    }
    if (max < q) res = 0;
    cout << res << el;
  }
}

Measured memory_bytes: 1196
n= int(input())
s = [input() for _ in range(n)]
r = {}
g=0
for c in s:
    r[c] = r.get(c,0) + 1
    g = max(g,r[c])
word = []
for c in r.keys():
    if r[c]==g:word.append(c)
word.sort()
for c in word:print(c)

Measured memory_bytes: 35216
#include<iostream>

using namespace std;

int main() {
    #ifdef EV
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif

    long long n, d, counter=0;
    cin>>n>>d;
    while(n--) {
        long long a, b;
        cin>>a>>b;
        if(a*a + b*b <= d*d) counter++;
    }
    cout<<counter<<"\n";

    return 0;
}

Measured memory_bytes: 3644
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

template <typename TYPE>
void print_vec(const vector<TYPE>& v){
	for(int i=0; i<v.size(); i++){
		cout << v[i] << " ";
	}
	cout << endl;
}

template <typename TYPE>
void print_vec2(const vector<vector<TYPE>>& v){
  cout << endl;
  for(int i=0; i<v[0].size(); i++) cout << i << "   "; 
  cout << endl;
	for(int i=0; i<v.size(); i++){
		cout << "i=" << i << ":   " << endl;
		for(int j=0; j<v[i].size(); j++){
			if(v[i][j] == 0) cout << "\x1B[0m" << v[i][j] << "   ";
      else cout << "\x1B[31m" << v[i][j] << "   ";//https://stackoverrun.com/ja/q/12618775
		}
		cout << "\x1B[0m" << endl;
	}
}
 
int main(){
	string S;
	cin >> S;
	int Q;
	cin >> Q;
	
	int is_reverse = 0;//リバースした回数
	for(int i=0; i<Q; i++){
		int t;
		cin >> t;
		if(t==1){
			//reverse(S.begin(), S.end());
			is_reverse++;
			continue;
		}
		int f; 
		char c;
		cin >> f >> c;
		if(f==1 && is_reverse%2==0  || f==2&&is_reverse%2==1){
			S = c + S;
		}
		else{
			S.push_back(c);
		}

	}

	if(is_reverse%2==0){
		cout << S << endl;
		return 0;
	}
	else for(int i=S.size()-1; i>=0; i--) cout << S[i];
	cout << endl;
}


Measured memory_bytes: 4720
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
typedef pair<int, int> P_i;
typedef pair<double,double> P_d;
#define rep(i,n) for(int i=0;i<(n);++i)
#define alrep(i,j,n) for(int i=0;i<(n);++i)for(int j=i+1;j<(n);++j)
#define Yes cout << "Yes" << endl;
#define No cout << "No" << endl;int ans=0;
#define answer cout << ans << endl;
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; }
const int MOD=1e9+7;
const long long INF = 1LL << 60;

using Graph = vector<vector<int>>;

int tmp=0;
// 深さ優先探索
vector<bool> seen;
void dfs(const Graph &G, int v, vector<int> &vec) {
  seen[v] = true; // v を訪問済にする
  tmp++;
  vec.push_back(v);
  // v から行ける各頂点 next_v について
  for (auto next_v : G[v]) {
    if (seen[next_v]) continue; // next_v が探索済だったらスルー
    dfs(G, next_v, vec); // 再帰的に探索
  }

}

signed main(){
  // 頂点数と辺数
  int N, M, K; cin >> N >> M >> K;

  int ans[N]={};
  // グラフ
  Graph Friend(N);
  for (int i = 0; i < M; ++i) {
    int a, b;
    cin >> a >> b;
    a--;b--;
    Friend[a].push_back(b);
    Friend[b].push_back(a);
  }
  Graph Block(N);
  for (int i = 0; i < K; ++i) {
    int a, b;
    cin >> a >> b;
    a--;b--;
    Block[a].push_back(b);
    Block[b].push_back(a);
  }
  //for(auto h:Block[1]) cout << h << endl;

  // 頂点 0 をスタートとした探索
  seen.assign(N, false); // 全頂点を「未訪問」に初期化
  for (int v = 0; v < N; ++v) {
    vector<int> node;
    tmp=0;
    if (seen[v]) continue;
    dfs(Friend, v, node); // v が未探索なら v を始点とした DFS を行う
    //tmp:node数 node:行けるnodeが格納されている
    sort(node.begin(),node.end());
    for(auto vv: node){
      int block=0;
      for(auto bv:Block[vv]){
        if(binary_search(node.begin(),node.end(),bv)){
          block++;
        }

        //cout << vv << " block: " <<  block << endl;
      }
      //cout << block << endl;
      ans[vv]=tmp-Friend[vv].size()-1-block;
    }
  }
  rep(i,N-1){
    cout << ans[i] << " ";
  }
  cout << ans[N-1] << endl;
  return 0;
}


Measured memory_bytes: 15484
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
	// write your code here
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int w = in.nextInt();

        int[] arrW = new int[n];
        long[] arrV = new long[n];

        long[][] arr = new long[n+1][w+1];

        for (int i=0;i<n;i++){
            int tmp = in.nextInt();
            arrW[i]=tmp;
            long temp = in.nextLong();
            arrV[i] = temp;
        }

        for(int row=0;row<n+1;row++){
            for(int col=0;col<w+1;col++){
                if(row==0 || col==0) arr[row][col]=0;
                else if(col - arrW[row-1] >=0)  arr[row][col] = Math.max(arr[row-1][col], arr[row-1][col-arrW[row-1]] + arrV[row-1] );
                else arr[row][col] = arr[row-1][col];
            }

        }

        long ans = arr[n][w];
        System.out.println(ans);

    }
}


Measured memory_bytes: 124756
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  int K;
  cin >> N >> K;
 
  vector<int> vec(N); // 果物の価格
 
  // 数学の点数データを受け取る
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  
  if (vec.size() == 1) {
  	cout << vec.at(0);
    return 0;
  } else {
    // ソートで昇順にする
  	sort(vec.begin(), vec.end());
    
    int answer;
    
    // K種類分取得
    for (int i = 0; i < K; i++) {
    	answer += vec.at(i);
    }
    
    cout << answer << endl;
    return 0;
    
  }

}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define F first
#define S second


int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin>>s;
    int i = 0,ans = 0;
    while(i < 3)
    {
    	if(s[i] == 'S')
    	{
    		i++;
    	}
    	else
    	{
    		int j = i;
    		while(j < 3)
    		{
    			if(s[j] == 'S')
    			{
    				break;
    			}
    			j++;
    		}
    		ans = max(ans,j-i);
    		i = j;
    	}
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define rep(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rer(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--)
#define sz(v) (int)(v).size()
#define pb push_back
#define sc second
#define fr first
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
using namespace std;
typedef long long int ll;
typedef pair <int, int> P;

const ll MOD=1000000007;
int A,B;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>A>>B;
    if(A>=13) cout <<B<<"\n";
    else if(A>=6) cout <<B/2<<"\n";
    else cout <<0<<"\n";
}

Measured memory_bytes: 256
import java.util.Scanner;

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

        char c = sc.next().toCharArray()[0];
        if (Character.isUpperCase(c)) {
            System.out.println("A");
        } else {
            System.out.println("a");
        }
    }
}


Measured memory_bytes: 35716
package main

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

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanLines)
	for sc.Scan() {
		s := strings.Split(sc.Text(), " ")
		x, err := strconv.Atoi(s[0])
		if err != nil {
			panic(err)
		}
		y, err := strconv.Atoi(s[1])
		if err != nil {
			panic(err)
		}

		if x == 0 && y == 0 {
			break
		}
		if x < y {
			fmt.Printf("%d %d\n", x, y)
		} else {
			fmt.Printf("%d %d\n", y, x)
		}
	}
}



Measured memory_bytes: 1176
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <functional>
#include <bitset>
#include <cmath>
#include <stack>
#include <iomanip>
typedef long long ll;
using namespace std;

const int MOD = 1000000007;
ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }

int main()
{
    int N;
    cin >> N;
    vector<int> d(N);
    for(int i = 0; i < N; i++)  cin >> d[i];
    sort(d.begin(),d.end());
    cout << d[N/2] - d[N/2 - 1] << endl;

}


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

int main(){
    string s;
    cin >> s;
    string year, month, day;
    //substr(i,k)はi番目の文字を基点に長さkの文字列を返す
    year = s.substr(0,4);
    month = s.substr(5,2);
    day = s.substr(8,2);
    
    int date = atoi((year + month + day).c_str());
    
    if(date <= 20190430) cout << "Heisei" << endl;
    else cout << "TBD" << endl;
}

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

using namespace std;

typedef long long lli;
typedef double lld;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<double> vdl;
typedef vector<vector<lli>> mat;
typedef vector<vdl> mad;
typedef unordered_map<lli,unordered_map<lli,lli>> graph;
typedef complex<double> cmp;
typedef vector<cmp> vcl;

graph t;

lli n,l;
lli m;
lli ans = 0;

void trytree(string& $,lli node,lli i){
  if(i == $.size()) return;
  for(auto& x : t[node]){
    if(x.second == $[i]) return trytree($,x.first,i+1);
  }
  t[node][m] = $[i];
  m++;
  trytree($,m-1,i+1);
  return;
}

void dfs(lli node,lli d){
  // cout << node << endl;
  if(t[node].size() == 1){
    lli x = 1;
    while((l-d)%x == 0) x <<= 1;
    x >>= 1;
    ans ^= x;
  }
  for(auto& x : t[node]){
    dfs(x.first,d+1);
  }
}

int main(){
  cin >> n >> l;
  m = 1;
  for(lli i = 0;i < n;i++){
    string $;
    cin >> $;
    trytree($,0,0);
  }
  dfs(0,0);
  cout << (ans == 0 ? "Bob" : "Alice") << endl;
}


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

#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define intll int long long
const int INF = 1e9;
const int MOD = 1e9 + 7;


int main() {
  map<int,int> data ;
  int n , m ; 
  cin >> n  ; 
  string ans = "YES" ; 
  
  rep(i,n){
    int p ; 
    cin >> p ; 
    data[p] ++ ;
  }
  
  cin >> m ; 
  
  rep(i,m){
    int p ; 
    cin >> p ; 
    data[p] -- ; 
    if(data[p] <0 ) ans = "NO" ;
  }
  
  cout << ans ;
  
  
}


Measured memory_bytes: 12968
l = list()
flg=True
for i in range(3):
  l.extend(input().split())
cnt = [0,0,0,0]
l = [int(i) for i in l]
for i in l:
  cnt[i-1]+=1
for i in cnt:
  if i > 2:
    flg=False
if flg:
  print("YES")
else:
  print("NO")

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

int main() {
  int H,N;
  cin >> H >> N;
  
  for(int i=0;i<N;i++){
    int a;
    cin >> a;
    H -= a;
    if(H<=0){
      cout << "Yes" << endl;
      return 0;
    }
  }
  
  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
import java.math.*;

class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int w=sc.nextInt();
int a=100000;
for(int i=0;i<w;i++){
a+=a/20;
BigDecimal x=new BigDecimal(a);
x=x.setScale(-3,RoundingMode.CEILING);
a=x.intValue();
}
System.out.println(a);
}
}

Measured memory_bytes: 17228
N, K = map(int, input().split())
li = [0] * (10 ** 5 +1)
for i in range(N):
    a, b = map(int, input().split())
    li[a] += b

count = 0
for i in range(1, 10 ** 5 + 1):
    count += li[i]
    if count >= K:
        print(i)
        break


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

typedef long long   ll;
typedef long double ld;
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    int count;
    int ans=n;
    for(int i = 0; i <= n; i++) {
        count=0;

        int sp=i;
        while(sp>0) {
            count+=sp%6;
            sp/=6;
        }
        int np=n-i;
        while(np>0) {
            count+=np%9;
            np/=9;
        }
        ans=min(ans,count);
    }

    cout << ans << "\n";
    return 0;
}

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

#define lli long long int
#define mpr make_pair
#define pr pair<lli,lli>
#define pb push_back
#define vl vector<lli>
#define mp map<lli,lli>
#define all(x) x.begin(),x.end()
#define FOR(i,n) for(lli i=0;i<(lli)n;i++)
#define FOR1(i,j,n) for(lli i=j;i<(lli)n;i++)
#define mod 1000000007

lli gcd(lli a,lli b)
{
	if(b==0)
	return a;
	return gcd(b,a%b);
}

lli power(lli x,lli n,lli m)
{
	lli res=1;
	while(n>0)
	{
		if(n&1) res=(res*x)%m;
		x=(x*x)%m;
		n=n>>1;
	}
	return res;
}

lli modInverse(lli n,lli  p)
{
	return power(n,p-2,p);
}

lli nCr(lli n,lli r,lli p)
{
	if(r==0)
	return 1;
	lli fac[n+1];
	fac[0]=1;
	for(lli i=1;i<=n;i++)
	fac[i]=fac[i-1]*i%p;
	return ((fac[n]* modInverse(fac[r], p) % p )%p* 
            modInverse(fac[n-r], p) % p) % p; 
}

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	lli n,res=0;
	cin>>n;
	vl v(n);
	mp m,cnt;
	for(lli i=0;i<n;i++)
	{
		cin>>v[i];
		cnt[v[i]]++;
	}
	sort(all(v));
	for(lli i=0;i<n;i++)
	{
		for(lli j=2*v[i];j<=v.back();j+=v[i])
		m[j]++;
	}
	for(lli i=0;i<n;i++)
	{
		if(cnt[v[i]]>1) continue;
		if(m[v[i]]==0) res++;
	}
	cout<<res<<endl;
	/*for(lli i=0;i<n;i++)
	{
		int cnt=0;
		for(lli j=1;j*j<=v[i];j++)
		{
			if(v[i]%j==0)
			{
				if(j!=v[i]&&m[j]==1||j==v[i]&&m[j]>1) 
				{
					cnt++;
					break;
				}
				if(v[i]/j!=v[i]&&m[v[i]/j]==1||v[i]/j==v[i]&&m[v[i]/j]>1)
				{
					cnt++;
					break;
				}
				//if(j!=v[i]&&m[j]==1&&j*j==v[i]) cnt--;
			}
		}
		if(cnt==0) res++;
	}
	cout<<res<<endl;*/
	
	
return 0;
}


Measured memory_bytes: 76392
#include<bits/stdc++.h>
#define lli long long int
using namespace std;
lli ip[10000001];
lli spf[10000001];

void sieve() 
{ 
	lli MAXN=10000001;
    spf[1] = 1; 
    for (lli i=2; i<MAXN; i++)  
        spf[i] = i; 

    for (lli i=4; i<MAXN; i+=2) 
        spf[i] = 2; 
  
    for (lli i=3; i*i<MAXN; i++) 
    {  
        if (spf[i] == i) 
        { 
            for (lli j=i*i; j<MAXN; j+=i)  
                if (spf[j]==j) 
                    spf[j] = i; 
        } 
    } 
} 
  
map<lli,lli> getFactorization(lli x) 
{ 
    map<lli,lli> ret; 
    while (x != 1) 
    { 
        ret[spf[x]]++; 
        x = x / spf[x]; 
    } 
    return ret; 
} 

int main()
{
	sieve();
	for(int i=1;i<=10000000;i++)
	{
		map<lli,lli> x=getFactorization(i);
		ip[i]=1;
		map<lli,lli> :: iterator it=x.begin();
		while(it!=x.end())
		{
			ip[i]*=(it->second+1);
			it++;
		}
	}
	ip[0]=0;
	for(int i=1;i<=10000000;i++)
	{
		ip[i]=ip[i-1]+ip[i]*i;
	}
	lli n;
	cin>>n;
	cout<<ip[n]<<endl;
}

Measured memory_bytes: 159884
/*
मनस्वी म्रियते कामं कार्पण्यं न तु गच्छति ।
अपि निर्वाणमायाति नानलो याति शीतताम् ॥
*/

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds;
using namespace std;

#define mod 1000000007
#define pb push_back
#define ll long long int
#define ull unsigned ll
#define ld long double
#define vi vector<int>
#define vl vector<ll>
#define v2i vector<vector<int>>
#define v2l vector<vector<ll>>
#define ppi pair<int,int>
#define ppl pair<ll,ll>
#define vpi vector<ppi>
#define vpl vector<ppl>
#define all(x) x.begin(),x.end()
#define ff first    
#define ss second
#define forn(i,a,b) for(int i=a;i<b;i++)
#define forr(i,a,b) for(int i=a;i>=b;i--)
#define forv(i,m) for(auto i : m)
#define p2d(v) for(auto a:v){for(auto b:a)cout<<b<<" ";cout<<endl;}
#define p1d(v) for(auto a:v)cout<<a<<" ";cout<<endl;
#define ppd(v) for(auto a:v)cout<<a.ff<<" "<<a.ss<<endl;
#define imx INT_MAX
#define imn INT_MIN
#define inf 9000000000000000000
#define minf -inf
#define endl "\n"
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define sze size()
#define rvs reverse 
#define itr iterator 
#define pre cout<<fixed<<setprecision(10);
#define umap unordered_map
#define uset unordered_set
#define pi 3.141592653589793
#define MAXN 100005
#define test1(x) cout << #x " = " << x << endl;
#define test2(x,y) cout << #x " = " << x << " " << #y " = " << y << endl;
#define test3(x,y,z) cout << #x " = " << x << " " << #y " = " << y << " " << #z " = " << z << endl;
#define test4(w,x,y,z) cout << #w " = " << w << " " << #x " = " << x << " " << #y " = " << y << " " << #z " = " << z << endl;
#define oset tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>

/*
const ll infinity = 9e18;

bool compare(ll a,ll b) {return a > b;}
bool compare1(ppl a,ppl b) {return a.ff > b.ff;}
bool compare2(ppl a,ppl b) {return a.ss < b.ss;}
bool isprime(ll n){if(n < 2) return 0; ll i = 2; while(i*i <= n){if(n%i == 0) return 0; i++;} return 1;}

ll Npower(ll a,ll b) {ll product = 1; while(b){if(b&1){product = product*a;}a = a*a;b = b>>1;} return product;}
ll power(ll a,ll b,ll md = mod) {ll product = 1; while(b){if(b&1){product = (product*a)%md;}a = (a*a)%md;b = b>>1;} return product%md;}
ll GCD(ll a,ll b) {return b==0 ? a:GCD(b,a%b);}
ll LCM(ll a,ll b) {return (a/GCD(a,b))*b; }
*/

bool isPossible(ll mid,vl &v,ll k)
{

    forn(i,0,v.sze)
    {
        k -= ((v[i]-1)/mid);

        if(k < 0) return 0;
    }

    return k >= 0;
}



int main()
{
    fast

/*
    #ifndef ONLINE_JUDGE
        freopen("input.txt",  "r",  stdin);
        freopen("output.txt", "w", stdout);
    #endif
//*/

        
    ll n,k;
    cin>>n>>k;

    vl v(n);
    ll sum = 0;
    forn(i,0,n)
    {
        cin>>v[i];
        sum += v[i];
    }

    ll st = 1, end = 1e15;
    ll ans = 0;
    while(st <= end)
    {
        ll mid = (st+end)/2;

        if(isPossible(mid,v,k))
        {
            ans = mid;
            end = mid-1;
        }
        else
        {
            st = mid+1;
        }
    }        
        

    cout<<ans;










    return 0;
}       

Measured memory_bytes: 4780
import java.util.Scanner;
import java.util.Set;

public class Main{
    public static void main(String[] args) {
        // Scanner sc = new Scanner("3 5\n.....\n.#.#.\n.....");
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] tmp = line.split(" ");
        int h = Integer.parseInt(tmp[0]);
        int w = Integer.parseInt(tmp[1]);
        char[][] grid = new char[h][w];
        for(int i=0;i<h;i++){
            grid[i] =  sc.nextLine().toCharArray();
        }
        
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(grid[i][j]=='#'){
                    System.out.print('#');
                }else{
                    int cnt = cntBomb(grid, i, j);
                    System.out.print(cnt);
                }
            }
            System.out.println();
        }
    }
    private static int cntBomb(char[][] grid, int i, int j){
        final int[] dx = new int[]{1, 1, 1, 0, 0, -1, -1, -1};
        final int[] dy = new int[]{1, 0, -1, 1, -1, 1, 0, -1};
        int cnt = 0;
        for(int idx=0;idx<8;idx++){
            int ni = i+dx[idx], nj=j+dy[idx];
            if(ni<0 || grid.length<=ni){continue;}
            if(nj<0 || grid[i].length<=nj){continue;}
            if(grid[ni][nj]=='#'){cnt++;}
        }
        return cnt;
    }
}

Measured memory_bytes: 22228
from heapq import heappush, heappop
from collections import deque
import re
import math
import functools

def sRaw():
    return input().rstrip("\r")

def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29


def make1d_arr(n, val=INF):
    return [val for i in range(n)]


def make2d_arr(h, w, val=INF):
    return [[val for i in range(w)]for i in range(h)]


def gcd(a, b):
    if(b == 0):
        return a
    return gcd(b, a % b)


def BFord(n,es):
    v_cost = [INF]*n
    v_cost[0] = 0
    for v in range(n*2):
        for e in es:
            frm = e[0]
            to = e[1]
            if v_cost[to] > v_cost[frm]+e[2]:
                v_cost[to] = v_cost[frm]+e[2]
                if v >= n:
                    v_cost[to] = -INF
        if v == n-1:
            prev = v_cost[:]
    v_cost = [-INF if prev[idx]!=v_cost[idx] else v_cost[idx] for idx in range(n)]
    return v_cost
    
def ZAlgo(s):
    l = len(s)
    A = [0]*l
    i =1
    j =0
    A[0]=l
    while i<l:
        while i+j<l and s[j] == s[i+j]:
            j+=1
        if j==0:
            i+=1
            continue
        A[i]=j
        k=1
        while (i+k<l) and (k+A[k]<j):
            A[i+k] =A[k]
            k+=1
        i+=k
        j-=k
    return A


def main():
    N = iRaw()
    i = 1
    ans = N
    while i*i <= N:
        if N%i ==0:
            j = N//i
            ans = min(ans,i-1+j-1)
        i+=1
    return ans

if __name__ == "__main__":
    print(main())


Measured memory_bytes: 39024
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

long long POW(long long a,long long b,const long long m){
  long long ans=1;
 	for(long long i=0;i<b;i++){
    	ans=ans*a%m;
    }
  return ans;
}

int main(){
  long long n;
  const long long mod=1000000007;
  cin>>n;
  cout<<(((POW(10,n,mod)-POW(9,n,mod)-POW(9,n,mod)+POW(8,n,mod))%mod)+mod)%mod<<endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,a[N],d[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=n;i>=1;i--)
		d[a[i]]=d[a[i]+1]+1;
	int res=n;
	for(int i=0;i<=n;i++)
	{
		int ned=i+d[i+1];
		res=min(res,n-ned+i);
	}
	cout<<res<<'\n';
	return 0;
}


Measured memory_bytes: 1792
def orderN(N,L,ices):
    upPeak = L - ices[0]
    downPeak = L - ices[0]
    peaks = []
    for i in range(len(ices)):
        if i < N-1:
            if ices[i] < ices[i+1]:
                peaks.append(downPeak)
                downPeak = L - ices[i+1]
                upPeak += L - ices[i+1]
            else:
                peaks.append(upPeak)
                upPeak = L - ices[i+1]
                downPeak += L - ices[i+1]
        else:
            peaks.append(upPeak)
            peaks.append(downPeak)
    print(max(peaks))

N,L = map(int,input().strip().split())
ices = []
while True:
    ice = int(input().strip())
    ices.append(ice)
    if len(ices) == N:
        break

orderN(N,L,ices)

Measured memory_bytes: 15544
#include<stdio.h>
#include<math.h>

int main(void)
{
    long long int a,b,n;
    scanf("%lld",&n);
    for(a=sqrt(n);a>0;a--){
        if(n%a==0){
            b=n/a;
            break;
        }
    }
    printf("%lld",a+b-2);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
typedef long long ll;
const ll inf = 1e9;
int main(){
    int q; cin >> q;
    set<ll> st;
    rep(i,q){
        ll com, x;
        cin >> com >> x;
        if(com == 0){
            st.insert(x);
            cout << st.size() << endl;
        }else cout << ((st.find(x) != st.end())?1:0) << endl;
    }
    return 0;
}


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

public class Main{
    public static void main(String[] args)throws Exception{
        Scanner sc=new Scanner(System.in);
        String n=sc.next();
        if(n.indexOf("7")>=0){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 35696
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 11;
int n, m;
int tong[N], du[N];
int head[N], to[N<<1], nex[N<<1], size = 1;
bool vis[N<<1], flag, ins[N];
void add(int x, int y){
	to[++size] = y;
	nex[size] = head[x];
	head[x] = size;
	du[y]++;
}
void dfs(int u, int st, int fl){
	if(u != st && du[u] == 4)fl = 1;
	for(int i = head[u];i;i = nex[i]){
		if(vis[i])continue;
		vis[i] = vis[i^1] = 1;
		int v = to[i];
		if(v == st && fl == 0)flag = 1; 
		if(v != st)dfs(v, st, fl);
	}
}
int main(){
	cin>>n>>m;
	int u, v;
	for(int i = 1;i <= m; i++){
		scanf("%d%d", &u, &v);
		add(u, v); add(v, u);
	}
	int ma = 0;
	for(int i = 1;i <= n; i++){
		tong[du[i]]++;
		ma = max(ma, du[i]);
		if(du[i] & 1){
			puts("No");
			return 0;
		}
	}
	if(ma >= 6){
		puts("Yes");
		return 0;
	}
	if(tong[4] >= 3){
		puts("Yes");
		return 0;
	}
	if(tong[4] == 1){
		puts("No");
		return 0;
	}
	if(tong[4] == 2){
		for(int i = 1;i <= n; i++){
			if(du[i] == 4){
				dfs(i, i, 0);
			}
		}
		puts(flag ? "Yes" : "No");
		return 0;
	}
	puts("No");
	return 0;
}

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

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

int main()
{
    long long x;
    cin >> x;
    cout << 1000 * (x / 500) + 5 * ((x % 500) / 5) << endl;
    // cout << 1000 * (x / 500) << " " << 5 * ((x % 500) / 5) << endl;
    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i32 = int32_t;
using i64 = int64_t;
constexpr char newl = '\n';

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
//#define F first
//#define S second
#define debug(x) cout << #x << ": " << x << '\n';

#if 1


// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N, K;
  cin >> N >> K;

  constexpr i8 Win = 1, Lose = -1;
  vector<i8> dp(K + 1, 0);

  vector<int> a(N);
  F0R(i, N) {
    cin >> a[i];
    if (a[i] < dp.size()) {
      dp[a[i]] = Win;
    }
  }
  auto amin = a.front();
  auto amax = a.back();

  // [0, amin) 手詰まり
  F0R(i, min(amin, K + 1)) {
    dp[i] = Lose;
  }

  FOR(i, amin, K + 1) {
    if (dp[i] != 0) continue;

    // Lose に行けるなら Win
    for (auto e : a) {
      if (i >= e && dp[i - e] == Lose) {
        dp[i] = Win;
        break;
      }
    }
    if (dp[i] != 0) continue;

    // Lose に行けないなら多分 Lose
    dp[i] = Lose;
  }

  cout << (dp[K] == Win ? "First" : "Second");
}
#endif


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    if(n==1 && k==1)
    {
        cout<<"YES"<<endl;
        return 0;
    }
    if(n%2==0 && n>k)
    {
        int val (n/2);
        if(val>=k)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    else if(n%2!=0 && n>k)
    {
        int val = (n/2) + 1;
        if(val>=k)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    else
        cout<<"NO"<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <complex>
#include <map>
#include <cstring>

using namespace std;

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

typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

int M;

// A*B
mat mulm(mat &A,mat &B){
  mat C(A.size(),vec(B[0].size()));
  for(int i = 0; i < A.size(); i++){
    for(int k = 0; k < B.size(); k++){
      for(int j = 0; j < B[0].size(); j++){
	C[i][j]=(C[i][j]+A[i][k]*B[k][j])%M;
      }
    }
  }
  return C;
}

// A^NÌvZ
mat pow(mat A,ll n){
  mat B(A.size(),vec(A.size()));
  for(int i = 0; i < A.size(); i++)
    B[i][i]=1;
  while(n>0){
    if(n&1)
      B=mulm(B,A);
    A=mulm(A,A);
    n>>=1;
  }
  return B;
}

int main(){
  ll n,l;
  int b=0;
  while(cin>>n>>M>>l&&!(n==0&&M==0&&l==0)){
    b++;
    map<pair<int,int> ,int> mis;
    pair<int,int> points[1000];
    ll initVal[1000];
    memset(initVal,0,sizeof(initVal));
    int idx=0;
    int bound=n;
    pair<int,int> prvPoint;
    for(int i = 0; i < 2*n-1; i++){
      pair<int,int> cPoint=prvPoint;
      if(i>n-1){
	cPoint.first+=dy[3];
	cPoint.second+=dx[3];
      }
      else{
	cPoint.first+=dy[4];
	cPoint.second+=dx[4];
      }
      prvPoint=cPoint;
      for(int j = 0; j < bound; j++){
	cin>>initVal[idx];
	points[idx]=cPoint;
	mis[cPoint]=idx++;
	cPoint.first+=dy[2];
	cPoint.second+=dx[2];
      }
      bound++;
      if(i>=n-1)
	bound-=2;
    }
    // for(int i = 0; i < idx; i++)
    //   cout<<points[i].first<<" "<<points[i].second<<" ";
    // sñðìé
    mat A(idx,vec(idx));
    // ÎpüãÉÍ1ðüêÄ¨­
    for(int i = 0; i < idx; i++){
      for(int j = 0; j < idx; j++){
	if(i==j)
	  A[i][j]=1;
	else
	  A[i][j]=0;
      }
    }
    //  éidxÌÀWðæ¾µA»ÌÀWÉJÚµÄ­évfðT·
    for(int i = 0; i < idx; i++){
      pair<int,int> p=points[i];
      // ÀWª¶Ý·é©Ç¤©ðTõµA¶Ý·êÎ,Y·ésñÌÓÉ1
      for(int j = 0; j < 6; j++){
	pair<int,int> np=points[i];
	np.first+=dy[j];
	np.second+=dx[j];
	// ¶Ý
	if(mis.find(np)!=mis.end()){
	  int id=mis[np];
	  A[i][id]=A[id][i]=1;
	}
      }
    }
    // sñÌlæðvZ
    A=pow(A,l);
    //   for(int j = 0; j < idx; j++){
    // 	cout<<A[i][j]<<" ";
    //   }
    //   cout<<endl;
    // }
    ll sum=0;
    //  ÆÍaðÆé¾¯
    for(int i = 0; i < idx; i++){
      ll tmp=0;
      for(int j = 0; j < idx; j++)
	tmp+=(A[i][j]*initVal[j])%M;
      sum+=tmp%M;
    }
    cout<<"Case "<<b<<": "<<sum<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include<iostream>
using namespace std;
int main () {
    int a,b,c;
    cin>>a>>b>>c;
    if(a-b==0){
        cout<<c<<endl;
    }else if(a-c==0){
        cout<<b<<endl;
    }else{
        cout<<a<<endl;
    }
    return 0;
}


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

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

typedef long long ll;
const ll MOD = 1e9 + 7;
const int MAX_N = 100000;

int main() {
  int N;
  ll A[MAX_N + 1], B[MAX_N];
  std::cin >> N;
  rep(i, N + 1) std::cin >> A[i];
  rep(i, N) std::cin >> B[i];

  ll ans = 0;
  rep(i, N) {
    if(A[i] >= B[i]) {
      ans += B[i];
    } else {
      ans += A[i];
      B[i] -= A[i];
      if(A[i + 1] >= B[i]) {
        ans += B[i];
        A[i + 1] -= B[i];
      } else {
        ans += A[i + 1];
        A[i + 1] = 0;
      }
    }
  }

  std::cout << ans << '\n';
}


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

#define LL long long
#define RG register

using namespace std;
template<class T> T gi() {
	T x = 0; bool f = 0; char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = 1, c = getchar();
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f ? -x : x;
}
char str[20]; 
int cnt[50][50];
int main() {
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	int n = gi<int>(), c = 0; LL ans = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%s", str);
		int len = strlen(str), p = len - 1; 
		for (int i = 0; i < len; i++)
			if (str[i] == '.')
				p = i;
		LL a = 0;
		for (int i = 0; i < len; i++)
			if (str[i] != '.')
				a = a * 10 + str[i] - '0';
		for (int j = 1; j <= 10 - len + p; j++)
			a = a * 10;
		int c1 = 0, c2 = 0;
		while (a % 2 == 0) a /= 2, c1++;
		while (a % 5 == 0) a /= 5, c2++;
		cnt[c1][c2]++;
		if (c1 >= 9 && c2 >= 9) c++;
	}
	for (int i = 0; i < 50; i++)
		for (int j = 0; j < 50; j++)
			for (int k = 0; k < 50; k++)
				for (int l = 0; l < 50; l++)
					if (min(i + k, j + l) >= 18)
						ans += 1ll * cnt[i][j] * cnt[k][l];				
	printf("%lld\n", (ans - c) / 2);
	return 0;
}


Measured memory_bytes: 3756
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    one = il()
    two = il()

    ret = 0
    for n in range(N):
        tmp = sum(one[:n + 1])
        tmp += sum(two[n:])
        ret = max(ret, tmp)
    print(ret)


if __name__ == '__main__':
    main()


Measured memory_bytes: 10232
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define REP(i, start, end) for (ll i = start, i##Len = (end); i < i##Len; ++i)
#define REPR(i, start, end) for (ll i = start, i##Len = (end); i > i##Len; --i)
using ll = long long;
using namespace std;

int main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);

    ll n, k;
    cin >> n >> k;
    vector<pair<ll, ll>> seg(k);
    REP(i, 0, k)
    {
        cin >> seg[i].first >> seg[i].second;
    }

    vector<ll> dp(n + 1);
    dp[1] = 1;
    dp[2] = -1;
    const ll mod = 998244353;
    REP(i, 1, n + 1)
    {
        dp[i] = (dp[i] + dp[i - 1]) % mod;
        for (auto [l, r] : seg)
        {
            if (i + l <= n)
                dp[i + l] = (dp[i + l] + dp[i]) % mod;
            if (i + r + 1 <= n)
                dp[i + r + 1] = (dp[i + r + 1] - dp[i] + mod) % mod;
        }
    }

    cout << dp[n] << endl;
}

Measured memory_bytes: 4780
import java.util.*;

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

		int a=scanner.nextInt();
		int b=scanner.nextInt();
//		System.out.println("a=" + a);
//		System.out.println("b=" + b);

		if(Math.abs(a-b)%2 == 1) System.out.println("IMPOSSIBLE");
		else {
			int sol=Math.abs(a-b) /2;
			System.out.println(Math.max(a, b) - sol);
		}

		scanner.close();
	}
}


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

iteral = 0
odd = 0
while True:
    for i in range(N):
        if A[i] % 2 != 0:
            odd += 1
        A[i] /= 2

    if odd != 0:
        break

    iteral += 1

print(iteral)


Measured memory_bytes: 2940
A, B, C, X, Y = map(int, input().split())

pay = 0

XY = min([X, Y])
X -= XY
Y -= XY

if (A+B) > C*2:
    pay += XY*C*2
else:
    pay += XY*A + XY*B

if A > C*2:
    pay += X*C*2
else:
    pay += X*A

if B > C*2:
    pay += Y*C*2
else:
    pay += Y*B

print(pay)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr double eps = 1e-9;
constexpr ll MOD = 1000000007LL;
template <typename T> bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
};
template <typename T> bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
};
template <typename T> ostream &operator<<(ostream &os, vector<T> v) {
    for (int i = 0; i < v.size(); i++) {
        os << v[i] << (i + 1 == v.size() ? "\n" : " ");
    }
    return os;
}
template <typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template <typename T, typename... Ts> auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T &t, const V &v) {
    t = v;
}
template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T &t, const V &v) {
    for (auto &e : t) {
        fill_v(e, v);
    }
};
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] *= -1LL;
    }
    vector<ll> dp(n + 1, INF);
    dp[0] = -INF;
    for (int i = 0; i < n; i++) {
        int id = upper_bound(all(dp), a[i]) - dp.begin();
        chmin(dp[id], a[i]);
    }
    for (int i = n; i >= 0; i--) {
        if (dp[i] != INF) {
            cout << i << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
typedef long long ll;
using namespace std;
int main() {
	int n;
	cin >> n;
	map<string, int> mp;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		sort(s.begin(), s.end());
		mp[s]++;
	}
	ll ans = 0;
	for (auto& p : mp) {
		int s = p.second;
		ans += (ll)s * (s - 1) / 2;
	}
	cout << ans << endl;
	return 0;
}

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

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

struct edge {
    int from, to, cost;
    edge(int f, int t, int c) :from(f), to(t), cost(c) {}
};

bitset<200001> ans;

int main() {
    int n, m;
    while (cin >> n >> m and n) {
        ans.reset();
        vector< pair<int, pair<int, int>> > p;
        rep(i, m) {
            int t, s, d;
            cin >> t >> s >> d;
            s--;
            d--;
            p.push_back(make_pair(t, make_pair(s, d)));
        }
        sort(p.begin(), p.end());
        vector<edge> g[20001];
        ans[0] = 1;
        rep(i, m) {
            pair<int, int> tmp = p[i].second;
            int to = tmp.first, from = tmp.second;
            if (ans[to]) ans[from] = 1;
        }
        cout << ans.count() << endl;
    }
    return 0;
}



Measured memory_bytes: 3952
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(int argc, char const *argv[])
{
	ll t1,t2,a1,a2,b1,b2;
	while(~scanf("%lld %lld %lld %lld %lld %lld",&t1,&t2,&a1,&a2,&b1,&b2)){
		ll cmp1 = (t1*(a1-b1));
		ll cmp2 = (t2*(a2-b2));

		if ((t1*a1+t2*a2)==(t1*b1+t2*b2))
		{
			printf("infinity\n");
			continue;
		}
		if ( (cmp1>0 && cmp2>0) || (cmp1<0 && cmp2<0) || cmp1==0 ||cmp2==0) 
		{
			printf("0\n");
			continue;
		}
		// printf("%lld %lld\n%lld %lld\n",(t1*a1+t2*a2),(t1*b1+t2*b2),cmp1,cmp2);
		if (cmp1<0)
		{
			ll abscmp1 = -cmp1;

			if (abscmp1>cmp2)
			{
				printf("0\n");
				continue;
			}
			
			if (abscmp1%(cmp1+cmp2))
			{
				printf("%lld\n",(abscmp1/(cmp1+cmp2))*2+1 );
			}
			else{
				printf("%lld\n",(abscmp1/(cmp1+cmp2))*2 );
			}
			
		}
		else{
			ll abscmp2 = -cmp2;

			if (cmp1 > abscmp2)
			{
				printf("0\n");
				continue;
			}

			if (cmp1% -(cmp1+cmp2))
			{
				printf("%lld\n",(cmp1/-(cmp1+cmp2))*2+1 );
			}
			else{
				printf("%lld\n",(cmp1/-(cmp1+cmp2))*2 );
			}

		}

	}
	return 0;
}

Measured memory_bytes: 256
from sys import stdin

input = stdin.readline

n = int(input())
A = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))

set_m = set([])

for i in range(2 ** n):
    tmp = 0
    for j in range(n):
        if (i >> j) & 1:
            tmp += A[j]

    set_m.add(tmp)

for i in m:
    if i in set_m:
        print("yes")
    else:
        print("no")



Measured memory_bytes: 5664
a,b,c,d = map(int,input().split())
chance = 0
while a>0 and c>0:
	if chance==0:
		c-=b
		chance=1
	else:
		a-=d
		chance=0
if a<=0 and c>0:
	print('No')
else:
	print('Yes')

Measured memory_bytes: 9200
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.regex : regex;
import std.container;
import std.bigint;


void main()
{
  int a, b;
  readf("%s %s\n", &a, &b);
  auto n = 1;
  int cnt;
  while (n < b) {
    n += a - 1;
    cnt++;
  }
  cnt.writeln;
}


Measured memory_bytes: 380
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()
#define all(v) (v).begin(), (v).end()


using namespace std;

typedef long long ll;

static const long long MOD = 1000000007;

int n;
vector<pair<int, int> > ans;
vector<int> v[105];

int main(void) {
    cin >> n;

    for (int i=1; i<=(n/2); i++) {
        v[i].pb(i);
        v[i].pb(n-i+1-(n%2));
    }

    for (int i=1; i<n/2; i++) {
        for (int x : v[i]) for (int y : v[i+1]) ans.pb(mp(x, y));
    }

    if (n%2==1) {
        for (int x : v[n/2]) ans.pb(mp(n, x));
        if (n!=3) for (int x : v[1]) ans.pb(mp(n, x));
    } else {
        if (n!=4) for (int x : v[n/2]) for (int y : v[1]) ans.pb(mp(x, y));
    }

    cout << (int)ans.size() << endl;

    for (pair<int, int> pr : ans) printf("%d %d\n", pr.first, pr.second);

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define MIN(a,b) ((a) <= (b) ? (a) : (b))
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort( ALL(v) )
#include <math.h>
#define _USE_MATH_DEFINES
using namespace std;
using ll = long long;
using P = pair<int,int>;

double PI = atan(1)*4;

int main()
{
    int R ;
    cin>>R;
    R *= 2;

    cout << setprecision(6);
    cout << fixed;
    cout << (double)PI*(double)R<<endl;
    return 0;
}


Measured memory_bytes: 3788
#include <bits/stdc++.h>
#include <array>
using namespace std;
using ULL = unsigned long long;
using UL = unsigned;
using LL = long long;
#define rep(i, n) for(UL i = 0; i < (n); i++)

struct Problem {

	void Solve() {
		string s, t; cin >> s >> t;
		UL a, b; cin >> a >> b;
		string u; cin >> u;
		if (s == u) a--; else b--;
		cout << a << " " << b << endl;
	}


	Problem();
};
int main() {
	unique_ptr<Problem> p(new Problem());
	p->Solve();
	return 0;
}
Problem::Problem() {
	cout << fixed << setprecision(10);
}

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

int main()
{
	int a = 0, b = 0, c = 0;
	string s;
	cin >> s;
	for (int i = 0; i < 3; i++) {
		if (s[i] == 'a') {
			a++;
		}
		else if (s[i] == 'b') {
			b++;
		}
		else {
			c++;
		}
	}
	if (a == 1 && b == 1 && c == 1) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}
	return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"math"
	"sort"
)

func main() {
	var n int
	fmt.Scan(&n)

	arr := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&arr[i])
	}

	sort.Ints(arr)

	ans := 0
	for i := 0; i < n; i++ {
		if i%2 == 0 {
			ans += arr[i]
		} else {
			ans -= arr[i]
		}
	}

	fmt.Println(math.Abs(float64(ans)))
}


Measured memory_bytes: 512
N = int(input())

cnum = 25
dnum = 14

res = 0

for i in range(cnum):
    for j in range(dnum):
        amm = 4 * i + 7 * j
        if amm == N:
            res += 1

if res > 0:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 2940
import sys
from bisect import bisect_left as bi_l

n, t, *a = map(int, sys.stdin.read().split())

def main():
  cand = []
  mi = a[0]
  for x in a[1:]:
    cand.append(x - mi)
    mi = min(mi, x)
  cand.sort() 
  ans = n - bi_l(cand, cand[-1]) - 1
  print(ans)
  
if __name__ == '__main__':
  main()

Measured memory_bytes: 14052
//#define _GLIBCXX_DEBUG
#include <iostream>
#include <bits/stdc++.h>


using namespace std;
#define ll long long
#define ld long double
#define  P pair<ll,ll>
#define FOR(i,n,m) for(ll i=n; i<(ll)m;i++)
#define FORr(i,m,n) for(ll i=n; i>=(ll)m; i--)
#define FORm(i,m) for(auto i=m.begin();i!=m.end();i++)
#define sortAl(v) sort(v.begin(),v.end())
#define sortAlr(v) sort(v.begin(),v.end()); reverse(v.begin(),v.end())
#define cout(n) cout<<fixed<<setprecision(n)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,k;
    cin>>n>>k;
    vector<ll> v(n);
    FOR(i,0,n)cin>>v[i];
    ll one = 0;
    ll ans = 0;
    FOR(i,0,n){
      FOR(j,i,n){
        if(v[i]>v[j])ans++;
      }
    }

    FOR(i,0,n){
      FOR(j,0,n){
        if(v[i]>v[j])one++;
      }
    }

    ll MOD = 1e9+7;

    cout<<(ans*k+k*(k-1)/2%MOD*one%MOD)%MOD<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
//#define TASK "file"

#define F first
#define S second
#define ALL(x) (x).begin(), (x).end()

using namespace std;
typedef long long i64;
typedef long double dbl;
const dbl PI = acos(-1.0L);
const dbl EPS = 1e-12L;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

namespace task {
i64 n, m;

int main() {
  cin >> n >> m;
  if (min(n, m) == 1) {
    cout << 1 << '\n';
  } else {
    cout << (n * m + 1) / 2 << '\n';
  }
  return 0;
}
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(11);
  cout.setf(ios::fixed);
#ifdef _DEBUG
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#elif defined(TASK)
  freopen(TASK".in", "r", stdin);
  freopen(TASK".out", "w", stdout);
#endif
  return task::main();
}


Measured memory_bytes: 256