akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define SORT(x) sort(x.begin(),x.end())
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

ll n,k;
vector<ll> a;
ll calc(ll p){
    ll ret=0;
    rep(i,n){
        ret+=(p^a[i]);
    }
    return ret;
}
int main(){
    cin>>n>>k;
    a.resize(n);
    ll sum=0;
    for(ll i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    //クソだろk>0でいいだろ
    if(k==0){
        cout<<sum<<endl;return 0;
    }

    ll bitlen=0,ck=k;
    while(ck>0){
        ck/=2;bitlen++;
    }
    vector<ll> count(bitlen,0);
    //桁ごと0のほうが多ければcountの値が0より大きい
    for(ll i=0;i<n;i++){
        for(int j=0;j<bitlen;j++){
            if((a[i]&(1ll<<j))>0){
                count[j]--;
            }
            else{
                count[j]++;
            }
        }
    }
    //これでbitごとの多数決ができるようになった
    //0のが多ければcount>0だし少なければcount<0
    //あとはkを超えないようにxを作ればいい

    ll x=0;
    bool flag=false;
    for(ll bit=bitlen-1;bit>=0;bit--){
        if(flag){
            if(count[bit]>0){
                x=x^(1ll<<bit);
            }
            continue;
        }
        if(count[bit]<=0){
            if((k&(1ll<<bit))>0){flag=true;}
        }
        else{
            if((k&(1ll<<bit))>0){
                x=x^(1ll<<bit);
            }
        }
    }
    cout<<calc(x)<<endl;
    return 0;
}


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

#define ll long long int
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR1(i, m, n) for(int i=m; i<n; i++)
#define FOR2(i, n, m) for(int i=n-1; i>=m; i--)

using namespace std;

int main(int argc, char const *argv[])
{
	FASTIO;
	int arr[3][3];
	for (int i = 0; i < 3; ++i)
	{
		for (int j = 0; j < 3; ++j)
		{
			cin >> arr[i][j];
		}
	}
	int n; cin >> n;
	int ans[3][3]={ {0,0,0},
					{0,0,0},
					{0,0,0}};
	int count=0;
	for (int i = 0; i < n; ++i)
	{
		int x;
		cin >> x;
		for (int i = 0; i < 3; ++i)
		{	
			for (int j = 0; j < 3; ++j)
			{
				if (arr[i][j] == x)
				{
					count++;
					ans[i][j] = 1;
				}
			}
		}	
	}
	int row[3] = {0};
	int col[3] = {0};
	int di=0;
	int di2 = 0;
	if (count >= 3)
	{
		for (int i = 0; i < 3; ++i)
		{
			for (int j = 0; j < 3; ++j)
			{
				if (ans[i][j]==1)
				{
					if (i==j)
					{
						di++;
					}
					if (i==0)
					{
						row[0]++;
					}
					else if (i==1)
					{
						row[1]++;
					}
					else
					{
						row[2]++;
					}
					if (j==0)
					{
						col[0]++;
					}
					else if (j==1)
					{
						col[1]++;
					}
					else
					{
						col[2]++;
					}
				}
			}
		}
		if (ans[0][2] == 1 && ans[1][1] == 1 && ans[2][0]==1)
		{
			di2 = 4;
		}
		if (row[1] >= 3 || row[0] >= 3 || row[2] >=3)
		{
			cout << "Yes"<<"\n";
		}
		else if(col[1] >= 3 || col[0] >= 3 || col[2] >=3)
		{
			cout << "Yes"<<"\n";
		}
		else
		{
			if (di >= 3)
			{
				cout << "Yes"<<"\n";		
			}
			else if (di2 >=3)
			{
				cout << "Yes"<<"\n";	
			}
			else
				cout << "No"<<"\n";
		}
	}
	else
	{
		cout << "No" << "\n";
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int id[1000010];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<n;++i)
	{
		int number;
		scanf("%d",&number);
		id[number]++;
	}
	for(int i=1;i<=n;i++)
	{
		cout<<id[i]<<endl;
	}
	return 0;
}

Measured memory_bytes: 4436
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <iomanip>

using namespace std;

bool cmp(tuple<int, int, int> n, tuple<int, int, int> m)
{
    if (get<0>(n) == get<0>(m)) // id
	return get<1>(n) < get<1>(m); // year
    else
	return get<0>(n) < get<0>(m);
}


int main()
{
    int n, m;
    cin >> n >> m;
    
//    vector<pair<int, int>> res;
//    res.reserve(m);
    pair<int, int> res[m];

    vector<tuple<int, int, int>> src;
    for (int i = 0; i < m; i++) {
	int a, b;
	cin >> a >> b;
	src.push_back(tie(a, b, i)); /* 県番号、　誕生年、　入力番号 */
    }

    sort(src.begin(), src.end(), cmp);

    int prefe = 0;
    int num = 1;
    for (auto i = src.begin(); i != src.end(); i++) {
	if (prefe == get<0>(*i))
	    num++;
	else
	    num = 1;
	res[get<2>(*i)] = make_pair(get<0>(*i), num);
	prefe = get<0>(*i);
    }

    for (pair<int, int> p : res) {
	cout << setw(6) << setfill('0') << p.first;
	cout << setw(6) << setfill('0') << p.second << endl;
    }

    return 0;
}


Measured memory_bytes: 3572
#include <iostream>
#include <iomanip> // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple> // get<n>(xxx)
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set> // S.insert(M);
// if (S.find(key) != S.end()) { }
// for (auto it=S.begin(); it != S.end(); it++) { }
// auto it = S.lower_bound(M);
#include <random> // random_device rd; mt19937 mt(rd());
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib> // atoi(xxx)
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.
// insert #if<tab> by my emacs. #if DEBUG == 1 ... #end

typedef long long ll;

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

// const int C = 1e6+10;
// const ll M = 1000000007;

const int N = 50;

int main () {
  ll K;
  cin >> K;
  ll ans[N];
  for (auto i = 0; i < N; ++i) {
    ans[i] = i + (K-1)/N;
  }
  for (auto i = N-(K-1)%N - 1; i < N; ++i) {
    ans[i]++;
  }
  cout << N << endl;
  for (auto i = 0; i < N; ++i) {
    cout << ans[i];
    if (i < N-1) {
      cout << " ";
    } else {
      cout << endl;
    }
  }
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
  int a, b, c, d;
  scanf("%d %d %d", &a, &b, &c);
  int flag = 0;
  for(int i = 0; i < b; i++){
    d = a % b;
    d *= i;
    if(d % b == c) flag = 1;
  }
  if(flag) printf("YES\n");
  else printf("NO\n");
  return 0;
}


Measured memory_bytes: 128
import sys
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
def I():
    s = input()
    mi = 0
    su = 0
    t = 0
    for a in s:
        if a == "(":
            t += 1
        else:
            t -= 1
            mi = min(mi, t)
    return (mi, t)

X = [I() for _ in range(N)]
if sum([x[1] for x in X]):
    print("No")
    exit()

X = sorted(X, key = lambda x: -10**10 if x[0] == 0 else -10**9 - x[0] if x[1] > 0 else x[0] - x[1])
T = 0
for mi, t in X:
    if T + mi < 0:
        print("No")
        exit()
    T += t
print("Yes")

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

int main(){
  int n,m;
  int k;
  int d[333];
  int dd[333];
  int t1[111];
  int t2[111];
  for(int i=0;i<200;i++){
    d[i] = i+1;
  }
  
  scanf(" %d",&n);
  scanf(" %d",&m);
  
  n*=2;
  for(int i=0;i<m;i++){
    scanf(" %d",&k);
    
    if(k==0){
      
      for(int i=0;i<n/2;i++){
	t1[i] = d[i];
	t2[i] = d[i+n/2];
      }
      
      for(int i=0;i<n;i++){
	if(i%2==0){
	  d[i] = t1[i/2];
	} else {
	  d[i] = t2[i/2];
	}
      }
      
    } else {
      
      for(int i=0;i<n;i++){
	dd[i] = d[i];
      }
      for(int i=0;i<n;i++){
	d[i] = dd[(i+k)%n];
      }
    }
    
  }
  for(int i=0;i<n;i++){
    printf("%d\n",d[i]);
  }

  return(0);
}

Measured memory_bytes: 3196
#include <algorithm>
#include <numeric>
#include <map>
#include <vector>
#include <cmath>
#include <iostream>

using namespace std;

const int maxn = 22, maxk = 12, maxs = 157;
int dp[maxn][maxk][maxs];

int rec(int n, int k, int s) {
  if (k < 0) return 0;
  if (dp[n][k][s] < 0) {
	int res = 0;
	for (int i = 1; i < n; i++) {
	  res += rec(i, k-1, s-i);
	}
	dp[n][k][s] = res;
  }
  return dp[n][k][s];
}

int main() {
  fill_n(dp[0][0], maxn*maxs*maxk, -1);
  for (int n = 0; n < maxn; n++)
	dp[n][0][0] = 1;
  while (true) {
	int p, q, r;
	cin >> p >> q >> r;
	if (p == 0 && q == 0 && r == 0) break;
	cout << rec(p+1, q, r) << endl;
  }
}

Measured memory_bytes: 1320
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans = count = 0

n,x=map(int,input().split())
L=list(map(int,input().split()))
for i in range(n):
    count+=L[i]
    if count<=x:
        ans+=1
print(ans+1)

Measured memory_bytes: 3932
import java.io._
import java.util.StringTokenizer
import scala.util.control.Breaks.{breakable,break}
import scala.collection.mutable.PriorityQueue


object Main extends App {
  val in = new InputReader(System.in)
  val pw = new PrintWriter(System.out)

  val pq = new PriorityQueue[Int]
  val N, M = in.next().toInt

  val a = new Array[Int](M)
  val b = new Array[Int](M)
  for(i <- 0 until M) {
    val x, y = in.next().toInt
    a(i) = x
    b(i) = y
  }

  val _leftTo = new Array[(Int, Int)](M)
  for(i <- 0 until M) {
    _leftTo(i) = (a(i), b(i))
  }
  val leftTo = _leftTo.sorted

  var ans = 0
  for((a, b) <- leftTo) {
    if(pq.isEmpty)
      pq.enqueue(-b)
    else {
      val now = -pq.head
      if(now <= a){
        ans += 1
        pq.clear
        pq.enqueue(-b)
      }
      else {
        pq.enqueue(-b)
      }
    }
  }

  if(!pq.isEmpty) {
    ans += 1
  }
    

  println(ans)
}


class InputReader(stream: InputStream) {
  private val reader = new BufferedReader(new InputStreamReader(stream))
  private var tokenizer: StringTokenizer = new StringTokenizer(reader.readLine())
  def next(): String = {
    while (!tokenizer.hasMoreTokens()) {
      tokenizer = new StringTokenizer(reader.readLine())
    }
    tokenizer.nextToken()
  }
}


Measured memory_bytes: 69180
def main():
    N, Q = [int(v) for v in input().split()]

    Query = [[int(v)-1 for v in input().split()] for _ in range(Q)]

    rows = [N-1] * (N - 1)
    cols = [N-1] * (N - 1)

    black = (N - 2) * (N - 2)
    min_row = N - 1
    min_col = N - 1

    for ty, x in Query:
        if ty == 0:
            if x < min_col:
                for j in range(x, min_col):
                    rows[j] = min_row
                min_col = x
            black -= rows[x] - 1
        else:
            if x < min_row:
                for j in range(x, min_row):
                    cols[j] = min_col
                min_row = x
            black -= cols[x] - 1

    print(black)

main()

Measured memory_bytes: 38980
package main

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

var (
	readString func() string
	stdout     *bufio.Writer
)

func init() {
	readString = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()
	}
	return b
}

func readLengthAndSlice() []int {
	n := readInt()
	return readIntSlice(n)
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func minInt(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func minUint(a, b uint) uint {
	if a < b {
		return a
	}
	return b
}

func minInt64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func minUint64(a, b uint64) uint64 {
	if a < b {
		return a
	}
	return b
}

func maxInt(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func maxUint(a, b uint) uint {
	if a < b {
		return b
	}
	return a
}
func maxInt64(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}

func maxUint64(a, b uint64) uint64 {
	if a < b {
		return b
	}
	return a
}

func absInt(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func absInt64(a int64) int64 {
	if a < 0 {
		return -a
	}
	return a
}

// readString() string
// readInt() int
// readIntSlice(n int) []int
// readLengthAndSlice() []int
func main() {
	defer stdout.Flush()

	n := readInt()

	fn := 0
	for m := n; m > 0; m /= 10 {
		fn += m % 10
	}
	if n%fn == 0 {
		println("Yes")
	} else {
		println("No")
	}
}


Measured memory_bytes: 640
import java.util.*;
import java.io.PrintWriter;
import static java.lang.Integer.*;
import static java.lang.Long.*;
import static java.lang.Math.*;
import static java.lang.System.*;

public class Main {
	public static final int N = 10001;
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(in);
		long x = parseLong(sc.next());
		sc.close();
		long[] fi = new long[N];
		for (i = 1; i < N; i++) {
			fi[i] = (long)i*i*i*i*i;
		}
		int idx=0;
		for (i = 0; i < N; i++) {
			long tmp=fi[i]-x;
			int sig=1;
			if(tmp<0) {
				sig=-1;
				tmp=-tmp;
			}
			idx = Arrays.binarySearch(fi, tmp);
//			out.println(idx);
			if(idx>=0) {
				idx*=sig;
				break;
			}
		}
		int a=i;
		int b=idx;
//		while(true) {
//			if(fi[a]-fi[b]==x) {
//				break;
//			}
//			if(fi[a]+fi[b]==x) {
//				b=-b;
//				break;
//			}
//			if(fi[a]-fi[b]<x) {
//				a++;
//			} else {
//				b--;
//			}
//		}
//		long p=0;
//		if(x==1) {
//			p=1;
//		} else {
//			if(x%2==0) {
//				p=2;
//			} else {
//				for (i = 3; i*i <= x; i+=2) {
//					if(x%i==0) {
//						p=i;
//						break;
//					}
//				}
//				if(p==0) {
//					p=x;
//				}
//			}
//		}
//		long b = 0;
//		for (i = x/p; i >= 0; i--) {
//			b = i - p;
//			if(i*i*i*i*i-b*b*b*b*b==x) break;
//		}
		out.printf("%d %d%n", a, b);
	}
}


Measured memory_bytes: 27088
#include<iostream>
#include<string>

using namespace std;

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

	return 0;
}


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

int main() {
  int a, b;
  std::cin >> a >> b;
  if (a == b) std::cout << "Draw\n";
  else if (a == 1) std::cout << "Alice\n";
  else if (b == 1) std::cout << "Bob\n";
  else std::cout << (std::max(a, b) == a ? "Alice\n" : "Bob\n");
  return 0;
}


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

int main() {
    ll n;cin>>n;
    ll sum=0;
    vector<ll>v(n,0);
    unordered_map<ll,ll>M;
    for(ll i=0;i<n;i++){cin>>v[i];sum+=v[i];};
    for(ll i=0;i<n;i++){
        M[v[i]]++;
    }
    ll q;cin>>q;
    while(q--){
        ll a,b;cin>>a>>b;
        ll ans=(ll)M[a]*(ll)(b-a);
        M[b]+=M[a];
        M[a]=0;
        sum=(ll)sum+(ll)ans;
        cout<<sum<<endl;
    }
	// your code goes here
}


Measured memory_bytes: 7888
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb               push_back
#define sz(c)            (int)c.size()
#define len(c)           (int)c.length()
#define vec              vector
#define int              long long int
#define mp(x,y)          make_pair(x,y)
#define all(c)           c.begin(), c.end()
#define rall(c)          c.rbegin(), c.rend()
#define trav(a,i)        for(auto& i: a)
#define loop(n,i,a)      for(int i=a;i<n;i++)
#define invect(v,n)       for(int i=0;i<n;i++ ){int arb;cin>>arb;v.pb(arb);}
#define inset(s,n)        loop(n,i,0){int aset;cin>>aset;s.insert(aset);}
#define display(c)        trav(c,i) cout<<i<<" ";
#define F                 first
#define S                 second
#define pii               pair<int,int>
#define pp               pop_back
#define endl              "\n"
#define copy(a,b)         copy(all(a),back_inserter(b));
#define intersect(a,b,w)    set_intersection(a.begin(), a.end(),b.begin(), b.end(),back_inserter(w));
#define union(a,b,w)      set_union(a.begin(), a.end(),b.begin(), b.end(),back_inserter(w));
#define diff(a,b,w)       set_difference(a.begin(), a.end(),b.begin(), b.end(),back_inserter(w));
#define symdiff(a,b,w)    set_symmetric_difference(a.begin(), a.end(),b.begin(), b.end(),back_inserter(w));
//int m=10000009;
//int arr[100000];
#define M                   1000000007
#define mm  998244353  
//set<int> st;
signed main()
{
    fast
    int n;
    cin>>n;
    int a[n];
    int cnt[n+1]= {0};
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        cnt[a[i]]++;
    }
    int val = 0;
    for(int i=1;i<=n;i++)
    {
        val += cnt[i]*(cnt[i]-1)/2;
    }
    for(int i=0;i<n;i++)
    {
        cout << val - (cnt[a[i]]-1) << endl;
    }
}


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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

int dist_2(int* x1, int* x2, int d) {
  int ret = 0;
  for (int i = 0; i < d; i++) {
    ret += abs(x1[i] - x2[i]) * abs(x1[i] - x2[i]);
  }

  return ret;
}

bool is_2(int a) {
  for (int i = 1; (i * i) <= a; i++) {
    if (i * i == a) {
      return true;
    }
  }
  return false;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, d;
  cin >> n >> d;
  int x[10][10] = {};
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < d; j++) {
      cin >> x[i][j];
    }
  }

  // for (int i = 0; i < 10; i++) {
  //   for (int j = 0; j < 10; j++) {
  //     printf("%d ", x[i][j]);
  //   }
  //   printf("\n");
  // }
  // printf("\n");

  int ans = 0;
  for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
      int dis = dist_2(x[i], x[j], d);
      // printf("dis=%d\n", dis);
      if (is_2(dis)) {
        ans++;
      }
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
N= int(input())
Xlist= list(map(int,input().split()))


from decimal import Decimal, ROUND_HALF_UP

y = Decimal(str(sum(Xlist)/N))
#四捨五入
P = y.quantize(Decimal('0'), rounding=ROUND_HALF_UP)


num=0
for i in range(len(Xlist)):
    num += (Xlist[i]-P)**2

print(num)

Measured memory_bytes: 5460
#include <iostream>
#include <iomanip>
#include <limits>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <unordered_map>
#include <random>
#define _USE_MATH_DEFINES
#include <cmath>
#include <complex>
#include <cfloat>
 
using namespace std;
 
#define INFD numeric_limits<double>::infinity()
#define INFL (int)1e8
#define INFLL (long long)1e15
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
#define bitmanip(m,val) static_cast<bitset<(int)m>>(val)
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
 
/*******************************************************/
 
int main() {
  int n; cin >> n;
  vll a(n); Loop(i, n) cin >> a[i];
  ll val[2];
  Loop(i, n) {
    val[a[i] % 2]++;
  }
  if (val[1] % 2) {
    cout << "NO" << endl;
  }
  else cout << "YES" << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> Zalgorithm(auto S){
    vector<int> res(S.size());
    res[0] = S.size();
    int i = 1, j = 0;
    while (i < S.size()) {
        while (i+j < S.size() && S[j] == S[i+j]) ++j;
        res[i] = j;
        if (j == 0) { ++i; continue;}
        int k = 1;
        while (i+k < S.size() && k+res[k] < j) res[i+k] = res[k], ++k;
        i += k; j -= k;
    }
    return res;
}

int main(){
    int N;
    while(cin >> N){
        string S; cin >> S;
        int res = 0;
        for(int i=0;i<N;i++){
            auto v = Zalgorithm(S.substr(i));
            for(int j=1;j<v.size();j++){
                res = max(res, min(j, v[j]));
            }
        }
        cout << res << endl;
    }
}

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

int main(){
    int a, b, k;
    cin >> a >> b >> k;

    vector<int> vec;

    for(int i = 1;i <= min(a, b);i++){
        if(a % i == 0 && b % i == 0){
            vec.push_back(i);
        }
    }

    cout << vec[vec.size()-k] << endl;
    return 0;
}



Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)
N = int(input())
dp = [-1] * (N + 1)

def rec(n):
    if n == 0:
        return 0
    if dp[n] != -1:
        return dp[n]
    res = n
    i = 0
    while n >= 6 ** i:
        pow6 = 6 ** i
        res = min(res, rec(n - pow6) + 1)
        i += 1
    j = 0
    while n >= 9 ** j:
        pow9 = 9 ** j
        res = min(res, rec(n - pow9) + 1)
        j += 1
    dp[n] = res
    return res
print(rec(N))

Measured memory_bytes: 89716
N = int(input())
st = input().split()
A = [0 for i in range(N)]
for i in range(N):
  A[i] = int(st[i])

A.sort(reverse = True)
U = []
for i in range(N-1):
  if A[i] == A[i+1]:
    U.append(A[i])
    A[i] = -1
    A[i+1] = -1
  if len(U) >= 2:
    break
if len(U) >= 2:
	print(U[0] * U[1])
else:
  print(0)


Measured memory_bytes: 14672
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
typedef long long LL;

const int MaxN = 100000;
const int Top = 1e9 + 7;
int n, father[MaxN + 5];
struct Point {
	int x, y, num;
}a[MaxN + 5];
struct EDGE {
	int u, v, w;
}edge[MaxN * 2];

bool cmp(Point A, Point B) {
	if (A.x == B.x) return A.y < B.y;
	return A.x < B.x;
}

bool cmp2(Point A, Point B) { 
	if (A.y == B.y) return A.x < B.x;
	return A.y < B.y;
}

bool cmp1(EDGE A, EDGE B) {
	return A.w < B.w;
}

int Find(int x)
{
	if (father[x] == x) return x;
	return father[x] = Find(father[x]);
}

int main()
{
	while (~scanf("%d", &n)) {
		for (int i = 1; i <= n; i++) {
			scanf("%d%d", &a[i].x, &a[i].y);
			a[i].num = i;
		}
		int tot = 0;
		sort(a + 1, a + n + 1, cmp);
		for (int i = 2; i <= n; i++) {
			edge[++tot].u = a[i].num;
			edge[tot].v = a[i - 1].num;
			edge[tot].w = abs(a[i].x - a[i - 1].x);
		}
		sort(a + 1, a + n + 1, cmp2);
		for (int i = 2; i <= n; i++) {
			edge[++tot].u = a[i].num;
			edge[tot].v = a[i - 1].num;
			edge[tot].w = abs(a[i].y - a[i - 1].y);
		}
		sort(edge + 1, edge + tot + 1, cmp1);
		for (int i = 1; i <= n; i++) father[i] = i;
		int ans = 0;
		for (int i = 1; i <= tot; i++) {
			if (Find(edge[i].u) != Find(edge[i].v)) {
				//printf("%d %d %d\n", edge[i].u, edge[i].v, edge[i].w);
				father[Find(edge[i].u)] = edge[i].v;
				ans += edge[i].w;
			}
		}
		printf("%d\n", ans);
	}
}

Measured memory_bytes: 4096
M=10**9+7
def extended_gcd(a, b)
  last_remainder, remainder = a.abs, b.abs
  x, last_x, y, last_y = 0, 1, 1, 0
  while remainder != 0
    last_remainder, (quotient, remainder) = remainder, last_remainder.divmod(remainder)
    x, last_x = last_x - quotient*x, x
    y, last_y = last_y - quotient*y, y
  end
 
  return last_remainder, last_x * (a < 0 ? -1 : 1)
end
def invmod(e)
  g, x = extended_gcd(e,M)
  x % M
end

n,*xs=$<.read.split.map(&:to_i)
np=n-1
npf=(2..np).reduce(1){|s,e| s*e%M }
npfh=npf*invmod(2)%M

s=(xs[np]*(2..np).reduce(npf){|s,e| s+npf*invmod(e) }-xs[np-1]*npf)%M
ts=t=npfh
2.step(np){|i|
  s=(s-xs[i-2]*npf+xs[i-1]*ts)%M
  ts+=t=t*(i-1)*invmod(i+1)%M
}
puts s

Measured memory_bytes: 11900
// failed to generate code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;

vector<P> G[200001];
bool check[200001];
ll color[200001];

void dfs() {
	queue<P> que;
	que.push(P(1,0));
	check[0] = true;
	color[0] = -1;
	while (!que.empty()) {
		P p = que.front(); que.pop();
		check[p.first] = true;
		ll now = 1;
		for (int i = 0; i < G[p.first].size(); i++) {
			ll to = G[p.first][i].first, h = G[p.first][i].second;
			if (!check[to]) {
				// cout << to << " " << h << " " << color[p.second] << endl;
				if (now == color[p.second]) now++;
				color[h] = now;
				que.push(P(to,h));
				now++;
			}
		}
	}
}

int main(){	
	ll N;
	cin >> N;
	vector<ll> a(N-1), b(N-1);
	rep(i, N-1) {
		cin >> a[i] >> b[i];
		G[a[i]].push_back(P(b[i],i+1));
		G[b[i]].push_back(P(a[i],i+1));
	}
	G[0].push_back(P(1,0));
	G[1].push_back(P(0,0));
	dfs();
	ll n = 0;
	repn(i, N-1) {
		n = max(n,color[i]);
	}
	cout << n << endl;
	repn(i, N-1) {
		cout << color[i] << endl;
	}
}


Measured memory_bytes: 12828
function Main(input) {
  var tmp = input[0].split(" ");
  var x = parseInt(tmp[0], 10);
  var y = parseInt(tmp[1], 10);

  var total = 0;
  if (x == 1 && y == 1) {
    total += 400000;
  }
  if (x == 1) {
    total += 300000;
  }
  if (x == 2) {
    total += 200000;
  }
  if (x == 3) {
    total += 100000;
  }
  if (y == 1) {
    total += 300000;
  }
  if (y == 2) {
    total += 200000;
  }
  if (y == 3) {
    total += 100000;
  }

  console.log("%s", total);
}

Main(
  require("fs")
    .readFileSync("/dev/stdin", "utf8")
    .split("\n")
);


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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;

  if ((A + B) == (C + D)) {
    cout << "Balanced" << endl;
  }
  else {
    if ((A + B) < (C + D)) {
      cout << "Right" << endl;
    }
    else {
      cout << "Left" << endl;
    }
  }  
}


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

#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;

typedef tree<
ll,
null_type,
less<ll>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
// ordered_set X;
// *X.find_by_order(i) = ith largest element (counting from zero)
// X.order_of_key(k) = number of items in X < k (strict lt)


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

    int H, W;
    cin >> H >> W;

    vs grid(H);
    for (int i=0;i<H;i++) cin >> grid[i];

    vi minfliprow(W, H*W + 1);
    vvi minflip(H, minfliprow);

    minflip[0][0] = 0;
    for (int y=0;y<H;y++) {
        for (int x=0;x<W;x++) {
            if (x > 0) {
                if (grid[y][x] == grid[y][x-1]) {
                    minflip[y][x] = min(minflip[y][x], minflip[y][x-1]);
                } else {
                    minflip[y][x] = min(minflip[y][x], minflip[y][x-1] + 1);
                }
            }
            if (y > 0) {
                if (grid[y][x] == grid[y-1][x]) {
                    minflip[y][x] = min(minflip[y][x], minflip[y-1][x]);
                } else {
                    minflip[y][x] = min(minflip[y][x], minflip[y-1][x] + 1);
                }
            }
        }
    }

    int ans = minflip[H-1][W-1];
    if (grid[0][0] == '#') ans++;
    if (grid[H-1][W-1] == '#') ans++;

    cout << ans / 2 << endl;    

    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define bit(n) (1<<(n))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
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;}
int const INF = 1001001001;

long long com[51][51];


int main()
{
    com[0][0] = 1;
    for (int i = 1; i < 51; ++i) {
        for (int j = 0; j <= i; ++j) {
            com[i][j] += com[i-1][j];
            if (j > 0) com[i][j] += com[i-1][j-1];        
        }
    }

    ll n,a,b;
    cin >> n >> a >> b;
    vector<ll> v(n);
    rep(i,n) cin >> v[i];
    sort(all(v),greater<ll>());

    ll sum = 0, res = 0;
    rep(i,a) sum += v[i];

    //1種類
    if(v[0] == v[a-1]) {
        ll m = count(all(v), v[0]);
        for(int i = a; i <= b; ++i) res += com[m][i];
    }
    //2種類以上
    else {
        ll m = count(all(v), v[a-1]);
        ll cnt = 0;
        rep(i,a) cnt += (v[i] == v[a-1]);
        res = com[m][cnt];
    }

    cout << fixed << setprecision(10) << (double)sum/(double)a << endl;
    cout << res << endl;


    return 0;
}

Measured memory_bytes: 3812
import math
N,M = [int(x) for x in input().split()]
e = {}
a = {}
for j in range(2,int(math.sqrt(M)) +2):
  cnt=0
  while M%j==0:
    cnt+= 1
    M = M//j
  if cnt!=0:
    e[j]=cnt
if M!=1:
  e[M]=1
for j in range(2,int(math.sqrt(N))+2):
  cnt=0
  while N%j==0:
    cnt+= 1
    N = N//j
  if cnt!=0:
    a[j]=cnt
if N!=1:
  a[N]=1
b = a.keys() & e.keys()
print(len(b)+1)

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

int count(int n, int a[]) {
    int counter = 0;
    while (true) {
        for (int i=0; i<n; ++i) {
            if (a[i] %2 != 0) return counter;
            a[i] /= 2;
        }
        counter++;
    }
    return 0;
}

int main() {
    int n;
    cin >> n;
    int a[n];
    for (int i=0; i<n;++i) cin >> a[i];

    cout << count(n, a) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
ll mod_pow(ll x,ll n,ll mod) {
ll res=1;
  while(n>0) {
if(n&1) {
res=res*x%mod;
}
   x=x*x%mod;
    n>>=1;
  }
return res;
}
 




int main() {
ll N,K;
  cin>>N>>K;
  ll mod=1000000007;
  
  vector<ll> ans(K,0);
  
  
 

for(ll i=1;i<=min(K,N-K+1);i++) {
ll S=1;
  ll A=1;
  for(ll j=0;j<i-1;j++) {
S*=(K-1-j);
    S%=mod;
  }
  
  for(ll j=2;j<=i-1;j++) {
A*=mod_pow(j,mod-2,mod);
    A%=mod;
  }
ll B=1;
ll C=1;
  for(ll j=2;j<=i;j++) {
    C*=mod_pow(j,mod-2,mod);
    C%=mod;
  }
  for(ll j=0;j<i;j++) {
B*=(N-K+1-j);
    B%=mod;
  }
  B*=C;
  B%=mod;
 S*=A;
  S%=mod;
  ans[i-1]=(S*B)%mod;
}
  
  for(ll i=0;i<K;i++) {
cout<<ans[i]<<endl;
  }
}

  
  
  
  
  
  
  
  
  

Measured memory_bytes: 3636
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int, pair<int,int> > mypair;
int main(void){
vector<mypair> a;
	while(1){
int h,w;
cin>>h>>w;
if(h==0)break;
int s=h*h+w*w;
bool f=false;
int ah,aw,sa=150*150;

for(int j=1;j<150;j++){
	for(int i=j+1;i<=150;i++)
	{
	int s2=i*i+j*j;
	if(s==s2&&h!=j&&h!=i&&h<j){
	f=true;
	ah=j;
	aw=i;
	break;
	}
	if(s<s2){
	if(sa>s2){
		ah=j;
		aw=i;
		sa=s2;
	}
	break;
	}

	}

	if(f)break;	
	}
cout<<ah<<' '<<aw<<endl;
	}

return 0;
}



Measured memory_bytes: 3080
#include<stdio.h>
#include<math.h>
int main(void){
    double x1,x2,y1,y2,result;
    scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
    result=pow(x2-x1,(double)2)+pow(y2-y1,(double)2);
    printf("%.8lf\n",sqrt(result));
    return 0;
}


Measured memory_bytes: 2112
#include<iostream>
#include<vector>
#include <cmath>
#include <map>
#include <algorithm>
using namespace std;
int main(void){
   int N;
   cin >> N ;
   int a[4];
   a[0] = N/1000 ;
   a[1] = ( N % 1000 ) / 100 ;
   a[2] = ( N % 100) / 10 ;
   a[3] = N % 10 ;

   int count = 1;
   for(int i = 0; i < 4 ; i++){
       if(a[i] == a[i+1]){
           count ++;
       }
   }

   if(count >= 3){
       if(a[1]==a[2]){
       cout << "Yes" << endl;
       }else{
       cout << "No" << endl;
       }
   }else {
       cout << "No" << endl;
   }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>

int main()
{
	std::string S, T;
	std::cin >> S >> T;

	T.erase(T.begin() + T.size() - 1);

	if (T == S)
	{
		std::cout << "Yes\n";
	}
	else
	{
		std::cout << "No\n";
	}

	return 0;
}

Measured memory_bytes: 3596
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> P;
#define INF 10000000000000
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for(ll i = 1; i < (ll)(n); i++)
#define repN_1(i, n) for(ll i = 0; i < (ll)(n - 1); i++)
#define repM(i, n) for(ll i = (ll)(n - 1); i >= 0; i--)
#define repM1(i, n) for(ll i = (ll)(n - 1); i > 0; i--)
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

// 素因数分解
vector<P> prime_factor(ll n) {
    vector<P> ret;
    for (ll i = 2; i * i <= n; i++) {
        ll tmp = 0;
        while (n % i == 0) {
            tmp++;
            n /= i;
        }
        ret.push_back(make_pair(i, tmp));
    }
    if (n != 1) ret.push_back(make_pair(n, 1));
    return ret;
}
int main()
{
	cout << fixed << setprecision(18);

	ll n;
	cin >> n;

	vector<P> res;

    res = prime_factor(n);

    ll ans = 0;
    rep(i, res.size())
    {
        ll count = 0;
        while (res[i].second > count) {
            count++;
            ans++;
            res[i].second -= count;
        }
    }

    cout << ans << endl;

	return 0;
}

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

using namespace std;
using ll = long long;

int init();
int solve();

#define rep(i, a) for (int i = 0; i < (int) (a); i++)
#define reps(i, a, b) for (int i = (int) (a); i < (int) (b); i++)
#define rrep(i, a) for (int i = (int) a-1; i >= 0; i--)
#define rreps(i, a, b) for (int i = (int) (a)-1; i >= (int) (b); i--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define TRUE__  "Yes"
#define FALSE__ "No"
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x

#ifdef LOCAL
#define lcout(a) cout << a
#define lcoutln(a) cout << a << endl
#define lcerr(a) cerr << a
#define lcerrln(a) cerr << a << endl
#else
#define lcout(a) 
#define lcoutln(a) 
#define lcerr(a) 
#define lcerrln(a) 
#endif
#define MOD 1000000007
#define PI 3.141592653589793238462643383

signed main()
{
	init();
	solve();
}

int N;

int init()
{
	cin >> N;
	return 0;
}

int solve()
{
	int sum = 0;
	int x;
	for (x = 1; sum < N; x++) sum += x;
	reps(i, 1, x) {
		if (i != sum - N) cout << i << endl;
	}
	return 0;
}


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

print(' '.join(map(str,list)))
for i in range(1, n):
    insertNum = list[i]
    j = i - 1
    while j >= 0 and list[j] > insertNum:
        list[j+1] = list[j]
        j-=1
    list[j+1] = insertNum
    print(' '.join(map(str,list)))


Measured memory_bytes: 5592
#include <iostream>

using namespace std;

int main() {
    
    int M, N;
    cin >> N >> M;
    int a[100];
    size_t sum = 0;
    for (size_t i = 0; i < N; ++i) {
        cin >> a[i];
        sum += a[i];
    }
    double k = (double)sum / (4.0 * M);
    size_t cnt = 0;
    for (size_t i = 0; i < N; ++i) {
        if (a[i] >= k) ++cnt;
    }
    if (cnt >= M) cout << "Yes";
    else cout << "No";

    return 0;
}

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

int main(){
    int n,m;
    cin >> n >> m;
    int x[m];
    for(int i = 0; i < m; i++){
        cin >> x[i];
    }
    sort(x, x+m);
    if(m == 1){
        cout << 0 << endl;
        return 0;
    }

    int p[m-1];
    for(int i = 0; i < m-1; i++){
        p[i] = x[i+1] - x[i];
    }
    sort(p,p+m-1);
    for(int i = 0; i < n-1; i++){
        p[m-2-i] = 0;
    }
    long long sum = 0;
    for(int i = 0 ; i < m-1; i++){
        sum += p[i];
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 1024
import sys
input = sys.stdin.readline


class Vector():
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __add__(self, vec):
        return Vector(self.x+vec.x, self.y+vec.y)

    def __sub__(self, vec):
        return Vector(self.x-vec.x, self.y-vec.y)

    def __mul__(self, sc):
        return Vector(self.x*sc, self.y*sc)

    def __truediv__(self, sc):
        return Vector(self.x/sc, self.y/sc)

    def __iadd__(self, vec):
        self.x += vec.x
        self.y += vec.y
        return self

    def __isub__(self, vec):
        self.x -= vec.x
        self.y -= vec.y
        return self

    def __imul__(self, sc):
        self.x *= sc
        self.y *= sc
        return self

    def __itruediv__(self, sc):
        self.x /= sc
        self.y /= sc
        return self

    def __str__(self):
        return '{:.9f} {:.9f}'.format(self.x, self.y)

    def __eq__(self, vec):
        return self.x == vec.x and self.y == vec.y

    def dot(self, vec):
        return self.x * vec.x + self.y * vec.y

    def abs(self):
        return (self.x*self.x + self.y*self.y)**0.5

    def ortho(self):
        return Vector(-self.y, self.x)


x1, y1, x2, y2 = map(int, input().split())
v1 = Vector(x1, y1)
v2 = Vector(x2, y2)
n = v2-v1
n /= n.abs()
m = n.ortho()

for _ in [0]*int(input()):
    x, y = map(int, input().split())
    v = Vector(x, y) - v1
    u = v - m * v.dot(m) * 2
    print(v1 + u)



Measured memory_bytes: 5740
#include <iostream>
#include <cmath>
#include <algorithm>

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

using namespace std;

const int mod=1000000000+7;
const ll inf=10000000000;

int main() {
    
    int N,K;
    cin>>N>>K;
    
    int h[N+1];
    h[0]=0;
    for(int i=1;i<=N;++i){
        cin>>h[i];
    }
    
    
    ll d[N+1];
    
    d[0]=0;
    d[1]=0;

    for(int i=2;i<=N;++i){
        ll m=inf;
        for(int j=1;j<=K&&j<i;++j){
            m=min(d[i-j]+abs(h[i]-h[i-j]),m);
        }
        d[i]=m;
    }
    
    cout<<d[N]<<endl;
}


Measured memory_bytes: 4764
#include <bits/stdc++.h>
#define int long long
#define Matrix vector<vector<int> >
// #define Matrix vector<vector<int> >
#define double long double
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define td(v) v.begin(),v.end()
#define tdr(v) v.rbegin(),v.rend()
// #define endl "\n"
#define Matrix vector<vector<int> >
using namespace std;
const int MOD = 1e9+7;
const long long INF = 5e18;
const double pi = acos(-1.0);
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int gcd(int a, int b){return (b == 0 ? a : gcd(b, a%b));}
int lcm(int a,int b){return (a*b)/gcd(a,b);}
 
inline long long mod(long long n, long long m){
    long long ret = n%m;
    if(ret < 0) ret += m;
    return ret;
}
 
double rad(double x){
    return x*pi/180.0;
}
 
bool isleft(pair<int,int> a, pair<int,int> b, pair<int,int> c){
    int det = (b.first-a.first)*(c.second-a.second) - (c.first-a.first)*(b.second-a.second);
    if(det>=0) return true;
    if(det<0) return false;
    return false;
}
 
int exp(int a, int b){
    int result = 1;
    while (b > 0){
        if (b & 1)
            result = mod(result*a,MOD);
 
        b >>= 1;
        a = mod(a*a,MOD);
    }
    return result;
}

void solve(){
    int n,m;
    cin>>n>>m;
    char adj[n][m];
    int dp[n][m];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>adj[i][j];
            dp[i][j]=0;
        }
    }
    for(int i=0;i<n;i++){
        if(adj[i][0]=='#') break;
        dp[i][0]=1;
    }
    for(int i=0;i<m;i++){
        if(adj[0][i]=='#') break;
        dp[0][i]=1;
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<m;j++){
            if(adj[i][j]!='#'){
                // cout<<"HERE"<<endl;
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
                dp[i][j]%=MOD;
            }
        }
    }
    cout<<dp[n-1][m-1]<<endl;
}

signed main(){
    fastio;
    int t=1;
    // cin>>t;
    while(t--)
        solve();
}

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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

typedef long long ll;
typedef long double ld;

const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

int x;
int cost[6] = {100, 101, 102, 103, 104, 105};

vector<bool> checked, a;

bool dfs(int s) {
    if (checked[s]) return a[s];
    if (s > x) return a[s] = false;
    if (s == x) return a[s] = true;
    bool res = false;
    rep (i, 6) res |= dfs(s + cost[i]);
    checked[s] = true;
    if (res) return a[s] = true;
    else return a[s] = false;
}


int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
    cin >> x;
    checked.resize(x + 111);
    a.resize(x + 111);
    if (dfs(0)) cout << 1 << endl;
    else cout << 0 << endl;
    
    return 0;
}



Measured memory_bytes: 384
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
#define MOD 1000000007
using namespace std;

struct Info{
	Info(){
		is_A = false;
		is_B = false;
	}
	bool is_A,is_B;
};

int main(){

	int N,num,ans = 0,tmp;
	scanf("%d",&N);

	Info info[N+1];

	scanf("%d",&num);

	for(int i = 0; i < num; i++){
		scanf("%d",&tmp);
		info[tmp].is_A = true;
	}

	scanf("%d",&num);

	for(int i = 0; i < num; i++){
		scanf("%d",&tmp);
		info[tmp].is_B = true;
	}

	scanf("%d",&num);

	for(int i = 0; i < num; i++){
		scanf("%d",&tmp);
		if(info[tmp].is_A == false || info[tmp].is_B == true)ans++;
	}

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

	return 0;
}

Measured memory_bytes: 2704
#include<cstdio>
#include<map>
#include<set>
using namespace std;

int main() {
  int n,t;
  while(scanf("%d", &n), n) {
    map<int,int> m;
    set<int> S;
    for(int i=0; i<n; ++i) {
      scanf("%d", &t);
      if(m.find(t) == m.end())
        m[t] = 1;
      else
        m[t]++;
      S.insert(t);
    }
    for(set<int>::iterator it = S.begin(); it!=S.end(); ++it)
      if(m[*it] > n/2) {
        printf("%d\n", *it);
        goto NEXT;
      }
    printf("NO COLOR\n");
  NEXT:
    ;
  }
}

Measured memory_bytes: 2620
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    int N = Integer.parseInt(sc.next());
    int T = Integer.parseInt(sc.next());

    int minCost = 2000;

    for (int i = 0; i < N; i++) {
      int c = Integer.parseInt(sc.next());
      int t = Integer.parseInt(sc.next());
      if (t <= T && c < minCost) {
        minCost = c;
      }
    }
    if (minCost > 1000) {
      System.out.println("TLE");
    } else {
      System.out.println(minCost);
    }

  }
}

Measured memory_bytes: 23124
n=int(input())
a=list(map(int,input().split()))
ans=float('inf')
s=sum(a)
s1 = a[0]
s2 = s-s1
ans = min(ans, abs(s1 - s2))
for i in range(1,n):
    s1+=a[i]
    s2-=a[i]
    ans = min(ans, abs(s1 - s2))

print(ans)

Measured memory_bytes: 88016
#include <stdio.h>
#define LL long long
int p[50],m[50],tot;
int main(){
	LL n;
	int i,j,ans=0;
	scanf("%lld",&n);
	for(i=2;(LL)i*i<=n;i++)
		if(n%i==0){
			p[++tot]=i;
			while(n%i==0)n/=i,m[tot]++;
		}
	if(n>1)p[++tot]=n,m[tot]=1;
	for(i=1;i<=tot;i++){
		j=1;
		while(1){
			if(m[i]>=j)ans++,m[i]-=j;
			else break;
			j++;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1704
from collections import deque


def nearlist(N, LIST):  # 隣接リスト
    NEAR = [set() for _ in range(N)]
    for a, b in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
    return NEAR


def bfs(NEAR, S, N):  # 幅優先探索  # キュー
    dist = [-1 for _ in range(N)]  # 前処理
    dist[S] = 0
    que, frag = deque([S]), set([S])

    while len(que) > 0:
        q = que.popleft()
        for i in NEAR[q]:  # 移動先の候補
            if i in frag:  # 処理済みか否か
                continue
            dist[i] = dist[q] + 1
            que.append(i), frag.add(i)
    return dist


n, u, v = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n - 1)]

near = nearlist(n, ab)
tkdist, akdist = bfs(near, u - 1, n), bfs(near, v - 1, n)

node = [i for i in range(n) if tkdist[i] <= akdist[i]]
ans = max(akdist[i] for i in node)
print(ans - 1)


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

int main() {
  int n;
  cin >> n;
  vector<int> v(n,0);
  r(i,n)cin >> v[i];
  if(n==1)cout << v[0]<<endl;
  else if(n%2==0){
    r(i,n/2)cout << v[n-1-2*i]<<" ";
    r(i,n/2-1)cout << v[2*i]<<" ";
    cout << v[n-2];
  }
  else{
    r(i,n/2+1)cout << v[n-1-2*i]<<" ";
    r(i,n/2-1)cout << v[2*i+1]<<" ";
    cout << v[n-2];
  }
  cout << endl;
}


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

int main(){
    int n;
    cin>>n;
    
    vector<int> B(n-1);
    for(int i = 0; i < n-1; i++) cin>>B[i];

    int res = B[0];
    for(int i = 1; i < n-1; i++){
        if(B[i]>B[i-1]) res+=B[i-1];
        else res+=B[i];
    }
    cout<<res+B[n-2];
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 2e5 + 5;
const ll LINF = 1e18 + 5;

int main()
{
 	ios::sync_with_stdio(false);
 	cin.tie(0);
 	int n, k;
 	cin >> n >> k;
 	string s;
 	cin >> s;
 	s[k-1] = tolower(s[k-1]);
 	cout << s;
	return 0;
}


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

#define rep(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define rrep(i,a,n) for(int (i)=(a);(i)>=(n);(i)--)

#define INF 1000000000
#define MOD 1000000007

typedef  long long ll;

using namespace std;

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

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

double euclid_distance(double a,double b){
    return sqrt(a*a+b*b);
}

int gcd(long long int a,long long int b){
    long long int r;
    if(a < b){
        int tmp;
        tmp = a;
        a = b;
        b = tmp;
    }
    while(r = a % b){
        a = b;
        b = r;
    }
    return a;
}

void Integer_factorization(long long int b,long long int n){
    long long int a = 2;
    long long int count = 0;
    long long int ans = 1;
    long long int ndash = n;
    if(b == 1) cout << n << endl;
    else{
    while(ndash >= a*a){
        if(n % a  == 0){
            count++;
            n/=a;

        if(count % b == 0){
            ans *= a;
        }
        }else{a++;count = 0;}
    }

    cout<<  ans << endl;
    }
}

void ys(){
    cout << "Yes" << endl;
}

void yb(){
    cout << "YES" << endl;
}

void ns(){
    cout << "No" << endl;
}

void nb(){
    cout << "NO" << endl;
}

void solve(void){
    int n;
    cin >> n;
    int a[n][3];

    rep(i,0,n){
        rep(j,0,3){
            cin >> a[i][j];
        }
    } 
        
    int  dp[n+1][3]; //[i円の時の回数][a,b,cのどこにいるか]

    rep(i,0,n+1){
        rep(j,0,3){
            dp[i][j] = 0;
        }
    }

    rep(i,0,n){
        rep(j,0,3){
            rep(k,0,3){
                if(j == k) continue;
                chmax(dp[i+1][k],dp[i][j] + a[i][k]);        
            }
        }
    }
    
    int ans = 0;
    rep(i,0,3) chmax(ans,dp[n][i]);
    cout << ans <<endl;

}

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

Measured memory_bytes: 2560