akhauriyash/Code-Regression huggingface dataset:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]

def main():
    t1,t2=inpm()
    a1,a2=inpm()
    b1,b2=inpm()
    if t1*a1+t2*a2 == t1*b1+t2*b2:
        print('infinity')
        return
    if t1*a1+t2*a2 < t1*b1+t2*b2:
        a1,b1 = b1,a1
        a2,b2 = b2,a2
    x = t1*a1+t2*a2 - (t1*b1+t2*b2)
    y = t1*a1-b1*t1
    if y>=0:
        print(0)
        return
    y*=-1
    ans=2*((y//x)+1)-1
    if y%x==0:
        ans-=1
    print(ans)
    

if __name__ == "__main__":
    main()

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

int main() {
  string s;
  cin>>s;
  string a="abcdefghijklmnopqrstuvwxyz";
  int vec[26]={0};
  for(int i=0;i<s.size();i++){
    for(int j=0;j<26;j++){
      if(s[i]==a[j]){
        vec[j]++;
        if(vec[j]==2){
          cout<<"no"<<endl;
          return 0;
        }
      }
    }
  }
  cout<<"yes"<<endl;
}

Measured memory_bytes: 256
w, h, n = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
x = [x_i for x_i in range(w + 1)]
y = [y_i for y_i in range(h + 1)]
for l_e in l:
    if l_e[2] == 1:
        x = [i for i in x if i > l_e[0] - 1]
    elif l_e[2] == 2:
        x = [i for i in x if i < l_e[0] + 1]
    elif l_e[2] == 3:
        y = [i for i in y if i > l_e[1] - 1]
    else:
        y = [i for i in y if i < l_e[1] + 1]
print(0 if len(x) == 0 or len(y) == 0 else (x[-1] - x[0]) * (y[-1] - y[0]))

Measured memory_bytes: 3064
package main

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

func main() {
	N := int(readInt()) - 2
	B := readInts()
	max := B[0]
	for i, b := range B {
		if i < N {
			if b > B[i+1] {
				max += B[i+1]
			} else {
				max += b
			}
		} else {
			max += b
		}
	}
	fmt.Println(max)
}

var reader = bufio.NewReaderSize(os.Stdin, 1024*1024)

func Min(a, b int64) int64 {
	if a > b {
		return b
	}
	return a
}

func Max(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

func readInt() int64 {
	temp := readLine()
	res, _ := strconv.ParseInt(temp, 10, 64)
	return res
}

func readInts() []int64 {
	nums := strings.Split(readLine(), " ")
	res := make([]int64, len(nums))
	for i, str := range nums {
		res[i], _ = strconv.ParseInt(str, 10, 64)
	}
	return res
}

func readLine() string {
	str, _, err := reader.ReadLine()
	if err == io.EOF {
		return ""
	}
	return strings.TrimRight(string(str), "\r\n")
}


Measured memory_bytes: 640
//By SiriusRen
#include <bits/stdc++.h>
using namespace std;
int n,ans;
bool solve(int x){
	int temp=0;
	for(int i=1;i<=x;i++){
		if(x%i==0)temp++;
	}return temp==8;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		if(i&1)ans+=solve(i);
	}printf("%d\n",ans);
}

Measured memory_bytes: 256
$<.each{|line|
  n = line.to_i
  ret = 0
  10.times{|a|
    10.times{|b|
      10.times{|c|
        10.times{|d|
          next if n != a + b + c + d
          ret+=1
          break
        }
      }
    }
  }
  puts ret  
}

Measured memory_bytes: 6092
program main
  
  implicit none
  integer(8) :: n, k
  
  read(*,*) n, k
  
  if( mod(n,k) < abs( mod(n,k) - k ) ) then
    print*, mod(n,k) 
  else
    print*, abs( mod(n,k) - k )
  end if
  
end program main


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

int main(){
    vector<int> primes;
    primes.push_back(2);
    for(int i=3;i<=500000;i=i+2){
        int flag=1;
        for(int j=3;j<=sqrt(i);j=j+2){
            if(i%j==0){flag=0;break;}
        }
        if(flag==1)primes.push_back(i);
    }
    int n;
    cin>>n;
    map<int,int> m; int maxx = INT_MIN; int soul=0;int amma=0;
    for(int i=0;i<n;++i){
        int temp;cin>>temp;maxx= max(maxx,temp);
        if(temp%2==0)amma++;
        if(i==0){
            soul = temp;
        }
        else {
            soul = __gcd(soul,temp);
        }
        m[temp]++;
    }
    if(amma>=2){
        if(soul==1)cout<<"setwise coprime"<<endl;
        else cout<<"not coprime"<<endl;
        return 0;
    }
    int flag=0; 
    for(int k=0;k<primes.size();++k){
        int i = primes[k];
        int j = 1;int bokka = 0;
        while(i*j<=maxx){
            if(m[i*j]>=2){
                flag = 1;break;
            }
            if(m[i*j]==1)bokka++;
            if(bokka==2){flag=1;break;}
            j++;
        }
        if(flag==1)break;
    }
    if(flag==0){
        cout<<"pairwise coprime"<<endl;
    }
    else if(soul==1){
        cout<<"setwise coprime"<<endl;
    }
    else cout<<"not coprime"<<endl;








    return 0;
}

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

#define ll long long

ll a, b, c, cnt, x, y, z;
int main()
{
	cin>>a>>b>>c;
	while(a%2==0 && b%2==0 && c%2==0)
	{
		cnt++;
		x=a,y=b,z=c;
		a=(y+z)/2;
		b=(x+z)/2;
		c=(x+y)/2;
		if(cnt==100000) break;
	}
	if(cnt==100000) cout<<-1<<endl;
	else cout<<cnt<<endl;
	return 0;	
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>
#include <random>
#include <complex>
#include <functional>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

const ll inf = 1LL << 60;

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

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

    ll N;
    cin >> N;
    vec A(N);
    Rep (i, N) {
        cin >> A[i];
    }

    ll dp[N+2][3];
    Rep (i, N+2) {
        Rep (j, 3) {
            dp[i][j] = -inf;
        }
    }
    dp[0][0] = 0;

    Rep (i, N+1) {
        Rep (j, 3) {
            if (i+2 < N+2) chmax(dp[i+2][j], dp[i][j] + A[i]);
            if (j+1 < 3) chmax(dp[i+1][j+1], dp[i][j]);
        }
    }

    // Rep (i, N+2) {
    //     Rep (j, 3) {
    //         cout << dp[i][j] << " \n"[j==2];
    //     }
    // }

    if (N%2 == 0) {
        cout << dp[N+1][1] << endl;
    } else {
        cout << dp[N+1][2] << endl;
    }

}

Measured memory_bytes: 9536
#include <cstdio>
#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

string s[200]; 

int main() {
  int n,L;
  scanf("%d%d",&n,&L);
  for(int i=0;i<n;i++){
    cin >> s[i];
  }
  sort(s,s+n);
  for(int i=0;i<n;i++){
    cout << s[i];

  }
  cout << endl;
}

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

using namespace std;
void Swap(char *a,char *b)
{
	char s[150];
	strcpy(s,a);
	strcpy(a,b);
	strcpy(b,s);
 } 

int main()
{
	int n;
	scanf("%d%*c",&n);
	char a[n+1][150];
	int b[n+1];
	int c[n+1];
	for(int i=1;i<=n;i++)
	{
        scanf("%s",a[i]);
        scanf("%d",&b[i]);
		c[i]=i;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<n;j++)
		{
			if(strcmp(a[j],a[j+1])>0)
			{
				Swap(a[j],a[j+1]);
				swap(b[j],b[j+1]);
				swap(c[j],c[j+1]);
			}
			else if(strcmp(a[j],a[j+1])==0)
			{
				if(b[j]<b[j+1])
				{
					Swap(a[j],a[j+1]);
					swap(b[j],b[j+1]);
					swap(c[j],c[j+1]);
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		cout << c[i] << endl;
	}
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys

#数直線上をN+1回跳ねるボールがあり、1回目は座標D1=0, i回目は座標Di=D(i-1)+L(i-1) (1<=i<=N+1)で跳ねます
#数直線がX以下の領域でボールが跳ねる回数は何回でしょうか

#Given:
    #N X
    #L1, L2, L3, ... LN-1, LN


#N, Xを格納
#inputをsplit関数でlistに変換
i = input()
lis = i.split()
#listの要素をN, Xに格納
N = int(lis[0])
#print("Nは"+str(N))
X = int(lis[1])
#print("Xは"+str(X))

#L1, L2, L3, ... LN-1, LNを格納
#inputをsplit関数でlistに変換
i = input()
lis = i.split()
#lisをLに順に格納
L = list()
for k in lis:
    #print(k)
    L.append(int(k)) #数値に変換
#print(L)

#NとLの数を確認
if N != len(L):
    print("跳ねる回数と跳ねる位置のリスト数が一致していません。")
    sys.exit()

#D1, D2, D3 ... DN-1, DNを生成
D = list()

#D0 = 0
D.append(0)
for k in range(0,len(L)):
    D.append(D[k]+L[k]) #D0～DN
#print(D)

#Dのうち、X以下の要素をcount
n = sum(test <= X for test in D)  # 真偽値リストを作って True の数を合計する方法

#戻り値n
print(n)


Measured memory_bytes: 3064
#include <iostream>

using namespace std;

int main(void) {
    int A, B, C, X;
    cin >> A >> B >> C >> X;
    int ans = 0;
    for(int i=0; i<=A; i++) {
        for(int j=0; j<=B; j++) {
            for(int k=0; k<=C; k++) {
                if(500*i+100*j+50*k == X) {
                    ++ans;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
while 1:
  c=[0,1,1]+[0]*98
  while 1:
    try: a, b = map(int, raw_input().split())
    except: exit()
    if a==0==b:break
    c[a] = 1-c[a]
    c[b] = 1-c[b]
  print ["NG","OK"][sum(c)==0]

Measured memory_bytes: 4212
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    l=[]
    for i in range(N):
        l.append(tuple(map(int,input().split())))
    l.sort(key=lambda t:t[0])
    for a,b in l:
        K-=b
        if K<=0:
            print(a)
            exit()

if __name__ == '__main__':
    main()


Measured memory_bytes: 57308
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define MOD 1000000007
ll fact[200005];
#define eps 1e-9
#define INF 1e18
#define N 200005
inline ll mul(ll a,ll b){
  a=(a+MOD)%MOD;
  b=(b+MOD)%MOD;
  ll c=a*b;
  c=(c+MOD)%MOD;
  return c;
}
ll power(ll a,ll b,ll c){
  ll ans=1;
  while(b){
    if(b&1){
      ans=mul(ans,a);
    }
    a=mul(a,a);
    b=b/2;
  }
  return ans;
}
int n,m,q; 
int qq[51][4];
ll res=0;
void update(vector<ll>&v){
	ll ans=0;
	for(int i=0;i<q;++i){
		int aa=qq[i][0];
		int bb=qq[i][1];
		int cc=qq[i][2];
		int dd=qq[i][3];
		aa--,bb--;
		if(v[bb]-v[aa]==cc)ans+=(ll)dd;
	}
	if(res<ans)res=ans;
}
void f(int p,int ind,vector<ll>&v){
	if(ind==n){
		//cout<<"hello";
		update(v);
		return;
	}
	for(int i=p;i<=m;++i){
		v.push_back(i);
		f(i,ind+1,v);
		v.pop_back();
	}
}
int main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        cin>>n>>m>>q;
        for(int i=0;i<q;++i)cin>>qq[i][0]>>qq[i][1]>>qq[i][2]>>qq[i][3];
        vector<ll> v;
        f(1,0,v);
        cout<<res;
        return 0;
}


Measured memory_bytes: 3624
import java.util.Scanner;


public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true){
			final int n = sc.nextInt();
			
			if(n == 0){
				break;
			}
			
			int sum = 0;
			int max = Integer.MIN_VALUE;
			int min = Integer.MAX_VALUE;
			for(int i = 0; i < n; i++){
				final int t = sc.nextInt();
				sum += t;
				max = Math.max(max, t);
				min = Math.min(min, t);
			}
			
			sum -= max;
			sum -= min;
			sum /= n - 2;
			
			System.out.println(sum);
		}
		
	}

}

Measured memory_bytes: 12000
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b;
  cin>>a>>b;
  int c[a][2],sum=0;
  for(int i=0;i<a;i++){cin>>c[i][0]>>c[i][1];
  long double d=sqrt(pow(c[i][0],2)+pow(c[i][1],2));
                       if(d<=b)sum++;}
  cout<<sum;
  return 0;}


Measured memory_bytes: 5132
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define MOD (ll) (1e9+7)
int main()
{
     string s,t;
     cin>>s>>t;
     ll no_change = 0;
     for(int i=0;i<s.size();i++)
     {
     	if(s[i]!=t[i])
     	{
     		no_change++;
     	}
     }
     cout<<no_change<<"\n";
}


Measured memory_bytes: 3924
input = gets.chomp
n,x = input.split.collect{ |item| item.to_i}
input = gets.chomp
llist = input.split.collect{ |item| item.to_i}

point = 0
count = 1
llist.each do |i|
  point += i
  if point <= x
    count += 1
  else
    break
  end
end

puts count

Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
int f(string c,string c1)
{
   int s=c1.length(),m=0;
   for(int i=0;i<s;i++)
   {
      m=m*10+(c1[i]-48);
      //cout<<m<<endl;
   }
   for(int i=0;i<m;i++)
   {
      cout<<c;
   }
   cout<<endl;
}
int main()
{
   string s1,s2,c,c1;
   //int c;
   while(cin>>s1>>s2)
   {
     c=min(s1,s2);
     c1=max(s1,s2);
     f(c,c1);
   }
  return 0;
}


Measured memory_bytes: 256
import heapq

n = int(input())
v = [int(_) for _ in input().split()]

heapq.heapify(v)
while len(v) > 1:
    h = (heapq.heappop(v) + heapq.heappop(v)) / 2
    heapq.heappush(v, h)

print(v[0])


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

using namespace std;

int main()
{
	string a;
	int n,i,j,k,p,q;
	cin >> a;
	n=a.size();
	if(n%2==0)
		j=n/2-1;
	else
		j=n/2;
	p=0;
	while(p==0)
	{
		k=j;
		q=0;
		for(i=0; i<k; i++)
		{
			if(a[i]!=a[i+k]) q=1;
		}
		if(q==0) break;
		j--;
	}
	cout << j*2;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
using namespace std;
int main(void){
    char s[30];
    cin>>s;
    int N;
    N=strlen(s);
    int check[26];
    for(int i=0;i<26;i++){
        check[i]=0;
    }
    int c;
    for(int i=0;i<N;i++){
       c=s[i]-'a' ;
       check[c]++;
    }
    int count=0;
    for(int i=0;i<26;i++){
        if(check[i]==1) count++;
    }
    if(count==N) cout<<"yes";
    else cout<<"no";
    return 0;
}


Measured memory_bytes: 256
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

ll n;
vector<ll> a;
vector<vector<ll>> edge;
vector<vector<pair<ll,bool>>> dp;

void merge(vector<pair<ll,bool>> &ret,vector<pair<ll,bool>> P,vector<pair<ll,bool>> &C){
    ret.resize(P.size()+C.size());
    for(auto &i:ret){i.F=E; i.S=false;}
    for(int i=0;i<P.size();i++){
        for(int t=0;t<C.size();t++){
            ret[i+t].F=min(ret[i+t].F,P[i].F+C[t].F);
            if(C[t].F<0 || C[t].S){
                ret[i+t+1].F=min(ret[i+t+1].F,P[i].F);
            }
            if(P[i].S && C[t].S){
                ret[i+t].S=true;
            }
            if(P[i].S && (C[t].S || C[t].F<0)){
                ret[i+t+1].S=true;
            }
        }
    }
}

void dfs(ll w,ll p){
    //cout<<w<<" "<<p<<endl;
    for(auto &i:edge[w]){
        if(i==p){continue;}
        dfs(i,w);
        merge(dp[w],dp[w],dp[i]);
    }
}



int main(){
    cin>>n;
    a.resize(n);
    edge.resize(n);
    dp.resize(n,vector<pair<ll,bool>>(1,{0,false}));
    for(int i=0;i<n;i++){
        cin>>a[i];
        dp[i][0].F=a[i];
        if(a[i]>0){dp[i][0].S=true;}
    }
    for(int i=1;i<n;i++){
        ll u,v;
        cin>>u>>v;
        u--; v--;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dfs(0,-1);
    for(int i=0;i<dp[0].size();i++){
        if(dp[0][i].F<0 || dp[0][i].S==true){
            cout<<i<<endl;
            return 0;
        }
    }
    
    
    
    return 0;
}


Measured memory_bytes: 163840
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)
#define ENDL '\n'
typedef pair<int,int> Pi;
typedef pair<ll,ll> PL;
constexpr ll mod = 1000000007;
constexpr ll INF = 1000000099;
constexpr ll LINF = (ll)(1e18 +99);
const vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}
template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T,typename Y> inline T mpow(T a, Y n) {
  T res = 1;
  for(;n;n>>=1) {
    if (n & 1) res = res * a;
    a = a * a;
  }
  return res;
}



signed main(){
  cin.tie(0);ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);
  int n;cin>>n;
  V<int> v(n,0);
  rep(i,0,n-1){
    int x;cin>>x;
    x--;
    v[x]++;
  }

  rep(i,0,n)cout<<v[i]<<ENDL;
}
//! ( . _ . ) ! 
//CHECK overflow,vector_size,what to output?

Measured memory_bytes: 3992
#include <bits/stdc++.h>
using namespace std;
const int PINF = 2000000000;
const int NINF = -2000000000;
int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++){
    cin >> a[i];
  }
  int q;
  cin >> q;
  for (int i = 0; i < q; i++){
    int t, b, e;
    cin >> t >> b >> e;
    if (t == 0){
      int m = PINF;
      for (int j = b; j < e; j++){
        m = min(m, a[j]);
      }
      cout << m << endl;
    }
    if (t == 1){
      int M = NINF;
      for (int j = b; j < e; j++){
        M = max(M, a[j]);
      }
      cout << M << endl;
    }
  }
}


Measured memory_bytes: 3116
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <math.h>
#include <algorithm>
#include <queue>
using namespace std;

typedef long long ll;
const int maxn = 200200;
int a[maxn];
void solve()
{
    int n,k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 2; i <= n; i++)
        a[i] += a[i - 1];
    int mx = 0;
    for (int i = k; i <= n; i++){
        mx = max(mx,a[i]-a[i - k]);
    }
    double ans = (mx + k) * 0.5;
    printf("%.9f\n",  ans);

    // atcoder expected value task
}


int main()
{
    int t;
    solve();
    return (0);
}





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

vector<int> enum_divisors(int N) {
    vector<int> res;
    for (int i = 1; i * i <= N; ++i) {
        if (N % i == 0) {
            res.push_back(i);
            // 重複しないならば i の相方である N/i も push
            if (N/i != i) res.push_back(N/i);
        }
    }
    // 小さい順に並び替える
    sort(res.begin(), res.end());
    return res;
}

signed main(){
    int N, M; cin >> N >> M;
    vector<int> vec = enum_divisors(M);
    int x = M / N;
    int ans;
    for(int i = vec.size() - 1; i >= 0; i--){
        if(vec[i] <= x){
            ans = vec[i];
            break;
        } 
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main (String[] args) {
        Scanner scan = new Scanner(System.in);
        String result_a = null;
        String result_b = null;

        while (true) {
            String s = scan.next();

            if (s.equals("-")) {
                break;
            }

            int m = scan.nextInt();

            for (int i = 0; i < m; i++) {
                int h = scan.nextInt();
                result_a = s.substring(0,h);
                result_b = s.substring(h);
                
                s = result_b + result_a;


            }

            System.out.println(s);
        }

    }
}


Measured memory_bytes: 26492
#include <bits/stdc++.h>
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n==0) return 1;
    ll res=modpow(x, n/2);
    if(n%2==0) return res*res%mod;
    else return res*res%mod*x%mod;
}

ll power(ll x, ll n){
    if(n == 0) return 1;

    ll res = power(x, n/2);
    if(n%2 == 0) return res*res;
    else return res*res*x;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };

// 線分 ab の偏角 返り値は[-π, π]
double argument(const pair<double, double> &a, const pair<double, double> &b){
    double ax=a.first, ay=a.second, bx=b.first, by=b.second;
    return atan2(by-ay, bx-ax);
}

/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */


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

    int n; cin >> n;
    vector<int> a(n+1, 0);
    rep(i, n) cin >> a[i+1];

    int ans = 0;
    int id = 1;
    for(int i=1; i<=n; ++i) {
        if (a[i]!=id) {
            ++ans;
        } else {
            ++id;
        }
    }

    if (ans == n) cout << -1 << endl;
    else cout << ans << endl;


    
    return 0;
}



Measured memory_bytes: 1152
// Problem : B - Crane and Turtle
// Contest : AtCoder - AtCoder Beginner Contest 170
// URL : https://atcoder.jp/contests/abc170/tasks/abc170_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int x,y;
	cin>>x>>y;
	int a = 2*x - (y/2);
	int b = (y/2) - x;
	
	if((a + b == x) && (2*a + 4*b == y) && a >= 0 && b >= 0)
	{
		cout<<"Yes";
	}
	else
	{
		cout<<"No";
	}
	return 0;
}

Measured memory_bytes: 3580
#include <stdio.h>
int main(void)
{
	long long int a,b,c,tmp,ans;
	scanf("%lld%lld%lld",&a,&b,&c);
	if(a%2==0 || b%2==0 || c%2==0){
		ans=0;
	}else{
		if(a*b<=b*c && a*b<=a*c)ans=a*b;
		else if(a*c<=a*b && a*c<=b*c)ans=a*c;
		else if(b*c<=a*b && b*c<=a*c)ans=b*c;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 128
//#include <bits/stdc++.h>
#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;
typedef pair<dd,dd> d_d;
ll inf=(ll)1E16;
#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);
#define fi first
#define se second
///////////////////////////

int main(){fastio
    ll a,b;cin>>a>>b;
    rep(i,1,10000){
        ll xa=i*8/100;
        ll xb=i*10/100;
        if(a==xa&&b==xb){
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<-1<<endl;
    
    return 0;
}


Measured memory_bytes: 256
import numpy as np
import functools
import sys
sys.setrecursionlimit(10**9)

# 最大公約数
def gcd_impl(n,m):
    for _ in range(10):
        t = n - m
        q = m > t
        if q:
            n = m
        else:
            n = t
        if q:
            m = t
        else:
            m = m
        if m == 0:
            return n
    return gcd_impl(m, n%m)

def gcd(n,m):
    if n > m:
        return gcd_impl(n,m)
    else:
        return gcd_impl(m,n)


def gcd_list(nums):
    return functools.reduce(gcd, nums)

N, X = map(int, input().split())
x = np.array(list(map(int, input().split())))
x = abs(X - x)
print(gcd_list(x))

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

#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define MOD 1000000007

const int MAX_M = 100000;


int main(){
  ll a, b, c, d;
  //string s;
  cin >> a >> b >> c >> d;
  
  while(1){
    c -= b;
    if(c<=0)
      break;
    a -= d;
    if(a<=0)
      break;
  }
    
  cout << ((c<=0)? "Yes" : "No") << endl;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f
#define MAXN int(1e6+3)
using namespace std;

ll n, dp[MAXN][9], vet[MAXN][9];

ll solve(int i, int k) {
    if(i > n+1)
        return -INF;
    if(dp[i][k] != -INF)
        return dp[i][k];
    if(i == n+1)
        return 0;

    for(int z = 1; z <= 3; z++) {
        if(z != k) dp[i][k] = max(dp[i][k], solve(i+1, z)+vet[i][z]);
    }
    return dp[i][k];
}
int main() {

    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= 3; j++)
            cin >> vet[i][j];

    for(int i = 0; i <= MAXN-1; i++)
        for(int j = 0; j <= 8; j++)
            dp[i][j] = -INF;

    solve(1, 0);
    cout << dp[1][0] << endl;
}

/*
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f
#define MAXN int(1e6+3)
using namespace std;
typedef pair<pair<int, int>, int> piii;

piii day[MAXN];
ll dp[MAXN][3], n;

int solve(int i, int k) {
    if(dp[i][k] != -INF)
        return dp[i][k];
    if(i == n)
        return 0;
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        day[i] = piii(make_pair(a, b) c);
    }
    for(int i = 0; i < n; i++)
        for(int i = 0; i < 3; i++)
}
*/



Measured memory_bytes: 87296
#include <bits/stdc++.h>
using namespace std;
using Graph=vector<vector<int>>;

bool dfs(Graph &G,int v,vector<int> &visit){
  for(auto nv:G.at(v)){
    if(visit.at(nv)!=-1){
      if((visit.at(v)+1-visit.at(nv))%2==1){
        return false;
      }else{
        continue;
      }
    }
    visit.at(nv)=visit.at(v)+1;
    if(!dfs(G,nv,visit)){
      return false;
    }
  }
  return true;
}

int main(){
  int N;
  cin>>N;
  vector<string> S(N);
  for(int i=0;i<N;i++){
    cin>>S.at(i);
  }

  Graph G(N);
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){
      if(S.at(i).at(j)=='1'){
        G.at(i).push_back(j);
        G.at(j).push_back(i);
      }
    }
  }

  vector<int> visit(N,-1);
  visit.at(0)=0;
  bool flag=dfs(G,0,visit);
  if(flag){
    int ans=0;
    for(int i=0;i<N;i++){
      vector<int> dist(N,-1);
      dist.at(i)=0;
      queue<int> q;
      q.push(i);
      int distance=0;
      while(!q.empty()){
        int v=q.front();
        q.pop();
        for(auto nv:G.at(v)){
          if(dist.at(nv)==-1){
            dist.at(nv)=dist.at(v)+1;
            distance=max(distance,dist.at(nv));
            q.push(nv);
          }
        }
      }
      ans=max(ans,distance+1);
    }
    cout<<ans<<endl;
  }else{
    cout<<-1<<endl;
  }
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <algorithm>
#include <ctime>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cassert>
#include <bitset>
#include <list>
#include <cstdio>
#include <stdio.h>
#include <string.h>
#include <cmath>

typedef long long ll;

using namespace std;

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

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long h, n;
    cin >> h >> n;
    long long sum=0;
    for(int i=0; i<n; i++)
    {
        long long a;
        cin >> a;
        sum += a;
    }
    if(sum>=h) cout << "Yes";
    else cout << "No";
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define POW(n) ((n)*(n))
#define ALL(a) (a).begin(),(a).end()
#define cerr if(false) cerr
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<unsigned long long> vull;

void solve(long long N, vector<long long> A){
	map<ll,bool> m;
	ll ans = 0;

	REP(i,A.size()){
		m[A[i]] = (i%2 == 0);
	}

	sort(ALL(A));

	REP(i,A.size()){
		bool f = (i%2 == 0);
		if(m[A[i]] != f)ans++;
	}

	cout << (ans/2) << endl;
}



int main(){	
	ios::sync_with_stdio(false);
	long long N;
	cin >> N;
	vector<long long> A(N-1+1);
	for(int i = 0 ; i <= N-1 ; i++){
		cin >> A[i];
	}
	solve(N, A);
	return 0;
}


Measured memory_bytes: 8064
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef vector<int>Vl;
typedef pair<int,int>pii;
typedef vector<pii>Vll;
typedef vector<pair<int,pair<int,int> > >Vlll;
#define S second
#define F first
#define mp make_pair
#define ms(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define sl(n) cin>>n 
#define pl(n) cout<<n<<" "
const int Nx=2e5+2;
const int mod=1e9+7;
const int inf=(int)(1e9+10LL);
const double pI=6.28318530717958623200;
int S(int l,int r){
	return ((l+r)*(r-l+1))/2;
	
}
void solve()
{
	int n,k;
	sl(n);sl(k);
	n++;
	int ans=0;
	for(int r=k;r<=n;r++){
	  int mn=S(0,r-1);
	  int mx=S(n-r,n-1);
	  ans+=(mx-mn+1)%mod;
	}
	cout<<ans%mod<<endl;
}


signed main(){
  int test=1;
 // sl(test);
 while(test--){
 	solve();
 }
 
}

Measured memory_bytes: 3636
#include <stdio.h>
#include <string.h>

int check(char p[], int s, int e)
{
	int i;
	for (i = s - 1; i < e; i++){
		if (p[i]<'0' || p[i]>'9') {
			 return 0;
		}
	}
	return 1;
}

int main(void)
{
	int a, b;
	char p[20];
	scanf("%d%d", &a, &b);
	scanf("%s", p);
	if (p[a] != '-') printf("No\n");
	else{
		int A = check(p, 1, a);
		int B = check(p, a + 2, a + b + 1);
		if (A&&B) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 128
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 10 **18
N,*A = map(int, read().split())
if 0 in A:
  print(0)
  sys.exit()
ans = 1
for i in A:
  ans *= i
  if ans > INF:
    print(-1)
    sys.exit()
print(ans)


Measured memory_bytes: 95212
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

int main() {
  ll N, M;
  cin >> N >> M;
  vector<pair<ll, ll>> ab(N), cd(M);
  ll x, y;
  for (int i = 0; i < N; i++) {
    cin >> x >> y;
    ab[i] = {x, y};
  }
  for (int i = 0; i < M; i++) {
    cin >> x >> y;
    cd[i] = {x, y};
  }
  for (int i = 0; i < N; i++) {
    ll min_l = INF;
    int index;
    for (int j = 0; j < M; j++) {
      ll l = abs(ab[i].first - cd[j].first) + abs(ab[i].second - cd[j].second);
      if (l < min_l) {
        index = j + 1;
        min_l = l;
      }
    }
    cout << index << endl;
  }
  return 0;
}

Measured memory_bytes: 3608
import bisect
n = int(input())
l = sorted(([int(x) for x in input().split()]))
count = 0
for i in range(n-1,-1,-1):
    for j in range(i-1,-1,-1):
        k = bisect.bisect_left(l,l[i]+l[j])
        count += k-(i+1)
print(count)

Measured memory_bytes: 3316
using System;

namespace A.Rated_for_Me
{
    class Program
    {
        static void Main(string[] args)
        {
            var R = int.Parse(Console.ReadLine());

            if (R >= 2800)
            {
                Console.WriteLine("AGC");
            }
            else if (R>= 1200)
            {
                Console.WriteLine("ARC");
            }else
            {
                Console.WriteLine("ABC");
            }
        }
    }
}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<int ,P> P3;
typedef pair<P ,P> PP;
const ll MOD = ll(1e9+7);
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX_N = int(1e5 + 5);
const double EPS = 1e-6;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define ALL(v) (v).begin(), (v).end()

int main() {
    ll n, q, t;
    vector<P> pos;
    vector<ll> ans, ls;
    bool used[MAX_N]{};
    cin >> n >> t >> q;
    REP(i,n){
        ll a, d;
        cin >> a >> d;
        pos.push_back({a,d});
    }
    ans.resize(n);
    ls.push_back(-LLINF);
    REP(i,n-1){
        ll l=pos[i].first, r=pos[i+1].first;
        if(pos[i].second==1 && pos[i+1].second==2 && r-l<=t*2){
            ans[i] = ans[i+1] = (l+r)/2;
            ls.push_back(ans[i]);
            used[i] = used[i+1] = true;
        }
    }
    ls.push_back(LLINF);
    REP(i,n){
        if(!used[i]){
            if(pos[i].second==1){
                ans[i] = min(pos[i].first+t, *lower_bound(ALL(ls),pos[i].first));
            }
            else{
                ans[i] = max(pos[i].first-t, *--lower_bound(ALL(ls),pos[i].first));
            }
        }
    }
    REP(i,q){
        int m;
        cin >> m;
        cout << ans[m-1] << endl;
    }
    return 0;
}



Measured memory_bytes: 5760
import sys
from bisect import bisect_left as bi_l

n, m, x, *a = map(int, sys.stdin.read().split())

def main():
    left = bi_l(a, x)
    right = m - left
    return min(left, right)

if __name__ == '__main__':
    ans = main()
    print(ans)

Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
#ifdef _DEBUG_
#define dump(val) cerr << __LINE__ << ":\t" << #val << " = " << (val) << endl
#else
#define dump(val)
#endif

using namespace std;

typedef long long int ll;

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

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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int A, B;
    cin >> A >> B;
    cout << ((B % A) == 0 ? A + B : B - A) << endl;
    return 0;
}


Measured memory_bytes: 256
N = int(input())

def sum_up(num):
    cnt_n = 0
    for i in range(105, num+1, 2):
        tmp = 0
        for j in range(1, i+1):
            if(i%j == 0):
                tmp += 1
                if(tmp > 8):
                    break
        if(tmp == 8):
            cnt_n += 1
    return cnt_n
    
if(N < 105):
    print(0)
else:
    ans = sum_up(N)
    print(ans)

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

using namespace std;

#define forn(i,n) for ( int i=0 ; i < n ; i++ )
#define all(a) (a).begin(), (a).end()
#define lb lower_bound
#define ub upper_bound
#define vi vector<int >
#define pii pair<int, int>
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define SQ(a) (a)*(a)
#define ll long long
#define lli long long int
#define ull unsigned long long
#define endl '\n'
#define Pi(a) printf("%d\n",a);
#define debug2(a,b) printf("%d\t%d\n",a,b);
#define debug1(a) printf("%d\n",a);
#define Si(a) scanf("%d",&a);
#define mod 1000000007
#define w(n) while(n--)



int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	double n,m,d,ans;
	cin >> n >> m >> d;
	ans=(2*(n-d)*(m-1))/(n*n);
	if(d==0) ans/=2;
	printf("%.10lf\n",ans);

	return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,start,end) for(int i=start;i<=end;i++)
const int INF = 1001001001;
using namespace std;
typedef long long ll;

int main()
{
  int N, K;
  int a[110000];
  int res=0;
  cin >> N >> K;

  int idx=0;
  rep(i,N) {
    cin >> a[i];
    if(a[i]==1) idx=i;
  }

  int L = idx;
  int R = N-idx-1;

  res += L/(K-1);
  res += R/(K-1);
  int lmod = L%(K-1);
  int rmod = R%(K-1);

  res += (lmod + rmod)/(K-1);
  if((lmod+rmod)%(K-1)) res++;

  cout << res << endl;
}


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

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

typedef long long ll;

const int INF = 1e8;

int yakusu(int n){
    int num = 0;
    for(int i=1; i<=n; i++){
        if(n%i == 0) num++;
    }
    return num;
}

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

    int res = 0;
    for(int i=1; i<=N; i++){
        if(yakusu(i) == 8 && i%2 == 1) res++;
    }

    cout << res << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
#include <fstream>
#define debug(x) cout << #x << " = " << x << endl
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define repr(i,n) for(int i = (n); i > -1; i--)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const double EPS = 1e-9;


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

  int n;
  cin>>n;
  int f[n][10];
  int p[n][11];
  rep(i,n) {
    rep(j, 10) cin>>f[i][j];
  }
  rep(i,n) {
    rep(j, 11) cin>>p[i][j];
  }
  
  int mx = -MOD;
  for(int i = 1; i < (1<<10); i++) {
    int tmp = 0;
    rep(j,n) {
      int cnt = 0;
      rep(k, 10) {
        if((i>>k) % 2 == 1 && f[j][k] == 1) cnt++; 
      }
      tmp += p[j][cnt];
    }
    mx = max(mx, tmp);
  }
  cout << mx << endl;

  return 0;

}


Measured memory_bytes: 256
use text_io::*;
use std::collections::*;
use std::process::exit;
use std::cmp::*;

fn main() {
    let mut n:String = read!();
    let mut v:Vec<char> = n.chars().collect();
    if (v[0]==v[1]&&v[1]!=v[2]&&v[2]==v[3]) || (v[0]==v[2]&&v[1]!=v[2]&&v[1]==v[3]) || (v[0]==v[3]&&v[0]!=v[2]&&v[2]==v[1]) {
        println!("Yes");
    }
    else {
        println!("No");
    }
}

Measured memory_bytes: 2152
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
using namespace std;
int val[15][15];
int use[15];
int len[15];
string dp[1<<14][15];
string str[15];
char in[20];
int main(){
	int a;
	while(scanf("%d",&a),a){
		for(int i=0;i<a;i++){
			scanf("%s",in);
			str[i]=in;
		}
		for(int i=0;i<a;i++)use[i]=1;
		for(int i=0;i<a;i++)len[i]=str[i].size();
		for(int i=0;i<a;i++)for(int j=0;j<a;j++)val[i][j]=0;
		for(int i=0;i<a;i++){
			for(int j=0;j<a;j++){
				if(i==j)continue;
				if(len[i]<len[j]||(len[i]==len[j]&&i<j)){
					for(int k=0;k<=len[j]-len[i];k++){
						bool ok=true;
						for(int l=0;l<len[i];l++)if(str[i][l]!=str[j][k+l])ok=false;
						if(ok)use[i]=0;
					}
				}
				for(int k=1;k<min(len[i],len[j]);k++){
					bool ok=true;
					for(int l=0;l<k;l++){
						if(str[i][len[i]-k+l]!=str[j][l])ok=false;
					}
					if(ok)val[i][j]=k;
				}
			}
		}
		for(int i=0;i<(1<<a);i++)for(int j=0;j<a;j++)dp[i][j]="~";
		for(int i=0;i<a;i++)if(use[i])dp[1<<i][i]=str[i];
		for(int i=0;i<(1<<a);i++){
			for(int j=0;j<a;j++){
				if(dp[i][j][0]=='~')continue;
			//	printf("%d %d: %s\n",i,j,dp[i][j].c_str());
				for(int k=0;k<a;k++){
					if((i&(1<<k))||!use[k])continue;
					if(dp[i+(1<<k)][k][0]=='~'||
					dp[i+(1<<k)][k].size()>dp[i][j].size()+len[k]-val[j][k]||
					(dp[i+(1<<k)][k].size()==dp[i][j].size()+len[k]-val[j][k]&&
					dp[i+(1<<k)][k]>dp[i][j]+str[k].substr(val[j][k],len[k]-val[j][k])))dp[i+(1<<k)][k]=dp[i][j]+str[k].substr(val[j][k],len[k]-val[j][k]);
				}
			}
		}
		int goal=0;
		for(int i=0;i<a;i++)if(use[i])goal+=(1<<i);
		int ret=999999999;
		string res="~";
		for(int i=0;i<a;i++){
			if(dp[goal][i][0]=='~')continue;
			if(ret>dp[goal][i].size()||(ret==dp[goal][i].size()&&res>dp[goal][i])){
				ret=dp[goal][i].size();
				res=dp[goal][i];
			}
		}
		printf("%s\n",res.c_str());
	}
}

Measured memory_bytes: 3780
arr=[]
for _ in range(int(input())):
    x,y=map(int,input().split())
    arr.append([x,y])
count=0
flag=0
for i in arr:
    if(i[0]==i[1]):
        count+=1
    else:
        count=0
    if(count>=3):
        print('Yes')
        flag=1
        break
if(flag==0):
    print('No')

Measured memory_bytes: 9020
N = raw_input()
S = raw_input()

def insert(string):
    # str_len = len(string)
    # print str_len
    left = 0
    right = 0
    i=0
    while i < len(string):
        if string[i] == "(":
            left += 1
            # print "left is " + str(left)
        else:
            right += 1
            # print "right is " + str(right)
        if right > left:
            string = "(" + string
            left += 1
            # print string
            i=0
            left = 0
            right = 0
        else:
            i += 1
    return string

def add_ket(string):
    bra = 0
    ket = 0
    for i in range(len(string)):
        if string[i] == "(":
            bra += 1
        else:
            ket += 1
    add = bra-ket
    string = string + add * ")"
    return string


tmp = insert(S)
print add_ket(tmp)


Measured memory_bytes: 2692
def main():
    n = int(input())
    org = [int(a) for a in input().split(" ")]
    q = int(input())

    for _ in range(q):
        b, m, e = map(int, input().split(" "))
        dummy = org[:]

        for k in range(e - b):
            first = b + k
            second = b + ((k + (e - m))%(e - b))
            dummy[second] = org[first]

        org = dummy[:]
    print(*dummy)
main()



Measured memory_bytes: 5820
from numpy import *
N,K = map(int,input().split())
M = zeros((3*K,3*K),int)
L = 2*K
O = 0

for n in range(N):
  x,y,c = input().split()
  x = int(x)%L
  y = int(y)%L
  t = c=="W"
  M[x,y]+=1-2*t
  O+=t

for n in range(2):
  M[L:] = M[:K]
  M = cumsum(M,axis=0)
  M[:L] = M[K:]-M[:L]
  M = M.T
  
M = M[:L,:L]
print(O+(M+roll(roll(M,K,axis=0),K,axis=1)).max())

Measured memory_bytes: 167628
n = int(input())

S = [0]
for i,s in enumerate(input().split()):
    S.append(int(s)+S[i])
S.sort()
S.append(10000000000)
count = 0
p = S[0]
l = 0
for i in range(n+2):
    if p != S[i]:
        count += (i-l)*(i-l-1)//2
        l = i
        p = S[i]
print(count)

Measured memory_bytes: 27616
#include<bits/stdc++.h>
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--)
typedef long long LL;
int N;
 
int main(){
	int H,W,h,w;
	cin>>H>>W>>h>>w;
	cout<<(H-h)*(W-w)<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fi first
#define se second

using namespace std;
typedef long long ll;

const int N=405;

struct vec{
	int a[4];
	vec(){a[0]=a[1]=a[2]=a[3]=0;}
	vec(int x,int y,int z,int t){a[0]=x,a[1]=y,a[2]=z,a[3]=t;}
	void read(){for(int i=0;i<4;i++)scanf("%d",&a[i]);}
	void move(){int t=a[0];a[0]=a[1],a[1]=a[2],a[2]=a[3],a[3]=t;}
	int& operator[](int x){return a[x];}
	bool friend operator<(const vec&x,const vec&y){
		for(int i=0;i<4;i++)if(x.a[i]!=y.a[i])return x.a[i]<y.a[i];
		return false;
	}
	bool friend operator==(const vec&x,const vec&y){
		for(int i=0;i<4;i++)if(x.a[i]!=y.a[i])return false;
		return true;
	}
	pair<vec,int> move_to_best(){
		vec r=*this;int t=0;
		for(int i=0;i<4;i++){
			if(*this<r)r=*this,t=1;
			else if(r==*this)t++;
			this->move();
		}
		return {r,t};
	}
};

struct node{
	ll way[4];
	ll get(int x){ll r=way[x-1];while(x)r*=x--;return r;}
	void update(int u){for(int i=3;i;i--)way[i]+=way[i-1]*u;way[0]+=u;}
	void dndate(int u){way[0]-=u;for(int i=1;i<=3;i++)way[i]-=way[i-1]*u;}
};
map<vec,node> data;
map<vec,int> now;
vec fc[N];
int ti[N],n;
ll ans;

ll chk(vector<vec> faces){
	now.clear();
	for(auto p:faces)now[p.move_to_best().fi]++;
	ll ret=1;
	for(auto it:now){
		if(!data.count(it.fi))return 0;
		ret*=data[it.fi].get(it.se);
	}
	return ret;
}

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		fc[i].read();
		auto p=fc[i].move_to_best();
		data[fc[i]=p.fi].update(p.se);
		ti[i]=p.se;
	}
	for(int i=0;i<n;i++){
		data[fc[i]].dndate(ti[i]);
		for(int j=i+1;j<n;j++){
			data[fc[j]].dndate(ti[j]);
			for(int k=0;k<4;k++){
				auto&a=fc[i],&b=fc[j];
				ans+=chk({vec(b[1],b[0],a[1],a[0]),vec(a[1],b[0],b[3],a[2]),vec(a[3],a[2],b[3],b[2]),vec(b[1],a[0],a[3],b[2])});
				fc[j].move();
			}
			data[fc[j]].update(ti[j]);
		}
		data[fc[i]].update(ti[i]);
	}
	printf("%lld\n",ans/3);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

const long long INF = 1e18;
//const ll mod = 1000000007;

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    int x, y, z;
    cin >> x >> y >> z;
    swap(x, y);
    swap(x, z);
    cout << x << " " << y << " " << z << endl;
    return 0;
}

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

int main(void)
{
    int N,K,sum = 0;
    
    cin >> N >> K;
    vector<int> l(N);

    rep(i, N)
        cin >> l[i];

    sort(l.begin(),l.end(),greater<int>());


    rep(i,K)
        sum += l[i];

    cout << sum << endl;

    return 0;
}

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

const int N = 5010;
const int M = 210;
inline int read(){
	int ans=0;
	char last=' ',ch=getchar();
	while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
	return ans;
}
int n,m,b[N][M];
ll a[N];
int q[M][N],head[M],tail[M];
ll f[N];
ll cal(){
	memset(head,0,sizeof(head));
	memset(tail,0,sizeof(tail));
	ll ret = 0,tmp;
	for(int i=1;i<=n;i++){
		tmp = 0 ;
		for(int j=1;j<=m;j++){
			while(head[j]<tail[j] && b[i][j]>=b[q[j][tail[j]-1]][j]) tail[j]--;
			q[j][tail[j]++] = i;
		}
		memset(f,0,sizeof(f));
		tmp = 0;
		for(int j=1;j<=m;j++){
			for(int k=head[j];k<tail[j]-1;k++) f[q[j][k]] += b[q[j][k]][j]-b[q[j][k+1]][j];
			f[i] += b[i][j];
		}
		for(int k=i;k>=1;k--){
			tmp+=f[k];
			ret=max(ret,tmp-a[i]+a[k]);
		}
	}
	return ret;
}

int main(){
	n = read(), m = read();
	for(int i=2;i<=n;i++) a[i] = read(), a[i] += a[i-1];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) 
			b[i][j] = read();
	}
	printf("%lld\n",cal());
	return 0;
}

Measured memory_bytes: 5376