akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<math.h>
double dMIN(double a,double b){return a<b?a:b;}
double f(int a,int b){return sqrt((a+b)*(a+b)-(a-b)*(a-b));}
int i,j,k,n=0,r=0,d[20];
double l[15][1000010]={};
int main(){
  char s[100010];
  double min;
  while(fgets(s,100000,stdin)){
    for(i=r=n=0;s[i];i++){
      if('0'<=s[i]&&s[i]<='9')n=n*10+s[i]-'0';
      else{
	d[r++]=n;
	n=0;
      }
    }
    //for(i=0;i<r;i++)printf("%d ",d[i]);printf("\n");
    for(i=0;i<(1<<(r-1));i++){
      for(j=0;j<r-1;j++)l[j][i]=1e9;
    }
    for(i=0;i<r-1;i++)l[i][1<<i]=d[i+1];
    for(i=0;i<(1<<(r-1));i++){
      for(j=0;j<r-1;j++){//printf("%18f ",l[j][i]);
	if(i&(1<<j)==0)continue;
	for(k=0;k<r-1;k++)l[k][i|(1<<k)]=dMIN(l[k][i|(1<<k)],l[j][i]+f(d[j+1],d[k+1]));
	//printf("%18f ",l[j][i]);
      }//printf("\n");
    }
  
    min=1e9;
    for(i=0;i<r-1;i++)min=dMIN(min,l[i][(1<<(r-1))-1]+d[i+1]);//printf("%f\n",min);
    printf("%s\n",min<d[0]+1e-9?"OK":"NA");
  }
  return 0;
}

Measured memory_bytes: 23064
#include<algorithm>
#include<climits>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<list>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<utility>
#include<vector>

#define lint long long
#define REP(i, x, n) for(int i = x ; i < n ; i++)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; i--)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())
#define IINF INT_MAX
#define LLINF LLONG_MAX

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<bool> color(8, false);
    int f = 0;
    rep(i, n){
        int a;
        cin >> a;
        a /= 400;
        if(a >= 8){
            f++;
        }else{
            color[a] = true;
        }
    }
    int minAns = 0, maxAns = 0;
    rep(i, 8){
        minAns += color[i];
    }
    maxAns = minAns + f;
    minAns = max(minAns, 1);
    cout << minAns << " " << maxAns << endl;
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(N: int, x: "List[int]", y: "List[int]", h: "List[int]"):
    for cx in range(0,101):
        for cy in range(0,101):
            H= 0
            for i in range(N):
                if h[i] != 0:
                    H = h[i] + abs(x[i]-cx) + abs(y[i]-cy)
            for i in range(N):
                if max(H - abs(x[i]-cx) - abs(y[i]-cy),0) != h[i]:
                        break
                else:
                    continue
            else:
                print(cx,cy,H)
                return

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    h = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
        h[i] = int(next(tokens))
    solve(N, x, y, h)

if __name__ == '__main__':
    main()


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

int n,m;
int dp[101000];
vector <int> v[101000];

int gao(int x){
	if(dp[x]!=-1) return dp[x];
	for(int i=0;i!=v[x].size();++i){
		dp[x]=max(dp[x],gao(v[x][i])+1);
	}
	return dp[x];
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		int a,b;
		cin>>a>>b;
		v[a].push_back(b);
	}
	memset(dp,-1,sizeof(dp));
	for(int i=1;i<=n;++i) if(v[i].size()==0) dp[i]=0;
	for(int i=1;i<=n;++i){
		if(dp[i]==-1) gao(i);
	}
	int ans=0;
	for(int i=1;i<=n;++i) ans=max(ans,dp[i]);
	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 8192
from collections import deque

H,W = map(int,input().split())

graph = [input() for i in range(H)]
q = deque([(0,0)])
dist = [[-1] * W for i in range(H)]
dist[0][0] = 1

while q:
    y, x = q.popleft()
    L = [(1,0), (-1,0), (0,1), (0,-1)]
    for i, j in L:
        if ((0 <= y+i <= H-1 and 0 <= x+j <= W-1)
            	and dist[y+i][x+j] == -1
            	and graph[y+i][x+j] == "."):
        	dist[y+i][x+j] = dist[y][x] + 1
        	q.append((y+i, x+j))

white = 0
for i in range(H):
    white += graph[i].count(".")
    
if dist[H-1][W-1] == -1:
    print("-1")
else:
    ans = white - dist[H-1][W-1]
    print(ans)

Measured memory_bytes: 40304
mod = 10**9+7
memo = dict()
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
factorial = [1 for i in range(n+1+k)]
for i in range(1,n+1+k):
    factorial[i] = (factorial[i-1] * i) % mod
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
#a/b = a*(b`)となるb`を求める
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod
def mod_combination(n,k,mod):
    if n < k:
        return 0
    return factorial[n] * mod_inv(factorial[n-k], mod) * mod_inv(factorial[k], mod)
ans = 0
for i in range(n):
    #今回の数字が、最小値として数えられる数の合計
    ans -= a[i] * mod_combination(n - i - 1, k-1,mod)
    #今回の数字が、最大値として数えられる数の合計
    ans += a[i] * mod_combination(i,k-1,mod)
    ans %= mod
print(int(ans))

Measured memory_bytes: 70056
#include <cstdio>
#include <utility>
using namespace std;

typedef pair<int, int> ii;

int H, W;
char board[8][15];
ii moves[2] = {ii(0, 1), ii(1, 0)};

int main(){
  int numHex = 0, numVisited = 1, r = 0, c = 0;
  scanf("%d %d", &H, &W);
  for(int i=0; i<H; i++) scanf("%s", board[i]);
  for(int i=0; i<H; i++)
    for(int j=0; j<W; j++) numHex+=board[i][j]=='#';
  while(r<H-1 || c<W-1){
    bool canMove = false;
    for(int i=0; i<2; i++){
      int r2 = r+moves[i].first, c2 = c+moves[i].second;
      if(r2>=H || c2>=W || board[r2][c2]!='#') continue;
      r = r2; c = c2; numVisited++; canMove = true; break;
    }
    if(!canMove) break;
  }
  printf(numVisited==numHex? "Possible\n": "Impossible\n");
  return 0;
}


Measured memory_bytes: 128
/* Author rumoisen */
/* created 2018/10/13 */

#include <vector>
#include <map>
#include <string>
#include <cmath>
#include <iomanip>
#include <numeric>
#include<iostream>
#include <algorithm>
 
using namespace std;
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define INF (ll)1e18
#define MOD (ll)1e9 + 7
#define pb push_back

void no(){cout<<"No"<<endl;exit(0);}
void yes(){cout<<"Yes"<<endl;exit(0);}
void No(){cout<<"NO"<<endl;exit(0);}
void Yes(){cout<<"YES"<<endl;exit(0);}

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

using namespace std;

int main()
{
    int n,a,b;
    cin>>n>>a>>b;
    if(a*n<=b) cout<<a*n;
    else cout<<b;
    return 0;
}

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

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

const ll INF=LLONG_MAX;

ll dp[11][1011];
ll p[111], c[111];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int n,m; cin >> n >> m;
	for(int i=1; i<=n; i++){
		cin >> p[i] >> c[i];
		c[i]/=100;
	}
	m/=100;
	memset(dp,-1,sizeof(dp));
	dp[0][0]=0LL;
	for(int i=1; i<=n; i++){
		for(int j=0; j<=1000; j++){
			if(dp[i-1][j]!=-1){
				for(int k=0; k<p[i]; k++)
					dp[i][j+k]=max(dp[i][j+k],dp[i-1][j]+k*i);
				dp[i][j+p[i]]=max(dp[i][j+p[i]],dp[i-1][j]+p[i]*i+c[i]);
			}
		}
	}
	for(int j=0; j<=1000; j++){
		if(dp[n][j]>=m){
			cout << j << endl;
			return 0;
		}
	}
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN


Measured memory_bytes: 384
X, Y = map(int, input().split())
reward = [300000, 200000, 100000, 0]
X -= 1
Y -= 1
if X >= 3:
  X = 3
if Y >= 3:
  Y = 3
answer = reward[X]+reward[Y]
if X == 0 and Y == 0:
  answer += 400000
print(answer)

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

typedef long long ll;

#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
#define INF 10e7
#define MOD 1000000000 + 7
#define MAX 51000
#define all(x) (x).begin(), (x).end()
#define MX(x) *max_element(all(x))
#define MN(x) *min_element(all(x))
using namespace std;

void solve(void)
{
    string a, b;
    cin >> a >> b;
    int x = stoi(a + b);
    string ans = "No";
    for (int i = 1; i * i <= x; ++i)
    {
        if (i * i == x)
            ans = "Yes";
    }
    cout << ans << endl;
}
int main(void)
{
    solve();
}

Measured memory_bytes: 3608
#include<iostream>
#include<string>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<algorithm>

using namespace std;

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

  if(a>=1000){
    cout<<"ABD"<<endl;
  } else {
    cout<<"ABC"<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STACK_MAX 1000

void push(int);
int pop();
static int top;
static int stack[STACK_MAX];

int main()
{
  int num,ans1,ans2;
  char c[100];

  while((scanf("%s",c))!=EOF){
    if(c[0]=='+'){
      ans1=pop();
      ans2=pop();
      push(ans2+ans1);
    }else if(c[0]=='-'){
      ans1=pop();
      ans2=pop();
      push(ans2-ans1);
    }else if(c[0]=='*'){
      ans1=pop();
      ans2=pop();
      push(ans2*ans1);
    }else{
      num=atoi(c);
      push(num);
    }
  }

  printf("%d\n",pop());
  return 0;
}

void push(int n){
  stack[top]=n;
  top++;
}
int pop(void){
  top--;
  return stack[top];
}



Measured memory_bytes: 2076
#include <bits/stdc++.h>
//Ishita
using namespace std;
 
int main(){
    int x, a, b;
    int dig, ans;
    cin >> x >> a >> b;
    ans = x - a;
    dig = ans / b;
    ans -= dig * b;
    cout << ans << endl; 
    return 0;
}

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

int main(){
int a,b,c,d;
for(;;){
cin>>a>>b>>c>>d;
c-=b;
if(c<=0){
cout<<"Yes"<<endl;
  break;
}
  a-=d;
if(a<=0){
cout<<"No"<<endl;
  break;
}
}
}



Measured memory_bytes: 3616
n,m=[int(x) for x in input().split()]
ab=[[int(x) for x in input().split()] for i in range(m)]

ab.sort(key=lambda x:x[1])
#print(ab)
split=[0,]

#while len(ab)!=0:
for item in ab:
  if (item[1]-split[-1]>0 and item[0]-split[-1]<=0)!=True:
    split.append(item[1]-1)
  
  #print(ab)
print(len(split)-1)

Measured memory_bytes: 64472
N, M, X, Y = map(int, input().split())
x_list = list(map(int, input().split()))
y_list = list(map(int, input().split()))

x_list.sort()
y_list.sort()

if x_list[-1] >= y_list[0]:
    print('War')
else:
    z_list = [z for z in range(x_list[-1], y_list[0]+1)]
    z_list.sort()
    if z_list[0] <= X or z_list[-1] > Y:
        print('War')
    else:
        print('No War')


Measured memory_bytes: 3064
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,A,B=MI()
    if (A-B)&1:
        if A<B:
            A,B=B,A
        if N-B<A-1:
            ans = N-B+1
            ans += (B-A)//2
        else:
            ans = A-1+1
            ans += (B-A)//2
        print(ans)
    else:
        print(abs(A-B)//2)
if __name__ == '__main__':
    main()

Measured memory_bytes: 38452
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.Closeable;
import java.io.IOException;
import java.util.NoSuchElementException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author HBonsai
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CUnification solver = new CUnification();
        solver.solve(1, in, out);
        out.close();
    }

    static class CUnification {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            char[] S = in.next().toCharArray();
            int zero = 0;
            int one = 0;
            for (int i = 0; i < S.length; i++) {
                if (S[i] == '0') zero++;
                else one++;
            }
            out.println(Math.min(zero, one) * 2);
        }

    }

    static class FastScanner implements Closeable {
        private final InputStream in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;

        public FastScanner(InputStream in) {
            this.in = in;
        }

        private boolean hasNextByte() {
            if (ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (buflen <= 0) {
                    return false;
                }
            }
            return true;
        }

        private int readByte() {
            if (hasNextByte()) return buffer[ptr++];
            else return -1;
        }

        private static boolean isPrintableChar(int c) {
            return 33 <= c && c <= 126;
        }

        public boolean hasNext() {
            while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
            return hasNextByte();
        }

        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while (isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public void close() {
            try {
                in.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

    }
}



Measured memory_bytes: 22740
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int main(){
    int N;
  cin >> N;
  string s;
  cin >>s;
  //累積和で解く。
  vector<int> wh(N+1,0);//wh[0]=0;
  vector<int> bl(N+1,0);
  for(int i=0;i<N;i++){
      if(s[i]=='.'){
          wh[i+1]=wh[i]+1;
          bl[i+1]=bl[i];
      }
      else{
          bl[i+1]=bl[i]+1;
          wh[i+1]=wh[i];
      }
  }
  int ans=N;
  for(int i=0;i<=N;i++){
ans=min(ans,bl[i]+wh[N]-wh[i]);
  }
  /*for(int i=1;i<=N;i++){
      cout <<bl[i];
  }cout<<endl;
for(int i=1;i<=N;i++){
      cout <<wh[i];
  }
  */
  cout <<ans <<endl;
return 0;
}

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

int main(){
  ll n;
  cin >> n;
  vector<ll> a;
  for (int i = 0; i < n; i++){
    ll x;
    cin >> x;
    a.push_back(x);
  }
  sort(a.begin(), a.end());
  ll res = 0;
  ll sz = 0;
  for (int i = 0; i < n; i++){
    sz += a[i];
    if (sz * 2 < a[i+1]) {
      res = i+1;
    }
  }
  cout << n - res << endl;
  return 0;
}


Measured memory_bytes: 1400
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) throws IOException {
    
    try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

      int n = Integer.parseInt( br.readLine() );
      String[] line = br.readLine().split(" ");

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

      insertionSort(a, n);
    }
  }

  public static void insertionSort(int a[], int max) {
    for (int i=0,j=0,v=0; i < max; i++) {
      for( j = i-1, v = a[i]; j>=0 && a[j]>v; j-- ) {
        a[j+1] = a[j];
      }
      a[j+1] = v;
      dispIntArray(a);
    }
  }
  public static void dispIntArray(int a[]) {
    for (int i=0, max = a.length-1; i < max; i++) {
      System.out.print(a[i] + " ");
    }
    System.out.println(a[a.length-1]);
  }
}


Measured memory_bytes: 29840
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int N = sc.nextInt();
		int[][] AB = new int[N][2];
		for(int i=0;i<N;i++) {
			AB[i][0]=sc.nextInt();
			AB[i][1]=sc.nextInt();
		}

		Arrays.sort(AB, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return Integer.compare(o1[1], o2[1]);
			}
		});
		long t=0;
		for(int i=0;i<N;i++) {
			t+=AB[i][0];
			if(t<=AB[i][1])continue;
			else {
				System.out.println("No");
				return;
			}
		}
		System.out.println("Yes");
	}


}

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

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define AND(x,y,z) set_intersection((x).begin(),(x).end(),(y).begin(),(y).end(),inserter((z),(z).end()))
#define CONCAT(x,y) (x).insert((x).end(),(y).begin(),(y).end())
#define DUMP(xs) for (auto x:xs) cout<<x<<' ';cout<<endl
#define FOR(i,a,b) for (int i=(int)(a);i<(int)(b);++i)
#define OR(x,y,z) set_union((x).begin(),(x).end(),(y).begin(),(y).end(),inserter((z),(z).end()))
#define OUT(x) cout<<x<<endl
#define REP(i,n) FOR(i,0,n)

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<int> VECINT;
typedef vector<ll> VECLL;

int main() {
  int H,W;cin>>H>>W;
  char grid[H][W];
  bool visited[H][W];

  REP(i,H)REP(j,W) cin>>grid[i][j];
  REP(i,H)REP(j,W) visited[i][j] = false;

  // グリッドを見ていって、訪問済みならcont
  // dfsで連結する全てのをtrueに変えていく
  // もし一つだけの要素があったらNo return
  // 最後までいったらyes

  REP(i,H) {
    REP(j,W) {
      if (grid[i][j]=='.' || visited[i][j]) continue;

      deque<P> dq{{i,j}};
      visited[i][j] = true;
      bool alone_flag = true;
      while (!dq.empty()) {
        P p = dq.front();
        int h = p.first;
        int w = p.second;
        dq.pop_front();
        if (h>0 && grid[h-1][w]=='#' && !visited[h-1][w]) {
          dq.push_back({h-1,w});
          visited[h-1][w] = true;
        }
        if (h<H-1 && grid[h+1][w]=='#' && !visited[h+1][w]) {
          dq.push_back({h+1,w});
          visited[h+1][w] = true;
        }
        if (w>0 && grid[h][w-1]=='#' && !visited[h][w-1]) {
          dq.push_back({h,w-1});
          visited[h][w-1] = true;
        }
        if (w<W-1 && grid[h][w+1]=='#' && !visited[h][w+1]) {
          dq.push_back({h,w+1});
          visited[h][w+1] = true;
        }
        // 一度でもここでtrueになればfalseになる
        if (!dq.empty()) alone_flag = false;
      }
      if (alone_flag) {
        OUT("No");
        return 0;
      }
    }
  }
  OUT("Yes");

  return 0;
}

Measured memory_bytes: 256
N = int(input())
arr = [0] + list(map(int, input().split(' '))) #ずらしておく。
for i in range(N//2, 0, -1):
  arr[i] = sum(arr[i::i]) % 2
ans = [i for i, j in enumerate(arr) if j == 1]
print(len(ans))
print(*ans)


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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}

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

	int64 N;
	cin >> N;
	vector<int64> A(N+1), B(N);
	REP(i, N+1) cin >> A[i];
	REP(i, N) cin >> B[i];
	int64 res = 0, rest = 0;
	REP(i, N) {
	    res += min(B[i], A[i]);
	    B[i] = max((int64)0, B[i]-A[i]);
	    res += min(B[i], A[i+1]);
	    A[i+1] = max((int64)0, A[i+1]-B[i]);
	}
	cout << res << endl;
}


Measured memory_bytes: 1792
import java.util.*;

public class Main {
	
	
	public static int MinorChange(String s ,String t) {
		int count = 0;
		
		 char[] arr1 = s.toCharArray();
		 char[] arr2 = t.toCharArray();
//		 
//		 Arrays.sort(arr1);
//		 Arrays.sort(arr2);
		for(int i=0,j=0;i<s.length();i++,j++)
		{
			if(arr1[i]!=arr2[j]) {
				count++;
			}
		}
		
		return count;
	}

	public static void main(String[] args) {
		Scanner s1 = new Scanner (System.in); 
		String s =s1.next();
		String t = s1.next();
		System.out.println(MinorChange(s, t));
		

	}

}


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

using namespace std;

int main(void)
{
    int n, k, s = 1, i;

    cin >> n >> k;
    for(i = 1; i <= n; i++){
        if(s > k){
            s += k;
        }
        else{
            s *= 2;
        }
    }

    cout << s << endl;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void){
  int w,h,n;
  scanf("%d",&w);
  scanf("%d",&h);
  scanf("%d",&n);
  int point[h][w];
  int x[n];
  int y[n];
  int a[n];
  int s = 0;
  for(int i = 0;i < h;i++){
    for(int j = 0;j < w;j++){
      point[i][j] = 0;
    }
  }
  for(int i = 0;i < n;i++){
    scanf("%d",&x[i]);
    scanf("%d",&y[i]);
    scanf("%d",&a[i]);
  }
  for(int i = 0;i < n;i++){
    if(a[i] == 1){
      for(int j = 0;j < h;j++){
        for(int k = 0;k < x[i];k++){
          point[j][k] = 1;
        }
      }
    }else if(a[i] == 2){
      for(int j = 0;j < h;j++){
        for(int k = x[i];k < w;k++){
          point[j][k] = 1;
        }
      }
    }else if(a[i] == 3){
      for(int j = 0;j < y[i];j++){
        for(int k = 0;k < w;k++){
          point[j][k] = 1;
        }
      }
    }else if(a[i] == 4){
      for(int j = y[i];j < h;j++){
        for(int k = 0;k < w;k++){
          point[j][k] = 1;
        }
      }
    }
  }
  for(int i = 0;i < h;i++){
    for(int j = 0;j < w;j++){
      if(point[i][j] == 0){
        s++;
      }
    }
  }
  printf("%d",s);
  printf("\n");
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

vector<vector<int>> G;

// O(HW)
int n;
int d[110];
void bfs(){
    queue<int> que;
    
    que.push(0); // (0,0)スタート
    d[0]=0;
    while(!que.empty()){
        int p=que.front();
        que.pop();
        for(int nv : G[p]){
            if(d[nv]!=-1) continue;
            que.push(nv);
            d[nv]=d[p]+1;
        }
    }
}

int main() {
    
    cin>>n;
    G.resize(n);
    rep(i,n){
        int u,k;
        cin>>u>>k;
        u--;
        rep(j,k){
            int v;
            cin>>v;
            v--;
            G[u].push_back(v);
        }
    }

    rep(i,n) d[i]=-1;
    bfs();

    rep(i,n){
        cout<<i+1<<" "<<d[i]<<endl;
    }

}





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

int main(void){
    int i, j, key, *a, n, k;
    scanf("%d", &n);
    a = (int *)calloc(n, sizeof(int));

    for(i = 0;i < n;i++){
        scanf("%d", &a[i]);
    }
    for(k = 0;k < n;k++){
        printf("%d", a[k]);
        ((k < n-1)?printf(" "):printf("\n"));
    }

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

    return 0;
}


Measured memory_bytes: 2680
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

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

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int H,W; cin>>H>>W;
	vector<string> s(H);
	for (int i=0; i<H; i++)
		cin>>s[i];
	queue<ii> q; q.push({0,0});
	vector<vector<int>> dist(H,vector<int>(W,-1));
	dist[0][0]=1;
	while(!q.empty()) {
		ii cur=q.front(); q.pop();
		for (int i=0; i<4; i++) {
			ii nxt=cur; nxt.first+=dx[i]; nxt.second+=dy[i];
			if(nxt.first<0||nxt.first>=H||nxt.second<0||nxt.second>=W) continue;
			if(s[nxt.first][nxt.second]=='#') continue;
			if(dist[nxt.first][nxt.second]!=-1) continue;
			dist[nxt.first][nxt.second]=dist[cur.first][cur.second]+1;
			q.push(nxt);
		}
	}
	if(dist[H-1][W-1]==-1) {
		cout<<-1<<"\n";
		return 0;
	}
	int ret=H*W-dist[H-1][W-1];
	for (int i=0; i<H; i++)
		for (int j=0; j<W; j++)
			if(s[i][j]=='#')
				ret--;
	cout<<ret<<"\n";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int d[55];
int main( void )
{
  ios::sync_with_stdio(false);
  int N, M, a, b;
  cin >> N >> M;
  for( int i=0; i<M; i++ ){
    cin >> a >> b;
    d[a]++; d[b]++;
  }
  for( int i=1; i<=N; i++ ){
    cout << d[i] << endl;
  }
}

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

int main() {
  string s;
  cin>>s;
  int count=0;
  int result=0;
  for(int i=0;i<s.size();i++){
    if(s.at(i)=='A'||s.at(i)=='T'||s.at(i)=='G'||s.at(i)=='C'){
      count++;
      result=max(result,count);
    }else{
      result=max(result,count);
      count=0;
    }
  }
  cout<<result<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <numeric>
using namespace std;
 
#define LOCAL  1
#define UPLOAD 2
 
#define ll long long
const long long INF = 1LL << 60;
 
template <class T = long long> T input(){T x;cin >> x;return x;}
template <class T> void output(T x){cout << x << endl;}
#define debug(x) cerr << #x<< ": " << x<< '\n';
#define debugBit(x,n) cerr << #x<< ": " << std::bitset<n>(x) << '\n';
#define REP(i,M) for(int i=0;i<M;i++)
 
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
 
int main()
{
#if ENVIRONMENT == LOCAL
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif
 
  ll A = input();
  ll B = input();
 
  for(int i=1;i<=10000;i++){
    ll s1 = floor(i*0.08);
    ll s2 = floor(i*0.1);

    if(s1 == A && s2 == B){
      output(i);
      return 0;
    }
  }

  output(-1);
  
  return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0
for i in range(n):
    if a[i] <= b[i]:
        ans += a[i]
        b[i] -= a[i]
        a[i] = 0
    else:
        ans += b[i]
        a[i] -= b[i]
        b[i] = 0
    if b[i] > 0:
        tmp = max(0, a[i + 1] - b[i])
        if tmp == 0:
            ans += a[i + 1]
        else:
            ans += b[i]
        a[i + 1] = tmp
print(ans)

Measured memory_bytes: 24080
#include <stdio.h>
#define A 100
int main(void){
  int num,i,j,in[A],temp,min;
  int cnt = 0;

  scanf("%d",&num);

  for(i=0;i<num;i++){
    scanf("%d",&in[i]);
  }
 
  for(i=0;i<num;i++){
    min = i;
    for(j=i;j<num;j++){
      if(in[j]<in[min]) min = j;
    }
    //if(min != i){
    if(in[i]>in[min]){
    temp = in[i];
    in[i] = in[min];
    in[min] = temp;
    cnt++;
  }
}

  for(i=0;i<num-1;i++){
    printf("%d ",in[i]);
  }
  
    printf("%d\n%d\n",in[num-1],cnt);

  return 0;
}



Measured memory_bytes: 2084
///******* In the name of Allah *******///

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

//long long int ar[100013];
//long int gcd(long int a, long int b)
//{
//    if(b==0)
//        return a;
//    return gcd(b,a%b);
//}
//int sieve(long long int a)
//{
//    long long int i,j;
//    memset(ar,0,sizeof(ar));
//    for(i=2; i<=10013; i++)
//    {
//        if(ar[i]==0)
//        {
//            for(j=i+i; j<=10013; j+=i)
//            {
//                ar[j] = 1;
//            }
//        }
//    }
//    if(ar[a]==0)
//    {
//        return ar[a];
//    }
//}

void Ok()
{
    long int a,b,c,h,t,i = 0,j = 0,k,l,m,n;
    long int ans_1,ans_2,ans_3,cnt = 0,Max,Min,flag = 0,temp,sum;
    double aa,bb,cc,dd,ee,ff,gg;
    char aaa[113],bbb[113],ccc[113],ddd;
    string spc,in;

    cin>>n;
    while(n!=0)
    {
        a = n%10;
        n /= 10;
        if(a==7)
        {
            flag = 1;
            cout<<"Yes"<<endl;
            break;
        }
    }
    if(!flag)
        cout<<"No"<<endl;

    return;
}

int main()
{
    Ok();

    return 0;
}


Measured memory_bytes: 3628
#include <stdio.h>
#include <stdlib.h>
 
int main(void)
{
    int n, t[100001], x[100001], y[100001];
    int i, dt, dist;
    scanf("%d", &n);
    t[0] = x[0] = y[0] = 0;
    for (i=1; i<n+1; i++)
    {
        scanf("%d %d %d", &t[i], &x[i], &y[i]);
    }
 
    for (i=1; i<n+1; i++)
    {
        dt =  t[i] - t[i-1];
        dist = abs(x[i] - x[i-1]) + abs(y[i] - y[i-1]);
        if (dt < dist) {
            printf("No");
            return 0;
        }
        if ((dt - dist) % 2 != 0) {
            printf("No");
            return 0;
        }
    }
 
        printf("Yes\n");

    return 0;
}

Measured memory_bytes: 1280
// This is the start of shubhams template//
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long int
void input(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
}
#define deg(x) cout<<#x<<" = "<<x;
#define vll vector<int>
#define pb push_back
#define pll pair<int,int>
#define mp(a,b) make_pair(a,b)
#define ff first
#define ss second
#define INF LONG_LONG_MAX
#define mod 1000000007
#define all(x) x.begin(),x.end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define cases int t; cin>>t; while(t--)
#define array(a,n) vll a(n); rep(i,0,n) cin>>a[i];
#define sortall(a) sort(a.begin(),a.end())
#define printall(a) rep(i,0,a.size()) cout<<a[i]<<" "; cout<<endl;
//this is the end of shubhams template //
int power(int a,int n);
void solve();
int32_t main()
{
	//input();
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
}
int power(int a,int n)
{
    if(n==0)
        return 1;
    if(n%2!=0)
    {
        return (a*power((a*a),n/2));
    }
    return power((a*a),n/2);
}
void solve()
{
	string ans;
	cin>>ans;

	if(ans[ans.size()-1]=='s')
		ans += "es";
	else
		ans += "s";
	cout<<ans<<endl;
}

//shubham gupta


Measured memory_bytes: 3644
#include <iostream>
#include <fstream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <unordered_set>
#include <bitset>
#include <limits>
#include <algorithm>

int MOD_BIG = 1000000007;
int MOD_BIG2 = 998244353;
using std::string;
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using ll = long long;
using pint = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using std::vector;

#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)

//////////////////////////////////////

//////////////////////////////////////

int main() {
    
    int N;
    cin >> N;
    
    string S;
    cin >> S;
    
    int cnt = 0;
    vector<bool> isred(N);
    REP(i, N) {
        if (S[i] == 'R') {
            isred[i] = true;
            cnt++;
        }
    }
    int ans = cnt;
    REP(i, cnt) {
        if (isred[i]) ans--;
    }
    
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 3756
import java.util.*;
import java.lang.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        int a[] = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);
        int sum = 0;
        int count = 0;
        for(int i = 0; i < n; i++){
            sum += a[i];
            if (sum > x) {
                break;
            }else{
                count++;
            }
        }
        if (count == n && sum != x) {
            System.out.println(count - 1);
        }else{
            System.out.println(count);
        }
    }
}

Measured memory_bytes: 21844
#include <stdio.h>
#define MAX 200000

int main(){
  int n,i,R[MAX],max,min;

  scanf("%d",&n);

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

  max=-2000000000;
  min=R[0];

  for(i=1;i<n;i++){
    if(max<R[i]-min) max=R[i]-min;
    if(min>R[i]) min=R[i];
  }

  printf("%d\n",max);

  return 0;
}


Measured memory_bytes: 2588
#include<stdio.h>
long long h[100000];
long long dp[100000];

	long long n;
long long abs(long long a,long long b);
long long min(long long a,long long b);

long long abs(long long a,long long b)

{
	if(a>b)
	{
		return a-b;
	}
	else
	{
		return b-a;
	}
}


long long min(long long a,long long b)
{
	if(a>b)
	{
		return b;
	}
	else
	{
		return a;
	}
}
long long cost(long long i)
{
	if(dp[i]!=-1)
	{
		return dp[i];
	}
	else if(i==n-1)
	{
		return dp[i]=0;
	}
	else if(i==n-2)
	{
		return dp[i]=abs(h[i],h[i+1]);
	}
	else
	{
		return dp[i]=min(abs(h[i],h[i+1])+cost(i+1),abs(h[i],h[i+2])+cost(i+2));
	}
}
int main()
{
	scanf("%lld",&n);
	long long i;
	for(i=0;i<n;i++)
	{
		scanf("%Ld",&h[i]);
	}
	for(i=0;i<n;i++)
	{
		dp[i]=-1;
	}
	printf("%Ld\n",cost(0));
	return 0;

}
	


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

int main() {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	int n, m; cin >> n >> m;
	cout << (n*(n - 1)) / 2 + (m*(m - 1)) / 2 << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const ll mod = 1e9+7;
const int N=2e5+9;
int main()
{
    FASTINOUT;
    int y[3];
    int a,b;
    cin>>a>>b;
    y[0]=a*b;
    y[1]=a-b;
    y[2]=a+b;
    sort(y,y+3);
    cout<<y[2];
    return 0;
}

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

signed main() {
  string s;
  cin >> s;

  int n = s.size();
  int answer = 0;
  for (int i = n - 1; i >= 0; i--) {
    string tmp = s.substr(0, i);
    if(tmp.size() % 2 != 0) continue;

    string left = tmp.substr(0, tmp.size()/2);
    string right = tmp.substr(tmp.size()/2, tmp.size()/2);
    if(left == right) {
      answer = i;
      break;
    }
  }

  cout << answer << endl;

  return 0;
}

Measured memory_bytes: 3640
#include <stdio.h>

int main(){

  int i,j,x,y,z,n=0,s,m,w=0;
  int C[2000000];
  char c[12];

  scanf("%d",&n);


  for(i=0;i<n;i++){
    scanf("%s%d",c,&y);
    if(c[0]=='i'){
      C[i]=y;
    }
    else if(c[6]=='F'){
      i-=2;
      n-=2;
    }
    else if(c[6]=='L'){
      w++;
      i--;
      n--;
    }
    else{
      m=0;
      n--;
      i--;

      for(j=i;j>=0;j--){
	if(m>0){
	    break;
	  }
	  if(y==C[j]){
	    s=i-j;
	    x=0;
	    m++;

	    while(s!=x++){
	      C[j+x-m]=C[j+x];
	    }
	    i--;
	    n--;
	  }
	  }
    }
  }

  i=0;
  while(i<n-w){
    if(i==n-w-1){
      printf("%d\n",C[n-1-i]);
    }
    else{
      printf("%d ",C[n-1-i]);
    }
    i++;
  }
  return 0;
}



Measured memory_bytes: 5696
#include <bits/stdc++.h>
using namespace std;
#define lmax LLONG_MAX
#define lmin LLONG_MIN
#define imax INT_MAX
#define imin INT_MIN
#define f(i,a,b) for(long long i=a;i<b;i++)
#define rf(i,a,b) for(long long i=a;i>=b;i--)
#define tc long long test;cin>>test;while(test--)
#define pb push_back
#define mp make_pair
#define gcd __gcd
#define F first
#define S second
#define input(a,n) for(ll i=0;i<n;i++) cin>>a[i];
#define output(a,n) for(ll i=0;i<n;i++){cout<<a[i]<<" ";}cout<<endl;
#define up upper_bound
#define lo lower_bound
#define endl "\n"
#define mem(a) memset(a,-1,sizeof(a))
#define ll long long
#define umap unordered_map

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    
    ll a,b,c,d;
    cin>>a>>b>>c>>d;

    cout<<max(a*c,max(a*d,max(b*c,b*d)));

    return 0;
}

Measured memory_bytes: 3632
import java.util.stream.*;
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        int n = scanner.nextInt();
        long i = 0, j = 0;
        long[] a = LongStream.range(0, n).map(k -> scanner.nextInt()).toArray();
        for (int k = 0; k < n; k++) {
            long b = scanner.nextInt();
            if (a[k] < b) {
                i += (b - a[k]) / 2;
            } else {
                j += a[k] - b;
            }
        }
        System.out.println(i >= j ? "Yes" : "No");
    }
}

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

int main()
{
	string str;
	cin >> str;
	int cnt = 0;
	for (int i = 0; i < 3; ++i)
	{
		if (str[i] == 'o') {
			cnt = cnt + 1;
		}
	}

	cout << 700 + cnt * 100 << endl;
}

Measured memory_bytes: 256
int main() {
  int x,y ,a;
  scanf("%d %d",&x,&y);
 
  while(x != 0 || y !=0) {
    if(x > y) {
      a = x;
      x =y;
      y = a;
    } 
    printf("%d %d\n",x , y);
    scanf("%d %d" ,&x,&y);
  
  }
  return 0;
}



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

#define F first
#define S second
#define PB push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef priority_queue<int> HEAP;
typedef priority_queue<int, vector<int>, greater<int> > RHEAP;

const int N = 110, M = 1010;

int n, m;
char s[N];

int C(int a, int b)
{
	int res = 1;
	for (int i = a; i > a - b; i -- ) res *= i;
	for (int i = 1; i <= b; i ++ ) res /= i;
	return res;
}

int qp(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1) res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}

int f(int n)
{
	if (!n) return 0;
	
	vector<int> nums;
	for (int i = n; i; i -- ) nums.PB(s[i] - '0');
	
	int res = 0;
	int last = 0;
	for (int i = n - 1; i >= 0; i -- )
	{
		int x = nums[i];
		if (x)
		{
			res += qp(9, m - last) * C(i, m - last);
			res += (x - 1) * qp(9, m - last - 1) * C(i, m - last - 1);
			last ++ ;
		}
		
		if (last == m)
		{
			res ++ ;
			break;
		}
		
		// if (!i) res ++ ;
	}
	
	return res;
}

int main()
{
	cin >> s + 1 >> m;
	n = strlen(s + 1);
	cout << f(n) << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main() {
	int x[5];
	for (int i = 0; i < 5; i++) {
		scanf("%d", x + i);
	}
	for (int i = 0; i < 5; i++) {
		if (x[i] == 0) {
			printf("%d\n", i + 1);
		}
	}
	return 0;
}

Measured memory_bytes: 1724
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String {
            bytes
                .by_ref()
                .map(|r| r.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
    input!{
        n: usize,
        k: usize
    }
    let d = 1000000007;
    let mut ns = vec![0; k];
    for i in 0..k {
        ns[i] = pow_m(k / (i + 1), n, d);
    }
    for i in (0..k).rev() {
        for j in 2..k / (i + 1) + 1 {
            ns[i] = (ns[i] + d - ns[j * (i + 1) - 1]) % d;
        }
    }
    let mut ans = 0;
    for i in 0..k {
        ans = (ans + (i + 1) * ns[i]) % d;
    }
    println!("{}", ans);
}

fn pow_m(n: usize, mut p: usize, d: usize) -> usize {
    let mut r = n;
    let mut ret = 1;
    while p > 0 {
        if p % 2 == 0 {
            r = r * r % d;
            p /= 2;
        } else {
            ret = ret * r % d;
            p -= 1;
        }
    }
    ret
}


Measured memory_bytes: 2776
use std::io::Read;

fn run() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let a: Vec<char> = it.next().unwrap().chars().collect();
    let b: Vec<char> = it.next().unwrap().chars().collect();
    if b.iter().all(|c| *c == '0') {
        if a.iter().all(|c| *c == '0') {
            println!("0");
        } else {
            println!("-1");
        }
        return;
    }
    let n = a.len();
    let mut x: Vec<char> = a.iter().cloned().cycle().take(2 * n).collect();
    let mut y: Vec<char> = b.iter().cloned().cycle().take(3 * n).collect();
    let mut ans = 3 * n;
    for _ in 0..2 {
        let mut left = vec![0; n];
        let mut right = vec![0; n];
        for i in 0..n {
            let mut j = i + n;
            while y[j] != '1' {
                j += 1;
            }
            right[i] = (j + n - i) % n;
            let mut j = i + n;
            while y[j] != '1' {
                j -= 1;
            }
            left[i] = (i + n - j) % n;
        }
        for k in 0..n {
            let mut sum = k;
            let mut cnt = 0;
            for i in 0..k {
                cnt += y[i].to_digit(10).unwrap();
            }
            let mut p = vec![];
            for i in 0..n {
                cnt += y[i + k].to_digit(10).unwrap();
                if x[i] != y[i + k] {
                    sum += 1;
                    if cnt == 0 {
                        p.push((left[i], right[(i + k) % n]));
                    }
                }
                cnt -= y[i].to_digit(10).unwrap();
            }
            if p.len() == 0 {
                ans = std::cmp::min(ans, sum);
                continue;
            }
            p.sort_by_key(|p| (n - p.0, p.1));
            let mut r = 0;
            for &(x, y) in &p {
                ans = std::cmp::min(ans, sum + 2 * x + 2 * r);
                r = std::cmp::max(r, y);
            }
            p.sort_by_key(|p| (n - p.1, p.0));
            let mut l = 0;
            for &(x, y) in &p {
                ans = std::cmp::min(ans, sum + 2 * y + 2 * l);
                l = std::cmp::max(l, x);
            }
        }
        x.reverse();
        y.reverse();
    }
    println!("{}", ans);
}

fn main() {
    run();
}


Measured memory_bytes: 4352
loop do
  n = gets.to_i
  break if n.zero?

  a = []
  n.times do |i|
    a << gets.to_i
  end

  max = -Float::INFINITY
  n.times do |i|
    sum = 0
    a[i..-1].each do |_a|
      sum += _a
      max = sum if sum > max
    end
  end

  puts max
end

Measured memory_bytes: 8784
#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 MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
using P = pair<int,int>;

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

int main()
{
  int H,W;
  cin >> H >> W;

  vector<string> A(H);
  REP(i, H) cin >> A[i];
  
  
  int flag = 0;
  REP(i,H){
    REP(j,W){
      if(i==0&&j==0){
        if(A.at(0).at(1)=='#'&&A.at(1).at(0)=='#'){
          flag = 1;
        }
        continue;
      }
      if(i==H-1&&j==W-1){
        if(A.at(H-1).at(W-2)=='#'&&A.at(H-2).at(W-1)=='#'){
          flag = 1;
        }
        continue;
      }
      if(A.at(i).at(j)=='#'){
        //xは左上の#の数、yは右下の#の数
        int x = 0;
        int y = 0;
        REP(k,4){
          if(i+dy[k]<0||i+dy[k]>H-1||j+dx[k]<0||j+dx[k]>W-1) continue;
          if(A.at(i+dy[k]).at(j+dx[k])=='#'){
            if(k<2){
              y++;
            }else{
              x++;
            }
          }
        }
        if(x!=1||y!=1){
          flag=1;
        }
      }
    }
  }

  if(flag == 1){
    cout << "Impossible" << endl;
  }else{
    cout << "Possible" << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 vector <int> a;
//int a[N];
int main(){
   int n;
   cin>>n;
   for (int i=0;i<n;i++){
	   int t;
       scanf("%d",&t);
	   a.push_back(t); 
	}
       bool f=1;
//    for (int i=0;i<n-1;i++) {
//	
//       if (a[i]-a[i+1]>1) {		  
//		  f=0;
//		  break;
//	   }
//        else if((a[i]-a[i+1]==1))
//           a[i]--; 
//	}
      for(int i=n-1;i>0;i--){
	  
         if (a[i-1]-a[i]>1)
             {
             	f=0;
             	break;
			 }
		  else if (a[i-1]-a[i]==1)
		      a[i-1]--;
		}  
    if (f==1)
       cout<<"Yes"<<endl;
	else 
	   cout<<"No"<<endl;   
  
   return 0;
}


Measured memory_bytes: 892
l=list(input())
keta=len(l)
i=0
S=[0]*keta
while i<keta:
    if i==0:
        S[i]=int(l[-1])
    else:
        a=10**i
        for j in range(i):
            a=a+(2**(i-1-j))*(10**j)
        S[i]=2*S[i-1]+int(l[-(i+1)])*a
    i=i+1
print(S[-1])


Measured memory_bytes: 3316