akhauriyash/Code-Regression huggingface dataset:
n,m=map(int,input().split())

par=[i for i in range(n)]
size=[1]*n

def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def union(a,b):
  x=find(a)
  y=find(b)
  if x!=y:
    if size[x]<size[y]:
      par[x]=par[y]
      size[y]+=size[x]
    else: 
      par[y]=par[x]
      size[x]+=size[y]
  else:
    return

for i in range(m):
    a,b=map(int,input().split())
    union(a-1,b-1)

ans={find(i) for i in range(n)}

print(len(ans)-1)

Measured memory_bytes: 81608
from itertools import combinations_with_replacement
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]

result = 0
for A in combinations_with_replacement(range(1,M+1),N):
    t = 0
    for a,b,c,d in abcd:
        if A[b-1] - A[a-1] == c:
            t += d
    result = max(result,t)
print(result)


Measured memory_bytes: 9220
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
p = []
for i in range(1,11111):
    n = 5*i + 1
    if is_prime(n):
        p.append(str(n))
N = int(input())
ans = p[:N]
print(' '.join(ans))


Measured memory_bytes: 3188
require 'pp'
$DEBUG ? define_method(:dpp){|e|pp e} : define_method(:dpp){|e|}

# 空白区切の入力値を数値の配列で返却する
def gets_i_list()
  gets.chomp.split(" ").map(&:to_i)
end
a, b = gets_i_list

if (a..b).include?(0)
  puts 'Zero'
elsif b < 0 && (b-a).even?
  puts 'Negative'
else
  puts 'Positive'
end

Measured memory_bytes: 2300
import numpy as np
N,M,*A = map(int, open(0).read().split())
A = np.sort(A)
B = np.cumsum(np.concatenate([[0],A[::-1]]))
l = -1
r = 10**6
while l+1<r:
  s = (l+r)//2
  cnt = np.sum(N-np.searchsorted(A,s-A))
  if cnt>=M:
    l = s
  else:
    r = s
ind = np.searchsorted(A,r-A)
M -= np.sum(N-ind)
ans = np.sum(B[N-ind]+A*(N-ind))+M*l
print(ans)


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

int main(){
    int n, k;
    cin >> n >> k;
    int h, cnt = 0;
    for (int i = 0; i < n; i++){
        cin >> h;
        if(h>=k)
            cnt++;
    }
    cout << cnt << endl;
}

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

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

	long long int anser=2020*2020;
    long long int ans;

    for(int i=a;(i<b && i<a+2020);i++){
        for(int j=a+1;(j<=b && j<a+2020);j++){
            ans=((i%2019)*(j%2019))%2019;
            if(ans==0){
                cout << ans <<endl;
                return 0;
            }else{
                if(ans<anser){
                    anser=ans;
                }
            }
        }
        
    }
    cout << anser <<endl;
    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
N=int(sys.stdin.readline().strip())
A=map(int, sys.stdin.readline().split())
C=defaultdict(lambda: 0)
ans=0
for i,a in enumerate(A):
    ans+=C[i-a]
    C[a+i]+=1
print ans


Measured memory_bytes: 144700
n = int(input())
cnt = 0
m = 0
for i in range(n):
  a,b = map(int,input().split())
  if a == b:
    cnt += 1
  else:
    cnt = 0
  m = max(m,cnt)
if m >= 3:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 9172
/*g++ main.cpp -o main.out*/
/*./main.out*/
/*std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);*/

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

#define LL long long
#define Mod 1000000007
#define L_Mod 17100000013

const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const double PI = 3.1415926535;

#define NO_TLE std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define ree(n,a) memset(n,a,sizeof(n));

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define red(i,l,u) for(int (i)=(int)(l);(i)>=(int)(u);--(i))

struct v
{
    int t=0,r;
}a[100005];
int ans=0;
void dfs(int m)
{
    ans++;
    if(m==2)
    {
        return;
    }
    else if(m!=2)
    {
        if(a[m].t==1)
        {
            ans=-1;
            return;
        }
        else if(a[m].t==0)
        {
            a[m].t=1;
            dfs(a[m].r);
        }
    }
    return;
}

int main()
{
    NO_TLE
    int n;
    cin>>n;
    rer(i,1,n)cin>>a[i].r;
    dfs(a[1].r);
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>

unsigned long long int height[100000] = {0};

int dec_sort(const void *a, const void* b)
{
//	printf("%lld %lld\n",*(unsigned long long int*)b , *(unsigned long long int*)a);
	return (int)(*(unsigned long long int*)b - *(unsigned long long int*)a);
}

unsigned long long int get_min(int n, int k)
{
	unsigned long long int min = 1000000000;
	int loop = 0;
	k -= 1;
	for(loop = 0; loop < n - k; loop++) {
//		printf("height=%8d \n",height[loop]);
		if ((height[loop] - height[loop+k]) < min) {
            min = (height[loop] - height[loop+k]);
		}
		if (min == 0) {
			break;
		}
	}
	return min;
}

int main()
{
	int n_num = 0;
	int k_selnum = 0;
	int loop = 0;
    unsigned long long int min = 0;

	scanf("%d %d", &n_num, &k_selnum);
	for(loop = 0; loop < n_num; loop++) {
		scanf("%d", &height[loop]);
	}

	qsort(height, n_num, sizeof(unsigned long long int),dec_sort);
	min = get_min(n_num, k_selnum);
	printf("%d\n", min);
	return 0;
}


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

static class IsItConvex
{
    static void Main()
    {
        Func<double[], double[], double[]> diff =
            (x, y) => new[] { y[0] - x[0], y[1] - x[1] };
        Func<double[], double[], double> cross =
            (x, y) => x[0] * y[1] - x[1] * y[0];
        var input = Console.In.ReadToEnd()
            .Split( 
                new[] { '\r', '\n' },
                StringSplitOptions.RemoveEmptyEntries )
            .Select( x => Array.ConvertAll( x.Split( ',' ), double.Parse ) );
        var q =
            from d in input
            let v = Enumerable.Range( 0, 4 )
                .Select( x => new[] { d[x * 2], d[x * 2 + 1] } )
                .ToArray()
            let c = new[] {
                cross( diff( v[0], v[1] ), diff( v[1], v[2] ) ),
                cross( diff( v[1], v[2] ), diff( v[2], v[3] ) ),
                cross( diff( v[2], v[3] ), diff( v[3], v[0] ) ),
                cross( diff( v[3], v[0] ), diff( v[0], v[1] ) ),
            }
            select c.Where( x => x < 0 ).Any() && c.Where( x => 0 < x ).Any()
                ? "NO" : "YES";
        q.ToList().ForEach( Console.WriteLine );
    }
}

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

int main(){
    
    int N;
    cin >> N;
    vector<int> vec;
    for(int i = 1; i <= N;i++)vec.push_back(i);
    
    int P[N];
    int Q[N];
    for(int i = 0; i < N;i++)cin >> P[i];
    for(int i = 0; i < N;i++)cin >> Q[i];
    
    bool flagP;
    bool flagQ;
    int p = 0;
    int q = 0;
    int cont = 1;
    
    // cout <<"PP";
    // for(int i = 0; i < N;i++)cout << P[i];
    // cout <<endl;
    // cout <<"QQ";
    //  for(int i = 0; i < N;i++)cout << Q[i];
    // cout <<endl;
    
    
    
    
    do {
        
        flagP = true;
        flagQ = true;
        
        for(int i = 0; i < N;i++){
            if(P[i]!=vec[i])flagP = false;
            if(Q[i]!=vec[i])flagQ = false;
        }
        
        if(flagP){
            p = cont;
            // cout <<"P";
            // for(auto u:vec)cout << u;
            // cout <<endl;
        }
        if(flagQ){
            q = cont;
            // cout <<"Q";
            // for(auto u:vec)cout << u;
            // cout <<endl;
        }
        cont++;
        
     } while (next_permutation(vec.begin(), vec.end()));
     
     cout << abs(p-q)<<endl;
}
    
    



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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
	ost<<"{";
	for(int i=0;i<v.size();i++){
		if(i)ost<<",";
		ost<<v[i];
	}
	ost<<"}";
	return ost;
}

inline int topbit(unsigned long long x){
	return x?63-__builtin_clzll(x):-1;
}

inline int popcount(unsigned long long x){
	return __builtin_popcountll(x);
}

inline int parity(unsigned long long x){
	return __builtin_parity(x);
}

signed main(){
	int A,V,B,W,T;
	cin>>A>>V>>B>>W>>T;

	if(V*T>=W*T+abs(A-B))cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0;
}

Measured memory_bytes: 3628
#include <stdio.h>
#define max 25
#define nil -1
typedef struct{
  int prev;
  int right;
  int left;
} node;
void PreorderPrint(int);
void InorderPrint(int);
void PostorderPrint(int);
int n;
node data[max];

int main()
{
  int i, id;

  scanf("%d",&n);

  for(i = 0 ; i < n ; i++) data[i].prev = nil;
  
  for(i = 0 ; i < n ; i++){
    scanf("%d",&id);
    scanf("%d%d",&data[id].left,&data[id].right);
    if(data[id].left != nil){
      data[data[id].left].prev = id; }
    if(data[id].right != nil){
      data[data[id].right].prev = id; }
  } 

  for(i = 0 ; i < n ; i++){
    if(data[i].prev == nil) break; }
  
  printf("Preorder\n");
  PreorderPrint(i);
  printf("\nInorder\n");
  InorderPrint(i);
  printf("\nPostorder\n");
  PostorderPrint(i);
  printf("\n");
  
  return 0;
}

void PreorderPrint(int u)
{
  if(u == nil) return;
  printf(" %d",u);
  PreorderPrint(data[u].left);
  PreorderPrint(data[u].right);
}

void InorderPrint(int u)
{
  if(u == nil) return;
  InorderPrint(data[u].left);
  printf(" %d",u);
  InorderPrint(data[u].right);
}

void PostorderPrint(int u)
{
  if(u == nil) return;
  PostorderPrint(data[u].left);
  PostorderPrint(data[u].right);
  printf(" %d",u);
}



Measured memory_bytes: 2104
x, y, a, b, c = map(int, input().split())
arrayP = list(map(int, input().split()))
arrayQ = list(map(int, input().split()))
arrayR = list(map(int, input().split()))
arrayP.sort(reverse=True)
arrayQ.sort(reverse=True)
arrayR.sort(reverse=True)
arrayAns = []
for i in range(x):
    arrayAns.append(int(arrayP[i]))
for i in range(y):
    arrayAns.append(int(arrayQ[i]))
arrayAns.sort()
for i in range(min(len(arrayR), len(arrayAns))):
    if arrayAns[i] <= int(arrayR[i]):
        arrayAns[i] = int(arrayR[i])
    else:
        break
print(sum(arrayAns))


Measured memory_bytes: 23328
#include <bits/stdc++.h>
#pragma optimize("O2")
#define IOS cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false)
using namespace std;
 
int A[200002];
vector<int> t(400000);
map<int, vector<int>> M;
 
int B[200001];
int main(){
	IOS;
	int n;
	cin >> n;
	int R = n;
	for(int i = 0; i < n; i++){
		cin >> A[i];
		B[A[i]] = i;
	}
	int ans = 0;
	for(int i = 1; i <= n; i++){
		if(R > B[i]){
			R = B[i];
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define LL_MAX LLONG_MAX
#define ULL_MAX ULLONG_MAX
#define ull unsigned long long
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define pb(x) push_back(x)
#define eb(x) emplace_back(x)
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
#define mk make_pair
#define endl '\n'

int main()
{
    IOS;
    string s,t;
    cin>>s>>t;
    if(s.size()+1!=t.size())
    {
        cout<<"No";
        return 0;
    }
    for (int i = 0; i < s.size(); i++)
    {
        if(s[i]!=t[i])
        {
            cout<<"No";
            return 0;
        }
        /* code */
    }
    cout<<"Yes";
}

Measured memory_bytes: 3532
odds = ['R','U','D']
evens = ['L','U','D']

s = input()

fl = 0
for i in range(len(s)):
    if i % 2 == 0:
        if s[i] not in odds:
            fl = 1
            break
    if i % 2 == 1:
        if s[i] not in evens:
            fl = 1
            break

if fl == 0:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
using Graph = vector<vector<ll>>;
using P = pair<int,int>;
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; }
#define MOD 1000000007
#define INF 1000000
#define PI 3.14159265358979323846264338327950L
#define MAX_N 200010
#define lb lower_bound 

int main()
{
  char c;
  cin>>c;
  if ('a'<=c && c<='z') cout<<'a'<<endl;
  else cout<<'A'<<endl;
}

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

char field[1001][1002];
int J[1001][1001], O[1001][1001], I[1001][1001];

int main(void) {
    int M, N, K, i, j, a, b, c, d;

    scanf("%d%d", &M, &N);
    scanf("%d", &K);
    for (i = 0; i <= M; i++) {
        for (j = 0; j <= N; j++) {
            J[i][j] = O[i][j] = I[i][j] = 0;
        }
    }
    for (i = 1; i <= M; i++) {
        scanf("%s\n", &(field[i][1]));
        for (j = 1; j <= N; j++) {
            J[i][j] = J[i][j-1] + J[i-1][j] - J[i-1][j-1];
            O[i][j] = O[i][j-1] + O[i-1][j] - O[i-1][j-1];
            I[i][j] = I[i][j-1] + I[i-1][j] - I[i-1][j-1];
            switch (field[i][j]) {
                case 'J': J[i][j]++; break;
                case 'O': O[i][j]++; break;
                case 'I': I[i][j]++; break;
                default: break;
            }
        }
    }
    for (i = 0; i < K; i++) {
        scanf("%d%d%d%d", &a, &b, &c, &d);
        printf("%d %d %d\n",
               J[c][d] - J[c][b-1] - J[a-1][d] + J[a-1][b-1],
               O[c][d] - O[c][b-1] - O[a-1][d] + O[a-1][b-1],
               I[c][d] - I[c][b-1] - I[a-1][d] + I[a-1][b-1]);
    }
    return 0;
}

Measured memory_bytes: 13268
#include <iostream>
#include <string>
int main()
{
	int a, b;
	std::cin >> a >> b;
	if (a + a - 1 >= a + b && a + a - 1 >= b + b - 1 ) {
		std::cout << a + a - 1 << std::endl;
	}
	else if (a + b >= a + a - 1 && a + b >= b + b - 1) {
		std::cout << a + b << std::endl;
	}
	else { 
		std::cout << b + b - 1 << std::endl;
	}
}





Measured memory_bytes: 256
// A.

#include <iostream>
#include <sstream>
#include <algorithm>

using namespace std;

int main(int argc, char *argv[]) {
	int a, b;
	cin >> a >> b;
	int c = a + b;
	if (c % 2) {
		cout << "IMPOSSIBLE" << endl;
	} else {
		cout << c / 2 << endl;
	}
	return 0;
}


Measured memory_bytes: 256
S=list(map(int,list(input())))
K=int(input())

sum=0
for i in range(0,len(S)):
    if(S[i]==1):
        sum+=1
        if(sum>=K):
                print(S[i])
                exit()
    else:
        tmp=S[i]
        for j in range(2,5000000000000000):
            tmp*=S[i]
            if(sum+tmp>=K):
                print(S[i])
                exit()
            else:
                sum+=tmp



Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp2
{
	class Program
	{
		static void Main(string[] args)
		{
			/*
			レート 1-399：灰色
			レート 400-799：茶色
			レート 800-1199：緑色
			レート 1200-1599：水色
			レート 1600-1999：青色
			レート 2000-2399：黄色
			レート 2400-2799：橙色
			レート 2800-3199：赤色
			*/
			bool[] color = new bool[8];
			for (int i = 0; i < 8; i++) color[i] = false;
			int N = int.Parse(Console.ReadLine());
			int data;
			int cnt = 0;
			var temp = Console.ReadLine().Split(' ');
			for (int i = 0; i < N; i++)
			{
				data = int.Parse(temp[i]);
				if (data < 400) color[0] = true;
				else if (data < 800) color[1] = true;
				else if (data < 1200) color[2] = true;
				else if (data < 1600) color[3] = true;
				else if (data < 2000) color[4] = true;
				else if (data < 2400) color[5] = true;
				else if (data < 2800) color[6] = true;
				else if (data < 3200) color[7] = true;
				else cnt++;
			}
			var app = 0;
			for (int i = 0; i < 8; i++)
			{
				if (color[i])
				{
					app++;
				}
			}
			var min = app;
			var max = app;

			max += cnt;
			min = (min <= 0) ? 1 : min;
			Console.WriteLine(min + " " + max);
		}
	}
}


Measured memory_bytes: 11092
package main

import (
	"fmt"
	"unicode"
)

func main() {
	var s string
	fmt.Scan(&s)
	l := len(s)
	ans := "AC"
	if s[0] != 'A' {
		ans = "WA"
	}
	cnt := 0
	for i := 1; i < l; i++ {
		if unicode.IsUpper(rune(s[i])) {
			if i == 1 || i == l-1 || s[i] != 'C' {
				ans = "WA"
			}
			cnt++
		}
	}
	if cnt != 1 {
		ans = "WA"
	}
	fmt.Println(ans)
}


Measured memory_bytes: 640
n,k=map(int,input().split())
*s,=input()
g=[]
t=1
for i in range(1,n):
    if s[i]==s[i-1]:
        t+=1
    else:
        g.append(t)
        t=1
g.append(t)
for i in range(1,len(g)):
    g[i]+=g[i-1]
g=[0]+g+[g[-1]]
a=0
for i in range(s[0]=='1',len(g),2):
    a=max(a,g[i]-g[max(0,i-2*k-1)])
print(a)

Measured memory_bytes: 9384
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <string.h>
#include<iomanip>
#include <iterator>

#define all(a) a.begin(),a.end()
#define VV(T) vector<vector< T > >
#define rep(i,N) for(int i = 0; i <N; i++)
#define name(x) #x
using namespace std;


const int INF = INT_MAX;
const int MOD = pow(10,9)+7;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

typedef long long ll,LL;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pLL;


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec) is >> x;
    return is;
}
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << ( i+1 == vec.size() ? "" : " " );
    }
    return os;
}

const int MAX_SIZE = 100005;
ll memo[MAX_SIZE];
ll cumSum[MAX_SIZE];
vector<ll> a;
int N,K;


int main() {

    cin >> N >> K;
    a.resize(N+1);
    for(auto i = 1; i<=N; i++) cin >> a[i];
    
    sort(all(a));
    
    for(auto k = 0; k<=a[1]; k++){
        
        memo[k] = 1;
        
    }
    
    for(auto n = 2; n<=N; n++){
        cumSum[0] = 1;
        
        for(auto k = 1; k<=K; k++){
            cumSum[k] = cumSum[k-1] + memo[k];
            cumSum[k]%=MOD;
        }
        
        
        for(auto k = 1; k<=K; k++){
            memo[k] = cumSum[k];
            
            if ( k - a[n]-1 >= 0 ) memo[k] -= cumSum[k-a[n]-1];
            
            if (memo[k] < 0) memo[k] += MOD;
            
            memo[k] %= MOD;
        }
        
        
    }
    
    
    cout << memo[K]%MOD << endl;
    
    
    return 0;
}




Measured memory_bytes: 1792
def main():
    N,M = [int(n) for n in input().split()]
    d = [-1]*N
    for i in range(M):
        s,c = [int(n) for n in input().split()]
        s -= 1
        if d[s] == -1 or d[s] == c:
            d[s] = c
        else:
            print("-1")
            return
    if d[0] == -1 and N != 1:
        d[0] = 1
    elif d[0] == -1 and N == 1:
        print(0)
        return
    for i in range(N):
        if d[i] == -1:
            d[i] = 0
    
    if d[0] == 0 and N != 1:
        print("-1")
    else:
        print("".join([str(n) for n in d]))
main()

Measured memory_bytes: 3064
N = int(input())
time_list = [int(i) for i in input().split()]
M = int(input())
drinked_time_list = []
for i in range(M) :
    drinked_time_list.append([int(i) for i in input().split()])

base_total_time = sum(time_list)
for dr in drinked_time_list :
    base_time = time_list[dr[0]-1]
    print(base_total_time-base_time+dr[1])





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

//const lol mod=1e9+7;

/*  author: H3XoRuSH  */

int main() {
    ios_base::sync_with_stdio(false);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    lol a,b;
    cin >> a >> b;
    if(a>8 || b>8) cout << ":(";
    else cout << "Yay!";
    return 0;
}


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

int main(){
    int n; cin >> n;
    vector<int> lis(n/2), lis2(n/2);
    map<int, int> mp, mp2;
    for(int i = 0; i < n/2; i++){
        cin >> lis[i] >> lis2[i];
    }
    for(int i = 0; i < n/2; i++){
        mp[lis[i]]++;
        mp2[lis2[i]]++;
    }
    int ma = 0, ma2 = 0, aa, bb;
    vector<vector<int> > ch1(n/2, vector<int>(2, 0));
    vector<vector<int> > ch2(n/2, vector<int>(2, 0));
    int i = 0;
    for(auto &x: mp){
        ch1[i][0] = x.second;
        ch1[i][1] = x.first;
        i++;
    }
    i = 0;
    for(auto &x: mp2){
        ch2[i][0] = x.second;
        ch2[i][1] = x.first;
        i++;
    }
    sort(ch1.begin(), ch1.end(), [](auto& x, auto& y){return x[0] > y[0];});
    sort(ch2.begin(), ch2.end(), [](auto& x, auto& y){return x[0] > y[0];});
    if(ch1[0][1] != ch2[0][1]){
        cout << n - ch1[0][0] - ch2[0][0] << endl;
    }else{
        if(ch1.size() > 2 && ch2.size() > 2){
            cout << min(n-ch1[0][0]-ch2[1][0] , n - ch1[1][0] - ch2[0][0]) << endl;
        }else if(ch1.size() > 2){
            cout <<  n - ch1[1][0] - ch2[0][0] << endl;
        }else if(ch2.size() > 2){
            cout <<   n-ch1[0][0]-ch2[1][0] << endl;
        }else{
            cout << min(n-ch1[0][0] , n - ch2[0][0]) << endl;
        }
    }
}

Measured memory_bytes: 10752
def bfs(graph,start,n,check):
    if check == False:
        arrival = [0 for i in range(n+1)]
    else:
        arrival = [0 for i in range(n+1)]
        arrival[check] = -1
    q = [start]
    arrival[start] = 1
    while len(q) != 0:
        for i in range(len(graph[q[0]])):
            if arrival[graph[q[0]][i]] == 0:
                q.append(graph[q[0]][i])
                arrival[graph[q[0]][i]] = arrival[q[0]]+1
        q.pop(0)
    return arrival

n = int(input())
graph = dict()
for i in range(1,n+1):
    graph[i] = []

for i in range(n-1):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)


fstart = bfs(graph,1,n,False)
sstart = bfs(graph,n,n,False)
fennec = 0
snuke = 0
for i in range(1,n+1):
    if abs(fstart[i]-fstart[1]) <= abs(sstart[i]-sstart[n]):
        fennec += 1
    else:
        snuke += 1


if fennec > snuke:
    print("Fennec")
else:
    print("Snuke")

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

using namespace std;

const int N = 500010;

struct Mo{
  int sz;
  vector<int> left,right,order;
  vector<bool> check;
  Mo(int n,int q):sz((int)sqrt(n)),order(q),check(n){}
  void insert(int l, int r){
    left.emplace_back(l);
    right.emplace_back(r);
  }
  template<typename ADD,typename DEL,typename REM>
  void build(const ADD &add,const DEL &del,const REM &rem){
    iota(order.begin(),order.end(),0);
    sort(order.begin(),order.end(),[&](int a,int b){
      return (left[a]/sz!=left[b]/sz?left[a]<left[b]:right[a]<right[b]);
    });
    int l=0,r=0;
    auto push=[&](int idx){
      check[idx].flip();
      if (check[idx]) add(idx);
      else del(idx);
    };
    for (int idx:order){
      while(l>left[idx]) push(--l);
      while(r<right[idx]) push(r++);
      while(l<left[idx]) push(l++);
      while(r>right[idx]) push(--r);
      rem(idx);
    }
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> arr(n);
  for (int i = 0; i < n; ++i) cin >> arr[i];
  Mo mo(n, m);
  for (int i = 0; i < m; ++i) {
    int l, r;
    cin >> l >> r;
    mo.insert(l - 1, r);
  }
  vector<int> cnt(n, 0), ans(m);
  int sum = 0;
  auto add=[&](int idx){if (cnt[arr[idx]]++==0) ++sum;};
  auto del=[&](int idx){if (--cnt[arr[idx]]==0) --sum;};
  auto rem=[&](int idx){ans[idx]=sum;};
  mo.build(add,del,rem);
  for (int i = 0; i < m; ++i) cout << ans[i] << '\n';
}

Measured memory_bytes: 15624
package main
 
import (
	"bufio"
	"fmt"
	"log"
	"os"
	"strconv"
)
 
func run(){
	
	s := next()
	t := next()
	count := 0
	for i := 0; i < 3; i++ {
		if s[i] == t[i] {
			count++
		}
	}
	Println(count)
}
 
// --- template ---
// Thanks https://gist.github.com/halllllll/853ab587fd82ee3ffe6f7fb7fb499695
 
var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)
 
// Caution: You will get unexpected result if a single token is larger than this size.
const BufferSize = 64 * 1024 * 1024
 
func Print(a ...interface{}) (n int, err error) {
	return fmt.Fprint(out, a...)
}
 
func Printf(format string, a ...interface{}) (n int, err error) {
	return fmt.Fprintf(out, format, a...)
}
 
func Println(a ...interface{}) (n int, err error) {
	return fmt.Fprintln(out, a...)
}
 
func next() string {
	sc.Scan()
	return sc.Text()
}
 
func nextInt() int {
	a, err := strconv.Atoi(next())
	if err != nil {
		log.Fatal(err)
	}
	return a
}
 
func nextFloat() float64 {
	a, err := strconv.ParseFloat(next(), 64)
	if err != nil {
		log.Fatal(err)
	}
	return a
}
 
func main() {
	sc.Buffer(make([]byte, 0, BufferSize), BufferSize)
	sc.Split(bufio.ScanWords)
	run()
	out.Flush()
}

Measured memory_bytes: 2816
import Data.List
import Data.Ord
import Data.Char
import Data.Ratio
import Data.Maybe

main = do
    _ <- getLine
    str <- words <$>getLine
    let card = reverse $sort $map read str 
    let aliceScore = alice card
    let totalScore = sum card
    print (aliceScore*2 - totalScore)

alice [] = 0
alice [x] = x
alice (x1:_:xs) = x1 + alice xs


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

int main() {
	int K;
	int A, B;
	cin >> K;
	cin >> A >> B;

	if (K == 1) {
		cout << "OK" << endl;
		return 0;
	}

	int x = 0;
	while (1) {
		x += K;
		if (x >= A) {
			if (x <= B) {
				cout << "OK" << endl;
				return 0;
			} else {
				break;
			}
		}
	}
	cout << "NG" << endl;

	return 0;
}

Measured memory_bytes: 3616
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
using namespace std;

template<class T>
void in(vector<T>& V) {
	for (auto itr = V.begin(); itr != V.end(); itr++)cin >> *itr;
	return;
}

template<class T>
void out(vector<T>& V) {
	for (T& itr : V)cout << itr << endl;
	return;
}

string S, T;
vector<vector<int>> DP;

string recover(int s,int t) {
	if (s == 0 || t == 0)return string("");
	if (S[s - 1] == T[t - 1])return recover(s - 1, t - 1) + S.substr(s - 1, 1);
	else if (DP[s - 1][t] < DP[s][t - 1])return recover(s, t - 1);
	else return recover(s - 1, t);
}

int main() {
	cin >> S >> T;
	DP.resize(S.size() + 1, vector<int>(T.size() + 1, 0));
	for (int t = 1; t <= T.size(); t++) {
		for (int s = 1; s <= S.size(); s++) {
			if (S[s - 1] == T[t - 1]) DP[s][t] = DP[s - 1][t - 1]+1;
			else {
				if (DP[s - 1][t] < DP[s][t - 1])DP[s][t] = DP[s][t - 1];
				else DP[s][t] = DP[s - 1][t];
			}
		}
	}
	cout << recover(S.size(), T.size()) << endl;
	return 0;
}

Measured memory_bytes: 36096
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
int main()
{
  int A, B;
  cin >> A >> B;
  rep(i, 1001) {
    if (int(i * 0.08) == A and int(i * 0.1) == B) {
      cout << i << endl;
      return (0);
    }
  }
  cout << -1 << endl;
}

Measured memory_bytes: 384
/*s1190073  Rina Sato
  File name: prog9c.c
  This is priority queue program.
*/

#include <stdio.h>
#include <stdlib.h>

#define MAX 2000003

int A[MAX];
int heap_size=0;

int Parent(int i){
  return i/2;
}
int Left(int i){
  return 2*i;
}
int Right(int i){
  return 2*i+1;
}

void maxHeapify(int i){
  int l,r,largest;
  int temp;
  
  l = Left(i);
  r = Right(i);
  
  
  if((l <= heap_size) && (A[l] > A[i])){
    largest = l;
  }
  else {
    largest = i;
  }
  
  if((r <= heap_size) && (A[r] > A[largest])){
    largest = r;
  } 
  
  if(largest != i){
    temp = A[i];
    A[i] = A[largest];
    A[largest] = temp;
    
    maxHeapify(largest);
  } 
}

int heapExtractMax(void){
  int max,j;
  if(heap_size < 1){
    return -20;
  }
  max = A[1];
  A[1] = A[heap_size];
  heap_size = heap_size-1;

  maxHeapify(1);
  
  return max;
}

void heapIncreaseKey(int i,int key){
  int temp;
  if(key < A[i]){
    printf("error\n");
    exit(1);
  }
  
  A[i] = key;
  
  while((i > 1) && (A[Parent(i)] < A[i])){
    temp = A[i];
    A[i] = A[Parent(i)];
    A[Parent(i)] = temp;

    i = Parent(i);
  }
}

void maxHeapInsert(int key){
  heap_size = heap_size+1;
  A[heap_size] = -1000000000;
  heapIncreaseKey(heap_size,key);
}

int main(void){
  int i=1,j=0,max,a;
  char com[20];
  
  while(1){
    scanf("%s",com);  
    if(com[0] == 'i'){
      scanf("%d",&a);
      maxHeapInsert(a);
    }
    
    else if(com[0] == 'e' && com[1] == 'x'){
      max = heapExtractMax();
      if(max == -20){
	exit(0);
      }
      printf("%d\n",max);
    }
    else {
      break;
    }
  }
  
  return 0;
}

Measured memory_bytes: 4328
import math
import string

def intinput():
    return int(input())

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

def splitintinput():
    return map(int,input().split())

N = intinput()
K = intinput()
ans = 1
for i in range(N):
    if ans < K:
        ans *= 2
    else:
        ans += K

print(ans)


Measured memory_bytes: 3956
#include <iostream>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int maxn = 210000, maxk = 20;
int x[maxn];
vi w;
int fw[maxn][maxk], fb[maxn][maxk];
int jfw[1 << maxk], jfb[1 << maxk];
int dans[maxn];

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

    int n, v;
    cin >> n >> v;
    forn(i, n) cin >> x[i];
    w.pb(v);
    while (w.back()) {
        int z = w.back();
        w.pb(z / 2);
    }
    reverse(all(w));
    int k = w.size();
    ford(i, n) forn(j, k) {
        if (i + 1 < n && x[i + 1] - x[i] <= w[j]) fw[i][j] = fw[i + 1][j];
        else fw[i][j] = i;
    }

    forn(i, n) forn(j, k) {
        if (i && x[i] - x[i - 1] <= w[j]) fb[i][j] = fb[i - 1][j];
        else fb[i][j] = i;
    }

    forn(i, 1 << k) jfw[i] = -1, jfb[i] = n;
    jfw[0] = 0;
    jfb[0] = n - 1;
    forn(i, 1 << k) {
        forn(j, k) {
            if ((i >> j) & 1) continue;
            if (jfw[i] >= 0) {
                if (jfw[i] < n) uax(jfw[i | (1 << j)], fw[jfw[i]][j] + 1);
                else jfw[i | (1 << j)] = n;
                if (jfw[27] >= 0) {
                    jfw[27] ^= 0;
                }
            }
            if (jfb[i] < n) {
                if (jfb[i] >= 0) uin(jfb[i | (1 << j)], fb[jfb[i]][j] - 1);
                else jfb[i | (1 << j)] = -1;
            }
        }
    }

    forn(i, 1 << (k - 1)) {
        int l = jfw[i], r = jfb[(1 << (k - 1)) - i - 1];
        if (l > r) {
//            cerr << i << "!\n";
            ++dans[0];
        } else if (fw[l][k - 1] >= r) {
//            cerr << i << ' ' << l << ' ' << r << '\n';
            ++dans[l];
            --dans[r + 1];
        }
    }
    forn(i, n - 1) dans[i + 1] += dans[i];
    forn(i, n) cout << (dans[i] ? "Possible" : "Impossible") << '\n';
}


Measured memory_bytes: 44160
s = list(input())

a = [chr(i) for i in range(97, 97+26)]
A = [chr(i) for i in range(65, 65+26)]

flg = "AC"

if not s[0] == "A":
    flg = "WA"

if not s[2:-1].count("C") ==1:
    flg = "WA"

b = set(s)-set(["A","C"])

if not b<=set(a):
    flg = "WA"

print(flg)

Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
#define ll           long long
#define all(v)       (v).begin() , (v).end()
#define vi           vector <ll>
#define vii          vector <pair<ll,ll>>
#define ii           pair<ll,ll>
#define sz(v)	     ((int)((v).size()))
#define lp(i,a,b)    for(int i=a;i<b;i++)
#define pb           push_back
#define pf           push_front
#define F            first
#define S            second
#define endl         "\n"
#define IOS          ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const double PI = 3.14159265358979323846;
const ll inf=1e18,MOD=1e8+7,MAX=1e3+5;


int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    IOS
    int x;
    cin>>x;
    cout<<!x;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

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

int main() {
	int n; scanf("%d", &n);
	std::vector<i64> x(n), y(n);
	std::vector<std::pair<long double, int>> vec;
	for(int i = 0; i < n; i++) {
		scanf("%lld%lld", &x[i], &y[i]);

		auto theta = atan2((long double)y[i], (long double)x[i]);
		vec.push_back({theta, i});
	}
	sort(begin(vec), end(vec));

	i64 ans = 0;
	for(int i = 0; i < n; i++) {
		i64 X = 0, Y = 0;
		for(int j = 0; j < n; j++) {
			int p = vec[(i + j) % n].second;
			X += x[p];
			Y += y[p];
			ans = std::max(ans, X * X + Y * Y);
		}
	}
	printf("%.32Lf\n", std::sqrt((long double)ans));
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
// #include <atcoder/all>
#define ll long long int
#define ld long double
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i, n) for (ll i = 1; i < (ll)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
// using namespace atcoder;
void Main()
{
    string S;
    cin >> S;

    vector<vector<ll> > dp(S.size() + 1, vector<ll>(4));
    dp[0][0] = 1;

    ll mod = 7LL + 1e9;
    rep(i, S.size()) {
        rep(j, 4) {
            if (S[i] == '?') dp[i+1][j] += (3 * dp[i][j]) % mod;
            else dp[i+1][j] += dp[i][j];
            dp[i+1][j] %= mod;
        }

        if (S[i] == 'A' || S[i] == '?') dp[i+1][1] += dp[i][0];
        if (S[i] == 'B' || S[i] == '?') dp[i+1][2] += dp[i][1];
        if (S[i] == 'C' || S[i] == '?') dp[i+1][3] += dp[i][2];

        rep(j, 4) {
            dp[i+1][j] %= mod;
        }
    }

    put(dp[S.size()][3]);
}
signed main(){ Main();return 0;}

Measured memory_bytes: 10344
#include <algorithm>
#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<set>
#include<string>
#include <sstream>
#include<bitset>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>
const int INF = 0x7fffffff;
using lll = long long;
using ull = unsigned long long;
using namespace std;


int main(){
  lll ii,jj,kk;
  vector<int> p;
  int n,k;

  cin >> n >> k;

  p.resize(n);

  for(ii=0;ii<n;ii++){
    cin >>p[ii] ;
  }

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

  int sum = 0;

  for(ii=0;ii<k;ii++){
    sum += p[ii];
  }

  cout << sum << endl;
  
  return 0;
}


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

int main(){
  int N;
  cin >> N;
  
  int A = 0;
  int B = 0;
  
  vector<int> cards(N);
  for (int i = 0; i < N; i++){
    cin >> cards.at(i);
  }
  
  int a = 0;
  int b = 0;
  
  for (int i = 0; i < N; i++){
    a = -1;
    b = -1;
    for (int j = 0; j < N; j++){
      if (cards.at(j) > a){
        a = cards.at(j);
        b = j;
      }
    }
    
    if (i % 2 != 1){
      A += a;
    }
    else{
      B += a;
    }
    cards.at(b) = 0;
  }
  
  cout << A - B << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
using namespace std;
pair<int,pair<int,int> > edge[10000];
int UF[100];
int FIND(int a){
	if(UF[a]<0)return a;
	return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
	a=FIND(a);
	b=FIND(b);
	if(a==b)return;
	UF[a]+=UF[b];
	UF[b]=a;
}
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a+b){
		for(int i=0;i<a;i++)UF[i]=-1;
		for(int i=0;i<b;i++){
			int c,d,e;
			scanf("%d%d%d",&c,&d,&e);
			edge[i]=make_pair(e,make_pair(c-1,d-1));
		}
		std::sort(edge,edge+b);
		int ret=99999999;
		for(int i=0;i<b;i++){
			for(int j=0;j<a;j++)UF[j]=-1;
			int com=0;
			int last=-1;
			for(int j=i;j<b;j++){
				if(FIND(edge[j].second.first)!=FIND(edge[j].second.second)){
					UNION(edge[j].second.first,edge[j].second.second);
					last=edge[j].first;
					com++;
				}
				if(com==a-1)break;
			}
			if(com==a-1){
				ret=min(ret,last-edge[i].first);
			//	printf("%d %d\n",edge[i].first,last);
			}
		}
		if(ret==99999999){
			printf("-1\n");
		}else printf("%d\n",ret);
	}
}

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

#define int long long
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define vcopy(v1,v2) copy((v1).begin(), (v1).end(), back_inserter((v2)));
#define pb(n) push_back(n);

int a,b,x;

main() {
    cin >> a >> b  >> x;
    if (a+b < x || a>x) ct("NO")
    else ct("YES")
}






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

int main(){
  int h,w,k;
  cin >> h >> w >> k;
  vector<string> v(h);
  r(i,h)cin >> v[i];
  vector<vector<int>> ans(h,vector<int>(w,0));
  int id=1;
  r(i,h){
    r(j,w){
      if(v[i][j]=='#'){
        ans[i][j]=id;
      id++;
      }
    }
  }
  
  r(i,h){
    r(j,w){
      if(j&&ans[i][j]==0)ans[i][j]=ans[i][j-1];
    }
  }
  r(i,h){
    for(int j=w-2;j>=0;j--)if(ans[i][j]==0)ans[i][j]=ans[i][j+1];
  }
  r(i,w){
    r(j,h){
      if(j&&ans[j][i]==0)ans[j][i]=ans[j-1][i];
    }
  }
  r(i,w){
    for(int j=h-2;j>=0;j--)if(ans[j][i]==0)ans[j][i]=ans[j+1][i];
  }
  r(i,h){
    r(j,w){
      cout<<ans[i][j]<<" ";
    }
    cout<<endl;
  }
}

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

#define rep(i, N) for (int i = 0; i < (N); i++)
#define all(a) (a).begin(), (a).end()
#define pb push_back

using ll = long long;
using i_i = tuple<int, int>;

int f(vector<vector<int>>& sum, int yl, int yr, int xl, int xr) {
    return sum[yr][xr] - sum[yl][xr] - sum[yr][xl] + sum[yl][xl];
}

int main() {
	int N, D;
    cin >> N >> D;
    vector<vector<int>> a(D, vector<int>(D));
    while (N--) {
        int y, x; scanf("%d%d", &y, &x);
        a[y % D][x % D]++;
    }
    int mi = INT_MAX, ma = INT_MIN;
    rep(y, D) rep(x, D) {
        mi = min(mi, a[y][x]);
        ma = max(ma, a[y][x]);
    }
    int lb = 0, ub = 1e6;
    while (ub - lb > 1) {
        int mid = (lb + ub) / 2;
        int k = mid / D, d = mid % D;
        ll z1 = (ll)k * k, z2 = (ll)k * (k + 1), z3 = (ll)(k + 1) * (k + 1);
        if (ma <= z1) {
            ub = mid;
            continue;
        }
        if (ma > z3) {
            lb = mid;
            continue;
        }
        vector<vector<int>> sum3(D * 2 + 1, vector<int>(D * 2 + 1));
        vector<vector<int>> sum2(D * 2 + 1, vector<int>(D * 2 + 1));
        rep(y, D * 2) rep(x, D * 2) {
            int z = a[y % D][x % D];
            sum3[y + 1][x + 1] = sum3[y + 1][x] + sum3[y][x + 1] - sum3[y][x] + (z > z2);
            sum2[y + 1][x + 1] = sum2[y + 1][x] + sum2[y][x + 1] - sum2[y][x] + (z > z1);
        }
        bool ok = false;
        rep(y, D) rep(x, D) {
            if (f(sum3, y, y + d, x, x + d) == sum3[D][D])
                if (f(sum2, y, y + d, 0, D) + f(sum2, 0, D, x, x + d) - f(sum2, y, y + d, x, x + d) == sum2[D][D])
                    ok = true;
        }
        if (ok) ub = mid;
        else lb = mid;
    }
    cout << ub - 1 << endl;
}


Measured memory_bytes: 35680
#include <iostream>
#include <stack>

using namespace std;

struct Rectangle {int height, pos;};

int main() {
  int h, w;
  cin >> h >> w;
  int C[w][h], R[w+1][h];
  for (int j = 0; j < h; j++) {
      for (int i = 0; i < w; i++) {
      cin >> C[i][j];
    }
  }
  for (int j = 0; j < h; j++) {
    for (int i = 0; i < w; i++) {
      if (!j) {
        R[i][j] = (C[i][j]+1) % 2;
      } else {
        R[i][j] = (!C[i][j] ? R[i][j-1] + 1: 0);
      }
    }
    R[w][j] = 0;
  }
  int max_area = 0;
  for (int j = 0; j < h; j++) {
    stack<Rectangle> s;
    for (int i = 0; i <= w; i++) {
      Rectangle rect;
      rect.height = R[i][j];
      rect.pos = i;
      if (s.empty()) {
        s.push(rect);
      } else {
        if (s.top().height < rect.height) {
          s.push(rect);
        } else if (s.top().height > rect.height) {
          int target = rect.pos;
          while (!s.empty() && s.top().height >= rect.height) {
            Rectangle pre_rect = s.top(); s.pop();
            max_area = max(max_area, pre_rect.height * (i - pre_rect.pos));
            target = pre_rect.pos;
          }
          rect.pos = target;
          s.push(rect);
        }
      }
    }
  }
  cout << max_area << endl;
  return 0;
}



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

#define ed cout<<"\n";
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long 
#define ffor(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(i, n) ffor(i,0,n)
#define All(obj) (obj).begin(),(obj).end()
#define INF ((ll)1e9+7)
#define c(a) cout<<a<<"\n";
using namespace std;
const int N = 100005;



int main() {
	speed;
	cout << fixed << setprecision(6);
	/*start*/
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	if (a + b > c + d) {
		c("Left");
	}
	else if (a + b == c + d) {
		c("Balanced");
	}
	else c("Right");
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define test() ll t;cin>>t;while(t--)
#define MOD 1000000007
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
string max(string a,string b){
	return a.length()>b.length()?a:b;
}
int main() {
    SPEED;
    //CODE
	string s,t;
	cin>>s>>t;
	ll m=s.length(),n=t.length();
	string dp[2][n+1];
	dp[0][0]="";
	for(ll i=0;i<=m;i++){
		for(ll j=0;j<=n;j++){
			if(j==0){
				dp[1][j]="";
			}
			else{
				if(s[i-1]==t[j-1]){
					dp[1][j]=dp[0][j-1]+s[i-1];
				}
				else{
					dp[1][j]=max(dp[0][j],dp[1][j-1]);
				}
			}
		}
		for(ll j=0;j<=n;j++){
			dp[0][j]=dp[1][j];
		}
	}
	cout<<dp[1][n];
	return 0;
}


Measured memory_bytes: 16888
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)

ll mod = 1e9 + 7;

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

  ll n;
  cin >> n;
  ll p[n], rec[n];
  REP(i, n){
    cin >> p[i];
    rec[p[i] - 1] = i + 1;
  }

  ll a[n], b[n], s[n];
  REP(i, n){
    a[i] = i * 40000 + rec[i];
    b[i] = (n - i) * 40000;
  }

  REP(i, n) cout << a[i] << " ";
  cout << endl;
  REP(i, n) cout << b[i] << " ";
  cout << endl;

  return 0;
}


Measured memory_bytes: 1280
from itertools import accumulate
# Eratosthenes
def eratosthenes(n):
    prime_table = [False,False,True]+[False if i%2!=0 else True for i in range(n-2)]
    i=3
    while i*i<=n:
        if prime_table[i]:
            j=i*i
            while j<=n:
                prime_table[j]=False
                j+=i
        i+=2
    return prime_table

pt=eratosthenes(100000)
ok=[0 for i in range(100000)]
i=1
while i<100000:
    if pt[i] and pt[(i+1)//2]:
        ok[i]=1
    i+=2
ok=list(accumulate(ok))

q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(ok[r]-ok[l-1])
    


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

int main(){
    ll n,count=0,mem,minimum;
    cin >> n;
    cin >> minimum;
    count ++;
    for(int i=0;i<n-1;i++){
        cin >> mem;
        if(mem<minimum){
            count++;
            minimum=mem;
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 256
a, b, h, m = map(int, input().split())

import math
h = h % 12
m = m % 60
theta = m / 60 * 2 * math.pi
theta2 = (h / 12 + m / 12 / 60) * 2 * math.pi
# print(theta, theta2)

sa = abs(theta - theta2)

if sa >= math.pi:
    sa = 2 * math.pi - sa

ans = math.sqrt(a**2 + b**2 - 2*b*a*math.cos(sa))
print(ans)

Measured memory_bytes: 9396