akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10 , OO = 0x3f3f3f3f;

#define clr(arr,val) memset(arr , val , sizeof (arr))
#define loop(i,n) for(int i = 0;i < int(n);i++)
#define rloop(i,n) for(int i = int(n)-1;i >= 0;i--)
#define xloop(i,a,b) for(int i = int(a);i <= int(b);i++)
#define range(vec) for(auto &x : vec) cin >> x;
#define ALL(v) ((v).begin()) , ((v).end())
#define SZ(v)  ((int)((v).size()))
int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
//int dx[6]={2,1,-1,-2,-1,1};int dy[6]={0,1,1,0,-1,-1}; //Hexagonal Direction
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

int x , y;

int main()
{

    #ifndef ONLINE_JUDGE
        //freopen("in.in", "r", stdin);
        //freopen("out.in", "w", stdout);
    #endif
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);



    cin >> x >> y;
    xloop(i, 1, 10000) {
        if ((i * 8) / 100 == x && (i * 10) / 100 == y)
             return cout << i << "\n" ,  0;
    }
    cout << -1 << endl;



    return 0;
}


Measured memory_bytes: 256
H, W, M = (int(i) for i in input().split())

hw = set()
hh = [0] * H
ww = [0] * W

for i in range(M):
    ht , wt = (int(i) for i in input().split())
    hw.add((ht-1) * W + wt - 1)
    hh[ht-1] += 1
    ww[wt-1] += 1

hhh = max(hh)
ih = [i for i, x in enumerate(hh) if x == hhh]

www = max(ww)
iw = [i for i, x in enumerate(ww) if x == www]

minus = 1
for iih in ih:
    for iiw in iw:
        if iih * W + iiw not in hw:
            minus = 0
            break

print(hhh + www - minus)




Measured memory_bytes: 169948
#include <stdio.h>
int main(void){
   int N,K,i;
   char  S[50];
   scanf("%d %d",&N,&K);
   
   for(i=0;i<N;i++){
   scanf("%s",&S[i]);
   if(i==K-1)
   S[i]=S[i]+32;
   }
   
   for(i=0;i<N;i++)
   printf("%c",S[i]);
   return(0);
    
}


Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
#include <set>
#include <ctime>
#include <tuple>
#include <bitset>
using namespace std;

/*
sort(sp.begin(), sp.end(), [](PAIR l, PAIR r){
        return l.first<r.first || (l.first==r.first && l.second > r.second);
        });
*/

typedef long long  ll;

#define fi first
#define se second

using Graph = vector<vector<int>>;


int main() {
    int n;
    cin>>n;
    vector<int>a(n+1,0);
    if(n<=1){
        cout<<1<<endl;
        return 0;
    }
    a[0]=1;
    a[1]=1;
    for(int i=2;i<=n;i++){
        a[i]=a[i-1]+a[i-2];
    }
    cout<<a[n]<<endl;



    return 0;
}



Measured memory_bytes: 3132
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
using LL = long long;
const LL LINF = 1e18;
using namespace std;
#define COUT(v) cout<<(v)<<endl
#define CIN(n)  int(n);cin >> (n)
#define LCIN(n) LL(n);cin >> (n)
#define SCIN(n) string(n);cin >> (n)
#define YES(n) cout<<((n)? "YES" : "NO")<<endl
#define Yes(n) cout<<((n)? "Yes" : "No")<<endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) <<endl

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

#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(obj) (obj).begin(),(obj).end()

#define P pair<LL,LL>
#define I vector<int>
#define S set<int>
#define pb(v) push_back(v)
#define V vector
#define rt return
#define rmsame(a) sort(ALL(a)),a.erase(unique(ALL(a)), a.end())

typedef string::const_iterator State;
class PalseError {};
class Edge{
public:
    LL from,to,value;
    Edge(LL a,LL b,LL c){
        from = a;
        to = b;
        value = c;
    }
    Edge(LL a,LL b){
        from = a;
        to = b;
    }
};
//スタート点,頂点数、辺を渡して、最短経路の配列を返す

int main(){
    CIN(N);
    set<string> hoge;
    SCIN(s);
    string ins = s;
    bool result = true;
    hoge.insert(s);
    for(int a = 1;a < N;a++){
        SCIN(r);
        if(s.back() == r.front() && hoge.count(r) == 0){

        }else{
            result = false;
        }
        s = r;
        hoge.insert(s);
    }
    Yes(result);
    return 0;
}


Measured memory_bytes: 256
import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
import math
r = int(input())
p = math.pi
print(2*r*p)



Measured memory_bytes: 9180
from heapq import heappop, heappush
from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))

hp = []
for i, e in enumerate(a, 1):
    heappush(hp, [-e, i])

dp = defaultdict(int)
dp[(0, n + 1)] = 0
while hp:
    e, i = heappop(hp)
    e = -e
    dp2 = defaultdict(int)
    for k, v in dp.items():
        l, r = k
        dp2[(l + 1, r)] = max(dp2[(l + 1, r)], v + abs(l + 1 - i) * e)
        dp2[(l, r - 1)] = max(dp2[(l, r - 1)], v + abs(r - 1 - i) * e)

    dp = dp2

ans = 0
for k, v in dp.items():
    ans = max(ans, v)

print(ans)


Measured memory_bytes: 83452
/* nuttela - Soham Chakrabarti */

#include <bits/stdc++.h>
 
using namespace std;
 
#define io ios_base::sync_with_stdio(false);cin.tie(NULL)
#define all(v) v.begin(),v.end()
#define pb push_back
#define ins insert
#define rep(i,j,k) for(ll i=j;i<k;i++)
#define per(i,j,k) for(ll i=j;i>=k;--i)
#define scan(a,n) rep(i,0,n)cin>>a[i]
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define error freopen("error.txt","w",stderr)
#define ff first
#define ss second
 
typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
 
const int N = 1e6+1;
const int MAX = 1e6+1; 
const int inf = INT_MAX;
const int mod = 1e9+7;

ll powm(ll a,ll b) {ll res=1LL;while(b) {if(b&1)res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return res;}
ll modmult(ll a,ll b) {ll r=0;a%=mod;while(b){if(b&1)r=(r+a)%mod;a=(a<<1)%mod;b>>=1;}return r;}
ll modexpo(ll a,ll b) {ll r=1;a%=mod;while(b){if(b&1)r=(r*a)%mod;a=(a*a)%mod;b>>=1;}return r;}

ll a[N],b[N];

int32_t main() {
    io;
    ll n;cin>>n;
    if(n>=30)
        cout<<"Yes\n";
    else
        cout<<"No\n";
    return 0;
}


Measured memory_bytes: 3648
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author NikuKyabe
 */

#include <iostream>
#include <fstream>

#include "bits/stdc++.h"

using namespace std;
#define D double
#define int long long
#define FOR(i, a, b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i, n)  FOR(i,0,(n))


class CMinimization {
public:
    void solve(std::istream &in, std::ostream &out) {
      int n, k;
      in >> n >> k;
      vector<int> a(n);
      REP(i, n) in >> a[i];

      out << (int) (ceil((D) (n - 1) / (k - 1))) << endl;
    }
};


signed main() {
  ios::sync_with_stdio(false);
  cout.tie(0);
  cout << fixed;
  CMinimization solver;
  std::istream &in(std::cin);
  std::ostream &out(std::cout);
  solver.solve(in, out);
  return 0;
}


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

#define reps(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   reps(i,0,n)
#define all(x) (x).begin(),(x).end()
#define INF (1000000000)
#define MOD (1000000007)
#define PI (acos(-1))

struct edge { int to; ll cost; };

ll N,D[100010];
vector<edge> tree[100010];

void bfs(int src){
  queue<int> Q;
  Q.push(src);

  rep(i,100010){//初期化
    D[i] = 1e18;
  }

  D[src] = 0;//スタート地点は距離0
  
  while(!Q.empty()){
    int cur = Q.front();
    Q.pop();
    rep(i,tree[cur].size()){
      edge e = tree[cur].at(i);
      if(D[e.to] > D[cur]+e.cost){
        D[e.to] = D[cur]+e.cost;
        Q.push(e.to);
      }
    }
  }
}

int main(){
  int N;
  cin >> N;
  for (int i=0; i<N-1; ++i) {
      int a, b, c;//from,to,costが与えられるとする
      cin >> a >> b >> c;
      a--;b--;
      tree[a].push_back(edge{b,c});
      tree[b].push_back(edge{a,c});
  }
  bfs(0);
  rep(i,N){
    if(D[i]%2==0)cout << 0 << endl;
    else cout << 1 << endl;
  }
}

Measured memory_bytes: 8704
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;
#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main(){
    let n = read_as_vec::<usize>()[0];
    let a = read_as_vec::<usize>().into_iter().map(|x| x-1).collect::<Vec<usize>>();

    let mut ans = 0;
    for i in 0..n{
        if i == a[a[i]]{
            ans += 1;
        }
    }

    println!("{}", ans/2);
}


Measured memory_bytes: 6396
a = int(input())
b = int(input())
c = int(input())
x = int(input())

cnt = 0
for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      cand = 500 * i + 100 * j + 50 * k
      if cand == x:
        cnt += 1
print(cnt)

Measured memory_bytes: 9184
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

// c++11
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>

#define mp make_pair
#define mt make_tuple
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

const int INF = 1 << 29;
const double EPS = 1e-9;
const ll MOD = 1000000007;

const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
const int MAX_N = 1000010;
ll N;
ll dp[MAX_N];
ll sum[MAX_N];
int main() {
  cin >> N;
  dp[1] = N;
  sum[1] = N;

  dp[2] = N * N % MOD;
  sum[2] = (sum[1] + dp[2]) % MOD;

  for (int i = 3; i <= N; i++){
    //1
    dp[i] = dp[i - 1];
    //A[i] >= 2 A[i - 1] >= 2
    dp[i] += (N - 1) * (N - 1) % MOD;
    //A[i] >= 2 A[i - 1] = 1
    dp[i] += (sum[i - 3] + (N - 1 - (i - 3))) % MOD;
    dp[i] %= MOD;
    sum[i] += (sum[i - 1] + dp[i]) % MOD;
  }

  cout << dp[N] << endl;
  return 0;
}


Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, number, bit, count;
  cin >> N;
  vector<int> button(N, 0);
  
  for (int i = 0; i < N; i++) {
    cin >> button.at(i);
  }

  count = 0;
  bit = 0;
  number = 1; // 次に押そうとしているボタンの番号名（光ったボタン）

  // ボタン i を探す

  for (int i = 0; i < N; i++) {
    count++; // ボタンを押したので押した数をカウント
    number = button.at(number - 1); // 押したことで光るボタン＝ボタンが指し示していた数字を格納
	if (number == 2) {
      bit = 1;
      break;
    }
  }
  
  if (bit == 1) {
    cout << count << endl; 
  }
  else {
    cout << -1 << endl;
  }
}

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

#define itn int
#define all(x) (x).begin(), (x).end()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())

using namespace std;

inline int nxt() {
	int x;
	scanf("%d", &x);
	return x;
}

int main() {
	string s;
	cin >> s;
	auto t = s;
	if (s.length() < 26) {
		char c = 'a';
		while (s.find(c) != string::npos) {
			++c;
		}
		cout << s << c << "\n";
		return 0;
	}
	if (next_permutation(all(s))) {
		int p = 0;
		while (s.substr(0, p) == t.substr(0, p)) {
			++p;
		}
		cout << s.substr(0, p) << "\n";
	} else if (s.length() == 26) {
		cout << "-1\n";
	}

	return 0;
}

Measured memory_bytes: 256
n = int(input())
a_b = [input() for i in range(n)]
min = 1000000001
max = -1
max_point = 0
for i in a_b:
    a, b = map(int, i.split(' '))
    if(min > a):
        min = a
    if(max < a):
        max = a
        max_point = b

num = 0
num += min
num += max - min
num += max_point

print(num)


Measured memory_bytes: 11040
def areadifference(h , w):
    ans = 0
    count1 = 10000000000
    count2 = 10000000000
    if h % 3 == 0 or w % 3 == 0:
        return ans

    for i in range(1 , h + 1):
        hcount = max( i * w , (((h - i)//2) * w) , ((-(-(h - i)//2)) * w)) - min( i * w , (((h - i)//2) * w) , ((-(-(h - i)//2)) * w))
        wcount = max( i * w , ((h - i) * (w//2)) , ((h - i) * (-(-w//2)))) - min( i * w , ((h - i) * (w//2)) , ((h - i) * (-(-w//2))))
        count1 = min(count1 , hcount , wcount)

    for i in range(1 , w + 1):
        hcount = max( i * h , (((w - i)//2) * h) , ((-(-(w - i)//2)) * h)) - min( i * h , (((w - i)//2) * h) , ((-(-(w - i)//2)) * h))
        wcount = max( i * h , ((w - i) * (h//2)) , ((w - i) * (-(-h//2)))) - min( i * h , ((w - i) * (h//2)) , ((w - i) * (-(-h//2))))
        count2 = min(count2 , hcount , wcount)

    ans = min(count1 , count2)

    return ans

def main():
    h , w = map(int , input().split())
    print(areadifference(h , w))

if __name__ == '__main__':
    main()


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

int main() {
  char op;
  int A, B;
  cin >> A >> op >> B;

  // ここにプログラムを追記
  if(op == '+') {
    cout << A+B << endl; 
  }
  else {
    cout << A-B << endl; 
  }
}

Measured memory_bytes: 3596
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
n = I()
a = LI()
b = [None for i in range(n)]
k = n//2
if n%2:
    for i in range(n):
        if i%2:
            b[k+(i+1)//2] = a[i]
        else:
            b[k-i//2] = a[i]
else:
    for i in range(n):
        if i%2:
            b[k-(i+1)//2] = a[i]
        else:
            b[k+i//2] = a[i]
print(*b)
"""

#D
n = I()
a = LI()
fact = [1 for i in range(n+2)]
for i in range(1,n+2):
    fact[i]*= fact[i-1]*i
    fact[i] %= mod
inv_fact = [1 for i in range(n+2)]
inv_fact[n+1] = pow(fact[n+1],mod-2,mod)
for i in range(1,n+1)[::-1]:
    inv_fact[i] = inv_fact[i+1]*(i+1)
    inv_fact[i] %= mod
count = [None for i in range(n+1)]
for i in range(n+1):
    if count[a[i]] != None:
        l = count[a[i]]
        r = n-i
        break
    count[a[i]] = i
for i in range(1,n+2):
    ans = fact[n+1]*inv_fact[i]*inv_fact[n+1-i]%mod
    if l+r >= i-1:
        ans -= fact[l+r]*inv_fact[i-1]*inv_fact[l+r-i+1]%mod
        ans %= mod
    print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T


Measured memory_bytes: 21148
import sys
from collections import defaultdict
import itertools
n = int(input())
dic = defaultdict(lambda : 0)
for _ in range(n):
    s = input()
    if s[0] in 'MARCH':
        dic[s[0]] += 1
if len(dic) <= 2:
    print(0)
    sys.exit()
if len(dic) == 3:
    ans = 1
    for val in dic.values():
        ans *= val
    print(ans)
    sys.exit()

ans = 0
for i, j, k in itertools.combinations(dic.keys(), 3):
    ans += dic[i] * dic[j] * dic[k]
print(ans)

Measured memory_bytes: 3316
n=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
ans=b[a[0]-1]
for i in range(1,n):
    ans+=b[a[i]-1]
    if a[i]==a[i-1]+1:
        ans+=c[a[i-1]-1]
print(ans)    

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
	using namespace std;
	int n;
	int sum = 0;
	vector<int> s;
	bool flag = true;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		sum += t;
		if (flag && t % 10 != 0) {
			flag = false;
		}
		s.push_back(t);
	}
	if (sum % 10 != 0) {
		cout << sum << endl;
		return 0;
	}
	if (flag) {
		cout << "0" << endl;
		return 0;
	}
	sort(s.begin(), s.end());

	for (auto e : s) {
		sum -= e;
		if (sum % 10 != 0) break;
		sum += e;
	}
	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 256
use proconio::input;

fn main() {
    input! {
        n: u32,
    }

    solve(n);
}

fn solve(n: u32) {
    for i in 1..10 {
        for j in 1..10 {
            if i * j == n {
                println!("Yes");
                return;
            }
        }
    }
    println!("No");
}


Measured memory_bytes: 2160
N, K = map(int, input().split())
X = list(map(int, input().split()))

ans = 3 * 10 ** 8
for i in range(N - K + 1):
  ans = min(ans, abs(X[i]) + abs(X[i] - X[i + K - 1]), abs(X[i + K - 1]) + abs(X[i] - X[i + K - 1]))
print(ans)
            

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

int main(){
  int A, B;
  cin >> A >> B;
  
  int C = A;
  int c_10000, c_1000, c_100, c_10, c_1;
  
  int n = 0;	//カウント
  
  while(C <= B){
    c_10000 = C/10000;
    c_1000  = C/1000 - c_10000*10;
    c_100   = C/100 - c_1000*10 - c_10000*100;
    c_10    = C/10 - c_100*10 - c_1000*100 - c_10000*1000;
    c_1     = C/1 - c_10*10 - c_100*100 - c_1000*1000 - c_10000*10000;
    
    if(c_10000 == c_1 && c_1000 == c_10){
      n++;
    }
    
    C++;
  }
  
  cout << n << endl;
  
}
  

Measured memory_bytes: 256
def DFS(N, copyedge):
    matrix = [[] for i in range(N)]
    for a, b in copyedge:
        matrix[a].append(b)
        matrix[b].append(a)
        
    check = [True]*N
    check[0] = False
    Que = [0]

    while len(Que) != 0:
        now = Que.pop()
        for i in matrix[now]:
            if check[i] == True:
                check[i] = False
                Que.append(i)
    if True not in check:
        return 0
    else:
        return 1
            
        

ans = 0
N, M = map(int, input().split())
edge = []

for i in range(M):
    edge.append([int(i) - 1 for i in input().split()])
    
for i in range(M):
    copyedge = edge[:i] + edge[i+1:] 
    ans += DFS(N, copyedge)
print(ans)

Measured memory_bytes: 3064
n = gets.to_i
a = n.times.map{gets.to_i}.sort


if n.even?
  u, v = a[0, a.size/2], a[a.size/2, a.size]
  puts (v.inject(0,&:+)*2 - v.min) - (u.inject(0,&:+)*2 - u.max)
else
  u1, v1 = a[0, a.size/2], a[a.size/2, a.size]
  u2, v2 = a[0, (a.size+1)/2], a[(a.size+1)/2, a.size]
  puts [
    (v1.inject(0,&:+)*2 - v1[0,2].inject(0,&:+)) - (u1.inject(0,&:+)*2),
    (v2.inject(0,&:+)*2) - (u2.inject(0,&:+)*2 - u2.reverse[0,2].inject(0,&:+))
  ].max
end


Measured memory_bytes: 4728
#include<stdio.h>
#define N 100000

int partition(int,int);

int A[N];

int main(){
  int n,i,q;

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

  q=partition(0,n-1);

  for(i=0;i<n;i++){
    if(i!=0){
      printf(" ");
    }
    if(i==q){
      printf("[");
    }
    printf("%d",A[i]);
    if(i==q){
      printf("]");
    }
  }
  printf("\n");
  return 0;
}



int partition(int p,int r){
  int i,x,j,tmp;
  x=A[r];
  i=p-1;
  for(j=p;j<r;j++){
    if(A[j]<=x){
      i=i+1;
      tmp=A[i];
      A[i]=A[j];
      A[j]=tmp;
    }
  }
  tmp=A[i+1];
  A[i+1]=A[r];
  A[r]=tmp;
  return i+1;
}
  



Measured memory_bytes: 2108
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.ByteString.Char8 as BS
import Data.Char (isSpace)
import Control.Monad
import Control.Monad.Primitive (PrimState)

main = do
  n <- readLn :: IO Int
  as <- VU.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  vm <- VUM.replicate (10^5+1) (0::Int) :: IO (VUM.MVector (PrimState IO) Int)
  forM_ [0..n-1] $ \i -> do
    let v = as VU.! i
    prev <- VUM.read vm v
    VUM.write vm v (prev+1)
  v <- VU.unsafeFreeze vm 
  print $ solve v (10^5)

solve :: VU.Vector Int -> Int -> Int
solve v n
  | n == 0 = current + front
  | n == VU.length v - 1 = max (prev + current) (solve v (n-1))  
  | otherwise = max (prev + current + front) (solve v (n-1))
    where
      prev = v VU.! (n-1)
      current = v VU.! n
      front = v VU.! (n+1)

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

using namespace std;

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

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;

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

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

int bitCount(long bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;  cin >> s;
    int ans;
    rep (i, s.size()) {
      if (s[i] == 'A') {
        int index = i;
        FOR (j, i, s.size()) {
            if (s[j] == 'Z') index = j;
        }
        ans = index - i + 1;
        break;
      }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 720
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

a,b = input().split()
a = int(a)
b = list(b)
c = ''
for i in range(4):
    if i != 1:
        c += b[i]
b = int(c)
# print(a,b)
# b = int(b*10000)
# print(b)
print(int((a*b)//100))


Measured memory_bytes: 10496
x,y = map(int,input().split())
a = [1,3,5,7,8,10,12]
b = [4,6,9,11]
c = [2]
if x in a:
    x = "A"
else:
    x = "B" if x in b else "C"
if y in a:
    y = "A"
else:
    y = "B" if y in b else "C"
if x == y:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
fun main(args: Array<String>) {
    val (N, K) = readLine()!!.split(" ").map { it.toLong() }

    var answer = 0L
    // a + b = k
    //println(answer)
    // Fix a + b
    // a % K をM固定すると
    //  b = K - m
    // c = K- m と決まる
    val num = LongArray(K.toInt(), { 0L })
    (1..N).forEach {
        num[it.mod(K).toInt()]++
    }


    (0 until K).forEach { a ->
        // a +b = K
        val b = (K - a).mod(K)
        // a +c = K
        val c = (K - a).mod(K)
        // check b + c
        if ((b + c).mod(K) == 0L) {
            answer += num[a.toInt()] * num[b.toInt()] * num[c.toInt()]
        }
    }
    println(answer)
}



Measured memory_bytes: 40248
using System;
using System.Linq;
using System.Numerics;
using System.Collections.Generic;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Diagnostics;
using System.Text.RegularExpressions;

namespace CsTest
{
    class Program
    {
        static void Main()
        {
            var Wab = AtCoder.ReadInt64Array();
            var W = Wab[0];
            var a = Wab[1];
            var b = Wab[2];

            long ret = a <= b ? MoveLength(W, a, b) : MoveLength(W, b, a);

            Console.WriteLine(ret);
        }

        static long MoveLength(long W, long s, long l)
        {
            if (s + W >= l) return 0;
            else return l - s - W;
        }
    }

    public class AtCoder
    {
        public static string[] ReadStringArray() => Console.ReadLine().Split(Array.Empty<char>(), StringSplitOptions.RemoveEmptyEntries);
        public static int[] ReadInt32Array() => ReadStringArray().Select(s => int.Parse(s)).ToArray();
        public static long[] ReadInt64Array() => ReadStringArray().Select(s => long.Parse(s)).ToArray();
    }
}

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

/* macros */
#define inf 1e9
#define int long long
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
#define vi vector<int>
#define vc vector<char>
#define vb vector<bool>
#define vt vector
#define pb push_back
#define fi first
#define se second
#define pi pair<int,int>
#define tc int t;cin>>t;while (t--){solve();}
#define gtc int t;cin>>t;int TC=1;while (t--) {cout << "Case #" << TC << ": " << solve() << "\n";TC++;}
#define gvtc int t;cin>>t;int TC=1;while (t--) {cout << "Case #" << TC << ": "; vsolve(); TC++;}
#define notc solve();
#define newline cout << "\n";
#define mod 1000000007
#define ret return 0;
#define sz(x) (int)x.size();
#define rep(i,a,b) for(int i=a;i<b;i++)
#define srt(x) sort(x.begin(), x.end())
#define rsrt(x) sort(x.rbegin(), x.rend())

void brute(int n, vi &nums) {
    int ans = 0;
    for (int i=0;i<n-1;i++) {
        for (int j=i+1;j<n;j++) {
            int subans = (nums[i]%mod * nums[j]%mod)%mod;
            ans = (ans%mod + subans%mod)%mod;
        }
    }
    cout << ans << "\n";
}

void solve() {
    int n;
    cin>>n;
    vi nums(n);
    rep (i,0,n) cin>>nums[i];
    
    //brute(n,nums);
    
    int ans = 0;
    vi dp(n+1);
    dp[1] = nums[0];
    for (int i=1;i<n;i++) {
        dp[i+1] = (nums[i]%mod + dp[i]%mod)%mod;
    }
    
    for (int i=1;i<n;i++) {
        int subans = (nums[i]%mod * dp[i]%mod)%mod;
        ans += subans;
        ans %= mod;
    }
    
    cout << ans << "\n";
}

int32_t main(){
    fastio
    notc
    ret
}


Measured memory_bytes: 6340
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;

typedef long long int llint;

int main(){
	int N;
	cin >> N;
	int A[N],B[N],C[N];
	for(int i=0;i<N;i++){
		cin >> A[i] >> B[i] >> C[i];
	}

	int dp[3][N+1];
	for(int i=0;i<N+1;i++){
		dp[0][i]=-1;
		dp[1][i]=-1;
		dp[2][i]=-1;
	}

	dp[0][0]=0;
	dp[1][0]=0;
	dp[2][0]=0;

	for(int i=1;i<N+1;i++){
		{
			int scoreA=dp[1][i-1]+A[i-1];
			int scoreB=dp[2][i-1]+A[i-1];
			if(scoreA>scoreB){
				dp[0][i]=scoreA;
			}else{
				dp[0][i]=scoreB;
			}
		}
		{
			int scoreA=dp[0][i-1]+B[i-1];
			int scoreB=dp[2][i-1]+B[i-1];
			if(scoreA>scoreB){
				dp[1][i]=scoreA;
			}else{
				dp[1][i]=scoreB;
			}
		}
		{
			int scoreA=dp[0][i-1]+C[i-1];
			int scoreB=dp[1][i-1]+C[i-1];
			if(scoreA>scoreB){
				dp[2][i]=scoreA;
			}else{
				dp[2][i]=scoreB;
			}
		}
	}

	vector<int> score={dp[0][N],dp[1][N],dp[2][N]};
	cout << *max_element(score.begin(),score.end()) << endl;
	return 0;
}


Measured memory_bytes: 2560
#include<iostream>
#include <cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
  int N; cin >> N;
  vector<pair<int, int>>ans;
  int tmp;
  if(N%2) tmp = N; else tmp = N+1;
  for(int i=1; i<=N; i++){
    for(int j=i+1; j<=N; j++){
      if(i+j!=tmp) ans.push_back({i, j});
    }
  }
  cout << ans.size() << endl;
  rep(i, ans.size()){
    cout << ans[i].first << " " << ans[i].second << endl;
  }
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define pb push_back
#define REP(i, n) for (signed long long i = 0; i < (n); i++)
#define MOD 998244353
#define INF 98765431219876543
#define bitcnt(a) (ll) __builtin_popcount((a))
#define lb(a, b) lower_bound((a).begin(), (a).end(), (b))
#define ub(a, b) upper_bound((a).begin(), (a).end(), (b))
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<string, string> PS;

vector<ll> g[214514];
vector<P> p;
ll vis[214514][3]; // 1-おとずれた 2-いまいってるとこ
ll n, m;
string s;

ll dfs(ll now, ll from, ll mae, ll kiten) {
  if (vis[now][from] == 1) {
    return 1;
  }
  // cout << now << " " << from << endl;
  if (from != 2 && (vis[now][2] == 2 || vis[now][1] == 2 || vis[now][0] == 2)) {
    // vis[now][from] = 3;
    // cout << now << " " << from << " " << mae << " " << kiten << endl;
    return 2;
  }
  if (vis[now][from] == 3) {
    return 2;
  }
  vis[now][from] = 2;
  bool b = 0, c = 0;
  for (auto &a : g[now]) {
    if (from == 2) {
      int res = dfs(a, s[now] - 'A', now, kiten);
      if (res == 2) {
        if (s[a] == 'A')
          b = 1;
        else
          c = 1;
      }
    } else if (from == 0 && s[a] == 'B') {
      int res = dfs(a, s[now] - 'A', now, kiten);
      if (res == 2) {
        vis[now][from] = 3;
        return 2;
      }
    } else if (from == 1 && s[a] == 'A') {
      int res = dfs(a, s[now] - 'A', now, kiten);
      if (res == 2) {
        vis[now][from] = 3;
        return 2;
      }
    }
  }
  vis[now][from] = 1;

  if (from == 2 && b == 1 && c == 1) {
    // cout << now << " aaa" << endl;
    return 2;
  }
  return 0;
}

int main() {

  cin >> n >> m >> s;

  REP(i, m) {
    ll a, b;
    cin >> a >> b;
    p.pb(P(a - 1, b - 1));
    g[a - 1].pb(b - 1);
    g[b - 1].pb(a - 1);
  }

  REP(i, n) {
    if (vis[i][2] == 0) {
      if (dfs(i, 2, 0, i) == 2) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }

  cout << "No" << endl;
}

Measured memory_bytes: 26224
import java.util.*;
public class Main{
	public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int m = 1;
      int k = sc.nextInt();
      int count = 0;
      while(m <= k && count < n){
      	m = m*2;
        count++;
      }
      while(count < n){
      	m = m+k;
        count++;
      }
      System.out.println(m);
    }
}


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

using namespace std;

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

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

	int x, y, a, b, c;
	cin >> x >> y >> a >> b >> c;

	vector<pli> v(a + b + c);
	rep(i, a){
		cin >> v[i].first;
		v[i].second = 0;
	}

	rep(i, b){
		cin >> v[i+a].first;
		v[i+a].second = 1;
	}

	rep(i, c){
		cin >> v[i+a+b].first;
		v[i+a+b].second = 2;
	}

	sort(v.begin(), v.end(), [](pli a, pli b){
		if(a.first != b.first) return a.first > b.first;
		return a.second < b.second;
	});

	int acnt = 0;
	int bcnt = 0;
	int cnt = 0;
	int p = -1;
	ll ans = 0;
	while(cnt < x + y){
		p++;
		if(v[p].second == 0){
			if(acnt == x) continue;
			ans += v[p].first;
			acnt++;
			cnt++;
		}else if(v[p].second == 1){
			if(bcnt == y) continue;
			ans += v[p].first;
			bcnt++;
			cnt++;
		}else{
			ans += v[p].first;
			cnt++;
		}
	}

	cout << ans << endl;
}


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

const double PI = acos(-1);

int main() {
    int a, b, h, m;
    cin >> a >> b >> h >> m;
    long double ans;
    long double w;
    w =  ((long double)h / 6.0 + (long double)m / 360.0 - (long double)m / 30.0) * PI;
    ans = (long double)(a*a + b*b) - (long double)(2 * a * b) * cosl(w);
    printf("%.20Lf\n", sqrt(ans));

    return 0;
}

Measured memory_bytes: 4100
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <sstream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define FOR(i, a, done) for (int i = (a); i < (done); ++i)
#define all(a) (a).begin(), (a).end()
#define F first
#define S second
#define x first
#define y second
#define pb push_back
#define pf push_front

namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

ll M = 1000000007;

int main()
{
    string s,t;
    cin>>s>>t;
    cout<<t<<s<<endl;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>

using namespace std;

int main()
{
    int a, b;
    char op;
    cin >> a >> op >> b;

    while (op != '?')
    {
        switch (op)
        {
        case '+':
            cout << a + b << endl;
            break;
        case '-':
            cout << a - b << endl;
            break;
        case '*':
            cout << a * b << endl;
            break;
        case '/':
            cout << a / b << endl;
            break;
        }
        cin >> a >> op >> b;
    }
}


Measured memory_bytes: 3112
## coding: UTF-8
from itertools import permutations, combinations,combinations_with_replacement,product


N_str = input()
L = (len(N_str)) #桁数
s = [] #各桁の数を格納
for i in range(L):
    s.append((N_str[i]))
#print(s)
#ビット演算、式を計算
a=list(product(['','+'],repeat=L-1))
#print(a)
answer = 0
for i in a:
    if(L == 1):
        tmp=s[0]    
    if(L == 2):
        tmp=s[0]+i[0]+s[1]
    if(L == 3):
        tmp=s[0]+i[0]+s[1]+i[1]+s[2]
    if(L == 4):
        tmp=s[0]+i[0]+s[1]+i[1]+s[2]+i[2]+s[3]
    if(L == 5):
        tmp=s[0]+i[0]+s[1]+i[1]+s[2]+i[2]+s[3]+i[3]+s[4]
    if(L == 6):
        tmp=s[0]+i[0]+s[1]+i[1]+s[2]+i[2]+s[3]+i[3]+s[4]+i[4]+s[5]   
    if(L == 7):
        tmp=s[0]+i[0]+s[1]+i[1]+s[2]+i[2]+s[3]+i[3]+s[4]+i[4]+s[5]+i[5]+s[6]       
    if(L == 8):
        tmp=s[0]+i[0]+s[1]+i[1]+s[2]+i[2]+s[3]+i[3]+s[4]+i[4]+s[5]+i[5]+s[6]+i[6]+s[7]
    if(L == 9):
        tmp=s[0]+i[0]+s[1]+i[1]+s[2]+i[2]+s[3]+i[3]+s[4]+i[4]+s[5]+i[5]+s[6]+i[6]+s[7]+i[7]+s[8]
    if(L == 10):
        tmp=s[0]+i[0]+s[1]+i[1]+s[2]+i[2]+s[3]+i[3]+s[4]+i[4]+s[5]+i[5]+s[6]+i[6]+s[7]+i[7]+s[8]+i[8]+s[9]





    answer += eval(tmp)
print(answer)



'''
answer = N #+を1個もいれない

sp = []
for i in range(L):
    if(i == 0):
        sp.append([0])
        sp.append([1])
        print(sp)
        print(len(sp))
    else:
        print(i)
        for j in range(len(sp)):
#未解決…
'''
'''
a=['a','b','C']
print(list(permutations(a)))
print(list(combinations(a,2)))
print(list(combinations_with_replacement(a,3)))
'''

'''
#ビット演算、式を計算
a=list(product(['','-'],repeat=3))
print(a)
s=['5', '5', '3', '4']
for i in a:
    ans=s[0]+i[0]+s[1]+i[1]+s[2]+i[2]+s[3]
    print(ans)

    if eval(ans)==21:
        print(ans+'=21')
        break
'''

Measured memory_bytes: 3192
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000000LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main() {
    int n; cin >> n;
    vector<int> L(n);
    int mx = -1, sum = 0;
    rep(i,n){
        cin >> L[i];
        chmax(mx, L[i]);
        sum += L[i];
    }
    if(mx < sum - mx) cout << "Yes" << ln;
    else cout << "No" << ln;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
#define N 500005
using namespace std;
map<int,int>mp;
int n,ans,a[N];
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),mp[a[i]]++;
	sort(a+1,a+n+1);
	for (int i=n;i;i--){
		if (!mp[a[i]]) continue;
		for (int j=1;j<=(1<<30);j*=2){
			if (!mp[a[i]]) break;
			int x=j-a[i];
			if (x<0) continue;
			if (mp[x]){
				if (x==a[i]){
					ans+=mp[a[i]]/2;
					mp[a[i]]%=2;
				}
				else {
					int t=min(mp[a[i]],mp[x]);
					ans+=t;mp[a[i]]-=t;mp[x]-=t;
				}
			}
			if (j==(1<<30)) break;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 29824
import numpy as np

N, K = map(int, input().split())
P = list(map(int, input().split()))

# N, K = 10, 4
# P = [17, 13, 13, 12, 15, 20, 10, 13, 17, 11]

exp = []
for i in range(N):
    exp.append((1 + P[i]) / 2)

cum_exp = np.cumsum(exp)

max = cum_exp[K-1]
for i in list(range(K, N)):
    val = cum_exp[i] - cum_exp[i - K]
    if val > max:
        max = val

print(max)


Measured memory_bytes: 37336
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main(void){
    //x1, y1, x2, y2 （実数）なので double 型を使う
    double x1,y1, x2, y2;
    cin >> x1 >> y1;
    cin >> x2 >> y2;
    double d = pow(x1-x2, 2) + pow(y1-y2, 2);
    cout << fixed << setprecision(5) << sqrt(d);
    cout << endl; 
}


Measured memory_bytes: 3252
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;

#define rep(i,n) for(int i=0; i<((int)n); i++)
#define REP(i,n) for(int i=0; i<=((int)n); i++)
#define srep(i,a,n) for(int i=a; i<((int)n); i++)
#define SREP(i,a,n) for(int i=a; i<=((int)n); i++)
#define rrep(i,n) for(int i=n-1; i>=0; i--)
#define RREP(i,n) for(int i=n; i>=0; i--)
#define INF 1000000000
const int mod = INF+7;

int binary(vector<int> array, int N, int k){
  int lb=-1;
  int ub=N;
  //arrayは降順。k未満で一番左を返す。
  while(ub-lb>1){
    int mid=(ub+lb)/2;
    if(k>array[mid]){
      ub=mid;
    }
    else{
      lb=mid;
    }
  }
  return ub;
}

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i,N){
    cin >> A[i];
  }

  vector<int> ans;
  ans.push_back(A[0]);
  int n=0;
  srep(i,1,N){
    if(A[i]<=ans[n]){
      ans.push_back(A[i]);
      n++;
    }
    else{
      //binary；A[i]未満で一番左を返す関数。（降順前提）
      int k=binary(ans, n+1, A[i]);
      ans[k]=A[i];
    }
  }

  printf("%d\n", n+1);
}


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

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

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> a(n);
  for(Int i=0;i<n;i++) cin>>a[i];
  vector<Int> s(n+1,0);
  for(Int i=0;i<n;i++) s[i+1]=s[i]+a[i];

  Int ans=s[n];
  //[0,i) || [i,n)
  Int x=1,y=3;
  vector<Int> v(4);
  for(Int i=2;i+2<=n;i++){
    while(s[i]-s[x]>s[x]) x++;
    chmax(y,i+1);
    while(s[n]-s[y]>s[y]-s[i]) y++;
    
    for(Int j=-2;j<=2;j++){
      for(Int k=-2;k<=2;k++){
	Int X=x+j,Y=y+k;
	if(0<X&&X<i&&i<Y&&Y<n){
	  v[0]=s[X]-0;
	  v[1]=s[i]-s[X];
	  v[2]=s[Y]-s[i];
	  v[3]=s[n]-s[Y];
	  sort(v.begin(),v.end());
	  chmin(ans,v[3]-v[0]);
	}
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define lli long long int
#define ulli unsigned long long int
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define pf pop_front()
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define loopl(i,a,b) for(lli i=a;i<b;i++) 
#define loop(i,a,b) for(int i=a;i<b;i++)
#define mod 1000000007
#define inf 7+1e18
#define lld long double
#define eps 0.000001
#define endl '\n'
using namespace std ;

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

/*seive
 int d[302]={0};
 int l=300;
  for(int i=2;i<l;i++)
		if(d[i]==0)
			for(int j=i;j<=l;j+=i)
				d[j]=d[j/i]+1;


  loop(i,1,301) cout<<i<<" "<<d[i]<<endl;
*/
bool vis[2005]={false};
int conn=0;
vector<int> v[2005];
void dfs(int q) 
{
	vis[q] = 1;
	
	for(int i=0;i<v[q].size() ;i++)
		if (!vis[v[q][i]])
			dfs(v[q][i]);
    
} 

/*lli power(lli x, lli y, lli p)
{
    lli res = 1;  
 
    x = x % p;  
    
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
 
        y = y>>1; 
		x = (x*x) % p;  
    }
    return res;
}*/
int main()
{
	////////////////////
	fastio;
	///////////////////
	lli n;
	cin>>n;
	lli a[n];
	loopl(i,0,n) cin>>a[i];
    lli ans=0;
    loopl(i,0,n) ans+=a[i]-1;
    
    cout<<ans<<endl;
}

Measured memory_bytes: 384
import sys
sys.setrecursionlimit(100001)
def input():
    return sys.stdin.readline()[:-1]

from collections import defaultdict
H, W, D = map(int, input().split())
dic = defaultdict()
for i in range(H):
    a = list(map(int, input().split()))
    for j in range(W):
        dic[a[j]] = [i, j]
dist = [0 for i in range(H*W+1)]
for i in range(1, D+1):
    for j in range(i, H*W-D+1, D):
        dist[j+D] = abs(dic[j][0] - dic[j+D][0]) + abs(dic[j][1] - dic[j+D][1])
for i in range(1, D+1):
    for j in range(i+D, H*W+1, D):
        dist[j] += dist[j-D]
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(dist[r] - dist[l])

Measured memory_bytes: 26048
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
 
import java.util.*;
import java.lang.*;
import java.io.*;

@SuppressWarnings("unchecked")
public class Main implements Runnable {

  static BufferedReader in;
  static PrintWriter out;
 
  public static void main(String[] args) {
      new Thread(null, new Main(), "whatever", 1<<29).start();
  }


  public int findDigitsInBase(long n, int base) 
  { 
      return (int)(Math.floor(Math.log(n)/Math.log(base)) + 1);  
  } 
 
  public void run() {
    in = new BufferedReader(new InputStreamReader(System.in));
    out = new PrintWriter(System.out, false);
 
    try
    {
      // in = new BufferedReader(new FileReader("class_treasurer.txt"));
      // out = new PrintWriter("output.txt");

      int t,x1,n,p,i;
      String str;
      String[] token;

      str=in.readLine().trim();
      token=str.split(" ");
      n=Integer.parseInt(token[0]);

      str=in.readLine().trim();
      token=str.split(" ");

      Integer[] a=new Integer[n];

      for(i=0;i<n;i++) {
        a[i]=Integer.parseInt(token[i]);
      }

      Arrays.sort(a);

      int min=Integer.MAX_VALUE;

      for(p=1;p<=100;p++) {
        int stamina=0;
        for(i=0;i<n;i++) {
          stamina+=(Math.abs(p-a[i])*Math.abs(p-a[i]));
        }
        min=Math.min(min, stamina);
      }

      out.println(min);


      out.flush();
      out.close();
    }
    catch(Exception e) {
      e.printStackTrace();
    }
  }
}


Measured memory_bytes: 23380
# ABC142E - Get Everything
import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    p = 1 << N
    dp = [float("inf")] * p
    dp[0] = 0
    for _ in range(M):
        a, _ = map(int, input().split())
        x = sum(1 << (int(i) - 1) for i in input().split())
        for y in range(p):
            if dp[x | y] > dp[y] + a:
                dp[x | y] = dp[y] + a
    ans = dp[-1] if dp[-1] != float("inf") else -1
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
int main() {
	int s;
	cin >> s;
	int i = 1;
	bool flg = true;
	vector<int> A;
	A.push_back(s);
	while (flg) {
		i++;
		if (s % 2 == 0) s /= 2;
		else s = s * 3 + 1;
		auto itr = find(A.begin(), A.end(),s);
		if (itr != A.end()) flg = false;
		A.push_back(s);
	}
	cout << i << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<math.h>
#include <stdlib.h>
#include<ctype.h>
int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}
int main() {

	int N,M;
	
	scanf("%d %d",&N,&M);
	
	int Homework[M];
	
	int days = 0;
	
	for(int i=0;i<M;i++){
		
		scanf("%d",&Homework[i]);
		
		days += Homework[i];
		
		if(days>N){
			printf("-1");
			return 0;
		}
		
	}
	printf("%d",N-days);
	
	
	return 0;
}

Measured memory_bytes: 1760
#include<stdio.h>
int max(int A, int B){
    int max = A+B;
    if(max < A-B){
        max = A-B;
    }
    if (max < A*B)
    {
        max = A*B;
    }
    
    return max;
}

int main(){
    int A,B;
    scanf("%d %d", &A, &B);

    printf("%d", max(A,B));
    
    return 0;
}

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

using namespace std;
using ll = long long;

int main(void) {
  string a, c;
  cin >> a >> c;
  int r, b;
  cin >> r >> b;
  string s;
  cin >> s;
  if (s == c) {
    cout << r << " " << b - 1 << endl;
    return 0;
  } else {
    cout << r - 1 << " " << b << endl;
    return 0;
  }
}



Measured memory_bytes: 256