akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
const long double PI =(acos(-1));

int main(){
    //int H=1,W=1;
    vector<int> H;
    vector<int> W;
    int n=1;
    int cnt=0;
    while(n){
        int h,w;
        cin >> h >> w;
        H.push_back(h);
        W.push_back(w);
        ++cnt;
        if(h==0 && w==0){
            n=0;
        }

    }
    int i=0;
    while(H.at(i)!=0 && W.at(i)!=0){
        for(int j=0;j<H.at(i);++j){
            for(int k=0;k<W.at(i);++k){
                if(j%2==0){
                    if(k%2==0){
                        cout << '#';
                    }else{
                        cout << '.';
                    }
                }else{
                    if(k%2==0){
                        cout << '.';
                    }else{
                        cout << '#';
                    }
                }
            }cout << endl;
        }cout << endl;
        ++i;
    }
    return 0;
}


Measured memory_bytes: 3104
import sys
input = sys.stdin.readline
A, B, K = map(int, input().split())
for i in range(K):
  if i % 2:
    B -= B % 2
    A += B // 2
    B //= 2
  else:
    A -= A % 2
    B += A // 2
    A //= 2
print(A, B)

Measured memory_bytes: 38256
unittest
{
	assert( [ "abaababaab" ].parse.expand.solve == 6 );
	assert( [ "xxxx" ].parse.expand.solve == 2 );
	assert( [ "abcabcabcabc" ].parse.expand.solve == 6 );
	assert( [ "akasakaakasakasakaakas" ].parse.expand.solve == 14 );
}



import std.conv;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto s = input.front.strip;
	return tuple( s );
}

auto solve( string s )
{
	for( auto i = ( s.length - 1 ) - ( s.length - 1 ) % 2; 2 <= i; i -= 2 )
	{
		auto t = s[ 0 .. i ];
		if( t[ 0 .. $ / 2 ] == t[ $ / 2 .. $ ] ) return t.length;
	}
	
	assert( false );
}


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

int main(){
  int n,d;
  cin >> n >> d;
  if(n % (2*d+1) == 0){
    cout << n / (2*d+1) << endl;
  }
  else{
    cout << (n / (2*d+1)) + 1 << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;

//定数
//円周率
const double pi = 3.141592653589793238462643383279;
//天井
const int INF = 1000000000; // = 10^9
const ll LINF = 100000000000000000; // = 10^17
//ABC文字列
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZABC";
const string abc = "abcdefghijklmnopqrstuvwxyzabc";
//よくあるmodくん
const ll MOD = 1000000007; // = 10^9 + 7
//前処理テーブルの大きさ指定
const int MAX = 1200000; // = 10^6 + 2*(10^5)
//ちなみに、1024MBで持てる最大長の配列は10^8程度

//データ構造
//隣接リスト用構造体（有向グラフ向け）
struct edge {
  ll to; // E.toでその辺の終点へアクセスできる。
  ll cost; // e.costでその辺の重みにアクセスできる。
};
//Union_Find木
struct UnionFind {
  vector<int> UF; // UF.at(i) : iの親の番号
  vector<int> SIZE; // SIZE.at(root(i)) : iと連結されてる要素の数
  UnionFind(int N) : UF(N), SIZE(N, 1) { // 最初は全てが根であるとして初期化
    for(int i = 0; i < N; i++) {
      UF.at(i) = i;
    }
  }
  int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
    if (UF.at(x) == x) {
      return x;
    }
    return UF.at(x) = root(UF.at(x));
  }
  void unite(int x, int y) { // xとyの木を併合
    int rx = root(x); // xの根をrx
    int ry = root(y); // yの根をry
    if (rx == ry) {
      return; // xとyの根が同じ(=同じ木にある)時はそのまま
    }
    // xとyの根が同じでない(=同じ木にない)時：小さい方の根を大きい方の根につける。
    if (SIZE.at(rx) < SIZE.at(ry)) {
      UF.at(rx) = ry;
      SIZE.at(ry) += SIZE.at(rx);
      SIZE.at(rx) = 0;
    }
    else {
      UF.at(ry) = rx;
      SIZE.at(rx) += SIZE.at(ry);
      SIZE.at(ry) = 0;
    }
  }
  bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す。
    int rx = root(x);
    int ry = root(y);
    return rx == ry;
  }
  int size(int x) { // xと連結されてる要素の数を返す。
    return SIZE.at(root(x));
  }
};

//関数 (計算量)
//ctoi (O(1))
int ctoi(char c){
  if (c == '0') return 0;
  if (c == '1') return 1;
  if (c == '2') return 2;
  if (c == '3') return 3;
  if (c == '4') return 4;
  if (c == '5') return 5; 
  if (c == '6') return 6;
  if (c == '7') return 7;
  if (c == '8') return 8;
  if (c == '9') return 9;
  return -1;  
}
//to_char (O(1))
char to_char(int i){
  if (i == 0) return '0';
  if (i == 1) return '1';
  if (i == 2) return '2';
  if (i == 3) return '3';
  if (i == 4) return '4';
  if (i == 5) return '5';
  if (i == 6) return '6';
  if (i == 7) return '7';
  if (i == 8) return '8'; 
  if (i == 9) return '9';
  return ' ';  
}

// A^N mod M を計算する。modしたくなかったらM = LINFとかにすればよい。(O(√N))
ll modpow(ll A, ll N, ll M) {
  ll ans = 1;
  while (N > 0) {
    if (N & 1) ans = ans * A % M;
      A = A * A % M;
      N >>= 1;
   }
  return ans;
}

//メイン処理
int main() {
  cout << fixed << setprecision(16); //精度向上
  //ここまでテンプレ
  ll N, K;
  cin >> N >> K;
  ll ans = 0;
  for (int i = 1; i <= N; i++) {
    int j = K - (i % K);
    if ((2 * j) % K == 0 && j <= N) {
      ans += ((N - j) / K + 1) * ((N - j) / K + 1);
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3620
N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
ans = A[0]

if A[0] == 0:
    print(0)

else:
    for i in range(1, N):
        ans = ans * A[i]
        if ans > 1E+18:
            ans = -1
            break
        else:
            continue
    print(ans)


Measured memory_bytes: 21456
from collections import deque
num = deque()
n = int(input())
for i in range(n):
    com = input().split()
    if com[0] == "deleteFirst":
        num.popleft()
    elif com[0] == "deleteLast":
        num.pop()
    elif com[0] == "insert":
        num.insert(0, com[1])
    elif com[0] == "delete":
        if num.count(com[1]):
            num.remove(com[1])
print(" ".join(num))


Measured memory_bytes: 69732
N = int(input())
dic = {} 
for i in range(N):
  num = int(input())
  if dic.get(num) is None:
    dic[num] = 1
  else:
    dic[num] += 1
ans = 0
for k in dic:
  if dic[k] %2 != 0:
    ans += 1
print(ans)

Measured memory_bytes: 15068
#include<stdio.h>
 
int d[100];
int f[100];
int n;
int graph[100][100]={0};
 
int time=1;
 
int dood(int node){
    d[node]=time++;
    int i,j;
    for(i=0;i<n;i++){
        if(graph[node][i]==1 && d[i]==0){
            dood(i);
        }
    }
    f[node]=time++;
}
 
int main(void){
    int u, k, v;
    int i, j;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d %d",&u,&k);
        for(j=0;j<k;j++){
            scanf("%d",&v);
            graph[u-1][v-1]=1;
        }
    }
    dood(0);
    for(i=0;i<n;i++){
        if(d[i]==0){
            dood(i);
        }
    }
    for(i=0;i<n;i++){
        printf("%d %d %d\n",i+1,d[i],f[i]);
    }
    return 0;
}

Measured memory_bytes: 632
from math import gcd

n = int(input())
alst = list(map(int, input().split()))
l_gcd = []
r_gcd = []

tmp = alst[0]
for num in alst[:-1]:
    tmp = gcd(tmp, num)
    l_gcd.append(tmp)
    
tmp = alst[-1]
for num in alst[1:][::-1]:
    tmp = gcd(tmp, num)
    r_gcd.append(tmp)
    
ans = max(r_gcd[-1], l_gcd[-1])
for r, l in zip(r_gcd[:-1], l_gcd[:-1][::-1]):
    tmp = gcd(r, l)
    ans = max(ans, tmp)
print(ans)


Measured memory_bytes: 23032
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn yn(result: bool) {
    if result {
        println!("Yes");
    } else {
        println!("No");
    }
}

fn main() {
    let v = read_vec::<u32>();
    let a = v[0];
    let b = v[1];

    if b % a == 0 {
        println!("{}", a+b);
    } else {
        println!("{}", b-a);
    }
}


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

int main() {
   
  string S;
  
  cin >> S;
  
  if(S.at(2) == S.at(3) && S.at(4) == S.at(5)){
  cout << "Yes" <<endl;
  }
  
  else{
  cout << "No" << endl;
  }
    return 0;
}

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

#define ll long long
#define ar array
 
using namespace std;

int main() {

    int a, b, t, res, i = 0;
    
    cin >> a >> b >> t;
	
	cout << (t/a)*b << endl;
	
    return 0;
}

Measured memory_bytes: 256
import numpy as np

def calculate(arr,n,k):
    max = 0

    maxSum = min(n,k)
    # A+B的和

    for i in range(0,maxSum+1):

        for l in range(0,i+1):
            larr = arr[:l]
            if i-l == 0:
                rarr = np.array([])
            else:
                rarr = arr[-(i-l):]

            ab = np.concatenate([larr,rarr])

            abs = np.sort(ab,axis=0)

            # 扔东西
            # k - i

            thawMax = (k-i)

            for th in range(thawMax+1):
                abs[:th] = 0
                tmpSum = np.sum(abs,axis=0)

                if tmpSum > max:
                    max = tmpSum


    return int(max)



S = input().split(" ")
N = int(S[0])
K = int(S[1])

arr = [int(s) for s in input().split(" ")]
arr = np.array(arr)

result = calculate(arr,N,K)

print(result)

Measured memory_bytes: 12480
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,m;
  cin >> n >> m;
  vector<int> v(m,0);
  for(int i=0;i<n;i++){
    int k;
    cin >> k;
    for(int j=0;j<k;j++){
      int l;
      cin>>l;
      l--;
      v[l]++;
    }
  }
  int ans = 0;
 
  for(int i=0;i<m;i++){
    if(v[i] == n) ans++;
  }
  cout << ans << endl;
}


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

int main() {
  int n;
  cin>>n;
  long long int s[n];
  for(int i=0;i<n;i++)
    cin>>s[i];
  int con=0,ans=1;
  for(int i=1;i<n;i++){
    if(con==0){
      if(s[i-1]>s[i])
        con=-1;
      else if(s[i-1]<s[i])
        con=1;
    }
    else if(con==1){
      if(s[i-1]>s[i]){
        ans++;
        con=0;
      }
    }
    else if(con==-1)
      if(s[i-1]<s[i]){
        ans++;
        con=0;
      }
  }
  
  cout<<ans;
    
  
}

Measured memory_bytes: 1024
#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <stack>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;
const int MOD = (int)1e9 + 7;
const ll INF = (ll)1e18 + 7;
#define int long long
#define vint vector<int>
#define pint pair<int, int>
#define pb(a) push_back(a)
#define all(v) v.begin(), v.end()
#define dbg(x) cerr << #x << " = " << (x) << endl
#define yn(b) cout << ((b) ? "Yes" : "No") << endl
#define YN(b) cout << ((b) ? "YES" : "NO") << endl

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

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

	int N;
	int ans;
	cin >> N;

	vint d(N);
	for (int i = 0; i < N; i++) {
		cin >> d[i];
	}

	sort(all(d));

	if (d[N / 2 - 1] == d[N / 2]) {
		ans = 0;
	} else {
		ans = d[N / 2] - d[N / 2 - 1];
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1152
import sys
import socket

hostnames = ['N551J', 'F551C', 'X553M']
input_file = 'c1.in'
if socket.gethostname() in hostnames:
    sys.stdin = open(input_file)


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


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


def read_str():
    return input()


def solve():
    inf = 10 ** 20
    n = read_int()
    x = read_int_list()
    res = inf
    for p in range(1, 101):
        s = 0
        for i in range(n):
            s += (p - x[i]) ** 2
        if res > s:
            res = s
    return res


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3700
import sys
from collections import deque
input = sys.stdin.readline

N, Q = [int(x) for x in input().strip().split()]
res = [0 for _ in range(N)]
tree = [[] for _ in range(N)]
for n in range(N-1):
    a, b = [int(x) for x in input().strip().split()]
    tree[a-1].append(b)

for q in range(Q):
    p, x = [int(x) for x in input().strip().split()]
    res[p-1] += x

q = deque([1])
cq = deque([0])
while q:
    n = q.popleft()
    c = cq.popleft()
    res[n-1] += c
    if len(tree[n-1])!=0:
        for num in tree[n-1]:
            q.append(num)
            cq.append(res[n-1])

print(*res)

Measured memory_bytes: 48224
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
static const int N = 1000;
 
int lcs(string X, string Y) {
    int c[N + 1][N + 1];
    int m = X.size();
    int n = Y.size();
    int maxl = 0;
    X = " " + X;
    Y = " " + Y;
    for(int i = 0; i <= m; i++) c[i][0] = 0;
    for(int j = 0; j <= n; j++) c[0][j] = 0;
     
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            if(X[i] == Y[j]) {
            c[i][j] = c[i - 1][j - 1] + 1;
        } else {
            c[i][j] = max(c[i - 1][j], c[i][j - 1]);
        }
        maxl = max(maxl, c[i][j]);
        }
    }
     
    return maxl;
}  
 
int main() {
    string s1, s2;
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> s1 >> s2;
        cout << lcs(s1, s2) << endl;  
    }
     
    return 0;
}

Measured memory_bytes: 7072
#include <iostream>
#include <string>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)
#define all(c) (c).begin(), (c).end()
#define mp(a, b) make_pair(a, b)

int main(){
    for(int N; cin >> N, N; cout << "#\n"){
        typedef tuple<string, int, int> Data;
        vector<Data> crops;
        rep(i, N){
            string L;
            int P, A, B, C, D, E, F, S, M;
            cin >> L >> P >> A >> B >> C >> D >> E >> F >> S >> M;
            crops.emplace_back(L, A + B + C + (D + E) * M, F * S * M - P);
        }
        auto comp = [](const Data& a, const Data& b){
            return mp(get<2>(b) * get<1>(a), get<0>(a)) < mp(get<2>(a) * get<1>(b), get<0>(b));
        };
        sort(all(crops), comp);
        for(auto& x: crops)cout << get<0>(x) << '\n';
    }
    return 0;
}

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

int main(){
    int n,x;
    cin >> n >> x;

    int i,j,k;
    
    while(1){
        int count=0;
        if(n==0&&x==0){
            break;
        }
    
        else {
            for (i=1;i<n+1;i++){
                for (j=1;j<n+1;j++){
                    for (k=1;k<n+1;k++){
                        if (i+j+k==x){
                            if (i!=j||j!=k||k!=i){
                                if (k>j&&j>i){
                                    count +=1;
                                }
   
                            }
                        }
                    }
                }
            }    
        }
        cin >> n >> x;
        cout << count << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3080
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define m1(x) memset(x,-1,sizeof(x))
const int INF = 1001001001;
const ll MOD = 1e9 + 7;
const double PI = 3.14159265358979;

int main(){
  int n;
  cin >> n;
  vector<P> testimony[15];
  for(int i = 0; i < n; i++){
    int a;
    cin >> a;
    for(int j = 0; j < a; j++){
      int x, y;
      cin >> x >> y;
      x--;y;
      testimony[i].push_back(P(x, y));
    }
  }
  int ans = 0;
  for(int i = 0; i < 1 << n ; i++){
    bool flag = true;
    bitset<15> s(i);
    for(int j = 0; j < n; j++){
      if(s.test(j)){
        for(P p : testimony[j]){
          if(p.second && !s.test(p.first)) flag = false;
          if(!p.second && s.test(p.first)) flag = false;
        }
      }
    }
    if(flag){
      int tmp = s.count();
      ans  = max(ans, tmp);
    }
  }
  cout << ans <<endl;
}

Measured memory_bytes: 256
import numpy as np

s = [ord(a)-ord('a') for a in input()]
n = len(s)

if n == 2:
    if s[0] == s[1]:
        print('1 2')
    else:
        print('-1 -1')
    exit()

cnt = np.array([0] * 26)
cum = [cnt.copy()]

for i, a in enumerate(s):
    cnt[a] += 1
    cum.append(cnt.copy())

def is_check(cum, n):
    i = 3
    d = 1
    for j in range(n-i+1):
        cum_ = cum[j+i] - cum[j]
        if cum_[cum_>1]:
            return j+1, j+i
    return -1, -1

print(' '.join(map(str, is_check(cum, len(s)))))

Measured memory_bytes: 50356
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <deque>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define print(x) cout<<(x)<<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 INF10 1001001001 
#define INF5 100000
#define EPS 1e-10


int main() {
	vector<int>a(5);
	REP(i, 5)cin >> a[i];
	int cnt = 0;
	REP(i, 5)cnt += ((a[i] + 9) - (a[i] + 9) % 10);

	int minsv = 10;
	REP(i, 5) {
		if (a[i] % 10 == 0)continue;
		else if (a[i] % 10 < minsv)minsv = a[i] % 10;
	}
	cnt -= (10 - minsv);
	print(cnt);


	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;


int main(){
    for(int i=1;i<10;i++){
        for(int j=1;j<10;j++){
            printf("%dx%d=%d\n",i,j,i*j);
        }
    }
    return 0;
}

Measured memory_bytes: 1088
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
    long long n,x,ans=0,cnt=0,total=0;
    cin >> n >> x;
    vector<long long> vec(n);
    rep(i,n){
        cin >> vec.at(i);
        total+=vec.at(i);
    }
    if(total<x){
        cout << n-1 << endl;
        return 0;
    }
    sort(vec.begin(),vec.end());
    rep(i,n){
        cnt+=vec.at(i);
        if(cnt<=x)ans++;
        else break;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
N, A, B = [int(s) for s in input().split()]
r = 0;
def sumdig(n):
    r = 0;
    d = n % 10;
    r += d;
    n = (n - d) / 10;
    d = n % 10;
    r += d;
    n = (n - d) / 10;
    d = n % 10;
    r += d;
    n = (n - d) / 10;
    d = n % 10;
    r += d;
    n = (n - d) / 10;
    d = n % 10;
    r += d;
    n = (n - d) / 10;
    return r;
for n in range(1, N + 1):
    s = sumdig(n)
    if (s >= A and s <= B):
        r += n;
print(r)


Measured memory_bytes: 3064
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define REP(i, n) for(i=0; i<n; i++)
#define REPR(i, n) for(i=n; i>=0; i--)
#define FOR(i, m, n) for(i=m; i<n; i++)
#define max(a, b) ((a)>(b) ? (a):(b))
#define min(a, b) ((a)<(b) ? (a):(b))
#define INF 10000000000
#define MOD 1000000007LL
#define MAX 100005
#define NIL -1
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> doup;

ll modpow(ll x, ll n) {
    ll res=1;
    while(n>0) {
        if(n&1) res=res*x%MOD;
        x=x*x%MOD;
        n>>=1;
    }
    return res;
}

int main(void) {
    ll N, H;
    P p[MAX];
    ll i, ans=0;
    vector<ll> v;
    cin >> N >> H;
    for(i=0; i<N; i++) {
        cin >> p[i].first >> p[i].second;
    }
    sort(p, p+N);
    
    for(i=0; i<N; i++) {
        if(p[N-1].first<=p[i].second) {
            v.push_back(p[i].second);
        }
    }
    sort(v.begin(), v.end());
    
    for(i=(ll)v.size()-1; i>=0; i--) {
        H-=v[i]; ans++;
        if(H<=0) {
            cout << ans << endl;
            return 0;
        }
    }
    ans+=H/p[N-1].first;
    ans+=(H%p[N-1].first==0 ? 0 : 1);
    cout << ans << endl;
}


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

int main()
{
    int n;
    cin >> n;
    int hmax = 0;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int h;
        cin >> h;
        if (hmax <= h) {
            ans++;
        }
        hmax = max(hmax, h);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define _USE_MATH_DEFINES
#include <math.h>
#define rep(i,n) for(int i = 0;i < n;i++)
#define NIL = -1;
#define all(x) x.begin(),x.end()
const ll INF = 1e9;
const ll mod = 1e9 + 7;
 
int digit(ll x) {
    if (x / 10 == 0) return 1;
    return digit(x / 10) + 1;
}
 
ll gcd(long long a,long long b) {
    if (a < b) swap(a,b);
    if (b == 0) return a;
    
    return gcd(b,a%b);
}

bool is_prime(long long N){
    if (N == 1) return false;
    for (long long i = 2;i * i <= N;i++){
        if (N % i == 0) return false;
    }
    return true;
}
 
ll lcm(ll a,ll b){
    return ((a * b == 0)) ? 0 : (a / gcd(a,b) * b);
}
 
double DegreeToRadian(double degree){
    return degree * M_PI / 180.0;
}
 
 
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
 
 
///////////////////////////////////////////////////////////////////////////////////

int main(){
    long long n, k;
    cin >> n >> k;
    long long ans = 0;
    for (long long i = k;i <= n+1;i++){
        long long mini = i*(i-1)/2;
        long long maxi = i*(n+(n-i+1))/2;
        ans += maxi - mini + 1;
    }
    ans = ans % mod;
    long long out = ans % mod;

    cout << ans << endl;
}

Measured memory_bytes: 3656
#include "bits/stdc++.h"
using namespace std;

int main(int argc, char **argv) {
  int i;
  int N;
  vector<int> d;
  cin >> N;
  for (int i = 0; i < N; i++) {
    int x;
    cin >> x;
    d.push_back(x);
  }

  int Sum = 0;
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      Sum += d[i] * d[j];
    }
  }
  cout << Sum << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    int n,i=1;
    cin>>n;
    do{
        int x=i;
        if(x%3==0)cout<<" "<<i;
        else {
            while(x){
                if(x%10==3){
                    cout<<" "<<i;
                    break;
                }
                x/=10;
            }
        }
    }while(++i<=n);
    cout<<endl;
    return 0;
}


Measured memory_bytes: 3092
import Control.Applicative
import Control.Monad

judge :: Int -> Int -> Int -> Int
judge n a b = b * (ceiling $ (fromIntegral n) / (fromIntegral a))

main = do
  (n:a:b:c:d:_) <- (map (read :: String -> Int) . words) <$> getLine
  print $ min (judge n a b) (judge n c d)



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

int main()
{
	int l, r, i, j, ans;
	cin >> l >> r;
	ans=2019*2019;
	if(r-l>=2018)
	{
		for(i=0; i<2018; i+=1)
		{
			for(j=i+1; j<=2018; j+=1)
				ans=min(ans, ((i*j)%2019));
		}
	}
	else
	{
		for(i=l; i<r; i+=1)
		{
			for(j=l+1; j<=r; j+=1)
				ans=min(ans, ((i%2019)*(j%2019))%2019);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#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;}

struct QuickFind{
  int n;
  vector<int> r,p;
  vector<vector<int> > v;
  QuickFind(){}
  QuickFind(int sz):n(sz),r(sz),p(sz),v(sz){
    for(int i=0;i<n;i++){
      r[i]=1,p[i]=i;
      v[i].resize(1,i);
    }
  }
  bool same(int x,int y){
    return p[x]==p[y];
  }
  void unite(int x,int y){
    x=p[x];y=p[y];
    if(x==y) return;
    if(r[x]<r[y]) swap(x,y);
    r[x]+=r[y];
    for(int i=0;i<(int)v[y].size();i++){
      p[v[y][i]]=x;
      v[x].push_back(v[y][i]);
    }
    v[y].clear();
  }
};

//INSERT ABOVE HERE
const int MAX = 114514;
int dp[MAX];
signed main(){
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++) cin>>a[i];
  
  memset(dp,0,sizeof(dp));
  for(int i=2;i<MAX;i++)
    if(!dp[i])
      for(int j=i;j<MAX;j+=i)
        if(!dp[j]) dp[j]=i;

  QuickFind qf(n+MAX);
  for(int i=0;i<n;i++){
    int k=a[i];
    while(dp[k]){
      qf.unite(i,n+dp[k]);
      k/=dp[k];
    }
  }
  
  vector<int> b(n);
  for(int i=0;i<n+MAX;i++){
    if(qf.p[i]!=i) continue;
    vector<int> v=qf.v[i];
    sort(v.begin(),v.end());
    vector<int> c;
    for(int x:v)
      if(x<n) c.emplace_back(a[x]);
    if(c.empty()) continue;
    sort(c.begin(),c.end());
    for(int i=0;i<(int)c.size();i++) b[v[i]]=c[i];
  }

  cout<<(is_sorted(b.begin(),b.end())?1:0)<<endl;
  return 0;
}



Measured memory_bytes: 18904
#include<iostream>

 using namespace std;

 int main(){
while(1){

 int a, mozi;
 cin >> a ;
    if(a==0)break;
 char wrong[a], right[a];
 for(int i=0; i < a; i++){
 cin >> wrong[i] >> right[i];
 }
 cin >> mozi;
 char mozire[mozi];
 for(int j=0; j < mozi; j++){
 cin >> mozire[j];
 for(int f=0; f < a; f++){
 if(mozire[j] == wrong[f]){
 mozire[j] = right[f];
 break;}}
 }
 for(int e = 0; e < mozi; e++)
 cout << mozire[e];
cout << endl;
}
 return 0;
 }

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

using namespace std;
using ll = long long;

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

    ll ans = 1, a = 0;
    int n;
    bool over = false, zero = false;

    cin >> n;

    for(int i = 0; i < n; ++i) {
        cin >> a;
        if(a == 0) {
            zero = true;
            break;
        }
        if(static_cast<__int128_t>(ans) * static_cast<__int128_t>(a) > static_cast<__int128_t>(1000000000000000000)) over = true;
        ans *= a;
    }

    if(zero) printf("0\n");
    else if(over) printf("-1\n");
    else printf("%lld\n", ans);

    return 0;
}

Measured memory_bytes: 3784
#include <cstdio>
int main(){
    int w,h,x,y,r;
    while(scanf("%d%d%d%d%d",&w,&h,&x,&y,&r)!=EOF){
        if(x+r<=w&&x-r>=0&&y+r<=h&&y-r>=0){
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }
    return 0;
}



Measured memory_bytes: 2684
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i++)
#define rep_d( i, n, m ) for(int i = ( n ) - 1; i >= ( m ); i--)
#define sort_asc( X ) sort(( X ).begin(), ( X ).end())
#define sort_desc( X ) sort(( X ).begin(), ( X ).end(), greater <>())

template <class T> bool chmax( T& a, T b );
template <class T> bool chmin( T& a, T b );
int* eratosthenes( int N );
bool bit_search( int pattern, int N );
template <class T> void cumulative_sum( T array, size_t N );

const ll INF = 1LL << 60;
const int k_mod = 1e9 + 7;

int main( void ){
	int N;
	cin >> N;
	vector<int> vec(N);
	rep(i,0,N) cin >> vec[i];
	sort_asc(vec);
	cout << vec[N/2] -  vec[N/2-1]  << endl;
}

int* eratosthenes( int N ){
	int* prime_array = new int[ N + 1 ];
	int lim = N;
	prime_array[ 0 ] = 0;
	prime_array[ 1 ] = 0;
	rep( i, 2, N + 1 ){
		prime_array[ i ] = 1;
	}
	rep( i, 2, lim ){
		if (prime_array[ i ] == 0)
			continue;
		lim = N / i;
		for(int j = i * 2; j < N + 1; j += i){
			prime_array[ j ] = 0;
		}
	}
	return prime_array;
}
template <class T> void cumulative_sum( T array, size_t N ) {
	rep( i, 1, N + 1 ){
		array[ i ] += array[ i - 1 ];
	}
}
template <class T> bool chmax( T& a, T b ) {
	if (a < b){
		a = b; return true;
	}
	return false;
}
template <class T> bool chmin( T& a, T b ) {
	if (a > b){
		a = b; return true;
	}
	return false;
}
bool bit_search( int pattern, int N ){
	int cnt = 0;
	rep( bit, 0, N ){
		if (pattern & ( 1 << bit )){
			cnt++;
		}
	}
	return true;
}


Measured memory_bytes: 768
#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>
 
 
using namespace std;
#define int long long int
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back

int N;
int d[100005];
int ans=0;
signed main(){
    scanf("%lld",&N);
    rep(i,N){scanf("%lld",&d[i]);}
    sort(d,d+N);
    ans=d[(N/2)]-d[(N/2)-1];
    printf("%lld\n",ans);
}


Measured memory_bytes: 896
#include "bits/stdc++.h"

using namespace std;
typedef long long int ll;
typedef pair<ll, ll > pi;  
typedef pair<pair<ll, ll >, ll > pii;  
vector<ll > vec;
vector<vector<ll > > vec2;
ll MOD = 1000000007;
ll INF = 1145141919454519;

ll mx = 0;
map<ll, vector<ll > > mp;
void solve(ll num, ll len = 0, ll posi = -1){
    for(ll i = 0; i < mp[num].size(); i++){
        //cout << num << " " << mp[num][i] << endl;
        if(posi >= mp[num][i]){
            continue;
        }

        solve(num + 1, len + 1, mp[num][i] );

    }
    mx = max(mx, len);
    return;
}

int main() {

    ll N = 0;
    cin >> N;
    //map<ll, vector<ll > > mp;
    for(ll i = 0; i < N; i++){
        ll t; cin >> t;
        vec.push_back(t);
        mp[t].push_back(i);
    }

    if(mp[1].empty()){
        cout << -1 << endl;
        return 0;
    }

    solve(1);

    cout << N - mx << endl;
}

Measured memory_bytes: 45552
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;



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

	int A, B;
	cin >> A >> B;

	int cnt = 1;
	int ans = 0;
	while (cnt < B) {
		cnt--;
		cnt += A;
		ans++;
	}
	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
 
int main(void) {
    
    int n,i;
    scanf("%d",&n);
    for (i=1; i<=n; i++){
        if (i%3==0) printf(" %d",i);
      else if(i%10==3)printf(" %d",i);
      else if(i/10%10==3)printf(" %d",i);
      else if(i/100%10==3)printf(" %d",i);
      else if(i/1000%10==3)printf(" %d",i);
        
        }
     
    printf("\n");
    return 0;
}

Measured memory_bytes: 600
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] stringArray = br.readLine().split("\\s");

        Deque<Integer> que = new ArrayDeque<>();
        int a = 0;
        int b = 0;
        for (int i = 0; i < stringArray.length; i++) {
            switch (stringArray[i]) {
            case "+":
                a = que.pollFirst();
                b = que.pollFirst();
                que.addFirst(b + a);
                break;
            case "-":
                a = que.pollFirst();
                b = que.pollFirst();
                que.addFirst(b - a);
                break;
            case "/":
                a = que.pollFirst();
                b = que.pollFirst();
                que.addFirst(b / a);
                break;
            case "*":
                a = que.pollFirst();
                b = que.pollFirst();
                que.addFirst(b * a);
                break;
            default:
                que.addFirst(Integer.parseInt(stringArray[i]));
            }
        }
        System.out.println(que.pop());
    }
}

Measured memory_bytes: 24476
#include <algorithm>
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;

int main(void) {
  int N, x;
  cin >> N >> x;
  vector<int> a(N);
  rep(i, N) cin >> a[i];
  sort(a.begin(), a.end());

  int answer = 0;
  while (answer < N && a[answer] <= x) {
    x -= a[answer];
    ++answer;
  }
  if (0 < x && answer == N) --answer;
  cout << answer << endl;
  return 0;
}

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

#define mp make_pair
#define ff first
#define ss second
#define pii pair <int,int>
#define pb push_back
#define debug(x)  cerr << #x << " = " << x << endl
using namespace std ;
typedef long long ll ;
char c[7][7] ;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int h=0,w=0,k=0,black=0 ;
	cin >> h >> w >> k;
	for(int i =1 ;i<= h ; i++){
		for(int j = 1 ; j<=w ; j++){
			cin >> c[i][j] ;
			if(c[i][j] == '#'){
				black++ ;
			}
		}
	}
	int ans=0 ;
	int x =0 , zart=0 ;
	vector <int> satr ,soton ;
	for(int mask=0 ; mask < (1<<(h+w)) ; mask++){
		for(int i =0 ; i<(h+w) ;i++){
			if(((1<<i) & mask)){
				if(i <= h-1){
					satr.pb((i+1)) ;
				}
				else{
					soton.pb((i-h+1)) ;
				}
			}
		}
		for(int i : satr ){
			for(int j : soton){
				if(c[i][j] == '#'){
					zart++ ;
				}
			}
		}
		for(int i : satr){
			for(int j=1 ; j <= w ; j++){
				if(c[i][j] == '#'){
					x++ ;
				}
			}
		}
		for(int j : soton){
			for(int i =1 ; i<= h ; i++){
				if(c[i][j] == '#'){
					x++ ;
				}
			}
		}
		if((x-zart) == (black-k)){
			ans++;
		}
		satr.clear() ;
		soton.clear() ;
		zart =0 ;
		x = 0 ;
	}
	cout << ans ;
	return 0 ;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
//#define INF (1LL<<31)-1
//#define MOD 998244353
#define MOD 1000000007

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

int main(){
    int k;
    cin>>k;
    ll ans=0;
    int a[4];
    a[3]=0;
    rep(i,0,3)a[i]=1;
    while(!a[3]){
        ans+=gcd(a[0],gcd(a[1],a[2]));
        for(int i=0;++a[i]==k+1;i++)a[i]=1;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3636
from itertools import combinations
original_vals = []
original_labels = []

while True:
    n, x = list(map(int, input().split()))
    if n+x == 0:
        break
    l = [ i for i in range(1,n+1)]
    original_vals.append(l)
    original_labels.append(x)

for i,row in enumerate(original_vals):
    cs = list(combinations(row, 3))
    count = 0
    for c in cs:
        if sum(c) == original_labels[i]:
            count += 1
    print(count)

Measured memory_bytes: 34156
#include <cstdio>
#include <cstring>

int main(){
    int N;
    scanf("%d\n",&N);
    char str[30],old[110];
    scanf("%s\n",str);
    int slen=strlen(str),ans=0;
    for(int i=0;i<N;i++){
        scanf("%s\n",old);
        int olen=strlen(old);
        for(int j=0;j<olen;j++){
            for(int d=1;d<olen;d++){
                bool is1=true;
                for(int k=0;k<slen;k++){
                    if(j+k*d>=olen || old[j+k*d]!=str[k]){
                        is1=false;
                        break;
                    }
                }
                if(is1){
                    ans++;
                    goto QUIT;
                }
            }
        }
QUIT:   ;
    }
    printf("%d\n",ans);
}

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

using namespace std;

long long inf=1000000007;

int main(){
	string s;
	cin>>s;
	map<char,bool> tes;
	tes['A']=true;
	tes['C']=true;
	tes['G']=true;
	tes['T']=true;

	long long ans=0;
	long long cnt=0;
	for(auto a:s){
		if(tes.count(a)) cnt++;
		else cnt=0;
		ans=max(ans,cnt);
	}

	cout<<ans<<endl;

	return 0;
}


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

int n;

void countingSort(int*, int*, int);  

int main() {
  int *a, *b;
  int i, max = 0;

  scanf("%d",&n);
  a = (int*)malloc(sizeof(int)*(n+1));
  b = (int*)malloc(sizeof(int)*(n+1));
  for(i = 1;i <= n;i++) { 
    scanf("%d",&a[i]);
    if(max < a[i])
      max = a[i];
  }
  countingSort(a, b, max);
  for(i = 1;i <= n;i++) { 
    printf("%d", b[i]);
    if(i != n) 
      printf(" "); 
  }
  printf("\n");

  free(a);
  free(b);
  return 0;
}

void countingSort(int* a,int* b, int k) {
  int i, j, c[k+1];
  for(i = 0;i <= k;i++) 
    c[i] = 0;
  
  for(j = 1;j <= n;j++)
    c[a[j]]++;

  for(i = 1;i <= k;i++)
    c[i] += c[i-1];

  for(j = n;j > 0;j--) {
    b[c[a[j]]] = a[j];
    c[a[j]]--;
  }  
}

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

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(a) max((a),-(a))
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repe(i,n) rep(i,(n)+1)
#define per(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define pere(i,n) rep(i,(n)+1)
#define all(x) (x).begin(),(x).end()
#define SP <<" "<<
#define RET return 0
#define MOD 1000000007
#define INF 1000000000000000000

typedef long long LL;
typedef long double LD;

int main(){
  string s;
  cin >> s;
  int d;
  cin >> d;
  int n=s.length();
  vector<LL> dp(d,0);
  int total=0;
  dp[0]=0;
  for(int i=0;i<n;i++){
    // cout << i << endl;
    vector<LL> ndp(d,0);
    for(int j=0;j<d;j++){
      for(int k=0;k<10;k++){
        ndp[(j+k)%d]=(ndp[(j+k)%d]+dp[j])%MOD;
      }
    }
    for(int j=0;j<s[i]-'0';j++){
      ndp[(total+j)%d]=(ndp[(total+j)%d]+1)%MOD;
    }
    total=(total+(int)(s[i]-'0'))%d;
    for(int j=0;j<d;j++){
      dp[j]=ndp[j];
      // cout << dp[j] << " ";
    }
    // cout << endl;
  }
  dp[total]=(dp[total]+1)%MOD;
  cout << (dp[0]-1+MOD)%MOD << endl;
  return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.Map.Entry;

public class Main {
	public static void main(String[] args) throws NumberFormatException,
			IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(
				System.in));
		StringBuilder builder = new StringBuilder();
		while (true) {
			String line = reader.readLine();
			if (line.equals("0 0")) {
				break;
			}
			StringTokenizer tokenizer = new StringTokenizer(line);
			int n = Integer.parseInt(tokenizer.nextToken());
			int s = Integer.parseInt(tokenizer.nextToken());

			Map<int[], Integer> memo = new HashMap<int[], Integer>();
			memo.put(new int[0], 0);
			int count = 0;
			for (int i = 0; i < 10; i++) {
				Map<int[], Integer> memotmp = new HashMap<int[], Integer>();
				memotmp.putAll(memo);

				for (Entry<int[], Integer> entry : memo.entrySet()) {
					if (entry.getKey().length == n || entry.getValue() + i > s) {
						continue;
					}
					int[] nearray = Arrays.copyOf(entry.getKey(),
							entry.getKey().length + 1);
					nearray[nearray.length - 1] = i;
					int sum = entry.getValue() + i;

					memotmp.put(nearray, sum);
					if (nearray.length == n && sum == s) {
						count++;
					}

				}
				memo = memotmp;
			}
			/*
			 * memo.entrySet().forEach( l ->
			 * System.out.println(Arrays.toString(l.getKey()) + " -> " +
			 * l.getValue()));
			 */
			System.out.println(count);
		}
	}
}

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

#define int long long
#define lson o<<1
#define rson o<<1|1
#define mid (l+r>>1)

int n,h[200005],a[200005];
int ans,f[200005];
struct segtree{
	int mx;
}dat[200005<<2];

void update(int o)
{
	dat[o].mx = max(dat[lson].mx,dat[rson].mx);
}

void modify(int o,int l,int r,int x,int v)
{
	if(l==x && r==x)
	{
		dat[o].mx = max(dat[o].mx,v);
		return;
	}
	if(x<=mid)
		modify(lson,l,mid,x,v);
	else
		modify(rson,mid+1,r,x,v);
	update(o);
}

int query(int o,int l,int r,int ql,int qr)
{
	if(l>=ql && r<=qr)
		return dat[o].mx;
	int res=0;
	if(ql<=mid)
		res = max(res,query(lson,l,mid,ql,qr));
	if(qr>mid)
		res = max(res,query(rson,mid+1,r,ql,qr));
	return res;
}

signed main()
{
	cin>>n;
	for(int i=1;i<=n;cin>>h[i++]);
	for(int i=1;i<=n;cin>>a[i++]);
	for(int i=1;i<=n;i++)
	{
		f[i]=query(1,1,n,1,h[i])+a[i];
		modify(1,1,n,h[i],f[i]);
	}
	for(int i=1;i<=n;i++)
		ans = max(ans,f[i]);
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 11136
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vl vaector<long>
#define vll vector<long long int>
#define vC  vector<char>
#define FastIO ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define db(...) ZZ(#__VA_ARGS__, __VA_ARGS__)
ll pow(ll x, ll y,ll m) { ll res = 1;x=x%m; while (y > 0) { if (y & 1) res = ((res%m) * (x%m))%m; y = y >> 1; x = ((x%m) * (x%m))%m; } return res%m; }
template <typename Arg1> void ZZ(const char* name, Arg1&& arg1){std::cerr << name << " = " << arg1 << endl;}
template <typename Arg1, typename... Args>void ZZ(const char* names, Arg1&& arg1, Args&&... args)
{
	const char* comma = strchr(names + 1, ',');
	std::cerr.write(names, comma - names) << " = " << arg1;
	ZZ(comma, args...);
}
const ll INF = 0xFFFFFFFFFFFFFFFL;
clock_t time_p=clock();
void abhigyan10()
{time_p=clock()-time_p;cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";}
ll seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline ll rnd(ll l=0,ll r=INF){return uniform_int_distribution<ll>(l,r)(rng);}
#define clrbuf cin.ignore(numeric_limits<streamsize>::max(),'\n');
#define preciset(x) cout<<setprecision(x)<<fixed;
const ll mod =1000000007;
int main()
{
        FastIO

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

        cout<< min(n%k, k- n%k );
        return 0;
    }

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) (v).begin(), (v).end()
//#define DEBUG
using namespace std;
typedef long long ll;


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

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

	int a = 1, b = n-1;
	int min = INF;

	while (a <= b){
		string sa, sb;
		sa = to_string(a);
		sb = to_string(b);

		int sum = 0;

		REP(i, (int)sa.size()){
			sum += sa[i] - '0';
		}

		REP(i, (int)sb.size()){
			sum += sb[i] - '0';
		}

		if (sum < min) min = sum;

#ifdef DEBUG
		cout << "sa = " << sa << endl;
		cout << "sb = " << sb << endl;
		cout << "a = " << a << endl;
		cout << "b = " << b << endl;
		cout << "sum = " << sum << endl;
		cout << "min = " << min << endl;
#endif //DEBUG

		a++; b--;
	}

	cout << min << endl;

}


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

using namespace std;

int main(int argc, const char *argv[]) {
  int n;
  cin >> n;
  map<int, int> cnts;
  vector<int> vd{0};
  for (int i = 0; i < n; ++i) {
    int d;
    cin >> d;
    cnts[d]++;
    vd.push_back(d);
  }

  cnts[0]++;

  int mx = 0;
  for (auto p : cnts) {
    mx = max(mx, p.second);
  }

  if (mx >= 3 || cnts[0] >= 2 || cnts[12] >= 2) {
    cout << 0 << '\n';
    return 0;
  }

  auto solve = [&](int bit) {
    vector<int> vd2;
    if (cnts[0] > 0) {
      vd2.push_back(0);
    }

    if (cnts[12] > 0) {
      vd2.push_back(12);
    }

    for (int i = 1; i <= 11; ++i) {
      if (cnts[i] <= 0) {
        continue;
      }

      if (cnts[i] >= 2) {
        vd2.push_back(i);
        vd2.push_back(24 - i);
        continue;
      }

      if (bit & (1 << i)) {
        vd2.push_back(24 - i);
      } else {
        vd2.push_back(i);
      }
    }

    int ans = 24;
    for (int i = 0; i < vd2.size() - 1; ++i) {
      for (int j = i + 1; j < vd2.size(); ++j) {
        int diff = abs(vd2[i] - vd2[j]);
        ans = min(ans, min(diff, 24 - diff));
      }
    }

    return ans;
  };

  int ans = 0;
  for (int i = 0; i < (1 << 12); ++i) {
    ans = max(ans, solve(i));
  }

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

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
// 型エイリアス
using pii = pair<int, int>;
using tisb = tuple<int, string, bool>;
using vi = vector<int>;
using vii = vector<vi>;

void print(vi A, int N){
  for(int i=0; i<N; ++i){
    if(i>0) cout << " ";
    cout << A[i];
  }
  cout << endl;
}

// 参照じゃないとうまくいかない。なんで参照？？？
int bubbleSort(vi &A, int N){
  int count=0;
  bool flag = 1;
  int i=0;

  while(flag){
    flag = 0;
    for(int j=N-1; j>i; --j){
      if(A[j]<A[j-1]){
        swap(A[j], A[j-1]);
        flag = 1;
        ++count;
      }
    }
    ++i;
  }

  return count;
}

int main(){
  int N; cin >> N;
  vi A(N);
  for(int i=0; i<N; ++i) cin >> A[i];

  int count = bubbleSort(A, N);
  print(A, N);
  cout << count << endl;
}


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

int main(){
  int n;
  string a;
  cin >> n;
  set<string> s;
  rep(i,n){
    cin >> a;
    s.insert(a);
  }
  cout << s.size() << endl;
  return 0;
}

Measured memory_bytes: 19208
#include <iostream>
using namespace std;
int main(void){
    int N;
    cin >> N;
    int m = 10;
    for (int i = 1; i < 10; i++)
        if (N % i == 0 && N / i < m)
            m = N / i;
    
    if (m == 10)
        cout << "No" << endl;
    else
        cout << "Yes" << endl;
}

Measured memory_bytes: 256
function Main(input) {
  var inputs = input.split(" ");
  var n = parseInt(inputs[0], 10);
  var y = parseInt(inputs[1], 10);
  var num = y / 1000;

  for(var i = 0; i <= n; i++) {
    for(var j = 0; j <= n; j++) {
      if(0 <= num - (10 * i + 5 * j) && num - (10 * i + 5 * j) === n - (i + j)) {
        console.log(i, j, n - (i + j));
        return;
      }
    }
  }
  console.log(-1, -1, -1);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7372
N = int(input())
xs = list(map(int, (input() for _ in range(N))))
ss = sorted(xs)
odd1 = set((x for i, x in enumerate(xs) if i % 2 == 1))
even2 = set((s for i, s in enumerate(ss) if i % 2 == 0))
print(len(odd1 & even2))

Measured memory_bytes: 14616
#include <stdio.h>
#define A 1000 

main(){
 int i,j,k,n,a[A];

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

 for(i=0;i<n;i++){
   j=i;
   while(j>0 && a[j]<a[j-1]){
     k=a[j-1];
     a[j-1]=a[j];
     a[j]=k;
     j--;
   }
  for(j=0;j<n;j++){
    printf("%d",a[j]);
    if(j!=n-1)printf(" ");
  }
  printf("\n");
 }
  return 0;
}

Measured memory_bytes: 608
//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<algorithm>
typedef long long LL;
using namespace std;
//#pragma comment(linker, "/STACK:102400000,102400000")

/*
题意：
对于每个 headline ，可以抠出一些字符然后重新组合成一个字符串。
要求找到一个最长的，字典序最小的字符串，能被所有的 headline 包含。
思路：
每次处理
*/
const int INF=0x3f3f3f3f;
int num[30],n;

void solve(char *str){
    int temp[30];
    int len=strlen(str);
    memset(temp,0,sizeof(temp));
    for(int i=0;i<len;i++)
        temp[str[i]-'a']++;
    for(int i=0;i<26;i++)
        num[i]=min(num[i],temp[i]);
}

int main(){
    char str[55];
    scanf("%d",&n);
    memset(num,INF,sizeof(num));
    for(int i=0;i<n;i++)
    {
        scanf("%s",str);
        solve(str);
    }
    string ans="";
    for(int i=0;i<26;i++){
        char x='a'+i;
        while(num[i]){
            ans.push_back(x);
            num[i]--;
        }
    }
    cout<<ans;
    return 0;
}



Measured memory_bytes: 256