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

#define Int register int
#define mod 1000000007
#define MAXN 2005

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

int n,k,fac[MAXN * MAXN],ifac[MAXN * MAXN],dp[MAXN][MAXN];
int mul (int a,int b){return 1ll * a * b % mod;}
int dec (int a,int b){return a >= b ? a - b : a + mod - b;}
int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}
int qkpow (int a,int b){int res = 1;for (;b;b >>= 1,a = mul (a,a)) if (b & 1) res = mul (res,a);return res;}
int binom (int a,int b){return mul (fac[a],mul (ifac[b],ifac[a - b]));}

signed main(){
	read (n,k);
	if (k == 1) return puts ("1"),0;fac[0] = 1;
	for (Int i = 1;i <= n * k;++ i) fac[i] = mul (fac[i - 1],i);
	ifac[n * k] = qkpow (fac[n * k],mod - 2);for (Int i = n * k;i;-- i) ifac[i - 1] = mul (ifac[i],i);
	for (Int i = 0;i <= n;++ i) dp[i][0] = 1;
	for (Int i = 1;i <= n;++ i)
		for (Int j = 1;j <= i;++ j)
			dp[i][j] = add (dp[i - 1][j],mul (dp[i][j - 1],binom (n * k - (k - 1) * (j - 1) - 1 - i,k - 2)));
	write (mul (dp[n][n],fac[n])),putchar ('\n');
	return 0;
}
/*
dp[i][j]表示前面i个白球，j个颜色已经填满了
dp[i][j]=dp[i-1][j]+dp[i][j-1]*C(n*k-(k-1)*(j-1)-1-i,k-2) 
dp[n][n]*n!
*/

Measured memory_bytes: 48648
program am
implicit none
integer::N
integer(16),allocatable,dimension(:)::A
integer(16),allocatable,dimension(:,:)::DP
integer(16)::i
read*,N
allocate(A(N))
read*,A
allocate(DP(N,3))
DP(1,1)=A(1)
DP(2,2)=A(2)
if(N>=3)DP(3,3)=A(3);DP(3,1)=A(1)+A(3)
do i=4,N
    DP(i,1)=DP(i-2,1)+A(i)
    DP(i,2)=max( DP(i-2,2), DP(i-3,1) )+A(i)
    DP(i,3)=max( DP(i-2,3), DP(i-3,2), DP(i-4,1) )+A(i)
end do
if(mod(N,2)==0)then
    print"(i0)",max(DP(N,2),DP(N-1,1))
else
    print"(i0)",max(DP(N,3),DP(N-1,2),DP(N-2,1))
endif
end program am

Measured memory_bytes: 15520
(async () => {
    let input = '';
    for await (const chunk of process.stdin) input += chunk;
    const values = input.split(/\s/);
    const n = +values.shift();
    let c = values[0].split('').slice(0, n);

    let count = 0;
    let lastRed = n;
    let firstWhite = 0;
    while(true){
        lastRed = c.lastIndexOf('R', lastRed);
        firstWhite = c.indexOf('W', firstWhite);
        if(lastRed < firstWhite)break;
        if(lastRed == -1)break;
        if(firstWhite == -1)break;
        c[lastRed] = 'W';
        c[firstWhite] = 'R';
        count++;
    }
    console.log(count);
})()


Measured memory_bytes: 36800
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    while(1){
        c-=b;
        if(c<=0){
            cout<<"Yes"<<endl;
            break;
        }
        a-=d;
        if(a<=0){
            cout<<"No"<<endl;
            break;
        }
    }
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const ll INF = 1LL << 60;

int main(){
    int n;
    cin >> n;
    vector<double> a(n);
    rep(i,n) cin >> a[i];

    double ans=0;
    rep(i,n){
        ans += 1/a[i];
    }
    ans = 1/ans;

    cout << setprecision(10) << ans << endl;
}

Measured memory_bytes: 3784
#include <iostream>
#include <map>

#define MAX_ 1510

using namespace std;

int main(int argc, char const *argv[])
{
	int n,m;

	int h[MAX_],w[MAX_];

	while(1){
		cin>>n>>m;
		if(n+m==0) break;

		for(int i1=0;i1<MAX_;i1++){
			h[i1]=0;
			w[i1]=0;
		}


		for(int i1=0;i1<n;i1++){
			cin>>h[i1];
		}
		for(int i1=0;i1<m;i1++){
			cin>>w[i1];
		}

		map<int,int> mh,mw;
		for(int i1=0;i1<n;i1++){
			int ln=0;
			for(int i2=i1;i2<n;i2++){
				ln+=h[i2];
				mh[ln]++;
			}
		}

		for(int i1=0;i1<m;i1++){
			int ln=0;
			for(int i2=i1;i2<m;i2++){
				ln+=w[i2];
				mw[ln]++;
			}
		}

		map<int,int>::iterator ih = mh.begin();
		map<int,int>::iterator iw = mw.begin();
		int count=0;
		while(1){
			if((*ih).first==(*iw).first) {
				count += ((*ih).second*(*iw).second);
				ih++;
				iw++;
			}
			else if((*ih).first>(*iw).first) iw++;
			else ih++;

			if(ih==mh.end() || iw==mw.end()) break;
		}

		cout<<count<<endl;



	}

	return 0;
}

Measured memory_bytes: 27988
#include <bits/stdc++.h>
using namespace std;
constexpr long long MOD = 1000000007;
using ll = long long;
int main() {
string s;
cin >> s;
if (s[0] != 'A') {
    cout << "WA" << endl;
    return 0;
}
ll cnt = 0;
for (ll i = 0; i < s.size(); i++) {
    if (i == 0) continue;
    else if(2<=i&&(s.size()-2>=i)){
        if (s[i] == 'C') cnt++;
    }
    else if(isupper(s[i])){
        cout << "WA" << endl;
        return 0;
    }
}
if (cnt != 1) cout << "WA" << endl;
else
    cout << "AC" << endl;
}


Measured memory_bytes: 256
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T

main :: IO ()
main = do
  (n : k : _) <- map unsafeTextToInt . T.words <$> T.getLine :: IO [Int]
  print . length . takeWhile (/= 0) . iterate (`div` k) $ n

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n


Measured memory_bytes: 508
n = int(input())
A = []
B = []
for _ in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

ans = 0
for a, b in zip(A[::-1], B[::-1]):
    a += ans
    if a % b == 0:
        continue
    ans += b - a % b

print(ans)


Measured memory_bytes: 12624
import sys
import os
# import math
# input = sys.stdin.readline

def int_array():
    return list(map(int, input().strip().split()))


def str_array():
    return input().strip().split()

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b, a % b);x

def take_input():
	if os.environ.get("check"):
		sys.stdin = open('input.txt', 'r') 
		sys.stdout = open('output.txt', 'w')
		
take_input()
######################### TEMPLATE ENDS HERE #################################


n, m = int_array()
count = 0
for _ in range(n):
    a,b = int_array()
    tmp = (a**2+b**2)**0.5

    if tmp <= m:
        count += 1

print(count)

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

from collections import defaultdict
import numpy

def sieve_of_eratosthenes(n):
  primes = [2]
  cands = numpy.array(list(range(3, n+1, 2)), dtype=numpy.int)
  while len(cands) != 0:
    prime = primes[-1]
    cands = cands[cands % prime != 0]
    if len(cands) == 0:
      break
    primes.append(cands[0])
  return primes

def main():
  n = int(input())
  k = 5
  primes = sieve_of_eratosthenes(55555) 
  counts = defaultdict(list)
  for prime in primes:
    counts[prime % k].append(prime)
    if len(counts[prime % k]) >= n:
      print(' '.join(list(map(str, counts[prime % k]))))
      return
    
    
if __name__=='__main__':
  main()



Measured memory_bytes: 21844
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include<iomanip>

using namespace std;
typedef long long ll;

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include<iomanip>

using namespace std;
typedef long long ll;

int numberSize(string N) {
	int sum = 0;
	for (int i = 0; i < (int)N.size(); i++) {
		sum += N[i] - '0';
	}
	return sum;
}

int main() {
	string N; cin >> N;
	int sum = numberSize(N);
	int Max = N[0] - '0' + 9 * ((int)N.size() - 1);
	if (sum == Max) cout << sum << endl;
	else cout << Max - 1 << endl;
}


Measured memory_bytes: 3596
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CommonSubsequence solver = new CommonSubsequence();
        solver.solve(1, in, out);
        out.close();
    }

    static class CommonSubsequence {
        public static int MOD = 1000000007;

        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();
            int[] s = new int[n];
            int[] t = new int[m];

            long[][] sum = new long[n + 1][m + 1];

            for (int i = 0; i < n; i++) {
                s[i] = in.nextInt();
            }
            for (int i = 0; i < m; i++) {
                t[i] = in.nextInt();
            }
            for (int i = 0; i <= n; i++) {
                for (int j = 0; j <= m; j++) {
                    if (i == 0 || j == 0) {
                        sum[i][j] = 1;
                    }
                }
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (s[i] == t[j]) {
                        sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j];
                        sum[i + 1][j + 1] %= MOD;
                    } else {
                        sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j];
                        sum[i + 1][j + 1] %= MOD;
                        sum[i + 1][j + 1] = modSub(sum[i + 1][j + 1], sum[i][j], MOD);

                    }
                }
            }

            out.println((sum[n][m]) % MOD);

        }

        static long modSub(long x, long n, long mod) {
            long v = x - n;
            if (v < 0) {
                v += mod;
            }
            return v % mod;
        }

    }
}



Measured memory_bytes: 86716
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>

using namespace std;
//#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
const int inf=1000000007;
const int MOD=1000000007;
signed main(){
  int a,b;cin>>a>>b;
  int res=-1;
  rep1(i,10000){
    if(i*8/100==a&&i*10/100==b){
      res=i;
      break;
    }
  }
  cout<<res<<endl;
  return 0;
}


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

int main() {
  string x,y;
  cin >> x >> y;
  int a = std::stoi(x, nullptr, 16); 
  int b = std::stoi(y, nullptr, 16); 
  
  if(x == y){
    cout << "=" << endl;
  }
  else if(a > b){
    cout << ">" << endl;
  }
  else{
    cout << "<" << endl;
  }
}


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

public class Main {
	static Scanner sc = new Scanner(System.in);
	static char[] N = new char[4];
	static int L,S;
	public static void main(String[] args){
		while(read()){
			solve();
		}
	}
	
	public static boolean read(){
		String tmp;
		tmp = sc.next();
		if(tmp.equals("0000")) return false;
		N = tmp.toCharArray();
		
		return true;
		
	}
	
	public static void solve(){
		
		int Nint = Integer.parseInt(String.valueOf(N));
		int ans = 0;
		
		while(Nint != 6174){
			Arrays.sort(N);
			S = Integer.parseInt(String.valueOf(N));
			L = ((int)N[3]-48) * 1000 + ((int)N[2]-48) * 100 + ((int)N[1]-48) * 10 + ((int)N[0]-48);
			
			
			Nint = L-S;
			if(Nint == 0) {
				System.out.println("NA"); return;
			}
			
			
			N = String.format("%04d", Nint).toCharArray();			
			ans++;
		}
		
		System.out.println(ans);
		
		return;
	}
}


Measured memory_bytes: 61952
#include<iostream>
#include<string>
#include<cmath>
#include<bits/stdc++.h>
using namespace std;

int main(){

    string N;
    int64_t n = 0;
    int i = 0;

    cin >> N;

    while(N[i]!='\0'){
        n = n + (int)(N[i]-'0');
        i++;
    }


    if(n%9 == 0){
        cout << "Yes" <<endl;
    }else{
        cout << "No" <<endl; 
    }
    
 
 }

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

int main() {
  string s;
  cin>>s;
  if(s.size()<4){
    cout<<"No"<<endl;
  }
  else{
    string t=s.substr(0,4);
    if(t=="YAKI") cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }



}


Measured memory_bytes: 3632
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;
 
public class Program{
  public static void Main(){
    int[] xyz = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
    int temp;
    
    temp = xyz[0];
    xyz[0] = xyz[1];
    xyz[1] = temp;
    
    temp = xyz[0];
    xyz[0] = xyz[2];
    xyz[2] = temp;
    
    Console.WriteLine("{0} {1} {2}",xyz[0],xyz[1],xyz[2]);
  }
}

Measured memory_bytes: 13268
neko = (30,30) #FATAL ERROR
unko = [True for i in xrange(neko[0])]
numbers=[]
for i in xrange(28):
    n = input()

#if False:n = int(raw_input())
    if False:neko.pop(n-1)
    dog = n #int(raw_input())
    numbers.extend([])
    numbers.append(dog)
for i in xrange(28):unko[numbers[i]-1]=False #Love

for i in xrange(30):
    if unko[i]:
        print i+1
exit()

neko.sort()
print neko[0]
#print "FK no unko smells like shit"
print neko[1]

Measured memory_bytes: 4248
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n;
    cin>>n;
    ll arr[n];
    map<ll,ll, greater<ll>>mp;
    for(ll i=0; i<n; i++ )
    {
        cin>>arr[i];
        mp[arr[i]]++;
    }
    ll c=0;
    ll ar=1;
    ll f=0;
    for(auto it=mp.begin(); it!=mp.end(); ++it)
    {
        ll s=it->second;
        if(c==0)
        {
            if(s>=4)
            {
                cout<<it->first*it->first<<endl;
                f=1;
                break;
            }
        }
        if(s>=2)
        {
            ar=ar*it->first;
            c++;
            if(c==2)
            {
                break;
            }
        }
    }
    if(c!=2&&f==0)
    {
        cout<<0<<endl;
    }
    else if(c==2&&f==0)
    {
        cout<<ar<<endl;
    }

}


Measured memory_bytes: 10624
def resolve():
    N, u, v = list(map(int, input().split()))
    u, v = u-1, v-1
    adjs = [ [] for _ in range(N)]
    for _ in range(N-1):
        a, b = list(map(lambda x: int(x)-1, input().split()))
        adjs[a].append(b)
        adjs[b].append(a)
    dist_from_u = [float("inf") for _ in range(N)]
    dist_from_u[u] = 0
    import collections
    q = collections.deque([u])
    while q:
        node = q.pop()
        for adj in adjs[node]:
            if dist_from_u[adj] > dist_from_u[node]+1:
                dist_from_u[adj] = dist_from_u[node]+1
                q.appendleft(adj)
    #print(dist_from_u)
    dist_from_v = [float("inf") for _ in range(N)]
    dist_from_v[v] = 0
    import collections
    q = collections.deque([v])
    while q:
        node = q.pop()
        for adj in adjs[node]:
            if dist_from_v[adj] > dist_from_v[node]+1:
                dist_from_v[adj] = dist_from_v[node]+1
                q.appendleft(adj)
    #print(dist_from_v)
    length = 0
    for i in range(N):
        if dist_from_u[i] < dist_from_v[i] and length < dist_from_v[i]:
            length = dist_from_v[i]
    print(length-1)
    
if __name__ == "__main__":
    resolve()



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

H, W = [int(x) for x in input().split()]
S = []
for _ in range(H):
    S.append(input().rstrip())

dp_left = [[0] * (W + 2) for _ in range(H + 2)]
dp_up = [[0] * (W + 2) for _ in range(H + 2)]
dp_right = [[0] * (W + 2) for _ in range(H + 2)]
dp_down = [[0] * (W + 2) for _ in range(H + 2)]

for i in range(1, H + 1):
    for j in range(1, W + 1):
        if S[i - 1][j - 1] == "#":
            dp_left[i][j] = 0
        else:
            dp_left[i][j] = dp_left[i][j - 1] + 1
        
        if S[i - 1][-j] == "#":
            dp_right[i][-(j + 1)] = 0
        else:
            dp_right[i][-(j + 1)] = dp_right[i][-j] + 1

for i in range(1, W + 1):
    for j in range(1, H + 1):
        if S[j - 1][i - 1] == "#":
            dp_up[j][i] = 0
        else:
            dp_up[j][i] = dp_up[j - 1][i] + 1

        if S[-j][i - 1] == "#":
            dp_down[-(j + 1)][i] = 0
        else:
            dp_down[-(j + 1)][i] = dp_down[-j][i] + 1

ans = 0

for i in range(1, H + 1):
    for j in range(1, W + 1):
        ans = max(ans, dp_left[i][j] + dp_up[i][j] + dp_right[i][j] + dp_down[i][j] - (dp_left[i][j] > 0) - (dp_up[i][j] > 0) - (dp_right[i][j] > 0) - (dp_down[i][j] > 0) + 1)

print(ans)






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

#define int long long

using namespace std;

signed main(){
    int N,M;
    cin>>N>>M;
    int arr[M];
    int sum=0;
    for(int i=0;i<M;i++){
        cin>>arr[i];
        sum += arr[i];
    }
    if(sum>N){
        cout<<-1;
    }
    else{
        cout<<N-sum;
    }
    

}

Measured memory_bytes: 3636
def main():
    N, K = map(int, input().split())
    S = input()

    prev = "s"
    count = 0
    for s in S:
        if prev != s:
            count += 1
            prev = s
    print(min(N + 2 * K - count, N - 1))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  vector<pair<int,int>> ab(N);
  for (int i = 0; i < N; i++){
    cin >> ab.at(i).first >> ab.at(i).second;
  }
  sort(ab.begin(),ab.end());
  vector<pair<int,int>> cd(N);
  for (int i = 0; i < N; i++){
    cin >> cd.at(i).first >> cd.at(i).second;
  }
  sort(cd.begin(),cd.end());
  vector<bool> nakayoshi(N);//仲良しペアに使われているかの判定
  int ans = 0;
  for (int i = 0; i < N; i++){
    int num;
    int yzahyo = -1;
    bool pea = false;
    for (int j = 0; j < N; j++){
      if(!(nakayoshi.at(j))){//仲良しに使われていないかの判定
        if (ab.at(j).first < cd.at(i).first && ab.at(j).second < cd.at(i).second){//仲良しペアになれる条件を満たしているかの判定
          if (yzahyo < ab.at(j).second){//y座標が今までの判定の中で最も大きい
            yzahyo = ab.at(j).second;
            num = j;
            pea = true;
          }
        }
      }
    }
    if (pea) {
      nakayoshi.at(num) = true;
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

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

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

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

template < typename T >
void vprint(T &V){
	for(auto v : V){
    	cout << v << " ";
	}
	cout << endl;
}

struct UnionFind{
    vector<ll> parent;
    UnionFind(ll sz){
        parent.resize(sz);
        reset();
    }

    void reset(){
        FOR(i, 0, parent.size()){
            parent[i] = i;
        }
    }

    void unite(ll a, ll b){
        if(a>b){
            swap(a, b);
        }
        ll rootA = findRoot(a);
        ll rootB = findRoot(b);
        if(rootA>rootB){
            swap(rootA, rootB);
        }
        if(rootA==rootB){
            return;
        }else{
            // 小さい方を親にする
            parent[rootB] = rootA;
        }
    }

    ll findRoot(ll a){
        if(parent[a]==a){
            return a;
        }else{
            return parent[a] = findRoot(parent[a]);
        }
    }

    map<ll, vector<ll> > getGroups(){
        map<ll, vector<ll> > G;
        FOR(i, 0, parent.size()){
            ll r = findRoot(i);
            G[r].push_back(i);
        }
        return G;
    }

    bool is_same_group(ll a, ll b){
        ll rootA = findRoot(a);
        ll rootB = findRoot(b);
        if(rootA==rootB){
            return true;
        }else{
            return false;
        }
    }
};

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

    // input
    ll N, M;
    cin >> N >> M;

    auto uf = UnionFind(N);

    FOR(i, 0, M){
        ll x, y, z;
        cin >> x >> y >> z;

        x--;
        y--;

        uf.unite(x, y);
    }

    auto groups = uf.getGroups();
    p(groups.size());
    
    return 0;
}

Measured memory_bytes: 12032
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int N;

long long int A[200005], B[200005];

set <pair<long long int, int> > S;

long long int CALC(void) {


	if (S.size() == 0) { return 0; }
	else {
		auto it = S.begin();
		int id = (*it).second;

		long long int w = - (*it).first;
		S.erase((*it));

		long long int ret = w;

		B[id] -= (B[(id - 1 + N) % N] + B[(id + 1) % N])*w;


		id = (id - 1 + N) % N;
		w = (B[id] - A[id]) / (B[(id - 1 + N) % N] + B[(id + 1) % N]);

		if (w > 0) {
			S.insert(make_pair(-w, id));
		}

		id =(id+2)%N;
		w = (B[id] - A[id]) / (B[(id - 1 + N) % N] + B[(id + 1) % N]);

		if (w > 0) {
			S.insert(make_pair(-w, id));
		}

		return ret;

	}

	return 0;

}

long long int CHECK(void) {

	int a = 1;
	for (int i = 0; i <= N - 1; i++) {
		if (A[i] != B[i]) { a = -1; }
	}

	if (a == 1) { return 1; }

	return -1;


}

int main(void) {


	cin >> N;

	for (int i = 0; i <= N - 1; i++) {
		cin >> A[i];
	}

	

	for (int i = 0; i <= N - 1; i++) {
		cin >> B[i];
	}

	for(int i=0;i<=N-1;i++){

		long long int w;
		w = (B[i] - A[i]) / (B[(i - 1 + N) % N] + B[(i + 1) % N]);

		if (w > 0) {
			S.insert(make_pair(-w, i));
		}
		
	}

	

	long long int ans = 0;


	int sign = 1;

	while (sign) {
		sign = 0;

		long long int tmp = CALC();

		//cout << "CHECK= " << tmp << endl;
		if (tmp == 0) { if (CHECK() == 1) { break; }
		else { cout << -1 << endl; return 0; }
		}
		else { ans += tmp; sign = 1; }
	
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 9600
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<functional>
#include<iostream>
#define rep(i,a) for(i=1;i<=a;i++)
using namespace std;
int main(void)
{
	int n,i,x;
	cin>>n;
	rep(i,n) {
		if(i%3==0) cout<<" "<<i;
		else {
			x=i;
			while(x>0) {
				if(x%10==3) {cout<<" "<<i;break;}
				else x=x/10;
			}
		}
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 3072
#include<stdio.h>
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<string>
#include<math.h>
#include <numeric>

using namespace std;
typedef long long ll;

#define REP(i,n) for(int i=0;i<n;++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << #s << " " << s << endl

const ll mod = 1e9 + 7;
const ll inf = 1e18;

void printVector(vector<ll> A){
    cout << "[vector]" << endl;
    for(int i=0; i<A.size(); i++){
        cout << A[i] << " ";
    }
    cout << endl;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    // input
    int N;
    cin >> N;

    vector<int> p;

    FOR(i, 0, N){
        int price;
        cin >> price;
        p.push_back(price);
    }    

    sort(ALL(p));

    int sum = accumulate(p.begin(), p.end()-1, 0) + p[N-1] / 2;

    p(sum);

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    long long N;
    long long a;
    int flag=0;
    cin >> N;
    for(long long i=0;i<N;i++){
        cin >> a;
        if(a%2==1){
            flag=1;
        }
    }
    if(flag==0){
        cout << "second";
    } else {
        cout << "first";
    }
    return 0;
}



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

using namespace std;

using int64 = long long;

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

  int p, q, r;
  cin >> p >> q >> r;
  cout << min(min(p + q, q + r), r + p) << endl;
}


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

const int MAXN = 200000 + 10;

int cnt[200];

int32_t main() {
    ios_base::sync_with_stdio(0);
    string s;

    cin >> s;

    int l = s.length();

    for (auto c: s) {
        cnt[c]++;
    }

    char c = 0;
    for (int i = 'a'; i <= 'z'; i++) {
        if (cnt[i] == 0) {
            c = i;
            break;
        }
    }

    if (c) {
        cout << s << c << "\n";
        return 0;
    }

    c = s[l-1];
    bool sorted = false;
    for (int i = l-2; i >= 0; i--) {
        if (s[i] < s[i+1]) {

            char bestc = s[i+1];
            for (int j = i+1; j < l; j++) {
                if (s[j] > s[i] && s[j] < bestc) {
                    bestc = s[j];
                }
            }
            s[i] = bestc;
            s = s.substr(0, i+1);
            sorted = true;
            break;
        }
    }

    if (sorted)
        cout << s << "\n";
    else
        cout << "-1\n";
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#include<utility>
#include<tuple>
#include<string>
#include<vector>
#include<numeric>
#include<algorithm>
#include<queue>
#include<deque>
#include<bitset>
#include<cmath>
#include<map>
#include<iomanip>
using namespace std;
using ll = long long int;
const ll mod = 1e9 + 7;
#define rep(i, a, b) for(int i = a; i < b; i++)

int gcd(int, int);

int main() {
	
	int n, X;
	cin >> n >> X;

	vector<int> x(n);
	rep(i, 0, n) {
		cin >> x[i];
		x[i] = abs(X - x[i]);
	}

	if (n == 1) {
		cout << x[0] << endl;
		return 0;
	}

	int ans = gcd(x[0], x[1]);

	rep(i, 1, n) {
		ans = gcd(ans, x[i]);
	}

	cout << ans << endl;

	return 0;
}

//最大公約数(ユークリッド互除法)
int gcd(int m, int n) {
	ll temp;
	while (m % n != 0) {
		temp = n;
		n = m % n;
		m = temp;
	}
	return n;
}

Measured memory_bytes: 640
import           Control.Monad

main :: IO ()
main = do
    [n, t] <- fmap (map read . words) getLine :: IO [Int]
    cts    <- replicateM n $ fmap (map read . words) getLine :: IO [[Int]]
    solve t cts

solve :: Int -> [[Int]] -> IO ()
solve t cts =
    let cs = map head $ filter (\(_ : ti : _) -> ti <= t) cts
    in  if null cs then putStrLn "TLE" else print $ minimum cs


Measured memory_bytes: 1020
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define min(p,q)((p)<(q)?(p):(q))
#define zahyoutype double

typedef struct Point{zahyoutype x,y;}P;
typedef struct line{P p1,p2;}L;
int sgn(zahyoutype x){return x<0?-1:x>0;}
double seglen(L s){return hypot(s.p2.x-s.p1.x,s.p2.y-s.p1.y);}

//opとoqの内積と外積
zahyoutype innerproduct(P p,P q,P o){return (p.x-o.x)*(q.x-o.x)+(p.y-o.y)*(q.y-o.y);}
zahyoutype crossproduct(P p,P q,P o){return (p.x-o.x)*(q.y-o.y)-(p.y-o.y)*(q.x-o.x);}
int iscross(L s,L t){
	//点(p,q)が直線f(x,y)=ax+by+c=0のどっち側にあるかは外積を見ればよい
	zahyoutype t1=crossproduct(t.p1,s.p2,s.p1);
	zahyoutype t2=crossproduct(t.p2,s.p2,s.p1);
	zahyoutype t3=crossproduct(s.p1,t.p2,t.p1);
	zahyoutype t4=crossproduct(s.p2,t.p2,t.p1);
	//同一直線上にない
	if(t1 || t2)return sgn(t1)!=sgn(t2) && sgn(t3)!=sgn(t4);
	//同一直線上にある
	//内積をみる
	zahyoutype c1=innerproduct(s.p2,s.p2,s.p1);
	zahyoutype c2=innerproduct(t.p1,s.p2,s.p1);
	zahyoutype c3=innerproduct(t.p2,s.p2,s.p1);
	if(0<=c2&&c2<=c1 || 0<=c3&&c3<=c1 || c2<=0&&c1<=c3 || c3<=0&&c1<=c2)return 1;
	return 0;
}
double distPP(P p,P q){L s={p,q};return seglen(s);}
double distPL(P p,L s){return fabs(crossproduct(p,s.p2,s.p1)/seglen(s));}
double distPS(P p,L s){
	zahyoutype c =innerproduct(   p,s.p2,s.p1);
	zahyoutype ss=innerproduct(s.p2,s.p2,s.p1);
	if(c<=0)return distPP(p,s.p1);
	if(c<=ss)return distPL(p,s);
	return distPP(p,s.p2);
}
double distSS(L s,L t){return iscross(s,t)?0:min(min(distPS(s.p1,t),distPS(s.p2,t)),min(distPS(t.p1,s),distPS(t.p2,s)));}

void readpoint(P*p){zahyoutype x=1;scanf(x/2?"%lf%lf":"%ld%ld",&p->x,&p->y);}
void printpoint(P p){zahyoutype x=1;printf(x/2?"%.9lf %.9lf\n":"%ld %ld\n",p.x,p.y);}

int main(){
	int q;
	scanf("%d",&q);
	while(q--){
		L s,t;
		for(int i=0;i<2;i++){
			readpoint(&s.p1);
			readpoint(&s.p2);
			if(!i)t=s;
		}
		printf("%.9f\n",distSS(s,t));
	}
}


Measured memory_bytes: 2088
<?php
  $s = strval(trim(fgets(STDIN)));
  $array = str_split($s);
  $prev = "default";
  $counter = 1;
  $change = 0;
  $length = count($array);
  foreach($array as $n){
    if($counter === 1){
      $prev = $n;
    }elseif($n === $prev){
      if($prev === "0"){
        $prev = "1";
      }else{
        $prev = "0";
      }
      $change++;
    }else{
      $prev = $n;
    }
    $counter++;
  }
//  if($change > $length/2){
//    $change = $length - $change;
//  }
  echo $change;


Measured memory_bytes: 21260
# -*- coding: utf-8 -*-

# input
n = int(input())
alist = list(map(int, input().split()))

# process
result = 0
for bit in range(60):
    m = 1 << bit
    c = sum(a & m for a in alist) >> bit
    result += (c * (n - c)) << bit
    result %= 10**9+7

# output
print(result)


Measured memory_bytes: 42156
def main():
    N = int(input())
    L = [int(_x) for _x in input().split()]
    length = len(L)
    LL = list(sorted(L))
    cnt = 0
    for i in range(0, length):
        for j in range(i+1, length):
            for k in range(j+1, length):
                if LL[i] + LL[j] > LL[k] and LL[i] != LL[j] and LL[i] != LL[k] and LL[j] != LL[k]:
                    cnt += 1
    print(cnt)


main()


Measured memory_bytes: 9216
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
  ll k;
  cin >>k;
  ll e[k];
  for(ll i=0;i<k;i++) cin >>e[i];
  sort(e,e+k);
  vector <pair<ll,ll>> ee;
  ll c=1;
  for(ll i=0;i<k;i++){//配列の中身がそれぞれ何個あるかのカウント
   if(e[i]==e[i+1]){
     c++;
     if(i==k-2){//122333みたいなときは3のところがansに入らないので
       ee.push_back(make_pair(c,e[i]));
       break;
     }
   }
   else{
     ee.push_back(make_pair(c,e[i]));
     if(i==k-2) {
         ee.push_back(make_pair(1,e[i+1]));//112223とかのときにansに3の分を足すため
         break;
     }
     c=1;
   }
  }
   ll es=ee.size();
   if(k%2==0) {
     if(es!=(k/2)) cout <<0<<endl;
     else {
       ll p=1;
        for(ll i=0;i<es;i++){
           if(ee[i].first!=2||ee[i].second!=p) {
             cout <<0<<endl;
             return 0;
           }
           p+=2;
        }
        ll o=k/2,l=1;
        for(ll i=0;i<o;i++){
           l*=2;
           l%=1000000007;
        }
        cout <<l<<endl;
        return 0;
     }
   }
   else{
     if(es!=(k/2)+1) cout <<0<<endl;
     else{
       ll p=2;
       if(ee[0].first!=1||ee[0].second!=0){
         cout <<0<<endl;
         return 0;
       }
       for(ll i=1;i<es;i++){
         if(ee[i].first!=2||ee[i].second!=p) {
           cout <<0<<endl;
           return 0;
         }
         p+=2;
       }
       ll o=k/2,l=1;
       for(ll i=0;i<o;i++){
          l*=2;
          l%=1000000007;
       }
       cout <<l<<endl;
       return 0;
     }
   }
}


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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};

vector<ll> v[510000];

int main()
{
    int h,w,d;
    ll ans=0;
    cin>>h>>w>>d;
    vector<tuple<int,int,int>> a;//num,x,y
    int dist[90010];
    
    
    for(int hh = 0; hh < h; hh++)
    {
        for(int ww = 0; ww < w; ww++)
        {
            int nnn;
            cin>>nnn;
            a.push_back(make_tuple(nnn-1,ww,hh));
        }        
    }
    sort(all(a)); 
    
    for(int i = 0; i < 90010; i++)
    {
        dist[i]=0;
    }
    
    for(int i = 0; i <= a.size(); i++)
    {
        if(i+d<=a.size())
        {
            dist[i+d]=dist[i]
            +abs(get<1>(a[i+d])-get<1>(a[i]))
            +abs(get<2>(a[i+d])-get<2>(a[i]));
        }
    }
    
    int q;
    cin>>q;
    
    for(int qq = 0; qq < q; qq++)
    {
        int l,r;
        cin>>l>>r;
        l--;
        r--;
        cout<<dist[r]-dist[l]<<endl;
    }
    

    return 0;
}

Measured memory_bytes: 14580
#include<bits/stdc++.h>
using namespace std;
int main()
{
  long long int n,d,x,y;
  int count = 0;
  cin>>n>>d;
  while(n--)
  {
    cin>>x>>y;
    if(x*x+y*y<=d*d)
      count++;
  }
  cout<<count;
  return 0;
}

Measured memory_bytes: 3604
#include<iostream>
#include<unordered_map>
#include<numeric>

using ui  = unsigned int;
using ull = unsigned long long;

int main() {
	ui n, m;
	std::cin >> n >> m;

	std::unordered_map<ui,ull> mp;
	
	ull accum = 0;
	mp[0] += 1;
	for (ui i{}; i < n; ++i) {
		ui ai;
		std::cin >> ai;
		accum += ai;
//		std::cout << accum << " ";
		mp[accum % m] += 1;

	}

	auto ans 
		=	std::accumulate(
				std::begin(mp)
				,std::end(mp)
				, ull{}
				, [](auto init, auto x) {
					const auto& t = x.second;
					//std::cout << t << " ";
					return
						init += t <= 1 ? 0 : t * (t - 1) / 2;
				}
			);

	std::cout << ans << "\n";

	return 0;
}

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

typedef long long ll;
 
int main(){
  int n, m;
  cin >> n >> m;
  vector<int> G(n, 0);
  for(int i=0; i<m; i++){
    int x, y;
    cin >> x >> y;
    x--; y--;
    G[x]++;
    G[y]++;
  }
  for(int i=0; i<n; i++){
    cout << G[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

int main(void) {

	int n;
	scanf("%d",&n);

	int a;
	int c=0,c2=0;//カウント
	int i,j;
	int s;

	for(i=0; i<n; i++) {

		scanf("%d",&a);
		
		s = (int)sqrt(a)+1;

		if (a>1) {
			
			if(a==2) c++;
			
			else if(a==3) c++;
			
			else if(a%2 != 0) {
				
				for(j=3; j <= s; j=j+2) {
					
					if(a%j==0){
						c2++;
					}
				}
				if(c2==0){
					c++;
				}
				c2=0;
			}
			else ;
		}
		else ;

	}

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

	return 0;

}


Measured memory_bytes: 2036
#include <bits/stdc++.h>
#define rep(i,n) for(long long i=0; i<n; i++)
#define Rep(i,n) for(long long i=1; i<n; i++)
#define ll long long
#include <math.h>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <queue>
#include <set>
#include <vector>


using namespace std;
#define PI acos(-1)
using P =pair<int,int>;

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

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

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

   cout <<lcm(a,b)<<endl;
   return 0;
}


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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, x[114], y[114], h[114];
	cin>>n;
	REP(i, n){
		cin>>x[i]>>y[i]>>h[i];
	}
	REP(c1, 101){
		REP(c2, 101){
			bool f=false, ok=true;
			int H=1<<30;
			REP(i, n){
				if(f){
					if(h[i]==0){
						if(H>abs(x[i]-c1)+abs(y[i]-c2)){
							ok=false;
							break;
						}
					}
					else if(H!=h[i]+abs(x[i]-c1)+abs(y[i]-c2)){
						ok=false;
						break;
					}
				}
				else{
					if(h[i]==0){
						H=min(H, abs(x[i]-c1)+abs(y[i]-c2));
					}
					else if(H<h[i]+abs(x[i]-c1)+abs(y[i]-c2)){
						ok=false;
						break;
					}
					else{
						H=h[i]+abs(x[i]-c1)+abs(y[i]-c2);
						f=true;
					}
				}
			}
			if(ok && H>=1){
				cout<<c1<<' '<<c2<<' '<<H<<'\n';
				return 0;
			}
		}
	}
	return 0;
}


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

typedef long long int LL;
typedef long long int LLint;
typedef pair<int,int> intpair;
typedef pair<bool,bool> boolpair;
typedef pair<string,string> strpair;
typedef pair<LL,LL> LLpair;
typedef pair<double,double> doublepair;
typedef pair<float,float> floatpair;
typedef vector<int> intvector;
typedef vector<bool> boolvector;
typedef vector<string> strvector;
typedef vector<LL> LLvector;
typedef vector<double> doublevector;
typedef vector<float> floatvector;
#define wait(sec) usleep((sec) * 1000000)
#define ED return 0;
#define TEST cout << "OK" << endl;
#define UP(a,b) ((a+(b-1))/b)
#define SORT(vec) sort(vec.begin(),vec.end());
#define DOUBLECHANGE(count) cout << setprecision(count);
#define REV(vec) reverse(vec.begin(),vec.end());
#define ipow(x,y) LL(pow(x,y))
#define INF 999999999
const long long mod = 1000000007;

int main(){
//    random_device rnd;
//    mt19937 mt(rnd());
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long int N;
    cin >> N;
    vector<long long int> vec (N);
    vector<long long int> sum (N);
    long long int error = 0;
    long long int ans1 = 0;
    long long int ans2 = 0;
    for(long long int i = 0;i < N;i++){
        cin >> vec[i];
        sum[i] = vec[i];
        if(i) sum[i] += sum[i-1];
    }
    for(long long int i = 0;i < N;i++){
        if(i % 2 == 0){
            if(sum[i]+error <= 0){
                ans1 += abs(sum[i]+error)+1;
                error += abs(sum[i]+error)+1;
            }
        }
        else{
            if(sum[i]+error >= 0){
                ans1 += abs(sum[i]+error)+1;
                error -= abs(sum[i]+error)+1;
            }
        }
    }
    error = 0;
    for(long long int i = 0;i < N;i++){
        if(i % 2 == 1){
            if(sum[i]+error <= 0){
                ans2 += abs(sum[i]+error)+1;
                error += abs(sum[i]+error)+1;
            }
        }
        else{
            if(sum[i]+error >= 0){
                ans2 += abs(sum[i]+error)+1;
                error -= abs(sum[i]+error)+1;
            }
        }
    }
    cout << min(ans1,ans2) << endl;
}


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

#define int long long

#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint,int> P1;
typedef pair<int,pint> P2;
typedef pair<pint,pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD=1000000007;
const ll INF=1e18;

int N,M;
ll mod_pow(ll x, ll n) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % MOD;
		x = x * x % MOD;
		n >>= 1;
	}
	return res;
}

signed main() {
    std::cin >> N>>M;
    cout<<mod_pow(N,M)<<endl;

    return 0;
}



Measured memory_bytes: 3120
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define MOD (ll)(1e9+7)
#define INF 1e17
#define int ll
#define EPS (1e-6)
#define double long double
using namespace std;
using ll=long long;
using pii=pair<double,double>;

int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
int lcm(int a,int b) { return a/gcd(a,b)*b; }

int fpow(int b,int p)
{
	if(p==0) return 1;
	int h=fpow(b,p/2);
	if(p%2) return h*b%MOD*h%MOD;
	return h*h%MOD;
}

#define rad(x) (x*PI/180)
const double PI=atan(1)*4;
bool cmp(pii a,pii b){
	if(a==pii(0,0)) return true;
	if(b==pii(0,0)) return false;
	return atan2(a.S,a.F)<atan2(b.S,b.F);
}

double get(pii a,pii b){
	double dx=abs(a.F-b.F);
	double dy=abs(a.S-b.S);
	return sqrt(dx*dx+dy*dy);
}

void out(pii a){
	cout<<fixed<<setprecision(1);
	cout<<" "<<a.F<<" "<<a.S;
	cout<<fixed<<setprecision(20);
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cout<<fixed<<setprecision(20);
	int n; cin>>n;
	vector<pii> v;
	double x,y;
	For(i,0,n-1){
		cin>>x>>y;
		if(x!=0 || y!=0) v.emplace_back(x,y);
	}
	v.emplace_back(0,0);
	sort(all(v),cmp);
	int size=sz(v);
	For(i,1,size-1) v.push_back(v[i]);
	For(i,1,sz(v)-1){
		v[i].F+=v[i-1].F;
		v[i].S+=v[i-1].S;
	}
	double ans=0;
	For(i,0,sz(v)-2) For(j,i+1,sz(v)-1){
		if(j-i>=size) continue;
		ans=max(ans,get(v[j],v[i]));
		//cout<<ans; out(v[j]); out(v[i]); cout<<"\n";
	}
	cout<<ans<<"\n";
	return 0;
}





























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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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

typedef long long ll;

void solve(long long N, long long X, long long Y)
{
    ll ans[2005] = {};
    ll shortcut = Y - X - 1;
    for (int i = 1; i < N; i++)
    {
        for (int j = i + 1; j <= N; j++)
        {
            if (i <= X && Y <= j)
            {
                ans[j - i - shortcut]++;
            }
            else if (i <= X && (X < j && j < Y))
            {
                ll temp = min((long long)j - i, X - i + 1 + Y - j);
                ans[temp]++;
            }
            else if (X < i && Y <= j)
            {
                ll temp = min((long long)j - i, i - X + 1 + j - Y);
                ans[temp]++;
            }
            else if (X < i && j <= Y)
            {
                ll temp = min((long long)j - i, i - X + 1 + Y - j);
                ans[temp]++;
            }
            else
            {
                ans[j - i]++;
            }
        }
    }
    for (int i = 1; i < N; i++)
    {
        cout << ans[i] << endl;
    }
}

int main()
{
    long long N;
    scanf("%lld", &N);
    long long X;
    scanf("%lld", &X);
    long long Y;
    scanf("%lld", &Y);
    solve(N, X, Y);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#define ll long long

using namespace std;
ll n , a[200100] , k;
vector < ll > Positive , Negative;


int main()
{
    cin >> n >> k;
    for(int i = 0;i<n;i++)  {
            cin >> a[i];
            if(a[i] < 0)  Negative.push_back(a[i]);
            else  Positive.push_back(a[i]);
    }
    sort(a , a + n);
    sort(Positive.begin() , Positive.end());
    sort(Negative.begin() , Negative.end());
    ll Start = -1e18 , End = 1e18 , Res = 0;
    while(Start <= End){
        ll mid = (Start + End)/2;
        ll pos = 0;
        for(int i = 0;i<Positive.size();i++){
            int Start2 = i + 1 , End2 = Positive.size() - 1 , idx = i;
            while(Start2 <= End2){
                int mid2 = (Start2 + End2)/2;
                if(Positive[i] * Positive[mid2] <= mid)  idx = mid2 , Start2 = mid2 + 1;
                else  End2 = mid2 - 1;
            }
            pos+=idx - i;
            Start2 = 0 , End2 = Negative.size() - 1 , idx = -1;
            while(Start2 <= End2){
                int mid2 = (Start2 + End2)/2;
                if(Positive[i] * Negative[mid2] <= mid)  idx = mid2 , Start2 = mid2 + 1;
                else  End2 = mid2 - 1;
            }
            pos+=idx + 1;
        }
        for(int i = 0;i<Negative.size();i++){
            int Start2 = i + 1 , End2 = Negative.size() - 1 , idx = i;
            while(Start2 <= End2){
                int mid2 = (Start2 + End2)/2;
                if(Negative[i] * Negative[mid2] > mid)  idx = mid2 , Start2 = mid2 + 1;
                else  End2 = mid2 - 1;
            }
            pos+=Negative.size() - (idx + 1);
        }
        if(pos < k)   Res = mid , Start = mid + 1;
        else  End = mid - 1;
    }
    cout << Res + 1;
    return 0;
}



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

#define int long long
using namespace std;
#define rep(i, n) for(int i=0;i<(n);++i)
typedef pair<int, int> pii;
const int INF = 1l << 60;
#define u_b upper_bound
#define l_b lower_bound

int N;
int A[22];
int B[22];
int C[22];

signed main() {
    cin >> N;
    rep(i, N) {
        cin >> A[i];
    }
    int ans = 0;
    rep(i, N) {
        cin >> B[i];
        ans += B[i];
    }
    rep(i, N - 1) {
        cin >> C[i];
    }
    rep(i, N - 1) {
        if (A[i + 1] == A[i] + 1) {
            ans += C[A[i] - 1];
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
N,M,L = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(M)]
Q = int(input())
ST = [tuple(map(int,input().split())) for i in range(Q)]

INF = float('inf')
ds = [[INF]*N for i in range(N)]
for a,b,c in ABC:
    a,b = a-1,b-1
    ds[a][b] = ds[b][a] = c
for i in range(N):
    ds[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            ds[i][j] = min(ds[i][j], ds[i][k]+ds[k][j])

ls = [[INF]*N for i in range(N)]
for i in range(N-1):
    for j in range(i+1,N):
        if ds[i][j] <= L:
            ls[i][j] = ls[j][i] = 1
for i in range(N):
    ls[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            ls[i][j] = min(ls[i][j], ls[i][k]+ls[k][j])

ans = []
for s,t in ST:
    ans.append(-1 if ls[s-1][t-1]==INF else ls[s-1][t-1] - 1)
print(*ans, sep='\n')

Measured memory_bytes: 99992
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;
 
#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
	#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}
 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mk(arr,n,type)  type *arr=new type[n];
 
clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
int main(){
	int A,B;
	cin >> A >> B;
	cout << A*B << "\n";
	return 0;
}


Measured memory_bytes: 3564
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

#define ll long long

ll bin(ll x, ll n, ll MOD) {
    ll ret = MOD != 1;
    for (x %= MOD; n; n >>= 1, x = x * x % MOD)
        if (n & 1) ret = ret * x % MOD;
    return ret;
}

inline ll get_inv(ll x, ll p) { return bin(x, p - 2, p); }

ll extended_euclid(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    } else {
        ll d = extended_euclid(b, a % b, x, y);
        ll xtemp = x, ytemp = y;
        x = ytemp;
        y = xtemp - (a / b) * ytemp;
        return d;
    }
}

#define maxn 300005
ll invf[maxn], fac[maxn] = {1};
#define mod  998244353

void fac_inv_init(ll n, ll p) {
    for (long long i = 1; i < n; i++) {
        fac[i] = i * fac[i - 1] % p;
    }
    invf[n - 1] = bin(fac[n - 1], p - 2, p);
    for (long long i = n - 2; i > -1; i--)
        invf[i] = invf[i + 1] * (i + 1) % p;

}

inline ll C(ll n, ll m) {
    return n < m || m < 0 ? 0 : fac[n] * invf[m] % mod * invf[n - m] % mod;
}

bool solve(ll a, ll b, ll c, ll &x, ll &y) {
    int n = extended_euclid(a, b, x, y);
    if (c % n) return false;
    int k = c / n;
    x *= k;
    y *= k;
    return true;
}


int main() {
    long long n, a, b, k;
    scanf("%lld%lld%lld%lld", &n, &a, &b, &k);
    long long res = 0;
    fac_inv_init(300005, mod);
    for (long long x = 0; x <= n; x++) {
        if (k - (x * a) >= 0 && (k - (x * a)) % b == 0 && (k - a * x) / b <= n) {
            res = (res + C(n, x) * C(n, (k - a * x) / b) % mod) % mod;
        }
    }
    printf("%lld\n", res);
}


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

using namespace std;

int main(){
    int n;
    string s;
    cin>>n;
    cin>>s;
    if(n%2==0){
        if(s.substr(0,n/2)==s.substr((n/2),n/2)){
        cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }else{
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 256