akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <functional>
#include <set>
#define DB cerr<<"D"<<endl
#define pb push_back
using namespace std; using ll=long long; using ld=long double; const int INF=1e9; const ll LINF=1e18; const double dINF = 1e18; const ld ldINF = 1e18; const double EPS = 1e-6;
template<typename T, typename U, typename O> void caut(T a, U b, O c){cout<<"("<<a<<","<<b<<","<<c<<") ";} template<typename T, typename U> void caut(T a, U b){cout<<"("<<a<<","<<b<<") ";} template<typename T> void caut(T a){cout<<"("<<a<<") ";}
using P=pair<double,int>;
const ll M = 1e9+7;
void add(ll& x, ll y) {x+=y; x%=M;}
void chmax(ll& x, ll y) {if (x<y) x=y;}
ll mod_pow(ll x, ll a) { ll an = 1; while(a > 0) { if (a&1) an = an * x % M; x = x * x % M; a >>= 1;} return an;}

int main() {
  ll w,h,x,y; cin>>w>>h>>x>>y;
  if (w%2==0 && h%2==0 && x==w/2 && y==h/2) {
    ld ans = ld(w*h)/2;
    cout<<ans<<" "<<1<<endl;
  } else {
    ld ans = ld(w*h)/2;
    cout<<ans<<" "<<0<<endl;
  }
}

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

#define ll long long int
#define oo 1L<<60;

int vals [100005];
ll memo[100005];
int N;
int K;

int op(int i){return i>0? i : 0;}

ll costo(){
	memo[0]= 0;
	memo[1]= abs(vals[1]-vals[0]);
	for(int i = 1; i<N;i++){
		memo[i] = oo;
		for(int k = 1; k<=K;k++)	memo[i] = min(abs(vals[op(i-k)]-vals[i])+memo[op(i-k)], 
										  memo[i]);
	}
	return memo[N-1];
}

int main() {
	cin>>N;
	cin>>K;
	for(int i = 0; i<N;i++)
		cin>>vals[i];
	cout<<costo()<<endl;
	return 0;
}

Measured memory_bytes: 4684
def calc(N, T, c, y):
    cost = 1001
    for i in range(N):
        if T >= y[i] and cost > c[i]:
            cost = c[i]
    return cost


def main():
    N, T = list(map(int, input().split()))
    c, y = [], []
    for _ in range(N):
        ct = list(map(int, input().split()))
        c.append(ct[0])
        y.append(ct[1])
    ret = calc(N, T, c, y)
    print([ret,"TLE"][ret==1001])


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
N = int(input())
li = [input() for _ in range(N)]
se = set(li)

Flag = True
for i in range(N-1):
    if li[i][-1] != li[i+1][0]:
        Flag = False

if len(li) != len(se):
    Flag = False
        
if Flag:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace  std;

int main() {
	int A, B, C, X, Y;
	cin >> A >> B >> C >> X >> Y;
	int price = 0 , price2=INT_MAX;
	if (A + B > 2 * C) {
		if (X > Y) {
			price += 2 * Y * C;
			price += (X - Y) * A;
			price2 = 2 * X * C;
		}
		else {
			price += 2 * X * C;
			price += (Y - X) * B;
			price2 = 2 * Y * C;
		}
	}
	else {
		price = X * A + Y * B;
	}
	if (price2 < price)price = price2;
	cout << price << endl;
	return 0;
}

Measured memory_bytes: 3596
# coding: UTF-8
import sys
import numpy as np
import math


n = int(input())
aList = list(map(int, input().split()))
numMinus = 0
for i in range(n):
	if aList[i] < 0:
		numMinus += 1
		aList[i] *= -1

aList.sort()

if numMinus % 2 == 0:
	print(sum(aList))
else:
	print(sum(aList) - 2 * aList[0])


Measured memory_bytes: 38024
#[allow(unused_imports)]
use itertools::Itertools;
#[allow(unused_imports)]
use num::*;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::collections::*;

#[allow(non_snake_case)] // for `input! { N: ... }`
fn solve() {
    input! {
        N: usize,
        P: [usize; N]
    };

    let mut indexes = vec![0; N + 1];
    for (i, &p) in P.iter().enumerate() {
        indexes[p] = i;
    }
    let mut set: BTreeSet<usize> = BTreeSet::new();
    set.insert(indexes[N]);
    let mut res = 0_usize;
    for n in (1..N).rev() {
        let i = indexes[n];
        let mut iter = set.range(0..i);
        let l1 = iter.next_back();
        let l2 = iter.next_back();
        let mut iter = set.range(i + 1..);
        let r1 = iter.next();
        let r2 = iter.next();
        res += match (l2, l1, r1) {
            (None, Some(l1), None) => (l1 + 1) * (N - i) * n,
            (None, Some(l1), Some(r1)) => (l1 + 1) * (r1 - i) * n,
            (Some(l2), Some(l1), None) => (l1 - l2) * (N - i) * n,
            (Some(l2), Some(l1), Some(r1)) => (l1 - l2) * (r1 - i) * n,
            _ => 0,
        };
        res += match (l1, r1, r2) {
            (None, Some(r1), None) => (i + 1) * (N - r1) * n,
            (None, Some(r1), Some(r2)) => (i + 1) * (r2 - r1) * n,
            (Some(l1), Some(r1), None) => (i - l1) * (N - r1) * n,
            (Some(l1), Some(r1), Some(r2)) => (i - l1) * (r2 - r1) * n,
            _ => 0,
        };
        set.insert(i);
    }
    println!("{}", res);
}

fn main() {
    std::thread::Builder::new()
        .name("big stack size".into())
        .stack_size(256 * 1024 * 1024)
        .spawn(|| {
            solve();
        })
        .unwrap()
        .join()
        .unwrap();
}


Measured memory_bytes: 6160
#include<iostream>
#include<vector>
#include <cmath>
#include <map>
#include <algorithm>
using namespace std;
int x0 (int r, int d,int x ){
    int x1;
    x1 = r * x - d; 


    return x1;
}

int main(void){
    int r ,d , x ;
    cin >> r >> d >> x ; 
    int x1;

    for ( int i = 0; i < 10; i++ ){
        x1 = x0 (r,d,x);
        cout << x1 <<endl;
        x = x1;
        
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define llu unsigned long long int
#define sa(a,n,t) for(int ii=0;ii<n;ii++) scanf("%"#t"",&(a)[ii])
#define rep(i,n) for(int i=0;i<n;i++) 
#define reps(i,a,n) for(int i=a;i<n;i++) 
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rreps(i,a,n) for(int i=n-1;i>=a;i--)
#define validl(i,a,b) ((i>=a)&&(i<=b))?1:0
#define validmat(x,y,a,b,c,d) (validl(x,a,b) && validl(y,a,b))?1:0
#define validmn(x,y,m,n) validmat(x,y,0,m,0,n)
#define valid(i,n) validl(i,0,n)
#define v(t) vector<t>
#define vv(t) vector<vector<t> >
#define mk make_pair
#define pb push_back
#define pa(a,n,t)  for(int i=0;i<n;i++) printf("%"#t"",a[i])
#define p2 pair<int,int>
#define p3 pair<p2,int>
#define fi first
#define se second
#define sd(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define pl(a) printf("%lld",a)
#define pd(a) printf("%d",a)
#define sf(a) scanf("%lf",&a)
#define pf(a) printf("%lf",a)
#define nline printf("\n")
#define ss(a) scanf("%s",a)
#define ps(a) printf("%s",a)
#define sc(a) scanf("%c",&a)
#define pc(a) printf("%c",&a)
#define mf(m,f) m.find(f)!=m.end()
#define pp3(m) cout<<m.fi.fi<<" "<<m.fi.se<<" "<<m.se<<" "
#define pp2(m) cout<<m.fi<<" "<<m.se<<" "
#define debug 0
int main()
{
  int a,b,c,d;
  int n;
  sd(n);
  string s;
  map<string,int> mp;
  rep(i,n) cin>>s,mp[s]=1;
  cout<<mp.size();
  nline;
  return 0;
}


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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

using i64=int64_t;

string increment(string s){
    ++s[0];
    rep(i,0,s.size()-1) if(s[i]=='z'+1){
        ++s[i+1];
        s[i]='a';
    }
    if(s.back()=='z'+1){
        s.back()='a';
        s+="a";
    }
    return s;
}

void solve(){
    string A;
    cin >> A;

    static int min_index[200000][26];
    fill_n((int*)min_index,200000*26,inf);
    min_index[A.size()-1][A.back()-'a']=A.size()-1;
    for(int i=int(A.size())-2; i>=0; --i){
        rep(c,0,26) min_index[i][c]=min_index[i+1][c];
        min_index[i][A[i]-'a']=i;
    }

    static int memo[200001]={};
    static bool done[200001]={};

    function<int(int)> rec=[&](int index){
        int &res=memo[index];
        
        if(done[index]) return res;
        done[index]=true;

        if(index==A.size()) return res=1;
        
        int ma=0;
        rep(c,0,26) ma=max(ma,min_index[index][c]);
        if(ma==inf) return res=1;
        
        return res=rec(ma+1)+1;
    };

    function<void(int)> ans=[&](int index){
        int impossible_len=rec(index);

        if(impossible_len==1) rep(c,0,26) if(min_index[index][c]==inf){
            cout << char('a'+c) << endl;
            return;
        }

        rep(c,0,26){
            int index_=min_index[index][c]+1;
            if(rec(index_)==impossible_len-1){
                cout << char('a'+c);
                ans(index_);
                return;
            }
        }
    };

    ans(0);
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
typedef long long ll;
typedef pair<int, int> pii;
const int inf=100100100;
const int mod=(int)1e9+7;

int main(){
    int n;
    cin>>n;
    vector<int>a(n+1);
    map<int,int>m;
    rep(i,1,n+1){
        cin>>a.at(i);
        m[a.at(i)+i]++;
    }
    ll ans=0;
    rep(i,1,n+1){
        ans+=m[i-a.at(i)];
    }
    cout<<ans<<endl;
return 0;
}

Measured memory_bytes: 21024
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
using namespace std;

struct Node{
  int key;
  Node *parent, *left, *right;
};

Node *nil;

class BinaryTree{
public:
  BinaryTree(){root = new Node; root = nil;}
  ~BinaryTree(){delete root;}
  void Preorder(Node *x);
  void Inorder(Node *x);
  void Postorder(Node *x);
  void insert(int key);

  Node *root;
};


void BinaryTree::insert(int key){
  Node *y = nil;
  Node *x = root;
  Node *z = new Node;
  // Node *z;
  // z = (Node *)malloc(sizeof(Node));
  z->key = key;
  z->left = nil;
  z->right = nil;

  while(x != nil){
    y = x;
    if(key > x->key){
      x = x->right;
    }
    else{
      x = x->left;
    }
  }
  z->parent = y;
  if(y == nil) root = z;
  else{
    if(key > y->key) y->right = z;
    else y->left = z;
  }
}

void BinaryTree::Preorder(Node *x){
  if(x == nil) return;
  cout << " " << x->key;
  Preorder(x->left);
  Preorder(x->right);
}

void BinaryTree::Inorder(Node *x){
  if(x == nil) return;
  Inorder(x->left);
  cout << " " << x->key;
  Inorder(x->right);
}

void BinaryTree::Postorder(Node *x){
  if(x == nil) return;
  Postorder(x->left);
  Postorder(x->right);
  cout << " " << x->key;
}

int main(){
  int n;
  cin >> n;
  string com;
  BinaryTree BT;
  int k;
  for(int i=0;i<n;i++){
    cin >> com;
    if(com == "insert"){
      scanf("%d", &k);
      // cin >> k;
      BT.insert(k);
    }
    else if(com == "print"){
      BT.Inorder(BT.root);
      cout << endl;
      BT.Preorder(BT.root);
      cout << endl;
    }
  }
  return 0;
}



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

typedef long long  ll;

ll MOD = 1000000007;
ll INF = 100000000000000;
double PI = 3.1415926535;

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<ll>>;

int main(){
    int N;cin >> N;
    vector<vector<pair<int,int>>> P(N);
    int ans = 0;
    for(int i = 0;i < N;i++){
        int a;cin >> a;
        for(int j = 0;j < a;j++){
            int x,y;cin >> x >> y;
            x--;
            P[i].push_back(make_pair(x,y));
        }
    }
    /*for(int i = 0;i< N;i++){
        int n = P[i].size();
        cout << '#' << endl;
        for(int j = 0;j < n;j++){
            cout << P[i][j].first << P[i][j].second << endl;
        }
    }*/
    for(int i = 0;i < (1 << N);i++){
        bitset<20> S(i);
        bool AR = 1;
        for(int j = 0;j < N;j++){
            int n = P[j].size();
            if(S.test(j)){
               for(int k = 0;k < n;k++){
                   if(P[j][k].second){
                       if(!S.test(P[j][k].first)){
                           AR = false;
                       }
                   }else{
                       if(S.test(P[j][k].first)){
                           AR = false;
                       }
                   }
               }
            }
        }
        if(AR){
            //cout << S << endl;
            int cnt = 0;
            for(int j = 0;j < N;j++){
                if(S.test(j))cnt++;
            }
            ans = max(ans,cnt);
        }else{
            continue;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#__author__ = "tatuo"
#__date__ = "$Mar 3, 2018 12:34:20 PM$"

import math
import re
import sys


def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()

    
    array_result.append(data.split(" "))

    flg = 1

    try:


        while flg:

            data = input()

            array_temp = []

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:


        return array_result




arr_data = getinputdata()

a = int(arr_data[0][0])
b = int(arr_data[0][1])

if a+b>=24:
    
    print(a+b-24)
    
else:
    
    print(a+b)


#print(n*800 - n//15*200)

#x = "ABC" if n <1200 else "ARC"
#
#print(x)

#s1 = arr_data[0][0][0]
#s2 = arr_data[1][0][1]
#s3 = arr_data[2][0][2]
#
#print(s1+s2+s3)
#


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define oo 1000000010

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

	int a[4], b[4], c[4];
	map<int, int> mp;

	for(int i=0; i<3; i++) cin >> a[i];
	for(int i=0; i<3; i++) cin >> b[i];
	for(int i=0; i<3; i++) cin >> c[i];
	int n;
	cin >> n;
	int d[n+1];
	for(int i=0; i<n; i++){
		cin >> d[i];
		mp[d[i]]++;
	}
	bool b1 = true, b2 = true, b3 = true, b4 = true, b5 = true, b6 = true, b7 = true, b8 = true;
	for(int i=0; i<3; i++){
		if(mp[a[i]] == 0) b1 = false;
		if(mp[b[i]] == 0) b2 = false;
		if(mp[c[i]] == 0) b3 = false;
	}
	if(b1 || b2 || b3){
		cout << "Yes" << endl;
		return 0;
	}
	if(mp[a[0]] == 0 || mp[b[0]] == 0 || mp[c[0]] == 0) b4 = false;
	if(mp[a[1]] == 0 || mp[b[1]] == 0 || mp[c[1]] == 0) b5 = false;
	if(mp[a[2]] == 0 || mp[b[2]] == 0 || mp[c[2]] == 0) b6 = false;
	if(b4 || b5 || b6){
		cout << "Yes" << endl;
		return 0;
	}

	if(mp[a[0]] == 0 || mp[b[1]] == 0 || mp[c[2]] == 0) b7 = false;
	if(mp[a[2]] == 0 || mp[b[1]] == 0 || mp[c[0]] == 0) b8 = false;
	if(b7 || b8){
		cout << "Yes" << endl;
		return 0;
	}

	cout << "No";

    return 0;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		new Main().run();
	}

	int n;
	boolean[] color;
	List<List<Edge>> adj = new ArrayList<List<Edge>>();
	int INF = 1 << 24;

	private void run() {
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		for (int i = 0; i < n; i++) {
			adj.add(new ArrayList<Edge>());
		}
		for (int i = 0; i < n; i++) {
			int v = scanner.nextInt();
			int k = scanner.nextInt();
			for (int j = 0; j < k; j++) {
				int f = scanner.nextInt();
				int s = scanner.nextInt();
				adj.get(v).add(new Edge(f, s));
			}
		}
		slove();
	}

	private void slove() {
		color = new boolean[n];
		int[] d = new int[n];
		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		pq.add(new Edge(0, 0));
		Arrays.fill(d, INF);
		d[0] = 0;
		while (!pq.isEmpty()) {
			Edge f = pq.poll();
			int u = f.second;
			color[u] = true;
			if (d[u] < f.first)
				continue;
			for (int i = 0; i < adj.get(u).size(); i++) {
				int v = adj.get(u).get(i).first;
				if (color[v])
					continue;
				int a = adj.get(u).get(i).second;
				if (d[v] > d[u] + a) {
					d[v] = d[u] + a;
					pq.add(new Edge(d[v], v));
				}
			}
		}
		for (int i = 0; i < n; i++) {
			System.out.printf("%d %d\n", i, d[i]);
		}

	}

	class Edge implements Comparable<Edge> {
		int first;
		int second;

		public Edge(int first, int second) {
			super();
			this.first = first;
			this.second = second;
		}

		@Override
		public int compareTo(Edge o) {
			return this.first - o.first;
		}

	}
}

Measured memory_bytes: 307552
#include<stdio.h>
int main(void)
{
	int k,p,n,i,w;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d %d",&k,&p);
		if(k<p){
			w=k;
		}
		else if(k%p==0){
			w=p;
		}
			else{
				w=k%p;
			}
		printf("%d\n",w);
	}
	return 0;
}


Measured memory_bytes: 2036
import java.util.*;
public class Main {

    public static void main(String[] args) {
        Scanner  yomi = new Scanner(System.in);
        int n = yomi.nextInt();
        int a = yomi.nextInt();
        if (n<10){
            System.out.println(a+(100*(10-n)));
        }else System.out.println(a);
    }
}

Measured memory_bytes: 21844
import bisect
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
A = sorted(LI())
B = sorted(LI())
C = sorted(LI())
ans = 0
for b in B:
    ok_a = bisect.bisect_left(A,b)
    ok_c = bisect.bisect_right(C,b)
    ans += ok_a*(N-ok_c)
print(ans)

Measured memory_bytes: 23156
# coding: utf-8
N, K = map(int, input().split())
H = []
for i in range(N):
    h = int(input())
    H.append(h)
H.sort()
L = []
ans = float("inf")
for i in range(N-K+1):
    ans = min(ans, abs(H[i] - H[i+K-1]))
print(ans)

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

int main()
{
	int S;
	int h, m, s;
	cin >> S;
	
	h = S / 3600;
	S = S % 3600;
	m = S / 60;
	s = S % 60;
	
	cout << h <<":"<< m <<":"<< s <<endl;
	return 0;
}

Measured memory_bytes: 3092
#include<iostream>
#include<cctype>
#include <stdio.h>
using namespace std;

int main(){
    char ch;
    while(1){
        scanf("%c", &ch);
        if(isupper(ch)){
            cout << (char)tolower(ch);
        }else if(islower(ch)){
            cout << (char)toupper(ch);
        }else{
            cout << ch;
        }
        if(ch == '\n') break;
    }
    
    return 0;
}

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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;
const LL INF = 1e17;

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

  long long n_, m_, a_, b_, p_, q_;
  cin >> n_ >> m_ >> a_ >> b_ >> p_ >> q_;
  LL n, m, a, b, p, q;
  n = n_;
  m = m_;
  a = a_;
  b = b_;
  p = p_;
  q = q_;

  LL ans = INF;
  if(a == 1 && b == 1){
	LL k = min(n, m / (p+q));
	mini(ans, abs(k*(p+q) - m));
	if(k+1 < n)
	  mini(ans, abs((k+1)*(p+q) - m));
  }
  else{
	LL M = min((LL)40, n);
	LL M2 = M / 2;
	vector<LL> as(M+1), bs(M+1);
	as[0] = bs[0] = 1;
	REP(i,M){
	  as[i+1] = (as[i]>=INF/a? INF: as[i] * a);
	  bs[i+1] = (bs[i]>=INF/b? INF: bs[i] * b);
	}
	
	vector<LL> xs = {0}, ys = {0};
	for(int bb=0;bb<1<<M2;++bb){
	  LL sum = 0;
	  REP(i,M2)
		if(bb>>i&1){
		  if(as[i] < INF/p)
			sum += as[i]*p;
		  else
			sum = INF;
		  if(bs[i] < INF/p)
			sum += bs[i]*q;
		  else
			sum = INF;
		}
	  xs.PB(sum);
	}
	for(int bb=0;bb<1<<(M-M2);++bb){
	  LL sum = 0;
	  REP(i,M-M2)
		if(bb>>i&1){
		  if(as[i+M2] < INF/p)
			sum += as[i+M2]*p;
		  else
			sum = INF;
		  if(bs[i+M2] < INF/p)
			sum += bs[i+M2]*q;
		  else
			sum = INF;
		}
	  ys.PB(sum);
	}

	for(auto x: xs){
	  auto it = upper_bound(ALL(ys), m - x);
	  if(it != end(ys))
		mini(ans, abs(x + *it - m));
	  if(it != begin(ys)){
		--it;
		mini(ans, abs(x + *it - m));
	  }
	}
  }

  long long ans_ = ans;
  cout << ans_ << endl;

  return 0;
}

Measured memory_bytes: 35636
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define ANS cout << ans << endl
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define REVERSE(a) reverse(all(a))
#define int long long
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define VIin(a) for(int i=0; i<a.size(); i++) cin >> a[i]
#define OUT(a) cout << a << endl
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD=1e9+7;
const long long INF = 1LL << 60;
/*最大公約数*/int gcd(int x, int y) { return y ? gcd(y,x%y) : x;}
/*最小公倍数*/int lcm(int a, int b) { int g = gcd(a, b); return a / g * b; }
/*素数判定*/int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*約数列挙*/vector<int> getDivisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------------------------------------
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n; cin >> n;
    VI l(n); VIin(l);
    SORT(l);
    int sum = 0;
    rep(i,n-1) sum += l[i];
    if(sum > l[n-1]) Yes;
    else No;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
int main() {
	int G, R;
	cin >> R >> G;
	cout << R + (G - R) * 2 << endl;
	return 0;
}

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

int main(){
	string o, e;
	cin >> o >> e;
	string ans;
	for(int i=0; i<e.size(); i++){
		ans+=o.at(i);
		ans+=e.at(i);
	}
	if(o.size()>e.size()){
		ans+=o.at(o.size()-1);
	}
	cout << ans << endl;
}


Measured memory_bytes: 3568
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <stack>
using namespace std;

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

int main() {
	string in;
	while(cin >> in, in[0]!='.') {
		string res="?";
		rep(i, 26) {
			string str = in;
/*
			rep(j, str.length()) {
				if(str[j]=='?') {
					str[j] = (char)('A'+i);
				}
			}
*/
			int diff = 0;
			stack<int> rev_s;
			string out = "";
			rep(i, str.length()) {
				if(str[i]=='+')
					diff++;
				else if(str[i]=='-')
					diff--;
				else if(str[i]=='[') {
					rev_s.push(out.length());
				} else if(str[i]==']') {
					reverse(out.begin()+rev_s.top(), out.end());
					rev_s.pop();
				} else if('A'<=str[i] && str[i]<='Z') {
					out += ('A'+(str[i]-'A'+26*4+diff)%26);
					diff = 0;
				} else {
					out += 'A';
					diff = 0;
				}
			}
			if(res[0]=='?' || out < res) {
				res = out;
			}
		}
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const ll INF = 1e18;
const int MOD = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
int n;
ll k;
vector<ll> a(n); 

bool ok(ll i){
  ll res = 0;
  rep(j,n){
    if(a[j] < 0){
      int l = -1,r = n;
      while( r - l > 1){
        int m = (l+r)/2;
        if(a[j] * a[m] < i) r = m; else l = m;
      }
      res += n-r;
    }      
    else if(a[j] == 0){
      if(i > 0) res += n;
      else ;
    }
    else{
      int l = -1,r = n;
      while( r - l > 1){
        int m = (l+r)/2;
        if(a[j] * a[m] < i) l = m ; else r = m;
      }
      res += r;
    }
    if(a[j]*a[j] < i) res --;
  }
  res /= 2;
  //cout << res << endl;
  return res < k;
}

int main() {
  cin >> n >> k;
  a.resize(n);
  rep(i,n) cin >> a.at(i);
  sort(a.begin(),a.end());
  ll left = -INF;
  ll right = INF;
  while(right - left > 1){
      ll mid = (right + left)/2;
      if(ok(mid)){
          left = mid;
      }else{
          right = mid;
      }
  }
  cout << left <<endl;
  return 0;
}



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

int main() {
  int N;
  cin >>  N;
  int a = N;
  while(true) {
    if (a % 2 == 0) {
      break;
    }else {
      a += N;
    }
  }
  cout << a << endl;
}


Measured memory_bytes: 256
# D - 2017-like Number
def isPrime(p):
    for i in range(2, int(p**0.5)+1):
        if p % i == 0:
            return False
    return True

q=int(input())
f=[1]*(10**5+1)
f[0],f[1]=0,0

for i in range(2,len(f)):
    if isPrime(i):
        for j in range(i*2,len(f),i):
            f[j]=0

c=[0]*(10**5+1)
for i in range(2,10**5+1):
    if i%2==1:
        if f[i]==1 and f[(i+1)//2]==1:
            c[i]=c[i-1]+1
            continue
        c[i]=c[i-1]
    else:
        c[i]=c[i-1]

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

Measured memory_bytes: 4980
#include <iostream>
using namespace std;
int main(void){
  int N, num = 0, maxNum = 1, count = 0,maxCount = 0;
  cin >> N;
  int tmp = 0;
  for(int i = 1; i <= N; ++i){
    count = 0;
    num = i;
    while(num % 2 == 0){
      ++count;
      num/=2;
    }
    if(count > maxCount){
      maxCount = count;
      maxNum = i;
    }
  }
  cout << maxNum << endl;
  return 0;
}


Measured memory_bytes: 256
def main():
    sx, sy, tx, ty = map(int, input().split())
    ans = ""
    ans += "R" * (tx-sx) + "U" * (ty-sy)
    ans += "L" * (tx-sx) + "D" * (ty-sy)
    ans += "D" + "R" * (tx-sx+1) + "U" * (ty-sy+1) + "L"
    ans += "U" + "L" * (tx-sx+1) + "D" * (ty-sy+1) + "R"
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 38256
#include <cstdio>

using namespace std;

int main(void){
  int a,b,c,d;
  
  scanf("%d%d%d%d", &a, &b, &c, &d);
  puts(a+b==c+d?"Balanced":a+b>c+d?"Left":"Right");
  
  return 0;
}

Measured memory_bytes: 128
from __future__ import print_function

import sys
input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return


# import re
# import array
# import copy
# import functools
# import operator

# import math
# import string
import fractions
# from fractions import Fraction
from fractions import gcd

# import collections
# import itertools
# import bisect

# import heapq
# from heapq import heappush
# from heapq import heappop
# from heapq import heappushpop
# from heapq import heapify
# from heapq import heapreplace
# from queue import PriorityQueue as pq
from queue import Queue

# from itertools import accumulate

# from collections import deque
# from collections import Counter

from operator import mul
from functools import reduce

# def lcm(n,m):
#     return int(n*m/gcd(n,m))


def coprimize(p, q):
    common = fractions.gcd(p, q)
    return (p // common, q // common)


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


# import random
# import time

n, k = map(int, input().strip().split())
h = list(map(int, input().strip().split()))
h.sort()
if k > n:
    print(0)
    sys.exit()
else:
    for i in range(k):
        h.pop()
        # eprint(h)
print(sum(h))


Measured memory_bytes: 107348
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U> using Pa = pair<T, U>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M;
    cin >> N >> M;
    vec<int> A(N+2,0),B(N+2,0);
    vec<int> L(M),R(M);
    map<int,int> mp;
    for(int i=0;i<N;i++){
        int a,b;
        cin >> a >> b;
        mp[a] = b;
    }
    int id = 1;
    for(auto& x:mp){
        A[id] = x.first;
        B[id] = x.second;
        id++;
    }
    A[0] = -2e9;
    A[N+1] = 2e9;
    for(int i=0;i<M;i++) cin >> L[i] >> R[i];
    //iとi+1の間
    vec<int> cnt(N+1);
    for(int i=0;i<=N;i++) if(B[i]!=B[i+1]) cnt[i] = 1;

    struct edge{
        int to,id;
    };

    vvec<edge> g(N+1);
    for(int i=0;i<M;i++){
        int l = lower_bound(A.begin(),A.end(),L[i])-A.begin();
        l--;
        int r = upper_bound(A.begin(),A.end(),R[i])-A.begin();
        r--;
        g[l].push_back({r,i});
        g[r].push_back({l,i});
    }
    
    vec<int> vis(N+1,0);
    vec<int> ans;
    vvec<edge> tree(N+1);

    auto solve = [&](int x){
        int c = 0;
        auto dfs = [&](auto&& self,int cur)->void{
            vis[cur] = 1;
            c += cnt[cur];
            for(auto& e:g[cur]) if(!vis[e.to]){
                tree[cur].push_back(e);
                self(self,e.to);
            }
        };
        dfs(dfs,x);
        if(c%2) return false;
        
        auto dfs2 = [&](auto&& self,int cur)->void{
            for(auto& e:tree[cur]){
                self(self,e.to);
                if(cnt[e.to]){
                    ans.push_back(e.id);
                    cnt[e.to] = 0;
                    (cnt[cur] += 1)%=2;
                }
            }
        };
        dfs2(dfs2,x);
        return true;
    };

    for(int i=0;i<N;i++) if(!vis[i]){
        if(!solve(i)){
            cout << -1 << "\n";
            return 0;
        }
    }
    sort(ans.begin(),ans.end());
    int n = ans.size();
    cout << n << "\n";
    for(int i=0;i<n;i++) cout << ans[i]+1 << (i!=n-1? " ":"\n");
}

Measured memory_bytes: 23676
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define INIT(a,n,x); REP(i,(n)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define INIT2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define LINY "YES\n"
#define Liny "Yes\n"
#define LINN "NO\n"
#define Linn "No\n"
#define umap unordered_map
//cout << setfill('0') << right << setw(4) << 12; // "0012"

ll min(ll x,ll y){return (x<y ? x:y);}
ll max(ll x,ll y){return (x>y ? x:y);}
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a*b /gcd(a,b);}

int main(){
  string s; cin>>s;
  int s_size = s.size();
  int r1=0,r2=0;
  int color;
  int x;
  color = 1;
  REP(i,s_size){
    x = ctoi(s[i]);
    r1 += (x==color);
    color = !color;
  }
  color = 0;
  REP(i,s_size){
    x = ctoi(s[i]);
    r2 += (x==color);
    color = !color;
  }
  cout << min(r1,r2) << "\n";

}

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <algorithm>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <ctype.h>
using namespace std;

#define N_MAX   (100000)
#define LL_MAX_NUM (1LL<<60)
#define INF 1e7

typedef long long ll;
typedef long long int lli;

int main() {
	int N, result;
	vector<ll> A;
	cin >> N;
	for (int i = 0; i < N; i++) {
		ll Ai;
		cin >> Ai;
		A.push_back(Ai);
	}
	sort(A.begin(), A.end());
	result = abs(A[0] - A[A.size() - 1]);
	cout << result << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define long long long
#define pll pair < long , long >
#define vll vector < pll >
#define ml map < long , long >
#define mll map < pll , long >
#define x first
#define y second
#define vl vector < long >
#define io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
vl a[100005];
long g[100005]={0};
void dfs(long node , long par)
{
    long i;
    for(i=0;i<a[node].size();++i)
    if(a[node][i]!=par)
    {
        dfs(a[node][i],node);
        g[node]^=(g[a[node][i]]+1);
    }
}
int main()
{
    io
    long n,x,y,i;
    cin>>n;
    n--;
    while(n--)
    {
        cin>>x>>y;
        a[x].pb(y);
        a[y].pb(x);
    }
    dfs(1,-1);
    if(g[1]==0) cout<<"Bob";
    else cout<<"Alice";
    return 0;
}

Measured memory_bytes: 11264
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,u) for(int i=start[u];i;i=e[i].next)
#define fi first
#define se second
#define mkr(a,b) make_pair(a,b)
#define SZ(A) ((int)A.size())
template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}
template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}
inline void myassert(bool a,string s){ if(!a)cerr<<s<<endl,exit(0);}
inline int read()
{
	int s=0,f=1;char ch=getchar();
	while(!isdigit(ch) && ch!='-')ch=getchar();
	if(ch=='-')ch=getchar(),f=-1;
	while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
	return ~f?s:-s;
}

const int maxn=1e5+20;

struct node {
	int v,next;
};
node e[maxn<<1];
int cnt=1,start[maxn];
inline void addedge(int u,int v){ e[++cnt]=(node){v,start[u]};start[u]=cnt;}
int rd[maxn];

int n,m;

inline void init()
{
	n=read();m=read();
	REP(i,1,m)
	{
		int u=read(),v=read();
		rd[u]++;rd[v]++;
		addedge(u,v);
		addedge(v,u);
	}
}

int cur[maxn];
int vis[maxn];
int st[maxn],top;

void dfs(int u)
{
	for(int &i=cur[u];i;i=e[i].next)
	{
		if(vis[i>>1])continue;
		int v=e[i].v,id=i;
		vis[id>>1]=1;
		dfs(v);
		st[++top]=id;
	}
}

int visit[maxn];
int point[maxn],ptot;

inline void doing()
{
	memcpy(cur,start,sizeof(int)*(n+1));
	REP(i,1,n)if(rd[i]&1)puts("No"),exit(0);
	dfs(1);
	visit[point[ptot=0]=1]=1;
	int num=0;
	cerr<<1<<" ";
	DREP(i,top,1)
	{
		int v=e[st[i]].v;
		cerr<<v<<" ";
		if(visit[v])
		{
			int x;
			do{
				x=point[ptot--];
				visit[x]=0;
			}while(point[ptot]!=v);
			num++;
		}else
		{
			visit[v]=1;
			point[++ptot]=v;
		}
	}
	int cnt4=0;
	REP(i,1,n)if(rd[i]>=4)cnt4++;
	
	if(num>=3 || cnt4>=3)puts("Yes");
	else puts("No");
}

int main()
{
	init();
	doing();
	return 0;
}


Measured memory_bytes: 7552
/* ****mittal**** */
#include<bits/stdc++.h>
#define ll          long long int 
#define pb          push_back
#define endl        '\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define jell        998244353
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define repr(i,a,b)   for(ll int i=a;i>=b;i--)
#define lbnd    lower_bound
#define ubnd        upper_bound
#define mp          make_pair
#define DEC(N)  cout << std::fixed; cout << setprecision(N);
using namespace std;
ll add(ll x,ll y)
{
return (x%hell+y%hell)%hell;
}
ll mul(ll x,ll y)
{
return ((x%hell)*(y%hell))%hell;
}
ll sub(ll x,ll y)
{
return (x-y+hell)%hell;
}
#define N  100005
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
   //cin>>t;
    for(int ok=1;ok<=t;ok++)
    {
        
        ll n;
        cin>>n;
        ll a[n+3];
        for(int i=1;i<=n+1;i++)
        {
            cin>>a[i];
        }
        if(n==0&&a[1]==1)
        {
        	 cout<<1<<endl;
        	 return 0;
        }
        if(n==0)
        {
        	cout<<-1;
        	return 0;
        }
        if(a[1]==1&&n!=0)
        {
        	  cout<<-1;
        	  return 0;
        }
        if(a[n+1]==0)
        {
        	 cout<<-1<<endl;
        	 continue;
        }
        ll x=1;
        ll w=0;
        ll b[n+3];
        b[1]=1;
        ll io=1e15;
        for(int i=2;i<=n+1;i++)
        {
            if(a[i]>2*x)
            {
            	 w=1;
            	 break;
            }
            ll o=2*x-a[i];
            o=min(io,o);
            x=o;
            b[i]=o;
        }
        if(w)
        {
        	cout<<-1;
        	return 0;
        }
        ll ans[n+4];
        ans[n+1]=a[n+1];
        ans[1]=1;
        ll ox=a[n+1];
        ll op=ans[1]+ans[n+1];
        for(int i=n;i>=2;i--)
        {     if(2*b[i]<ox)
        	{
        		cout<<-1;
        		return 0;
        	}
              if(ox<b[i])
              	ox=a[i]+ox;
              else
              	ox=a[i]+b[i];
              ans[i]=ox;
              op+=ans[i];
        }
        cout<<op;

    }
    return 0;
}

Measured memory_bytes: 5964
class UnionFind:
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n+1)
        self.cnt = 0

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def groupsize(self):
        self.cnt = 0
        for i,x in enumerate(self.par):
            if x == i:
                self.cnt += 1
        return self.cnt

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    
N,M = map(int,input().split())
XYZ = [list(map(int,input().split())) for _ in range(M)]
uf = UnionFind(N)
for i in range(M):
    uf.union(XYZ[i][0]-1,XYZ[i][1]-1)

print(uf.groupsize())

    

Measured memory_bytes: 32284
N,M=map(int,input().split())
H=list(map(int,input().split()))

ans=[True for _ in range(N)]

for _ in range(M):
    Ai,Bi=map(int,input().split())
    if H[Ai-1]>H[Bi-1]:
        ans[Bi-1]=False
    elif H[Ai-1]<H[Bi-1]:
        ans[Ai-1]=False
    else:
        ans[Ai-1]=False
        ans[Bi-1]=False

print(ans.count(True))


Measured memory_bytes: 85072
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<functional>
#include<string>
#include<iomanip>
#include<map>
#include<utility>
#include<string>
#include<unordered_map>
#include<queue>

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

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
int gcd(int a, int b){return b ? gcd(b, a%b) : a;}

int main(){
    int x; cin >> x;
    vector<bool> dp(x+1, false);
    dp[0] = true;
    for(int i = 1; i <= x; i++){
        int cnt = 0;
        while(cnt <= 5 && i-100-cnt >= 0){
            if(dp[i-100-cnt] == true) dp[i] = true;
            cnt++;
        }
    }
    // for(int i = 0; i <= x; i++) cout << dp[i] << endl;

    if(dp[x] == true) cout << 1 << endl;
    else cout << 0 << endl;
    return 0;
}


Measured memory_bytes: 384
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.System.exit;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	static void solve() throws Exception {
		String s = scanString();
		long k = scanInt();
		boolean same = true;
		for (int i = 1; i < s.length(); i++) {
			if (s.charAt(i) != s.charAt(0)) {
				same = false;
				break;
			}
		}
		if (same) {
			out.print(s.length() * k / 2);
			return;
		}
		long ans = 0, scnt = 0;
		for (int i = 0, j; i < s.length(); i = j) {
			for (j = i + 1; j < s.length() && s.charAt(i) == s.charAt(j); j++) { }
			if (i == 0 && s.charAt(0) == s.charAt(s.length() - 1)) {
				ans += (j - i) / 2;
				scnt = j - i;
			} else if (j == s.length() && s.charAt(0) == s.charAt(s.length() - 1)) {
				ans += (j - i) / 2 + (scnt + j - i) / 2 * (k - 1);
			} else {
				ans += (j - i) / 2 * k;
			}
		}
		out.print(ans);
	}

	static int scanInt() throws IOException {
		return parseInt(scanString());
	}

	static long scanLong() throws IOException {
		return parseLong(scanString());
	}

	static String scanString() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}

	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer tok;

	public static void main(String[] args) {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			solve();
			in.close();
			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			exit(1);
		}
	}
}

Measured memory_bytes: 23124
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <random>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int) n; i++)

int main() {
    int n; cin >> n;
    int ans = 100;
    rep(i,n) {
        int d; cin >> d;
        int cnt = 0;
        while (d % 2 == 0 && d > 0) {
            d /= 2; cnt++;
        }
        ans = min(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> a(m);
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	vector<bool> isBroken(n + 1, false);
	for (auto e : a) {
		isBroken[e] = true;
	}

	// i段目までの移動方法
	vector<long long> ans(n + 1, 0);
	ans[0] = 1;
	if (!isBroken[1]) ans[1] = 1;

	for (int i = 2; i < n + 1; i++) {
		if (!isBroken[i]) {
			if (!isBroken[i - 1]) ans[i] += ans[i - 1];
			if (!isBroken[i - 2]) ans[i] += ans[i - 2];
			ans[i] %= 1000000007;
		}
	}

	cout << ans[n] << endl;

	return 0;
}

Measured memory_bytes: 1408
import java.util.Scanner;

public class Main {
	public long knapsack(int[] weights,int[] values,int W)
	{
		long[][] dp=new long[W+1][weights.length+1];
		
		for(int w=1;w<=W;w++)
		{
			for(int item=0;item<weights.length;item++)
			{
				dp[w][item+1]=dp[w][item];
				if(weights[item]>w)
					continue;
				dp[w][item+1]=
						Math.max(dp[w][item+1], 
						values[item]+dp[w-weights[item]][item]);
			}
		}
		
		return dp[W][weights.length];
	}
	public static void main(String[] args) {
		Scanner s=new Scanner(System.in);
		int size=Integer.parseInt(s.next());
		int W=Integer.parseInt(s.next());
		int[] weights=new int[size];
		int[] values=new int[size];
		
		for(int i=0;i<size;i++)
		{
			weights[i]=s.nextInt();
			values[i]=s.nextInt();
		}
		System.out.println(new Main().knapsack(weights, values, W));
		s.close();
	}
}


Measured memory_bytes: 130384
total = []
average = []
while tmp = gets
  break if tmp == nil
  tmp = tmp.chomp.split(",").map(&:to_i)
  # puts tmp.split(",").map(&:to_i)
  total << tmp[0] * tmp[1]
  average << tmp[1]
end


puts total.inject(:+)
puts (average.inject(:+).to_f/average.size).round


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

const int INF = 1e9+5;

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

	vector<int> h(n);

	for(int &i : h)
	{
		scanf("%d",&i);
	}

	vector<int> dp(n , INF);
	dp[0] = 0;
	for(int i=0; i<n; ++i)
	{
		for(int j=i+1; j<= i+k; ++j)
		{
			if(j<n)	
			{
				dp[j] = min(dp[j] , dp[i] + abs(h[i] - h[j]));
			}
		}
	}

	printf("%d\n",dp[n-1]);
	return 0;
}










//END


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


int main(){
    ll n,score=0; cin >> n;
    string s;
    pair<pair<string,int>,int> pairs[n];

    rep(i,n){
        cin >> s >> score;
        pairs[i]=make_pair(make_pair(s,-score),i+1);
         }
    std::sort(pairs,pairs+n);
    for(int i=0;i<n;i++){
        cout << pairs[i].second << endl;
    }

    

}




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

using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  int m = 1 << n;
  vector<int> s(m);
  multiset<int> now, buf;
  map<int, int> mas;
  int mx = 0;
  for (int i = 0; i < m; i++) {
    cin >> s[i];
    mas[s[i]]++;
    mx = max(s[i], mx);
  }
  sort(s.begin(), s.end());
  if (mas.count(mx) > 1) {
    cout << "No" << endl;
    return 0;
  }
  buf.insert(mx);
  mas.erase(mx);
  for (int i = 0; i < n; i++) {
    for (auto &j : buf) now.insert(j);
    buf.clear();

    for (auto &j : now) {
      auto it = mas.lower_bound(j);
      if (it == mas.begin()) {
        cout << "No" << endl;
        return 0;
      }
      it--;
      buf.insert(it->first);
      it->second--;
      if (it->second == 0)
        mas.erase(it);
    }
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 16640
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
string ma[210];
int dp[210];
int n,f;
queue<int> q;
void ae(int x,int y){
	//cout<<x<<' '<<y<<endl;
	if(dp[x]>=0 && dp[x]%2!=y%2) f=1;
	else if(dp[x]>=0) return;
	else{
		dp[x]=y;q.push(x);
	}
}
int cal(int a){
	f=0;
	memset(dp,-1,sizeof(dp));
	ae(a,0);
	while(!q.empty()){
		int x=q.front();q.pop();
		rep(i,n){
			if(ma[x][i]=='1') ae(i,dp[x]+1);
		}
	}
	if(f>0) return -1;
	int ret=0;
	rep(i,n) ret=max(ret,dp[i]);
	//cout<<a<<' '<<ret<<endl;
	return ret+1;
}
int main()
{
	cin>>n;
	rep(i,n) cin>>ma[i];
	int out=-1;
	rep(i,n) out=max(out,cal(i));
	cout<<out<<endl;
}


Measured memory_bytes: 256
import math
x = int(input())

ceil_num = math.ceil(math.sqrt(x))


def is_prime(n):
    if n <= 1:
        return False
    else:
        pass
    for i in range(2, ceil_num):
        if n % i == 0:
            return False
    else:
        return True

while(is_prime(x)==False):
    x += 1
ans = x
print(ans)

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

int main() {
  int n;string s;cin>>n>>s;
  int ans=0;
  for(int i=1;i<n-1;i++){
    vector<int> a(26),b(26);
    for(int j=0;j<i;j++)a[s[j]-'a']++;
    for(int j=i;j<n;j++)b[s[j]-'a']++;
    int cnt=0;
    rep(j,26)if(a[j]>0&&b[j]>0)cnt++;
    ans=max(ans,cnt);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3604