akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)	
#define show1d(v) rep(i,v.size())cout<<" "<<v[i];cout<<endl;
#define show2d(v) rep(i,v.size()){rep(j,v[i].size())cout<<" "<<v[i][j];cout<<endl;}cout<<endl;
using namespace std;
typedef long long ll;
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<string> vs;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
Def inf = sizeof(Def) == sizeof(ll) ? 2e18 : 1e9+10;
vvi G,in,t;
int n,m,N;
bool h;
vvi data;
void dfs(int x,int y,int d,int c){
//	data[c][0]=min(data[c][0],y);
//	data[c][1]=max(data[c][1],y);
	data[c][2]+=y;
	data[c][3]++;
	
	t[x][y]=c;
	in[x][y]=-1;
	rep(i,4){
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx<0||ny<0||nx>=n||ny>=m)continue;
		if(in[nx][ny]==d){
			dfs(nx,ny,d,c);
		}
	}
}
pii dfs2(int a){
	int sum=data[a][2],co=data[a][3];
	rep(i,N)if(G[a][i]){
		pii tmp=dfs2(i);
		sum+=tmp.first;
		co+=tmp.second;
	}
	//  sum/co
//	cout<<sum<<" "<<co<<endl;
	if(!((2*data[a][0]-1)*co<2*sum&&2*sum<(2*data[a][1]+1)*co))h=false;
	return {sum,co};
}
int main(){
	while(cin>>m>>n,n){
		in=vvi(n,vi(m));
		data=vvi(0);
		rep(i,n)rep(j,m){
			char c;
			cin>>c;
			if(c=='.')in[i][j]=-1;
			else in[i][j]=c-'0';
		}
		t=in;
		int c=0;
		rep(i,n)rep(j,m)if(in[i][j]+1){
			data.pb({inf,-inf,0,0});
			dfs(i,j,in[i][j],c++);
		}
//		show2d(t);
		N=data.size();
		G=vvi(N,vi(N));
		rep(i,n-1)rep(j,m){
			int x=i+1,y=j;
			if(t[i][j]+1&&t[x][y]+1&&t[i][j]!=t[x][y]){
				G[t[x][y]][t[i][j]]=1;
				data[t[i][j]][0]=min(data[t[i][j]][0],j);
				data[t[i][j]][1]=max(data[t[i][j]][1],j);
			}
		}
		rep(i,m)if(t[n-1][i]+1){
			data[t[n-1][i]][0]=min(data[t[n-1][i]][0],i);
			data[t[n-1][i]][1]=max(data[t[n-1][i]][1],i);
		}
//		show2d(G);
		h=true;
		rep(i,N){
			dfs2(i);
		}
		if(h)cout<<"STABLE"<<endl;
		else cout<<"UNSTABLE"<<endl;
	}
}











Measured memory_bytes: 3164
def main():
	n, m =  map(int , input().split())
	ab = []
	for i in range(0 , n):
		ab.append(list(map(int , input().split())))
	ab.sort()
	ans = 0
	for i in range(0 , n):
		if (m-ab[i][1]>=0):
			m = m-ab[i][1]
			ans = ans+(ab[i][0]*ab[i][1])
		elif(m>0):
			ans = ans+(m*ab[i][0])
			m  = 0
	print(ans)
if __name__ =="__main__":
	main()

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

if n%2==0:
    lis=[[i,n+1-i] for i in range(1,int(n/2)+1)]
else:
    lis=[[i,n-i] for i in range(1,int((n-1)/2)+1)] + [[n]]

connect_lis=[]

for i in lis:
    for j in i:
        for k in lis:
            if k!=i:
                for p in k:
                    if j < p:
                        connect_lis.append([j,p])
        
print(len(connect_lis))
for i in connect_lis:
    print(i[0],i[1])

Measured memory_bytes: 4124
import qualified Data.ByteString.Char8 as BS
import Control.Monad
import Data.List
import Data.Array.ST
import Data.Array (elems)
import Data.Maybe (fromJust)


solve :: [[Int]] -> Int -> Int -> Int
solve (x:xs) k count
    | count + b >= k = a
    | otherwise = solve xs k (count + b)
    where
        (a:b:_) = x

sortByNumber :: [Int] -> [Int] -> Ordering
sortByNumber (a:_) (b:_)
    | a >= b = GT
    | otherwise = LT

main :: IO ()
main = do
    [n, k] <- map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine
    arr <- replicateM n (map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine)
    let arr2 = sortBy sortByNumber arr
    print $ solve arr2 k 0



Measured memory_bytes: 65916
#include<bits/stdc++.h>
using namespace std;
int a[4];
int main()
{
	int s5=0;
	int s7=0;
	for(int i=0;i<3;i++)
	{
		cin>>a[i];
		if(a[i]==5)s5++;
		if(a[i]==7)s7++;
	}
	if(s5==2&&s7==1)
	{
		cout<<"YES"<<endl;
		return 0;
	}
	else
	{
		cout<<"NO"<<endl;
		return 0;
	}
	return 0;
}

Measured memory_bytes: 256
let acc_ab n s =
  snd @@ Array.fold_left (fun (c, n) c' ->
    (c', n + if c = 'A' && c' = 'B' then 1 else 0)) ('_', n) @@
  Array.init (String.length s) (String.get s)

let () = Scanf.scanf "%d\n" @@ fun n ->
  let ss = Array.init n @@ fun _ -> Scanf.scanf "%s\n" @@ fun s -> s in
  let (a, b, ba) =
    Array.fold_left (fun (a, b, ba) s ->
      if s.[0] = 'B' && s.[String.length s - 1] = 'A' then (a, b, ba + 1)
      else if s.[0] = 'B' then (a, b + 1, ba)
      else if s.[String.length s - 1] = 'A' then (a + 1, b, ba)
      else (a, b, ba)) (0, 0, 0) ss in
  let n = min a @@ min b ba in
  Printf.printf "%d\n" @@
  Array.fold_left acc_ab 0 ss +
  if a <= 0 && b <= 0 then max 0 (ba - 1) else ba + min a b

Measured memory_bytes: 4864
def resolve():
    '''
    code here
    '''
    import collections
    H, W = [int(item) for item in input().split()]

    grid = [[item for item in input()] for _ in range(H)]

    cnt = 0
    for line in  grid:
        for i in line:
            if i == '#':
                cnt += 1

    if cnt > H + W -1:
        print('Impossible')
    else:
        print('Possible')

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  string s;
  cin >> s;
  int n = s.size(), nine = 0;
  rep(i, 1, n) if (s[i] == '9') nine++;
  if (n - 1 == nine)
    cout << (s[0] - '0') + (n - 1) * 9 << endl;
  else
    cout << (s[0] - '0') - 1 + (n - 1) * 9 << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<set>
using ll = long long;
using namespace std;
int main(){
    ll n,a;
    set<ll> s;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a;
        if(s.find(a)==s.end())  s.insert(a);
        else    s.erase(a);
    }
    cout << s.size() << endl;
    return 0;
}

Measured memory_bytes: 4864
#include <cstdio>
#include <iostream>
#include <map>
using namespace std;

#define mod 1000000007

map<int, long long> ma;

void add(int t){
  if (ma.find(t) != ma.end()) {
    ma[t]++;
  } else ma.insert(make_pair(t, 1));
}

int main(){
  int n; cin >> n;
  for (int ni = 1; ni <= n; ni++) {
    int i = ni;
    for (int j = 2; i != 1 && j <= i; j++) {
      while (i % j == 0) {
        add(j);
        i /= j;
      }
    }
  }
  long long ans = 1;
  for (map<int, long long>::iterator it = ma.begin(); it != ma.end(); it++) {
    ans *= it->second + 1;
    ans %= mod;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define f first
#define s second
#define int long long int
const int N=1000000007;
main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	multiset<int>se;
	int n, k;
	cin>>n>>k;
	vector<int>pos;
	vector<int>neg;
	vector<int>zero;
	int numc=1;
	for(int i=0; i<n; i++){
		int x;
		cin>>x;
		numc=(numc*x)%N;
		numc=(numc+N)%N;
		if(x==0){
			zero.pb(0);
		}
		else if(x>0){
			pos.pb(x);
		}
		else{
			neg.pb(abs(x));
		}
	}
	if(n==k){
		cout<<numc;
		return 0;
	}
	if(n-k<zero.size()){
		cout<<0;
		return 0;
	}
	if(pos.size()==0 && k%2==1){
		if(zero.size()>0){
			cout<<0;
			return 0;
		}
		sort(neg.begin(), neg.end());
		int num=1;
		for(int i=0; i<k; i++){
			num=(num*neg[i])%N;
		}
		num=(N-num)%N;
		cout<<num;
		return 0;
	}
	if(pos.size()==0 && k%2==0){
		sort(neg.begin(), neg.end());
		reverse(neg.begin(), neg.end());
		int num=1;
		for(int i=0; i<k; i++){
			num=(num*neg[i])%N;
		}
		cout<<num;
		return 0;
	}
	sort(neg.begin(), neg.end());
	sort(pos.begin(), pos.end());
	reverse(neg.begin(), neg.end());
	reverse(pos.begin(), pos.end());
	int maxi=0;
	
	for(int i=2; i<=k; i=i+2){
		
		if(neg.size()<i){
			break;
		}
		else{
			maxi=i;
		}
	}
	
	int rem=k-maxi;
	int pt1=rem-1;
	int pt2=maxi-1;
	
	int ma=pt1;
	while(1){
		if(pt1+2<pos.size() && pt2-2>=-1 && pos[pt1+1]*pos[pt1+2]>neg[pt2-1]*neg[pt2]){
			pt2=pt2-2;
			pt1=pt1+2;
		}
		else{
			ma=pt1;
			break;
		}
	}
	
	int ans=1;
	for(int i=0; i<=pt1; i++){
		ans=(ans*pos[i])%N;
	}
	if(pt2==-1){
		cout<<ans;
		return 0;
	}
	for(int i=0; i<=pt2; i++){
		ans=(ans*neg[i])%N;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 5564
#include<bits/stdc++.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (b < a) { a = b; return 1; } return 0; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
int main() {
	long long dp[100010][3];
	long long a[100010][3];
	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				if (j == k) continue;
				chmax(dp[i+1][k], dp[i][j] + a[i][k]);
			}
		}
	}
	long long  ans = 0;
	for (int i = 0; i<3; i++) {
		chmax(ans, dp[N][i]);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4992
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();

        if (n%2 != 0) {
            System.out.println("No");
            return;
        }
        
        int half = n / 2;
        String t1 = s.substring(0, half);
        String t2 = s.substring(half, n);
        
        if(t1.equals(t2)){
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 23764
n, m = map(int, input().split())
*x, = map(int, input().split())
*y, = map(int, input().split())

acx = [0]*(n)
acy = [0]*(m)
acx2 = [0]*(n)
acy2 = [0]*(m)
MOD = 10**9+7

for i in range(1, n):
    acx2[i] = acx2[i-1]+i*(x[i]-x[i-1])
    acx2[i] %= MOD
for i in range(1, m):
    acy2[i] = acy2[i-1]+i*(y[i]-y[i-1])
    acy2[i] %= MOD

for i in range(1, n):
    acx[i] = (acx[i-1]+acx2[i])%MOD
for i in range(1, m):
    acy[i] = (acy[i-1]+acy2[i])%MOD

print(acx[-1]*acy[-1]%MOD)

Measured memory_bytes: 90144
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(' ').map { it.toInt() }.sorted()
    val b = readLine()!!.split(' ').map { it.toInt() }
    val c = readLine()!!.split(' ').map { it.toInt() }.sortedDescending()

    var ans = 0L
    for (i in (0 until n)) {
        val x = a.binarySearch { if (it >= b[i]) 1 else -1 }
        val y = c.binarySearch { if (it <= b[i]) 1 else -1 }
        ans += (-x - 1).toLong() * (-y - 1).toLong()
    }
    println(ans)
}

Measured memory_bytes: 110548
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
using ll = long long;
using P = pair<ll,ll>;

int main(){
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
ll n,d;
cin >> n >> d;
vector<P> xy(n);
rep(i,n){
    cin >> xy[i].first >> xy[i].second;
}
d *= d;
ll ans = 0;
rep(i,n){
    if(xy[i].first * xy[i].first + xy[i].second * xy[i].second <= d)
        ans++;
}
cout << ans << endl;
}

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

int main() {
  int N, M, count = 0;
  cin >> N;
  M = N * 3;
  vector<int> vec(M);
  for (int i = 0; i < M; i++) {
    cin >> vec.at(i);
  }
  sort(vec.rbegin(),vec.rend());
  
  long long sum = 0;
  int i = 1;
  while (count < N) {
    sum += vec.at(i);
    i += 2;
    count++;
  }
  
  cout << sum << endl;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
  ll n;
  cin>>n;
  ll ar[n];
  for(ll i=0;i<n;++i){cin>>ar[i];}
  ll dp[n+1];
  dp[0]=0;dp[1]=0;
  dp[2]=abs(ar[1]-ar[0]);
  for(ll i=3;i<n+1;++i)
  {
    dp[i]=min(dp[i-1]+abs(ar[i-1]-ar[i-2]),dp[i-2]+abs(ar[i-1]-ar[i-3]));
  }
  cout<<dp[n];
}


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

dict = {}
L = []

for i in range(N):
  s = input()
  if s in dict:
    dict[s] = dict[s] + 1
  else:
    dict[s]=1
    L.append(s)

L.sort()

M = 0
for i in dict:
  M = max(M, dict[i])

for i in L:
  if dict[i] == M:
    print(i)

Measured memory_bytes: 97240
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define rrep(i, a, b) for (int i = a; i >= (b); i--)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <class T>
inline bool chmin(T& a, T b) {
   if (a > b) {
      a = b;
      return true;
   }
   return false;
}
template <class T>
inline bool chmax(T& a, T b) {
   if (a < b) {
      a = b;
      return true;
   }
   return false;
}
void hr() {
   cerr << "--------------" << endl;
}
const int INF = 1001001001;
const int MOD = 1000000007;

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

   int n, m;
   cin >> n >> m;
   vector<int> a(n);
   rep(i, 0, m) cin >> a[i];
   ll sum = 0;
   rep(i, 0, m) sum += a[i];
   if (n - sum >= 0)
      cout << n - sum << endl;
   else
      cout << "-1" << endl;
   return 0;
}

Measured memory_bytes: 7144
#include <iostream>

using namespace std;

int A, B;
char map[105][105];

int main(void)
{
	cin >> A >> B;
	
	int h = 100, w = 100;
	for(int y = 1; y <= h; y++){
		for(int x = 1; x <= w; x++){
			if(y > h/2) map[x][y] = '.';
			else map[x][y] = '#';
		}
	}
	
	A--, B--;
	for(int y = 1; y <= h/2; y += 2){
		for(int x = 1; x <= w; x += 2){
			if(A){
				map[x][y] = '.';
				A--;
			}
		}
	}
	for(int y = h/2+2; y <= h; y += 2){
		for(int x = 1; x <= w; x += 2){
			if(B){
				map[x][y] = '#';
				B--;
			}
		}
	}
	
	cout << h << " " << w << endl;
	for(int y = 1; y <= h; y++){
		for(int x = 1; x <= w; x++){
			cout << map[x][y];
		}
		cout << endl;
	}
	
	return 0;
}

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

using ll = long long;
using P = pair<int, int>;

const int INF = 1e9;
const int MOD = 1e9 + 7;

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main() {
  // 入力
  char grid[3][3];
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      cin >> grid[i][j];
    }
  }

  // 解答
  cout << grid[0][0] << grid[1][1] << grid[2][2] << endl;

  return 0;
}


Measured memory_bytes: 384
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
q=int(input())

sm=sum(a)
d=defaultdict(int)
for i in range(n):
    d[a[i]]+=1

for i in range(q):
    b,c=map(int,input().split())
    cnt=d[b]
    sm+=(c-b)*cnt
    d[b]=0
    d[c]+=cnt
    print(sm)

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

const int MAX_N = (int)(1e5 + 5);

int n;

int times[MAX_N];

int ans;

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

  times[1] = 1;

  for (int i = 2; i <= n; ++i) {
    int six = 6;
    int nine = 9;

    while (six < i) {
      six *= 6;
    }

    while (nine < i) {
      nine *= 9;
    }

    if (six == i || nine == i) {
      times[i] = 1;
      continue;
    }

    six = six / 6;
    nine = nine / 9;

    int use6 = MAX_N;
    int use9 = MAX_N;

    if (i - six >= 1) use6 = times[i - six] + 1;
    if (i - nine >= 1) use9 = times[i - nine] + 1;

    times[i] = min(times[i - 1] + 1, min(use6, use9));
  }

  ans = times[n];

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

  return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>
#include <set>
using namespace std;

#ifdef INPUT
#include <sstream>
stringstream input(R"(
6
6 5 4 3 2 1
)");
#define cin input
#endif

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

	vector<int> vec(n);
	for (int i=0; i<n; i++)
	{
		cin >> vec[i];
		vec[i] = vec[i]-(i+1);
	}
	sort(vec.begin(), vec.end());

	long long median;
	if (n%2==1)
		median = vec[n/2];
	else
	{
		if (vec[n/2-1] < vec[n/2])
			median = vec[n/2];
		else
			median = vec[n/2-1];
	}

	long long sum = 0;
	for (int i=0; i<n; i++)
	{
		sum += abs(vec[i]-median);
	}
	cout << sum << endl;
}

Measured memory_bytes: 1024
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V)) //小さい方からソート
#define REV(V) reverse(ALL(V)) //リバース
#define RSORT(V) SORT(V);REV(V) //大きい方からソート
#define NPN(V) next_permutation(ALL(V)) //順列
#define pb(n) push_back(n)
#define endl '\n'
#define Endl '\n'
#define DUMP(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define Yay(n) cout << ((n) ? "Yay!": ":(") << endl
#define RAPID cin.tie(0);ios::sync_with_stdio(false)
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c 
#define IN4(a,b,c,d) cin >> a >> b >> c >> d
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) REP(i, (V).size()) {cout << (V)[i] << endl;}
#define VOUT2(V) REP(i, (V).size()) {cout << (V)[i] << " ";} cout<<endl;

// 型マクロ定義
#define int long long
#define P pair<ll,ll>
#define Vi vector<ll>
#define Vd vector<double>
#define Vs vector<string>
#define Vc vector<char>
#define M map<ll,ll>
#define S set<ll>
#define PQ priority_queue<ll>
#define PQG priority_queue<ll,V,greater<ll>
//

const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int gcd(int a,int b){return b?gcd(b,a%b):a;} //最小公倍数
string toStrUp(string str){char diff = 'A'-'a';REP(i,str.size()) str[i] += diff;return str;}
string gCh(string str, int key){return str.substr(key,1);}

signed main() {
  RAPID;
  // デフォルト変数定義
  int n,m,a,b,c,d,x,y,z;
  string s,t;
  //

  // ここから
  Vi v(3);
  VIN(v)
  SORT(v);
  YES(v[0]==5 && v[1]==5 && v[2]==7);
}

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

int main() {
	int A,B,H,M;
	cin>>A>>B>>H>>M;
	long double time=H*60+M;
	long double angleH,angleM;
	angleH=time*2*M_PI/12.0/60;
	angleM=M*6*M_PI/180.0;
	//cout<<angleH*180/M_PI;
	
	long double ans=pow(A,2)+pow(B,2)-2*A*B*cos(angleH-angleM);
	ans=sqrt(ans);
	cout<<setprecision(20)<<ans;
	return 0;
}

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

ll a, b, c, d;

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

int main() {
    cin >> a >> b >> c >> d;
    ll ans = 0;
    ll cnt = b - a + 1;
    ll cd = c * d / gcd(c, d);
    ans += cnt / c;
    ans += cnt / d;
    ans -= cnt / cd;
    ans += (a % c + cnt % c - 1 < c) ? 0 : 1;
    ans += (a % d + cnt % d - 1 < d) ? 0 : 1;
    ans -= (a % cd + cnt % cd - 1 < cd) ? 0 : 1;
    cout << cnt - ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define N 100001
using namespace std;
vector<int> G[N];

vector<int> ans;
int used[N];

void pr(){
  cout<<ans.size()<<endl;
  for(int i=0;i<ans.size();i++){
    if(i)cout<<" ";
    cout<<ans[i]+1;
  }
  cout<<endl;
  exit(0);
}


void dfs(int pos,int start){
  int flg = 0;
  for(int i=0;i<G[pos].size();i++){
    int nx = G[pos][i];
    if(used[nx])continue;
    flg = 1;
    used[nx] = 1;
    ans.push_back(nx);
    dfs(nx,start);
    used[nx] = 0;
    ans.pop_back();
  }

  if(flg==0){
    for(int i=0;i<(int)G[start].size();i++)if(used[G[start][i]]==0)return;
    pr();
  }
}

typedef pair<int,int> P;

int main(){
  int n,m;
  cin>>n>>m;
  
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;a--,b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  vector<P > g(n);
  for(int i=0;i<n;i++)g[i] = P(G[i].size(),i);
  sort(g.begin(),g.end());

  for(int i=0;i<n;i++){
    int nx = g[i].second;
    used[nx]=1;
    ans.push_back(nx);
    dfs(nx,nx);
    used[nx]=0;
    ans.pop_back();
  }


  return 0;
}


Measured memory_bytes: 14200
d, g =map(int,input().split())
a = []
b = []
for i in range(d):
    p,c = map(int,input().split())
    a.append(p)
    b.append(c)
ans = float('inf')
for i in range(2**d):
    ten = 0
    mon = 0
    for j in range(d):
        if i>>j&1:
            ten += a[j]*((j+1)*100)+b[j]
            mon += a[j]
    if ten < g:
        for j in range(d):
            tenp = ten
            monp = mon
            if i>>j&1 == 0:
                for k in range(a[j]-1):
                    tenp += (j+1)*100
                    monp += 1
                    if tenp >= g:
                        ans = min(ans,monp)
    else:

        ans = min(ans,mon)
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
inline void read(ll &x) {
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
ll a[4],n,res=6e18;
ll solve(ll n, int S){
	assert((S>>2&1)&&(S>>3&1));
	ll res=0;
	/*if(S>>3&1)res+=n/8*a[3],n%=8;
	if(S>>2&1)res+=n/4*a[2],n%=4;
	if(S>>1&1)res+=n/2*a[1],n%=2;
	if(S>>0&1)res+=n/1*a[0],n%=1;*/
	res+=n/8*a[3],n%=8;res+=n/4*a[2],n%=4;
	assert(!n);return res;
}
int main() {
	rep(i,0,3)read(a[i]);rep(i,1,3)a[i]=min(a[i],a[i-1]*2);
	read(n);
	n*=4;
	cout<<solve(n,15);
	return 0;
}


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

using namespace std;

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

    if (a < b)
    {
        tmp = a;
        a = b;
        b = tmp;
    }

    if (!((a - b) % 2))
    {
        cout << a - ((a - b) / 2);
    }
    else
        cout << "IMPOSSIBLE" << endl;
}

Measured memory_bytes: 256
def main():
    N = int(input())
    c = [[0 for i in range(10)] for j in range(10)]
    for k in range(1, N+1):
        s = str(k)
        c[int(s[0])][int(s[-1])] += 1

    ans = 0
    for i in range(10):
        for j in range(10):
            ans += c[i][j] * c[j][i]
    print(ans)


if __name__ == '__main__':
    main()


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

using namespace std;

bool
sortByZero(const vector<int> &la, const vector<int> &ra) {return la[0] < ra[0];}

bool
sortByOne(const vector<int> &la, const vector<int> &ra) {return la[1] < ra[1];}

int
main(void) {
  int n, m, i, left, right, counter, _a, _b;

  cin >> n >> m;
  vector< vector<int> > A(m, vector<int>(2));

  for(i=0; i<m; i++) {
    cin >> _a >> _b;
    A[i][0] = _a;
    A[i][1] = _b;
  }
  sort(A.begin(), A.end(), sortByOne);
  sort(A.begin(), A.end(), sortByZero);

  left = -1; right = -1;
  counter = 0;
  for(i=0; i<m; i++) {
    _a = A[i][0];
    _b = A[i][1];
    if (_a < right) {
      left = _a;
      right = min(_b, right);
    } else {
      counter += 1;
      left = _a;
      right = _b;
    }
  }
  cout << counter << endl;

  return 0;
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);in(name)
#define vv(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define VV(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__));in(name)
#define vvv(type,name,h,w,...) vector<vector<vector<type>>>name(h,vector<vector<type>>(w,vector<type>(__VA_ARGS__)))
inline int scan(){ return getchar(); }
inline void scan(int &a){ scanf("%d", &a); }
inline void scan(unsigned &a){ scanf("%u", &a); }
inline void scan(long &a){ scanf("%ld", &a); }
inline void scan(long long &a){ scanf("%lld", &a); }
inline void scan(unsigned long long &a){ scanf("%llu", &a); }
inline void scan(char &a){ cin >> a; }
inline void scan(float &a){ scanf("%f", &a); }
inline void scan(double &a){ scanf("%lf", &a); }
inline void scan(long double &a){ scanf("%Lf", &a); }
inline void scan(vector<bool> &vec){ for(unsigned i = 0; i < vec.size(); i++) { int a; scan(a); vec[i] = a; } }
inline void scan(string &a){ cin >> a; }
template<class T> inline void scan(vector<T> &vec);
template<class T, size_t size> inline void scan(array<T, size> &vec);
template<class T, class L> inline void scan(pair<T, L> &p);
template<class T, size_t size> inline void scan(T (&vec)[size]);
template<class T> inline void scan(vector<T> &vec){ for(auto &i : vec) scan(i); }
template<class T, size_t size> inline void scan(array<T, size> &vec){ for(auto &i : vec) scan(i); }
template<class T, class L> inline void scan(pair<T, L> &p){ scan(p.first); scan(p.second); }
template<class T, size_t size> inline void scan(T (&vec)[size]){ for(auto &i : vec) scan(i); }
template<class T> inline void scan(T &a){ cin>>a; }
inline void in(){}
template <class Head, class... Tail> inline void in(Head &head, Tail&... tail){ scan(head); in(tail...); }
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using Graph = vector<vector<int>>;
/* 4方向への隣接頂点への移動を表すベクトル */
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

const long long INF = 1LL << 60;
int main(){
    LL(N);
    vector<pair<pair<string,ll>,ll>> list;
    for(int i = 0; i < N; ++i){
        STR(s);
        LL(p);
        list.push_back({{s,-p},i+1});
    }

    sort(list.begin(),list.end());
    for(auto i : list){
        cout << i.second << endl;
    }
}

Measured memory_bytes: 256
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define INF 2e9
signed main(){
  int n,count=0,flag=0;
  vint a(10000,0);
  cin>>n;
  rep(i,n){
    cin>>a[i];
    rep(j,i){
      if(a[i]==a[j]){
	flag=1;
      }
    }
    if(flag==0){
      count++;
    }
    flag=0;
  }
  cout<<count<<'\n';
  return(0);
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define rnt re int
#define re register
#define I inline int
#define V inline void
#define ll long long int
#define isnum(ch) ('0'<=ch&&ch<='9')
#define FOR(i,a,b) for(rnt i=a;i<=b;i++)
#define ROF(i,a,b) for(rnt i=a;i>=b;i--)
#define gc (_op==_ed&&(_ed=(_op=_buf)+fread(_buf,1,100000,stdin),_op==_ed)?EOF:*_op++)
char _buf[100000],*_op(_buf),*_ed(_buf);
I getint(){
	rnt _s=0;re char _ch=gc;
	while(!isnum(_ch))_ch=gc;
	while(isnum(_ch))_s=_s*10+_ch-48,_ch=gc;
	return _s;
}
const int N=1<<19,mod=998244353,inv2=mod+1>>1;
V check(int&x){x-=mod,x+=x>>31&mod;}
I Pow(ll t,rnt x){
	ll s=1;
	for(;x;x>>=1,t=t*t%mod)if(x&1)s=s*t%mod;
	return s;
}
int n,a[N],p[N];
V input(){
	n=getint();rnt l=1<<n;
	FOR(i,0,l-1)a[i]=getint();
}
V FWT(int*a,rnt l){
	for(rnt i=1;i<l;i<<=1)for(rnt j=0,d=i<<1;j<l;j+=d)FOR(k,0,i-1){
		rnt Nx=a[j+k],Ny=a[i+j+k];
		check(a[j+k]=Nx+Ny),check(a[i+j+k]=Nx-Ny+mod);
	}
}
V IFWT(int*a,rnt l){
	for(rnt i=1;i<l;i<<=1)for(rnt j=0,d=i<<1;j<l;j+=d)FOR(k,0,i-1){
		rnt Nx=a[j+k],Ny=a[i+j+k];
		check(a[j+k]=Nx+Ny),check(a[i+j+k]=Nx-Ny+mod);
		a[j+k]=1ll*a[j+k]*inv2%mod;
		a[i+j+k]=1ll*a[i+j+k]*inv2%mod;
	}
}
V init(){
	rnt sum=0,l=1<<n;
	FOR(i,0,l-1)sum+=a[i];sum=Pow(sum,mod-2);
	FOR(i,0,l-1)a[i]=1ll*a[i]*sum%mod;
	a[0]--;
}
V work(){
	rnt l=1<<n;p[0]=l-1;
	FOR(i,1,l-1)p[i]=mod-1;
	FWT(a,l),FWT(p,l);
	FOR(i,0,l-1)
		a[i]=1ll*p[i]*Pow(a[i],mod-2)%mod;
	IFWT(a,l);
	FOR(i,0,l-1)
		cout<<(a[i]+mod-a[0])%mod<<' ';
}
int main(){
	input();
	init();
	work();
	return 0;
}

Measured memory_bytes: 6016
def fibo(n):
	S=[1,1]
	s=1
	if n>1:
		for i in range(2,n+1):
			S.append(S[i-1]+S[i-2])
			s=S[i]
	return s

def main():
	if __name__=="__main__":
		n=input()
		print(fibo(n))

main()

Measured memory_bytes: 6444
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<set>
#include<stdio.h>
using namespace std;
int main(){
    string s;
    int k;
    cin>>s>>k;
    set<string> substring;
    for(int i=0;i<s.size();i++){
        for(int j=1;j<k+1;j++){
            substring.insert(s.substr(i,j));
        }
    }
    set<string>::iterator t=substring.begin();
    for(int i=1;i<k;i++)t++;
    cout<<*t<<endl;
    


return 0;
}

Measured memory_bytes: 1664
x,y = map(int,input().split())

money = [ 300000, 200000, 100000,]
result = 0
if x <= 3:
    result += money[x-1]
if y <= 3:
    result += money[y-1]
if x == 1 and y == 1:
    result += 400000
print(result)

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

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

ll Pow(ll A, ll N){
  if (N ==0) return 1;
  else if (N % 2 == 0) return Pow(A*A%MOD, N/2);
  else return Pow(A*A%MOD, N/2) * A % MOD;
}


int main(){
  ll N, M, K; cin >> N >> M >> K;

  ll cnt1 = 0, cnt2 = 0;
  for (ll i = 0; i <= N - 1; i++){
    cnt1 += i * (N - i); cnt1 %= MOD;
  }
  cnt1 *= M * M % MOD; cnt1 %= MOD;
  for (ll i = 0; i <= M - 1; i++){
    cnt2 += i * (M - i); cnt2 %= MOD;
  }
  cnt2 *= N * N % MOD; cnt2 %= MOD;
  ll ans = (cnt1 + cnt2) % MOD;

  ll nCr = 1;
  for (ll i = 1; i <= K - 2; i++){
    nCr *= N * M - 1 - i; nCr %= MOD;
    nCr *= Pow(i, MOD-2); nCr %= MOD;
  }
  ans *= nCr; ans %= MOD;
  cout << ans << endl;


  return 0;
}


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

int main() {
    ll h;
    cin >> h;
    ll counter = 0;
    ll ans = 0;
    while (h) {
        if (h & 1) h--;
        h = h >> 1;
        ans += (1LL << counter);
        counter++;
    }
    cout << ans << endl;
}

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

typedef long long int ll;
typedef long double ld;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pll pair<ll,ll>
#define MP make_pair
#define ff first
#define ss second
#define PB push_back
#define mod 1000000007
#define lp(i,start,end) for(ll i=start;i<=end;i++) 
#define deb1(a) cout<<#a<<" = "<<(a)<<endl;
#define deb2(a,b) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<endl;
#define deb3(a,b,c) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<endl;


ll modu(ll a, ll b)
{
	ll ans =1;
	while(b>0)
	{
		if(b&1)
		ans = (ans*a)%mod;
		b/=2;
		a = (a*a)%mod;
	}
	return ans;
}

int main()
{
	fastio
	ll n;
	cin>>n;
	ll a[n+1];
	lp(i,1,n)
	cin>>a[i];
	ll ans=0;
	for(ll i=2; i<=n; i++){
		if(a[i]<a[i-1]){
			ans+=a[i-1]-a[i];
			a[i]=a[i-1];
		}
	}
	cout<<ans<<endl;
	return 0;	
}


Measured memory_bytes: 5204
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define mt make_tuple
#define MOD 1000000007
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define vl vector <long long int>
#define pii pair <int,int>
#define pll pair <long long int, long long int>
#define vpii vector< pair<int,int> >
#define vpll vector < pair <long long int,long long int> >
#define boost ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
const int inf = 1e9 + 5;
const ll inf64 = 1e18 + 5;
int main()
{
	boost;
	ll a, b, n;
	cin >> a >> b >> n;
	ll ans = 0;
	if(b == 1)
	ans = 0;
	else if(b > n)
	ans = (a * n) / b;
	else {
		ll x = n / (b - 1);
		x *= (b - 1);
		ans = (a * x) / b - a * (x / b);
	}
	cout << ans;
}


Measured memory_bytes: 3608
n = int(input())
a = [int(i)-1 for i in input().split()]
dic = {}
for i in range(n):
    dic[a[i]] = i

for i in range(n):
    print(dic[i]+1,end = "")
    if i != n-1:
        print(" ",end = "")
    else:
        print("")


Measured memory_bytes: 20704
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define rep(i, n) for(ll i=0; i<(ll)(n); i++)
#define repd(i, n) for(ll i=n-1; 0<=i; i--)
#define FOR(i, a, b) for(ll i=a; i<(ll)(b); i++)
#define FORD(i, a, b) for(ll i=b-1; (ll)(a)<=i; i--)
#define ALL(x) x.begin(), x.end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};


int main(){
    ll h, n;    cin >> h >> n;
    vector<ll> s(n), c(n);
    rep(i, n)   cin >> s[i] >> c[i];
    vector<ll> dp(h+1, LINF);
    dp[0] = 0;
    rep(i, h){
        rep(j, n){
            ll nv = min(i+s[j], h);
            dp[nv] = min(dp[nv], dp[i]+c[j]);
        }
    }
    cout << dp[h] << endl;
}


Measured memory_bytes: 3664
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String[] s = new String[3];
        for(int i = 0;i<3;i++){
            s[i] = sc.nextLine();
        System.out.print(s[i].charAt(i));
        }
        System.out.println();
    }
}


Measured memory_bytes: 20820
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define COUNT(i,n) for(int i=1;i<=(n);i++)
// repeat for accumulational summention
#define Acu(i,n,m) for(int i=(n);i<=(m);i++)
#define DownREP(i,n) for(int i=(n);i>0;i--)
#define ll long long
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int MAX=1e9;
int MOD=1e9+7;


int main(){
  int N,A,B;cin>>N>>A>>B;
  cout<<((abs(B-A)%2==0)?"Alice":"Borys")<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define EPS (1e-10)
#define equals(a, b) (fabs((a)-(b)) < EPS)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;

ll mpow(ll a,ll b,int mod) {
  a %= mod;
  ll res = 1;
  while(b > 0) {
    if(b&1) {
      res = (res*a) % mod;
    }
    a = (a*a) % mod;
    b >>= 1;
  }
  return res;
}
  
int main() {
  int N;
  cin >> N;
  string s;
  cin >> s;
  vi memo(300000,0);
  srep(k,1,300000) {
    int x=k;
    int y = __builtin_popcountll(x);
    x %= y;
    memo[k]=memo[x]+1;
  }
  int cnt = 0;
  rep(i,N) {
    cnt += s[i]=='1';
  }
  ll Nmc=0;
  rep(i,N) {
    Nmc <<= 1;
    Nmc += s[i]=='1';
    Nmc %= cnt;
  }
  ll Nmcd=0;
  if(cnt>1) {
    rep(i,N) {
      Nmcd <<= 1;
      Nmcd += s[i]=='1';
      Nmcd %= cnt-1;
    }
  }
  ll Nmci=0;
  rep(i,N) {
    Nmci <<= 1;
    Nmci += s[i]=='1';
    Nmci %= cnt+1;
  }
  rep(i,N) {
    if(s[i]=='0') {
      ll k = Nmci+mpow(2,N-1-i,cnt+1);
      k %= cnt+1;
      cout << memo[k]+1 << endl;
    } else {
      if(cnt==1) {
        cout << 0 << endl;
        continue;
      }
      ll k = Nmcd-mpow(2,N-1-i,cnt-1);
      k += cnt-1;
      k %= cnt-1;
      cout << memo[k]+1 << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 4708
import bisect as bi

def S(T): # Ai+Aj>=Tなる(i,j)の個数
    global N
    res=0
    for i in range(N):
        res+=k(i,T)
    return res

def k(i,T): # Ai+Aj>=Tなるjの個数
    global A
    N=len(A)
    res=N-bi.bisect_left(A,T-A[i])
    return res

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
# print(A) #DB

l=A[0]*2;r=A[N-1]*2
while r-l>1:    
    m=(l+r)//2
    # print(l,m,r)
    # print(S(m))
    if S(m)>=M: # 十分な組合せがある
        l=m
    else:
        r=m
# print(l,r)

# lがM通り作れるmax
b=[0] # 累積和 bi=Aの大きいほうからi項の和
for i in range(N):
    b.append(b[-1]+A[N-1-i])
# print(b)

ans=0
cnt=0
for i in range(N):
    cnt+=k(i,l)
    ans+=A[i]*k(i,l)+b[k(i,l)]

# print(cnt)
if cnt>M:
    ans-=l*(cnt-M)

print(ans)

Measured memory_bytes: 61504
package main

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

var sc = bufio.NewScanner(os.Stdin)

func readInt() int {
	sc.Scan()
	iv, _ := strconv.Atoi(sc.Text())
	return iv
}

var n int
var G map[int][]int

func initGraph() {
	G = make(map[int][]int)
}

func add(x, y int) {
	if _, ok := G[x]; !ok {
		G[x] = make([]int, 0, n)
	}
	G[x] = append(G[x], y)
}

var seen map[int]bool
var ba, bb int

func dfs(v int) {
	seen[v] = true
	for _, nv := range G[v] {
		if seen[nv] {
			continue
		}
		if (v == ba && nv == bb) || (v == bb && nv == ba) {
			continue
		}
		dfs(nv)
	}
}

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n = readInt()
	m := readInt()
	initGraph()

	type bridge struct{ a, b int }
	bs := make([]bridge, m)
	for i := 0; i < m; i++ {
		a, b := readInt(), readInt()
		add(a, b)
		add(b, a)
		bs[i] = bridge{a, b}
	}

	ans := 0
	for _, bv := range bs {
		ba, bb = bv.a, bv.b
		seen = make(map[int]bool)
		dfs(1)
		if len(seen) != n {
			ans++
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  long long a, ans;
  cin >> n;
  bool ng = false;
  ans = 1;
  for (int i = 0; i < n; i++) {
    cin >> a;
    if (a == 0) {
      cout << '0' << '\n';
      return 0;
    }
    if (ng || a > 1000000000000000000 / ans) {
      ng = true;
    } else {
      ans *= a;
    }
  }
  if (ng) cout << -1 << endl;
  else cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 3620
import java.util.Scanner;


public class Main {
        public static void main(String[] args){
                Scanner sn = new Scanner(System.in);
                int n = sn.nextInt();
                for(int i = 0; i < n; i++){
                        System.out.println( decode(sn.next(),  sn.next()));
                }
        }

        static Message decode(String order, String msg){
        	Message m = new Message(msg);
                for(int i = order.length()-1; i >= 0; i--){
                        switch(order.charAt(i)){
	                        case 'J': m = m.c(); break;
	                        case 'C': m = m.j(); break;
	                        case 'E': m = m.e(); break;
	                        case 'A': m = m.a(); break;
	                        case 'P': m = m.m(); break;
	                        case 'M': m = m.p(); break;
                        }
                }
                return m;
        }
}

class Message{
        private String s;
        public String toString(){
                return s;
        }

        Message(String s){
                this.s = s;
        }

        Message j(){
                return new Message(s.substring(1)+s.charAt(0));
        }

        Message c(){
                return new Message(s.charAt(s.length()-1)+s.substring(0, s.length()-1));
        }

        Message e(){
                int half = s.length()/2;
                return  (s.length()%2==0)? new Message( s.substring(s.length()-half, s.length()) + s.substring(0, half)):
                        new Message( s.substring(s.length()-half, s.length()) + s.charAt(half) + s.substring(0, half));
        }

        Message a(){
                return new Message(new StringBuffer(s).reverse().toString());
        }

        Message p(){
                String ns = "";
                char[] digits = {'1', '2', '3', '4', '5', '6', '7', '8', '9', '0'};
                for(int i = 0; i < s.length(); i++){
                        ns += (s.charAt(i) >= '0' && s.charAt(i) <= '9')? digits[s.charAt(i)-'0']:
                                s.charAt(i);
                }
                return new Message(ns);
        }

        Message m(){
                String ns = "";
                char[] digits = {'9', '0', '1', '2', '3', '4', '5', '6', '7', '8'};
                for(int i = 0; i < s.length(); i++){
                        ns += (s.charAt(i) >= '0' && s.charAt(i) <= '9')? digits[s.charAt(i)-'0']:
                                s.charAt(i);
                }
                return new Message(ns);
        }
}

Measured memory_bytes: 17256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
typedef unsigned int uint;
using namespace std;

int main(){
  string s;
  int K;
  cin >> s >> K;
  int N = s.size();

  string INF = "z";//最大の文字列
  for(int i=0;i<5000;i++){
    INF += "z";
  }

  string ans[K];
  fill(ans,ans+K,INF);
  for(int i=0;i<K;i++){
    if(i==0){
      for(int j=0;j<N;j++){
        for(int k=j;k<N && k-j+1<=K ;k++){
          ans[0] = min(ans[0], s.substr(j,k-j+1));
        }
      }
    }
    else{
      for(int j=0;j<N;j++){
        for(int k=j;k<N && k-j+1<=K ;k++){
          if(ans[i-1]<s.substr(j,k-j+1)){
            ans[i] = min(ans[i], s.substr(j,k-j+1));
          }
        }
      }
    }
  }

  cout << ans[K-1] << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N;
    cin >> N;
    
    int array[110];
    for(int i=0; i<N; i++){
        cin >>  array[i];   
    }
    
    sort(array, array+N, greater<int>());
    for(int i; i<N; i++){
    	//cout << "array" << i << "=" << array[i] << endl;  
    }

    int Bob=0;
    int Alice=0;
    for(int i=0; i<N; i++){
        if(i %2 ==0){
            Alice += array[i];
            //cout << "Alice=" << Alice << endl;
        }else{
            Bob += array[i];
            //cout << "Bob=" << Bob << endl;
        }
    }
    
    cout << Alice - Bob <<endl;
    
    return 0;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
long long int MOD = 998244353;

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

    vector<long long int> a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }

    vector<long long int> ans(s+1);
    vector<long long int> exponent(s+1);// formal power series

    for(int i=0; i<n; i++){// * (1 + x^a[i])
        vector<long long int> next(s+1);
        exponent[0] += 1;
        //for(long long int e : exponent) cout << e << " ";
        //cout << endl;

        for(int j=0; j<=s; j++){
            next[j] += exponent[j];
            if(j - a[i] >= 0) next[j] += exponent[j-a[i]];
            next[j] %= MOD;
        }
        exponent = next;
        for(int j=0; j<=s; j++){
            ans[j] += exponent[j];
            ans[j] %= MOD;
        }
    }
    cout << ans[s] << endl;
    return 0;
}

Measured memory_bytes: 3724
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from math import factorial


def comb(n,k,p):
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1
    mink = min(k,n-k)
    a = 1
    b = 1
    for i in range(mink):
        a = a * (n-i) % p
        b = b * (i+1) % p

    return (a*power_func(b,p-2,p))%p


def power_func(a,b,p):
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p


def main():
    n,a,b = map(int,input().split())

    mod = 10 ** 9 + 7

    temp1 = comb(n,a,mod)
    temp2 = comb(n,b,mod)

    res = power_func(2,n,mod) - 1
    res -= temp1 + temp2
    res %= mod

    print(res)



main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std; 
int main(){
	ios_base::sync_with_stdio(false);  
	cin.tie(NULL);
	int n;cin>>n;
	bool flag = true;
	for(int i=0;i<n;i++){
		int a;cin>>a;
		if(a%2==0){
			if(a%3!=0 && a%5!=0){
				flag = false;
			}
		}
	}
	if(flag==false){
		cout<<"DENIED"<<endl;
	}
	else{
		cout<<"APPROVED"<<endl;
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define fip ios_base::sync_with_stdio(false); cin.tie(NULL) 
#define reptUsual(b) for(i=0; i<b; ++i)
#define reptArIn(i,a,b,ar) for( i=a; i<b; ++i) cin>>ar[i];
#define rept(i,a,b) for(i=a; i<b; ++i)
#define all(a)  a.begin(), a.end()
#define maX(a,b)    ( (a) > (b) ? (a) : (b))
#define miN(a,b)    ( (a) < (b) ? (a) : (b))
#define sz(a) ((int)(a.size()))
#define pb(a) push_back(a)
#define ins(a) insert(a)
#define mp make_pair
#define newln cout<<"\n";
#define bigPrime 1000000007
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>  new_data_set;  

int main()
{  
    fip;
    int n,i,cnt=0;
    cin>>n;
    int ar[n];
    reptUsual(n)
    {
        cin>>ar[i];
    }
    if(n&1)
    {
        cout<<"0";
    }

    else
    {
        int id = n/2;
        
        sort(ar,ar+n);
        if(ar[id]==ar[id-1])
            cout<<"0";
        else
            cout<<(ar[id]-ar[id-1]);
    }

    return 0;
    
}

Measured memory_bytes: 640
import numpy as np
import bisect
from typing import List


def main():
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    print(t(n, m, k, a, b))


def t(n: int, _: int, k: int, a: List[int], b: List[int]) -> int:
    a = np.concatenate([[0], a])
    a = np.cumsum(a)
    b = np.concatenate([[0], b])
    b = np.cumsum(b)

    ret = 0
    for i in range(n + 1):
        x = a[i]
        s = k - x
        if s < 0:
            break
        j = bisect.bisect(b, s) - 1
        ret = max(ret, i + j)

    return ret


if __name__ == '__main__':
    main()


Measured memory_bytes: 58040