akhauriyash/Code-Regression huggingface dataset:
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <math.h> // sqrt
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <iomanip> // setprecision
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<long long>;
using pii = pair<int, int>;
using psi = pair<string, int>;

int main() {
    string sa, sb, sc;
    cin >> sa >> sb >> sc;
    deque<char> da, db, dc;
    for (char c : sa) {
        da.push_back(c);
    }
    for (char c : sb) {
        db.push_back(c);
    }
    for (char c : sc) {
        dc.push_back(c);
    }
    bool A = true, B = false;
    while(true) {
        if (A) {
            if (da.empty()) {
                cout << "A" << endl;
                return 0;
            }
            if (da.front() == 'b') {
                B = true;
                A = false;
            }
            else if (da.front() == 'c') {
                A = false;
            }
            da.pop_front();
        }
        else if (B) {
            if (db.empty()) {
                cout << "B" << endl;
                return 0;
            }
            if (db.front() == 'a') {
                A = true;
                B = false;
            }
            else if (db.front() == 'c') {
                B = false;
            }
            db.pop_front();
        }
        else {
            if (dc.empty()) {
                cout << "C" << endl;
                return 0;
            }
            if (dc.front() == 'a') {
                A = true;
            }
            else if (dc.front() == 'b') {
                B = true;
            }
            dc.pop_front();
        }
    }
}


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

int main(){
    string s, t;
    cin >> s >> t;
    sort(s.begin(), s.end());
    sort(t.rbegin(), t.rend());
    if(s < t) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}

Measured memory_bytes: 256
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout

	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)

	n := getNextInt(scanner)
	m := getNextInt64(scanner)

	aa := make(I64, n)
	ss := make([]int64, n+1)
	for i := 0; i < n; i++ {
		aa[i] = getNextInt64(scanner)
	}

	sort.Sort(aa)
	for i := 0; i < n; i++ {
		ss[i+1] = ss[i] + aa[i]
	}

	var ans int64
	l := int64(-1)
	r := aa[0]<<1 + 1

	for l+1 < r {
		mid := (l + r) >> 1
		c := m
		for i := 0; i < n; i++ {
			ll := i - 1
			rr := n
			for ll+1 < rr {
				mm := (ll + rr) >> 1
				if aa[mm]+aa[i] < mid {
					rr = mm
					continue
				}
				ll = mm
			}
			if rr-i == 0 {
				continue
			}
			c -= int64(rr-i-1)<<1 + 1
		}
		if c < 0 {
			l = mid
			continue
		}
		r = mid
	}

	c := m
	for i := 0; i < n; i++ {
		ll := i - 1
		rr := n
		for ll+1 < rr {
			mm := (ll + rr) >> 1
			if aa[mm]+aa[i] <= l {
				rr = mm
				continue
			}
			ll = mm
		}
		if rr-i == 0 {
			continue
		}
		ans += (int64(rr-i-1)<<1)*aa[i] + (ss[rr]-ss[i])<<1
		c -= int64(rr-i-1)<<1 + 1
	}
	ans += c * l

	fmt.Fprintln(writer, ans)
	writer.Flush()
}

type I64 []int64

func (a I64) Len() int           { return len(a) }
func (a I64) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a I64) Less(i, j int) bool { return a[i] > a[j] }


Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
constexpr int mod=1000000007;
constexpr int mod1=998244353;
vector<int> dx={0,1,0,-1},dy={-1,0,1,0};
bool inside(int y,int x,int h,int w){
	if(y<h && y>=0 && x<w && x>=0) return true;
	return false;
}





int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	vector<int> a(n);
	rep(i,n) cin >> a.at(i);
	int ans = 0;
	bool flg = false;
	while(true){
		bool ch = true;
		rep(i,n){
			if(flg){
				if(a.at(i) == 0){
				flg = false;
					continue;
				}
				a.at(i)--;
			}
			else{
				if(a.at(i) > 0){
					ans++;
					flg = true;
					a.at(i)--;
					ch = false;
				}
			}
		}
		flg = false;
		if(ch) break;
	}
	cout << ans << endl;
}


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

N=int(input())
XD=[]
for i in range(N):
    XD.append(tuple(map(int,input().split())))
XD.sort(key=lambda t: t[0])
X,D=[0]*N,[0]*N
for i in range(N):
    X[i],D[i]=XD[i]

class SegmentTree:
    def __init__(self,n,segfunc,ide_ele):
        self.segfunc=segfunc
        self.ide_ele=ide_ele
        self.num=2**(n-1).bit_length()
        self.dat=[ide_ele]*2*self.num
    
    def init(self,iter):
        for i in range(len(iter)):
            self.dat[i+self.num]=iter[i]
        for i in range(self.num-1,0,-1):
            self.dat[i]=self.segfunc(self.dat[i*2],self.dat[i*2+1])
    
    def update(self,k,x):
        k+=self.num
        self.dat[k]=x
        while k:
            k//=2
            self.dat[k]=self.segfunc(self.dat[k*2],self.dat[k*2+1])
    
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p+=self.num
        q+=self.num-1
        res=self.ide_ele
        while q-p>1:
            if p&1==1:
                res=self.segfunc(res,self.dat[p])
            if q&1==0:
                res=self.segfunc(res,self.dat[q])
                q-=1
            p=(p+1)//2
            q=q//2
        if p==q:
            res=self.segfunc(res,self.dat[p])
        else:
            res=self.segfunc(self.segfunc(res,self.dat[p]),self.dat[q])
        return res

edge=[0]*N
s=SegmentTree(N,lambda a,b: max(a,b),0)
s.init([i for i in range(N)])
for i in range(N-1,-1,-1):
    res0=bisect_left(X,X[i]+D[i])
    res=s.query(i,res0)
    edge[i]=res
    s.update(i,res)
dp=[0]*(N+1)
dp[-1]=1
for i in range(N-1,-1,-1):
    dp[i]+=dp[i+1]+dp[edge[i]+1]
    dp[i]%=MOD
print(dp[0])

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

using namespace std;

#define m2(x) ((x) * (x))
#define mp(a, b) make_pair(a, b)
#define ms(a, w) memset(a, w, sizeof(a))
#define fi first
#define se second

typedef long long LL;
typedef pair <int, int> ii;

const int MAXN = 200000 + 10;
const int INF = 1000000001;
const int MOD = 1000000000 + 7;
const int MAX = 200000;

int a[MAXN], b[MAXN];

int main () {
//	ios::sync_with_stdio(false);
//	freopen("1.in", "r", stdin);
//	freopen("CirclesGame.out", "w", stdout);
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	int p = 1, q = n;
	for (int i = n; i >= 1; i--)
		if (n - i & 1)
			b[q--] = a[i];
		else
			b[p++] = a[i];
	for (int i = 1; i <= n; i++)
		printf("%d ", b[i]);

	return 0;
}


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

using namespace std;


class Queue{
    int times[1000000];
    string names[1000000];
    int tail;
    int head;

public:
    Queue(){
        tail = 0;
        head = 0;
    }

    // queueに追加
    void enqueue(string name, int time){
        if (tail == 999999) tail = 0;
        times[tail] = time;
        names[tail] = name;
        tail++;
    }

    void dequeue(string* name, int* time){
        if (head == 999999) head = 0;
        *time = times[head];
        *name = names[head];
        head++;
    }

    bool isEmpty(){
        return head == tail;
    }


};

int main(){
    Queue queue;
    int n, q;
    cin >> n;
    cin >> q;

    for (int i = 0; i < n; i++){
        string name;
        int time;
        cin >> name;
        cin >> time;
        queue.enqueue(name, time);
    }
    int sum_times = 0;

    while(!queue.isEmpty()){
        string name;
        int time;

        queue.dequeue(&name, &time);
        time -= q;

        if (time <= 0){
            sum_times += time + q;
            cout << name << " " << sum_times << endl;
        }else{
            sum_times += q;
            queue.enqueue(name, time);
        }
    }
    return 0;
}




Measured memory_bytes: 13980
#include <bits/stdc++.h>
using namespace std;
#define LL long long
int main()
{
	string s,t;
	cin>>s>>t;
	int ans=0;
	for(int i=0;i<s.size();++i)if(s[i]!=t[i]) ++ans;
	cout<<ans;
	return 0;
}

Measured memory_bytes: 3916
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if(a+b==c+d){
        cout<<"Balanced"<<endl;
    }
    else if(a+b>=c+d){
        cout<<"Left"<<endl;
    }
    else if(a+b<=c+d){
        cout<<"Right"<<endl;
    }
}


Measured memory_bytes: 256
#define FOR(i,a,b) for(int i=a;i<b;i++)
#include <cstdio>
int main(){
	int n,a[200002];
	scanf("%d",&n);	//cin >> n;
	int f=n/2,b=n/2+1;
	FOR(i,0,n){
		if((n-i)%2 == 0) scanf("%d",&a[b++]);	//cin >> a[b++];
		else scanf("%d",&a[f--]);	//cin >> a[f--];
	}
	FOR(i,f+1,b) printf("%d ",a[i]);	//cout << a[i] << " ";
	return 0;
}

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

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

	int *h = new int[N];
	int *r = new int[N];

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

	r[0] = 0;
	r[1] = abs(h[1] - h[0]);

	for(int n=2; n<N; n++){
		r[n] = min(abs(h[n] - h[n-1]) + r[n-1],
			abs(h[n] - h[n-2]) + r[n-2]);
	}

	cout << r[N-1] << endl;

	return 0;
}


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

// using ll = long long;
#define int long long

#define LOG(variable) cout << #variable":\t" << (variable) << endl
#define LOGCON(i, container) for(int (i) = 0; (i) < (container).size(); ++(i)) cout << (i) << ":\t" << (container)[(i)] << endl
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, r, n) for(int i = (n); i >= (r); --i) // from n to r
#define REPOBJ(itr, obj) for(auto itr = (obj).begin(); itr != (obj).end() ; ++itr)
#define REPROBJ(itr, obj) for(auto itr = (obj).rbegin(), e = (obj).rend(); itr != e; ++itr)
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))
/***** MAIN *****/
signed main() {
  int a, b, c;
  cin >> a >> b >> c;
  int tmp = c-a-b;
  if(tmp<=0) {
    cout << "No" << endl;
    return 0;
  }
  if(4*a*b < tmp*tmp) {
    cout << "Yes";
  } else {
    cout << "No";
  }
  cout << "\n";
  return 0;
}
/***** MAIN *****/


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#define INF 999999
typedef long long ll;
using namespace std;
int n,a,b,c,maxm;
		int sum,miniNo,minim;
int t[100][100];
int main(){
	while(cin>>n,n){
		for(int i=0;i<100;i++)for(int j=0;j<100;j++){
			if(i!=j)t[i][j]=INF;
			else t[i][j]=0;
		}
		maxm=0;
		for(int i=0;i<n;i++){
			cin>>a>>b>>c;
			maxm=max(maxm,max(a,b));
			t[a][b]=c;
			t[b][a]=c;
		}
		maxm++;
		for(int k=0;k<maxm;k++){
			for(int i=0;i<maxm;i++){
				for(int j=0;j<maxm;j++){
					t[i][j]=min(t[i][k]+t[k][j],t[i][j]);
				}
			}
		}
		
		
		minim=INF;
		for(int i=0;i<maxm;i++){
			sum=0;
			for(int j=0;j<maxm;j++)sum+=t[i][j];
			if(minim>sum){
				minim=sum;
				miniNo=i;
			}
		}
		cout<<miniNo<<" "<<minim<<endl;
		
	}
	return 0;
}

Measured memory_bytes: 1208
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <tuple>
#include <cmath>
#include <map>
#include <climits>
#include <deque>
#include <numeric>
using namespace std;
using Int = long long;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n,m) for(int i=n;i<m;i++)
int main()
{
    int K; cin >> K;
    vector<pair<int, int>> N(K);
    REP(i, K) N[i] = { (i*10) % K, (i+1) % K };
    vector<int> score(K, INT_MAX);
    deque<int> deque;
    deque.push_back(1);
    score[1] = 1;
    while (!deque.empty()) {
        int i = deque.front();
        deque.pop_front();
        if (i == 0) break;
        if (score[N[i].first] > score[i]) {
            score[N[i].first] = score[i];
            deque.push_front(N[i].first);
        }
        if (score[N[i].second] > score[i] + 1) {
            score[N[i].second] = score[i] + 1;
            deque.push_back(N[i].second);
        }
    }
    cout << score[0] << endl;
    return 0;
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll taka;
    cin>>taka;
    ll ans,d;
    ans=0;
    d=taka/500;
    ans+=d*1000;
    taka=taka-d*500;
    if(taka>4)
    {
        d=taka/5;
        ans+=d*5;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
n, m = map(int,input().split())
x = list(map(int,input().split()))

if n >= m:
    print(0)
else:
    d = []
    x.sort()
    for i in range(m-1):
        d.append(x[i+1]-x[i])
    d.sort()
    ans = 0
    for i in range(m-n):
        ans += d[i]
        #print(d[i])
    print(ans)

Measured memory_bytes: 56872
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define reg(i,a,b) for(int i=((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int,int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))

int w,h;
char s[25][25];
int dat[25][25];

int gone[25][25];
int dd[5]={1,0,-1,0,1};

typedef pair<int,mp> mmp;

int gd(mp a,mp b){
	memst(gone,-1);
	queue<mmp> que;
	que.push(mmp(0,a));
	while(!que.empty()){
		mmp pa = que.front();
		que.pop();
		mp p = pa.sec;
		int c = pa.fir;
		if(p==b)return c;
		if(gone[p.fir][p.sec]!=-1)continue;
		gone[p.fir][p.sec]=c;
		rep(i,4){
			int ty = p.fir + dd[i],
				tx = p.sec + dd[i+1];
			if(dat[ty][tx]==-1)continue;
			if(gone[ty][tx]!=-1)continue;
			que.push(mmp(c+1,mp(ty,tx)));
		}
	}
	return -1;
}

int d[15][15];

int dp[15][1<<12];

int main(void){
	for(;;){
		scanf("%d%d",&w,&h);
		if(h==0)break;
		memst(dat,-1);
		rep(y,h)scanf("%s",s[y]);
		vector<mp> v;
		mp st;
		reg(y,1,h)reg(x,1,w){
			char c = s[y-1][x-1];
			if(c=='*')v.push_back(mp(y,x));
			if(c=='o')st = mp(y,x);
			dat[y][x] = (c=='x')?-1:0;
		}
		if(v.size()==0){
			printf("0\n");
			continue;
		}
		
		bool ok=true;
		memst(d,0);
		
		pque(mmp) que;
		
		rep(i,v.size()){
			rep(j,i){
				d[i][j]=d[j][i]=gd(v[i],v[j]);
				if(d[i][j]==-1)ok=false;
			}
			int c = gd(st,v[i]);
			if(c==-1)ok=false;
			que.push(mmp(c,mp(i,1<<i)));
		}
		
		if(!ok){
			printf("-1\n");
			continue;
		}
		int ls = v.size();
		
		memst(dp,0);
		for(;;){
			mmp pa = que.top();
			que.pop();
			int c = pa.fir,
				no = pa.sec.fir,
				ns = pa.sec.sec;
			if(ns==(1<<ls)-1){
				printf("%d\n",c);
				break;
			}
			if(dp[no][ns])continue;
			dp[no][ns]=1;
			rep(i,ls){
				if(ns&(1<<i))continue;
				int ts = ns | (1<<i);
				if(dp[i][ts])continue;
				que.push(mmp(c+d[no][i],mp(i,ts)));
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1564
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include<ctype.h>
int main(void)
{
    char str[100];
    int i;
    scanf("%s",str);
    for(i=strlen(str)-1;i>=0;i--)
        printf("%c",str[i]);

    puts("");
    return 0;
}

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

int main()
{
int a=0,min=10000000,i=0,b,max=-1000000;
long long total=0;
scanf("%d",&a);
for(i=0;i<a;i++){
	scanf("%d",&b);
	total = total +b;
	if(b<min){
		min=b;
	}
	if(b>max){
		max=b;
	}
	
}
printf("%d %d %lld\n",min,max,total);
return 0;
}


Measured memory_bytes: 3220
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int a = scanner.nextInt();
		String op = scanner.next();
		int b = scanner.nextInt();
		while (true) {
			if (op.equals("*")) {
				System.out.println(a * b);
			} else if (op.equals("+")) {
				System.out.println(a + b);

			} else if (op.equals("-")) {
				System.out.println(a - b);

			} else if (op.equals("/")) {
				System.out.println(a / b);

			} else {
				break;

			}
			a = scanner.nextInt();
			op = scanner.next();
			b = scanner.nextInt();
		}
	}
}


Measured memory_bytes: 26408
import math

N, D = map(int, input().split())
Ps = []
count = 0

for i in range(N):
  P = list(map(int, input().split()))
  Ps.append(P)

def dis2(A, B):
  dis = 0
  for i in range(D):
    dis += (A[i] - B[i])**2
  return dis

for i in range(N-1):
  for j in range(i+1, N):
    if math.sqrt(dis2(Ps[i], Ps[j])).is_integer():
      count += 1

print(count)

Measured memory_bytes: 3064
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def lcm(a, b):
	return a * b // gcd (a, b)
A, B, C, D = map(int, input().split())
diff = B - A + 1
count_c = B//C - (A-1)//C
count_d = B//D - (A-1)//D
cd = lcm(C,D)
count_cd = B//cd - (A-1)//cd
print(diff - count_c - count_d + count_cd)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
const int INF = 2*1e9;
#define ll long long
ll knapsack(vector<pair<ll,ll>>&A,vector<vector<ll>>&dp,ll i,ll totalWeight){
    if(i>=A.size())
        return 0;
    if(dp[i][totalWeight]!=-1)
        return dp[i][totalWeight];
    ll itemWt = A[i].first;
    ll itemVa = A[i].second;
    
    if(itemWt<=totalWeight){
        ll cost1  = itemVa+knapsack(A,dp,i+1,totalWeight-itemWt);
        ll cost2 = knapsack(A,dp,i+1,totalWeight);
        
        dp[i][totalWeight] = max(cost1,cost2);
    }
    else
        return dp[i][totalWeight] = knapsack(A,dp,i+1,totalWeight);
    return dp[i][totalWeight];
     
}
int main(){
  ll n,w;
  cin>>n>>w;
  vector<pair<ll,ll>> A(n);
  ll val,wt;
  for(ll i=0;i<n;i++){
      cin>>wt>>val;
      A[i]={wt,val};
  }
  
  vector<vector<ll>> dp(n,vector<ll>(w+1,-1));
//   for(int i=0;i<n;i++){
//       for(int j=1;j<=w;j++){
//           int vl = A[i].second;
//           wt = A[i].first;
//           if(j-wt>=0)
//             dp[i][j]= max(dp[i-1][j],dp[i][j-wt]+vl);
//         // else{
//         //     if(i>0)
//         //         dp[i][j] = dp[i-1][w];
//         // }
            
//       }
//   }
//   for(int i=0;i<n;i++){
//       for(int j=1;j<=w;j++){
//           cout<<dp[i][j]<<" ";
//       }
//       cout<<endl;
//   }
//   cout<<endl;
//   cout<<dp[n-1][w]<<endl;
  cout<<knapsack(A,dp,0,w)<<endl;
  return 0;
}

Measured memory_bytes: 79488
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define sqr(x) ((x)*(x))
#define mp make_pair
#define uint unsigned
#define ld long double
#define PI pair<int,int>
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define getchar gc
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=100005;
int tong[N<<1],a[N],n,k;
ll check(int x){
	memset(tong,0,sizeof(tong));
	int dq=n,dd=1; ll ans=0;
	tong[n]=1; 
	for(int i=1;i<=n;i++){
		if(a[i]>=x){
			dq++; dd+=tong[dq];
		}else{
			dd-=tong[dq]; dq--;
		}
		ans+=dd; tong[dq]++; dd++;
	}
	return ans;
}
signed main(){
	n=read(); ll k=((ll)n*(n+1)/2+1)/2;
	for(int i=1;i<=n;i++)a[i]=read(); //cout<<check(30)<<endl; return 0;
	int l=1,r=1e9;
	while(l<r){
		int mid=(l+r)>>1; mid++;
		if(check(mid)>=k)l=mid; else r=mid-1;
	}
	cout<<l<<endl;
}

Measured memory_bytes: 1656
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using str = string;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
const double PI = 3.141592653589793238;
const ll mod = 1000000007;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define REP(i, m, n) for (int i = m; i < (int)n; i++)
#define all(a) (a).begin(), (a).end()
#define allg(a) (a).begin(), (a).end(), greator<>()
#define d20 std::setprecision(20)
#define veci vector<int>
#define vecll vector<long long int>
#define vecb vector<bool>
#define vecd vector<double>
template <typename T>
T lcm(T a, T b)
{
	return a / __gcd(a, b) * b;
}
void comb(vector<vector<long long int>> &v)
{
	for (size_t i = 0; i < v.size(); i++)
	{
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (size_t k = 1; k < v.size(); k++)
	{
		for (size_t j = 1; j < k; j++)
		{
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j]);
		}
	}
}
ll repeat_squaring(ll n, ll p, ll m)
{
	if (p == 0)
		return 1;
	if (p % 2 == 0)
	{
		ll t = repeat_squaring(n, p / 2, m);
		return t * t % m;
	}
	return n * repeat_squaring(n, p - 1, m);
}

int main()
{
	int a, b, k;
	cin >> a >> b >> k;
	int cnt = 0;
	for (size_t i = min(a,b); i >= 0; i--)
	{
		if (a % i == 0 && b % i == 0)
		{
			cnt++;
			if (cnt == k)
			{
				cout << i << endl;
				return 0;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 3568
#include <cstdio>

inline int Min(int a,int b){return a<b?a:b;}
inline int Max(int a,int b){return a>b?a:b;}

const int N=305,Inf=0x3f3f3f3f;
int n,m,f[N][N],d[N][N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            scanf("%d",&d[i][j]);
    for(int i=0;i<=100;++i)
        for(int j=0;j<=100;++j)
            for(int x=1;x<=n;++x)
                for(int y=1;y<=m;++y)
                    f[i][j]=Max(f[i][j],d[x][y]-i*x-j*y);
    for(int x=1;x<=n;++x)
        for(int y=1;y<=m;++y)
        {
            int Now=Inf;
            for(int i=0;i<=100;++i)
                for(int j=0;j<=100;++j)
                    Now=Min(Now,f[i][j]+i*x+j*y);
            if(Now!=d[x][y])return puts("Impossible"),0;
        }
    puts("Possible\n202 10401");
    for(int i=1;i<=100;++i)printf("%d %d X\n",i,i+1);
    for(int i=102;i<=201;++i)printf("%d %d Y\n",i,i+1);
    for(int i=0;i<=100;++i)
        for(int j=0;j<=100;++j)
            printf("%d %d %d\n",i+1,202-j,f[i][j]);
    return puts("1 202"),0;
}

Measured memory_bytes: 512
#include <iostream>

 

using namespace std;

 

int main()
{
    int i, x;
    for(i=1; i<=10000; i++)
    {
        cin >> x;
        if(x == 0)
          break;
        else
        cout << "Case " << i << ": " << x << endl;
        
        
    }
}


Measured memory_bytes: 3012
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <iterator>
#include <map>
#include <set>
#include <iomanip>
#include <vector>
#include <cstdint>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Graph = vector<vector<int>>;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define rep(i, N) for(int i = 0; i < N; i++)
#define rep2(i, l, r) for (ll i = (ll)l; i < (ll)(r); i++)
#define INF 1000000000000000
#define MAX 200001

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
const ll MOD = 1000000007;

template <typename T > inline string toString(const T &a) {ostringstream oss; oss << a; return oss.str();};

bool solve(ll N, ll K, ll mid, vector<ll> &A, vector<ll> &F){
    rep(i,N){
        ll now = A[i]*F[i];
        if(now <= mid) continue;
        K -= A[i] - mid/F[i];
    }
    if(K < 0) return false;
    else return true;
}

int main(){
    ll N,K;
    cin >> N >> K;
    vector<ll> A(N),F(N);
    rep(i,N) cin >> A[i];
    rep(i,N) cin >> F[i];
    sort(A.begin(), A.end());
    sort(F.begin(), F.end());
    reverse(F.begin(), F.end());
    ll left = -1;
    ll right = 1000000000005;
    while(right-left>1){
        ll mid = (right + left) / 2;
        if(solve(N, K, mid, A, F)) right = mid;
        else left = mid;
    }
    cout << right << endl;
}

Measured memory_bytes: 6428
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007ll
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define db(x) cout << #x << " = " << x << '\n'
#define sep cout << "********************************************\n"
#define fast ios_base::sync_with_stdio(false), cin.tie(NULL)
ll fac[200005], ifac[200005], n, m, k, md = 998244353ll;
ll pwr(ll b, ll e)
{
	ll ans = 1;
	while (e)
	{
		if (e & 1)
			ans = (ans * b) % md;
		b = (b * b) % md;
		e >>= 1;
	}
	return ans;
}
void pre()
{
	fac[0] = ifac[0] = 1;
	for (int i = 1; i <= 200000; ++i)
	{
		fac[i] = (i * fac[i - 1]) % md;
		ifac[i] = (ifac[i - 1] * pwr(i, md - 2)) % md;
	}
}
ll ncr(ll n, ll r)
{
	if (r > n)
		return 0;
	ll ans = fac[n];
	ans = (ans * ifac[r]) % md;
	ans = (ans * ifac[n - r]) % md;
	return ans;
}
int main(int argc, char const *argv[])
{
	fast;
	pre();
	ll ans = 0;
	cin >> n >> m >> k;
	for (int i = n - 1 - k; i <= n - 1; ++i)
	{
		ll c;
		c = (ncr(n - 1, i) * m) % md;
		c = (c * pwr(m - 1, i)) % md;
		ans = (ans  + c) % md;
	}
	cout << ans;
	return 0;
}

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

int main()
{
    int n ,w;
    cin >> n >> w;
    vector<long> weight(n), value(n);
    for(int i=0; i<n; i++)
    {
        cin >> weight[i] >> value[i];
    }

    vector<vector<long>> dp(n+1, vector<long>(w+1, 0));

    for(int i=0; i<n; i++)
    {
        for(int j=1; j<=w; j++)
        {
            if(weight[i] <= j)
            {
                dp[i+1][j] = max(dp[i][j], dp[i][j-weight[i]] + value[i]);
            }
            else
            {
                dp[i+1][j] = dp[i][j];
            }
        }
    }

    cout << dp[n][w];
}

Measured memory_bytes: 80256
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const int N = 4e3 + 5, mod = 1e9 + 7;
int n, k, p[N][N];
int add(int a, int b){
    return (a + b) % mod;
}
int mul(int a, int b){
    return (1ll * a * b) % mod;
}
void pascal(){
    for(int i = 0; i < N; i++)
        for(int j = 0; j <= i; j++)
            p[i][j] = ((j)? add(p[i - 1][j - 1] , p[i - 1][j]) : 1);
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    pascal();
    cin >> n >> k;
    for(int i = 1; i <= k; i++)
        cout << mul(p[n - k + 1][i], p[k - 1][i - 1]) << '\n';
    return 0;
}


Measured memory_bytes: 61440
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
#define ff first
#define ss second
ll INF = 1e18+5;
const int N=100005;
pair<double,pair<ll,ll>> rat[N];
ll w[N]={},dp[N]={},v[N]{};
void solve()
{
    ll n,k=1,m=0,i=1,j,x,y,l,r,z;
    ll ans=0,sum=0,value=0,weight;
    cin>>n>>weight;
    for(i=0;i<n;i++) cin>>w[i]>>v[i];
    for(i=0;i<n;i++)value+=v[i];
    for(i=1;i<=value;i++) dp[i]=INF;
    for(i=0;i<n;i++)
    {
        for(j=value;j>=v[i];j--)
        {
            if(dp[j-v[i]]!=INF)
            dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    for(i=0;i<=value;i++) 
    {
        if(dp[i]<=weight)
            ans=i;
    }
    cout<<ans;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
     #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin) ;
    freopen("output.txt", "w", stdout) ;
    #endif 
    int t=1;
    //cin>>t;
    while(t--)solve();
    return 0;
}

Measured memory_bytes: 4376
#include<iostream>

using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	double sum = 0;
	for (int i = 1; i <= n; i++) {
		double d = 1.0 / n;
		for (int j = i; j < k; j *= 2) {
			d *= 0.5;
		}
		sum += d;
	}
	printf("%.12f\n", sum);

	return 0;
}


Measured memory_bytes: 256
mod = 10**9 + 7
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

is_broken = [1] * (n+1)

for i in range(m):
    is_broken[a[i]] = 0

step = [i for i in range(n+1)]
step[0] = 1

for i in range(n):
    if i - 1 >= 0:
        step[i+1] = step[i] * is_broken[i] + step[i-1] * is_broken[i-1]
    else:
        step[i+1] = step[i] * is_broken[i]
    step[i+1] %= mod

print(step[n])

Measured memory_bytes: 11824
#include <bits/stdc++.h>
using namespace std;
#define rep0(i,n) for(ll (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(ll (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(ll (i) = 1; (i) <= (n); ++(i))
#define rrep1(i,n) for(ll (i) = (n); (i) >= 1; --(i))
#define nfor(i,a,b) for(ll (i) = (a); (i) < (b); ++(i))
#define rnfor(i,a,b) for(ll (i) = (a) - 1; (i) >= (b); --(i))
#define ll long long
#define mod (1000000007)
#define pf(x) cout << (x) << endl
#define all(x) (x).begin(),(x).end()
const ll inf = 1e9;

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

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

ll factorial(ll n){
    ll t = 1;
    rep1(i, n)t *= i;
    return t;
}

ll combinations(ll n, ll k) {
    ll r = 1;
    rep1(i, k)r = r * n-- / i;
    return r;
}

int main(){
    ll n,m,q;
    cin >> n >> m >> q;
    ll cnt[n + 1][n + 1];
    rep0(i, n + 1)rep0(j, n + 1)cnt[i][j] = 0;
    rep0(i, m){
        ll l,r;
        cin >> l >> r;
        ++cnt[l][r];
    }
    
    rep1(i, n)rep1(j, n)cnt[i][j] += cnt[i][j - 1];
    rep0(i, q){
        ll l,r;
        cin >> l >> r;
        ll ans = 0;
        nfor(j, l, r + 1)ans += cnt[j][r] - cnt[j][l - 1];
        pf(ans);
    }
    return 0;
}


Measured memory_bytes: 2944
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;
constexpr int MOD = 1'000'000'007;
//inline void modAdd(LL &l, LL &r) {l = (l + r) % MOD;}

template<class T> inline T sqr(T x) {return x*x;}

void solve() {
    int n;
    cin >> n;
    VS s(n);
    REP(i,0,n) cin >> s[i];
    bool isc = false;
    int enda = 0, stab = 0, both = 0;
    REP(i,0,n) {
        if (s[i][0] == 'B' && s[i][s[i].size()-1] == 'A') both++;
        else if (s[i][s[i].size()-1] == 'A') enda++;
        else if (s[i][0] == 'B') stab++;
    }
    dump(enda);
    dump(stab);
    dump(both);
    int cnt = 0;
    REP(i,0,n) REP(j,0,s[i].size()-1) if (s[i][j] == 'A' && s[i][j+1] == 'B') ++cnt;
    dump(cnt);
    cnt += min(enda, stab);
    dump(cnt);
    enda -= min(enda, stab);
    stab -= min(enda, stab);
    if (both > 0) cnt += both + ((max(enda, stab) - min(enda, stab)) > 0) - 1;
    cout << cnt << endl;
}

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

Measured memory_bytes: 768
#include <cstdio>
#include <cstring>
using namespace std;

char pi[23333];

int main()
{
	int p; scanf("%d",&p);
	scanf("%s",pi); int l=strlen(pi);
	for(int i=0; i<l; i++) printf("%c",'A'+(pi[i]+p-'A')%26);
	return 0;
}

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

using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<>, rb_tree_tag,
//        tree_order_statistics_node_update>
//        indexed_set;


#define MP make_pair
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int((x.size())))
#define fi first
#define se second
#define REP(i, a, b) for (int (i)=(a);(i)<(b);(i)++)
#define PER(i, a, b) for (int (i)=(b)-1;(i)>=(a);(i)--)

typedef long double ld;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<PII> VPI;

//#ifndef ONLINE_JUDGE
#define dbb(x)        { cerr << #x << " = " << x << "\t";      }
#define db(x)        { dbb(x); cerr << endl; }
#define db2(x, y)    { dbb(x); dbb(y); cerr << endl; }
#define db3(x, y, z)    { dbb(x); dbb(y); dbb(z); cerr << endl; }
//#else
//#define dbb(x)		;
//#define db(x)		;
//#define db2(x,y)	;
//#define db3(x,y,z)	;
//#endif



const ll MOD = 998244353ll;

ll powmod(ll a, ll b) {
    ll res = 1;
    a %= MOD;
    assert(b >= 0);
    for (; b; b >>= 1) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
    }
    return res;
}

template<typename t1, typename t2>
inline bool upmax(t1 &a, t2 b) {
    if (a < (t1) b) {
        a = (t1) b;
        return true;
    } else return false;
}

template<typename t1, typename t2>
inline bool upmin(t1 &a, t2 b) {
    if (a > (t1) b) {
        a = (t1) b;
        return true;
    } else return false;
}

template<typename T>
inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

template<typename T>
inline T lcm(T a, T b) { return a * (b / gcd(a, b)); }

template<typename T>
inline T sqr(T a) { return a * a; }

int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
int dkx[] = {-1, -1, 1, 1, -2, -2, 2, 2};
int dky[] = {-2, 2, -2, 2, -1, 1, -1, 1};

const int INF = 1000000404;
const ll LINF = 1e18 * (1ll);
const ld PI = 3.14159265358979323846;
const ld EPS = 1e-9;

const int SQ = 318;
int timer = 0;
const int a_lot_of_test = 0;
#define N 100100


void solve() {
    ll n, a, b;
    cin >> n >> a >> b;
    if ((b - a) & 1) {

        ll f = min(b - 1, n - a);
        ll g = min(a + (b - a) / 2, n - b + 1 + (n - (a + n - b + 1)) / 2);
        cout << min(f, g) << endl;

    } else cout << (b - a) / 2 << endl;

}

int main() {

#ifdef qwerty
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    //freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    if (a_lot_of_test) cin >> t;

    for (int i = 1; i <= t; i++) {
        solve();
    }


    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream> 
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>

using namespace std;
using ll = long long;
using ull = unsigned long long;

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

#define REP(i, n) for(int i = 0; i < n; i++)
#define RREP(i, n) for(int i = n - 1; i >= 0; i--)
#define REP2(i, n, k) for(int i = 0; i < n; i += k)


int h, w, b[55][55] = {};
string s[55];

void bfs(int x, int y, int d) {
	if (x < w - 1 && s[y][x + 1] == '.' && b[y][x + 1] - 1 > d) {
		b[y][x + 1] = d + 1;
		bfs(x + 1, y, d + 1);
	}
	if (x > 0 && s[y][x - 1] == '.' && b[y][x - 1] - 1 > d) {
		b[y][x - 1] = d + 1;
		bfs(x - 1, y, d + 1);
	}
	if (y < h - 1 && s[y + 1][x] == '.' && b[y + 1][x] - 1 > d) {
		b[y + 1][x] = d + 1;
		bfs(x, y + 1, d + 1);
	}
	if (y > 0 && s[y - 1][x] == '.' && b[y - 1][x] - 1 > d) {
		b[y - 1][x] = d + 1;
		bfs(x, y - 1, d + 1);
	}
}

int main()
{
	int c[3][3];

	REP(i, 3) {
		REP(j, 3) {
			cin >> c[i][j];
		}
	}

	REP(i, 2) {
		int t = c[0][i + 1] - c[0][i];
		REP(j, 3) {
			if (t != c[j][i + 1] - c[j][i]) {
				cout << "No" << endl;
				return 0;
			}
		}

		int u = c[i + 1][0] - c[i][0];
		REP(j, 3) {
			if (u != c[i + 1][j] - c[i][j]) {
				cout << "No" << endl;
				return 0;
			}
		}
	}

	cout << "Yes" << endl;
}

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

int main() {
  int n;
  double w, h, bmi;
  char c;

  while (cin >> n >> c >> w >> c >> h) {
    bmi = w/(h*h);
    if (bmi >= 25.0) cout << n << endl;
  }

  return 0;
}

Measured memory_bytes: 1232
#n = int(input())
#n,k = map(int,input().split())
#x = list(map(int,input().split()))

li = list("abcdefghijklmnopqrstuvwxyz")

n = int(input())

memo = [50 for i in range(len(li))]
for i in range(n):
    cnt = [0 for i in range(len(li))]
    s = list(input())
    for j in range(len(s)):
        for l in range(26):
            if s[j] == li[l]:
                cnt[l] += 1

    for j in range(len(li)):
        memo[j] = min(memo[j],cnt[j])

    

for j in range(len(li)):
    for i in range(memo[j]):
        print(li[j],end="")

print()






Measured memory_bytes: 3064
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
int main(){
	int n,k;
	int sum = 0;
	int a[105];
	int b[105];
	scanf("%d",&n);
	scanf("%d",&k);
	for(int i = 1;i <= n;i++){
		scanf("%d",&a[i]);
	}
	for(int i = 1;i <= n;i++){
		b[i] = min((2 * a[i]),(k - a[i]) * 2);
		sum = sum + b[i];
	}
	printf("%d\n",sum);
}

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

signed main() {
  int n,c,k;
  string s;
  cin >> n >> k >> c >> s;

  vector<int> l(k+1,-1), r(k+1,-1);
  int cnt = 1;
  for (int i = 0; i < n; i++) {
    if(s[i] == 'o') {
      l[cnt] = i;
      i+=c;
      cnt++;
    }
    if(cnt > k) break;
  }
  cnt = k;
  for (int i = n - 1; i >= 0; i--) {
    if(s[i] == 'o') {
      r[cnt] = i;
      i-=c;
      cnt--;
    }
    if(cnt < 0) break;
  }

  for (int i = 1; i <= k; i++) {
    if(l[i] == r[i]) cout << l[i] + 1 << '\n';
  }


}

Measured memory_bytes: 5120
#include<iostream>
#include<string>
using namespace std;
int main() {
	int n,sum,memo=0;
	char ch;
	cin>>n;
	memo=n;
	while(1){
		cin>>ch;
		if(ch=='=')break;
		cin>>n;
		if(ch=='+')memo+=n;
		else if(ch=='-')memo-=n;
		else if(ch=='*')memo*=n;
		else if(ch=='/')memo/=n;
	
	}
	cout<<memo<<endl;
	return 0;
}


Measured memory_bytes: 3096
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <array>
#include <climits>

long long int solve(std::vector<long long int> H)
{
    long long int temp = 0, ans = 0;
    for (long unsigned int i = 0; i < H.size() - 1; i++)
    {
        if(H[i]>=H[i+1])
        {
            temp++;
        }
        else
        {
            ans = std::max(ans, temp);
            temp = 0;
        }
    }

    ans = std::max(ans, temp);
    return ans;
}

int main()
{
    int N; std::cin >> N;
    std::vector<long long int> H(N, 0);
    
    for(int i = 0; i < N; i++)
    {
        std::cin >> H[i];
    }
    
    long long int ans = solve(H);

    std::cout << ans << std::endl;
    return 0;
}

Measured memory_bytes: 4720
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <chrono>
#include <random>
#include <unordered_map>
#include <cassert>
#pragma GCC optimize("O3")
#pragma comment(linker, "STACK:36777216")
using namespace std;
using i64 = int64_t;
constexpr i64 MOD = 1e9 + 7;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
using vi = vector<i64>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using ii = pair<i64, i64>;

int h, w;
int b[500][500];

struct a {
    int y1, x1, y2, x2;
};

vector<a> ans;

int cnt() {
    int ret = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (b[i][j] % 2 == 0) ret++;
        }
    }
    return ret;
}

int main() {
    cin >> h >> w;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> b[i][j];
        }
    }
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (b[i][j] % 2) {
                if (j != w - 1 && b[i][j + 1] % 2) {
                    b[i][j] -= 1;
                    b[i][j + 1] += 1;
                    ans.push_back({i, j, i, j + 1});
                    continue;
                }
                if (i != h - 1 && b[i + 1][j] % 2) {
                    b[i][j] -= 1;
                    b[i + 1][j] += 1;
                    ans.push_back({i, j, i + 1, j});
                    continue;
                }
                if (j != w - 1) {
                    b[i][j] -= 1;
                    b[i][j + 1] += 1;
                    ans.push_back({i, j, i, j + 1});
                    continue;
                }
                if (i != h - 1) {
                    b[i][j] -= 1;
                    b[i + 1][j] += 1;
                    ans.push_back({i, j, i + 1, j});
                    continue;
                }
            }
        }
    }
//    cout << cnt() << endl;
    cout << ans.size() << endl;
    for (auto a: ans) {
        cout << a.y1 + 1 << " " << a.x1 + 1 << " " << a.y2 + 1 << " " << a.x2 + 1 << endl;
    }
}


Measured memory_bytes: 5104
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> a(100000),b(100000);
ll result[2][100000];
vector<ll> path[100000];

void f(int start,int no,int num){
  result[no][start]=num;
  for(int i=0;i<path[start].size();i++){
    if(result[no][path[start][i]]==0){
      f(path[start][i],no,num+1);
    }
  }
}

int main () {
    int n;
    cin >> n;
    for(int i=0;i<n-1;i++){
      int t1,t2;
      cin >> t1 >> t2 ;
      t1--;
      t2--;
      path[t1].push_back(t2);
      path[t2].push_back(t1);
    }
    f(0,0,1);
    f(n-1,1,1);
    int b=0,w=0;
    for(int i=0;i<n;i++){
      if(result[0][i]<=result[1][i]){
        b++;
      }else{
        w++;
      }
    }
    if(b>w){
      cout<<"Fennec"<<endl;
    }else{
      cout<<"Snuke"<<endl;
    }
    return 0;
}


Measured memory_bytes: 15104
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int maxn = 2e5 + 20;

ll n, dp[maxn], a[maxn], x[maxn], r[maxn];

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> x[i] >> a[i];

	dp[0] = a[0];
	for (int i = 1; i < n; i++)
	{
		if (a[i] > dp[i-1] - (x[i] - x[i-1]) + a[i])
			dp[i] = a[i];
		else
			dp[i] = dp[i-1] - (x[i] - x[i-1]) + a[i];
	}
	ll ans = 0;
	for (int i = 0; i < n; i++)
		ans = max (ans, dp[i]);
	cout << ans << endl;
	return 0;
}

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

using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define repr(i,x,n) for(int i=(x);i<(n);i++)
#define sortn(a) sort((a).begin(),(a).end())
#define sortr(a) sort((a).begin(),(a).end(),greater<int>())
#define MOD 1000000007

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

int main(){
    
    int n,k,q,a;
    cin >> n >> k >> q;
    vi count(n+1,0);
    rep(i,q){
        cin >> a;
        count[a]++;
    }

    repr(i,1,n+1){
        if(k-(q-count[i]) > 0)cout << "Yes" << endl;
        else cout << "No" << endl;
    } 
    
    return 0;
}



Measured memory_bytes: 1024
def main():
  N = int(input())
  dic = {}
  for i in range(N):
    a = int(input())
    if dic.get(a):
      dic[a] += 1
    else:
      dic[a] = 1
  ans = 0
  for val in dic.values():
    if val % 2 == 1:
      ans += 1
  print(ans)

if  __name__ == "__main__":
  main()

Measured memory_bytes: 15072
#include <algorithm>
#include <iostream> //入出力
#include <stdio.h>
#include <map>
#include <set>
#include <string>
#include <math.h> //算術演算子
#include <vector>
#include <cstdlib>
#include <queue>
#include <stack>
#include <list>
#include <iomanip> //小数点以下を表示させる(setprecision())
//#include <bits/stdc++.h>
using namespace std;
typedef long long ll; //64bit型

#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << x << " " \
                      << "(L:" << __LINE__ << ")" << '\n'
#define PRINT(V)                                   \
        {                                          \
                for (int i = 0; i < V.size(); i++) \
                {                                  \
                        cout << V[i] << " ";       \
                }                                  \
                cout << endl;                      \
        }

int gcd(int a, int b)
{
        return b ? gcd(b, a % b) : a;
}

int main()
{
        //input->compute->output//
        string s;
        cin >> s;

        int len = s.length();

        for (int mask = 0; mask < (1 << (len - 1)); mask++)
        {
                int num = s[0] - '0';
                string ans;
                ans += s[0];
                for (int i = 0; i < len - 1; i++)
                {
                        if (mask & (1 << i))
                        {
                                ans += '-';
                                num -= (s[i + 1] - '0');
                                ans += s[i + 1];
                        }
                        else
                        {
                                ans += '+';
                                num += (s[i + 1] - '0');
                                ans += s[i + 1];
                        }
                }
                if (num == 7)
                {
                        cout << ans << "=7" << endl;
                        return 0;
                }
        }

        return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

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

    vector<int64_t> a(n);
    int64_t s = 0;
    int64_t b = 1;
    for (auto&& aa : a) {
        cin >> aa;
        s += b * aa;
        b *= -1;
    }

    cout << s;
    for (auto i : irange(0L, n - 1)) {
        auto aa = a[i];
        s = 2 * (aa - s / 2);
        cout << " " << s;
    }
    cout << endl;
}


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

int main(void) {
  long long N, K, S;
  cin >> N >> K >> S;
  for (int i = 0; i < K; i++) {
    cout << S << " ";
  }
  for (int i = K; i < N; i++) {
    cout << (S + 1) % ((long long)(1e9)) << " ";
  }
  return 0;
}

Measured memory_bytes: 1280