akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <math.h>
#include <string>
#include <numeric>
#include <queue>
#include <cstdio>
#include <cstring>
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define rep1(i,n) for(ll i=1;i<n;++i)
#define mrep(i,n) for(ll i=n;i>=0;--i)
#define all(a) (a).begin(),(a).end()
#define vl vector<ll>
#define vvl vector<vector<ll> >
#define vb vector<bool>
#define vvb vector<vector<bool> >
#define pl pair<ll,ll>
#define inf 1001001001001001000
#define mod 1000000007
//#define mod 998244353
#define pi 3.1415926535
using namespace std;
struct __INIT{
    __INIT(){
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout<<fixed<<setprecision(15);
    }
}__init;

ll d;


pl f(vvl s,vl c,vl last,ll depth,ll hukasa){
    if(hukasa >= 3 || depth >= d) return {0,0};
    ll ret = -inf;
    ll retind = 0;
    rep(i,26){
        ll minus = 0;
        rep(j,26){
            if(j != i) minus += c[j]*(depth-last[j]);
        }
        ll moto = last[i];
        last[i] = depth;
        pl saki = {0,0};
        if(depth >= d-3) saki = f(s,c,last,depth+1,hukasa+1);
        last[i] = moto;
        if(ret < s[depth][i]-minus+saki.second){
            ret = s[depth][i]-minus+saki.second;
            retind = i;
        }
    }
    return {retind,ret};
}

void score(vvl s,vl c,vl t){
    vl last(26);
    ll ans = 0;
    rep(i,d){
        ans += s[i][t[i]];
        ll minus = 0;
        last[t[i]] = i;
        rep(j,26) minus += c[j]*(i-last[j]);
        ans -= minus;
    }
    cout<<ans<<endl;
}

int main(){
    cin>>d;
    vl c(26);
    rep(i,26) cin>>c[i];
    vvl s(d,vl(26));
    rep(i,d) rep(j,26) cin>>s[i][j];
    vl last(26,0);
    vl t(d);
    rep(i,d){
        ll tmp = f(s,c,last,i,0).first;
        last[tmp] = i;
        cout<<tmp+1<<endl;
        t[i] = tmp;
    }
    //score(s,c,t);
    return 0;
}


Measured memory_bytes: 3940
#include <iostream>

using namespace std;

int main()
{
    long long int N = 0,A = 0,B = 0;
    cin >> N >> A >> B;
    long long int count = N /(A+B);
    long long int tmp = N - count*(A+B); 
    if(tmp < A){
        cout << (A*count) + tmp << endl;
    }
    else{
        cout << (A*count) + A << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<set>
using namespace std;
int main() {
    int q;
    cin >> q;

    long A = 0, B = 0;
    
    multiset<int> ls, rs;

    while (q--) {
        int flag;
        cin >> flag;
        flag--;
        if (flag) {
            cout << *ls.rbegin() << ' ' << A + B << endl;
        } else {
            int a, b;
            cin >> a >> b;

            int precenter = a;
            if(ls.size() != 0) precenter = *ls.rbegin();

            B += b;

            if (ls.size() == 0) ls.insert(a);
            else if (a <= *ls.rbegin()) {
                ls.insert(a);
                if (ls.size() - 1 > rs.size()) {
                    rs.insert(*ls.rbegin());
                    auto itr = ls.end();
                    itr--;
                    ls.erase(itr);
                }
            } else {
                rs.insert(a);
                if (ls.size() < rs.size()) {
                    ls.insert(*rs.begin());
                    rs.erase(rs.begin());
                }
            }

            A += abs(a - *ls.rbegin());
            if(ls.size() == rs.size()) A += precenter - *ls.rbegin();
        }
    }
}


Measured memory_bytes: 9600
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long int ll;
typedef vector<pair<ll,ll> > Q;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
const ll inf=1e9+7;

int n;

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

  int cnt=0,tmp=1,ans;
  bool flag=false;
  rep(i,n){
    tmp=a[tmp-1];
    cnt++;

    if(tmp==2){
      flag=true;
      ans=cnt;
      break;
    }
  }

  if(flag) cout<<ans;
  else cout<<-1;
  cout<<endl;
}

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

int main() {
  int N;
  cin >> N;
  if(N / 10 % 111 == 0 || (N - N / 1000 * 1000) % 111 == 0) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    ll n, t, rock, scissors, paper;
    string s;
    cin >> n >> t >> rock >> scissors >> paper >> s;
    vector<vector<char>> hands(t);
    for (ll i = 0; i < n; i++)
    {
        hands[i % t].emplace_back(s[i]);
    }
    ll ans = 0;
    for (ll i = 0; i < t; i++)
    {
        ll cnt = 0;
        for (ll j = 0; j < hands[i].size(); j++)
        {
            if (j == 0)
            {
                hands[i][0] == 'r' ? ans += paper : hands[i][0] == 's' ? ans += rock : ans += scissors;
            }
            else if (j != 0 && hands[i][j] == hands[i][j - 1] && cnt == 0){
                cnt = 1;
            }
            else if ((j != 0 && hands[i][j] == hands[i][j - 1] && cnt == 1) || hands[i][j] != hands[i][j - 1]){
                hands[i][j] == 'r' ? ans += paper : hands[i][j] == 's' ? ans += rock : ans += scissors;
                cnt = 0;
            }
        }
    }
    cout << ans << endl;
}

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

int main(){
    int H,R;
    cin>>H>>R;

    if(H + R > 0) cout<<"1"<<endl;
    else if(H + R == 0) cout<<"0"<<endl;
    else if(H + R < 0) cout<<"-1"<<endl;


 return 0;
}



Measured memory_bytes: 3096
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;

public class Main {
	static int N;
	static int K;
	static int a;
	static int b;
	public static void main(String[]args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		K=sc.nextInt();
		List<Integer> list =new ArrayList<Integer>();
		for(int n=0;n<K;n++) {
			int d=sc.nextInt();
			for(int m=0;m<d;m++) {
				list.add(sc.nextInt());
			}
		}
		list=new ArrayList<Integer>(new HashSet<>(list));
		a=list.size();
		b=N-a;
		System.out.println(b);
	}
}


Measured memory_bytes: 46320
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N 200000


int main(){
	long long n, k;
	long long x, y, z;
	long long s, ans;
	bool v = true;
	ans = 0;
	scanf("%lld %lld", &n, &k);
	x = n / k;
	n += (k / 2);
	y = n / k;

	ans += (x*x*x);
	if (k % 2 == 0){
		ans += (y*y*y);
	}

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


	return 0;
}

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

int main(void){
    int h, w, diag;
    int bh, bw;
    while(cin >> h >> w && h) {
        int mind = numeric_limits<int>::max();
        bh = numeric_limits<int>::max();
        diag = h*h + w*w;
        for(int i=1; i<151; ++i) {
            for(int j=i+1; j<151; ++j) {
                int t = i*i+j*j;
                if(t > diag || (t==diag && i>h)) {
                    if(t < mind || (t==mind && i<bh)) {
                        mind = t;
                        bh = i;
                        bw = j;
                    }
                    break;
                }
            }
        }
        cout << bh << " " << bw << endl;
    }
}

Measured memory_bytes: 1160
// https://atcoder.jp/contests/abcXXX/tasks/abcXXX_x

#include <iostream>
#include <vector>
#include <tuple>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pll = pair<ll, ll>;

static const ll INF = 1001001001;

void debug_out() {};
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 1
#endif

struct C1 {
    vector<ll> v_{};
    explicit C1(vector<ll> v) : v_(move(v)){}
    explicit C1(ll N, vector<ll> r, vector<tuple<ll, ll, ll>> v) {}
    ll resolve() {
        return 0;
    }
};

int main() {
    ll A, B;
    cin >> A >> B;
    cout << std::max(0LL, A - 2 * B) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>  // g++ -std=c++14 -o a a.cpp

using namespace std;

typedef pair<int, int> P;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;

int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

__attribute__((constructor))
void initial() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

int main() {
    int N;
    cin >> N;
    set<string> gachas;
    rep(i, N) {
        string Si;
        cin >> Si;
        gachas.insert(Si);
    }
    cout << gachas.size() << endl;
}


Measured memory_bytes: 19140
def getKth(x, a, k):
    if(k < a):
        return k
    return k + 1
def getRKth(x, a, k):
    if(x < a):
        return x - k + 1
    if(k < (x - a)):
        return x - k + 1
    return x - k
def NB(x, b):
    if(x < b):
        return x
    return x + 1
def f(x, a, b):
    half = (x + 1) / 2
    rep = 0
    for delta in xrange(-50, 51):
        if(half + delta >= 1 and half + delta <= x):
            rep = max(rep, getKth(x, a, half + delta) * getRKth(NB(x, b), b, half + delta))
    half = b - a
    for delta in xrange(-50, 51):
        if(half + delta >= 1 and half + delta <= x):
            rep = max(rep, getKth(x, a, half + delta) * getRKth(NB(x, b), b, half + delta))
    half = NB(x, b) - b
    for delta in xrange(-50, 51):
        if(half + delta >= 1 and half + delta <= x):
            rep = max(rep, getKth(x, a, half + delta) * getRKth(NB(x, b), b, half + delta))
    return rep
q = int(raw_input())
while(q > 0):
    a, b = map(int, raw_input().split())
    if(a > b):
        a, b = b, a
    lo = 1
    hi = 10**19
    res = 0
    # print f(1, a, b)
    # print f(2, a, b)
    # print f(3, a, b)
    # print getKth(2, a, 1), getRKth(NB(2, b), b, 1)
    # print getKth(2, a, 2), getRKth(NB(2, b), b, 2)
    while(lo <= hi):
        mid = (lo + hi)/2
        if(f(mid, a, b) < a * b):
            lo = mid + 1
            res = mid
        else:
            hi = mid - 1
    print res
    q -= 1


Measured memory_bytes: 2696
# -*- coding: utf-8 -*-
"""
Time to Study
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0238

"""
import sys


def solve(t):
    n = int(input())
    for _ in range(n):
        s, f = map(int, input().split())
        t -= (f-s)
    return 'OK' if t <= 0 else t


def main(args):
    while True:
        t = int(input())
        if t == 0:
            break
        ans = solve(t)
        print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


Measured memory_bytes: 5620
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx,avx2,fma")

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

#define ll long long
#define ull unsigned long long
#define dd double
#define ld long double
#define sl(n) scanf("%lld", &n)
#define si(n) scanf("%d", &n)
#define sd(n) scanf("%lf", &n)
#define pll pair <ll, ll>
#define pii pair <int, int>
#define mp make_pair
#define pb push_back
#define all(v) v.begin(), v.end()
#define inf (1LL << 62)
#define loop(i, start, stop, inc) for(ll i = start; i <= stop; i += inc)
#define for1(i, stop) for(ll i = 1; i <= stop; ++i)
#define for0(i, stop) for(ll i = 0; i < stop; ++i)
#define rep1(i, start) for(ll i = start; i >= 1; --i)
#define rep0(i, start) for(ll i = (start-1); i >= 0; --i)
#define ms(n, i) memset(n, i, sizeof(n))
#define casep(n) printf("Case %lld:", ++n)
#define pn printf("\n")
#define pf printf
#define EL '\n'
#define fastio std::ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

const ll sz = 2e5 + 10, block = 62;
ll pw1[sz], pw2[sz], dp[sz];
char s[sz];

ll calc(ll n)
{
    if(dp[n] != -1) return dp[n];
    if(n == 0) return 0;
    ll one = __builtin_popcount(n);

    return 1 + calc(n % one);
}

int main()
{
    ms(dp, -1);
    dp[0] = 0;
    for(ll i = 1; i < sz; i++) {
        dp[i] = calc(i);
    }

    ll n;
    cin >> n;
    scanf("%s", s);

    ll one = 0;
    for0(i, n) {
        ll v = s[i] - '0';
        one += v;
    }

    const ll mod1 = one + 1, mod2 = one - 1;

    ll val1 = 0, val2 = 0;

    if(mod1 != 0) pw1[0] = 1 % mod1;
    if(mod2 != 0) pw2[0] = 1 % mod2;

    for1(i, n) {
        if(mod1 != 0) pw1[i] = (pw1[i-1] * 2LL) % mod1;
        if(mod2 != 0) pw2[i] = (pw2[i-1] * 2LL) % mod2;
    }

    for0(i, n) {
        ll v = s[i] - '0';

        if(mod1 != 0) val1 = (val1 * 2 + v) % mod1;
        if(mod2 != 0) val2 = (val2 * 2 + v) % mod2;
    }

    for0(i, n) {

        ll pos = n - i -1, val = -1;
        if(s[i] == '0') {
            if(mod1 != 0) val = (val1 + pw1[pos]) % mod1;
        }
        else {
            if(mod2 != 0) {
                val = (val2 - pw2[pos]) % mod2;
                if(val < 0) val += mod2;
            }
        }

        if(val == -1) pf("0\n");
        else pf("%lld\n", 1 + dp[val]);
    }

    return 0;
}



Measured memory_bytes: 8580
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long int64;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const long long  INFL = 1e18;
const int MOD = 1000000007;
const int MAX = 210000;
const int MAX_NUM = 999999999;
void solve() {
	int n; cin >> n;
	vector<int> a;
	for (int i = 0; i < n; ++i) {
		auto it = a.begin();
		int ta; cin >> ta;
		if (n % 2 == 0) {
			if (i % 2 == 0) {
				a.push_back(ta);
			} else {
				a.insert(it, ta);
			}
		} else {
			if (i % 2 == 0) {
				a.insert(it, ta);
			} else {
				a.push_back(ta);
			}
		}
	}
	for (int i = 0; i < a.size(); ++i) {
		cout << a[i] << endl;
	}
	return;
}
int main() {
	solve();
	return 0;
}

Measured memory_bytes: 3060
#include <iostream>
#include <stdio.h>
using namespace std;
int main() {
    int n;
    scanf("%d",&n);
    int a[n+1];
    int a4=0,a2=0,a1=0;
    for (int i = 0;i<n;i++) {
        scanf("%d",&a[i]);
    }
    for (int i = 0;i<n;i++) {
        if (a[i]%4==0) {
            a4++;
        }
        else if(a[i]%2==0)
            a2++;
        else
            a1++;
    }
    if (a2>0) {
        if (a4>=a1)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    else
        if(a4>=a1-1)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
int main() {
int a[3];
int Put;
std::cin >> a[0] >> a[1] >> a[2];
for(int i = 0; i < 2; i++){
if(a[i+1] < a[i]){
Put = a[i];
a[i] = a[i+1];
a[i+1] = Put;
}
}
if(a[1] < a[0]){
Put = a[0];
a[0] = a[1];
a[1] = Put;
}
std::cout << a[0] << ' ' << a[1] << ' ' << a[2] << std::endl;
}

Measured memory_bytes: 3088
#include <stdio.h>

int main(int argc, const char * argv[]) {
    int N;
    scanf("%d",&N);
    char s[N];
    scanf("%s",s);
    int i,j;
    int sum=0;
    for(i=0;i<=N;i++){
        sum++;
        if(s[i]==s[i+1]){
        for(j=i+1;j<=N;j++){
            i++;
            if(s[j]==s[j+1]){
                continue;
            }else{
                break;
            }
        }
        }
    }
    printf("%d",sum-1);
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
using namespace std;
int n, a[111], ans = ~0U >> 1;
inline int sqr(int x) {
	return x * x;
}
inline int calc(int x) {
	int res = 0;
	for (int i = 1; i <= n; ++i)
		res += sqr(a[i] - x);
	return res;
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = -100; i <= 100; ++i)
		ans = min(ans, calc(i));
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
answers = []
last_input_op = nil

def calc(a, b, op)
  if op == "+"
    return a + b
  elsif op == "-"
    return a - b
  elsif op == "*"
    return a * b
  elsif op == "/"
    return a / b
  end
end

while true
  input_value = []
  input_value = gets.chomp.split
  a = input_value[0].to_i
  op = input_value[1]
  b = input_value[2].to_i
  if op == "?"
    break
  end
  answers.push(calc(a, b, op))
end

puts answers.join("\n")

Measured memory_bytes: 8596
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] line = br.readLine().split(" ");
		int N = Integer.parseInt(line[0]);
		int L = Integer.parseInt(line[1]);
		String[] S = new String[N];
		for(int i=0;i<N;i++){
			S[i] = br.readLine();
		}
		Arrays.sort(S);
		
		for(String s : S){
			System.out.print(s);
		}
		System.out.println();
	}
}


Measured memory_bytes: 8020
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cassert>
#include <functional>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL << 60;
const int n_max = 110;
const int sum_v_max = 100100;


// 入力
int n;
long long w, weight[n_max], value[n_max];

// DPテーブル
long long dp[n_max][sum_v_max] = {0};

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

  for (int i = 0; i < n_max; i++) for (int j = 0; j < sum_v_max; j++) dp[i][j] = INF;

  dp[0][0] = 0;

  // DPループ
  for (int i = 0; i < n; ++i) {
    for (int sum_v = 0; sum_v <= sum_v_max; ++sum_v) {

      // i 番目の品物を選ぶ場合
      if (sum_v - value[i] >= 0) {
          chmin(dp[i+1][sum_v], dp[i][sum_v - value[i]] + weight[i]);
      }

      // i 番目の品物を選ばない場合
      chmin(dp[i+1][sum_v], dp[i][sum_v]);
    }
  }

  // 最適値の出力
  long long res = 0;
  for (int sum_v = 0; sum_v < sum_v_max; sum_v++){
    if(dp[n][sum_v] <= w) res = sum_v;
  }
  cout << res << endl;

  return 0;
}


Measured memory_bytes: 86272
#include <bits/stdc++.h>
using namespace std;
const int MM=100013;
int dp[MM],T[MM];
int main()
{
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>T[i];
    }
    dp[2]=abs(T[2]-T[1]);
    for(int i=3;i<=n;i++)
    {
        dp[i]=min(dp[i-1]+abs(T[i-1]-T[i]),dp[i-2]+abs(T[i-2]-T[i]));
    }
    cout<<dp[n]<<endl;
    return 0;
}


Measured memory_bytes: 1024
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S, W = MAP()

if W >= S:
    print('unsafe')
else:
    print('safe')


Measured memory_bytes: 10652
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define RFOR(i, a, b) for(int i=(b-1);i>=(a);i--)
#define REP(i, n) for(int i=0; i<(n); i++)
#define RREP(i, n) for(int i=(n-1); i>=0; i--)
#define REP1(i, n) for(int i=1; i<=(n); i++)
#define RREP1(i, n) for(int i=(n); i>=1; i--)
#define ALL(a) (a).begin(),(a).end()
#define UNIQUE_SORT(l) sort(ALL(l)); l.erase(unique(ALL(l)), l.end());
#define CONTAIN(a, b) find(ALL(a), (b)) != (a).end()
#define out(...) printf(__VA_ARGS__)
#if DEBUG
#define debug(...) printf(__VA_ARGS__)
#else
#define debug(...) /* ... */
#endif
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

void solve();
signed main()
{
#if DEBUG
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

/*================================*/
#if DEBUG
#define SIZE 2223450
#else
#define SIZE 2223450
#endif

int N,Q,K;
string X;
// -1したとき+1したとき,2^jを割った→あまり
int DP[2][SIZE];

int calc(int n) {
    bitset<30> b(n);
    int ret = 0;
    while(n) {
        n %= b.count();
        b = bitset<30>(n);
        ret++;
    }
    return ret;
}
int M[2];
int v[2] = {0,0};

void solve() {
    cin>>N>>X;
    int cnt = 0;
    REP(i,N)if (X[i]=='1')cnt++;
    REP(i,2) {
        int m = (i==0) ? cnt-1 : cnt+1;
        M[i] = m;
        if (m <= 0) continue;
        DP[i][0] = 1%m;
        REP(j,N) {
            (DP[i][j+1] = DP[i][j]*2) %= m;
        }
    }
    reverse(ALL(X));
    REP(k,N) {
        if (X[k]=='1') {
            REP(i,2) v[i] += DP[i][k];
        }
    }
    RREP(k,N) {
        if (X[k]=='1') {
            int m = M[0];
            if (m<=0) {
                out("0\n");
            } else {
                int val = (v[0] - DP[0][k] + m) % m;
                out("%lld\n",calc(val)+1);
            }
        } else {
            int m = M[1];
            int val = (v[1] + DP[1][k]) % m;
            out("%lld\n",calc(val)+1);
        }
    }
}


Measured memory_bytes: 6992
#include <iostream>
#include <string>
#include <set>
using namespace std;
typedef long long ll;

int main(void) {
  ll i, n;
  cin >> n;
  string t;
  set<string> s;
  for(i = 0; i < n; ++i) cin >> t, s.insert(t);
  cout << s.size();
  return 0;
}

Measured memory_bytes: 19188
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define mod 1000000007
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

ll n;
ll a[30][30];
ll dp[30][ll(1<<21)];

ll solve(ll cm, ll mask){
  if(cm>n)return 1;
  if(dp[cm][mask]!= -1)return dp[cm][mask];
  ll ways =0;
  for(ll i=1;i<=n; i++){
    if(a[cm][i]==0)continue;
    if(mask&1<<(i-1))continue;
    ways += solve(cm+1,mask|1<<(i-1))%mod;
  }
  dp[cm][mask] = ways%mod;
  return dp[cm][mask]%mod;
}

int main(){
  fastio
  cin>>n;
  for(ll i=1; i<=n; i++){
    for(ll j=1; j<=n; j++){
      cin>>a[i][j];
    }
  }
  memset(dp,-1,sizeof(dp));
  cout<<solve(1ll,0ll)<<"\n";
  return 0;
}

Measured memory_bytes: 495172
import sys
input=sys.stdin.readline
from heapq import heappush, heappop

def dijkstra(x,Route):
    n=len(Route)
    D=[float('inf')]*n
    D[x]=0
    hq=[(0,x)]
    while hq:
        c,u=heappop(hq)
        if D[u]<c:
            continue
        for v,cost in Route[u]:
            if D[u]+cost<D[v]:
                D[v]=D[u]+cost
                heappush(hq,(D[v],v))
    return D

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Edges=[[] for _ in range(n+2)]
for i in range(n+1):
    for j in range(i+1,n+2):
        d=dist(V[i],V[j])
        Edges[i].append((j,d))
        Edges[j].append((i,d))
print(dijkstra(0,Edges)[-1])

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

using namespace std;


void solve() {
    int n, k;
    cin >> n >> k;
    map<int, int> mp;
    for (int _ = 0; _ < n; _++) {
        int x;cin >> x;
        mp[x]++;
    }
    if ((int)mp.size()<=k) {
        cout << 0; return;
    }
    vector<int> a;
    for (auto& p: mp) {
        a.emplace_back(p.second);
    }
    sort(a.begin(), a.end());
    int m = a.size();
    int res = 0;
    for (int i = 0; i < m-k; i++) {
        res += a[i];
    }
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


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

int main(){
    int N;
    cin >> N;
    map<string, int> mp;
    rep(i, N){
        string s;
        cin >> s;
        mp[s]++;
    }
    /*int max = 0;
    for(const auto& x : mp){
        int v = x.second;
        if(v > max){
            max = v;
        }
    }*/
    cout << mp.size() << endl;
return 0;}

Measured memory_bytes: 19176
S = input()
S = list(S)

formar = S[0]+S[1]
latter = S[2]+S[3]

if int(formar) > 12 and int(latter) > 12:
    print("NA")
elif int(formar) <= 12 and int(latter) <= 12:
    if formar == "00" and not latter == "00":
        print("YYMM")
    elif latter == "00" and not formar == "00":
        print("MMYY")
    elif formar == "00" and latter == "00":
        print("NA")
    else:
        print("AMBIGUOUS")
elif int(formar) > 12:
    if latter == "00":
        print("NA")
    else:
        print("YYMM")
else:
    if formar == "00":
        print("NA")
    else:
        print("MMYY")


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

int main(){
  int n;
  ll a[100006];
  ll sum = 0;

  scanf("%d", &n);

  int i;
  for(i = 1;i <= n;i++){
    scanf("%lld", &a[i]);
    sum += a[i];
  }

  ll sum2 = 0;

  for(i = 2;i <= n - 1;i += 2){
    sum2 += a[i];
  }

  ll ans[100006];

  ans[1] = sum - 2*sum2;

  for(i = 1;i < n;i++){
    ans[i + 1] = 2*a[i] - ans[i];
  }

  for(i = 1;i <= n;i++) printf("%lld\n", ans[i]);
  return 0;
}

Measured memory_bytes: 2816
#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;cin>>n;
  string s;cin>>s;
  int ans=0;
  for(int i=1;i<n;i++){
    int cnt=0;
    for(char c='a';c<='z';c++){
      bool left=false,right=false;
      for(int j=0;j<i;j++)
        if(s[j]==c)left=true;
      for(int j=i;j<n;j++)
        if(s[j]==c)right=true;
      if(left&&right)cnt++;
    }
    ans=max(ans,cnt);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3584
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val s = readLine()!!

    var slime = 0
    var prev = '0'
    for (c in s) {
        if (c != prev) {
            slime++
            prev = c
        }
    }
    println(slime)
}

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

int main() {
  string s;
  cin >> s;
  int ans = 1e9;

  for (int i = 0; i < s.size() - 2; i++) {
    int n;
    n = abs(753 - ((s[i] - '0')* 100 + (s[i + 1] - '0')  * 10 + (s[i + 2] - '0')));
    ans = min(ans, n);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
N, A, B, C, D = map(int, input().split())
S = input()
s = [0]
for i in range(N):
    if S[i] == '.':
        s.append(0)
    else:
        s.append(1)
if C < B and B < D: #ACBDの順番
    flag = 0
    for i in range(C - A):
        if s[A + i] == 1 and s[A + i + 1] == 1:
            flag = 1
            break
    if flag == 0:
        for i in range(D - B):
            if s[B + i] == 1 and s[B + i + 1] == 1:
                flag = 1
                break
    if flag == 1:
        print('No')
    else:
        print('Yes')
elif B < C and C < D: # ABCDの順番
    flag = 0
    for i in range(D - B):
        if s[B + i] == 1 and s[B + i + 1] == 1:
            flag = 1
            break
    if flag == 0:
        for i in range(B - A):
            if s[A + i] == 1 and s[A + i + 1] == 1:
                flag = 1
                break
    if flag == 1:
        print('No')
    else:
        print('Yes')
else: #ABDCの順番
    flag = 0
    for i in range(D - B + 1):
        if s[B + i - 1] == 0 and s[B + i] == 0 and s[B + i + 1] == 0:
            flag = 1
            break
    if flag == 1:
        for i in range(C - A):
            if s[A + i] == 1 and s[A + i + 1] == 1:
                flag = 0
                break
    if flag == 1:
        print('Yes')
    else:
        print('No')


Measured memory_bytes: 5044
import sys
from itertools import accumulate
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
b = list(map(int,sys.stdin.readline().split()))
s = 0
for i in range(n):
    if a[i] >= b[i]:
        s += a[i]-b[i]
print(s)


Measured memory_bytes: 3060
#include <iostream>

using namespace std;

int main() {

  int n, s = 0, m = 0, l = 0;
  cin >> n;
  for(int i = 1;i <= n;i++){
    cin >> l;
    s += l;
    m = max(m, l);
  }
  cout << s - m + (m / 2);
  return 0;
}


Measured memory_bytes: 3560
#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
template<typename T> void read(T &num){
	char c=getchar();T f=1;num=0;
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){num=(num<<3)+(num<<1)+(c^48);c=getchar();}
	num*=f;
}
template<typename T> void qwq(T x){
	if(x>9)qwq(x/10);
	putchar(x%10+'0');
}
template<typename T> void write(T x){
	if(x<0){x=-x;putchar('-');}
	qwq(x);putchar('\n');
}
int l[110];

int main(){
	int n;read(n);
	rep(i,1,n)read(l[i]);
	
	int ans=0;
	rep(i,1,n){
		rep(j,i+1,n){
			rep(k,j+1,n){
				if(l[i]==l[j]||l[j]==l[k]||l[i]==l[k])continue;
				int nop=max(max(l[i],l[j]),l[k]);
				ans+=(l[i]+l[j]+l[k]-nop>nop);
			}
		}
	}
	write(ans);
	return 0;
}

Measured memory_bytes: 3632
import math

def Next(): return input()
def NextInt(): return int(Next())
def NextInts(): return map(int,input().split())
def Nexts(): return map(str,input().split())
def NextIntList(): return list(map(int,input().split()))
def RowInts(n): return [input() for i in range(n)]

r = NextInt()
print(r*2*math.pi)

Measured memory_bytes: 9192
#include <iostream>
#include <string>
#include <stdio.h>
#include <cmath>
#include <cfloat>
#include <algorithm>
#include <numeric>
using namespace std;

const double PI=acos(-1);

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

    int a = 0, b = 0, t;
    int l[100];
    fill(l, l, 0);
    for(int i = 0; i < n; i++){
        cin >> t;
        l[i] = t;
    }
    sort(l, l+n, greater<int>());
    for(int i = 0; i < n; i++){
        if(i%2 == 0) a += l[i];
        else b += l[i];
    }
    cout << a-b << endl;
    return 0;
}

Measured memory_bytes: 256
s=input()
k=int(input())
if len(set(list(s)))==1:print((len(s)*k)//2);exit()
t=[1]
for i in range(1,len(s)):
  if s[i-1]==s[i]:t[-1]+=1
  else:t.append(1)
a=0
for i in t:a+=(i//2)*k
if s[0]==s[-1]:
  if t[0]%2==t[-1]%2==1:a+=k-1
print(a)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;cin>>n;
  vector<int> v[n+1];
  for(int i=0;i<n-1;i++){
    int a,b;cin>>a>>b;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  if(n%2){
    cout<<"First"<<endl;
    return 0;
  }
  queue<int> q;
  bool used[n+1];
  fill(used,used+n+1,false);
  int d[n+1];
  int cnt[n+1];
  fill(cnt,cnt+n+1,0);
  int ko[n+1];
  fill(ko,ko+n+1,0);
  for(int i=1;i<=n;i++){
    if(v[i].size()==1){
      q.push(i);
      used[i]=true;
      d[i]=0;
    }
    cnt[i]=v[i].size();
  }
  while(q.size()>0){
    int now=q.front();
    q.pop();
    for(int i=0;i<v[now].size();i++){
      int ne=v[now][i];
      
      if(used[ne])continue;
      cnt[ne]--;
      if(d[now]==0)ko[ne]++;
      if(ko[ne]>=2){
        cout<<"First"<<endl;
        return 0;
      }
      if(cnt[ne]==1){
        used[ne]=true;
        q.push(ne);
        if(ko[ne]==1)d[ne]=1;
        else d[ne]=0;
      }
    }
  }
  cout<<"Second"<<endl;
}
      
      


Measured memory_bytes: 7296
#include<iostream>
#include<cmath>
#include<string>
using namespace std;
int main(){
	string a;
	cin>>a;
	if(a[0]==a[1]&& a[2]==a[3]&& a[0]!=a[2]){
		cout<<"Yes";
	}
	else if(a[0]==a[2]&& a[1]==a[3]&& a[0]!=a[3]){
		cout<<"Yes";
	}
	else if(a[0]==a[3]&& a[2]==a[1] && a[0]!=a[2]){
		cout<<"Yes";
	}
	else {
		cout<<"No";
	}
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int n;
  cin>>n;
  string s,t,u;
  cin>>s;
  
  int ans=0;
  
  for(int i=0;i<s.length()-1;i++){
    t=s.substr(0,i+1);
    u=s.substr(i+1);
    int tmpans=0;
    int flag=0;
    
    for(char i='a';i<='z';i++){
      for(int j=0;j<t.length();j++){
        if(t.at(j)==i){
          flag=1;
          break;
        }
        flag=0;
      }
      
      for(int k=0;k<u.length();k++){
        if((u.at(k)==i)&&(flag)){
          tmpans++;
          //cout<<i;
          flag=0;
          break;
          
        }
      }
    //cout<<t<<" "<<u<<" "<<ans<<" "<<tmpans<<endl;
    }
    ans=max(ans,tmpans);
  }
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho10
#define ll long long int
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#define sz size
#define f first
#define s second
#define pb push_back
#define er erase
#define in insert
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 1000000007
#define PI 3.14159265359
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll n;
string s;
map<string,ll>m;
int32_t main(){
CODE_START;
cin>>n;
ll ans=0;
for(ll i=0;i<n;i++)
{
    cin>>s;
    if(m[s]==0){
        ans++;
    }
    m[s]++;
}
cout<<ans<<endl;
}




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

using namespace std;

#define int         long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)

void solve()
{
    int n, w, i, j, maxVal = 0;
    cin>>n>>w;
    vector<int> val(n), wt(n);
    for(i = 0; i < n; i++)
    {
        cin>>wt[i]>>val[i];
        maxVal += val[i];
    }
    vector<int> dp(maxVal+1, 1e12 + 1); // minimum weight to attain that value
    dp[0] = 0;
    for(int item = 0; item < n; item++)
        for(int value = maxVal; value >= 0; value--)
            if(value>=val[item])
                dp[value] = min(dp[value], dp[value-val[item]] + wt[item]);
    for(i = maxVal; i >= 0; i--)
        if(dp[i]<=w && dp[i]!=-1)
        {
            cout<<i<<endl;
            break;
        }
}


signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc;
	tc = 1;
    // cin>>tc;
    while(tc--)
        solve();

    return 0;
}


Measured memory_bytes: 1024
q = int(input())
lr = []
for i in range(q):
    lr.append(list(map(int, input().split())))


def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1
    found = False
    while first <= last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found


def is_prime(num):
    i = 2
    while i ** 2 <= num:
        if num % i == 0:
            return False
        i += 1
    return True


primes = []
for i in range(2, 10 ** 5 + 1):
    if is_prime(i):
        primes.append(i)

like_2017 = []
count = [0 for _ in range(10 ** 5)]
for i in range(len(primes)):
    if binarySearch(primes, primes[i] * 2 - 1):
        like = 2 * primes[i] - 1
        count[like] += 1
for i in range(len(count) - 1):
    count[i + 1] += count[i]
for i in range(q):
    print(count[lr[i][1]] - count[lr[i][0] - 1])


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

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

    ll ans = 0;

    // vector<int> when(M, -1);
    ll when[M];
    rep(i, M) when[i] = -1;
    ll pos = X;
    ll num = 1;

    while(when[pos] == -1){
        when[pos] = num;
        ans += pos;

        // cout << pos << endl;

        if(num == N){
            cout << ans << endl;
            return 0;
        }

        pos = (pos * pos) % M;
        num++;
    }

    ll st = when[pos];
    // cout << "st: "<< st << endl;
    ll period = num - when[pos];
    // cout << "period: "<< period << endl;

    ll beforeans = 0;
    // vector<ll> periodans(period, 0);
    ll periodans[period];
    rep(i, period) periodans[i] = 0;


    rep(i, M){
        if (when[i] != -1){
            if (when[i] < st){
                beforeans += i;
            }else{
                for(ll j = when[i]; j < st + period; j++){
                    periodans[j-st] += i;
                }
            }
        }
    }
    // cout << "beforeans: "<< beforeans << endl;
    // cout << "periodans[0]: "<< periodans[0] << endl;

    ll cnt = N - (st-1);
    ans = beforeans + (cnt / period) * periodans[period - 1];

    if (cnt % period != 0){
        ans += periodans[cnt % period - 1];
    }
    
    cout << ans << endl;

    return 0;
}

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

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

typedef long long ll;
const ll MOD = 1e9 + 7;
const int MAX_N = 20;

int main() {
  int N;
  std::cin >> N;
  std::vector<int> A(N), B(N), C(N - 1);
  rep(i, N) {
    std::cin >> A[i];
    --A[i];
  }
  rep(i, N) std::cin >> B[i];
  rep(i, N - 1) std::cin >> C[i];

  int ans = 0, last = -2;
  rep(i, N) {
    ans += B[A[i]];
    if(A[i] == last + 1) ans += C[last];
    last = A[i];
  }
  std::cout << ans << '\n';
}


Measured memory_bytes: 256
/*
    Ujjawal Pabreja [cuber_coder]
*/
#include <bits/stdc++.h> 
#include <functional> 
using namespace std;
#define speed_cubing    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll              long long
#define ld              long double
#define rep(i,a)        for(ll i = 0 ; i < a ; i++)
#define repe(i,a,b)     for(ll i = a ; i < b ; i++)
#define bac(i,a)        for(ll i = a ; i >= 0 ; i--)
#define bace(i,a,b)     for(ll i = a ; i >= b ; i--)
#define pb              push_back
#define in              insert
#define ff              first
#define ss              second
#define setbit(x)       __builtin_popcountll(x)
#define init(c,a)       memset(c,a,sizeof(c))
#define all(c)          c.begin(),c.end()
#define sz(c)           (ll)c.size()
#define lb              lower_bound
#define ub              upper_bound
#define maxe            *max_element
#define mine            *min_element
#define rev             reverse
#define Y				"YES"
#define N 				"NO"
#define endl            "\n"
#define debug(x)        cout << #x << " : " << x << endl;
const ll inf = 1e18;  
const ll mod = 1e9 + 7;
const ll MOD = 998244353;
const ll MAX = 2e5 + 1;

// ====== BigInt begins ======
// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
// ====== BigInt ends ======

// ====== PBDS begins ======
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, 
//         tree_order_statistics_node_update> 
//         pbds; 
// ====== PBDS ends ======

// ====== Useful functions begin ======
inline ll add(ll a,ll b) {return ((a % mod) + (b % mod)) % mod;}
inline ll sub(ll a,ll b) {return ((a % mod) - (b % mod) + mod) % mod;}
inline ll mul(ll a,ll b) {return ((a % mod) * (b % mod)) % mod;}
ll pwr(ll x,ll n){
    if(n == 0){
        return 1;
    }
    if(n&1){
        return mul(x, pwr(mul(x, x), (n - 1) / 2));
    } else {
        return pwr(mul(x, x), n / 2);
    }
}
ll modInv(ll n){ 
    return pwr(n, mod - 2); 
}
ll gcd(ll a,ll b) {
    if(b == 0) {
        return a;
    }
    return gcd(b, a % b);
}
// ====== Useful functions end ======
 
// ====== Variables begin ======

// ====== Variables end ======
void speed_solve(){
    ll n, k;
    cin >> n >> k;
    ll a[n];
    rep(i,n){
        cin >> a[i];
    }
    repe(i,k, n){
        cout << (a[i] > a[i - k] ? "Yes" : "No") << endl;
    }
}

int main(){
	// #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #endif
    speed_cubing;
    ll test_cases = 1;
    // cin >> test_cases;
    rep(i,test_cases){
        // cout << "Case #" << i + 1 << ": ";
        speed_solve();
    }
    return 0;
}

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

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

    vector<int> p;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        p.push_back(a);
    }

    sort(p.begin(), p.end());
    int sum = 0;
    for (int i = 0; i < k; i++) {
        sum += p.at(i);
    }

    cout << sum << endl;
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define dbg(x) cout<<#x<<":"<<x<<endl
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;

struct RMQ{

  static const int MAX_N = 1<<17;
  static const ll INF = (1LL<<31)-1;
  
  ll n;
  ll dat[2*(MAX_N)-1];

  RMQ(){}
  RMQ(ll n_){init(n_);}
  
  void init(ll n_){
    n=1;
    while(n<n_)n*=2;
    for(int i=0;i<2*n-1;i++)dat[i]=INF;
  }

  void update(int k,ll a){
    k+=n-1;
    dat[k]=a;
    while(k>0){
	 k=(k-1)/2;
	 dat[k]=min(dat[k*2+1],dat[k*2+2]);
    }
  }
  
  //[a,b)
  ll query(int a,int b,int k,int l,int r){
    if(r<=a||b<=l)return INF;
    if(a<=l&&r<=b)return dat[k];
    else{
	 ll vl=query(a,b,k*2+1,l,(l+r)/2);
	 ll vr=query(a,b,k*2+2,(l+r)/2,r);
	 return min(vl,vr);
    }
  }
  
  ll query(int a,int b){
    return query(a,b,0,0,n);
  }
};

int main(){
  ll n,x;
  cin>>n>>x;

  RMQ t(n*2); 
  for(int i=0;i<n;i++){
    ll a;
    cin>>a;
    t.update(i,a);
    t.update(i+n,a);
  }
  
  ll ans = 1LL<<60;
  for(int i=0;i<n;i++){
    ll sum=0;
    for(int j=0;j<n;j++){
	 sum+=t.query(j,j+i+1);
    }
    ans=min(ans,sum+x*i);
  }
  cout<<ans<<endl;
  return 0;
}


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

int main(){
  int N,M; cin >> N >> M;
  
  pair<int,int> price[100000];
  for(int i=0; i<N; i++){
    int A,B; cin >> A >> B;
    price[i]=make_pair(A,B);
  }
  sort(price,price+N);
  
  long long result=0;
  for(int i=0; i<N; i++){
    if(M>=price[i].second){
      result+=(long long)price[i].first*price[i].second;
      M-=price[i].second;
    }else{
      result+=(long long)price[i].first*M;
      M=0;
    }
    if(M<=0) break;
  }
  cout << result << endl;
}

Measured memory_bytes: 1024
using namespace std;
#include<iostream>
#include<bits/stdc++.h>
#define w(x) int x;cin>>x;while(x--)
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define MAX 1000000
#define ll long long

void abc()
{
	FIO;
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

void sieve(vector<int>& prime) {
	for (int i = 2; i * i <= MAX; i++) {
		if (prime[i] == 1) {
			for (int j = i * i; j < MAX; j += i) {
				prime[j] = 0;
			}
		}
	}
}



int main()
{
	abc();

	ll n;
	cin >> n;
	ll m = n;

	ll res = 0;

	for (ll i = 2; i * i <= n; i++) {
		ll cost = 0;

		while (n % i == 0 and n > 1) {
			cost++;
			n = n / i;
		}

		int temp = 0, j = 1;
		while (cost - j >= 0) {
			cost = cost - j;
			temp++;
			j++;
		}
		res += temp;
	}

	if (n > 1) res++;
	cout << res;




}

Measured memory_bytes: 3628
#include <iostream>
#include<string>
#include<time.h>
#include<math.h>
#include<stdlib.h>
#include<map>
#include <stdio.h>
#include <sstream>
using namespace std;

int main() {
	int N;
	unsigned  long long A , B;
	unsigned long long C = 0;
	unsigned long long max = 0, ans = 0;
	cin >> N;
	cin >> A;
	max = A;
	int i;
	for (i = 0; i < N-1;i++) {
		cin >> B;
		if (max > B) ans = ans + max - B;
		else if (max < B)max = B;
	
	}
	cout << ans << endl;
	return 0;

}

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

#define REP(i,n) for(int i=0;i<n;i++)
#define llong long long

using namespace std;

int main() {

	int N, M, red_count, blue_count, max = 0;
	string red, blue;

	cin >> N;

	vector<string> s;
	REP(i, N) {
		cin >> blue;
		s.push_back(blue);
	}

	cin >> M;

	vector<string> t;
	REP(i, M) {
		cin >> red;
		t.push_back(red);
	}

	REP(l, N) {

		REP(i, N)
			blue_count = count(s.begin(), s.end(), s[l]);

		REP(j, M)
			red_count = count(t.begin(), t.end(), s[l]);

		if ((blue_count - red_count) > max)
			max = blue_count - red_count;

	}

	cout << max << endl;

  return 0;
}


Measured memory_bytes: 256
#include <string>
#include <cstdint>
#include <cassert>
#include <functional>
#include <vector>
#include <unordered_map>
#include <iostream>
namespace lc {
struct Edge {
	int to;
	explicit Edge(int to) : to(to) { }
};
}
namespace lc {
template <typename EdgeType>
class AdjacencyList {
public:
	typedef std::vector<EdgeType> ListType;
private:
	std::vector<ListType> m_lists;
public:
	explicit AdjacencyList(int n = 0)
		: m_lists(n)
	{ }
	int size() const { return m_lists.size(); }
	template <typename... Args>
	void add_edge(int u, Args&&... args){
		m_lists[u].emplace_back(args...);
	}
	const ListType &operator[](int u) const { return m_lists[u]; }
};
}
namespace lc {
template <typename EdgeType, typename Func>
void enumerate_maximal_independent_sets(
	const AdjacencyList<EdgeType> &graph, Func func)
{
	const int n = graph.size();
	std::vector<uint64_t> bit_graph(n), incr_bit_graph(n + 1);
	for(int i = n - 1; i >= 0; --i){
		uint64_t mask = 0;
		for(const auto &e : graph[i]){ mask |= (1ull << e.to); }
		bit_graph[i] = mask;
		incr_bit_graph[i] = mask | incr_bit_graph[i + 1];
	}
	std::function<void(int, uint64_t, uint64_t)> recur =
		[&, n](int i, uint64_t picked, uint64_t eliminated) -> void {
			if(i == n){
				if((picked | eliminated) == (1ull << n) - 1){ func(picked); }
			}else if((incr_bit_graph[i + 1] | eliminated) & (1ull << i)){
				recur(i + 1, picked, eliminated);
				if(!(eliminated & (1ull << i))){
					recur(
						i + 1, picked | (1ull << i),
						eliminated | bit_graph[i]);
				}
			}else{
				recur(i + 1, picked | (1ull << i), eliminated | bit_graph[i]);
			}
		};
	recur(0, 0, 0);
}
}
namespace lc {
class NameTable {
private:
	std::unordered_map<std::string, int> m_table;
	std::vector<std::string> m_inv_table;
public:
	NameTable(){ }
	int operator[](const std::string &s){
		const auto it = m_table.find(s);
		if(it != m_table.end()){ return it->second; }
		const int t = m_inv_table.size();
		m_table.insert(std::make_pair(s, t));
		m_inv_table.push_back(s);
		return t;
	}
};
}
using namespace std;
typedef lc::Edge Edge;
int main(){
	ios_base::sync_with_stdio(false);
	while(true){
		int n;
		cin >> n;
		if(n == 0){ break; }
		lc::NameTable name_table;
		vector<int> powers(n);
		lc::AdjacencyList<Edge> graph(n);
		for(int i = 0; i < n; ++i){
			string u_name;
			int p, m;
			cin >> u_name >> p >> m;
			const int u = name_table[u_name];
			powers[u] = p;
			for(int j = 0; j < m; ++j){
				string v_name;
				cin >> v_name;
				const int v = name_table[v_name];
				graph.add_edge(u, v);
			}
		}
		int answer = 0;
		lc::enumerate_maximal_independent_sets(graph, [&](uint64_t s){
			if((s & 1) == 0){ return; }
			int sum = 0;
			for(int i = 0; i < n; ++i){
				if(s & (1ull << i)){ sum += powers[i]; }
			}
			answer = max(answer, sum);
		});
		cout << answer << endl;
	}
	return 0;
}

Measured memory_bytes: 1256
#define _USE_MATH_DEFINES
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<climits>
using namespace std;

int main(){
	int N, M;
	while(cin >> N >> M, N || M){
		double List[100][100], dp[100][100] = {};
		for(int i = 0; i < N; i++){
			dp[0][i] = 1;
			for(int j = 0; j < N; j++)
				cin >> List[i][j];
		}
	
		for(int i = 0; i < M-1; i++){
			for(int j = 0; j < N; j++){
				for(int k = 0; k < N; k++){
					dp[i+1][k] = max(dp[i+1][k], dp[i][j]*List[j][k]);
				}
			}
		}
		double ans = 0;
		for(int i = 0; i < N; i++) ans = max(ans, dp[M-1][i]);
		printf("%.2lf\n", ans);
	}
	return 0;
}

Measured memory_bytes: 1404