akhauriyash/Code-Regression huggingface dataset:
import java.io.*;

class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringBuilder stringBuilder = new StringBuilder();
            final int term = 12; //?????????????????????
            
            String line;
             while ((line = br.readLine()) != null) {
            	 if(line.equals("0")){
            		 break;
            	 }
            	 
            	 int goal = Integer.parseInt(line);
            	 int totalAmount = 0;
            	 String progressMonth = "";
            	 for(int i=0; i<term; i++){
            		 String[] dataSet = br.readLine().split(" ");
            		 if(goal > totalAmount){
            			 totalAmount = calculate(dataSet, totalAmount);
            			 progressMonth = check(i, goal, totalAmount);
            		 }
            	 }
            	 stringBuilder.append(progressMonth + "\n");
             }
             System.out.print(stringBuilder);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    /*
     * ????????????????¨??????????
     * @param int????????\?????????????????\????????????????????±
     * @param int??????????????????????????????????????????
     * @return int????????°?????????????????±??????????????????????????????
     */
    private static int calculate(String[] dataSet, int totalAmount){
    	 int income = Integer.parseInt(dataSet[0]);
		 int outcome = Integer.parseInt(dataSet[1]);
		 
		 totalAmount += (income - outcome);
		 return totalAmount;
    }
    
    /*
     * ????¨??????????????????????????????????????????§????????????
     * @param int????????????????§??????????????????????????????°
     * @oaram int??????????¨???????
     * @param int????????????????????§???????????????
     * @return String?????????????????°
     */
    private static String check(int progressMonth, int goal, int totalAmount){
    	if(goal <= totalAmount){
    		return String.valueOf(progressMonth + 1);
    	}
    	return "NA";
    }
}

Measured memory_bytes: 30068
#include <stdio.h>

int main(void) {

  long a,b,c;
  scanf("%ld %ld %ld", &a, &b, &c);
  long count = 0;
  long next_a,next_b,next_c;
  while (1) {
    if (a%2 != 0 || b%2 != 0 || c%2 != 0) {
      break;
    }
    if (a == b || b == c || c == a) {
      printf("-1\n");
      return 0;
    }
    count++;
    next_a = (b+c)/2;
    next_b = (c+a)/2;
    next_c = (a+b)/2;
    a = next_a;
    b = next_b;
    c = next_c;
  }
  printf("%ld\n", count);

  return 0;
}

Measured memory_bytes: 128
object Main {
  def main(args: Array[String]): Unit = {
    val scanner = new java.util.Scanner(System.in)

    val n = scanner.nextInt
    val t1, s1, e1, w1, n1, b1 = scanner.nextInt
    var d1 = Dice(t1, n1, e1, s1, w1, b1)

    for(_ <- 2 to n) {
      val t2, s2, e2, w2, n2, b2 = scanner.nextInt
      var d2 = Dice(t2, n2, e2, s2, w2, b2)

      for(_ <- 1 to 4) {
        for(_ <- 1 to 4) {
          for(_ <- 1 to 4) {
            for(_ <- 1 to 4) {
              if(d1.equals(d2)) {
                println("No")
                System.exit(0)
              }
              d2 = d2.rotN()
            }
            d2 = d2.rotE()
          }
          d1 = d1.rotN()
        }
        d1 = d1.rotE()
      }
    }

    println("Yes")
  }
}

case class Dice(t: Int, n: Int, e: Int, s: Int, w: Int, b: Int) {
  def rotN(): Dice = Dice(s, t, e, b, w, n)
  def rotS(): Dice = Dice(n, b, e, t, w, s)
  def rotW(): Dice = Dice(e, n, b, s, t, w)
  def rotE(): Dice = Dice(w, n, t, s, b, e)
  def rot(): Dice = Dice(t, e, s, w, n, b)
  def equals(that: Dice): Boolean = (t == that.t && n == that.n && e == that.e && s == that.s && w == that.w && b == that.b)
}



Measured memory_bytes: 48512
#[allow(unused_imports)]
use std::{cmp::Reverse, collections::*};

#[allow(unused_imports)]
use proconio::{
    fastout, input,
    marker::{Chars, Usize1},
};

#[allow(unused_imports)]
use itertools::Itertools;

#[allow(unused_imports)]
use num::Integer;

#[fastout]
pub fn main() {
    input! {
        n: usize, _m: usize,
    }
    let mut map = HashMap::new();
    for _ in 0..n {
        input! {
            k: usize,
            a: [Usize1; k],
        }
        for a in a {
            *map.entry(a).or_insert(0) += 1;
        }
    }
    println!("{}", map.iter().filter(|(_, &v)| v == n).count());
}


Measured memory_bytes: 2172
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import sys
sys.setrecursionlimit(10**8)

def main():
  n, m = map(int, input().split())
  tree = [[] for _ in range(n)]
  for im in range(m):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
  
  def get_bridge(tree):
    bridge_targets = []
    n = len(tree)
    pres = [0 for _ in range(n)]
    lows = [0 for _ in range(n)]
    visited = [0 for _ in range(n)]
    used_edges = []
    def dfs(inode, count=0):
      pres[inode] = lows[inode] = count
      visited[inode] = 1
      for ichild in tree[inode]:
        if not visited[ichild]:
          used_edges.append((inode, ichild))
          count = dfs(ichild, count+1)
        if lows[ichild] < lows[inode]:
          if not (ichild, inode) in used_edges:
            lows[inode] = lows[ichild]
      if pres[inode] == lows[inode]:
        bridge_targets.append(inode)
      
      return count
    dfs(0)
    return [(s, t) for (s, t) in used_edges if t in bridge_targets]
  bridges = get_bridge(tree)
  print(len(bridges))
  
if __name__=='__main__':
  main()



Measured memory_bytes: 3064
str = input()

s_ans = 'Yes'
if len(str)%2 == 1:
    s_ans ='No'
else:
    for i in range(0,len(str),2):
        moji = str[i:i+2]
        if str[i:i+2] != 'hi':
            s_ans = 'No'
            break
print(s_ans)

Measured memory_bytes: 9008
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using static ConsoleApp.Util;
using static System.Math;
 
namespace ConsoleApp
{
    class Program
    {
       
        static void Main(string[] args)
        {
            string n = ReadLine();
            int k = int.Parse(ReadLine());

            //dp[i,j,m] 上からi桁まで決定した時の、0でない数字がj個ある数の個数(m:未満フラグ)
            long[,,] dp = new long[n.Length+1,k+1,2];

            dp[0, 0, 0] = 1;

            for (int i = 0; i < n.Length;i++)
            {
                for (int j = 0; j <= k;j++)
                {
                    for (int flag = 0; flag <= 1;flag++)
                    {
                        int D =  n[i] - '0'; 

                        for (int d = 0; d <= (flag >= 1 ? 9 : D); d++)
                        {
                            int jplus = 0;
                            int nextFlag = 1;
                            
                            if(d != 0)
                                jplus = 1;
                            if(flag == 0 && d == D)
                                nextFlag = 0;

                            if(j + jplus > k){
                                //kより多く０でない数字が入ってしまったときは抜かす
                                continue;
                            }
   
                            dp[i + 1, j + jplus, nextFlag] += dp[i,j,flag];

                        }
                    }
                }
            }

            WriteLine(dp[n.Length,k,0] + dp[n.Length,k,1]);
        }
 
        
    }
 
 
    static class Util{
        public static void ChMin(ref long a,long b){
            
            if(a > b){
                a = b;
            }
        }
 
        public static void ChMax(ref long a,long b){
            if(a < b){
                a = b;
            }
        }
 
 
 
		
    }
}

Measured memory_bytes: 13140
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	p := make([]int, n)
	for i := range p {
		fmt.Scan(&p[i])
	}
	cnt := 0
	for i := 1; i < len(p)-1; i++ {
		if (p[i-1] < p[i] && p[i] < p[i+1]) ||
			(p[i+1] < p[i] && p[i] < p[i-1]) {
			cnt++
		}
	}
	fmt.Println(cnt)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1001001001
#define LINF 1001001001001001001
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

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

/**
 * 高速素因数分解 O(n log log n + log k)
 * n以下の自然数に対する初期化を行い、n以下の自然数kをO(log k)で素因数分解する
 **/
class Factorization {
  private:
    vector<bool> isPrime;
    vector<int> prime;
    vector<int> divisor;
  public:
    Factorization(int n);
    map<int, int> getPrimeFactors(int k);
};

Factorization::Factorization(int n) {
  isPrime.assign(n + 1, true);
  isPrime[0] = false;
  isPrime[1] = false;
  divisor.assign(n + 1, -1);
  for (int i = 2; i <= n; i++) {
    if (!isPrime[i]) continue;
    divisor[i] = i;
    prime.push_back(i);
    for (int j = 2; i * j <= n; j++) {
      isPrime[i * j] = false;
      divisor[i * j] = i;
    }
  }
}

/**
 *  n以下の自然数kをO(log k)で素因数分解する
 *  key = 素因数 / value = 素因数の個数 のmapで返す
 **/
map<int, int> Factorization::getPrimeFactors(int k) {
  map<int, int> res;
  while (k >= 2) {
    int d = divisor[k];
    if (res.find(d) == res.end()) {
      res.emplace(d, 1);
    } else {
      res[d]++;
    }
    k /= d;
  }
  return res;
}

int main() {
  
  int N;
  cin >> N;
  vector<int> A(N);
  int max_A = 0;
  rep(i,N) {
    cin >> A[i];
    max_A = max(max_A, A[i]);
  }

  Factorization fact(max_A);

  map<int, int> factor;
  rep(i,N) {
    if (A[i] == 1) continue;
    map<int, int> f = fact.getPrimeFactors(A[i]);
    for (auto p: f) {
      if (factor.find(p.first) == factor.end()) {
        factor.emplace(p.first, 1);
      } else {
        factor[p.first]++;
      }
    }
  }

  int maximum = 0;

  for (const auto& [key, value]: factor) {
    maximum = max(maximum, value);
  }

  if (maximum <= 1) cout << "pairwise coprime" << endl;
  else if (maximum < N) cout << "setwise coprime" << endl;
  else cout << "not coprime" << endl;

  return 0;
}

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

int n;
int a[200000];
vector<int> g[200000];
int ans[200000], dp[200000];
stack<pair<int,int>> s;

void dfs(int cur, int p) {
  auto it = lower_bound(dp, dp + n, a[cur]);
  int idx = it - dp;
  s.push(make_pair(idx, dp[idx]));
  dp[idx] = min(dp[idx], a[cur]);
  ans[cur] = lower_bound(dp, dp + n, 1e9+1) - dp;
  for (int to: g[cur]) {
    if (to == p) {
      continue;
    }
    dfs(to, cur);
  }
  auto top = s.top();
  s.pop();
  dp[top.first] = top.second;
}
int main() {
  cin>>n;
  for (int i=0; i<n; i++) cin>>a[i];
  for (int i=0; i<n-1; i++) {
    int u, v;
    cin>>u>>v;
    --u;
    --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i=0; i<n; i++) ans[i] = 0;
  for (int i=0; i<n; i++) dp[i] = 1e9 + 1;
  dfs(0, -1);
  for (int i=0; i<n; i++) {
    cout<<ans[i]<<endl;
  }
}

Measured memory_bytes: 35100
#include <stdio.h>

int main(void){
    
    int x,y,i,amari;
    int array[100];
    int saidaikouyakusuu;
    
    scanf("%d%d",&x,&y);
    
 
    
 	if (x>y) {
		amari = x % y;
		for (i = 1; i < amari; i++) {
			if (amari%i == 0 && y%i == 0) {
				saidaikouyakusuu = i;
			}
		}
	}
	else if(x<y){
		amari = y % x;
		for (i = 1; i < amari; i++) {
			if (amari%i == 0 && x%i == 0) {
				saidaikouyakusuu = i;
			}
		}

	}else {saidaikouyakusuu = x;
	}
    printf("%d\n", saidaikouyakusuu);
    
    return 0;
}


Measured memory_bytes: 2140
#define _GLIBCXX_DEBUG
#define rep(i,N) for(int i = 0; i < N;i++)
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#include <string.h>
#include <iomanip>
#include <numeric>
#include <cstdlib>
#include <cstdint>
#include <cmath>
#include <functional>
#include <limits>
#include <cassert>

using namespace std;


/* template */
int main (){
  int N;
  vector<int> vec(N);
  cin >> N;
  rep(i,N){
    cin >> vec[i];
  }
  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());
  int a=0;
  rep(i,N){
      if(vec[i]>vec[i+1]){
        a++;
      }
      else continue;
  }
  cout << a <<endl;
 }
 

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <string>

using namespace std;

int main(){
  int N;
  int result = 0;
  cin >> N;
  int s = N;
  while(N != 0){
    result += N % 10;
    N /= 10;
  }
  if(s % result == 0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define mem(a) memset(a,0,sizeof(a))
#define dbg(x) cout<<#x<<" = "<<x<<endl
#define ll long long
//不要再爆long long了！！！！！！！！不要再爆long long了！！！！！！！ 
ll a[100010];//a[i]:第i层最多有a[i]个 
ll b[100010];//从下往上的限制 
ll min(ll a,ll b)
{
	return (a<b?a:b);
}
ll pow(ll b)
{
	ll k=1;
	for(int i=0;i<b;i++)k*=2;
	return k;
}
int main()
{
	int n,i;
	cin>>n;
	for(i=0;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	if(n!=0&&a[0]!=0){cout<<"-1";return 0;}
	if(n==0)
	{
		if(a[0]==0){cout<<"0";return 0;}
		else if(a[0]==1){cout<<"1";return 0;}
		else {cout<<"-1";return 0;}
	}
	b[n]=a[n];
	for(i=n-1;i>-1;i--)
	{
		b[i]=a[i]+b[i+1];
	} 
	ll wangxia=1,lilunmax,s=1;
	for(i=1;i<=n;i++)
	{
		lilunmax=min(wangxia*2,b[i]);
		if(i<40)lilunmax=min(lilunmax,pow(i));
		s+=lilunmax;
		wangxia=lilunmax-a[i];
		if(wangxia<0){cout<<"-1";return 0;}
	}
	printf("%lld",s);
	
//	for(ll i=0;i<=50;i++)
//	{
//		printf("pow(2,%d)=%lld\n",i,pow(i));
//	}
	return 0;
}

Measured memory_bytes: 5360
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<unsigned char, unsigned char> pcc;
typedef pair<double, double> pdd;
typedef vector<vector<ll>> matrix;

void solve() {
  int r, c, d;
  cin >> r >> c >> d;
  for(int i = 0; i < r; i++) {
    for(int j = 0; j < c; j++) {
      int x = (i+j);
      int y = (i-j);
      x %= (2*d);
      y %= (2*d);
      x += (2*d);
      y += (2*d);
      x %= (2*d);
      y %= (2*d);
      if(x < d && y < d) cout << "R";
      if(x < d && y >= d) cout << "Y";
      if(x >= d && y < d) cout << "G";
      if(x >= d && y >= d) cout << "B";
    }
    cout << "\n";
  }
}

void casesolve() {
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ":" << "\n";
    solve();
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
  // casesolve();
}


Measured memory_bytes: 512
#include<iostream>
using namespace std;
int main(){
  int n;
  cin >> n;
  long long int b=1;
  long long int c=1;
  for(int i=0;i<n;i++){
    long long int t,a;
    cin >> t >> a;
    long long int d,e;
      d = b / t;
      if(b%t>0) d++;
      e = c / a;
      if(c%a>0) e++;
      long long int k = max(d,e);
      b = k * t;
      c = k * a;
  }
  cout << b+c << endl;
  return 0;
}


Measured memory_bytes: 256
// IO library
#include <cstdio>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>

// container library
#include <deque>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>

// namespace
using namespace std;

// typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VII;
typedef vector<string> VS;

// container
#define EACH(i, c) for (auto i = (c).begin(); i != (c).end(); i++)
#define SORT(c) sort((c).begin(), (c).end())
#define GSORT(c) sort((c).begin(), (c).end(), greater<typeof((c).front())>())
#define SZ(x) ((int)(x).size())
#define MEMSET(c, v) memset((c), v, sizeof(c))

// repetition
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define NREP(i, n) FOR(i, 1, n + 1)
#define RFOR(i, a, b) for (int i = (a); i >= (b); i--)
#define RREP(i, n) RFOR(i, n, 0)
#define RNREP(i, n) RFOR(i, n, 1)

// constant
// const ll MOD = 1e9 + 7;
// const int INF = 1e9;
// const ll INF = 1e15;
// const int dx[4] = {0, -1, 1, 0};
// const int dy[4] = {-1, 0, 0, 1};
// const int dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
// const int dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};

// debug
#define test(x) cout << #x << " = " << x << endl

// answer output
#define Yes(c) cout << ((c) ? "Yes" : "No") << endl;
#define YES(c) cout << ((c) ? "YES" : "NO") << endl;
#define possible(c) cout << ((c) ? "possible" : "impossible") << endl;
#define POSSIBLE(c) cout << ((c) ? "POSSIBLE" : "INPOSSIBLE") << endl;


// --------------------------------------------------------


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

    int maxw = 100, maxs = 0;
    REP(wa, F / (A * 100) + 1)
    {
        REP(wb, F / (B * 100) + 1)
        {
            int w = wa * A * 100 + wb * B * 100;
            // test(w);

            if (w < F) {
                REP(sc, (w * E) / (100 * C) + 1)
                {
                    REP(sd, (w * E) / (100 * D) + 1)
                    {

                        int s = sc * C + sd * D;
                        // test(s);

                        if ((w + s <= F) && (100 * s <= w * E)) {
                            if (maxs * (w + s) <= s * (maxw + maxs)) {
                                maxw = w;
                                maxs = s;
                            }
                        }
                    }
                }
            }
        }
    }

    cout << maxw + maxs << " " << maxs << endl;

    return 0;
}

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

int main(){
    int n;
    cin >> n;
   vector< pair<int,int>> c(n);
    for(int i = 0; i < n; i++){
        int a,b;
        cin >> a >> b;
        
        c[i] = make_pair(a,b);
    }
    sort(c.begin(),c.end());
    cout<< c[n - 1].second + c[n - 1].first << "\n";
}

Measured memory_bytes: 1024
n=int(input())
from collections import defaultdict
d1=defaultdict(int)
d2=defaultdict(int)
ar=[]
for i in range(n):
    k=int(input())
    d1[k]=i
    ar.append(k)
ar.sort()
for i in range(n):
    k=ar[i]
    d2[k]=i
c=0
for i in ar:
    a,b=d1[i],d2[i]
    if (a+b)%2==1:
        c+=1
print(c//2)

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

using namespace std;

int N,M;
typedef pair<int,int> pint;

vector<pint> A;
bool cmp(pint a,pint b){return a.second<b.second;}

int main(){
    cin>>N>>M;
    A.resize(M);
    for(int i=0;i<M;i++)cin>>A[i].first>>A[i].second;
    sort(A.begin(),A.end(),cmp);
    int res=0;
    int endtime=0;
    for(int i=0;i<M;i++){
        if(A[i].first>=endtime){
            endtime=A[i].second;
            res++;
        }
    }
    cout<<res<<endl;
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<stdlib.h>
#define df 0
int cost[8];
int val[8];
typedef long int li ;
int main (){
  int i,n,ga,sa,ba,gb,sb,bb;
  scanf("%d%d%d%d%d%d%d",&n,&ga,&sa,&ba,&gb,&sb,&bb);
  cost[0]=1;
  cost[1]=ga;
  cost[2]=sa;
  cost[3]=ba;
  cost[4]=gb;
  cost[5]=sb;
  cost[6]=bb;
  cost[7]=1;
  val[0]=1;
  val[1]=gb;
  val[2]=sb;
  val[3]=bb;
  val[4]=ga;
  val[5]=sa;
  val[6]=ba;
  val[7]=1;
  
  int* dp;
  dp=(int*)malloc(sizeof(int)*(n+1));


  dp[0]=0;
  for(i=1;i<=n;i++){
    dp[i]=0;
    int j;
    for(j=0;j<4;j++){
      if(i>=cost[j]){
	if(dp[i]<dp[i-cost[j]]+val[j])dp[i]=dp[i-cost[j]]+val[j];
      }
    }
  }
  n=dp[n];
  li* dp2;
  dp2=(li*)malloc(sizeof(li)*(n+1));
  
  dp2[0]=0;
  for(i=1;i<=n;i++){
    dp2[i]=0;
    int j;
    for(j=4;j<8;j++){
      if(i>=cost[j]){
	if(dp2[i]<dp2[i-cost[j]]+val[j])dp2[i]=dp2[i-cost[j]]+val[j];
      }
    }
  }
  if(df){
    for(i=0;i<=n;i++)
      printf("%ld ",dp2[i]);
      printf("\n");
  }
  printf("%ld",dp2[n]);
  free(dp);
  free(dp2);
}


Measured memory_bytes: 195456
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
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 (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

int n,m,q;
vi a,b,c,d;
int ans = 0;

void dfs(vi A){
    if(A.size() == n+1){
        int tmp = 0;
        rep(i,q){
            if(A[b[i]]- A[a[i]]==c[i])tmp += d[i];
        }
        ans = max(ans,tmp);
        return ;
    }

    A.pb(A.back());
    while(A.back()<=m){
    dfs(A);
    A.back()++;
    }
}

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


    cin >> n >> m >> q;
    a = b = c = d = vi(q);
    rep(i,q){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    dfs(vi(1,1));
    cout << ans << endl;
    return 0;
}


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

int comp(const void* a, const void* b){
	return *(int*)a - *(int*)b;
}

int main(){
	int a, b, k, ans[105];
	cin >> a >> b >> k;
	for(int i = min(a, b); i >= 1; --i){
		if(a % i == 0 && b % i == 0){
			k--;
			if(k== 0){
				cout << i << endl;
				return 0;
			}
		}
	}
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdint>
#include <numeric>
#include <vector>
#include <algorithm>
#include <utility>

intmax_t gcd(intmax_t m, intmax_t n) {
  while (n) std::swap(m %= n, n);
  return m;
}

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

  intmax_t res = 0;
  for (int a = 1; a <= k; ++a)
    for (int b = 1; b <= k; ++b)
      for (int c = 1; c <= k; ++c)
        res += gcd(gcd(a, b), c);

  printf("%jd\n", res);
}


Measured memory_bytes: 1728
// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
	int X=0,w=1; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
	while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
	return X*w;
}

const int N=100000+10;

int n,f[N]; char s[N];

int trans(char c,int x,int y) {
	if (y) {
		if (c=='x') return x;
		else return !x;
	} else {
		if (c=='o') return x;
		else return !x;
	}
}

bool check(int a,int b) {
	f[1]=a,f[2]=b;
	for (int i=3;i<=n;++i)
		f[i]=trans(s[i-1],f[i-2],f[i-1]);
	if (trans(s[n],f[n-1],f[n])!=f[1]) return 0;
	if (trans(s[1],f[2],f[1])!=f[n]) return 0;
	return 1;
}

int main() {
	n=read(); scanf("%s",s+1);
	if (check(0,0)) {
		for (int i=1;i<=n;++i) putchar("SW"[f[i]]);
		return 0;
	}
	if (check(0,1)) {
		for (int i=1;i<=n;++i) putchar("SW"[f[i]]);
		return 0;
	}
	if (check(1,0)) {
		for (int i=1;i<=n;++i) putchar("SW"[f[i]]);
		return 0;
	}
	if (check(1,1)) {
		for (int i=1;i<=n;++i) putchar("SW"[f[i]]);
		return 0;
	}
	puts("-1");
	return 0;
}

Measured memory_bytes: 4236
use std::collections::*;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn main() {
    let s = read::<String>().chars().collect::<Vec<_>>();

    let mut count_dict = HashMap::<char, u64>::new();
    for ch in s {
        *count_dict.entry(ch).or_insert(0) += 1;
    }

    let values = count_dict.values().cloned().collect::<Vec<_>>();
    let value_sum = values.iter().sum::<u64>();

    let mut ans = values.iter().fold(0, |s, &v| s + v * (value_sum - v));
    println!("{}", ans / 2 + 1);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;

int main() {
  ll s, c;
  cin >> s >> c;

  ll ans = min(s, c / 2);
  s -= ans;
  c -= ans * 2;

  ans += c / 4;
  cout << ans << endl;
}


Measured memory_bytes: 3560
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 100005
typedef long long ll;
int main()
{
    char s[55];
    scanf("%s",s);
    int n=strlen(s);
    for(int i=0;i<n-8;i++)
        printf("%c",s[i]);
    printf("\n");
    return 0;
}


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

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  array<int, 3> A;
  for(auto& e : A)cin >> e;
  sort(begin(A), end(A));
  cout << (A.back() - A.front()) << endl;
}


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

using namespace std;

int main() {
	int n ,d ;
	scanf("%d %d",&n ,&d ) ;
	int v = d * 2 + 1 ;
	int ans = 0;
	if ( n % v == 0 ) {
		ans = n / v ;
	} else {
		ans = n / v + 1 ;
	}
	printf("%d\n",ans) ;
	return 0;
}

Measured memory_bytes: 384
n,d=(int(x) for x in input().split())
x=[ [int(x) for x in input().split()] for i in range(n)]
c=0
for i in range(n):
  for j in range(i+1,n):
    sum=0
    for k in range(d):
      sum+=(x[i][k]-x[j][k])**2
    dis=sum**0.5
    if dis.is_integer():
      c+=1
print(c)

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

class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int M=sc.nextInt();
		int[] keta=new int[N+1];
		boolean val=true;
		Arrays.fill(keta,-1);
		for(int i=0; i<M; i++) {
			int s=sc.nextInt();
			int c=sc.nextInt();
			if(keta[s]==-1) {
				keta[s]=c;
			}
			else if(keta[s]!=-1 && keta[s] != c){
				val =false;		//矛盾
			}
		}
		if(!val) {
			pl(-1);
			System.exit(0);
		}
		if(N==1) {
			if(keta[1]==-1) {
				pl(0);
			}
			else {
				pl(keta[1]);
			}
		}
		else if(N==2) {
			if(keta[1]==0) {
				pl(-1);
			}
			else if(keta[1]==-1) {
				keta[1]=1;		//条件なしのとき、
			}
			keta[2] = Math.max(keta[2], 0);
			pl(keta[1]*10+keta[2]);
		}
		else if(N==3) {
			if(keta[1] == 0 ) {
				pl(-1);
			}
			else {
				keta[1]=Math.max(keta[1], 1);
				for(int i=2; i<=3; i++) {
					keta[i]=Math.max(keta[i], 0);
				}
				pl(keta[1]*100+keta[2]*10+keta[3]);
			}
		}
	}
	public static void pl(Object o) {
		System.out.println(o);
	}
}

Measured memory_bytes: 21716
// #include <bits/stdc++.h>
#include <cctype>
#include <cstdio>
#include <algorithm>
#include <emmintrin.h>
 
using std::scanf;
using std::printf;
using std::max;
using std::isdigit;
 
typedef long long ll;
 
typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)

#define __my_getchar getchar_unlocked
inline void read(unsigned int &x){
  x=0;char c;
  while(!isdigit(c=__my_getchar()));
  x=c-'0';
  while(isdigit(c=__my_getchar()))x=10*x+(c-'0');
}
 
unsigned int n,m;
const int MAX_N = 5000;
const int MAX_M = 200;
unsigned int a[MAX_N] __attribute__((aligned(16)));
unsigned int b[MAX_N * MAX_M] __attribute__((aligned(16)));
unsigned int mx[MAX_M] __attribute__((aligned(16)));
 
static inline __m128i __attribute__((always_inline))
po_mm_max_epi32(__m128i a, __m128i b){
  __asm__("pmaxsd %1, %0" : "+x" (a) : "xm" (b));
  return a;
}
// max of two array
// a[i] = max(a[i], b[i])
void vec_chmax(int n, unsigned int *a, unsigned int *b){
  for(int i=0;i<n;i+=4){
    __m128i xx = _mm_load_si128((__m128i*)(a+i));
    __m128i yy = _mm_load_si128((__m128i*)(b+i));
    xx = po_mm_max_epi32(xx,yy);
    _mm_store_si128((__m128i*)(a+i), xx);
  }
}
 
unsigned long long tmp[2] __attribute__((aligned(16)));
// sum of array
// Σa[i]
ll vec_sumll(int n, unsigned int *a){
  __m128i x = _mm_setzero_si128();
  __m128i y = _mm_setzero_si128();
  const __m128i zero = _mm_setzero_si128();
 
  for(int i=0;i<n;i+=4){
    __m128i xx = _mm_load_si128((__m128i*)(a+i));
    __m128i yy = _mm_unpackhi_epi32(xx,zero);
            xx = _mm_unpacklo_epi32(xx,zero);
    x = _mm_add_epi64(x,xx);
    y = _mm_add_epi64(y,yy);
  }
  x = _mm_add_epi64(x,y);
  _mm_store_si128((__m128i*)tmp, x);
  return tmp[0] + tmp[1];
}
 
int main(){
  read(n);read(m);
  REP(i,n-1)read(a[i]);
  REP(i,n)REP(j,m)read(b[MAX_M*i+j]);
 
  ll ans = 0;
  REP(l,n){
    ll lensum = 0;
    REP(j,m)mx[j]=0;
    vec_chmax(m, mx, b+MAX_M*l);
    ans = max(ans, vec_sumll(m, mx)-lensum);
 
    FOR(r,l+1,n){
      lensum += a[r-1];
      vec_chmax(m, mx, b+MAX_M*r);
      ans = max(ans, vec_sumll(m, mx)-lensum);
    }
  }
  printf("%lld\n",ans);
  return 0;
}

Measured memory_bytes: 4096
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

#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 ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define ssrep(i, s, t) for (int i = s; i <= t; ++i)

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using ld = long double;

long int M = 1e+7;
int main(void){
    int n,m;
    cin >> n >> m;
    int sum =0;
    rep(i,m){
        int tmp;
        cin >> tmp;
        sum += tmp;
    }
    if(sum <= n){
        cout << n-sum << endl;
        return 0;
    }
    cout << "-1" << endl;
    return 0;
}

Measured memory_bytes: 3224
#include<atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;
const ll LINF = 1LL<<60;
const int INF = 1LL<<17;
#define rep(i, n) for(ll i=0; i<(ll)(n); i++)
#define repd(i, n) for(ll i=n-1; 0<=i; i--)
#define FOR(i, a, b) for(ll i=a; i<(ll)(b); i++)
#define FORD(i, a, b) for(ll i=b-1; (ll)(a)<=i; i--)
#define ALL(x) x.begin(), x.end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
string YES[2] = {"NO", "YES"};
string yes[2] = {"No", "Yes"};
int op(int a, int b){return max(a, b);}
int e(){return 0;}
const int MAX_A = 300005;
int main(){
    int n, k;    cin >> n >> k;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    segtree<int, op, e> dp(MAX_A);
    rep(i, n){
        int x = a[i];
        int l = max(x-k, 0), r = min(x+k+1, MAX_A);
        int cur = dp.prod(l, r)+1;
        dp.set(x, cur);
    }
    cout << dp.prod(0, MAX_A) << endl;
}


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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll K;
    cin >> K;
    cout << K / 2 * (K / 2 + K % 2) << endl;
    return 0;
}


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

using namespace std;

typedef long long ll;

const ll MD = 1000000007;
const int MAXN = 400000;

ll fact[MAXN + 1];
ll invfact[MAXN + 1];

// binary exp
ll mod_pow(ll x, ll tn){
  if(tn == 0) return 1;
  ll res = mod_pow(x*x %MD, tn/2);
  if(tn &1) res = res*x %MD; // n is odd
  return res;
}

void init(int N){
  fact[0] = 1;
  for(ll i=1;i<=N;i++) fact[i] = (fact[i-1]*i) %MD;
  for(int i=1;i<=N;i++){
    invfact[i] = mod_pow(fact[i], MD-2);
  }
}

ll comb(int tn, int r){
  if(r == 0 || tn == r) return 1;
  if(tn < r) return 0;
  return ((fact[tn]*invfact[r] %MD)*invfact[tn-r]) %MD;
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  ll n; cin >> n;
  // first: value, second: id
  vector<pair<ll, ll> > pa;
  for(int id=1;id<=n+1;id++){
    ll val; cin >> val;
    pa.push_back(make_pair(val, id));
  }
  sort(pa.begin(), pa.end());
  ll left, right;
  for(int i=0;i<pa.size()-1;i++){
    if(pa[i].first == pa[i+1].first){
      left = pa[i].second;
      right = pa[i+1].second;
    }
  }
  ll N = n + 1;
  ll M = left - 1 + N - right;
  init(N);
  for(int k=1;k<=n+1;k++){
    /*
    cout << "comb" << N << " " << k << ": " << comb(N, k) << endl;
    cout << "comb" << M << " " << k-1 << ": " << comb(M, k-1) << endl;
    */
    cout << ((comb(N, k) - comb(M, k-1)) %MD + MD) %MD << endl;
  }
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> veci;
typedef vector<ll> vecll;
typedef vector<string> vecs;
template<class T,class U> using Hash=unordered_map<T,U>;

#define REP(i, a, n) for(ll i = (a); (i) < (ll)(n); (i)++)
#define RREP(i, a, n) for(ll i = (n)-1; (i) >= (a); (i)--)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) RREP(i, 0, n)
#define MD 1000000007ULL
#define _SPLIT "\n"

template<class T> T read(){T a;cin >> a;return a;}
template<class T> void read(T& a){cin >> a;}
template<class T,class ...Args> void read(T& a, Args&... args){cin >> a; read(args...);} 
template<class T> void rarr(T& a, int n){for(int i = 0; i < n; i++) {cin >> a[i];}}
template<class T> void write(T a){cout << setprecision(22) << a << endl;}
template<class T,class ...Args> void write(T a, Args... args){cout << setprecision(22) << a << _SPLIT; write(args...);}
template<class T> void warr(vector<T> a, const char* c = " "){cout << a[0];for(int i = 1; i < (int)a.size(); i++)cout << c << a[i];cout << endl;;}
template<class T> void warr(T a, int n, const char* c = " "){cout << a[0];for(int i = 1; i < n; i++)cout << c << a[i];cout << endl;}
void split(string s, string delim, veci& result){result.clear();string::size_type pos = 0;while(pos != string::npos){string::size_type p = s.find(delim, pos);if(p == string::npos){result.push_back(atoi(s.substr(pos).data()));break;}else {result.push_back(atoi(s.substr(pos, p - pos).data()));}pos = p + delim.size();}}
void split(string s, string delim, vecs& result){result.clear();string::size_type pos = 0;while(pos != string::npos){string::size_type p = s.find(delim, pos);if(p == string::npos){result.push_back(s.substr(pos));break;}else {result.push_back(s.substr(pos, p - pos));}pos = p + delim.size();}}
ll gcd(ll a, ll b){while(true){ll k = a % b;if(k == 0)return b;a = b;b = k;}}
ll comb(ll n, ll m){ll p=1;m=min(m,n-m);for(ll i=1;i<=m;i++){p*=n-i+1;p/=i;}return p;}

int main(void)
{
    string s;
    read(s);
    map<char,int> m;
    rep(i,s.size()){
        m[s[i]]++;
    }
    if((m['W']==0&&m['E']>0)||(m['E']==0&&m['W']>0))write("No");
    else if((m['N']==0&&m['S']>0)||(m['S']==0&&m['N']>0))write("No");
    else write("Yes");
    return 0;
}


Measured memory_bytes: 256
# モンスターの体力　H
# アライグマの必殺技の種類　N
# i 番目の必殺技を使うとモンスターの体力を A i減らすことができる。
# 必殺技を使う以外の方法でモンスターの体力を減らすことはできない
# モンスターの体力が0以下にすれば、アライグマの勝ち
# アライグマが同じ必殺技を2度以上使うことはない
# モンスターに買ったらYes　できないならNo　と出力

H, N = map(int, input().split())
A = list(map(int, input().split()))

# モンスターの残り体力
rest_H = H - sum(A)

if rest_H <= 0:
    print("Yes")
else:
    print("No")

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

#include <iostream>
#include <fstream>

#include <iostream>
#include <vector>

bool isSorted(const std::vector<int> &ns) {
    if (ns.size() <= 1) {
        return true;
    }
    for (int i = 1; i < ns.size(); ++i) {
        if (ns[i] < ns[i - 1]) {
            return false;
        }
    }
    return true;
}

class B0Or1Swap {
public:
    void solve(std::istream &in, std::ostream &out) {
        int n;
        in >> n;
        std::vector<int> ps;
        ps.reserve(n);

        for (int i = 0; i < n; ++i) {
            int p;
            in >> p;
            ps.push_back(p);
        }

        if (isSorted(ps)) {
            out << "YES";
            return;
        }

        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                std::vector<int> ks;
                ks.reserve(n);
                for (int k = 0; k < n; ++k) {
                    ks.push_back(ps[k]);
                }
                ks[i] = ps[j];
                ks[j] = ps[i];
                if (isSorted(ks)) {
                    out << "YES";
                    return;
                }
            }
        }

        out << "NO";
    }
};


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


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

int main() {
  ll n,W,v[100],w[100];
  cin>>n>>W;
  for (ll i = 0; i < n; i++)
  {
    cin>>v[i]>>w[i];
  }
  
  ll dp[101][10001];//max val. when w=i
  fill(dp[0],dp[0]+10001,0);
  for (ll i = 0; i < n; i++)
  {
    for (ll j = 0; j <=W; j++)
    {
      if (j>=w[i]) dp[i+1][j]=max(dp[i][j-w[i]]+v[i],dp[i][j]);
      else dp[i+1][j]=dp[i][j];
    }
    
  }
  
  cout<<dp[n][W]<<endl;

  return 0;
}



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

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	vector<int> mod(m);
	vector<int> pr(m);
	int ans = 0;
	
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	for(int i = 0; i < m; i++){
		mod[i] = 0;
		pr[i] = 0;
	}
	
	sort(a.begin(), a.end());
	
	mod[a[0] % m]++;
	for(int i = 1; i < n; i++){
		mod[a[i] % m]++;
		if(a[i] == a[i-1]){
			pr[a[i] % m] += 2;
			a[i] *= -1;
			a[i-1] *= -1;
		}
	}
	
	ans += mod[0] / 2;
	for(int i = 1; i < (m+1) / 2; i++){
		int tmp = min(mod[i], mod[m - i]);
		ans += tmp;
		mod[i] -= tmp;
		mod[m - i] -= tmp;
	}
	if(m % 2 == 0){
		ans += mod[m / 2] / 2;
		mod[m / 2] %= 2;
	}
	
	for(int i = 1; i < m; i++){
		ans += min(mod[i] / 2, pr[i] / 2);
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 1408
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        long upper = (long) Math.floor(Math.sqrt(N))+1L;
        long ans = helper(N);
        for(long i=upper;i>0;i--){
            if(N%i==0){
                ans = Math.max(helper(N/i),helper(i));
                break;
            }
        }
        System.out.println(ans);
    }
    static long helper(long n){
        if(n==0) return 0;
        long cnt = 0;
        while(n>0){
            cnt++;
            n = n/10;
        }
        return cnt;
    }
}


Measured memory_bytes: 22740
//raja1999

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
//#define int ll

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;


//std::ios::sync_with_stdio(false);

int main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int n;
	cin>>n;
	set<string>se;
	string s;
	int i;
	rep(i,n){
		cin>>s;
		se.insert(s);
		//cout<<se.size()<<endl;
	}
	cout<<se.size()<<endl;
	return 0;
} 


Measured memory_bytes: 19248
#include<stdio.h>
#include<string.h>
int main(void)
{
	char x[10000];
	int k,n,a,i;
	while(1)
	{
		scanf("%s", x);
		if(x[0]=='0')
		break;
		k=0;
		n=strlen(x);
		for(i=0; i<n; i++)
		{
			a=x[i]-'0';
			k+=a;
		}
		printf("%d\n", k);
	}
	
	return 0;
}


Measured memory_bytes: 2076
import java.util.*;
public class Main {

	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		while(n>0){
			String w = sc.next();
			int t = Integer.parseInt(w);
			int[] a = new int[8];
			for(int i=0; i<8; i++){ a[i] = t%10; t /= 10;}
			Arrays.sort(a);
			String min = a[0] +""+ a[1] +""+ a[2] +""+ a[3] +""+ a[4] +""+ a[5] +""+ a[6]+""+ a[7];
			String max = a[7] +""+ a[6] +""+ a[5] +""+ a[4] +""+ a[3] +""+ a[2] +""+ a[1]+""+ a[0];
			System.out.println(Long.parseLong(max)-Long.parseLong(min));
			n--;
		
		}
	}

}

Measured memory_bytes: 11000
#演習２－２ 
def tax(p,x):
    return p*(100+x) // 100 

def solve(X,Y,S):
    ans = 0
    oldsum = 0
    newsum = 0
    for a in range(1,S):
        for b in range(1,S-a+1): #税抜き価格a,bの総和はS以下である
            oldsum = tax(a,X)+tax(b,X) #税制改定前の税込合計額
            if oldsum == S: # 新税でのtax(a,Y)+tax(b,Y) について検討 
                newsum = tax(a,Y)+tax(b,Y) 
                if newsum > ans:
                    ans =newsum
            if oldsum > S:
                break # b増加ならばsum増加のため
    return ans

while True:
    X,Y,S = map(int, input().split())
    if X == 0:
        break
    print(solve(X,Y,S))


Measured memory_bytes: 5600
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define rep(i, n) for (ll i = 0; i < ll(n); i++)
#define repd(i, n) for (ll i = n - 1; i >= 0; i--)
#define all(x) x.begin(), x.end()

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

    int n;
    cin >> n;

    string s;
    vector<string> rsl = {"AC", "WA", "TLE", "RE"};
    vector<int> num(4, 0);
    rep(i, n) {
        cin >> s;
        rep(j, 4) {
            if (s == rsl[j]) {
                num[j]++;
                break;
            }
        }
    }
    
    rep(i, 4) {
        cout << rsl[i] << " x " << num[i] << endl;
    }
}

Measured memory_bytes: 3628
N = int(input())
h = list(map(int, input().split()))

tmp = [int(1e9)] * (N+10)
tmp[0] = 0
tmp[1] = abs(h[1] - h[0])
for i in range(2, N):
    tmp[i] = min(tmp[i-2]+abs(h[i]-h[i-2]), tmp[i-1]+abs(h[i]-h[i-1]))


print(tmp[N-1])

Measured memory_bytes: 13980
#include <bits/stdc++.h>
using namespace std;
#define all int i=0; i<n; i++
#define pb push_back
typedef long long int ll;

#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define endl '\n'
#define mod 1000000007

bool sortinrev(const pair<ll,ll> &a,  
               const pair<ll,ll> &b) 
{ 
       return (a.first > b.first); 
}
int ans = 0; int a,b,c;
void solve(){
	while(true){
		if(b>=1 && c>=2){
			ans+=3;
			b--;
			c-=2;
		}
		else break;
	}
	while(true){
		if(a>=1 && b>=2){
			ans+=3;
			b-=2;
			a--;
		}
		else break;
	}
	cout<<ans<<endl;
}
ll power(ll x, ll y, ll p) 
{ 
    ll res = 1;
  
    x = x % p;
  
    while (y > 0) 
    { 
        if (y & 1){
			res = (res*x) % p; 
			y--;
		}
        y = y>>1;
        x = (x*x) % p;   
    } 
    return res; 
}
int main(){ 
 	int n;
 	cin>>n;
 	int arr[n], sum=0;
 	for(all)cin>>arr[i];
 	for(int i=0; i<n; i++){
 		for(int j=i+1; j<n; j++){
 			ans+=arr[i]*arr[j];
		 }
	 }
	 cout<<ans<<endl;
}



Measured memory_bytes: 256
#!/usr/bin/env python3
from math import hypot

EPS = 10 ** -8


def f(r):
    global n, xy
    cs = []
    for i in range(n):
        for j in range(i + 1, n):
            x0, y0 = xy[i]
            x1, y1 = xy[j]
            d = hypot(x1 - x0, y1 - y0)
            if r - d / 2 < EPS:
                continue
            h = (r ** 2 - (d / 2) ** 2) ** 0.5
            c = [(x0 + x1) / 2, (y0 + y1) / 2]
            cs.append([c[0] + h * (y0 - y1) / d, c[1] + h * (x1 - x0) / d])
            cs.append([c[0] - h * (y0 - y1) / d, c[1] - h * (x1 - x0) / d])
    for cx, cy in cs:
        if all(hypot(x - cx, y - cy) - r < EPS for x, y in xy):
            return True
    return False


n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
ok = 10 ** 9
ng = 0
while abs(ok - ng) > EPS:
    m = (ok + ng) / 2
    if f(m):
        ok = m
    else:
        ng = m
print(ok)


Measured memory_bytes: 3572
n,m = map(int, input().split())
d = dict()
for i in range(1,n+1):
  d[i] = 0
for _ in range(m):
  a = map(int, input().split())
  for x in a:
    d[x] += 1
    d[x] %= 2
if any(d.values()):
  print("NO")
else:
  print("YES")

Measured memory_bytes: 15084
#include <bits/stdc++.h>
using namespace std;
 
int a[200020];
int lps = 1, lpp = 0, lpl = 0; // loop start, loop path, loop length
map <int,int> was;

pair <int,pair<int,int>> lpGet(int i, int s) {
  // printf(">>>> %d \n",i);
  if (was.count(i)) return make_pair(i,make_pair(was[i],s));
  was[i] = s;
  return lpGet(a[i],s+1);
}
 
int walk(int start, int s) {
  if (s==0) return start;
  return walk(a[start],s-1);
}
 
int main() {
  int n;
  long long k;
  scanf("%d%lld",&n,&k);
  for (int i = 0; i < n; i++) {
    scanf("%d",&a[i+1]);
  }

  pair <int,pair<int,int>> lp = lpGet(1,0);
  // printf("lpGet: done\n");
  // printf("lpGet: (%d, (%d, %d))\n",lp.first,lp.second.first,lp.second.second);
  lpp = lp.second.first;
  lps = lp.first;

  if (k<lpp) {
    printf("%d\n",(walk(1,k)));
    return 0;
  }

  was.clear();
  lpl = lpGet(lps,0).second.second;
 
  k = k - lpp;
  k%=lpl;
  
  // printf("%lld %d %d \n",k,lps,lpp);
  
  printf("%d\n",(walk(lps,k)));
  return 0;
 
}

Measured memory_bytes: 29296
//条件によって絞り込むことができる

#include<bits/stdc++.h>

using namespace std;

signed main(){

    int a,b,c,d,e,k;
    cin >>a >>b >>c >>d >>e >>k;
    
    cout<<( e - a <= k ? "Yay!" : ":(");
    
    return 0;

 }


Measured memory_bytes: 256