akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>

#define LL long long

using namespace std;
const int maxn=2*123456;
struct he{
    LL x,y,vx,vy;
    LL val;
}edge[maxn];
int n,m;
vector<LL> V;
int k;

int a,b,c;
map<LL,int> M;
bool cmp(he a,he b){
    ///if(a.val!=b.val)return a.val<b.val;
    if(a.vx!=b.vx)return a.vx<b.vx;
    return a.vy>b.vy;
}
char ch[55];
int ai[55][55];
int row[]={1,-1,0,0};
int col[]={0,0,1,-1};
int main(){
    
   // cout<<LONG_LONG_MAX<<endl;
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(ai,0,sizeof(ai));
        for(int i=1;i<=n;i++){
            scanf("%s",ch+1);
            for(int j=1;j<=m;j++){
                if(ch[j]=='#')ai[i][j]=1;
            }
        }
        bool ans=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(ai[i][j]==0)continue;
                bool flag=0;
                for(int k=0;k<4;k++){
                    if(ai[i+row[k]][j+col[k]]==1){
                        flag=1;
                        break;
                    }
                }
                if(flag)continue;
                ans=0;
                break;
            }
            
        }
        if(ans)printf("Yes\n");
        else printf("No\n");
    }
    
    
    return 0;
}


Measured memory_bytes: 256
def myAnswer(N:int,A:list,B:list) -> str:
   dic = {}
   for a,b in  zip(A,B):
      if(b in dic.keys()):
         dic[b].append(a)
      else:
         dic[b] = [a]
   now = 0
   dic = sorted(dic.items())
   for deadline,time in dic:
      time.sort()
      # print(deadline,time)
      for t in time:
         if(deadline < now + t):
            return "No"
         now += t
   return "Yes"

def modelAnswer():
   return
def main():
   N = int(input())
   A = []
   B = []
   for _ in range(N):
      a,b = map(int,input().split())
      A.append(a)
      B.append(b)
   print(myAnswer(N,A,B))
if __name__ == '__main__':
   main()

Measured memory_bytes: 64644
mod io{
    use std::io::*;
    pub fn read<T: ::std::str::FromStr>()->T{
        let stdin=stdin();
        let ret=stdin.lock().bytes().map(|c|c.unwrap()as char)
        .skip_while(|c|c.is_whitespace())
        .take_while(|c|!c.is_whitespace())
        .collect::<String>().parse().ok().unwrap();
        ret
    }
}
use io::read;
fn main(){
    let mut c=0;
    for a in read::<String>().as_bytes(){
    	if *a as char=='+'{c+=1}else{c-=1}
    }
    println!("{}",c)
}


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

int H, W;
char maze[10][10];

int main() {
	cin >> H >> W;
	int sum = 0;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> maze[i][j];
			if (maze[i][j] == '#')sum++;
		}
	}
	cout << (sum == H + W - 1 ? "Possible" : "Impossible") << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int maxn=1e6+5;
int main() {
	cout<<setiosflags(ios::fixed)<<setprecision(12);
    int xs,ys,xt,yt,n;cin>>xs>>ys>>xt>>yt>>n;
    vector<vector<pair<int,ld>>> edge(n+10);
    vector<pair<pii,int>> cir;
    cir.push_back({{ys,xs},0});
    cir.push_back({{yt,xt},0});
    auto pdis =[&](const pii& a,const pii&b) ->ld{
    	return sqrt(((ld)a.first-b.first)*(a.first-b.first)+(ld)(a.second-b.second)*(a.second-b.second)) ;
    };
    auto dis =[&](const pair<pii,int>& a,const pair<pii,int>& b)->ld {
    	ld pd=pdis(a.first,b.first);
    	return max((ld)0,pd-a.second-b.second);
    };
    for(int i=1;i<=n;i++) {
    	int x,y,r;cin>>x>>y>>r;
    	cir.push_back({{y,x},r});
    }
    for(int i=0;i<=n+1;i++) {
    	for(int j=i+1;j<=n+1;j++) {
    		ld ds=dis(cir[i],cir[j]);
    		edge[i].push_back({j,ds});
    		edge[j].push_back({i,ds});
    	}
    }
    vector<ld> ans(n+10,1e18);
    vector<bool> vis(n+10);
    auto dijkstra =[&](){
    	priority_queue<pair<ld,int>,vector<pair<ld,int>>,greater<pair<ld,int>>> PQ;
    	PQ.emplace(0,0);
    	while(!PQ.empty()) {
    		ld ds=PQ.top().first,u=PQ.top().second;PQ.pop();
    		if(vis[u]) continue;vis[u]=1;ans[u]=ds;
    		for(auto e:edge[u]) {
    			int v=e.first;
    			if(vis[v]||ans[v]<ans[u]+e.second) continue;
    			PQ.emplace(ans[u]+e.second,v);
    		}
    	}
    };
    dijkstra();
    cout<<ans[1]<<endl;
    return 0;
}

Measured memory_bytes: 52356
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#include<cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<char,int>;

const ll MOD = INF + 7;


int main(){
   int n;
   cin >> n;
   vector<ll> a(n), b(n);
   ll suma = 0, sumb = 0;
   rep(i, n){
      cin >> a[i];
      suma += a[i];
   }
   bool f = true;
   rep(i, n){
      cin >> b[i];
      if(a[i] != b[i])f = false;
      sumb += b[i];
   }
   ll man = sumb - suma;
   if(man < 0){
      cout << "No" << endl;
      return 0;
   }
   else if(man == 0){
      cout << (f ? "Yes" : "No") << endl;
      return 0;
   }
   else {

      ll cnta = man, cntb = man;
      rep(i, n){
         ll diff = b[i] - a[i];
         if(diff > 0){
            cnta -= (diff + 1) / 2;
            a[i] += (((diff + 1) / 2) * 2);
            if(cnta <= 0)break;
         }
      }
      rep(i, n){
         ll diff = a[i] - b[i];
         if(diff > 0){
            cntb -= diff;
            b[i] += diff;
            if(cntb <= 0)break;
         }
      }

      bool g = true;
     if(cnta < 0 || cntb < 0)g = false;
      rep(i, n){
         if(a[i] != b[i])g = false;
      }
      if(g && cntb == 2 * cnta){
         cout << "Yes" << endl;
      }
      else cout << "No" << endl;
   }
}

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

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

        String[] in = br.readLine().split(" ");
        int n = Integer.parseInt(in[0]);
        int w = Integer.parseInt(in[1]);
        int[] vi = new int[n];
        int[] wi = new int[n];
        for(int i = 0; i < n; i++) {
            in = br.readLine().split(" ");
            vi[i] = Integer.parseInt(in[0]);
            wi[i] = Integer.parseInt(in[1]);
        }

        int[][] dp = new int[n + 1][w + 1];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j <= w; j++) {
                if(j >= wi[i]) dp[i + 1][j] = Math.max(dp[i][j], dp[i + 1][j - wi[i]] + vi[i]);
                else dp[i + 1][j] = dp[i][j];
            }
        }

        System.out.println(dp[n][w]);

        br.close();
    }
}


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

typedef unsigned long long  ULL;
typedef long long LL;

#define PB push_back
#define MP make_pair
#define RESET(a, b) memset(a, b, sizeof(a))
#define FOR(i,a,b) for(int i=a; i<=b; i++)
#define F first 
#define S second

 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int k,n;
    cin>>k>>n;
    int a[n];
    FOR(i,0,n-1) cin>>a[i];
/*    
    LL ans1= *max_element(a, a+n)- *min_element(a, a+n);
    int key;
    FOR(i,0,n-1){
        if(a[i]>n/2){
            key=i-1;
            break;
        }
    }
    LL ans2=a[key]+k-a[key+1];
    if(ans1<=ans2) cout<<ans1;
    else cout<<ans2;*/
    int b[n];
    FOR(i, 0, n-1){
        if(i==0) b[i]=a[n-1]-a[i];
        else b[i]=a[i-1]+k-a[i];
    }
    cout<<*min_element(b, b+n);
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int main(void){
    string s;
    cin >> s;
    int a = (s[0] - '0')*10 + (s[1] - '0');
    int b = (s[2] - '0')*10 + (s[3] - '0');
    bool YYMM = (1<=b && b<=12);
    bool MMYY = (1<=a && a<=12);
    if(YYMM){
        if(MMYY) puts("AMBIGUOUS");
        else puts("YYMM");
    }else{
        if(MMYY) puts("MMYY");
        else puts("NA");
    }
}


Measured memory_bytes: 256
# include <bits/stdc++.h>
using namespace std;
# define MOD 1000000007
typedef long long ll;
bool compare(pair<ll, ll> a, pair<ll, ll> b){
    return a.first + a.second < b.first + b.second;
}
ll inverse[200001];
ll factorial[200001];
ll power(ll x, ll e){
    if(e == 0) return 1;
    ll y = power(x, e/2);
    if(e%2 == 0){
        return (y*y)%MOD;
    }else{
        return (x*((y*y)%MOD))%MOD;
    }
}
ll inv(ll x){
    return power(x, MOD - 2);
}
ll getWays(ll x1, ll y1, ll x2, ll y2){
    return ((factorial[x2 - x1 + y2 - y1]*inverse[x2 - x1])%MOD*inverse[y2 - y1])%MOD;
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    
    factorial[0] = 1;
    inverse[0] = inv(factorial[0]);
    for(int i=1;i<200001;i++){
        factorial[i] = (i*factorial[i-1])%MOD;
        inverse[i] = inv(factorial[i]);
    }
	int h, w, n;
	cin>>h>>w>>n;
	pair<ll, ll> blocks[n];
	for(int i=0;i<n;i++){
	    cin>>blocks[i].first>>blocks[i].second;
	}
	sort(blocks, blocks + n, compare);
	ll ans = getWays(1, 1, h, w);
	ll dp[n];
	for(int i=0;i<n;i++){
	    ll x = getWays(1, 1, blocks[i].first, blocks[i].second);
	    ll y = getWays(blocks[i].first, blocks[i].second, h, w);
	    for(int j=i-1;j>=0;j--){
	        if(blocks[i].first >= blocks[j].first and blocks[i].second >= blocks[j].second){
	            x = (x - (dp[j]*getWays(blocks[j].first, blocks[j].second, blocks[i].first, blocks[i].second))%MOD + MOD)%MOD;
	        }
	    }
	    dp[i] = x;
	    ans = (ans - (x*y)%MOD + MOD)%MOD;
	}
	cout<<ans;
	return 0;
}

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

signed main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k; cin >> n >> k;
    vector<int> h(n);
    rep(i,n) cin >> h[i];
    sort(h.begin(), h.end());
    rep(i,k) h.pop_back();
    int sum = 0;
    rep(i,h.size()) sum += h[i];
    cout << sum << endl;
    return 0;
}

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

int main() {
	long long int T, N, temp[10][100100], temp2 = 0, ans = 0, i, j = 0, tempT, temp3 = 0;

	cin >> T >> N;

	for (i = 0; i < N; i++) {
		cin >> temp[0][i] >> temp[1][i];
	}


	for (i = 0; i < N; i++) {
		tempT = temp[0][i] + T; 
		if (i != 0) { ans -= temp[1][i - 1] - temp[0][i - 1] + temp3;}

		while (j < N && temp[1][j] <= tempT) {
			ans += temp[1][j] - temp[0][j];
			j++;
		}
		if (j < N && temp[0][j] <= tempT) {
			temp3 = tempT - temp[0][j]; 
			ans += temp3;
		}
		else temp3 = 0;
		temp2 = max(temp2, ans);
	}
	cout << temp2 << endl;

	//cin >> T;


	return 0;
}


Measured memory_bytes: 4648
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

class Point {
public:
    int x, y;
    Point(int a = 0, int b = 0)
    {
        int x = a;
        int y = b;
    };
    bool operator <(const Point& p) const {
        return y < p.y || (y == p.y && x < p.x);
    }
};

inline bool direct(Point& base, Point& a, Point& b) {
    return (a.x - base.x)*(b.y - base.y) - (a.y - base.y)*(b.x - base.x) < 0;
}


int main() {
    int n, i;
    int k = 2;
    Point* P;
    Point* H;
    scanf("%d", &n);
    P = new Point[n];
    for (i = 1; i <= n; ++i) {
        scanf("%d%d",&P[i - 1].x, &P[i - 1].y);
    }
    sort(P, P + n);
    H = new Point[2*n];
    H[0] = P[0];
    H[1] = P[1];
    for (i = 0; i < n - 2; ++i) {
        while (k >= 2 && direct(H[k - 2],H[k - 1],P[i + 2])) k--;
        H[k++] = P[i + 2];
    }
    H[k++] = P[n - 2];
    for (i = n; i > 2; i--) {
        while (k >= 2 && direct(H[k - 2],H[k - 1],P[i - 3])) k--;
        H[k++] = P[i - 3];
    }
    printf("%d\n", k - 1);
    for (i = 0; i < k - 1; ++i) {
        printf("%d %d\n", H[i].x, H[i].y);
    }
    return 0;
}

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

int main(void){
    int N = 0;
    scanf("%d", &N);
    int d[100] = {0};
    for(int i = 0; i < N; i++){
        scanf("%d", &d[i]);
    }
    int height = 0; int max = 0;
    qsort(d, N, sizeof(int), compare_int);
    for(int i = 0; i < N; i++){
        if(max < d[i]){
            max = d[i];
            height++;
        }
    }
    printf("%d\n", height);
    return 0;
}

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

int main(void){
    int N;

    scanf("%d",&N);

    if(N%2 == 0){ 
        printf("%d\n",N/2);
    }else{
        printf("%d\n",N/2+1);
    }   
    
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
 
int main(){
  int k, s_len;
  string s;
  cin >> k >> s;
  s_len = (int)(s.length());
  if(s_len > k){
	  cout << s.substr(0, k) << "..." << endl;
  }else{
	  cout << s << endl;
  }
}

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

const int maxn = 1e7+10;

int prime[maxn];
bool is_prime[maxn];

int sieve(const int& n){
	int p = 0;
	fill(is_prime,is_prime+n+1,true);
	is_prime[0] = is_prime[1] = false;

	for(int i=2; i<=n; i++){
		if(is_prime[i]){
			prime[p++] = i;
			for(int j=2*i; j<=n; j+=i){
				is_prime[j] = false;
			}
		}
	}

	return p;
}

int main(){
	int n;
	while(cin>>n){
		cout << sieve(n) << endl;
	}
}

Measured memory_bytes: 4284
package main

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

func main() {
	sc = initScanner(os.Stdin)
	a, b, c, d, e := scanInt(sc), scanInt(sc), scanInt(sc), scanInt(sc), scanInt(sc)
	fmt.Println(resolve(a, b, c, d, e))
}

func resolve(a, b, c, d, e int) int {
	s := []int{a, b, c, d, e}

	index, max := 0, 0
	for i := 0; i < 5; i++ {
		tmp := s[i] % 10

		if tmp != 0 {
			tmp = 10 - tmp
		}

		if max < tmp {
			max = tmp
			index = i
		}
	}

	total := 0
	for i:=0; i<5; i++ {
		if i != index {
			tmp := s[i] % 10
			if tmp != 0 {
				total += 10-tmp
			}
		}
		total += s[i]
	}

	return total
}

// --------------- BASE DEFINITIONS ---------------

const (
	initialBufSize = 100000
	maxBufSize     = 1000000
)

var sc *bufio.Scanner

func initScanner(r io.Reader) *bufio.Scanner {
	buf := make([]byte, initialBufSize)

	sc := bufio.NewScanner(r)
	sc.Buffer(buf, maxBufSize)
	sc.Split(bufio.ScanWords)
	return sc
}

func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func scanIntSlice(sc *bufio.Scanner, n int) []int {
	is := make([]int, n)
	for i := 0; i < n; i++ {
		is[i] = scanInt(sc)
	}

	return is
}

func scanString(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 1780
N,K = map(int,input().split())
TD = [[int(x) for x in input().split()] for _ in range(N)]
TD.sort(key = lambda x: x[1], reverse=True)

T = 0
neta = set()
doublecounts = []
ans = []

for i in range(K):
    T += TD[i][1]    
    if not(TD[i][0] in neta):    
        neta.add(TD[i][0])       
    else:      
        doublecounts.append(TD[i][1])    
            
ans.append(T+len(neta)**2)

for i in range(K,N):
    if(len(doublecounts)==0):
        break
    if not(TD[i][0] in neta):
        T -= doublecounts.pop(-1)
        T += TD[i][1]
        neta.add(TD[i][0])   
        ans.append(T+len(neta)**2)
print(max(ans))


Measured memory_bytes: 24128
# ABC129C - Typical Stairs
import sys
input = sys.stdin.readline

def main():
    N, M = tuple(map(int, input().rstrip().split()))
    A = set(map(int, [input().rstrip() for _ in range(M)]))
    MOD = 10 ** 9 + 7
    dp = [0] * (N + 1)
    dp[:2] = 1, 1 if 1 not in A else 0
    for i in range(2, N + 1):
        if i in A:
            continue
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
    print(dp[-1])


if __name__ == "__main__":
    main()

Measured memory_bytes: 18336
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

h,w,k,*hwk = map(int,read().split())
it = iter(hwk)
b = [[0]*w for _ in range(h+1)]
for hi,wi,ki in zip(it,it,it):
    b[hi-1][wi-1] = ki

dp = [[0]*4 for _ in range(w)]
for i in range(h):
    ndp = [[0]*4 for _ in range(w)]
    for j in range(w):
        if j != 0:
            ndp[j] = ndp[j-1][:]
        ndp[j][0] = max(ndp[j][0],max(dp[j]))
        
        
        for k in range(3,0,-1):
            ndp[j][k] = max(ndp[j][k],ndp[j][k-1]+ b[i][j])
        

    dp = ndp

print(max(dp[-1]))

#print(dp)







Measured memory_bytes: 225244
def main():
    n = int(input())
    pp = []
    for _ in range(n):
        pp.append(int(input()))
    dd = {}
    for i in range(n):
        dd[pp[i]] = i

    xx = [-1] * n
    for s in range(n - 1, -1, -1):
        if xx[s] >= 0:
            continue
        count = 1
        pre = pp[s]
        while pre + 1 in dd and dd[pre + 1] > s:
            i = dd[pre + 1]
            if xx[i] >= 0:
                xx[s] = xx[i] + count
                break
            pre += 1
            count += 1
        else:
            xx[s] = count
    print(n - max(xx))


if __name__ == '__main__':
    main()


Measured memory_bytes: 86744
// Try AtCoder
//author: Leonardone @ NEETSDKASU

fn main() {
	let mut stdin = String::new();
    std::io::Read::read_to_string(
    	&mut std::io::stdin(),
        &mut stdin).unwrap();
    let mut stdin = stdin.split_whitespace();
    let mut get = || stdin.next().unwrap();
    macro_rules! get {
    	($t:ty) => (get().parse::<$t>().unwrap());
        () => (get!(i64));
    }
    
    let x = get!();
    
    if x == 3 || x == 5 || x == 7 {
    	println!("YES");
    } else {
    	println!("NO");
    }
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define REP(i,N) for(i=0;i<N;i++)
#define INF 1e9
typedef long long ll;

int main(void){
  int i,N;
  string S;
  cin >> N;
  cin >> S;
  vector<int> w(N);
  vector<int> b(N);
  int x=0;
  REP(i,N){
    b[i] = x;
    if(S[i]=='#')x++;
  }
  x=0;
  for(i=N-1;i>=0;i--){
    w[i] = x;
    if(S[i] =='.')x++;
  }
  int min = 1e9;
  REP(i,N){
    if(min>w[i]+b[i])min=w[i]+b[i];
  }
  cout << min << endl;
  return 0;
}


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

using namespace std;

#define PAD(n, d) ((n+d-1)/d)

int main(int argc, char* argv[])
{
  int N, D; cin >> N >> D;
  cout << PAD(N, (2*D+1)) << endl;
  return 0;
}


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

inline void prnt(string msg="No") {
    cout << msg << "\n";
    exit(0);
}

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

    int n;
    cin >> n;
    vector<int> v(n);
    for(int i=0; i<n; ++i) cin >> v[i];

    sort(v.begin(), v.end());
    if(v.front() == v.back()) {
        if(n == v.front()+1) prnt("Yes");
        else if(n < 2*v.front()) prnt();
        else prnt("Yes");
    }
    else {
        int cnt = count(v.begin(), v.end(), v.front());
        if(cnt > v.front()) prnt();
        else {
            int c = v.back() - cnt;
            int ncnt = n - cnt;
            if(ncnt < 2 * c) prnt();
            else prnt("Yes");
        }
    }

    return 0;
}


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

#include <iostream>
#include <fstream>

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <bitset>
using namespace std;
using ll = long long;
constexpr ll INF = 1010000000000000017LL;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define all(v) v.begin(), v.end()

ll GCD(ll a, ll b) { if(b==0) return a; else return GCD(b, a%b); }
ll LCM(ll a, ll b) { return a/GCD(a,b)*b; }

class BBounding {
public:
	void solve(std::istream& in, std::ostream& out) {
        int n,x;in>>n>>x;
        int d = 0;
        vector<ll> l(n);
        rep(i,n) in>>l[i];

        int j;
        for (j = 1;  d <= x && j-1 < n; ++j) {
            d += l.at(j-1);
//            out<<d<<endl;
        }
        if(d<=x) out<<j<<endl;
        else out<<j-1<<endl;
	}
};


int main() {
	BBounding solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using st = string;
using P = pair<int, int>;
#define mrep(i, m, n) for(int i = m; i < n; i++)
#define rep(i, n) mrep(i, 0, n)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

const int mod = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    vector<ll> dp(n + 1);
    dp.at(0) = 1;
    ll sm = 0;
    mrep(i, 1, n + 1){
        if(i >= 3){
            sm = (sm + dp.at(i - 3)) % mod;
        }
        dp.at(i) = sm % mod;
    }
    cout << dp.at(n) << endl;
    return 0;
}

Measured memory_bytes: 3592
/*********************
*  Author: xuziyuan  * 
*********************/

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

using namespace std;

LL n,ans=0;

int main()
{
  cin>>n;
  LL tmp=n,nw=0,firn=n;
  while(firn>9) firn/=10;
  while(tmp>0)
  {
    tmp/=10;
    nw++;
  }
  repn(i,n)
  {
    LL fir=i%10,lst=i;
    if(fir==0) continue;
    while(lst>9) lst/=10;
    if(fir==lst) ans++;
    if(fir*10+lst<=n) ans++;
    repn(j,4) if(j<nw-2) ans+=(LL)pow(10,j);
    if(nw>2)
    {
      if(fir<firn) ans+=(LL)pow(10,nw-2);//cout<<fir<<' '<<firn<<endl;
      else if(fir==firn)
      {
      	//cout<<i<<' '<<ans<<' ';
        LL val=n/10-firn*pow(10,nw-2)+1;//if(i==2) cout<<ans<<endl;
        ans+=val;//if(i==2) cout<<firn*pow(10,nw-1)<<' '<<n/10<<' '<<ans<<endl;
        if(lst>n%10) ans--; //cout<<ans<<endl;
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define ppb pop_back()
#define fi first
#define se second
#define pi pair<int, int>
#define rep(i, a, n) for(int i = a; i <= n; i++)
#define REP(i, a, n) for(int i = a; i < n; i++)
#define Y "Yes"
#define N "No"
using namespace std;

ll k, n;
int ans;
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> k;
	
	if (k % 7 == 0) k /= 7;
	bool b[k];
	REP(i, 0, k) b[i] = 0;
	
	rep(i, 1, k) {
		n = (n * 10 + 1) % k;
		if (n == 0) {
			ans = i;
			break;
		} else if (b[n]) {
			break;
		} else {
			b[n] = 1;
		}
	}
	if (ans) cout << ans;
	else cout << -1;
}

Measured memory_bytes: 4604
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = ll(1e18) + 5;

struct UnionFind {
    vector<int> d;
    UnionFind(int n = 0) : d(n, -1) {}
    int find(int x) {
        if (d[x] < 0) return x;
        return d[x] = find(d[x]);
    }
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (d[x] > d[y]) swap(x, y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return -d[find(x)]; }
};

int main() {
    ll N, M;
    cin >> N >> M;
    UnionFind uf = UnionFind(N);
    for (int i = 0; i < M; i++) {
        ll a, b;
        cin >> a >> b;
        --a;
        --b;
        uf.unite(a, b);
    }
    int ans = 0;
    for (int i = 0; i < N; i++) {
        ans = max(ans, uf.size(i));
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4028
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
//const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
const int dx[8]={-1,0,1,0,-1,-1,1,1},dy[8]={0,-1,0,1,-1,1,-1,1};

const int N=16;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	while(1){
		char c;
		cin>>c;
		if(c=='#') break;
		vector<vs> a(4,vs(13));
		for(int i=0;i<4;i++) for(int j=0;j<13;j++) cin>>a[i][j];
		int p=0,q=0;
		int pre=0;
		for(int i=0;i<13;i++){
			int mx=-1,id=0;
			for(int j=0;j<4;j++){
				int x=0;
				char t=a[j][i][0];
				if(isdigit(t)) x=t-'2';
				if(t=='T') x=9;
				if(t=='J') x=10;
				if(t=='Q') x=11;
				if(t=='K') x=12;
				if(t=='A') x=13;
				t=a[j][i][1];
				if(t==c) x+=10000;
				if(t==a[pre][i][1]) x+=1000;
				if(x>mx){
					mx=x;
					id=j;
				}
			}
			pre=id;
//			cout<<id<<' ';
			if(id%2==1) p++;
			else q++;
		}
//		cout<<endl;
		if(p>q){
			cout<<"EW"<<' '<<p-6<<endl;
		}
		else{
			cout<<"NS"<<' '<<q-6<<endl;
		}
	}
}


Measured memory_bytes: 3148
X,Y = map(int,input().split())
ans = 0
if X <= 3:
    ans += [300000, 200000, 100000][X-1]
if Y <= 3:
    ans += [300000, 200000, 100000][Y-1]
if X==Y==1:
    ans += 400000

print(ans)


Measured memory_bytes: 2940
#include <iostream>

using namespace std;

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


Measured memory_bytes: 888
#include <bits/stdc++.h>
#define ll long long
#define MAX 1000005
using namespace std;
ll n, m, i ,j ,k ,l, ans, tmp, res;
ll arr[MAX], brr[MAX];
vector<ll> v;
string s;
map<ll,ll> mp;
int main()
{
	
		cin>>n;
		for(i=0;i<n;i++)
		{
			cin>>arr[i];
			if(mp[arr[i]])continue;
			mp[arr[i]]=1;
			ans++;
		}
		cout<<ans;
	
return 0;
}
 

Measured memory_bytes: 2304
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<int> VI;
const ll MOD = 1000000007;
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()
int main() {
	int a, b;
	cin >> a >> b;
	if ((a + b) % 2)
		cout << "IMPOSSIBLE";
	else
		cout << (a + b) / 2;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
	int a,b,c,d;
	char str[21];
	while(~scanf("%s",&str))
	{
		for(int i=0;i<19;i++)
		{
			if(i==5||i==13) cout<<" ";
			else cout<<str[i];
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#pragma warning (disable: 4996)
using namespace std;

int N, P, Q, A[1 << 18], B[1 << 18], C[1 << 18], D[1 << 18];
vector<int> X[1 << 18], Y[1 << 18];

int col[1 << 18], group[1 << 18], cnts;

void dfs(int pos) {
	col[pos] = cnts;
	group[cnts]++;
	for (int i : X[pos]) {
		if (col[i] >= 1) continue;
		dfs(i);
	}
}

int main() {
	cin >> N >> P >> Q;
	for (int i = 1; i <= P; i++) {
		cin >> A[i] >> B[i];
		X[A[i]].push_back(B[i]);
		X[B[i]].push_back(A[i]);
	}
	for (int i = 1; i <= Q; i++) {
		cin >> C[i] >> D[i];
		Y[C[i]].push_back(D[i]);
		Y[D[i]].push_back(C[i]);
	}
	for (int i = 1; i <= N; i++) {
		if (col[i] >= 1) continue;
		cnts++; dfs(i);
	}
	for (int i = 1; i <= N; i++) {
		if (i >= 2) cout << " ";
		int current = group[col[i]] - 1;
		map<int, int> Map;
		for (int j : X[i]) {
			if (col[i] == col[j] && Map[j] == 0) { current--; Map[j] = 1; }
		}
		for (int j : Y[i]) {
			if (col[i] == col[j] && Map[j] == 0) { current--; Map[j] = 1; }
		}
		cout << current;
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 28536
import java.util.Scanner;

public class Main {

	static int count = 0;
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++)
        	a[i] = sc.nextInt();
        mergeSort(a, 0, n);

        System.out.print(a[0]);
        for (int i = 1; i < n; i++) {
            System.out.print(" " +a[i]);
        }
        System.out.println();
        System.out.println(count);
	}

	static void mergeSort(int[] a, int left, int right) {
		if(left + 1 < right) {
			int mid = (left + right) / 2;
			mergeSort(a, left, mid);
			mergeSort(a, mid, right);
			merge(a, left, mid, right);
		}
	}

	static void merge(int[] a, int left, int mid, int right) {
		int n1 = mid - left;
		int n2 = right - mid;
		int[] L = new int[n1 + 1];
		int[] R = new int[n2 + 1];

		for(int i = 0; i < n1; i++) {
			L[i] = a[left + i];
		}
		for(int i = 0; i < n2; i++) {
			R[i] = a[mid + i];
		}

		L[n1] = Integer.MAX_VALUE;
		R[n2] = Integer.MAX_VALUE;

		int l = 0;
		int r = 0;
		for(int k = left; k < right; k++) {
			count++;
			if(L[l] < R[r]) {
				a[k] = L[l];
				l++;
			}
			else {
				a[k] = R[r];
				r++;
			}
		}
	}
}



Measured memory_bytes: 170048
#include <cstdio>
#include <queue>
#include <algorithm>
#define maxn 200005
using namespace std;

int a[maxn], n;

struct Position
{
	int lf, rf, comfort;
	inline Position(int l, int r)
	{
		lf = l, rf = r;
		comfort = min(l, r);
	}
	inline bool operator<(const Position& p) const
	{
		return comfort < p.comfort;
	}
};

priority_queue<Position> q;

inline bool cmp(int x, int y) {return x > y;}

int main(int argc, char** argv)
{
	scanf("%d", &n);
	for(int i=0; i<n; i++)
		scanf("%d", a + i);
	sort(a, a + n, cmp);
	q.push(Position(a[0], a[1]));
	long long res = a[0];
	for(int i=2; i<n; i++)
	{
		Position p = q.top();
		if(q.size() > 1) q.pop();
		res += p.comfort;
		q.push(Position(a[i], p.lf));
		q.push(Position(a[i], p.rf));
	}
	printf("%lld\n", res);
	return 0;
}


Measured memory_bytes: 6628
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>

using namespace std;

int n, m;
int a[51], b[51];
int hen[51][51];
//bool hen[50][50];
bool tyo[51];
bool tyo2[51];

struct MyStruct
{
	int reki[50];
}st;


int func(int ima, MyStruct stt, int cnt) {
	tyo[ima] = true;

	for (int i = 1; i <= 50; i++) {
		if (hen[ima][i] == 1) {
			if (tyo[i] == false) {
				hen[ima][i] = 2;
				hen[i][ima] = 2;
				stt.reki[cnt] = i;
				func(i, stt, cnt + 1);
			}
			else {
				for (int j = 0; j < cnt; j++) {
					if (stt.reki[j] == i) {
						for (int k = j; k < cnt; k++) {
							int toji = stt.reki[k];
							tyo2[toji] = true;
						}
					}
				}
			}
		}
	}

	return 0;
}

int main() {
	int i, j, k;
	int reki[50];
	
	fill(reki, reki + 50, 0);
	fill(tyo, tyo + 50, false);
	fill(tyo2, tyo2 + 50, false);
	fill((int*)hen, (int*)(hen + 50), -1);
	//fill((bool*)hen, (bool*)(hen + 50), false);

	cin >> n >> m;

	for (i = 0; i < m; i++) {
		cin >> a[i] >> b[i];
		int aa = a[i];
		int bb = b[i];
		hen[aa][bb] = 1;
		hen[bb][aa] = 1;
	}

	MyStruct stt;

	stt.reki[0] = 1;

	func(1, stt, 1);

	int tojihenCnt = 0;

	for (i = 0; i < m; i++) {
		if (tyo2[a[i]] == true && tyo2[b[i]] == true) {
			tojihenCnt++;
		}
	}


	cout << m - tojihenCnt << endl;

	




	getchar();
	getchar();
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define inf (int)(1e8)
using namespace std;

struct dat {
  int x, y, cost;
  dat(int _x, int _y, int c = 0) : x(_x), y(_y), cost(c) {}
};

bool operator<(const dat& l, const dat& r) { return l.cost > r.cost; }

using P = pair<int, int>;
int h, w, sx, sy, gx, gy;
vector<string> s;
vector<vector<int>> dist;
int d[4] = {0, 1, 0, -1};

int solve();
bool isvalid(int x, int y) {
  return x >= 0 && x < h && y >= 0 && y < w && s[x][y] == '.';
}

int main() {
  cin >> h >> w >> sx >> sy >> gx >> gy;
  --sx, --sy, --gx, --gy;
  dist.assign(h, vector<int>(w, inf));
  s.resize(h);
  for (auto& p : s) cin >> p;
  cout << solve() << endl;
  return 0;
}

int solve() {
  priority_queue<dat> pq;
  pq.push(dat(sx, sy, 0));
  dist[sx][sy] = 0;
  while (pq.size()) {
    auto [x, y, c] = pq.top();
    pq.pop();
    if (dist[x][y] != c) continue;

    for (int i = 0; i < 4; ++i) {
      int nx = x + d[i], ny = y + d[i ^ 1];
      if (!isvalid(nx, ny)) continue;
      if (dist[nx][ny] > c) {
        dist[nx][ny] = c;
        pq.push(dat(nx, ny, c));
      }
    }

    for (int i = -2; i <= 2; ++i)
      for (int j = -2; j <= 2; ++j) {
        int nx = x + i, ny = y + j;
        if (!isvalid(nx, ny)) continue;
        if (dist[nx][ny] > c + 1) {
          dist[nx][ny] = c + 1;
          pq.push(dat(nx, ny, c + 1));
        }
      }
  }
  if (dist[gx][gy] == inf) return -1;
  return dist[gx][gy];
}


Measured memory_bytes: 9496
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vs = vector<string>;
using vll = vector<long long>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vi h(n);
    rep(i, n) cin >> h[i];

    for (int i = n-1; i >= 0; --i) h[i] = h[i] - h[i-1];

    int ans = 0;
    rep(i, n) ans += max(0, h[i]);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef pair<int,int>pii;
struct edge{int to,next;}e[1000002];
int head[80002],low[80002],dfn[80002],scc[80002],tim,cnt,a[2][10002],n,cnte,tr[800002],tot;
pii lsh[80002];
stack<int> stk;
const int Mxdt=200000; 
inline char gc(){
	static char buf[Mxdt],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxdt,stdin),p1==p2)?-1:*p1++;
}
#define gc getchar
inline int read(){
	int res=0;char ch=gc();
	while(ch<'0')ch=gc();
	while(ch>='0')res=(res<<3)+(res<<1)+(ch^48),ch=gc();
	return res;
}
inline void add(int x,int y){
	e[++cnte]=(edge){y,head[x]};
	head[x]=cnte;
}
inline void build(int p,int l,int r){
	if(l==r){
		tr[p]=lsh[l].s;
		return;
	}
	tr[p]=++tot;
	int mid=l+r>>1;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r);
	add(tr[p],tr[p<<1]),add(tr[p],tr[p<<1|1]);
}
inline void add(int p,int l,int r,int x,int y,int v){
	if(x>y)return;
	if(l>=x&&r<=y){add(v,tr[p]);return;}
	int mid=l+r>>1;
	if(x<=mid)add(p<<1,l,mid,x,y,v);
	if(y>mid)add(p<<1|1,mid+1,r,x,y,v);
}
inline void tj(int x){
	stk.push(x);
	low[x]=dfn[x]=++tim;
	for(int i=head[x];i;i=e[i].next)
		if(!dfn[e[i].to]){
			tj(e[i].to);
			low[x]=min(low[x],low[e[i].to]);
		}
		else if(!scc[e[i].to])low[x]=min(low[x],dfn[e[i].to]);
	if(dfn[x]==low[x]){
		int p;++cnt;
		do{
			scc[p=stk.top()]=cnt;
			stk.pop();
		}while(p^x);
	}
}
inline bool check(int x){
	cnte=tim=cnt=0;
	memset(head,0,sizeof(head));build(1,1,tot=2*n);
	for(int i=1;i<=n;++i)
		for(int k=0;k<2;++k){
			int l=lower_bound(lsh+1,lsh+1+2*n,pii(a[k][i]-x+1,0))-lsh,r=upper_bound(lsh+1,lsh+1+2*n,pii(a[k][i]+x-1,2*n+1))-lsh-1,m=lower_bound(lsh+1,lsh+1+2*n,pii(a[k][i],(k^1)*n+i))-lsh;
			add(1,1,2*n,l,m-1,k*n+i);
			add(1,1,2*n,m+1,r,k*n+i);
		}
	while(!stk.empty())stk.pop();
	memset(dfn,0,sizeof(dfn)),memset(low,0,sizeof(low)),memset(scc,0,sizeof(scc));
	for(int i=1;i<=tot;++i)if(!dfn[i])tj(i);
	for(int i=1;i<=n;++i)if(scc[i]==scc[i+n])return 0;
	return 1;
}
int main(){
	n=read();
	for(int i=1;i<=n;++i)a[0][i]=read(),a[1][i]=read();
	for(int i=1;i<=n;++i)lsh[2*i-1].f=a[0][i],lsh[2*i-1].s=i+n,lsh[2*i].f=a[1][i],lsh[2*i].s=i;
	sort(lsh+1,lsh+1+2*n);
	int l=0,r=1e9,mid,ans=0;
	while(l<=r){
		mid=l+r>>1;
		if(check(mid))ans=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%d",ans);
}

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

int main(){
    while(1){
        int n,m;
        cin >> n >> m;
        if(n == 0) break;

        vector<int> p(n, 0);
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                int a;
                cin >> a;
                p[j] += a;
            }
        }
        cout << *max_element(p.begin(), p.end()) << endl;
    }
    return 0;
}



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

class state{
public:
  int n,a[2];
  bool f[1014];
};

int main(){
  int i,j,n,m;
  while(cin >> n >> m && n && m){
    int l[1001];
    for(i=0;i<n;i++) cin >> l[i];
    state u,v;
    queue<state> Q;
    bool ans = false;
    u.n = 0;
    u.a[1] = l[0];
    u.a[0] = m - l[0];
    Q.push(u);

    while(!Q.empty()){
      u = Q.front();
      Q.pop();

      if(u.n < n - 1){
	if(u.a[0] == 0 && u.a[1] == 0){
	  if(l[u.n+1] - l[u.n] == 1 && !u.f[u.n]){
	    v = u;
	    v.f[v.n+m] = 1;
	    v.n++;
	    Q.push(v);
	  }
	  else if(l[u.n+1] - l[u.n] == 0){
	    if(u.f[u.n]){
	      v = u;
	      v.f[v.n+m] = 1;
	      v.n++;
	      Q.push(v);
	    }
	    else{
	      v = u;
	      v.f[v.n+m] = 0;
	      v.n++;
	      Q.push(v);
	    }
	  }
	  else if(l[u.n+1] - l[u.n] == -1 && u.f[u.n]){
	    v = u;
	    v.f[v.n+m] = 0;
	    v.n++;
	    Q.push(v);
	  }
	}
	else{
	  if(l[u.n+1] - l[u.n] == 1 && u.a[0] > 0){
	    v = u;
	    v.f[v.n+m] = 1;
	    v.f[v.n] = 0;
	    v.a[0]--;
	    v.n++;
	    Q.push(v);
	  }
	  else if(l[u.n+1] - l[u.n] == 0){
	    if(u.a[1] > 0){
	      v = u;
	      v.f[v.n+m] = 1;
	      v.f[v.n] = 1;
	      v.a[1]--;
	      v.n++;
	      Q.push(v);
	    }
	    if(u.a[0] > 0){
	      v = u;
	      v.f[v.n+m] = 0;
	      v.f[v.n] = 0;
	      v.a[0]--;
	      v.n++;
	      Q.push(v);
	    }
	  }
	  else if(l[u.n+1] - l[u.n] == -1 && u.a[1] > 0){
	    v = u;
	    v.f[v.n+m] = 0;
	    v.f[v.n] = 1;
	    v.a[1]--;
	    v.n++;
	    Q.push(v);
	  }
	}
      }

      else{
	if(u.a[0] == 0 && u.a[1] == 0){
	  ans = true;
	  for(i=0;i<n+m-1;i++) cout << u.f[i];
	  cout << endl;
	  break;
	}
	else{
	  if(u.a[0] > 0){
	    v = u;
	    v.f[v.n] = 0;
	    v.a[0]--;
	    v.n++;
	    Q.push(v);
	  }
	  if(u.a[1] > 0){
	    v = u;
	    v.f[v.n] = 1;
	    v.a[1]--;
	    v.n++;
	    Q.push(v);
	  }
	}
      }
    }

    if(!ans) cout << "Goofy" << endl;
  }
  return 0;
}

Measured memory_bytes: 1132
#include<stdio.h>

long long Fibonacci(int);

long long ap[100];
int  main() {
  int h,i;

  for(i=0;i<100;i++)ap[i]=-1;

  scanf("%d",&h);
  printf("%d\n",Fibonacci(h));

  return 0;
}

long long Fibonacci(int x){
  if(x==0|| x==1)return ap[x]=1;
  if(ap[x]!=-1)return ap[x];
  return ap[x]=Fibonacci(x-1)+Fibonacci(x-2);
}



Measured memory_bytes: 2112
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define ALL(a) a.begin(), a.end()
ll dx[4] = { 0, 1, 0, -1 };
ll dy[4] = { 1, 0, -1, 0 };
const ll INF = 1e14;
const ll MOD = 1e9 + 7;
const ll len = 1e6 + 10;

bool is_prime[len];
ll ans = 0;
ll A, B;
int Eratosthenes(ll g)
{
    int res = 0;
    for (ll i = 2; i * i <= g; i++) {
        if (g % i != 0) {
            continue;
        }
        int num = 0;
        while (g % i == 0) {
            g /= i;
        }
        ++res;
    }
    if (g != 1) {
        ++res;
    }
    return res;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> A >> B;
    ll g = __gcd(A, B);
    ans = Eratosthenes(g);
    cout << ans + 1LL << endl;
    return 0;
}

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

using namespace std;

int main(){	
  int N;
  cin>>N;
  vector<int> v(N);
  int cnt=1;
  int res =0;
  for(int i=0;i<N; i++){
    cin>>v[i];
    if(i>0 ){
      if( v[i-1] != v[i])
      {
        res+=cnt/2;
        cnt =1;
      }
      else{
          
  		  cnt++;
          if(i==N-1) res+=cnt/2;
      }
    }
      
  }
  
  
  cout<<res;
}





Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

int a[205];
int sum,n,l,sum2=0x7fffffff,qwq;

int main() {
	
	scanf("%d%d",&n,&l);
	
	for(int i=1;i<=n;i++) a[i]=l+i-1,sum+=a[i];
	
	for(int i=1;i<=n;i++) {
		if(abs(sum-(sum-a[i]))<sum2) sum2=abs(sum-(sum-a[i])),qwq=sum-a[i];
	}
	printf("%d",qwq);	
}

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

int main(void)
{
    char S[4+1];
    int tmp=0;
    int flag=0;
    int i;

    fgets(S,4+1,stdin);
    tmp=atoi(S);

    if(tmp/100<=12&&tmp/100!=0){
        flag++;
    }
    if(tmp%100<=12&&tmp%100!=0){
        flag+=2;
    }

    if(flag==1){
        printf("MMYY");
    }else if(flag==2){
        printf("YYMM");
    }else if(flag==3){
        printf("AMBIGUOUS");
    }else{
        printf("NA");
    }

    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cout << #x << " = " << (x) << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//#define int long long

void solve() {
	ll n; cin >> n;
    int cnt = 0;
    ll n_ = n;
    int ma = 0, sum = 0;;
    while(n_ > 0) {
        ma = n_ % 10;
        sum += ma;
        n_ /= 10;
        ++cnt;
    }
    cout << max(sum, ma - 1 + (cnt - 1) * 9) << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init();
	solve();
	//cout << "finish" << endl;
    return 0;
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
int main(){
	int x;
	cin>>x;
	int temp=x;
	int ans=0;
	ans+=(x%100)/5;
	x=(x%100-(x%100)/5*5);
	ans+=x/4;
	x=(x-x/4*4);
	ans+=x/3;
	x=(x-x/3*3);
	ans+=x/2;
	x=(x-x/2*2);
	ans+=x/1;
	if(ans>temp/100)cout<<0<<endl;
	else cout<<1<<endl;
} 

Measured memory_bytes: 256
import java.util.*;

public class Main {
    
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Color[] colors = new Color[n - 1];
		ArrayList<ArrayList<Color>> graph = new ArrayList<>();
		for (int i = 0; i < n; i++) {
		    graph.add(new ArrayList<>());
		}
		for (int i = 0; i < n - 1; i++) {
		    int a = sc.nextInt() - 1;
		    int b = sc.nextInt() - 1;
		    colors[i] = new Color(a, b);
		    graph.get(a).add(colors[i]);
		    graph.get(b).add(colors[i]);
		}
		paint(0, 0, 0, graph);
		StringBuilder sb = new StringBuilder();
		int max = 0;
		for (Color c : colors) {
		    sb.append(c.color).append("\n");
		    max = Math.max(max, c.color);
		}
		System.out.println(max);
		System.out.print(sb);
	}
	
	static class Color {
	    int left;
	    int right;
	    int color;
	    public Color(int left, int right) {
	        this.left = left;
	        this.right = right;
	    }
	    
	    public String toString() {
	        return left + ":" + right + ":" + color;
	    }
	}
	
	static void paint(int idx, int parent, int without, ArrayList<ArrayList<Color>> graph) {
	    int num = 0;
	    for (Color c : graph.get(idx)) {
	        int next;
	        if (c.left == idx) {
	            next = c.right;
	        } else {
	            next  = c.left;
	        }
	        if (next == parent) {
	            continue;
	        }
	        num++;
	        if (num == without) {
	            num++;
	        }
	        c.color = num;
	        paint(next, idx, num, graph);
	    }
	}
}


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

int main() {
	int N;
	cin >> N;
	vector<int> d(N);
	for (int n = 0; n < N; n++) {
		cin >> d.at(n);
	}
	sort(d.begin(), d.end());
	reverse(d.begin(), d.end());
	int answer = 1;
	for (int n = 1; n < N; n++) {
		if (d.at(n) < d.at(n - 1)) {
			answer++;
		}
	}
	cout << answer << endl;
}


Measured memory_bytes: 256
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque
H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
X = [1] * (W + 2)
for _ in range(H):
    X += [1] + [1 if a == "@" else 0 for a in input()] + [1]
X += [1] * (W + 2)
H, W = H+2, W+2
s, t = x1 * W + y1, x2 * W + y2

def BFS(i0=0):
    Q = deque([(i0, 3)])
    D = [-1] * (H * W)
    D[i0] = 0
    while Q:
        x, t = Q.popleft()
        if t & 1:
            for d in (1, -1):
                for y in range(x + d, x + d * K, d):
                    if X[y]: break
                    if 0 <= D[y] <= D[x]: break
                    D[y] = D[x] + 1
                    Q.append((y, 2))
                else:
                    y = x + d * K
                    if X[y] == 0:
                        if D[y] == -1:
                            D[y] = D[x] + 1
                            Q.append((y, 3))
        if t & 2:
            for d in (W, -W):
                for y in range(x + d, x + d * K, d):
                    if X[y]: break
                    if 0 <= D[y] <= D[x]: break
                    D[y] = D[x] + 1
                    Q.append((y, 1))
                else:
                    y = x + d * K
                    if X[y] == 0:
                        if D[y] == -1:
                            D[y] = D[x] + 1
                            Q.append((y, 3))
                        
    return D

print(BFS(s)[t])

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

int main(){

    map<ll,int> a;
    ll n;
    cin >> n;

    rep(i,n){
        ll t;
        cin >> t;
        a[t]++;
    }

    ll ans=0;

    for(auto itr=a.begin();itr!=a.end();itr++){
        if(itr->second%2!=0){
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 6528