akhauriyash/Code-Regression huggingface dataset:
N = int(input())
s = input()
t = input()

if s == t:
  print(N)
  exit(0)

cnt = 0
for i in range(N):
  tmp_s = s[i:]
  tmp_t = t if i == 0 else t[:-i]

  tmp_cnt = 0
  for j in range(len(tmp_s)):
    if tmp_s[j] == tmp_t[j]:
      tmp_cnt += 1

  cnt = max(cnt, tmp_cnt)

print(2 * N - cnt)


Measured memory_bytes: 63768
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using u128 = __uint128_t;

#define int long long
#define idxSet tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define atIdx find_by_order
#define idxOf order_of_key
#define MOD 1000000007
#define MAX 200005
#define endl '\n'

#define v(type) vector<type>
#define p(type1, type2) pair<type1 , type2>
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

int dp[MAX];

void solve() {
    string x;
    cin>>x;
    int n = x.size();
    int a[n];
    for(int i = 0 ; i< n ; ){
        if(x[i] == 'R'){
            int j = i + 1;
            while(x[j] != 'L'){
                j++;
            }
            for(int k = i ; k < j ; k++){
                a[k] = j;
            }
            i = j;
            continue;
        }else{
            i++;
        }
    }
    for(int i = n - 1; i >= 0 ; ){
        if(x[i] == 'L'){
            int j = i - 1;
            while(x[j] != 'R'){
                j--;
            }
            for(int k = i ; k > j ; k--){
                a[k] = j;
            }
            i = j;
            continue;
        }else{
            i--;
        }
    }
    int ans[n] ;
    memset(ans , 0 , sizeof(ans));
    for(int i = 0 ; i< n ; i++){
        if(x[i] == 'R'){
            if((a[i] - i ) % 2 == 0){
                ans[a[i]]++;
            }else {
                ans[a[i] - 1]++;
            }
        }else{
            if((i - a[i]) % 2 == 0){
                ans[a[i]]++;
            }else {
                ans[a[i] + 1]++;
            }
        }
    }
    for(int i = 0 ; i < n ; i++){
        cout<<ans[i]<<" ";
    }
    cout<<endl;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //cin>>t;
    while (t--)
        solve();
    return 0;
}

Measured memory_bytes: 2256
#![allow(unused)]

use cmp::Ordering::{Equal, Greater, Less};
use collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque};
use io::{Read, Write};
use std::{cmp, collections, fmt, io, iter, ops, str};

#[cfg(feature = "debug")]
macro_rules! debug {
    ($fmt: expr) => { eprintln!($fmt) };
    ($fmt: expr, $($args: tt)*) => { eprintln!($fmt, $($args)*) };
}

#[cfg(not(feature = "debug"))]
macro_rules! debug {
    ($fmt:expr) => {};
    ($fmt:expr, $($args:tt)*) => {};
}

macro_rules! vmax {
    ($x: expr, $y: expr) => { cmp::max($x, $y) };
    ($x: expr, $($args: expr),*) => { cmp::max($x, vmax!($($args),*)) };
}

macro_rules! vmin {
    ($x: expr, $y: expr) => { cmp::min($x, $y) };
    ($x: expr, $($args: expr),*) => { cmp::min($x, vmin!($($args),*)) };
}

fn main() {
    const MAX: i32 = 1000;

    let x = parse_line::<i32>();

    let mut is_pow = vec![false; MAX as usize + 1];
    is_pow[1] = true;

    for b in 2..(MAX + 1) {
        for p in (2..).take_while(|p| b.pow(*p) <= MAX) {
            is_pow[b.pow(p) as usize] = true;
        }
    }

    let ans = (1..(x + 1))
        .rev()
        .filter(|&i| is_pow[i as usize])
        .next()
        .unwrap();
    println!("{}", ans);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        //
    }
}

fn read_line() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().to_owned()
}

fn read_word() -> String {
    const CAPACITY: usize = 16;

    let mut stdin = io::stdin();
    let mut byte: [u8; 1] = [0];

    loop {
        let mut buf = Vec::with_capacity(CAPACITY);

        loop {
            let res = stdin.read(&mut byte);

            if res.unwrap_or(0) == 0 || byte[0] <= b' ' {
                break;
            } else {
                buf.push(byte[0]);
            }
        }

        if buf.len() > 0 {
            return String::from_utf8(buf).unwrap();
        }
    }
}

fn parse_line<T: str::FromStr>() -> T {
    read_line().parse().ok().unwrap()
}

fn parse_word<T: str::FromStr>() -> T {
    read_word().parse().ok().unwrap()
}

fn parse_vec<T: str::FromStr>() -> Vec<T> {
    read_line()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn flush() {
    io::stdout().flush();
}

fn next_prime(x: i32) -> i32 {
    for i in (x + 1).. {
        if is_prime(i) {
            return i;
        }
    }

    panic!("attempt to add with overflow");
}

fn is_prime(x: i32) -> bool {
    let ceil = (x as f64).sqrt().ceil() as i32;
    x == 2 || (2..(ceil + 1)).all(|i| x % i != 0)
}


Measured memory_bytes: 4352
// ABC177B.cpp 

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
    string s, t;
    cin >> s >> t;
    int ans = 1000;
    for (int i = 0; i <= s.length()-t.length(); i++) {
        string sp = s.substr(i);
        int count = 0;
        for (int j = 0; j < t.length(); j++) {
            char tp = t.at(j);
            if (tp != sp.at(j)) count++;
        }
        ans = min(ans, count);
    }
    cout << ans << endl;
}


Measured memory_bytes: 3224
#from functools import lru_cache
#@lru_cache(maxsize=None)
def is_prime(x):
    if x==1:
        return False
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return True

# @lru_cache(maxsize=None)
def like2017(x):
    return is_prime(i) and is_prime((i+1)//2)
    
table=[0,0]
for i in range(2,10**5):
    table+=table[i-1]+like2017(i),
        
n=int(input())
for _ in range(n):
    a,b=map(int,input().split())
    print(table[b]-table[a-1])
# print(table)


Measured memory_bytes: 6484
using System;
using System.Collections.Generic;


class Program
{
    static void Main(string[] args)
    {
        List<int> a = new List<int> { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30};
        while (true)
        {
            string gh = Console.ReadLine();
            if (gh == null) { break; }
            a.Remove(int.Parse(gh));
        }
        for(int i = 0; i < a.Count; i++)
        {
            Console.WriteLine(a[i]);
        }
    }

}

Measured memory_bytes: 9664
using System;


public class C
{
	public static void Main()
	{
		int N = Int32.Parse(Console.ReadLine());
		int[] r = new int[N + 2];
		r[N + 1] = 0;  // sentinel
		
		string[] args = Console.ReadLine().Split(' ');

		int hMax = 0;
		for(int i = 0; i < N; i++)
		{
			int h = Int32.Parse(args[i]);
			if(h > hMax)
				hMax = h;
			r[i + 1] = h;	
		}
		
		int counter = 0;
		for(int i = 1; i <= hMax; i++)
		{
			for(int j = 1; j <= N; j++)
			{	
				if(r[j] > 0)
				{
					counter++;
					do
					{
						r[j]--;
						j++;
					}
					while(r[j] > 0);
				}
			}			
		}
		
		Console.WriteLine(counter);
	}
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
#define double long double
#define int long long
#define inf (int)1e16
#define rep(i,n) for(int i = 0; i < n; i++) 
using namespace std;
int n;
int a[114514];
signed main() {
	cin >> n;
	int mi = 0;
	rep(i, n) {
		cin >> a[i];
		if (a[i] < 0) {
			mi++;
		}
	}
	if (mi % 2 == 0) {
		int cnt = 0;
		rep(i, n) cnt += abs(a[i]);
		cout << cnt << endl;
	}
	else {
		int mini = inf;
		int cnt = 0;
		rep(i, n) {
			cnt += abs(a[i]);
			mini = min(mini, abs(a[i]));
		}
		cout << cnt - 2 * mini << endl;
	}
}


Measured memory_bytes: 1024
#include <iostream>
#include <stdio.h>
using namespace std;
int main() {
  int N, D;
  cin >> N >> D;
  if (N%(D+D+1)==0){
    cout << N/(D+D+1) << endl;
  }else{
    cout << N/(D+D+1)+1 << endl;
  }
  return 0;
}

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


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

int main2() {
  int N, M, C; cin >> N >> M >> C;
  vector<int> B(M);
  REP(i, M) cin >> B[i];
  ll ans = 0;
  REP(_, N) {
    vector<int> A(M);
    REP(i, M) cin >> A[i];
    ll s = 0;
    REP(i, M) s += A[i] * B[i];
    s += C;
    if (s > 0) ans++;
  }
  cout << ans << endl;
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws)
    main2();
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>

using namespace std;
typedef long long int ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
ll MOD = 1000000007;
#define INF (1e9)

ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
typedef pair <ll,ll> P;


int main()
{
    ll A, B, C;
    cin >> A >> B >> C;
    if (A == B) cout << C << endl;
    if (A == C) cout << B << endl;
    if (C == B) cout << A << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PI pair<P,int>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}
int Madd(int x,int y) {return (x+y)%M;}
int Msub(int x,int y) {return (x-y+M)%M;}
int Mmul(int x,int y) {return (x*y)%M;}




template< typename T >
struct edge {
  int src, to;
  T cost;

  edge(int to, T cost) : src(-1), to(to), cost(cost) {}

  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WG = vector< Edges< T > >;
using UG = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

template < typename T >
bool is_cycle_dfs(int k,int p,vector<bool> &visited,vector<bool> &used,WG<T> &es){
  if(visited[k]){
    return true;
  }
  if(used[k]){
    return false;
  }

  visited[k]=true;
  used[k]=true;
  bool ret=false;
  for(auto e:es[k]){
    if(e.to==p||ret) continue;
    ret|=is_cycle_dfs(e.to,k,visited,used,es);
  }

  visited[k]=false;

  return ret;
}



template < typename T >
bool is_cycle(WG<T> &es){
  vector<bool> visited(es.size(),false);
  vector<bool> used(es.size(),false);
  bool flag=false;
  rep(i,es.size()){
    if(used[i]||flag) continue;
    flag|=is_cycle_dfs(i,-1,visited,used,es);
  }

  return flag;
}


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

  int n,m;
  cin>>n>>m;

  WG<int> es(n);
  rep(i,m){
    int a,b;
    cin>>a>>b;
    es[a].PB(edge<int>(b,1));
  }

  cout<<is_cycle(es)<<endl;


}


Measured memory_bytes: 3184
using System;
using System.Collections.Generic;

namespace MyProgram{
    class AtCoder{
        static void Main(){
            long x = long.Parse(Console.ReadLine());
            long y = 2*(x/11);
            if(x%11>6)y+=2;
            else if(x%11>0)y+=1;
            Console.WriteLine(y);
        }  
    } 
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
#define loop2(i, s, n, a) for (int i = int(s); i < int(n); i += a)
#define loop(i, s, n) loop2(i, s, n, 1)
#define rep(i, n) loop(i, 0, n)

#define pb push_back
#define all(in) in.begin(),in.end()

using ll = long long;
using ull = unsigned long long;
using namespace std;

const int mod = 2019;

int main(){
    string s; cin >> s;
    int n = s.length();

    int dp1[n]; // 10^n mod.mod
    dp1[0] = 1; for(int i=0; i<n-1; i++) dp1[i+1] = (dp1[i]*10)%mod;
    int dp2[n+1]; // Ti mod.mod
    dp2[n] = 0; for(int i=n-1; i>=0; i--) dp2[i] = (dp2[i+1] + (s[i]-'0')*dp1[n-1-i])%mod;

    int count[mod]; 
    rep(i,mod) count[i] = 0;
    rep(i,n+1) count[dp2[i]]++;

    int ans = 0;
    rep(i,mod){
        ans += count[i]*(count[i]-1)/2;
    }
    cout << ans << endl;
}

Measured memory_bytes: 5292
#include <stdio.h>
int main(void)
{
    int a,b,c,tmp;
    scanf("%d",&a);
    scanf("%d",&b);
    scanf("%d",&c);
    if(b<a){
        tmp=a;
        a=b;
        b=tmp;
    }
    if(c<b){
        tmp=b;
        b=c;
        c=tmp;
    }
    if(b<a){
        tmp=a;
        a=b;
        b=tmp;
    }
    printf("%d %d %d\n",a,b,c);
    return 0;
}



Measured memory_bytes: 2044
parseInt(x)=parse(Int, x)
parseMap(x::Array{SubString{String},1})=map(parseInt, x)

function root(uf::Array{Int,1},x);s=x;while uf[s]>0;s=uf[s];end;s;end
same(uf::Array{Int,1},x,y)=root(uf,x)==root(uf,y)?true:false
function unite(uf::Array{Int,1},x,y);l=root(uf,x);r=root(uf,y);if l!=r;if uf[l]<uf[r];uf[l]+=uf[r];uf[r]=l;else;uf[r]+=uf[l];uf[l]=r;end;end;end

function main()
	n,m = readline() |> split |> parseMap
	uf = -ones(Int,n+m)
	for i in 1:n
		k = readline() |> split |> parseMap
		for j in 2:length(k)
			unite(uf,i,n+k[j])
		end
	end
	x = root(uf,1)
	f = 0
	for i in 2:n
		if root(uf,i)!=x
			f = 1
		end
	end
	println(f==0 ? "YES" : "NO")
end

main()

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

int main() {
    string s;
    cin >> s;
    if((s[0] == s[1] && s[1] == s[2]) || (s[1] == s[2] && s[2] == s[3])) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

class Card {
	char mark;
	long num;

	public Card(char mark, long num) {
		super();
		this.mark = mark;
		this.num = num;
	}

	@Override
	public String toString() {
		return mark + " " + num;
	}

	public boolean equals(Card o) {
		return this.mark == o.mark && this.num == o.num;
	}

}

class Main {

	public static void main(String[] args) {

		int n = 0;
		Card[] cards = null;

		try(BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in));) {

			n = Integer.parseInt(br.readLine());

			cards = new Card[n];
			for (int i = 0; i < n; i++) {
				String line = br.readLine();

				cards[i] = new Card(
						line.charAt(0), Long.parseLong(line.substring(2))
						);
			}

		} catch (NumberFormatException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}

		Card[] copy = Arrays.copyOf(cards, n);
		quickSort(cards, 0, n-1);
		mergeSort(copy, 0, n);

		boolean stable = true;
		for (int i = 0; i < n; i++) {
			if(!cards[i].equals(copy[i])) {
				stable = false;
				break;
			}
		}

		if(stable) {
			System.out.println("Stable");
		} else {
			System.out.println("Not stable");
		}

		for (int i = 0; i < n; i++) {
			System.out.println(cards[i]);
		}

	}

	private static void mergeSort(Card[] cards, int left, int right) {

		if(left+1 < right) {
			int mid = (left + right)/2;
			mergeSort(cards, left, mid);
			mergeSort(cards, mid, right);

			merge(cards, left, mid, right);
		}

	}

	private static void merge(Card[] cards, int left, int mid, int right) {

		int n1 = mid - left;
		int n2 = right - mid;

		Card[] L = new Card[n1+1];
		Card[] R = new Card[n2+1];
		for (int i = 0; i < n1; i++) {
			L[i] = cards[left + i];
		}
		for (int i = 0; i < n2; i++) {
			R[i] = cards[mid + i];
		}
		Card inf = new Card('X', Long.MAX_VALUE);
		L[n1] = inf;
		R[n2] = inf;

		int i = 0;
		int j = 0;

		for (int k = left; k < right; k++) {

			if(L[i].num <= R[j].num) {
				cards[k] = L[i];
				i++;
			} else {
				cards[k] = R[j];
				j++;
			}

		}

	}

	private static void quickSort(Card[] cards, int p, int r) {
		if (p < r) {
			int q = partition(cards, p, r);
			quickSort(cards, p, q-1);
			quickSort(cards, q+1, r);
		}
	}

	private static int partition(Card[] cards, int p, int r) {

		Card x = cards[r];
		int i = p-1;
		for (int j = p; j < r; j++) {
			if (cards[j].num <= x.num) {
				i++;
				Card tmp;
				tmp = cards[j];
				cards[j] = cards[i];
				cards[i] = tmp;
			}
		}

		Card tmp;
		tmp = cards[r];
		cards[r] = cards[i+1];
		cards[i+1] = tmp;

		return i + 1;

	}
}

Measured memory_bytes: 74884
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;

int main(void){ 
    IOS;
    string s, p;
    cin >> s >> p;
    if (p.size() != s.size()+1){
        cout << "No" << endl; return 0;
    }
    for (int i = 0; i < s.size(); ++i){
        if (s[i] != p[i]){
            cout << "No" << endl; return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 3652
#include<iostream>
#include<cstring>
#include<vector>
#include<sstream>
using namespace std;
vector< vector<int> > Hg(100);
bool used[100];
int solve(int);
int main(){
  int n;
  while(cin >> n && n){
    for(int i=0;i<100;i++){
      Hg[i].clear();
    }
    for(int i=0,a,b;i<n;i++){
      cin >> a >> b;
      Hg[a-1].push_back(b-1);
      Hg[b-1].push_back(a-1);
    }
    memset(used,false,sizeof(used));
    int ans = 0;
    for(int i=0;i<100;i++){
      ans = max(ans,solve(i));
    }
    cout << ans << endl;
  }
}
int solve(int a){
  if(used[a] || Hg[a].empty() ) return 0;
  used[a] = true;
  int cnt = 0;
  for(int i=0,l=Hg[a].size();i < l;i++){
      cnt = max(cnt,solve(Hg[a][i]));
  }
  used[a] = false;
  return cnt + 1;
}

Measured memory_bytes: 1224
/**
 *    author:  tourist
 *    created: 11.05.2020 14:12:32       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  int k;
  cin >> k;
  int n = (int) s.size();
  int ans = 0;
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    int limit = (int) (s[i] - '0');
    if (i < n - 1) {
      --limit;
    }
    for (int d = 0; d <= limit; d++) {
      int cur = cnt + (d > 0);
      if (k - cur == 0) {
        ans += 1;
      }
      if (k - cur == 1) {
        ans += (n - i - 1) * 9;
      }
      if (k - cur == 2) {
        ans += (n - i - 1) * (n - i - 2) / 2 * 9 * 9;
      }
      if (k - cur == 3) {
        ans += (n - i - 1) * (n - i - 2) * (n - i - 3) / 6 * 9 * 9 * 9;
      }
    }
    if (s[i] != '0') {
      cnt += 1;
    }
  }
  cout << ans << '\n';
  return 0;
}


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

int main(){
char x[200];
char Roma[7]={'I','V','X','L','C','D','M'};
int Arabia[7]={1,5,10,50,100,500,1000};
int a=0,b,ans=0,ls;
string s;
while(cin>>s){
ans=0;
a=0;
ls=s.size();
for(int i=ls-1;i>-1;i--){
for(int j=0;j<7;j++){
if(s[i]==Roma[j])b=Arabia[j];}
if(b>=a){ans+=b; a=b;}
if(b<a)ans-=b;}
cout<<ans<<endl;}}

Measured memory_bytes: 1180
#include <iostream>
using namespace std;
long long int a[100001];
int f_max(int s, int e) {
    long long int max=a[s];
    int m_p=s;
    for(int i=s+1;i<e;i++) {
        if(max<a[i]){
            m_p=i, max=a[i];
        }
    }
    return m_p;
}
int f_min(int s, int e) {
    long long int min=a[s];
    int m_p=s;
    for(int i=s+1;i<e;i++) {
        if(min>a[i]) {
            m_p=i, min=a[i];
        }
    }
    return m_p;
}
int main() {
    int n, t, cnt=0;
    long long int max=0;
    cin >> n >> t;
    for(int i=0;i<n;i++) {
        cin >> a[i];
    }
    int s=0, e;
    while(s<n) {
        e=f_max(s, n);
        s=f_min(s, e);
        if(a[e]-a[s]>max) {
            max=a[e]-a[s];
            cnt=1;
        }
        else if(a[e]-a[s]==max) cnt++;
        s=e+1;
    }
    cout << cnt;
}

Measured memory_bytes: 1152
package main

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

//input
var sc = bufio.NewScanner(os.Stdin)

func nextStr() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

type Node struct {
	key int
	p   *Node
	l   *Node
	r   *Node
}

var NIL *Node

var root *Node
var n int

func preorder(u *Node, l []int) []int {
	if u != NIL {

		//fmt.Printf(" %d", u.key)
		l = append(l, u.key)
		l = preorder(u.l, l)
		l = preorder(u.r, l)
	}
	return l

}

func inorder(u *Node, l []int) []int {
	if u != NIL {
		l = inorder(u.l, l)
		//fmt.Printf(" %d", u.key)
		l = append(l, u.key)
		l = inorder(u.r, l)
	}
	return l
}

func printList(list []int) {
	buf := bufio.NewWriter(os.Stdout)
	for _, v := range list {
		buf.Write([]byte(fmt.Sprintf(" %d", v)))
	}
	buf.Write([]byte("\n"))
	buf.Flush()
}

//solve
func insert(v int) {
	var x, y *Node

	//x: 走査する初期値
	//y: xの親 = NIL
	x = root

	//z: 挿入するNode
	z := &Node{v, NIL, NIL, NIL}
	//zの親を求める
	for x != NIL {
		y = x
		if z.key < x.key {
			x = x.l
		} else {
			x = x.r
		}
	}

	z.p = y
	if y == NIL {
		root = z //木が空のときは、zをrootとする
	} else if z.key < y.key {
		y.l = z //zをyの左の子にする
	} else {
		y.r = z //zをyの右のことする
	}

}

func main() {
	sc.Split(bufio.ScanWords)
	n = nextInt()
	for i := 0; i < n; i++ {
		verb := nextStr()
		if verb == "insert" {
			v := nextInt()
			insert(v)
		} else if verb == "print" {
			printList(inorder(root, []int{}))
			printList(preorder(root, []int{}))
		}
	}
	//fmt.Println(root)
}



Measured memory_bytes: 44948
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

using namespace std;

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

#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 FORR(i, m, n) for (int i = m; i >= n; i--)

int const M_MAX = 200000;

int N, M;

vector<P> G[M_MAX + 1];
map<int, int> used;
map<int, map<int, ll>> costs;

int bfs(int current) {
  queue<int> Q;
  used[current]++;
  Q.push(current);

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

    for (auto p : G[idx]) {
      ll cost = costs[current][p.first];
      if (cost) {
        if (cost != costs[current][idx] + p.second) return 0;
      } else {
        costs[current][p.first] = costs[current][idx] + p.second;
        costs[p.first][current] = -1 * costs[current][p.first];
      }

      if (used[p.first]) continue;
      used[p.first]++;
      Q.push(p.first);
    }
  }
  return 1;
}

int main() {
  scanf("%d %d", &N, &M);

  rep(i, M) {
    int l, r, d;
    scanf("%d %d %d", &l, &r, &d);

    G[l].push_back(P(r, d));
    G[r].push_back(P(l, -1 * d));
  }

  rep(i, N + 1) {
    if(!bfs(i)) {
      printf("No\n");
      return 0;
    }
  }
  printf("Yes\n");
}


Measured memory_bytes: 68736
#include <iostream>

int main() {
	using namespace std;
	for (;;) {
		int n;
		cin >> n;
		if (cin.eof()) { break; }

		int pair = 0;
		for (int a = 0; a <= 9; ++a) {
			for (int b = 0; b <= 9; ++b) {
				int ab = a + b;
				for (int c = 0; c <= 9; ++c) {
					int abc = ab + c;
					for (int d = 0; d <= 9; ++d) {
						if (abc + d == n) { ++pair; }
					}
				}
			}
		}

		cout << pair << endl;
	}
	return 0;
}

Measured memory_bytes: 0
import java.util.*;

public class Main {
	Scanner sc = new Scanner(System.in);
	final int MOD = 1000000007;

	void doIt() {
		int n = sc.nextInt();
		int k = sc.nextInt();
		String s = sc.next();
		char[] ca = s.toCharArray();
		ca[k - 1] += 32;
		System.out.println(new String(ca));
		
	}

	public static void main(String[] args) {
		new Main().doIt();
	}
}


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

using namespace std;
int main()
{
    int n,a[1000];
    cin >> n ;
    int x,y;
    x=y=0;
    for(int i=0;i<n;i++)
    {
        cin >> a[i];
    }
    sort(a,a+n);
    for(int i=0;i+1<n;i+=2)
    {
        x+=a[i];
        y+=a[i+1];
    }
    if(n%2==0) printf("%d\n",y-x);
    else printf("%d\n",x-y+a[n-1]);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define f(i,n) for(int i=0;i<(n);i++)
#define P pair<int,int>
#define LONG LLONG_MAX/3;
#define INT INT_MAX/3;
#define mod 1000000007
#define S second
#define F first
typedef long long ll;
using namespace std;
int x[100000],ans;
int main(){
	int a,b;
	cin>>a>>b;
	if(a*b%2) puts("Yes");
	else puts("No");
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1e9
#define endl '\n'
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define FORE(i, a, b) for (int i = (a), e = (b); i < e; ++i)
#define RFORE(i, a, b) for (int i = (b)-1, e = (a); i >= e; --i)
#define ALL(x) (x).begin(), (x).end()
#define SORT(c) sort((c).begin(), (c).end())
#define SORTR(c) sort((c).begin(), (c).end(), greater<int>())
using namespace std;
typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A.at(i);
    }
    SORT(A);
    int ans   = 0;
    int tmp   = 0;
    int count = 0;
    for (ll& a : A) {
        if (tmp != a) {
            if (count % 2 == 1) { ++ans; }
            count = 0;
        }
        ++count;
        tmp = a;
    }
    if (count % 2 == 1) { ++ans; }
    cout << ans << endl;
}


Measured memory_bytes: 3972
#include <stdio.h>

struct node{
	int key;
	int parent;
	int right;
	int left;
};

struct node tree[300];

int main(){
	int H;
	int i;
	scanf("%d",&H);
	int temp;

	for(i=0;i<H+1;i++){
		tree[i].key = -1;
		tree[i].parent = -1;
		tree[i].right = -1;
		tree[i].left = -1;
	}

	for(i=1;i<H+1;i++){
		scanf("%d",&temp);
		tree[i].key=temp;
	}

	for(i=1;i<H+1;i++){
		tree[i].parent = i / 2;
		if(2*i<=H){
			tree[i].left = 2 * i;
		}
		if(2*i+1<=H){
			tree[i].right = 2 * i + 1;
		}
	}

	for(i=1;i<H+1;i++){
		printf("node %d: key = %d, ",i,tree[i].key);
		if(tree[i].parent!=0){
			printf("parent key = %d, ",tree[tree[i].parent].key);
		}
		if(tree[i].left!=-1){
			printf("left key = %d, ",tree[tree[i].left].key);
		}
		if(tree[i].right!=-1){
			printf("right key = %d, ",tree[tree[i].right].key);
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 604
use proconio::input;

fn main() {
    input! {
        mut target: i32,
        mut every: i32,
        mut takes: i32
    }

    let mut answer = 0;
    loop {
        target -= every;
        answer += takes;

        if target <= 0 {
            break;
        }
    }

    println!("{}", answer);
}


Measured memory_bytes: 2136
import Control.Applicative

getInt :: IO Int
getInt = (\a -> read a :: Int) <$> getLine
getIntArray :: IO [Integer]
getIntArray = ((map (\a -> read a :: Integer)) . words) <$> getLine

main = do
    [n, k] <- getIntArray
    print $ (*) k $ (k - 1) ^ (n - 1)


Measured memory_bytes: 508
def read(): return list(map(int, input().split()))


n = input()
a = read()

odd, four, not4 = 0, 0, 0
for i in a:
    if i % 4 == 0:
        four += 1
        continue

    if i & 1:
        odd += 1
    else:
        not4 += 1

odd += (not4 & 1)

print("Yes" if odd <= four + 1 else "No")

Measured memory_bytes: 14252
from sys import stdin
# stdin = open('./input.txt')
import math

N, K = stdin.readline().rstrip().split()
N = int(N)
K = int(K)
if K <= 1:
    print(1)
    exit(0)


print(sum([(1/2)**(math.floor(math.log(((K-1)/n), 2))+1) if n < K else 1 for n in range(1, N+1)]) / N)


Measured memory_bytes: 44784
//By TheOneYouWant
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define memreset(a) memset(a,0,sizeof(a))
#define testcase(t) int t;cin>>t;while(t--)
#define forstl(i,v) for(auto &i: v)
#define forn(i,e) for(int i=0;i<e;++i)
#define forsn(i,s,e) for(int i=s;i<e;++i)
#define rforn(i,s) for(int i=s;i>=0;--i)
#define rforsn(i,s,e) for(int i=s;i>=e;--i)
#define bitcount(a) __builtin_popcount(a) // set bits (add ll)
#define ln '\n'
#define getcurrtime() cerr<<"Time = "<<((double)clock()/CLOCKS_PER_SEC)<<endl
#define dbgarr(v,s,e) cerr<<#v<<" = "; forsn(i,s,e) cerr<<v[i]<<", "; cerr<<endl
#define inputfile freopen("input.txt", "r", stdin)
#define outputfile freopen("output.txt", "w", stdout)
#define dbg(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); \
stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) { cerr<<endl; }
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << "\t"; err(++it, args...);
}
template<typename T1,typename T2>
ostream& operator <<(ostream& c,pair<T1,T2> &v){
	c<<"("<<v.fi<<","<<v.se<<")"; return c;
}
template <template <class...> class TT, class ...T>
ostream& operator<<(ostream& out,TT<T...>& c){
    out<<"{ ";
    forstl(x,c) out<<x<<" ";
    out<<"}"; return out;
}
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> p64;
typedef pair<int,int> p32;
typedef pair<int,p32> p96;
typedef vector<ll> v64;
typedef vector<int> v32; 
typedef vector<v32> vv32;
typedef vector<v64> vv64;
typedef vector<p32> vp32;
typedef vector<p64> vp64;
typedef vector<vp32> vvp32;
typedef map<int,int> m32;
const int LIM=2e5+5,MOD=1e9+7;
const ld EPS = 1e-9;

int read(){
    int xx=0,ff=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
    return xx*ff;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main(){
	fastio;

	ll k; cin>>k;

    ll rem = 1;
    ll mod = 9*k;


    forsn(i,1,1e8){
        rem *= 10;
        rem %= mod;
        ll rem2;
        rem2 = 7 * (rem-1);
        rem2 %= mod;
        if(rem2<0) rem2 += mod;
        if(rem2 == 0){
            cout<<i<<ln;
            return 0;
        }
    }
    cout<<-1<<ln;
	

	return 0;
}

Measured memory_bytes: 3656
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int a[100005],b[100005];
 
int main()
{
    //printf("%d",int(ceil(double(45/9))));
int n,total;
    scanf("%d%d",&n,&total);
    for (int i=0; i<n; i++)
    {
        scanf("%d%d",&a[i],&b[i]);
    }
 
    sort(a,a+n);
    sort(b,b+n);
    int pos = upper_bound(b,b+n,a[n-1])-b;
    //cout<<pos<<endl;
    int pos2 = n-1;
    int ans = 0;
    while(total>0 && pos2>=pos)
    {
        total -=b[pos2];
        pos2--;
        ans++;
    }
    //cout<<total<<endl;
    if(total>0){
    int cnt = ceil(total*1.0/a[n-1]);
    ans+=cnt;}
 
    printf("%d\n",ans);
 
 
    return 0;
}

Measured memory_bytes: 1024
# -*- coding: utf-8 -*-

n = input()
l = map(int, raw_input().split())

# 総和を求める
sum = 0
for i in l:
    sum += i

# 最小を求める
s = 0
ans = 10000
for i in l:
    s += i
    s2 = sum-s
    ans = min(ans, abs(s-s2))

print ans
        


Measured memory_bytes: 2568
#include <bits/stdc++.h>
#define inf 1e16
#define dummy -1e17
using namespace std;

long long num[2] = {0};
long long dp[55][55][55][55][2][4] = {0};
vector<long long> lst[2];

long long solve(long long x, long long y, long long p,
                long long q, long long scorep,
                long long scoreq, bool turn, int fin);

int main() {
  cin >> num[0] >> num[1];
  for(int i = 0; i < 2; ++i) {
    lst[i].resize(num[i]);
    for(int j = 0; j < num[i]; ++j) cin >> lst[i][j];
  }
  for(int i = 0; i <= num[0]; ++i)
    for(int j = 0; j <= num[1]; ++j)
      for(int k = 0; k <= num[0]; ++k)
        for(int l = 0; l <= num[1]; ++l)
          for(int m = 0; m < 2; ++m){
            for(int n = 0; n < 3; ++n)
              dp[i][j][k][l][m][n] = dummy;
              dp[i][j][k][l][m][3] = 0;
            }
  for(int i = 0; i < 3; ++i)
    dp[num[0]][num[1]][0][0][0][i] =
        dp[num[0]][num[1]][0][0][1][i] = 0;
  cout << solve(0, 0, 0, 0, 0, 0, 0, 1) << endl;
  return 0;
}

long long solve(long long x, long long y, long long p,
                long long q, long long scorep,
                long long scoreq, bool turn, int fin) {
  if(dp[x][y][p][q][turn][fin] != dummy)
    return dp[x][y][p][q][turn][fin];
  long long ans = -inf;
  if(turn) ans = inf;
  // stack pattern
  if(!turn && x < num[turn]) {
    if(lst[turn][x] == -1)
      ans = max(ans, solve(x + 1, y, p + 1, 0, scorep, 0,
                           !turn, 0));
    else
      ans = max(ans, solve(x + 1, y, p + 1, q,
                           scorep + lst[turn][x], scoreq,
                           !turn, 0));
  }
  else if(turn && y < num[turn]) {
    if(lst[turn][y] == -1)
      ans = min(ans, solve(x, y + 1, 0, q + 1, 0, scoreq,
                           !turn, 0));
    else
      ans =
          min(ans, solve(x, y + 1, p, q + 1, scorep,
                         scoreq + lst[turn][y], !turn, 0));
  }
  // pass pattern
  if(!turn)
    ans = max(ans,
              scorep - scoreq +
                  solve(x, y, 0, 0, 0, 0, !turn, fin + 1));
  else
    ans = min(ans,
              scorep - scoreq +
                  solve(x, y, 0, 0, 0, 0, !turn, fin + 1));
  return dp[x][y][p][q][turn][fin] = ans;
}


Measured memory_bytes: 468700
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner reader = new Scanner(System.in);
		int N = reader.nextInt();
		int K = reader.nextInt();
		int ans = 0;
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = reader.nextInt();
		}
		Arrays.sort(arr);
		for (int i = N-K; i < N; i++) {
			ans += arr[i];
		}


		System.out.println(ans);
		reader.close();

	}
}

Measured memory_bytes: 21588
/*input
8 6
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}
//}}}
const ll maxn=300005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		
		b>>=1;
	}
	return res;
}
int main()
{
	IOS;
	int n,k;
	cin>>n>>k;
	cout<<(n%k>0);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <map>
#include <iomanip>
#include <limits.h>
#include <queue>

using namespace std;    
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const bool DEBUG = false;

int main(){

    ll N, S, K;
    cin >> N >> K >> S;

    vector<ll> v(N);
    for(int i = 0; i < N; i++){
        if(i < K) v[i] = S;
        else{
            if(S == 1000000000) {
                v[i] = S - 1;
            }
            else{
                v[i] = S + 1;
            }
        } 

    }

    for(int i = 0; i < N; i++){
        cout << v[i];
        if(i != N - 1) cout << " ";
        else cout << endl;
    }

}

Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
long long n,m,k,ans=0,cnt=0,tmp;
string s,t;
int main(){
  cin >> n >> m;
  if(n%2==0 or m%2==0){
    cout << "No" << endl;
  }else{
  cout << "Yes" << endl;
    
  }
  return 0;
}

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

vector<int> adjList[100005];
int Distance[100005];
int parent[100005];

void bfs()
{
	queue<int> nodes;
	nodes.push(1);
	
	while(!nodes.empty())
	{
		int currNode = nodes.front();
		nodes.pop();
		
		vector<int>::iterator itr;
		for(itr = adjList[currNode].begin(); itr != adjList[currNode].end(); itr++)
		{
			if(Distance[currNode] + 1 < Distance[*itr])
			{
				Distance[*itr] = Distance[currNode] + 1;
				nodes.push(*itr);
				
				parent[*itr] = currNode;
			}
		}
	}
}

int main()
{
	int N, M;
	scanf("%d%d", &N, &M);
	
	for(int i = 1; i <= M; i++)
	{
		int Ai, Bi;
		scanf("%d%d", &Ai, &Bi);
		
		adjList[Ai].push_back(Bi);
		adjList[Bi].push_back(Ai);
	}
	
	Distance[1] = 0;
	for(int i = 2; i <= N; i++)
		Distance[i] = INT_MAX;
	
	bfs();
	for(int i = 2; i <= N; i++)
	{
		if(Distance[i] == INT_MAX)
		{
			printf("No");
			return 0;
		}
	}
	
	printf("Yes\n");
	for(int i = 2; i <= N; i++)
		printf("%d\n", parent[i]);
}

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

int main(void)
{
    long long n;
    string s;
    cin >> n >> s;
    long long res = 1;
    for (int i = 1; i < n; i++) {
        if (s[i] == s[i-1]) {
            continue;
        } else {
            res++;
        }
    }

    cout << res << endl;
}


Measured memory_bytes: 512
N,W = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(N)]

dp = [{} for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    w,v = src[i-1]
    for v0,w0 in dp[i-1].items():
        if v0 in dp[i]:
            dp[i][v0] = min(dp[i][v0], w0)
        else:
            dp[i][v0] = w0
        if w0+w > W: continue
        if v0+v in dp[i]:
            dp[i][v0+v] = min(dp[i][v0+v], w0+w)
        else:
            dp[i][v0+v] = w0+w
print(max(dp[-1].keys()))

Measured memory_bytes: 286344
n = gets.to_i
s = gets.chomp

result = s.count("R") * s.count("G") * s.count("B")

n.times do |i|
  j = i + 1
  while j < n
    k = 2 * j - i
    if j < k && k < n && s[i] != s[j] && s[j] != s[k] && s[k] != s[i]
      result -= 1
    end
    j += 1
  end
end

puts result

Measured memory_bytes: 14352
using System;
using System.IO;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;
public static class P {
  public static void Main() {
    var nw = Console.ReadLine().Split().Select(int.Parse).ToArray();
    int n = nw[0];
    int W = nw[1];
    int[] v = new int[n];
    int[] w = new int[n];
    foreach (int i in Enumerable.Range(0, n)) {
      var vw = Console.ReadLine().Split().Select(int.Parse).ToArray();
      v[i] = vw[0];
      w[i] = vw[1];
    }
    int inf = int.MaxValue;
    int[] dp = Enumerable.Repeat(-inf, W + 1).ToArray();
    dp[0] = 0;
    foreach (int j in Enumerable.Range(0, n).Reverse()) {
      foreach (int i in Enumerable.Range(0, W).Reverse()) {
        if (W < i + w[j]) continue;
        dp[i + w[j]] = Max(dp[i + w[j]], dp[i] + v[j]);
      }
      // Console.WriteLine("dp: {0}", String.Join(" ", dp.Select(x => x.ToString("D"))));
    }
    int ans = dp.Max();
    Console.WriteLine(ans);
  }
}



Measured memory_bytes: 31804
#include <bits/stdc++.h>
using namespace std;
#define INT(a) scanf("%d",&a)
#define STR(a) scanf("%s",a)
#define DBL(a) scanf("%lf",&a)
#define LNG(a) scanf("%lld",&a)
#define PI acos(-1)

int main(){
	long long H;
	cin>>H;
	int cnt =0;
	while(H){
		cnt++;
		H/=2LL;
	}
	//cout<<cnt<<endl;
	cout<<(1LL<<cnt)-1<<endl;
	return 0;
}

Measured memory_bytes: 256
//In the Name of God
//Ya Ali

#include<bits/stdc++.h>

//#define int long long

#define err(A) cout<<#A<<" = "<<(A)<<endl

using namespace std;

const int inf=1e9+7;
const int maxn=512;

int n;

string s[maxn];

int r[maxn],c[maxn];
				     
int ans=inf;

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

  cin>>n;

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

  int tot=0;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      if(s[i][j]=='#')
	{
	  r[i]++;
	  c[j]++;
	  tot++;
	}

  if(tot==0)
    {
      cout<<-1<<endl;
      return 0;
    }

  int C=0;
  for(int j=0;j<n;j++)
    C+=(c[j]==n);

  for(int i=0;i<n;i++)
    if(c[i])
      ans=min(ans,n-r[i]+n-C);
    else
      ans=min(ans,n-r[i]+n-C+1);
  
  cout<<ans<<endl;
  
  return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<set>
#include<sstream>
using namespace std;
typedef long long ll;
const ll maxn=1e6+10;
const ll inf=0x3f3f3f3f3f3f3f3f;
void io(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
ll flag[maxn],num[maxn],vis[maxn],a[maxn],b[maxn];
int main()
{
	io();
	ll n;
	cin>>n;
	for(ll i=1;i<=n;i++)
	{
		cin>>num[i];
		vis[num[i]]++;
	}
	ll sum=0;
	for(ll i=1;i<=n;i++)
	{
		if(!flag[num[i]])
		{
			a[num[i]]=max((ll)0,(vis[num[i]]*(vis[num[i]]-1)/2));
			b[num[i]]=max((ll)0,(vis[num[i]]-2)*(vis[num[i]]-1)/2);
			flag[num[i]]=1;
			sum+=a[num[i]];
		}
	}
	for(ll i=1;i<=n;i++)
	{
		cout<<(sum-a[num[i]]+b[num[i]])<<endl;
	}
	return 0;
}

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




int max(int a[]){
    int n = 0;
    for(int i=0;i<3;i++){
        if(a[i] > n){
            n = a[i];
        }
    }
    return n;
}

int min(int a[]){
    int n = 100;
    for(int i=0;i<3;i++){
        if(a[i] < n){
            n = a[i];
        }
    }
    return n;
}


int main(void){
    int a[3];
    cin >> a[0] >> a[1] >> a[2];
    cout << max(a)-min(a) << endl;

    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N;
  string S;
  int K;
  
  cin >> N >> S >> K;
  char key = S.at(K - 1);
  
  for(int i = 0; i < N; i++){
    if(S.at(i) != key){
      S.at(i) = '*';
    }
  }
  
  cout << S << endl;
}

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

char mat[1401][1401];
int dp[1401][1401];

int main(){
    int h, w;
    cin >> h >> w;

    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> mat[i][j];
        }
    }

    int ans = 0;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(mat[i][j] == '0'){
                dp[i+1][j+1] = min(dp[i][j], min(dp[i][j+1], dp[i+1][j]))+1;
                ans = max(ans, dp[i+1][j+1]);
            }
        }
    }

    cout << ans*ans << endl;

    return 0;
}


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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

typedef long long ll;
typedef pair<ll,ll> P;

vector<vector<P>> v(111111);
int out[111111];

void dfs(int now, int pre){
	REP(i, v[now].size()){
		if(v[now][i].FI == pre)continue;
		if(v[now][i].SE % 2){
			out[v[now][i].FI] = 1 - out[now];
		}
		else {
			out[v[now][i].FI] = out[now];
		}
		dfs(v[now][i].FI, now);
	}
}

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

	int n;cin >> n;
	REP(i, n-1){
		ll a, b, c;cin >> a >> b >> c;
		a--;b--;
		v[a].EB(b, c);
		v[b].EB(a, c);
	}

	dfs(0, -1);

	REP(i, n)cout << out[i] << endl;

	return 0;
}


Measured memory_bytes: 10880
a,b,c = gets.split(" ").map!{|i| i.to_i}
k = gets.to_i
other = 0
max = 0
if a >=  b and a >= c
  max = a; other = b+c
elsif b >= a and b >= c
  max = b;other = a+c
else max = c;other = a+b
end
k.times do |k|
  max = max*2
end
puts max + other


Measured memory_bytes: 1788
#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#define MOD 1000000007
using namespace std;

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

    vector<int> Nums;
    int now = 1;
    int cnt = 0;

    for(int i=0;i<n;i++){
        if(s[i] == (char)('0'+now)) cnt++;
        else{
            Nums.push_back(cnt);
            now = 1 - now;
            cnt = 1;
        }
    }
    if (cnt != 0) Nums.push_back(cnt);

    //1-0-1-0-1-0-1が欲しい
    //1-0-1-0みたいなので終わってたら1を足したい
    if(Nums.size() % 2 == 0) Nums.push_back(0);

    /*for(int i=0;i<n;i++){
        cout << Nums[i];
    }*/

    int Add = 2 * k + 1;

    int ans = 0;
    int tmp = 0;

    //偶数番目だけ足したい
    for(int i = 0;i < Nums.size();i+=2){
        tmp = 0;

        int left = i;
        int right = min(i+Add,(int)Nums.size());

        for(int j = left; j < right;j++){
            tmp += Nums[j];
        }
        ans = max(ans,tmp);
    }

    cout << ans << endl;

}

Measured memory_bytes: 1020
// ACPC_AIZUDAI_DROPOUT
// coder : naan

#include <bits/stdc++.h>

int main(){
    using namespace std;
    unsigned long N;
    cin >> N;
    long cons{0}, coef{1};
    for(unsigned long i = 0, q, x; i < N; ++i){
        cin >> q >> x;
        if(q == 1){
            cons *= x;
            coef *= x;
        }else if(q == 2){
            cons += x;
        }else{
            cons -= x;
        }
    }
    cout << -cons << " " << coef << endl;
    return 0;
}


Measured memory_bytes: 3120
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <fstream>
#include <string>
#include <math.h>
using namespace std;
typedef long long ll;
//typedef pair<ll, ll> P;
//typedef pair<double, P> T;

const ll mod = 1000000007;
const ll INF = 100000010000;

ll N, C[200010];

ll ans;

ll pow_mod(ll x, ll y)
{
	if (y == 0) return 1;
	if (y % 2 == 1)
	{
		return x * pow_mod(x, y - 1) % mod;
	}
	else
	{
		ll half = pow_mod(x, y / 2);
		return half * half % mod;
	}
}

ll div_mod(ll x)
{
	return pow_mod(x, mod - 2);
}

/*ll sum_bit(ll i)
{
	ll s = 0;
	while (i > 0)
	{
		s += bit[i];
		i -= i & -i;
	}
	return s;
}

void add_bit(ll i, ll x)
{
	while (i <= 2 * N + 10)
	{
		bit[i] += x;
		i += i & -i;
	}
}*/

void init()
{
	
}

void output()
{
	cout << ans << endl;
}



void solve()
{
	ll N;
	string s;
	cin >> N >> s;
	for (int i = 1; i < N - 1; i++)
	{
		if (s[i - 1] == 'A' && s[i] == 'B' && s[i + 1] == 'C')
		{
			ans++;
		}
	}
}

int main()
{
	init();
	
	solve();

	

	output();
	ll N;
	cin >> N;
}

Measured memory_bytes: 256