akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long int

ll groupingRec(vector<vector<ll>> &arr, int n, int mask, vector<ll> &dp,
               vector<ll> &scores){

    if(dp[mask] != -1)
        return dp[mask];
    // Pick a non-empty subset of not chosen rabbits among 2^n possible subsets
    // and take that as one group
    ll ans = 0;
    for(int group = 1; group<(1<<n); group++){
        if(!(group&mask)){ // If these rabbits are not yet taken
            ll currGroupScore = scores[group];
            ll currRecAns = groupingRec(arr, n, mask|group, dp, scores) +
                            currGroupScore;
            if(currRecAns > ans)
                ans = currRecAns;
        }
    }
    dp[mask] = ans;
    return ans;
}

void precalculateScores(vector<vector<ll>> &arr, int n, vector<ll> &scores){

    // Store the score for every group combinations

    for(int group=0; group<(1<<n); group++){
        ll score = 0;
        for(int i=0; i<n; i++)
            if((group&(1<<i)))
                for(int j=i+1; j<n; j++)
                    if((group&(1<<j)))
                        score += arr[i][j];
        scores[group] = score;
    }
}

ll grouping(vector<vector<ll>> &arr, int n){

    vector<ll> dp(1<<n, -1);
    vector<ll> scores(1<<n);
    precalculateScores(arr, n, scores);
    ll ans = groupingRec(arr, n, 0, dp, scores);
    return ans;
}

int main()
{
 int n;
 cin>>n;
 vector<vector<ll>> arr(n, vector<ll>(n));
 for(int i=0; i<n; i++)
    for(int j=0; j<n; j++)
        cin>>arr[i][j];
 ll ans = grouping(arr, n);
 cout<<ans;
 return 0;
}

Measured memory_bytes: 4316
from math import gcd
K=int(input())
ans=0
for i in range(1,K+1):
  for j in range(1,K+1):
    a=gcd(i,j)
    if a==1:
      ans+=K
    else:
      for k in range(1,K+1):
        ans+=gcd(a,k)
print(ans)

Measured memory_bytes: 68788
#include <iostream>
#include <algorithm>
#include <string>
#include "stdio.h"
#include <vector>
#include <functional>
#include "math.h"
#include <set>
#include <iomanip>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define VI vector<int>
#define debug(x) cout<<#x<<": "<<x<<endl
#define DEBUG(x) cout<<#x<<": "<<x<<endl
int N;
vector<char> a;
vector<vector <int> > ans;
string S;

int main()
{
	cin >>N>> S;

	REP(i,S.length()){
		if(S[i]-'A'+ N >= 26){
			S[i] = S[i]+N-26;
		} else{
			S[i] = S[i]+N;
		}
	}

cout << S;

}



Measured memory_bytes: 256
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        int S = sc.nextInt();
        long ans = 0;
        for(int x=Math.max(0,S-2*K);x<=Math.min(K,S);x++){
            int left = S-x;
            ans += Math.min(K,left)-Math.max(0,left-K)+1;
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 21332
from collections import deque

k=int(input())


q = deque([1,2,3,4,5,6,7,8,9])

i=0
ans=0
while i < k:
    ans=q.popleft()
    if ans%10 != 0:
        q.append(10*ans+ans%10-1)
    q.append(10*ans+ans%10)
    if ans%10 != 9:
        q.append(10*ans+ans%10+1)
    i+=1
print(ans)



Measured memory_bytes: 18876
#include <iostream>
using namespace std;
int main(int argc, char const *argv[]) {
  int a,b;
  cin>>a>>b;
  if(a>=13){
    cout<<b<<endl;
  }else if(a>=6&&a<13){
    cout<<b/2<<endl;
  }else{
    cout<<'0'<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <deque>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <cmath>

using namespace std;

int main() {
    int N;
    cin >> N;
    deque<int> A(N);
    
    for (auto& e: A) cin >> e;

    sort(A.begin(), A.end());

    int first = A.front();
    int last = A.front();
    A.pop_front();

    long long int ans = 0;
    while (!A.empty()) {
        int dff = abs(A.front() - first);
        int dbf = abs(A.back() - first);
        int dfl = abs(A.front() - last);
        int dbl = abs(A.back() - last);

        int tf = max(dff, dbf);
        int tl = max(dfl, dbl);
        if (tf > tl) {
            if (dff > dbf) {
                ans += dff;
                first = A.front();
                A.pop_front();
            } else {
                ans += dbf;
                first = A.back();
                A.pop_back();
            }
        } else {
            if (dfl > dbl) {
                ans += dfl;
                last = A.front();
                A.pop_front();
            } else {
                ans += dbl;
                last = A.back();
                A.pop_back();
            }

        }
    }

    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 640
#include<stdio.h>

int main()
{
	int i,j,a;
	int dise[6] = {0};
	char move;
	
	for(i=0;i<6;i++){
		scanf("%d\n",&dise[i]);
	}
	
	while(1){
		scanf("%c",&move);
		if(move == 'E'){
			a = dise[0];
			dise[0] = dise[3];
			dise[3] = dise[5];
			dise[5] = dise[2];
			dise[2] = a;
		}else if(move == 'N'){
			a = dise[0];
			dise[0] = dise[1];
			dise[1] = dise[5];
			dise[5] = dise[4];
			dise[4] = a;
		}else if(move == 'S'){
			a = dise[0];
			dise[0] = dise[4];
			dise[4] = dise[5];
			dise[5] = dise[1];
			dise[1] = a;
		}else if(move == 'W'){
			a = dise[0];
			dise[0] = dise[2];
			dise[2] = dise[5];
			dise[5] = dise[3];
			dise[3] = a;
		}
		
		if(move == '\n'){
			break;
		}
	}
	
	printf("%d\n",dise[0]);
	
	return 0;
}

Measured memory_bytes: 596
#include <iostream>

int main() {
	using namespace std;

	int sampleNum;
	cin >> sampleNum;

	for (; sampleNum > 0; --sampleNum) {
		int a, b, c;
		cin >> a >> b >> c;
		bool right = false;
		right = a * a == b * b + c * c || b * b == c * c + a * a || c * c == a * a + b * b;
		cout << (right ? "YES" : "NO") << endl;
	}

	return 0;
}

Measured memory_bytes: 0
class KMP:
    def partial(self, P):
        ret = [0]
        for i in range(1, len(P)):
            j = ret[i - 1]
            while j > 0 and P[j] != P[i]:
                j = ret[j - 1]
            ret.append(j + 1 if P[j] == P[i] else j)
        return ret

    def search(self, S, P):
        partial, ret, j = self.partial(P), [], 0        
        for i in range(len(S)):
            while j > 0 and S[i] != P[j]:
                j = partial[j - 1]
            if S[i] == P[j]: j += 1
            if j == len(P): 
                ret.append(i - (j - 1))
                j = partial[j - 1]
        return ret

def main():
    S=list(map(ord,input()))
    T=list(map(ord,input()))
    N,M=len(S),len(T)
    I=KMP().search(S*(M//N+2),T)
    A=[False]*N
    B=[False]*N
    C=[0]*N
    for i in I:
        A[i%N]=True
    for i in range(N):
        if B[i]: continue
        B[i]=True
        j=i
        acc=0
        while A[j]:
            j=(j+M)%N
            acc+=1
            if B[j] and A[j]:
                C[i]=C[j]+acc
                break
            C[j]=max(C[j],acc)
            B[j]=True
        if acc and i==j:
            print(-1)
            return
        C[i]=max(C[i],acc)
    print(max(C))

if __name__ == "__main__":
    main()

Measured memory_bytes: 132588
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
import math
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math as M
MOD=10**9+7
import sys
#####################################
n=int(input())
A=INPUT()
money=1000
for i in range(n-1):
    stocks=0
    if A[i]<A[i+1]:
        stocks=money//A[i]
    money+=(A[i+1]-A[i])*stocks
print(money)


Measured memory_bytes: 62168
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;   
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define PI 3.14159265
#define ll long long
#define ld long double
#define vi vector<int>
#define pb push_back
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 300000000000000001
#define infx 9223372036854775806
#define all(c) c.begin(),c.end()
#define mk(x,yy) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define eb emplace_back
#define ff first
#define ss second
#define re return
// #define endl "\n"
#define max2(x,y)           (x>y)?x:y
#define min2(x,y)           (x<y)?x:y
#define mid(s,e)               (s+(e-s)/2)
#define mini                   INT_MIN
#define maxo                   INT_MAX
#define rep(i,a,b) for(int i=a;i<(int)(b);++i)
#define read(a,n) for(int i=0;i<n;i++)cin>>a[i]
#define show(a,n) for(int i=0;i<n;i++)cout<<a[i]<<' ';cout<<endl
#define ene cout<<"\n";

ll gcd(ll a, ll b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);  
      
}
ll power(ll x,  ll y, ll p) 
{ 
    ll res = 1;      // Initialize result 
  
    x = x % p;  // Update x if it is more than or  
                // equal to p 
  
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res*x) % p; 
  
        // y must be even now 
        y = y>>1; // y = y/2 
        x = (x*x) % p;   
    } 
    return res; 
} 
 
bool compr(std::vector<ll> a, std::vector<ll> b)
{
    if(a[0]==b[0])
        return a[1]<b[1];
    else
        return a[0]<b[0];
}

bool comp(std::vector<ll> a, std::vector<ll> b)
{
    if(a[1]==b[1]&&a[2]==b[2])
        return a[0]<b[0];
    else if(a[1]==b[1])
        return a[2]>b[2];
    else
        return a[1]<b[1];
}
ll dp[100005] = {};
ll pre[100005] = {};
int main()
{
    #ifdef SHIVANSH 
     freopen("input.txt","r",stdin);
     freopen("output.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,k;
    cin>>n>>k;
    ll a[n];
    for(ll i=0;i<n;i++)
        cin>>a[i];
    // ll dp[k+1] = {};
    for(ll i=0;i<=a[0];i++)
        dp[i] = 1;
    ll sm = a[0];
    // ll pre[k+2] = {};
    for(ll i=1;i<=k+1;i++)
    {
        pre[i] = pre[i-1]+dp[i-1];
    }
    // cout<<"hello"<<endl;
    for(ll i=1;i<n;i++)
    {
        sm = min(sm+a[i],k);
        // cout<<"pta hai"<<endl;
        for(ll j=sm;j>=0;j--)
        {
            ll tmp = 0;
            // cout<<j<<endl;
            if(j-a[i]>=0)
            {
                tmp = (pre[j+1]-pre[j-a[i]]+mod)%mod;
            }
            else
                tmp = pre[j+1];
            dp[j] = tmp; 
        }
        // cout<<"pta "<<endl;
        for(ll i=1;i<=k+1;i++)
        {
            pre[i] = (pre[i-1]+dp[i-1])%mod;
        }
        // cout<<"pta nai"<<endl;

    }
    cout<<dp[k]<<endl;

}

Measured memory_bytes: 5180
N, M = map( int, input().split())
ANS = [1]*(M+1)
ANS[0] = 0
for _ in range(N):
    C = list( map( int, input().split()))[1:]
    for i in range(1, M+1):
        if i in C:
            pass
        else:
            ANS[i] = 0
print( sum(ANS))


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

class Program
{
    static void Main(string[] args)
    {
        string[] QHSD = Console.ReadLine().Split();
        int Q = int.Parse(QHSD[0]);
        int H = int.Parse(QHSD[1]);
        int S = int.Parse(QHSD[2]);
        int D = int.Parse(QHSD[3]);
        double N = double.Parse(Console.ReadLine());

        // Order them from best to worst
        var options = new List<Tuple<double, int, double>>();
        options.Add(new Tuple<double, int, double>(0.25, Q, Q / 0.25));
        options.Add(new Tuple<double, int, double>(0.5, H, H / 0.5));
        options.Add(new Tuple<double, int, double>(1, S, (double)S / 1));
        options.Add(new Tuple<double, int, double>(2, D, (double)D / 2));
        options.Sort((x,y) => x.Item3.CompareTo(y.Item3));

        // Now go through and max them out
        ulong cost = 0;
        foreach (var o in options)
        {
            int itemsToAdd = (int)(N / o.Item1);
            cost += (ulong)itemsToAdd * (ulong)o.Item2;
            N -= itemsToAdd * o.Item1;
        }

        Console.WriteLine(cost);
        Console.ReadLine();
    }
}



Measured memory_bytes: 13268
import java.util.Scanner;

public class Main
{
    public static void main(String[] args) 
    {
        Scanner scanner = new Scanner(System.in);
        int s = scanner.nextInt();
        
        
        System.out.println(s / 3600 +":"+(s%3600/60)+":"+(s%3600%60%60) );
        
        
        return;
    }
}


Measured memory_bytes: 26276
N,M=map(int,input().split())
A=list(map(int,input().split()))




S=[0]*(N+1)
for i in range(N):
    S[i+1]=(A[i]+S[i])%M


def tr(k):
    return k*(k-1)//2

S.sort()
S=[-1]+S+[-1]
count=0
ANS=0

for i in range(1,N+3):
    if S[i]==S[i-1]:
        count+=1
    else:
        ANS+=tr(count)
        count=1

print(ANS)


Measured memory_bytes: 14696
#include <iostream>
#include <vector>

using namespace std;

long long f(long long b, long long n){
    long long res = 0;
    while(n){
        res += n%b;
        n /= b;
    }
    return res;
}

long long solve(long long n, long long s){
    for(long long b=2;b*b<=n;b++){
        if(f(b, n) == s) return b;
    }
    long long res = -1;
    for(long long d=1;d*d<n;d++){
        auto src = n/(d+1) + 1;
        auto dst = n/d;
        if(n-s+d < 0) continue;
        if((n-s+d)%d != 0) continue;
        auto c = (n-s+d)/d;
        if(c < src || dst < c) continue;
        if(res == -1 || c < res) res = c;
    }
    if(res != -1) return res;
    if(s == n) return n+1;
    return -1;
}

int main(){
    long long n, s;
    while(cin >> n >> s){
        cout << solve(n, s) << endl;
    }
}

Measured memory_bytes: 256
p=0
n,m=map(int,input().split())
d = {i:[] for i in range(n)}
h=list(map(int,input().split()))
for i in range(m):
    a,b=map(int,input().split())
    d[a-1].append(b-1)
    d[b-1].append(a-1)
#print(d)
for i,j in d.items():
    hi=h[i]
    if set([hi-h[k]>0 for k in j])==set([True]):
        p+=1
    elif j==[]:
        p+=1
print(p)

Measured memory_bytes: 37844
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
				new Main().solveA();
		//		new Main().solveB();
//		new Main().solveC();
		// new Main().solveD();
	}

	private void solveA() {
		Scanner scanner = null;
		int numH = 0;
		int numW = 0;
		int h = 0;
		int w = 0;

		try {
			scanner = new Scanner(System.in);
			numH = scanner.nextInt();
			numW = scanner.nextInt();
			h = scanner.nextInt();
			w = scanner.nextInt();

			int total = numH * numW;
			int col = h * numW;
			int row = w * (numH - h);
			System.out.println(total - col - row);

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

	private void solveB() {
		Scanner scanner = null;
		int numN = 0;
		int numM = 0;
		int numC = 0;

		try {
			scanner = new Scanner(System.in);
			numN = scanner.nextInt();
			numM = scanner.nextInt();
			numC = scanner.nextInt();
			int[] bArray = new int[numM];
			int[][] aArray = new int[numN][numM];

			for (int i = 0; i < bArray.length; i++) {
				bArray[i] = scanner.nextInt();

			}
			for (int i = 0; i < aArray.length; i++) {
				for (int j = 0; j < aArray[i].length; j++) {
					aArray[i][j] = scanner.nextInt();
				}
			}
			int cnt = 0;

			for (int i = 0; i < aArray.length; i++) {
				int res = 0;
				for (int j = 0; j < aArray[i].length; j++) {
					res += (aArray[i][j] * bArray[j]);
				}
				if (res + numC > 0) {
					cnt++;
				}
			}

			System.out.println(cnt);

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

	public static class LComp implements Comparator<Long[]> {

		@Override
		public int compare(Long[] o1, Long[] o2) {
			return Long.compare(o1[0], o2[0]);
		}

	}

	private void solveC() {
		Scanner scanner = null;
		int numN = 0;
		long numM = 0;

		try {
			scanner = new Scanner(System.in);
			numN = scanner.nextInt();
			numM = scanner.nextLong();

			Long[][] wk = new Long[numN][2];

			for (int i = 0; i < numN; i++) {
				wk[i][0] = scanner.nextLong();
				wk[i][1] = scanner.nextLong();
			}

			//			Arrays.sort(wk, new LComp());
			Arrays.sort(wk, (x, y) -> Long.compare(x[0], y[0]));

			long resNumM = numM;
			long res = 0;
			for (int i = 0; i < wk.length; i++) {
				if (resNumM == 0) {
					break;
				}
				long key = wk[i][0];
				long value = wk[i][1];
				if (resNumM >= value) {
					res += (key * value);
					resNumM -= value;
				} else {
					res += (key * resNumM);
					resNumM = 0;
				}

			}

			System.out.println(res);

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

	private void solveD() {
		Scanner scanner = null;
		int numN = 0;
		int numK = 0;
		int numS = 0;

		try {
			scanner = new Scanner(System.in);
			numN = scanner.nextInt();

			System.out.println("");

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}
}

Measured memory_bytes: 21844
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string str;

main(){
  while(cin >> str){
    char ope = ' ';
    bool er = false;
    int ans = 0, i = 0;
    while(1){
      if(ope == ' '){
        string s;
        while('0' <= str[i] && str[i] <= '9') s += str[i++];
        if(s.size() > 4){
          er = true;
          break;
        }
        ans += atoi(s.c_str());
        
        ope = str[i++];
      }else{
        if(ope == '=') break;
        string s;
        while('0' <= str[i] && str[i] <= '9') s += str[i++];
        if(s.size() > 4){
          er = true;
          break;
        }
        int tmp = atoi(s.c_str());
        if(ope == '+') ans += tmp;
        if(ope == '-') ans -= tmp;
        if(ope == '*') ans *= tmp;
        ope = str[i++];
      }
      if(ans < 0 || 9999 < ans){
        er = true;
        break;
      }
    }
    if(er) cout << 'E' << endl;
    else cout << ans << endl;
  }
}

Measured memory_bytes: 0
/* kadai4_3
   Saikyo_Kazune
*/
#include <stdio.h>
//プロトタイプ宣言
int snow_depth(int west_height_seen,int east_height_seen);

int main(void){
   
   //int型　雪上に見えている等の高さを格納する変数を宣言
   int west_height_seen,east_height_seen;
   //標準入力から受け取り
   scanf("%d %d",&west_height_seen,&east_height_seen);
   //関数により雪の深さを求めて出力
   printf("%d\n", snow_depth(west_height_seen,east_height_seen));
   return 0;
}
int snow_depth(int west_height_seen,int east_height_seen){
    //西側の塔の本来の高さを格納する変数 int west_heightを宣言
    int west_height=0;
    //雪の上に見えている東側の塔の高さから西側の等の高さを引いた数がnのとき、西側の塔本来のたかさが0からn-1までの和であるから
    for(int i=0;i<(east_height_seen-west_height_seen);i++){
        west_height+=i;
    }
    //西側の塔の本来の高さから雪上に見える高さを引いたものが雪の深さ
    return west_height-west_height_seen;
}

Measured memory_bytes: 128
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]

[N,K]=i2()
a=i2()
mod = 10**9+7
c=[0 for i in range(N+1)]
ci=[0 for i in range(N+1)]
c[0]=1
for i in range(1,N+1):
 c[i]=c[i-1]*i
 c[i]%=mod
def bp(x,n):
        r=1
        while(n):
           if n%2:
              r=r*x%mod
           x=x*x%mod
           n>>=1
        return r
for i in range(N+1):
  ci[i]=bp(c[i],10**9+5)
ans=0
a.sort()
for i in range(N):
 if i>=K-1:
   ans+=a[i]*((c[i]*ci[i-K+1]*ci[K-1])%mod)
 if i<=N-K:
   ans-=a[i]*((c[N-i-1]*ci[N-i-1-K+1]*ci[K-1])%mod)
 ans%=mod
print(ans%mod)

Measured memory_bytes: 64936
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
using P = pair<ll,ll>;
const ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REPS(i,n) for(ll (i)=1;(i)<=(n);(i)++)
#define RREP(i,n) for(ll (i)=(n-1);(i)>=0;(i)--)
#define RREPS(i,n) for(ll (i)=(n);(i)>0;(i)--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());

template<class T> inline void chmin(T& a, T b){
    if (a > b){
        a = b;
    }
}

template<class T> inline void chmax(T& a, T b){
    if (a < b){
        a = b;
    }
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    int N;
    cin >> N;
    vector<pair<ll,ll>> A(N);
    REP(i,N){
        ll As,Bs;
        cin >> As >> Bs;
        A[i] = mp(As+Bs,As);
    }
    sort(ALL(A),greater<>());
    ll answer = 0;
    REP(i,N){
        if(i%2 == 0){
            answer += A[i].S;
        }else{
            answer -= A[i].F - A[i].S;
        }
    }
    cout << answer << "\n";
}

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

using ll = long long;

#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 rng(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

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

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

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  rep(i, (int)v.size()) {
    if (i)
      os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
  for (auto val : array)
    std::cout << val << ", ";
  std::cout << "\n";
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << std::setprecision(10);

  string s; std::cin >> s;
  int n = s.size();
  if (n == 2 && s[0] == s[1]) {
    std::cout << "1 2" << "\n";
    return 0;
  } 
  rep(i, n-2) {
    map<char, int> cnt;
    cnt[s[i]]++, cnt[s[i+1]]++, cnt[s[i+2]]++;
    if (cnt.size() != 3) {
      std::cout << i+1 << " " << i+3 << "\n";
      return 0;
    }
  }
  std::cout << -1 << " " << -1 << "\n";
}


Measured memory_bytes: 512
#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
from typing import *
import collections
import itertools
import math
import sys

INF = float('inf')


def solve(N: int, A: "List[int]"):
    c = collections.Counter(A+[i+1 for i in range(N)])
    return "\n".join([f'{c[i+1]-1}' for i in range(N)])


def main():

    sys.setrecursionlimit(10 ** 6)

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N - 2 + 1)]  # type: "List[int]"
    print(solve(N, A))


if __name__ == '__main__':
    main()


Measured memory_bytes: 132496
import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try {
            int w = Integer.parseInt(br.readLine());
            int[] x = new int[w+1];
            for (int i = 0; i < w+1; i++) {
                x[i] = i;
            }
            int n = Integer.parseInt(br.readLine());
            for (int i = 0; i < n; i++) {
                String st = br.readLine();
                String[] s = st.split(",", 0);
                int a = Integer.parseInt(s[0]);
                int b = Integer.parseInt(s[1]);
                int sw = x[a];
                x[a] = x[b];
                x[b] = sw;
            }
            for (int i = 1; i < w+1; i++) {
                System.out.println(x[i]);
            }
        } catch (Exception ex) {
            System.exit(0);
        }
    }
}

Measured memory_bytes: 24124
n,y = map(int, input().split())

y //= 1000
a,b,c = -1,-1,-1

for ai in range(n+1):

    if ai*10> y:
        break

    if ai  == y:
        a,b,c = ai,0,0
        break

    remain = n-ai
    for bi in range(remain+1):
        ci = remain - bi
        
        if y == ai *10  + bi * 5 + ci :
            a,b,c = ai,bi,ci


print('{} {} {}'.format(a,b,c))



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

using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

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; }

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  vector<vector<int>> A(3);
  vector<vector<int>> C(3);

  int tmp;
  rep(i, 3){
    rep(j, 3){
      cin >> tmp;
      A[i].push_back(tmp);
      C[i].push_back(0);
    }
  }

  int N;
  cin >> N;
  vector<int> B(N);
  rep(i, N) cin >> B[i];

  rep(i, 3){
    rep(j, 3){
      rep(k, N){
        if(A[i][j] == B[k]){
          C[i][j] = 1;
        }
      }
    }
  }

  // 横に
  bool ans = false;

  rep(i, 3){
    int cnt = 0;
    rep(j, 3){
      cnt += C[i][j];
    }
    if(cnt == 3){
      ans = true;
      break;
    }
  }

  rep(i, 3){
    int cnt = 0;
    rep(j, 3){
      cnt += C[j][i];
    }
    if(cnt == 3){
      ans = true;
      break;
    }
  }

  // ななめに
  if(C[0][0] + C[1][1] + C[2][2] == 3){
    ans = true;
  }

  if(C[0][2] + C[1][1] + C[2][0] == 3){
    ans = true;
  }

  if(ans){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }



  

  return 0;
}


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

int main(){
  int W,N;
  int dp[1001];
  int num = 1;
  while(scanf("%d",&W),W){
    scanf("%d",&N);
    memset(dp,0,sizeof(dp));
    
    for(int i=0;i<N;i++){
      int v,w;
      scanf("%d,%d",&v,&w);
      for(int j=W;j>=0;j--){
	if(j+w <= W)dp[j+w] = max(dp[j+w], dp[j]+v);
      }
    }
    cout << "Case " << num++ << ":\n"; 
    cout << dp[W] << endl << (lower_bound(dp,dp+W+1,dp[W])-dp) << endl;
  }
}

Measured memory_bytes: 1212
N,M = map(int,input().split())
es = [tuple(map(int,input().split())) for i in range(M)]

INF = float('inf')
d = [INF] * N
d[0] = 0
for i in range(N):
    for fr,to,cost in es:
        fr,to = fr-1,to-1
        cost *= -1
        if d[fr] != INF and d[to] > d[fr]+cost:
            d[to] = d[fr] + cost
            if i == N-1 and to == N-1:
                print('inf')
                exit()
print(-d[-1])

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

int main(){
	int x,y;
	cin>>x>>y;
	if(x<y){
		int tmp;
		tmp = x;
		x = y;
		y = tmp;
	}
	int amari = x%y;
	while(amari!=0){
		x=y;
		y=amari;
		amari = x%y;
	}
	cout<<y<<endl;
	return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/















int H, W, A[80][80], B[80][80];
bitset<30101> dp[80][80];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> H >> W;
	rep(y, 0, H) rep(x, 0, W) cin >> A[y][x];
	rep(y, 0, H) rep(x, 0, W) cin >> B[y][x];

	int base = 15000;
	dp[0][0].set(base + A[0][0] - B[0][0]);
	dp[0][0].set(base - A[0][0] + B[0][0]);

	rep(y, 0, H) rep(x, 0, W) {
		int d = abs(A[y][x] - B[y][x]);
		if (y) {
			dp[y][x] |= dp[y - 1][x] >> d;
			dp[y][x] |= dp[y - 1][x] << d;
		}
		if (x) {
			dp[y][x] |= dp[y][x - 1] >> d;
			dp[y][x] |= dp[y][x - 1] << d;
		}
	}

	int ans = inf;
	rep(d, 0, 30101) if (dp[H - 1][W - 1][d]) {
		chmin(ans, abs(d - base));
	}
	cout << ans << endl;
}







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

const int MAX_N = 101010;
int N, K;
int h[MAX_N];
int cost[MAX_N];

int main(){

    for(int i = 1; i < MAX_N; i++)cost[i] = 1145141919;
    cin >> N >> K;
    for(int i = 0; i < N; i++)cin >> h[i];
    for(int i = 0; i < N; i++){
        for(int k = 1; k <= K; k++){
            cost[i + k] = min(cost[i + k], cost[i] + abs(h[i] - h[i + k]));
        }
    }
    cout << cost[N - 1] << endl;

    return 0;
}

Measured memory_bytes: 1024
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define rrep(i,n) for(ll i##_len=(n) ,i=i##_len-1;i>=0;--i)
#define repi(i,a,b) for(ll i=ll(a);i<=ll(b);++i)
#define ALL(f,x,...) ([&](decltype((x)) xxxx) { return (f)(begin(xxxx), end(xxxx), ## __VA_ARGS__); })(x)
#define lim 1000000007ll
#define Yes(flag) cout<<((flag)? "Yes":"No");
#define YES(flag) cout<<((flag)? "YES":"NO");
#define MSG(msg1,msg2,flag) cout<<((flag)? msg1:msg2);

#include<bits/stdc++.h>
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = std::pair<ll,ll>;
using namespace std;
template<class T>T 
chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
template<class T>T 
chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template <class T> T 
gcd(T a, T b){if (a < b) {a ^= b;b ^= a;a ^= b;} return b ? gcd(b, a % b) : a;}
template <class T> T 
lcm(T a, T b){return a * b / gcd(a, b);}
vector<char> 
string_to_vector_char(const string& input){vector<char> out(input.length());rep(i,input.length()){out[i]=input[i];}return out;}
template <class T> map<T,int> 
count_same_elements(const vector<T>& v){map<T,int>cmap; for_each(v.begin(),v.end(),[&cmap](auto x){cmap[x]++;}); return cmap; }
template<class A,class B> vector<B> 
mapf(const vector<A>& v,const function<B(A)>& func){vector<B> v_(v.size());rep(i,v.size()){ v_[i]=func(v[i]); }return v_;}
template<class A,class B> vector<B> 
adjacent_map(const vector<A>& v,const function<B(A,A)>& func){vector<B> v_(v.size()-1);rep(i,v.size()-1){ v_[i]=func(v[i+1],v[i]); }return v_;}
template<class A> bool
all_of(const vector<A>& v){bool flag=true;rep(i,v.size()){ if(v[i]<1){flag=false;}; }return flag;}
template<class A> bool
any_of(const vector<A>& v){bool flag=false;rep(i,v.size()){ if(v[i]>0){flag=true; break;}; }return flag;}
template<class A> bool
none_of(const vector<A>& v){bool flag=true;rep(i,v.size()){ if(v[i]>0){flag=false;}; }return flag;}
template<class T>
void scan_vector(long long size,vector<T>& vector){
    vector.resize(size);
    for(long long i=0;i<size;++i){
        cin>>vector[i];
    }
}
int n,m,x,y;
vector<int> xx,yy;
void input(){
    cin>>n>>m>>x>>y;
    scan_vector(n,xx);
    scan_vector(m,yy);
}
void src(){
    xx.push_back(x);
    yy.push_back(y);
    sort(xx.begin(),xx.end());
    sort(yy.begin(),yy.end());
    MSG("No War","War",yy.front()-xx.back()>0);
}   

int main(int argc,char* argv[]){
    ios::sync_with_stdio(false);
 //   ifstream in( argv[1] ); cin.rdbuf(in.rdbuf());
    input();
    src();    
    return 0;
}

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

int main() {
  int n;cin>>n;
  vector<int> vec(n);
  rep(i,n) cin>>vec[i];
  int pre = -999;
  rep(i,n) {
    if (pre<=vec[i]-1) {
      pre=vec[i]-1;
    }
    else if (pre<=vec[i]) {
      pre = vec[i];
    }
    else {
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;
  return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define forn for(int i=0;i<n;i++)
#define pb push_back
#define pr pair<int,int>
#define mp make_pair
#define ll long long int
const int mod=1e9+7;
int main()
{
    ll t=1;
    while(t--){
   ll n,m;
   cin>>n>>m;
   ll ans=0;
   if(n<2)ans+=0;
   else ans+=(n*(n-1))/2;
   if(m<2)ans+=0;
   else ans+=(m*(m-1))/2;
   cout<<ans<<endl;
    }
}

Measured memory_bytes: 256
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, M = in_nn()

    dim = [0] * N
    edge = [set() for _ in range(N)]
    for i in range(N + M - 1):
        x, y = in_nn()
        x, y = x - 1, y - 1
        dim[y] += 1
        edge[x].add(y)

    root = dim.index(0)
    q = deque()
    q.append(root)

    while q:
        v = q.popleft()
        delete = set()
        for nv in edge[v]:
            if dim[nv] > 1:
                dim[nv] -= 1
                delete.add(nv)
            else:
                q.append(nv)
        edge[v] -= delete

    ans = [-1] * N

    for v1 in range(N):
        for v2 in edge[v1]:
            ans[v2] = v1

    for i in range(N):
        print(ans[i] + 1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 41908
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
//#define i_7 (ll)(1E9+7)
#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E18;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
////////////////////////////



int main(){fastio
    ll n,p;cin>>n>>p;
    vector<ll>v[n+1];
    rep(i,1,n-1){
        ll a,b;cin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
    }
    ll par[n+1];memset(par,-1,sizeof(par));
    par[1]=0;
    vector<ll>chi[n+1];
    
    ll ans[n+1];memset(ans,0,sizeof(ans));
    while(p--){
        ll a,b;cin>>a>>b;
        ans[a]+=b;
    }
    queue<ll>q;q.push(1);
    while(!q.empty()){
        ll t=q.front();q.pop();
        for(auto x:v[t]){
            if(par[x]==-1){
                par[x]=t;
                chi[t].pb(x);
                q.push(x);
                ans[x]+=ans[t];
            }
        }
    }
    rep(i,1,n)cout<<ans[i]<<" ";
    
    return 0;
}


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

const int nm = 1e5;
int n, a[nm], x;
long long rv = 0;

int main() {
	cin >> n >> x;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n - 1; i++) {
		if (a[i] + a[i + 1] > x) {
			rv += a[i] + a[i + 1] - x;
			a[i + 1] = max(0, x - a[i]);
		}
	}
	cout << rv << endl;
}


Measured memory_bytes: 640
use proconio::input;
use proconio::marker::{Chars, Usize1};
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused)]
const ALPHA_SMALL: [char; 26] = [
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's',
    't', 'u', 'v', 'w', 'x', 'y', 'z',
];
#[allow(unused)]
const ALPHA: [char; 26] = [
    'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S',
    'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
];

fn main() {
    input!(N: usize, M: usize);
    let mut g = vec![vec![]; N];
    for _ in 0..M {
        input!(a: Usize1, b: Usize1);
        g[a].push(b);
        g[b].push(a);
    }

    let cell = bfs(&g);
    let mut ans = 0;
    for &e in &cell {
        if ans < e {
            ans = e;
        }
    }

    println!("{}", ans + 1);
}

fn bfs(g: &Vec<Vec<usize>>) -> Vec<usize> {
    let mut ret = vec![];
    let N = g.len();
    let mut visited = vec![false; N];
    for i in 0..N {
        if visited[i] {
            continue;
        }
        let c = bfs_dist(N, &g, i, &mut visited);
        ret.push(c);
    }
    ret
}

fn bfs_dist(n: usize, g: &Vec<Vec<usize>>, start: usize, visit: &mut Vec<bool>) -> usize {
    let mut q = std::collections::VecDeque::new();
    let mut ret = 0;

    //init
    visit[start] = true;
    q.push_back(start);

    while let Some(now) = q.pop_front() {
        for &e in &g[now] {
            if !visit[e] {
                visit[e] = true;
                ret += 1;
                q.push_back(e);
            }
        }
    }
    ret
}


Measured memory_bytes: 18288
#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <bitset>

#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <fstream>
#include <random>
//#include <time.h>
#include <ctime>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
#define ALL(X) X.begin(), X.end()
/////////
#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef std::pair<LL,LL> PLL;//
typedef std::pair<int,int> PII;//
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)1e18+20;
const LD PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

void solve(){
	int N,M,K;
	cin >> N >> M >> K;
	vector<LL> A(N+1);
	A[0] = 0;
	for(int i=0;i<N;++i){
		cin >> A[i+1];
	}
	
	
	//p1:[1,N-K+1]
	vector<LL> now(N+1,0),next(N+1);

	for(LL k=1;k<=K;++k){//300
		//スライド最大値
		vector<int> deq(N+1,-1);
		int s=0;
		int t=0;
		for(int i=1;i<=N;++i){
			//[max(0,i-M),i-1]
			//より小さい値なら削除
			while(s<t && now[ deq[t-1] ] <= now[i-1] )--t;
			deq[t++] = i-1;//nowのindex
			
			if( i < k ) continue;
			next[i] = now[ deq[s] ];//先頭がmax
			next[i] += A[i]*k;//LL*int
			if( deq[s] == i-M){
				//先頭が範囲外になるなら削除
				s++;
			}
		}
		now = next;
	}
	LL ans = 0;
	for(int i=K;i<=N;++i){
		ans = max(ans,now[i]);
	}
	cout << ans << endl;
}

#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}
#pragma endregion //main()

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include <cmath>
#include <limits>
#include<set>
#include <iomanip>
#include <queue>
#include <string>
#pragma GCC optimize("Ofast")
using namespace std;
const long long INF=20000000000;
//setprecision(2) <<

const int MOD = 1000000007;

long long max(long long a,long long b){
	if(a<b)return b;
	else return a;	
}
long long min(long long a,long long b){
	if(a>b)return b;
	else return a;	
}
long long gcd(long long a,long long b){
	if(a<b)swap(a,b);
	if(a%b==0)return b;
	else return gcd(a%b,b);
}

long long lcm(long long a,long long b){
	return a*b/gcd(a,b);
}

long long com(long long n,long long k){
	
}
long long getDigit(long long n){
	if(n==1)return 1;
	else return log10(n)+1;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	vector< pair<long long,long long> >v;
	long long n,k;
	cin>>n>>k;
	for(int i=0;i<n;i++){
		long long a,b;
		cin>>a>>b;
		v.push_back(make_pair(a,b));
	}
	sort(v.begin(),v.end());
	long long num=0;
	int i=0;
	while(num<k){
		num+=v[i].second;
		//cout<<i;
		i++;
	}
	
	cout<<v[i-1].first<<endl;
	
}

	


Measured memory_bytes: 2420
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-15
inline int read() {
	res s=0;
	bool w=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')w=1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
	return w?-s:s;
}
inline void _swap(res &x,res &y) {
	x^=y^=x^=y;
}
inline int _abs(const res &x) {
	return x>0?x:-x;
}
inline int _max(const res &x,const res &y) {
	return x>y?x:y;
}
inline int _min(const res &x,const res &y) {
	return x<y?x:y;
}
const int N=2e3+10;
namespace MAIN {
	int n,m;
	struct E {
		int next,to;
		E() {}
		E(res next,res to):next(next),to(to) {}
	} edge[N<<1];
	int head[N],cnt;
	inline void addedge(res u,res v) {
		edge[++cnt]=E(head[u],v),head[u]=cnt;
		edge[++cnt]=E(head[v],u),head[v]=cnt;
	}
	int tot;
	void dfs(res x,res fax,res depx) {
		if(depx>m/2)tot++;
		for(res i=head[x]; ~i; i=edge[i].next) {
			res tox=edge[i].to;
			if(tox==fax)continue;
			dfs(tox,x,depx+1);
		}
	}
	int ans=inf;
	inline void MAIN() {
		memset(head,-1,sizeof(head));
		n=read(),m=read();
		for(res i=1; i<n; i++) {
			res u=read(),v=read();
			addedge(u,v);
		}
		if(m&1) {
			for(res x=1; x<=n; x++)
				for(res i=head[x]; ~i; i=edge[i].next) {
					res tox=edge[i].to;
					tot=0;
					dfs(tox,x,0);
					dfs(x,tox,0);
					ans=_min(ans,tot);
				}
		} else {
			for(res x=1; x<=n; x++)
				tot=0,dfs(x,0,0),ans=_min(ans,tot);
		}
		printf("%d\n",ans);
	}
}
int main() {
	MAIN::MAIN();
	return 0;
}

Measured memory_bytes: 384
a,b,c,x=[int(input()) for i in range(4)]

"""
aが500円
bが100円
cが50円
"""
flag = 0

for i in range(a + 1):
    for j in range(b + 1):
        for k in range(c + 1):
            if 500*i + 100*j + 50*k == x:
                flag += 1
print(flag)

Measured memory_bytes: 3060
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#define ll long long
using namespace std;
int main()
{
	int n;
	ll lasta = 0, lastb = 0, a, b;
	scanf("%d", &n);
	while(n--)
	{
		scanf("%lld%lld", &a, &b);
		if(!lasta)
			lasta = a, lastb = b;
		else
		{
			if(lasta % a)
				lasta += a - lasta % a;
			if(lastb % b)
				lastb += b - lastb % b;
			ll x = max(lasta / a, lastb / b);
			lasta = a * x, lastb = b * x;
		}
	}
	printf("%lld\n", lasta + lastb);
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
const int MOD = pow(10,9)+7;
int N;
unordered_map<int,int> cnt;
int get(vector<vector<bool>>& match,int ix,int y){
  if(cnt.count(y)) return cnt[y];
  if(ix == N) return 1;
  int tmp = 0;
  for(int i = 0; i < N; ++i){
    if(y&(1<<i)){
      if(match[ix][i]) tmp = (tmp+get(match,ix+1,y-(1<<i)))%MOD;
    }
  }
  cnt[y] = tmp;
  return tmp;
}
int main(){
  int a;
  cin >> N;
  vector<vector<bool>> match(N,vector<bool>(N));
  for(int i = 0; i < N; ++i){
    for(int j = 0; j < N; ++j){
      cin >> a;
      if(a) match[i][j] = true;
    }
  }
  cout << get(match,0,(1<<N)-1);
  return 0;
}

Measured memory_bytes: 82512
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int N;
    cin >> N;
    int F[N][10];
    for(int i = 0; i < N; i++){
        for(int j = 0; j < 10; j++) cin >> F[i][j];
    }
    int P[N][11];
    for(int i = 0; i < N; i++){
        for(int j = 0; j < 11; j++) cin >> P[i][j];
    }
    long long ans = -1e18;
    for(int bit = 1; bit < (1 << 10); bit++){
        long long res = 0;
        vector<int> ope(10, 0);
        for(int i = 0; i < 10; i++){
            if(bit & (1 << i)) ope[i] = 1;
        }
        for(int i = 0;i < N; i++){
            int cnt = 0;
            for(int j = 0; j < 10; j++){
                if(ope[j] == F[i][j] && ope[j] == 1) cnt++;
            }
            res += P[i][cnt];
        }
        ans = max(ans, res);
    }
    cout << ans << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define M 10000
#define  INF 1<<20
int n;
vector<pair<int,int > > a[M];
void dijkstra(){
	priority_queue<pair<int,int> > Q;
	bool col[M];
	int d[M];
	for(int i=0;i<n;i++){
		col[i]=0;
		d[i]=INF;
	}
	d[0]=0;
	Q.push(make_pair(0,0));
	while(!Q.empty()){
		pair<int,int>f=Q.top();Q.pop();
		int u=f.second;col[u]=1;
		if(d[u]<f.first*(-1))continue;
		for(int j=0;j<a[u].size();j++){
			int v=a[u][j].first;
			if(col[v])continue;
			if(d[v]>d[u]+a[u][j].second){
				d[v]=d[u]+a[u][j].second;
				Q.push(make_pair(d[v]*(-1),v));
			}
		}
	}
	for(int i=0;i<n;i++)cout<<i<<' '<<(d[i]==INF?-1:d[i])<<endl;
}
int main() {
	int k,u,v,c;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>u>>k;
		for(int j=0;j<k;j++){
			cin>>v>>c;
			a[u].push_back(make_pair(v,c));
		}
	}
	dijkstra();
}

Measured memory_bytes: 8080
import math

def main():

    n, d = map(int, input().split())
    cnt = 0
    for _ in range(n):
        x, y = map(int, input().split())
        if math.sqrt(x ** 2 + y ** 2) <= d:
            cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

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

m = [0]*n

for i in range(n):
  m[i] = l[i] -(i+1)

m.sort()
if n%2 == 0:
  p = n//2-1
else:
  p = (n-1)//2

ans = 0
for j in range(n):
  ans += abs(m[j] - m[p])

print(ans)

Measured memory_bytes: 88276
using System;
using System.Linq;
using System.Collections.Generic;

namespace abc088b
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split().Select(s => int.Parse(s)).ToArray();
            var ans = input.All(x => x <= 9) ? input[0] * input[1] : -1;
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13396
import scala.io.StdIn

object Main{
  def main(args:Array[String]) {
    val inputs = StdIn.readLine().split(" ")
    val a = inputs(0).toInt
    val b = inputs(1).toInt
    val c = inputs(2).toInt
    
    val numList = (a to b).toList
    
    println(numList.count(c % _ == 0))
  }
}

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

using namespace std;

unordered_map<string, bool> record;

int main(int argc, char const *argv[])
{
    int n;
    string oper, s;
    while (~scanf("%d", &n))
    {
        record.clear();
        for (int i = 0; i < n; ++i)
        {
            cin >> oper >> s;
            if("insert" == oper) record[s] = true;
            else
            {
                if(record[s]) printf("yes\n");
                else printf("no\n");
            }
        }
    }
    return 0;
}

Measured memory_bytes: 50204