akhauriyash/Code-Regression huggingface dataset:
def strange_bank(N: int) -> int:
    prices = [1] + \
        [9 ** i for i in range(1, 6)] + \
        [6 ** i for i in range(1, 7)]
    dp = [float('inf')] * (N + 1)
    dp[N] = 0

    for n in range(N, 0, -1):
        for p in prices:
            if p <= N:
                dp[n-p] = min(dp[n] + 1, dp[n-p])

    return dp[0]


if __name__ == "__main__":
    N = int(input())
    ans = strange_bank(N)
    print(ans)


Measured memory_bytes: 3828
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll ans=0;
  ll n;
  cin>>n;
  vector<ll> counts(n+1,0);
  for(int i=1;i<=n;i++){
    for(int j=i;j<=n;j+=i){
      counts[j]++;
    }
  }
  for(int i=0;i<n+1;i++){
    ans+=counts[i]*i;
  }
  cout<<ans<<endl;
}
    
  

Measured memory_bytes: 81352
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  
#include <chrono>
#include <random>
#include <time.h>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define REP(e,v) for(auto e:v)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define tii tuple<int,int,int>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define edge(v,a,b) v[a].pb(b);v[b].pb(a);
#define MAX_V 400010
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define endl "\n"
#define ALL(c) (c).begin(),(c).end()
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}

#define INF 1e9+7
#define LLINF 1e18+7
ll MOD=1e9+7;
#define N 110000
ll n,x;
ll s[N];
vector<ll> dp(N);
main(){
    n=in(),x=in();
    rep(i,n){
        s[i]=in();
    }
    sort(s,s+n,greater<int>());
    dp[x]=1;
    rep(i,n){
        vector<ll> dp2(N);
        rep(j,100100){
            dp2[(j%s[i])]+=dp[j];
            dp2[(j%s[i])]%=MOD;
            dp2[j]=(dp2[j]+dp[j]*(n-1-i)%MOD)%MOD;
        }
        dp=dp2;
    }
    ll ans=0;
    rep(i,s[n-1]){
        ans+=i*dp[i]%MOD;
        ans%=MOD;
    }
    cout<<ans;
}


Measured memory_bytes: 1956
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define loop(i, a, b) for (int i = a; i < (int)(b); i++)


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

    double rate = 0;
    for (int i = 1; i <= n; i++) {
        if (i >= k) {
            rate += 1;
            continue;
        }
        double r = 1.0;
        int s = i;
        while (s < k) {
            s *= 2;
            r /= 2.0;
        }
        rate += r;
    }
    double ans = rate / (double)n;
    printf("%.12f", ans);
}

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

public class Main{
	public static void main(String args[]){
		try{
			new Main();
		}catch(IOException err){
			err.printStackTrace();
		}
	}

	public Main() throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		List<Integer> ans = new ArrayList<Integer>();
		String line = in.readLine();

		int size = Integer.parseInt(line);

		for(int n=0; n<size; n++){
			line = in.readLine();
			int a = SC(line);
			ans.add(a);
		}

		for(int i=0; i<ans.size(); i++){
			System.out.println(ans.get(i));
		}
	}

	public int SC(String line){
		List<String> eq = new ArrayList<String>();
		int count = 0;
		while(true){
			String str = line.substring(count, count+1);
			if(str.equals("=")){
				break;
			}
			eq.add(str);
			count++;
		}

		count = 0;
		while(count < eq.size()-1){
			if(isNumber(eq.get(count)) && isNumber(eq.get(count+1))){
				String dst = eq.get(count) + eq.get(count+1);
				eq.add(count+2, dst);
				eq.remove(count);
				eq.remove(count);
			}
			else{
				count++;
			}
		}


		while(eq.size() != 1){
			//ツ環古環づ個計ツ算
			int m;
			int bra_count = 0;
			int n = eq.indexOf("(");
			if(n != -1){
				for(int i=n+1; i<eq.size(); i++){
					if(eq.get(i).equals(")") && bra_count == 0){
						eq = RangeReplace(eq, n, i);
						break;
					}
					else if(eq.get(i).equals("(")){
						bra_count++;
					}
					else if(eq.get(i).equals(")")){
						bra_count--;
					}
				}

				continue;
			}

			//ツ掛ツつッツ算ツ環づィツ算
			n = eq.indexOf("*");
			m = eq.indexOf("/");

			if(n != -1 && (m == -1 || n < m)){
				int a = Integer.parseInt(eq.get(n-1)) * Integer.parseInt(eq.get(n+1));
				eq.add(n+2, Integer.toString(a));
				eq.remove(n-1);
				eq.remove(n-1);
				eq.remove(n-1);
				continue;
			}

			if(m != -1 && (n == -1 || m < n)){
				int a = Integer.parseInt(eq.get(m-1)) / Integer.parseInt(eq.get(m+1));
				eq.add(m+2, Integer.toString(a));
				eq.remove(m-1);
				eq.remove(m-1);
				eq.remove(m-1);
				continue;
			}

			//ツ堕ォツつオツ算ツ暗クツつォツ算
			n = eq.indexOf("+");
			m = eq.indexOf("-");

			if(n != -1 && (m == -1 || n < m)){
				int a = Integer.parseInt(eq.get(n-1)) + Integer.parseInt(eq.get(n+1));
				eq.add(n+2, Integer.toString(a));
				eq.remove(n-1);
				eq.remove(n-1);
				eq.remove(n-1);
				continue;
			}

			if(m != -1 && (n == -1 || m < n)){
				int a = Integer.parseInt(eq.get(m-1)) - Integer.parseInt(eq.get(m+1));
				eq.add(m+2, Integer.toString(a));
				eq.remove(m-1);
				eq.remove(m-1);
				eq.remove(m-1);
				continue;
			}
		}

		return Integer.parseInt(eq.get(0));
	}

	public List<String> RangeReplace(List<String> eq, int s, int e){
		String part = "";

		for(int i=s+1; i<e; i++){
			part += eq.get(i);
		}

		part = Integer.toString(SC(part+"="));

		eq.add(e+1, part);

		for(int i=s; i<=e; i++){
			eq.remove(s);
		}

		return eq;
	}

	public boolean isNumber(String s){
		try{
			int n = Integer.parseInt(s);
		}catch(NumberFormatException err){
			return false;
		}

		return true;
	}
}

Measured memory_bytes: 10000
#include<cstdio>
#include<iostream>
#include<string>

using namespace std;

int main(void)
{
	int N = 0;
	int K = 0;
	string S;
	cin >> N;
	cin >> K;
	cin >> S;

	K--;

	S[K] = tolower(S[K]);

	cout << S;
}

Measured memory_bytes: 256
N, M, Q = map(int, input().split())
tracks = [[] for i in range(N)]
for i in range(M):
    L, R = map(int, input().split())
    tracks[L-1].append(R-1)
    
for track in tracks: track.sort()

ans = [[None for j in range(N)] for i in range(N)]
for L in range(N):
    cur = 0
    tot = 0
    for R in range(L, N):
        while cur < len(tracks[L]) and tracks[L][cur] <= R:
            cur += 1
            tot += 1
        ans[L][R] = tot

dp =[[None for i in range(N)] for j in range(N)]
for i in range(Q):
    p, q = map(int, input().split())
    if dp[p-1][q-1] == None:
        dp[p-1][q-1] = sum(ans[i][q-1] for i in range(p-1, q))
    print(dp[p-1][q-1])
    


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

Measured memory_bytes: 3056
/*
 *  author : Atul Anand   
 *  created on : Wed Apr 01 2020
 */

import java.io.*;
import java.util.*;

public class Main{

    public static void main(String[] args) throws IOException {
        long A = in.nextLong();
        long B = in.nextLong();
        long K = in.nextLong();
        if(A >= K){
            println((A-K) + " " + B);
        }
        else{
            println(0 + " " + Math.max(0, B - K + A));
        }
        in.close();
        out.close();
    }

    static int MIN = Integer.MIN_VALUE;
    static int MAX = Integer.MAX_VALUE;
    static Reader in = new Reader();
    static PrintWriter out = new PrintWriter(System.out);

    static void read(int arr[], int N) throws IOException { 
    	for(int i = 0; i < N; i++){ 
    		arr[i] = in.nextInt(); 
    	} 
    }
    
    static void read(long arr[], int N) throws IOException { 
    	for(int i = 0; i < N; i++){ 
    		arr[i] = in.nextLong(); 
    	} 
    }
    
    static void read(String arr[], int N) throws IOException { 
    	for(int i = 0; i < N; i++){ 
    		arr[i] = in.next(); 
    	} 
    }
    
    static void print(Object O) {  
    	out.print(O); 
    }
    
    static void println(Object O) { 
    	out.println(O); 
    }
    
    static void println(int arr[]) { 
    	for(int i = 0; i < arr.length; i++){ 
    		print(arr[i]+" "); 
    	} 
    	println(""); 
    }

    static void println(int arr[][]) { 
    	for(int i = 0; i < arr.length; i++){ 
    		println(arr[i]); 
    	}
    }
    
    static void debug(Object O) { 
    	System.out.println(O); 
    }
}

class Reader {
    BufferedReader reader;
    StringTokenizer tokenizer;

    Reader() {
        reader = new BufferedReader(new InputStreamReader(System.in));
        tokenizer = new StringTokenizer("");
    }

    String next() throws IOException {
        while (!tokenizer.hasMoreTokens() ) { 
            tokenizer = new StringTokenizer(reader.readLine()); 
        }
        return tokenizer.nextToken();
    }

    int nextInt() throws IOException { 
        return Integer.parseInt(next()); 
    }
    
    double nextDouble() throws IOException { 
        return Double.parseDouble(next());
    }
    
    long nextLong() throws IOException { 
        return Long.parseLong(next()); 
    }
    
    String nextLine() throws IOException { 
        return reader.readLine(); 
    }
    
    void close() throws IOException { 
        reader.close(); 
    }
}

Measured memory_bytes: 23124
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(void)
{
    IOS
    string s; cin >> s;
    int ans = 0;
    REP(i,s.size()) {
        if (s[i] == '+') ans++;
        else ans--;
    }

    cout << ans << '\n';

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include<vector>
#include <algorithm>
#include<cstdlib>
#include<set>
#include<math.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i,n) for(ll i=0;i<n;i++)

int main()
{
	int n;
	string s;
	cin >> n >> s;
	string a = "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ";
	string b = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	int num = s.size();
	for(int x = 0  ;x < num; x++ )
	{
		
		for(int y=0 ; y < 26 ; y++ )
		{
			if (s[x]==b[y])
			{
				cout << a[y + n];				
			}
		}
	}

	cout << "\n";


	return 0;
}

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


void solve(long long M, long long K){
    if (M == 1) {
        if (K == 0) {
            cout << "0 0 1 1" << endl;
        }
        else
        {
            cout << -1 << endl;
        }
    }
    else if (K >= pow(2, M)) {
        cout << -1 << endl;
    }
    else if (K == 0) {
        for (int i = 0; i<pow(2,M)-1 ;i++) {
            cout << i << " " << i << " ";
        }
        cout << pow(2,M) -1 << " " << pow(2,M) -1 << endl;
    }
    else
    {
        for (int i = 0; i<pow(2,M) ;i++) {
            if (i != K) {
                cout << i << " ";
            }
        }
        cout << K << " ";
        for (int i = pow(2,M)-1; i>=0 ;i--) {
            if (i != K) {
                cout << i << " ";
            }
        }
        cout << K << endl;

    }
    
}

// Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long M;
    scanf("%lld",&M);
    long long K;
    scanf("%lld",&K);
    solve(M, K);
    return 0;
}


Measured memory_bytes: 1792
def f(i):
    global m
    if i == len(b):
        c = []
        c = [s[0]]
        for j in range(len(b)):
            if not b[j] == 0:
                for k in range(len(c)):
                    m += int(c[len(c) - k - 1]) * 10 ** k
                c = []
            c.append(s[j + 1])
        for k in range(len(c)):
            m += int(c[len(c) - k - 1]) * 10 ** k
        c = []
        return
    f(i + 1)
    b[i] = 1
    f(i + 1)
    b[i] = 0

s = list(input())
b = [0] * (len(s) - 1)
m = 0
f(0)
print(m)

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

int main(){
	int N, Q;
	cin >> N >> Q;
	char S[N];
	for(int i=0; i<N; i++) cin >> S[i];
	int sum[N];
	sum[0] = 0;
	for(int i=1; i<N; i++){
		if(S[i-1] == 'A' && S[i] == 'C') sum[i] = sum[i-1] + 1;
		else sum[i] = sum[i-1];
	}
	for(int i=0; i<Q; i++){
		int l, r;
		cin >> l >> r;
		cout << sum[r-1] - sum[l-1] << endl;
	}
	return 0;
}


Measured memory_bytes: 1280
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>

#define int long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define FST first
#define SND second
#define SZ(a) (signed)((a).size())
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;

const int MOD = 1000000007;

#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")"  << " " << __FILE__ << endl;

signed main(void) {
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed, ios::floatfield);
    cout.precision(10);
    cin.tie(0);

    int n, k;
    cin >> n >> k;
    VI a(n);
    REP(i, n) {
        cin >> a[i];
    }

    int ans = 0;
    REP(i, n) {
        if (a[i] > 0) {
            ans += a[i];
        }
    }

    int pos = 0, neg = 0;
    REP(i, k) {
        if (a[i] > 0) {
            pos += a[i];
        } else {
            neg += a[i];
        }
    }
    int posmin = pos, negmax = neg;
    FOR(i, k, n) {
        if (a[i] > 0) {
            pos += a[i];
        } else {
            neg += a[i];
        }
        if (a[i - k] > 0) {
            pos -= a[i - k];
        } else {
            neg -= a[i - k];
        }
        posmin = min(posmin,pos);
        negmax = max(negmax,neg);
    }

    cout << max(ans-posmin,ans+negmax) << endl;

    return 0;
}

Measured memory_bytes: 1024
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/stack:16777216")
#include <string>
#include <vector>
#include <map>
#include <list>
#include <iterator>
#include <cassert>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <stack>
#include <deque>
#include <cmath>
#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <utility>
#include <time.h>
#include <complex>
using namespace std;

#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i)
#define FILL(A,value) memset(A,value,sizeof(A))

#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
#define Pi 3.14159265358979
#define x0 ikjnrmthklmnt
#define y0 lkrjhkltr
#define y1 ewrgrg

typedef long long Int;
typedef unsigned long long UInt;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<Int, Int> PLL;
typedef pair<double, double> PDD;
typedef complex<double> base;

const int INF = 1000000000;
const int BASE = 1000000007;
const int MAX = 2007;
const int MAXX = 1000000;
const int ADD = 1000000;
const int MOD = 1000000007;
const int CNT = 800;

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("distance.in",  "r", stdin);
    //freopen("distance.out", "w", stdout);
    //freopen("out.txt" , "w" , stdout);
    
    
    int n , a , b;
    cin >> n >> a >> b;
    if (a % 2 != b % 2)
    {
        cout << "Borys" << endl;
    }
    else
    {
        cout << "Alice" << endl;
    }
    
    return 0;
}













Measured memory_bytes: 764
import * as fs from "fs";

const memo: Array<Array<number>> = [];
function gcd(x: number, y: number): number {
	if (y === 0) return x;
	if (memo[y] === undefined) memo[y] = [];
	if (memo[y][x] === undefined) {
		return memo[y][x] = gcd(y, x % y);
	}
	return memo[y][x];
}
const input = (fs.readFileSync("/dev/stdin", "utf8") as string).split("\n");
const k = +input[0];

let result = 0;
for (let a = 1; a <= k; a++) {
	for (let b = 1; b <= k; b++) {
		const temp = gcd(Math.max(a, b), Math.min(a, b));
		for (let c = 1; c <= k; c++) {
			result += gcd(Math.max(temp, c), Math.min(temp, c));
		}
	}
}
console.log(result);


Measured memory_bytes: 33288
A, B, C, X, Y = map(int, input().split())
if A + B <= 2 * C:
    ans = A * X + B * Y
elif A + B > 2 * C:
    nokori = abs(X - Y)
    if X >= Y and A >= 2 * C:
        ans = C * 2 * X
    if Y >= X and B >= 2 * C:
        ans = C * 2 * Y
    if X >= Y and A <= 2 * C:
        ans = C * 2 * Y + nokori * A
    if Y >= X and B <= 2 * C:
        ans = C * 2 * X + nokori * B
print(ans)

Measured memory_bytes: 3064
#include<stdio.h>

int main(){
  int i,j,k,n,v;
  scanf("%d",&n);
  int A[n];
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  
  
  for(k=0;k<n;k++){
    printf("%d",A[k]);
    if(k<n-1){
      printf(" ");
    }else{
      printf("\n");
    }
  }
  
  for(i=1;i<=n-1;i++){
    v=A[i];
    
    for(j=i-1;j>=0&&A[j]>v;j--){
      A[j+1]=A[j];
    }
    A[j+1]=v;
    for(k=0;k<n;k++){
      printf("%d",A[k]);
      if(k<n-1){
	printf(" ");
      }else{
	printf("\n");
      }
    }
  }
  return 0;
}



Measured memory_bytes: 2124
#include <algorithm>
#include <iostream>
#include <numeric>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

const int M = 1000000000 + 7;

long long inv(int x, int m) {
  long long a[3] = {1, 0, x};
  long long b[3] = {0, 1, m};
  while (b[2] > 0) {
    long long r = a[2] / b[2];
    for (int i = 0; i < 3; ++i) {
      a[i] = a[i] - b[i] * r;
    }
    std::swap(a, b);
  }
  if (a[2] != 1) {
    throw std::runtime_error("no inv");
  }
  return a[0] > 0? a[0] % m: (m - (-a[0]) % m) % m;
}

long long comb(int n, int r) {
  long long x = 1;
  r = std::min(n, n - r);
  for (int i = 0; i < r; ++i) {
    x = x * (n - i) % M * inv(i + 1, M) % M;
  }
  return x;
}

int main() {
  long long h, w, a, b, c;
  long long ans = 0;
  std::cin >> h >> w >> a >> b;
  ans = comb(h + w - 2, h - 1);
  for (int i = 0; i < b; ++i) {
    // c = comb(h - a + i - 1, h - a - 1) * comb(a + w - i - 2, a - 1) % M;
    if (i == 0) {
      c = comb(h - a - 1, h - a - 1) * comb(a + w - 2, a - 1) % M;
    } else {
      c = c * (h - a + i - 1) % M * inv(i, M) % M;
      c = c * (w - i) % M * inv(a + w - i - 1, M) % M;
    }
    ans = (ans + M - c) % M;
  }
  std::cout << ans << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int n;
ll arr[200100], brr[200100];

int pre(int i) {return (i+n-1)%n;}
int nxt(int i) {return (i+1)%n;}
int good(int i) {return brr[i]>=brr[pre(i)]+brr[nxt(i)]+arr[i];}
int main() {
    scanf("%d",&n);
    for (int i=0;i<n;i++) scanf("%lld",&arr[i]);
    for (int i=0;i<n;i++) scanf("%lld",&brr[i]);
    queue<int> q;
    for (int i=0;i<n;i++) {
        if (good(i)) q.push(i);
    }
    ll ans = 0;
    while(!q.empty()) {
        int t = q.front(); q.pop();
        ll v = (brr[t]-arr[t])/(brr[pre(t)]+brr[nxt(t)]);
        ans += v;
        brr[t]-= v*(brr[pre(t)]+brr[nxt(t)]);
        if (good(pre(t))) q.push(pre(t));
        if (good(nxt(t))) q.push(nxt(t));
    }
    for (int i=0;i<n;i++) if (arr[i]!=brr[i]) {
        puts("-1");
        return 0;
    }
    printf("%lld\n",ans);

    return 0;
}


Measured memory_bytes: 3840
#include<stdio.h>
int main()
{
    int n;
    scanf("%d", &n);
    if (n == 3)
    {
        printf("61\n");
        return 0;
    }
    long long int m = 1000000007;
    long long int p[102][4][4][4][4];
    int a, b, c, d, e;
    for (a = 0; a < 102; a++)
        for (b = 0; b < 4; b++)
            for (c = 0; c < 4; c++)
                for (d = 0; d < 4; d++)
                    for (e = 0; e < 4; e++)
                        p[a][b][c][d][e] = 0;
    for (a = 0; a < 4; a++)
        for (b = 0; b < 4; b++)
            for (c = 0; c < 4; c++)
                for (d = 0; d < 4; d++)
                    p[4][a][b][c][d] = 1;
    for (a = 0; a < 4; a++)
    {
        p[4][a][0][2][3] = 0;
        p[4][a][2][0][3] = 0;
        p[4][a][0][3][2] = 0;
        p[4][0][a][2][3] = 0;
        p[4][0][2][a][3] = 0;
        p[4][0][2][3][a] = 0;
        p[4][2][0][3][a] = 0;
        p[4][0][3][2][a] = 0;
    }
    int q;
    for (q = 4; q < n; q++)
    {
        for (a = 0; a < 4; a++)
            for (b = 0; b < 4; b++)
                for (c = 0; c < 4; c++)
                    for (d = 0; d < 4; d++)
                    {
                        p[q + 1][b][c][d][0] += p[q][a][b][c][d];
                        p[q + 1][b][c][d][1] += p[q][a][b][c][d];
                        p[q + 1][b][c][d][2] += p[q][a][b][c][d];
                        p[q + 1][b][c][d][3] += p[q][a][b][c][d];
                        p[q + 1][b][c][d][0] %= m;
                        p[q + 1][b][c][d][1] %= m;
                        p[q + 1][b][c][d][2] %= m;
                        p[q + 1][b][c][d][3] %= m;
                    }
        for (a = 0; a < 4; a++)
        {
            p[q + 1][a][0][2][3] = 0;
            p[q + 1][a][2][0][3] = 0;
            p[q + 1][a][0][3][2] = 0;
            p[q + 1][0][a][2][3] = 0;
            p[q + 1][0][2][a][3] = 0;
        }
    }
    long long int ans = 0;
    for (a = 0; a < 4; a++)
        for (b = 0; b < 4; b++)
            for (c = 0; c < 4; c++)
                for (d = 0; d < 4; d++)
                    ans = (ans + p[n][a][b][c][d]) % m;
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<numeric>
#include<set>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
typedef long long li;
#define repa(i,a,n) for(int i=(a);i<(n);i++)
#define MOD 1000000000
#define rep(i,n) for(int i=0;i<(n);i++)

#define df 0
template<class T> void print(const T& t){ cout << t << "\n"; }
template<class T, class... Ts> void print(const T& t, const Ts&... ts) { cout << t; if (sizeof...(ts)) cout << " "; print(ts...); }
// // Container コンテナ型, map以外
// template< template<class ...> class Ctn,class T>
// std::ostream& operator<<(std::ostream& os,const Ctn<T>& v){
//   // ここでストリームに obj を書き込みます。
//   auto itr=v.begin();
//   while(itr!=v.end()){
//     if(itr!=v.begin())cout << " ";
//     cout << *(itr++);
//   }
//   return os;
// }


int main(){
  int n; cin >>n;
  vector<int> a(n+1),b(n);
  rep(i,n+1) cin >>a[i];
  rep(i,n) cin >>b[i];
  li cnt=0;
  rep(i,n){
    int m=min(a[i],b[i]);
    cnt+=m;
    a[i]-=m; b[i]-=m;
    m=min(a[i+1],b[i]);
    cnt+=m;
    a[i+1]-=m; b[i]-=m;
  }
  print(cnt);
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define LLINF (1LL<<60)
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

//C++14 (GCC 5.4.1)
int main() {
    int A,B;
    cin >>A>>B;
    
    //-----------------------------------
    int Ans=2*A-1;
    chmax(Ans,A+B);
    chmax(Ans,2*B-1);
    cout << Ans <<endl;
    return (0);
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
using namespace std;
long long maxn;
long long sum;
long long mp[510][510];
int main(){
	int H,W,h,w;
	scanf("%d%d%d%d",&H,&W,&h,&w);
	if(H % h == 0 && W % w == 0){
		printf("No");
		return 0;
	}
	else if(h == 1 && w == 1){
		printf("No");
		return 0;
	}
	maxn = (int)H*W / (h*w) +100;
	//printf("Yes\n");
	for(int i = 1;i <= H;i ++){
		for(int j = 1;j <= W; j++){
			if(i % h == 0 && j % w == 0){
				mp[i][j] = - maxn*(h*w-1) - 1;
				//printf("%lld",- maxn*(h*w-1) - 1);
			}
			else{
				mp[i][j] = maxn;
				//printf("%lld",maxn);
			}
			sum += mp[i][j];
			//printf("\n");
		}
	}
	if(sum < 0){
		printf("No");
	}
	else{
		printf("Yes\n");
		for(int i = 1;i <= H;i ++){
			for(int j = 1;j <= W;j ++){
				printf("%lld ",mp[i][j]);
			}
			printf("\n");
		}
	}
	return 0;
}

Measured memory_bytes: 4096
x = input().split()
x = [int(i) for i in x]
apples = []
for i in range(x[0]):
  apples.append(i+x[1])
ab_apples = [abs(i) for i in apples]
max_ap = max(apples)
min_ab = min(ab_apples)
if max_ap > min_ab:
  apples.remove(min_ab)
  print(sum(apples))
else:
  apples.remove(max_ap)
  print(sum(apples))

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

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const ld eps = 1e-9;
const ll MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}

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

  int n; cin >> n;
  bool ok = false;
  while(n > 0) {
    ok |= n % 10 == 7;
    n /= 10;
  }
  cout << (ok ? "Yes" : "No") << endl;
  
}


Measured memory_bytes: 3652
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <numeric>//accumulateを使うためにインクルード

using namespace std;

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    if(a <= c && c <= b) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
readline=sys.stdin.readline
N,M=map(int,readline().split())
mlst = [0] * M
for i in range(1,M+1):
  _, *tmp = map(int,readline().split())
  for j in tmp:
    mlst[i-1] |= 1<<(j-1)
    
def popcnt(n):
    # 求1的个数
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
    return c
  
  
mod = list(map(int, readline().split()))
ab = list(zip(mlst, mod))
res = 0
for i in range(1<<N):
  for a,b in ab:
    tmp = a & i
    if popcnt(tmp) & 1 != b:
      break
  else:
    res += 1
print(res)

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;

void Main(){
    int n, m; cin >> n >> m;
    vvi sw(m);
    vi p(m);
    
    rep(i, m){
        int k; cin >> k;
        rep(j, k){
            int s; cin >> s; s--;
            sw[i].pb(s);
        }
    }   
    rep(i, m) cin >> p[i];
    
    int tot = 0;
    rep(bit, 1 << n){
        vi on(n, 0);
        rep(i, n){
            if(bit >> i & 1) on[i] = 1; 
        }
        bool ok = true;
        rep(j, m){
            int par = p[j];
            for(auto s : sw[j]){
                par += on[s];
            }
            if(par % 2) ok = false; 
        }
        if(ok) tot++;
        // cout << bit << " " << ok << endl;
    }
    
    cout << tot << endl;
    return;
}

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}

Measured memory_bytes: 3580
mod = 10**9+7
def comb(n, k):
    c = 1
    for i in range(k):
        c *= n - i
        c %= mod
    d = 1
    for i in range(1, k + 1):
        d *= i
        d %= mod
    return (c * pow(d, mod - 2, mod)) % mod
x,y=map(int,input().split())

ans=0

z=x//2

for q in range(z,x+1):
  w=2*q-x
  if w*2+(q-w)==y:
    t=comb(q,w)
    ans+=t
    
  
  
print(ans)


Measured memory_bytes: 65068
#include <bits/stdc++.h>
using namespace std;
template<class T>bool chmax(T &a, const T &b){return(a=max(a,b))==b;}
int n, ans=0,l=0,r=1;
string s;
int main(){
    cin>>n>>s;
    for(;r<=n;r++){
        if(s.find(s.substr(l,r-l),r)<n)chmax(ans,r-l);
        else l++;
    }
    cout<<ans<<endl;
    return 0;
}


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

int main() {
  int n,m;
  cin >> n;
  m = n;
  
  int digit = 0;
  for(int i=0; i<10; i++) {
    if(m / 10 == 0) {
      digit = i + 1;
      break;
    }
    else
      m /= 10;
  }
  
  if(digit % 2 == 0)
    cout << (pow(100, digit/2) - 1) / 11 << endl;
  else 
    cout << (pow(100, digit/2) - 1) / 11 + n - pow(10, digit - 1) + 1 << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define LL long long
#define int long long
#define db double
using namespace std;
 
const int MAXN = 500500;
const int MAXE = 400400;
const int INF = (1LL << 60 | 100);
 
template<typename T> inline void CheckMax(T &A, T B) {
	A < B ? A = B : A;
}
 
template<typename T> inline void CheckMin(T &A, T B) {
	A > B ? A = B : A;
}
 
template <typename T> inline void read(T &x) {
    int c = getchar();
    bool f = false;
    for (x = 0; !isdigit(c); c = getchar()) {
        if (c == '-') {
            f = true;
        }
    }
    for (; isdigit(c); c = getchar()) {
        x = x * 10 + c - '0';
    }
    if (f) {
        x = -x;
    }
}
 
LL n, m;
LL P[MAXN], cnt, num[MAXN];
 
void solve(LL x) {
	for(LL i = 2; i * i <= x; i++) {
		if(x % i == 0) {
			LL cur = 0;
			while(x % i == 0) {
				x /= i;
				cur++;
			}
			P[++cnt] = cur;
			num[cnt] = i;
		}
	}
	if(x > 1) P[++cnt] = 1;
}
 
signed main() {
	cin >> n >> m;
	if(n == 1) {
		cout << m << endl;
		return 0;
	}
	if(n > m) {
		cout << 1 << endl;
		return 0;
	}
	solve(m);
	LL ans = 1LL;
	for(int i = 1; i <= cnt; i++) {
		while(P[i] >= n) {
			ans = ans * num[i], P[i] -= n;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 2304
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    for(int i = 0; i+1 < n; i++){
        if(a[i] == a[i+1]){
            for(int j = i+2; j < n; j++){
                if(a[j] == a[j+1]){
                    cout << (long long)a[i] * a[j] << endl;
                    return 0;
                }
            }
            i = n;
        }
    }
    cout << 0 << endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
#ifdef __LOCAL
#define debug(x) cerr << __LINE__ << ": " << #x << " = " << x << endl
#define debugArray(x, n)                           \
  cerr << __LINE__ << ": " << #x << " = {";        \
  for (long long hoge = 0; (hoge) < (n); ++(hoge)) \
    cerr << ((hoge) ? "," : "") << x[hoge];        \
  cerr << "}" << endl
#else
#define debug(x) (void(0))
#define debugArray(x, n) (void(0))
#endif

template <int mod>
struct ModInt {
  int x;
  ModInt() : x(0) {}
  ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod)) {}
  ModInt &operator+=(const ModInt &p) {
    if ((x += p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator-=(const ModInt &p) {
    if ((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator*=(const ModInt &p) {
    x = (int)(1LL * x * p.x % mod);
    return *this;
  }
  ModInt &operator/=(const ModInt &p) { return *this *= p.inverse(); }
  ModInt operator-() const { return ModInt() - *this; }
  ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
  ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
  ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
  ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
  bool operator==(const ModInt &p) const { return x == p.x; }
  bool operator!=(const ModInt &p) const { return x != p.x; }
  ModInt inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while (b) t = a / b, swap(a -= t * b, b), swap(u -= t * v, v);
    return ModInt(u);
  }
  ModInt pow(int64_t e) const {
    ModInt ret(1);
    for (ModInt b = *this; e; e >>= 1, b *= b)
      if (e & 1) ret *= b;
    return ret;
  }
  friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; }
  friend istream &operator>>(istream &is, ModInt &a) {
    int64_t t;
    is >> t;
    a = ModInt<mod>(t);
    return (is);
  }
  static int modulo() { return mod; }
};

vector<int> primes;
void init(int n) {
  primes.push_back(2);
  bool is_prime[n + 1];
  fill(is_prime, is_prime + n + 1, true);
  for (long long p = 3; p <= n; p += 2)
    if (is_prime[p]) {
      primes.push_back(p);
      for (long long i = p * p; i <= n; i += p) is_prime[i] = false;
    }
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  using Mint = ModInt<int(1e9 + 7)>;
  init(1e6);
  int N;
  cin >> N;
  Mint ans = 0;
  int cnt[primes.size()];
  fill(cnt, cnt + primes.size(), 0);
  for (int i = 0; i < N; i++) {
    int X;
    cin >> X;
    ans += Mint(X).inverse();
    for (int j = 0; j < primes.size(); j++) {
      int p = primes[j];
      int c = 0;
      while (X % p == 0) {
        X /= p;
        c++;
      }
      cnt[j] = max(cnt[j], c);
    }
  }
  for (int j = 0; j < primes.size(); j++) {
    ans *= Mint(primes[j]).pow(cnt[j]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4840
# -*- coding: utf-8 -*-
def main():
    a, b, c = map(int, input().split())
    
    mp = {}
    if(a not in mp):
        mp[a] = 1
    else:
        mp[a] += 1
    if(b not in mp):
        mp[b] = 1
    else:
        mp[b] += 1
    if(c not in mp):
        mp[c] = 1
    else:
        mp[c] += 1

    if(mp[5] == 2 and mp[7] == 1):
        print('YES')
    else:
        print('NO')
    
    
main()


Measured memory_bytes: 3188
#include<iostream>
#include<algorithm>
#include<climits>
#include<vector>
#include<utility>//pair
#include<cmath>//abs,sqrt
#include<cstring>
#include<map>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define prin(arg) cout<<arg<<"\n"
#define prin2(arg1,arg2) cout<<arg1<<" "<<arg2<<"\n"
#define fill(arg,n) memset(arg,n,sizeof(arg))
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int INF=1e+9;
const ll INFLL=1e+17;
int n,m;
int a[51],b[51];
int res[51];
void solve(){
  rep(i,n) res[i]=0;
  rep(i,m){
    res[a[i]]++;
    res[b[i]]++;
  }
}
int main(){
  cin>>n>>m;
  rep(i,m){
    cin>>a[i]>>b[i];
    a[i]--;
    b[i]--;
  }
  solve();
  rep(i,n){
    prin(res[i]);
  }
  
  return 0;
}


Measured memory_bytes: 256
//=======================================
// abc146b
//
//  2019/11/23
//=======================================

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char* argv[])
{
	cin.tie(0);
  ios::sync_with_stdio(false);

  int n; cin >> n;
  string s; cin >> s;

  for(int i=0; i<s.size(); ++i)
  {
    char t;
    t = s[i]+n;
    if(t>='A'+26) t-=26;
    cout << t;
  }
  cout << endl;


  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
priority_queue<pair<double,int>,vector<pair<double, int>>, greater<pair<double, int>> > pq;
double min_t[31][31][31];
int N, M, S, G;
int x, y, d, c;
struct R {int to, d, c;};
vector<R> town[31];

int main() {
	/*ifstream in("Ain.txt");
	cin.rdbuf(in.rdbuf());
	ofstream ofs("Aout.txt");
	cout.rdbuf(ofs.rdbuf());*/
	while(cin >> N >> M, N) {
		for(int i = 0; i < 31; i++) town[i].clear();
		for(int i = 0; i < 31; i++) for(int j = 0; j < 31; j++) for(int k = 0; k < 31; k++) min_t[i][j][k] = 20000000.0;
		cin >> S >> G;
		for (int m = 0; m < M; m++) {
			cin >> x >> y >> d >> c;
			town[x].push_back((R){y, d, c});
			town[y].push_back((R){x, d, c});
		}
	
	pq.push(make_pair(0.0, S * 31));
	while (!pq.empty()) {
		double t = pq.top().first;
		int u = pq.top().second / 1000;
		int p = (pq.top().second - u * 1000) / 31;
		int v = (pq.top().second - u * 1000) % 31;
		pq.pop();
		for (auto r : town[p]) {
			if (r.to == u) continue;
			for(int v2 = max(1, v - 1); v2 <= min(r.c, v + 1); v2++) {
				double t2 = t + (double)r.d / (double)v2;
				if (min_t[r.to][v2][u] > t2) {
					min_t[r.to][v2][u] = t2;
					pq.push(make_pair(t2, p * 1000 + r.to * 31 + v2));
				}
			}
		}
		}
		double ans = 2e7;
		for (int k = 0; k < 31; k++) ans = min(ans ,min_t[G][1][k]);
		if (ans == 2e7) cout << "unreachable" << endl;
		else cout << ans << endl;
	}
}
	
	
	



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

#define int long long
typedef pair<int, int> P;

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

/*
#define cin ifs
#define cout ofs
ifstream ifs("in.txt");
ofstream ofs("out.txt");
//*/
int Q;
int A[110], B[110];

signed main() {
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        cin >> A[i] >> B[i];
    }
    for (int i = 0; i < Q; i++) {
        if (A[i] == B[i]) {
            cout << (A[i] - 1) * 2 << endl;
            continue;
        }
        if (A[i] > B[i]) swap(A[i], B[i]);
        int seki = A[i] * B[i];
        int rt = (int)sqrt(seki);
        int ans = 2 * rt - 1;
        if ((seki - 1) / rt == rt) ans--;
        if (rt * rt == seki) ans-=2;
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define ld double
#define mp make_pair
#define pb push_back
#define mod 1000000007
#define ff first
#define ss second
#define pll pair <ll,ll>
#define nl "\n"
ll dp[2][100005];
int main()
{
	ios_base::sync_with_stdio(false);
	ll n,wt,i,j,ans;	
	cin>>n>>wt;
	ll w[n+2],v[n+2];
	for(i=0;i<n;i++)
		cin>>w[i]>>v[i];
	if(n==1)
	{
		cout<<v[0]<<nl;
		return 0;
	}
	for(i=0;i<2;i++)
	{
		for(j=0;j<=100005;j++)
			dp[i][j]=1e10;
	}
	dp[1][v[n-1]]=w[n-1];
	dp[1][0]=0;
	for(i=n-2;i>=0;i--)
	{
		for(j=0;j<100005;j++)
		{
			dp[0][j] = dp[1][j];
			if(j>=v[i])
			{
				dp[0][j] = min(dp[0][j], dp[1][j-v[i]] + w[i]);
			}
		}
		for(j=0;j<100005;j++)
			dp[1][j]=dp[0][j];
	}

	for(i=0;i<100005;i++)
	{
		if(dp[0][i] <= wt)
			ans = i;
	}
	cout<<ans<<nl;
	return 0;
}

Measured memory_bytes: 5076
from bisect import bisect_left

N = int(input())
*A, = map(int, input().split())

L = [A[0]]
for a in A[1:]:
    if a > L[-1]:
        # Lの末尾よりaが大きければ増加部分列を延長できる
        L.append(a)
    else:
        # そうでなければ、「aより小さい最大要素の次」をaにする
        # 該当位置は、二分探索で特定できる
        L[bisect_left(L, a)] = a

ret = N + 1
for cnt, l_ in enumerate(L, 1):
    if l_ != cnt:
        break
    ret = cnt

print(N - ret)


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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
template<typename T> using v = vector<T>;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto& i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
void dump_debug(T list) {
#ifdef MY_DEBUG
    each(e, list) cout << e << " ";
    printf("\n");
#endif
}

inline ll inl() {
    ll x;
    cin >> x;
    return x;
}

inline string ins() {
    string x;
    cin >> x;
    return x;
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        string s = ins();
        string ans;
        for (long long i = 0; i < s.size(); i += 2) {
            ans += s[i];
        }
        cout << ans << endl;
#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Measured memory_bytes: 512
fun main(arg: Array<String>) {
    val S = next()
    val N = S.length - 1
    val e = Eval()
    var ans = 0L
    for (b in 0 until 1.shl(N)) {
        val P = BooleanArray(N)
        for (n in 0 until N) {
            if (b.shr(n).and(1) == 1) P[n] = true
        }
        val Ex = StringBuilder()
        for (n in 0 until N) {
            Ex.append(S[n])
            if (P[n]) Ex.append('+')
        }
        Ex.append(S.last())
        ans += e.eval(Ex.toString())
    }


    println(ans)
}

fun next() = readLine()!!
fun nextInt(delta: Int = 0) = Integer.parseInt(next()) + delta
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map(String::toInt)
fun listOfLong() = listOfString().map(String::toLong)
fun listOfInt(delta: Int = 0) = listOfString().map { Integer.parseInt(it) + delta }


class Eval {
    private val num_list = java.util.ArrayList<Long>()
    private val ope_list = java.util.ArrayList<Char>()
    private fun _list_init() {
        num_list.clear()
        ope_list.clear()
    }
    private fun _lexical_analysis(formula: String) {
        val sequenceList = formula.toCharArray()
        var set_num = 0L
        for (token in sequenceList) {
            if ("+-*/".indexOf(token) > -1) {
                ope_list.add(token)
                num_list.add(set_num)
                set_num = 0L
            } else if ("123456789".indexOf(token) > -1) {
                set_num *= 10L
                set_num += (token - '0').toLong()
            }
        }
        num_list.add(set_num)
    }
    fun _calculation(): Long {
        var num1_num: Long
        var num2_num: Long
        var set_num: Long
        var num1_id: Int
        var num2_id: Int
        var hit_id: Int
        var hit_count = 0
        for (token in ope_list) {
            hit_id = -1
            if (token == '*' || token == '/') {
                hit_id = ope_list.indexOf(if (token == '*') '*' else '/')
                ope_list[hit_id] = '@'
                num1_id = hit_id - hit_count
                num2_id = hit_id - hit_count + 1
                num1_num = num_list[num1_id]
                num2_num = num_list[num2_id]
                set_num = if (token == '*') num1_num * num2_num else num1_num / num2_num
                num_list[num1_id] = set_num
                num_list.removeAt(num2_id)
                hit_count++
            }
        }
        while (ope_list.remove('@')) { }
        for (token in ope_list) {
            num1_id = 0
            num2_id = 1
            num1_num = num_list[num1_id]
            num2_num = num_list[num2_id]
            set_num = num1_num + if (token == '+') num2_num else -num2_num
            num_list[num1_id] = set_num
            num_list.removeAt(num2_id)
        }
        return num_list[0]
    }

    fun eval(formula: String): Long {
        var anser = 0L
        _list_init()
        _lexical_analysis(formula)
        anser = _calculation()
        return anser
    }
}

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

using namespace std;

using ll=long long;

ll table[100001];

int main(){
    ll n,k;cin>>n>>k;
    for(int i=0;i<n;++i){
        int a,b;cin>>a>>b;
        table[a]+=b;
    }
    for(int i=1;i<=100000;++i){
        k-=table[i];
        if(k<=0){
            cout<<i<<endl;
            break;
        }
    }
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll INF=mod*mod;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(x) (x).begin(),(x).end()
ll min(ll a,ll b){
  if(a>b){
    return b;
    }
      else{
        return a;
      }
  }
  
  ll max(ll a,ll b){
    if(a>b){
      return a;
    }
    else{
      return b;
    }
  }

ll power(ll a,ll b){
 ll ans=1;
 for(ll i=1;i<=b;i++){
ans*=a;
  }
  return ans;
}

 ll gcd(ll m,ll n){
 	if(n==0){
       return m;
     }
   return gcd(n,m%n);
 }
ll lcm(ll a,ll b){
  ll g=gcd(a,b);
  return a/gcd(a,b)*b;
		

}
int main(){
  ll N;
  cin>>N;
  vector<ll>a(N);
   vector<ll>ans(N);
  ll odd=0;
  ll eve=0;
  rep(i,N){
    cin>>a[i];
   if(i<N-1){
     if((i+1)%2==0){
eve+=a[i];
     }
     else{
       odd+=a[i];
     }

   }
    
  }
  ll X;
 for(ll i=0;i<=a[0];i++){
   X=i;
   if(a[N-1]==eve-odd+2*X){
   break;
   }
 }
   ans[0]=X*2;
   ll num=X;
   for(ll j=1;j<N;j++){
 num=a[j-1]-num;
     ans[j]=num*2;
   }

  
  rep(i,N){
    cout<<ans[i]<<" ";
  }
  cout<<endl;
}



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


int main(){
	int n;
	char c;
	cin>>n;
	int res = 0,tmp = 0;
	for(int i=0;i<n;i++){
		cin>>c;
		if(c=='I')  res = max(res,++tmp);
		else tmp--;
	}
	cout<<res;
}

Measured memory_bytes: 256