akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<functional>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<complex>
#include<cstdlib>
#include<cctype>

#define REP(i,n) for(int i = 0;i < (n);i++)
#define PB push_back
#define MP make_pair
#define SHOW1d(v,n) {for(int i = 0;i < (n);i++)cout << v[i] << ' ';cout << endl << endl;}
#define SHOW2d(v,i,j) {for(int a = 0;a < i;a++){for(int b = 0;b < j;b++)cout << v[a][b] << ' ';cout << endl;}cout << endl;}
#define ALL(v) v.begin(),v.end()

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;


ll gmax[100010];
ll smax[100010];


struct medaru
{
	int gc,sc;
	medaru(int a,int b):gc(a),sc(b){}
};

int main()
{
	vector<medaru> v;
	int x,y,z;
	ll c_base = 0;
	
	cin >> x >> y >> z;
	
	REP(i,x+y+z)
	{
		int a,b,c;
		cin >> a >> b >> c;
		medaru tmp(a-c,b-c);
		v.PB(tmp);
		c_base += c;
	}
	
	sort(ALL(v),[](const medaru& l,const medaru& r){return (l.gc - l.sc) < (r.gc - r.sc);});
	
	//REP(i,x+y+z)
	//{
	//	cout << v[i].gc - v[i] .sc << endl;
	//}
	
	priority_queue<int,vector<int>,greater<int> > pqa;
	priority_queue<int,vector<int>,greater<int> > pqb;
	
	for(int i = 0;i < y;i++)
	{
		pqa.push(v[i].sc);
		smax[y-1] += v[i].sc;
	}
	//cout << pqa.size() << endl;
	for(int i = y;i < y+z;i++)
	{
		smax[i] = smax[i-1];
		pqa.push(v[i].sc);
		smax[i] += v[i].sc;
		smax[i] -= pqa.top();pqa.pop();
	}
	
	for(int i = x+y+z-1;i >= y+z;i--)
	{
		pqb.push(v[i].gc);
		gmax[y+z] += v[i].gc;
	}
	//cout << pqb.size() << endl;
	for(int i = y+z-1;i > y-1;i--)
	{
		gmax[i] = gmax[i+1];
		pqb.push(v[i].gc);
		gmax[i] += v[i].gc;
		gmax[i] -= pqb.top();pqb.pop();
	}
	ll ret = -1000000000000000;
	
	for(int i = y-1;i < y+z;i++)
	{
		ret = max(ret , smax[i] + gmax[i+1]);
	}
	
	cout << ret + c_base << endl;
	
	return 0;
}




Measured memory_bytes: 2292
#include <bits/stdc++.h>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
const int INF = 1010000000;
const double EPS = 1e-10;

int h,w,x;
char s[1000][1000];
bool visited [1000][1000];
pair<int,int> start,goal;
queue<pair<int,pair<int,int>>> q;
vector<pair<int,int>> ino;

int main(){
  string a,b,c;cin>>a>>b>>c;
  cout<<a[0]<<b[1]<<c[2];
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
typedef long long ll;
using namespace std;


int main(void) {
    ll X,K,D;
    cin >> X >> K >> D;
    ll ans;
    X = abs(X);
    if (X/D > K) {
        ans = X - (K * D);
    }else{
        ll e = (X / D);
        K -= e;
        X -= e * D;
        if (K % 2 == 1) X = abs(X - D);
        ans = X;
    }
    cout << ans << endl;;
    return 0;
}



Measured memory_bytes: 3616
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;


int main() {
	int N; cin >> N;
	vector<int>ns(N);
	for (int i = 0; i < N; ++i) {
		cin >> ns[i];
	}
	int Q; cin >> Q;
	int sum = 0;
	while (Q--) {
		int a; cin >> a;
		auto it = lower_bound(ns.begin(), ns.end(), a);
		auto jt = upper_bound(ns.begin(), ns.end(), a);
		sum += min(1,int(jt - it));
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 3052
#include <bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin >> s;
	if(s=="Sunny")
		cout << "Cloudy";
	if(s=="Cloudy")
		cout << "Rainy";
	if(s=="Rainy")
		cout << "Sunny";
	return 0;
}

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

class Node {
public:
  int location;
  int p, l, r;
  Node() {}
};

class Point {
public:
  int id, x, y;
  Point() {}
  Point(int id, int x, int y): id(id), x(x), y(y) {}
  bool operator < ( const Point &p) const {
    return id < p.id;
  }

  void print() {
    printf("%d\n", id);  // cout より高速な printf 関数を使用
  }
};

static const int MAX = 1000000;
static const int NIL = -1;

int N;
Point P[MAX];
Node T[MAX];
int np;

bool lessX(const Point &p1, const Point &p2) { return p1.x < p2.x; }
bool lessY(const Point &p1, const Point &p2) { return p1.y < p2.y; }

int makeKDTree(int l, int r, int depth) {
  if ( !(l < r) ) return NIL;
  int mid = ( l + r ) / 2;
  int t = np++;
  if ( depth % 2 == 0 )
    sort(P + l, P + r, lessX);
  else
    sort(P + l, P + r, lessY);
  T[t].location = mid;
  T[t].l = makeKDTree(l, mid, depth + 1);
  T[t].r = makeKDTree(mid + 1, r, depth + 1);

  return t;
}

void find(int v, int sx, int tx, int sy, int ty, int depth, vector<Point> &ans ) {
  int x = P[T[v].location].x;
  int y = P[T[v].location].y;

  if ( sx <= x && x <= tx && sy <= y && y <= ty )
    ans.push_back(P[T[v].location]);

  if ( depth % 2 == 0 ) {
    if ( T[v].l != NIL )
      if ( sx <= x ) find(T[v].l, sx, tx, sy, ty, depth + 1, ans);
    if ( T[v].r != NIL )
      if ( x <= tx ) find(T[v].r, sx, tx, sy, ty, depth + 1, ans);
  } else {
    if ( T[v].l != NIL )
      if ( sy <= y ) find(T[v].l, sx, tx, sy, ty, depth + 1, ans);
    if ( T[v].r != NIL )
      if ( y <= ty ) find(T[v].r, sx, tx, sy, ty, depth + 1, ans);
  }
}

int main() {
  int x, y;
  scanf("%d", &N);
  for ( int i = 0; i < N; i++ ) {
    scanf("%d %d", &x, &y);  // cin より高速な scanf 関数を使用
    P[i] = Point(i, x, y);
    T[i].l = T[i].r = T[i].p = NIL;
  }

  np = 0;

  int root = makeKDTree(0, N, 0);

  int q;
  scanf("%d", &q);
  int sx, tx, sy, ty;
  vector<Point> ans;
  for ( int i = 0; i < q; i++ ) {
    scanf("%d %d %d %d", &sx, &tx, &sy, &ty);
    ans.clear();
    find(root, sx, tx, sy, ty, 0, ans);
    sort(ans.begin(), ans.end());
    for ( int j = 0; j < ans.size(); j++ )
      ans[j].print();
    printf("\n");
  }

  return 0;
}


Measured memory_bytes: 15900
import numpy as np
N,D = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
count = 0
for i in range(N-1):
    x = np.array(X[i])
    for j in range(i+1,N):
        y = np.array(X[j])
        d = np.linalg.norm(x-y)
        if d - int(d) == 0:
            count += 1
print(count)

Measured memory_bytes: 14520
#include <iostream> // cin, cout, cerr, clog
#include <algorithm> // min, max, sort, swap
#include <numeric> // iota, accumulate, inner_product
#include <cmath> // long, trig, pow
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <stack> // stack
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <unordered_map> // hashed by keys
#include <unordered_set> // hashed by keys
#include <iomanip> // cout<<setprecision(n)
#include <functional> // std::function<void(int)>
using namespace std;
#define rep(i,n) rep1(i,0,n)
#define rep1(i,m,n) for(int i=m;i<(n);i++)
#define All(v) (v).begin(),(v).end()
using ll = long long;
const ll mod = 1000000007;
const ll INF = 100000000000000000LL;
const double PI = acos(-1);
int main(){
    int n;
    cin >> n;
    vector<int> h(n);
    rep(i, n) cin >> h[i];
    int res = h[0];
    rep1(i,1,n){
        if(h[i]>h[i-1])
            res += h[i] - h[i - 1];
    }
    cout << res << endl;
}

Measured memory_bytes: 256
use itertools::Itertools;

fn main() {
    let (n, m, x, mut c) = input();
    println!("{}", solve(n, m, x, &mut c))
}

fn input() -> (usize, usize, usize, Vec<Vec<usize>>) {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    buf.pop();
    let mut iter = buf.split_whitespace();
    let n: usize = iter.next().unwrap().parse().unwrap();
    let m: usize = iter.next().unwrap().parse().unwrap();
    let x: usize = iter.next().unwrap().parse().unwrap();

    let mut c: Vec<Vec<usize>> = Vec::new();
    for _ in 0..n {
        let mut buf = String::new();
        std::io::stdin().read_line(&mut buf).unwrap();
        buf.pop();
        let iter = buf.split_whitespace();
        c.push(iter.map(|v| v.parse().unwrap()).collect());
    }
    (n, m, x, c)
}

fn solve(n:usize, m:usize, x:usize, c: &mut Vec<Vec<usize>>) -> i64 {
   let mut ans = 100000000;
    for i in 1..n+1 {
        for v in (0..n).combinations(i) {
            if is_over_x(x, m, &v, c) {
                ans = std::cmp::min(ans, sum(&v, c));
            }
        }
    }
    if ans == 100000000 { return -1; }
    ans as i64
}

fn sum(buy: &Vec<usize>, c: &Vec<Vec<usize>>) -> usize {
    let mut res = 0;
    for i in buy.iter() {
        res += c[*i][0];
    }
    res
}

fn is_over_x(x: usize, m: usize, buy: &Vec<usize>, c: &Vec<Vec<usize>>) -> bool {
    let mut sum = vec![0usize; m];
    for i in buy.iter() {
        for j in 1..m+1 {
            sum[j-1] += c[*i][j]
        }
    }
    for s in sum.iter() {
        if *s < x { return false; }
    }
    true
}

Measured memory_bytes: 2172
from collections import deque
#S = deque(['x', 'y'])
#print(S)   ->   deque(['x', 'y'])
#popleft  ->  キュー
#pop  ->  スタック

stack = deque()

l = list(input().split())
for i in l:
    if i!='+' and i!='-' and i!='*':
        stack.append(int(i))
    else:
        b = stack.pop()
        a = stack.pop()
        if i=='+':
            stack.append(a+b)
        elif i=='-':
            stack.append(a-b)
        else:
            stack.append(a*b)
print(stack.pop())


Measured memory_bytes: 5996
while True:
    H, W = map(int, input().split())
    if (H == W == 0):
        break
    else:
        for j in range(H):
            if (j % 2 == 0):
                for i in range(W):
                    if(i % 2 == 0):
                        print("#", end='')
                    else:
                        print(".", end='')
            else:
                for f in range(W):
                    if(f % 2 == 0):
                        print(".", end='')
                    else:
                        print("#", end='')


            print()
        print()

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

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    int k;
    cin >> k;
    int cnt = 0;

    while(b <= a){
        b *= 2;
        cnt++;
    }
    while(c <= b){
        c *= 2;
        cnt++;
    }

    if(cnt <= k) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

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

int main() {
	long long int n,k,q;
	cin >> n >> k >> q;
	int a[q];
	int score[n];
	for(int i=0;i<n;i++){
		score[i] = k;
	}
	for(int i=0;i<q;i++){
		cin >> a[i];
		score[a[i]-1] ++;
	}
	
	for(int i=0;i<n;i++){
		if(score[i]>q) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	
	
	return 0;
}

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

bool is_prime(long long n){
    for(long long i = 2; i*i <= n; i++){
        if(n%i == 0) return false;
    }
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long x;
    cin >> x;
    while(!is_prime(x)){
        x++;
    }
    cout << x << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
    int t,r=0;
    char a[200003];
    int cnt=0;
    scanf("%d\n",&t);
    for(int i=0;i<t;i++)
    {
        scanf("%c",&a[i]);
        if(a[i]=='R')
        {
            r++;
        }
    }
    
    for(int i=0;i<r;i++)
    {
        if(a[i]=='W')
        {
            cnt++;
        }
    }
    printf("%d\n",cnt);
    return 0;
}


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

using namespace std;


#define rep(i,n) for(int i=0;i<(int)(n);i++)

int main(){
	int n;
	cin>>n;
	int  now=0;
	bool f=false;
	rep(i,n){
		char ch;
		int a;
		cin>>ch>>a;
		if(ch=='(')now+=a;
		else if( ch==')' )now-=a;

		if(now<0){
			f=true;
		}
	}
	if(now!=0)f=true;

	if(f)cout<<"NO"<<endl;
	else cout<<"YES"<<endl;
	return 0;
}

Measured memory_bytes: 1156
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in);) {
            solve(sc);
        }
    }

    public static void solve(Scanner sc) {
        int a = sc.nextInt();

        System.out.println("ABC" +a);
    }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
#define fol(i,n) for(int i=0;i<n;++i)
#define pb push_back
typedef long long ll;
typedef pair<int,int> P;
typedef vector<P> vip;

int main(){
  int n;cin>>n;
  int a[n];
  fol(i,n){cin>>a[i];}
  sort(a,a+n);
  long long ans = 0;
  long long b1=0,b2=0;
  if(n%2){
    int s = n/2;
    int mid = a[s];
    int am = a[0];
    int bm = a[s-1];
    int an = a[n-1];
    int bn = a[s+1];
    fol(i,n){
      if(i==s)continue;
      ans+= a[i]*(i<s?-2:2);
    }
    ans -= min({mid-am,bn-mid,an-mid,mid-bm});
  }else{
    int s = n/2;
    fol(i,n){
      ans+= a[i]*(i<s?-2:2);
    }
    ans -= min({a[s]-a[0],a[s]-a[s-1],a[n-1]-a[s-1],a[n-1]-a[0]});
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;

int main() {
    ios::sync_with_stdio(false);

    int N;
    cin >> N;

    vector<int> s(100000+1, 0);
    map<int, int> p;
    for (int i = 0, d; i < N; ++i) {
        cin >> d;
        s[d]++;
    }
    
    int ans = 0;
    for (int k = 1; k <= 100000; ++k) {
        s[k] += s[k-1];
        if (s[k] == N/2) ++ans;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 640
// Math = ♥️

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define ld long double
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define pq priority_queue
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define sz(c) ((ll)c.size())
// #define ordered_set                            \
//     tree<ll, null_type, less<ll>, rb_tree_tag, \
//          tree_order_statistics_node_update>

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n;
    cin >> n;

    vi arr(n);
    for (auto &it : arr) {
        cin >> it;
    }

    ll xoro = 0;
    for (int i = 2; i < n; i++) {
        xoro ^= arr[i];
    }

    ll ando = (arr[0] + arr[1] - xoro);
    if (ando < 0) {
        cout << "-1\n";
        return 0;
    }

    if (ando & 1ll) {
        cout << "-1\n";
        return 0;
    }

    ando /= 2;

    ll sum = arr[0] + arr[1];
    sum -= ando * 2;

    if (sum < 0) {
        cout << "-1\n";
        return 0;
    }

    if (sum & ando) {
        cout << "-1\n";
        return 0;
    }

    if (ando > arr[0]) {
        cout << "-1\n";
        return 0;
    }

    ll ans = ando;
    for (ll i = 60; i >= 0; i--) {
        if (sum & (1ll << i)) {
            if ((ans | (1ll << i)) <= arr[0]) {
                ans |= (1ll << i);
            }
        }
    }

    if (ans) {
        cout << arr[0] - ans << "\n";
    } else {
        cout << "-1\n";
    }
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
unordered_map<long long , int> um;

int main(){
  int N;cin >> N;
  vector<long long> V(N);
  for(auto&&e:V){
    cin >> e;
    um[e]++;
  }
  sort(V.begin(), V.end(), greater<long long>());
  int ans = 0;
  for(int i = 0; i < N; ++i){
    if(um[V[i]] < 1)continue;
    um[V[i]]--;
    long long nx = 1;
    while(nx <= V[i])nx<<=1;
    nx -= V[i];
    if(um.count(nx)==0)continue;
    int c = um[nx];
    if(c < 1)continue;
    um[nx]--;
    ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 10056
N=input()
a=0
k=0
for i in range(len(N)-1,-1,-1):
    n=int(N[i])+k
    if n<6:
        a+=n
        if n==5 and i!=0 and int(N[i-1])>4:
            k=1
        else:
            k=0
    elif n!=10:
        a+=10-n
        k=1
    else:
        a+=0
        k=1
a+=k
print(a)

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

bool check = true;
int main(){
    string s;
    cin >> s;
    int cnt = 0;
    int idx;
    if(s[0]!='A')check = false;
    for(int i=2;i<s.size()-1;i++){
        if(s[i]=='C'){
            cnt++;
            idx = i;
        }
    }
    if(cnt!=1)check=false;
    for(int i=1;i<s.size();i++){
        if(i!=idx){
            if(!islower(s[i]))check=false;
        }
    }
    if(check)cout << "AC" << endl;
    else cout << "WA" << endl;
    return 0;
}

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

#define rep(i, n) for(int i = 0; i < (n); ++i)

using namespace std;

int n, p;
int x[50];

int main(){
	while(scanf("%d%d", &n, &p), n){
		int c = 0;
		int q = p;
		while(1){
			if(q > 0){
				++x[c];
				--q;
				if(x[c] == p){
					printf("%d\n", c);
					break;
				}
			}
			else{
				q += x[c];
				x[c] = 0;
			}
			c = (c + 1) % n;
		}

		rep(i, n){
			x[i] = 0;
		}
	}
	return 0;
}

Measured memory_bytes: 1028
#include<bits/stdc++.h>
using namespace std;
namespace FAST_IO
{
	template<typename T> void read(T &a)
	{
		a=0;
		int f=1;
		char c=getchar();
		while(!isdigit(c))
		{
			if(c=='-')
			{
				f=-1;
			}
			c=getchar();
		}
		while(isdigit(c))
		{
			a=a*10+c-'0';
			c=getchar();
		}
		a=a*f;
	}
	template <typename T> void write(T a)
	{
		if(a<0)
		{
			a=-a;
			putchar('-');
		}
		if(a>9)
		{
			write(a/10);
		}
		putchar(a%10+'0');
	}
	template <typename T> void writeln(T a)
	{
		write(a);
		puts("");
	}
}
int n,t,ans=1001;
int main()
{
	cin>>n>>t;
	for(int i=1;i<=n;i++)
	{
		int ti,ci;
		cin>>ci>>ti;
		if(ti<=t)
		{
			ans=min(ans,ci);
		}
	}
	if(ans==1001)
	{
		cout<<"TLE";
	}
	else
	{
		cout<<ans;
	}
}


Measured memory_bytes: 256
N,M = (int(i) for i in input().split())
A = []
for i in range(N):
    a = str(input())
    a = list(a)
    A.append(a)

B = []
for i in range(M):
    b = str(input())
    b = list(b)
    B.append(b)
    
    
ans = 0
for i in range(N-M+1):
    for j in range(N-M+1):
        X = []
        Y = A[i:M+i]
        for k in range(M):
            x = Y[k][j:M+j]
            X.append(x)
        
        if X == B:
            ans = 1
if ans == 1:
    print('Yes')
else:
    print('No')
    

Measured memory_bytes: 3064
#include <iostream>
#include <iomanip> //! for setprecision(10)
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>

using namespace std;

typedef long long LL;

#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define rep(i,n) for (int i = 0; i < (n); ++i)

const int MOD = 1000000007;

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

    string S;
    int K;
    cin >> S >> K;

    int pos = 0;
    while (S[pos] == '1' && pos+1 < K) ++pos;

    cout << S[pos] << endl;

    return 0;
}


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

public class Main {
    private static final int MOD = (int) Math.pow(10, 9);

    public static void main(String[] args) {
        FastReader sc = new FastReader();
        int n = sc.nextInt();
        String str = sc.next();
        LinkedList<Character> stack = new LinkedList<>();

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);


                while (!stack.isEmpty() && stack.peek() == c) {
                    stack.pop();
                }
                stack.push(c);

        }
        System.out.println(stack.size());


        System.exit(0);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try{
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}


Measured memory_bytes: 25300
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <functional>
#include <assert.h>
#define int long
#define ll long long
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define SZ(x) x.size()
#define fi first
#define se second
const int INF = 1e9;
const int MOD = 1e9+7;
using namespace std;

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class T>
inline bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>
inline bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}

const int MX = 777777 + 5;
int fac[MX+5],inv[MX+5];
 
int power(int x,int y,int p){
	int res=1;
	x=x%p;
	while(y){
		if(y&1)res=(res*x)%p;
		y=y>>1;
		x=(x*x)%p;
	}
	return res;
}
void init(){
  int n=MX+4;
	fac[0] = 1;
  for(int i=0;i<n;++i)fac[i+1]=fac[i]*(i+1)%MOD;
  inv[n]=power(fac[n],MOD-2,MOD);
  for(int i=n-1;i>=0;--i)inv[i]=inv[i+1]*(i+1)%MOD;
}
// nPk = nCk * fac[k]
int comb(int n,int r){return (fac[n]*inv[r])%MOD*inv[n-r]%MOD;}

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

    int N,K; cin >> N >> K;
    int A[N]; rep(i,N) cin >> A[i];
    int ans=0;
    sort(A,A+N);
    per(i,N){
        if(i<K-1) break;
        ans=(ans+(A[i]*comb(i,K-1))%MOD)%MOD;
    }
    rep(i,N){
        if(N-i-1<K-1) break;
        ans-=(A[i]*comb(N-i-1,K-1))%MOD;
        ans%=MOD;
    }
    if(ans<0) ans+=MOD;
    cout << ans << endl;
}


Measured memory_bytes: 13184
function Main(input) {
  input = input.split("\n");
  var N = parseInt(input[0]);
  var ans = 0;
  var set = new Set();
  var N2=N;
  function isPrime(n) {
    if (isNaN(n) || !isFinite(n) || n%1 || n<2) return false; 
    var m=Math.sqrt(n);
    for (var i=2;i<=m;i++) if (n%i==0) return false;
    return true;
  }
  for(var i=2;i<Math.sqrt(N);i++){
    if(!set.has(i)&&isPrime(i)){
      var x =i;
      for(var j=1;x<N;j++){
        if(N2%Math.pow(i,j)==0){
          ans++;
          N2=N2/Math.pow(i,j);
        }else{
          break;
        }
        set.add(Math.pow(i,j));
        x=Math.pow(i,j+1);
      }
    }
  }
  if(N2>Math.sqrt(N)){
    ans++;
  }
  



  console.log('%s', ans);
  return ans;
}

function debug(n){
  var input = document.getElementById("input"+n).value;
  var ans=Main(input);
  var result="WA";
  if(ans==document.getElementById("output"+n).value.split("\n")[0]){
    result="AC";
  }
  document.getElementById("result"+n).innerHTML=result;
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

use std::{cell, cmp, collections, convert, fmt, io, iter, ops, str};

use cell::{Cell, RefCell};
use cmp::Ordering::{Equal, Greater, Less};
use collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque};
use io::{Read, Write};

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

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

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

#[cfg(not(feature = "debug"))]
macro_rules! debugln {
    ($($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() {
    let n = parse_line::<i32>();
    if n < 1000 {
        println!("ABC");
    } else {
        println!("ABD");
    }
}

#[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.is_empty() {
            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 = f64::from(x).sqrt().ceil() as i32;
    x == 2 || (2..(ceil + 1)).all(|i| x % i != 0)
}

fn bit_high(bits: u64, pos: u64) -> bool {
    bits & (1 << pos) != 0
}


Measured memory_bytes: 4352
package main

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

const (
	initialBufSize = 100000
	maxBufSize     = 10000000
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

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

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func nextInt4() (int, int, int, int) {
	return nextInt(), nextInt(), nextInt(), nextInt()
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func min(nums ...int) int {
	ret := nums[0]
	for _, v := range nums {
		if v < ret {
			ret = v
		}
	}
	return ret
}

// llの棒を一つにまとめて長さlに変えるためのコスト
func joinCost(ll []int, l int) int {
	if len(ll) == 0 {
		return 1 << 50
	}
	c, sum := 10*(len(ll)-1), 0
	for i := range ll {
		sum += ll[i]
	}
	return c + abs(l-sum)
}

// group: A, B, C, 使わない
func rec(l, group []int, n, id, a, b, c int) int {
	if id == n {
		ll := [][]int{[]int{}, []int{}, []int{}}
		for i := range group {
			if group[i] == 3 {
				continue
			}
			ll[group[i]] = append(ll[group[i]], l[i])
		}
		return joinCost(ll[0], a) + joinCost(ll[1], b) + joinCost(ll[2], c)
	}

	mp := 1 << 60
	for i := 0; i < 4; i++ {
		group[id] = i
		mp = min(mp, rec(l, group, n, id+1, a, b, c))
	}
	return mp
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, initialBufSize), maxBufSize)
	defer wt.Flush()

	n, a, b, c := nextInt4()
	l := nextInts(n)

	puts(rec(l, make([]int, n), n, 0, a, b, c))
}


Measured memory_bytes: 6272
#include <iostream>
using namespace std;
int N;
int numlist[210];
int main(void){
    cin >> N;
    int res = 0;
    for (int i = 0; i < N; ++i) cin >> numlist[i];
    while (true) {
        bool exist_odd = false;
        for (int i = 0; i < N; ++i) {
            if (numlist[i] %2 == 1) exist_odd = true ;
        }    
        if (exist_odd) break;
        for (int i = 0; i < N; ++i) numlist[i] /= 2;
        res += 1;
    }
    cout << res << endl;
  
    return 0;
}

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

string X, Y;
int v[1001][1001];

int  dp(string X, string Y) {
	int n = X.size();
	int m = Y.size();

	for (int i = 0; i <= n; i++) {
		v[i][0] = 0;											///０のテーブル
		for (int j = 0; j <= m; j++) {
			v[0][j] = 0;
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (X[i-1] == Y[j-1]) {
				v[i][j] = v[i - 1][j - 1] + 1;
			}
			else {
				v[i][j] = max(v[i - 1][j], v[i][j - 1]);
			}
		}
	}
	return v[n][m];
}

int main(void)
{
	int x;
	cin >> x;
	
	for (int i = 0; i < x; i++) {
		cin >> X >> Y;
		int ans = dp(X, Y);
		cout << ans << endl;
	}
	
	
}


Measured memory_bytes: 6960
v, e = gets.split.map(&:to_i)
ret = []
set = Array.new(v){ |i| i }
g = Array.new(v){ Array.new }
rg = Array.new(v){ Array.new }
e.times do
  s,t = gets.split.map(&:to_i)
  g[s] << t
  rg[t] << s
end
until set.empty?
  n = -1
  set.each do |i|
    if rg[i].empty?
      n = i
      break
    end
  end
  set.delete(n)
  ret << n
  g[n].each do |m|
    rg[m].delete(n)
    if rg[m].empty?
      set << m
    end
  end
end
ret.each{|v| p v}

Measured memory_bytes: 12704
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

    private static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static void main(final String[] args) throws IOException {
        FastReader in = new FastReader();
        PrintWriter out = new PrintWriter(System.out, true);

        char a = in.next().charAt(0);
        if (Character.isUpperCase(a)) {
            out.println('A');
        } else {
            out.println('a');
        }
    }
}


Measured memory_bytes: 32964
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)n; i++)
#define rep2(i, m, n) for(int i=(int)m; i<(int)n; i++)
#define ALL(vec) vec.begin(), vec.end()
typedef long long ll;
typedef long double ld;

int main(){
    int N, K;
    cin >> N >> K;
    vector<ll> p(N);
    rep(i, N) cin >> p[i];

    ll sum = 0;
    rep(i, K) sum += p[i];

    ll cmax = sum;
    rep(i, N-K){
        sum += p[i+K] - p[i];
        cmax = max(cmax, sum);
    }
    
    ld ans = ld(cmax + K) / 2.0;
    cout << setprecision(10) << ans << endl;
}

Measured memory_bytes: 1792
N = int(input())
A = list(input())
B = list(input())
C = list(input())
ans = 0
for i in range(N):
    if A[i] == B[i]:
        if A[i] != C[i]:
            ans += 1
    else:
        if A[i] == C[i]:
            ans += 1
        elif B[i] == C[i]:
            ans += 1
        else:
            ans += 2
print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
#include<cassert>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
const int inf = 1e9 + 7;
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
#define ceil(a, b) a / b + !!(a % b)

void outv(vector<int> v, vector<int> vv) {
    rep(i, v.size()) cout << v[i] << " "; cout << endl;
    rep(i, vv.size()) cout << vv[i] << " "; cout << endl;
}
int main() {
    //#.##....##....#..##..##.
    int n; cin >> n;
    string s; cin >> s;
    int i = 0;
    vector<int> v, vv;
    while (1) {
        int c = 0;
        while (s[i] == '#' && i < s.size()) {c++; i++;}
        //cout << i << endl;
        v.push_back(c);
        if (i == s.size()) break;
        c = 0;
        while (s[i] == '.' && i < s.size()) {c++; i++;}
        vv.push_back(c);
        if (i == s.size()) break;
    }
    if (s[s.size() - 1] == '.') v.push_back(0);
    if (vv.size() == 0) {cout << 0 << endl; return 0;}
    rrep(i, 1, v.size()) v[i] += v[i - 1];
    rrep(i, 1, vv.size()) vv[i] += vv[i - 1];
    //outv(v, vv);
    int ans = vv[vv.size() - 1];
    rrep(i, 1, v.size()) {
        ans = min(ans, vv[vv.size() - 1] - vv[i - 1] + v[i - 1]);
    }
    cout << ans << endl;
}



Measured memory_bytes: 1408
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int hoge(vector<vector<int>> vec, int x, vector<int> choice = {}, int pos = 0) {
  int n = static_cast<int>(vec.size());
  int m = static_cast<int>(vec[0].size()) - 1;

  if (pos == n) {
    int cost = 0;
    vector<int> asum(m, 0);
    for (auto &c : choice) {
      for (int i = 0; i < m; ++i)
        asum[i] += vec[c][i+1];
      cost += vec[c][0];
    }

    bool flag = true;
    for (auto &a : asum)
      if (a < x)
        flag = false;
    return flag ? cost : INT_MAX;
  }

  int cost_a, cost_b;
  cost_a = hoge(vec, x, choice, pos + 1);
  choice.push_back(pos);
  cost_b = hoge(vec, x, choice, pos + 1);
  return min(cost_a, cost_b);
}

int main() {
  int n, m, x;
  cin >> n >> m >> x;
  vector<vector<int>> vec(n, vector<int>(m + 1));
  for (auto &v1 : vec)
    for (auto &v2 : v1)
      cin >> v2;

  int ans = hoge(vec, x);
  cout << (ans != INT_MAX ? ans : -1) << endl;
}


Measured memory_bytes: 3572
import math
import sys

i=int(input())
def prime(i):
  k=[]
  num=i
  j=2
  while j*j<=num:
    if i%j==0:
      i//=j
      k.append(j)
    else:
      j+=1
  if i!=1:
    k.append(i)
  #k.append(1)

  return k

j=set(prime(i))
ans=i
for z in j:
  ans*=(1-1/z)
  
print(int(ans))


Measured memory_bytes: 5660
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
#define EPS (1e-10)
#define equals(a, b) (fabs((a) - (b)) < EPS)

class Point {
    public:
    double x, y;

    Point(double x = 0, double y = 0): x(x), y(y) {}

    Point operator + (Point p) { return Point(x + p.x, y + p.y); }
    Point operator - (Point p) { return Point(x - p.x, y - p.y); }
    Point operator * (double a) { return Point(x * a, y * a); }
    Point operator / (double a) { return Point(x / a, y / a); }

    double norm() { return x * x + y * y; }
    double abs() { return sqrt(norm()); }

    bool operator < (const Point &p) const {
        return x != p.x ? x < p.x : y < p.y;
    }

    bool operator == (const Point &p) const {
        return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;
    }
};

struct Segment {
    Point p1, p2;
};

typedef Point Vector;
typedef Segment Line;

double dot(Vector a, Vector b) {
    return a.x * b.x + a.y * b.y;
}

double cross(Vector a, Vector b) {
    return a.x * b.y - a.y * b.x; 
}

bool isOrthogonal(Vector a, Vector b) {
    return equals(dot(a, b), 0.0);
}

bool isOrthogonal(Point a1, Point a2, Point b1, Point b2) {
    return isOrthogonal(a1 - a2, b1 - b2);
}

bool isOrthogonal(Segment s1, Segment s2) {
    return equals(dot(s1.p2 - s1.p1, s2.p2 - s2.p1), 0.0);
}

bool isParallel(Vector a, Vector b) {
    return equals(cross(a, b), 0.0);
}

bool isParallel(Point a1, Point a2, Point b1, Point b2) {
    return isParallel(a1 - a2, b1 - b2);
}

bool isParallel(Segment s1, Segment s2) {
    return equals(cross(s1.p2 - s1.p1, s2.p2 - s2.p1), 0.0);
}

Point project(Segment s, Point p) {
    Vector base = s.p2 - s.p1;
    double r = dot(p - s.p1, base) / base.norm();
    return s.p1 + base * r;
}

int main()
{
    int q;
    double x1, x2, x3, y1, y2, y3;
    Segment s;

    cin >> x1 >> y1 >> x2 >> y2;
    s.p1 = Point(x1, y1);
    s.p2 = Point(x2, y2);
    
    cin >> q;
    for (int i = 0; i != q; ++i)
    {
        cin >> x3 >> y3;
        Point p3 = Point(x3, y3);
        Point e = project(s, p3);
        cout << fixed << setprecision(10) << e.x << " " << e.y << endl;
    }
    return 0;
}


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

using namespace std;

int main() {

	long long n,x;
	cin >> n >> x;

	vector<vector<long long>> b(n + 1, vector<long long>(5, 0));
	vector<long long> p(n + 1, 0);

	b[0] = { 0,0,1,0,0 };
	p[0] = 1;
	for (int i = 1; i < n+1; i++) {
		b[i][0] = 1;
		b[i][2] = 1;
		b[i][4] = 1;
		b[i][1] = b[i - 1][0] + b[i - 1][1] + b[i - 1][2] + b[i - 1][3] + b[i - 1][4];
		b[i][3] = b[i][1];
		p[i] = p[i - 1] * 2 + 1;
	}

	long long total = 0;
	long long totalp = 0;
	for (int i = n; i >= 0; i--) {
		for (int j = 0; j < 5; j++) {
			total += b[i][j];
			if (total == x) {
				if (j == 0) {cout << totalp << endl;}
				if (j == 1) { cout << totalp + p[i - 1] << endl; }
				if (j == 2) { cout << totalp + p[i - 1] + 1 << endl; }
				if (j == 3) { cout << totalp + 2 * p[i - 1] + 1 << endl; }
				if (j == 4) { cout << totalp + 2 * p[i - 1] + 1 << endl; }
				return 0;
			}
			else if (total > x) {
				total -= b[i][j];
				if (j == 3) { 
					totalp += p[i - 1]+1;
				}
				break;
			}
		}
	}

}

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

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

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

const double eps = 1e-10;

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

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

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

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

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

int main(void) {
  int64 n;
  int64 res = 0;
  vector<PLL> q;
  vector<int64> sum(100010, 0);
  cin >> n;
  REP(i, n) {
    int64 a, b;
    cin >> a >> b;
    sum[a] += 1;
    sum[b+1]--;
  }
  REP(i, sum.size()-1) sum[i+1] += sum[i];
  REP(i, sum.size()) {
    if (sum[i] >= i-1) {
      res = max(res, i-1);
    }
  }
  cout << res << endl;
}


Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); i++)
#define REP(i, d, n) for(int i=(d); i<(n); i++)
typedef long long ll;
const int mod = 1e9 + 7;
int main() {

    char a;
    cin >> a;

    char ans = a + 1;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pi acos(-1)
#define cross(a,b) (conj(a)*(b)).imag()
#define dot(a,b) (conj(a)*(b)).real()
#define vec(a,b) b-a
#define Reka ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
int arr[999999][4];
int n,k=0;
int cl[999999][4];
int f(int r,int c)
{
    if(r == n){
        return cl[r][c] = 0;
    }
    if(cl[r][c]!=-1)
    {
        return cl[r][c];
    }
    else{
     int ans = -1;
    for(int i=0;i<3;i++)
    {
       if(i == c )
            continue;
        else{
            ans = max(ans,f(r+1,i)+arr[r][i]);
        }
    }
    return cl[r][c] = ans;
    }
}

int main()
{
    Reka
    memset(cl,-1,sizeof(cl));
   cin>>n;
   for(int i=0;i<n;i++)
   {
      for(int j=0;j<3;j++)
      {
          cin>>arr[i][j];
      }
   }
cout<<f(0,4);
   return 0;
}


Measured memory_bytes: 24960
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9,mod=1e9+7;
typedef long long ll;
int read() {
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*f;
}
struct node {
	int to,next,v;
} a[2000001];
int head[2000001],cnt,vis[1000001];
void add(int x,int y,int v) {
	a[++cnt].to=y;
	a[cnt].next=head[x];
	a[cnt].v=v;
	head[x]=cnt;
}
int f[1001][10001];
int dp[1000001];
int DP(int i) {
	if(dp[i]>0) return dp[i];
	for(int j=head[i]; j; j=a[j].next)
		dp[i]=max(dp[i],DP(a[j].to)+a[j].v);
	return dp[i];
}
const int N=10000010;
int tot,ans;
vector<int> e[N];
queue<int> que;
int dis[N];
void topo() {
	ans=0;
	while(!que.empty()) que.pop();
	for(int i=1; i<=tot; i++)
		if(dis[i]==0)
			que.push(i);
	while(!que.empty()) {
		int q1,q2,q3;
		q1=que.front();
		que.pop();
		ans++;
		for(int j=0; j<e[q1].size(); j++) {
			dis[e[q1][j]]--;
			if(!dis[e[q1][j]]) {
				que.push(e[q1][j]);
			}
		}
	}
	if(ans!=tot) puts("-1"),exit(0);
}
main() {
	int n=read(),maxx=0,x,last;
	for(int i=1; i<=n; i++)
		for(int j=1; j<i; j++)
			f[j][i]=f[i][j]=++tot;
	for(int i=1; i<=n; i++)
		for(int j=1; j<n; j++) {
			x=read();
			if(j>1) add(f[i][last],f[i][x],1),dis[f[i][x]]++,e[f[i][last]].push_back(f[i][x]);
			last=x;
		}
	topo();
	for(int i=1; i<=tot; i++)
		maxx=max(DP(i),maxx);
	cout<<maxx+1<<endl;
}


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

int main() {

  int N;
  cin >> N;

  vector<int> v(N);
  int answer = 0;
  bool validate = false;
  for (int i = 0; i < N; i++) {
    int p;
    cin >> p;
    if ((p - 1) == i) {
      v[i] = 1;
      if (validate) {
        validate = false;
      } else {
        answer++;
        validate = true;
      }
    } else {
      validate = false;
    }
  }

  cout << answer << endl;

}

Measured memory_bytes: 640
n=int(input())
A=list(map(int,input().split()))
count=0
Sums=[]
for i in range(n):
  if A[i]<=0:
    count+=1
  Sums.append(abs(A[i]))
Sums=sorted(Sums)
if count%2==0:
  print(sum(Sums))
else:
  print(sum(Sums)-2*Sums[0])

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

string S,T;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>T;
	int ret=0;
	FOR(i,3) {
		if(S[i]==T[i]) ret++;
	}
	cout<<ret<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for(ll i = 0; i < (n); ++i )
#define rep_rev(n,i) for(ll i = n; i >= 0; --i )
using namespace std;
using P = pair<int, int>;
const long long INF = 1LL << 60;

int main(){
  int N,ans = 0; cin >> N;
  vector<int> A(N);
  rep(i,N) cin >> A[i];
  sort(A.begin(),A.end());
  rep(i,N){
    int j = i;
    while(A[i] == A[j]) j++;
    ans += (j-i) % 2;
    i += j-i-1;
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<vector<ll>> VV;

#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define rep(i, n) REP(i, 0, n)
const int INF=1e9;
const int MOD=1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define ALL(v) v.begin(), v.end()
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define REPM(i, mp) for (auto i = mp.begin(); i != mp.end(); ++i)
#define dbgmap(mp) for (auto i = mp.begin(); i != mp.end(); ++i) { cout << i->first <<":"<<i->second << endl;}
#define sum(v) accumulate(ALL(v),0)
#define fi first
#define se second

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

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len=v.size();
    for(int i=0; i<len; ++i) {
        s<<v[i];
        if(i<len-1) s<<" ";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    string t;
    ll cnt=0;
    cin>>s>>t;
    for(int i = 0; i < (int)s.size(); ++i){
        char chs = s[i];
        char cht = t[i];
        if (chs == cht){
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return  0;
}

Measured memory_bytes: 256
n = int(input())
p = list(map(int, input().split()))

ans = 0
for i in range(n-2):
    P = p[i], p[i+1], p[i+2]
    max_P = max(P)
    min_P = min(P)
    if p[i+1] != max_P and p[i+1] != min_P:
        ans += 1
print(ans)


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

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
typedef vector < ll > vl;

const int MAXN = 2e5 + 500;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int LOG = 18;
const double EPS = 1e-9;
const double PI = 3.1415926535;
const int OFF = 1 << 17;

struct block {
    int r, c;
};

vector <block> blocks;
int fact[MAXN];
int mult_inv[MAXN];
int dp[3005];

ll add(const ll& a, const ll& b) {
    if(a + b >= MOD)
        return (a + b - MOD);
    return (a + b);
}

ll subt(const ll& a, const ll& b) {
    if(a - b < 0)
        return (a - b + MOD);
    return (a - b);
}

ll mult(const ll& a, const ll& b) {
    return (a * b) % MOD;
}

ll power(int a, int N) {
    int res = 1;
    while(N > 0) {
        if(N & 1)
            res = mult(res, a);
        N = (N >> 1);
        a = mult(a, a);
    }
    return res;
}

void preprocess() {
    fact[0] = 1;
    mult_inv[0] = 1;
    for(int i = 1; i < MAXN; i++) {
        fact[i] = mult(i, fact[i - 1]);
        mult_inv[i] = power(fact[i], MOD - 2);  // a^(-1) = a^(MOD - 2) (% MOD)
    }
}

ll choose(int N, int K) {
    if(N < 0 || K < 0 || N < K)
        return 0;
    return mult(fact[N], mult(mult_inv[K], mult_inv[N - K]));
}

int main() {
    preprocess();
    int H, W, N;
    int r, c, c1, r1;

    scanf("%d%d%d", &H, &W, &N);
    for(int i = 0; i < N; i++) {
        scanf("%d%d", &r, &c);
        blocks.push_back(block{r, c});
    }

    blocks.push_back(block{H, W});
    sort(blocks.begin(), blocks.end(), [](const block& a, const block& b) {
        return (a.r + a.c < b.r + b.c);
    });

    // counting on first block contacted
    for(int i = 0; i <= N; i++) {
        c = blocks[i].c;
        r = blocks[i].r;
        dp[i] = choose(r + c - 2, r - 1);
        for(int j = 0; j < i; j++) {
            c1 = blocks[j].c;
            r1 = blocks[j].r;
            if(r1 <= r && c1 <= c)
                dp[i] = subt(dp[i], mult(dp[j], choose(r - r1 + c - c1, r - r1)));
        }
    }

    cout << dp[N] << endl;

    return 0;
}



Measured memory_bytes: 1920