akhauriyash/Code-Regression huggingface dataset:
/*
 *  ん？今何でもするって
 *  言ってないね
 */

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

int dp[2 << 10][2001];
int books[10][2001];
int book_nums[10];
int sell_prices[10][2001];

int greater_int(const void *a, const void *b) {
    return *(int*)b - *(int*)a;
}

int main() {
    int a, b, c, d;
    int n, k;
    int book_bits;
    int max;

    scanf("%d %d", &n, &k);
    for (a=0; a<n; a++) {
        int c, g;
        int ind;

        scanf("%d %d", &c, &g);
        --g;
        ind = book_nums[g];
        books[g][ind] = c;
        ++book_nums[g];
    }
        
    for (a=0; a<10; a++) {
        qsort(books[a], book_nums[a], sizeof(int), greater_int);

        sell_prices[a][1] = books[a][0];
        for (b=2; b<=book_nums[a]; b++) {
            sell_prices[a][b] = sell_prices[a][b-1] + books[a][b-1] + (b-1)*2;
        }
    }

    book_bits = 1 << 10;
    for (a=0; a<k; a++) {
        for (b=0; b < book_bits; b++) {
            for (c=0; c<10; c++) {
                int num;

                if ((b >> c) & 1) continue;

                num = book_nums[c];
                if (num > k-a) {
                    num = k-a;
                }

                for (d=1; d<=num; d++) {
                    int val = dp[b][a] + sell_prices[c][d];
                    int *p = &dp[b | 1 << c][a+d];

                    if (*p < val) *p = val;
                }
            }
        }
    }

    max = 0;
    for (a=0; a < book_bits; a++) {
        if (max < dp[a][k]) {
            max = dp[a][k];
        }
    }

    printf("%d\n", max);
}

Measured memory_bytes: 9176
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}

#ifdef DEBUG
template <class T, class N> void verr(const T& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << "\n" << flush; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << "\n" << flush; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 4e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//
ll modpow(ll a, ll n, ll mod_) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod_;
        a = a * a % mod_;
        n >>= 1;
    }
    return res;
}

const ll MAX_SIZE = 200005;
array<ll, MAX_SIZE> fac, inv, finv;
void finit() {
    // combination init
    fac[0] = 1;
    for (ll i = 1; i < MAX_SIZE; i++) fac[i] = fac[i - 1] * i % MOD;
    finv[MAX_SIZE - 1] = modpow(fac[MAX_SIZE - 1], MOD - 2, MOD);
    for(ll i = MAX_SIZE - 1; i > 0; i--) finv[i - 1] = finv[i] * i % MOD;
    
    //inv init
    repe(i, 1, MAX_SIZE) inv[i] = modpow(i, MOD - 2, MOD);
}

ll perm(ll a, ll b) { return fac[a] * finv[a - b] % MOD; }

ll comb(ll a, ll b) { return fac[a] * finv[b] % MOD * finv[a - b] % MOD; }

int main() {
    init();
    finit();
    ll N, K;
    cin >> N >> K;
    
    if(N<K){
        cout << 0 << endl;
        return 0;
    }

    ll ans = 0;
    rep(i,K+1){
        ans += (i & 1 ? -1 : 1) * comb(K, i) * modpow(K - i, N, MOD) % MOD;
    }

    cout << (MOD + ans%MOD)%MOD << endl;
}


Measured memory_bytes: 7908
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>

using namespace std;
using ll =long long;
using vi = vector<int>; 
using vvi = vector<vi>; 
using vl = vector<ll>; 
using vvl = vector<vl>; 
using vs = vector<string>;
using vvs = vector<vs>; 
using vc = vector<char>;
using vvc = vector<vc>; 
using vb = vector<bool>;
using vvb = vector<vb>; 

#define rep(i,n) ;for( int i =0; i < n ; i ++)
#define all(a) a.begin(),a.end()
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i=a;i<b;i++)
#define pri(a)  printf("%.14lf\n",a);
#define MOD 1000000007
bool is_int_lround(double x){
  return std::lround(x)==x;
}
ll keta(ll x){
  ll n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}

ll conbi(int n,int m){
  
  cin>>n>>m;
  vector<ll> a(100);
  a[0] =1;
  for(int i=0;i<14;i++){
    a[i+1]=a[i]*(i+1);
  }
  return a[n] /(a[m] *a[n-m]);
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;//繰り返し二乗法
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll kaijo(ll x){
  ll z=1;
  if(x==0){
    return 1;
  }
  while(x>0){
    z *=x;
    z %=MOD;
    x--;
  }
  return z;
}
ll yakusu_num(ll n){
  vl yakusu(n+1,1);
  for(ll i=2;i*i<=n;i++){ 
    while(n%i==0){
      n /=i;
      yakusu[i]++;
    }
  }
  if(n!=1)yakusu[n]++;
  ll num=1;
  for(ll i=0;i<=n;i++){
    num*=yakusu[i];
  }
  return num;
}

int H,W;
vs s(50);
vi dv ={-1,0,1,0};vi du={0,-1,0,1};
int cnt=1;
int dfs(int u,int v){
  s[u][v]='.';
  
  rep(i,4){
   
      int nu =u +du[i],nv=v+dv[i];
      if(nu<0||nu>=H||nv<0||nv>=W)continue;
      if(s[nu][nv]=='.')continue;
      cnt ++;
      dfs(nu,nv);
    
  }
  return cnt;

}
int keta_wa(int x){
  int tot=0;
  while(x>0){
    tot +=x%10;
    x/=10;
  }
  return tot;
}

//vc alp(26) ={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
//cout<<""<<endl;
int main(){
  string N;cin>>N;

  if(N[0]==N[2])cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}







Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

int main() {
  int n, m, p;
  

while (true) {
  cin >> n >> m >> p;
if (n==0 && m == 0 && p == 0) break;
 vector< int > x(n);
  double sm = 0;
  for (int i=0; i<n; ++i) {
    cin >> x[i];
    sm += x[i];
  }

  //# 3 2 50
  //# 1 2 3
  
  sm *= 100.0;
int ans;
  if (x[m-1] == 0) {ans = 0;}
  else ans = (sm * (double)(100 - p) / 100.0) / (double)x[m-1];
  cout << ans << endl;
}
  
  return 0;
}



Measured memory_bytes: 3088
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define _ << ' ' <<
using namespace std;
using ll = long long;


int main()
{
  int a, b, c, k;
  cin >> a >> b >> c >> k;
  int sol = 0;
  a = min(a, k);
  sol += a;
  k -= a;
  b = min(b, k);
  k -= b;
  c = min(c, k);
  sol -= c;
  cout << sol;
}


Measured memory_bytes: 3600
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;

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

    if( Character.isUpperCase(a.charAt(0) ) ) {
	    System.out.println("A");
	}
    else {
        System.out.println( "a" );
    }
  }
}

Measured memory_bytes: 35724
#!/usr/bin/env python3

import math
import itertools
def main():
    N = int(input())
    town_zahyou = [ [int(s) for s in input().split()] for i in range(N)]

    sum_route = 0

    for junban_list in list(itertools.permutations(town_zahyou, N)):
        route = 0
        for i, town in enumerate(junban_list):
            if i == N-1:
                continue
            from_town = town
            to_town = junban_list[i+1]
            route += math.sqrt((from_town[0] - to_town[0])**2 + (from_town[1] - to_town[1])**2)
        sum_route += route
    
    print(sum_route / math.factorial(N))



if __name__ == "__main__":
    main()


Measured memory_bytes: 8052
#include <iostream>
#include <string>
#include <cctype>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
	string s;
	getline(cin, s);

	transform(s.begin(), s.end(),
		ostream_iterator<char>(cout),
		[](char c) { return islower(c) ? toupper(c) : isupper(c) ? tolower(c) : c; });
	cout << endl;

	return 0;
}



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

int main(){
  int h,w;
  char s[100][100];
  cin>>h>>w;
  for(int i=0;i<h;++i)
    for(int j=0;j<w;++j)
      cin>>s[i][j];
  
  for(int i=0;i<w;++i){
    for(int j=0;j<h;++j){
      if(s[j][i]=='#')
        break;
      if(j==h-1){
        for(int k=0;k<h;++k)s[k][i]='0';
      }
    }
  }
  
  for(int i=0;i<h;++i){
    bool ans=false;
    for(int j=0;j<w;++j){
      if(s[i][j]=='#'){
        break;
      }
      if(j==w-1){
        for(int k=0;k<w;++k)s[i][k]='0';
        ans=true;
      }
    }
    if(!ans){
      for(int j=0;j<w;++j){
        if(s[i][j]!='0')cout << s[i][j];
      } 
      cout << endl;
    }
  }

  return 0;
}

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

int main(){
	int k = 38,n = k * (k - 1) + 1,num[2][40][40];
	cout << n << " " << k << endl;
	for(int i = 0;i < k;i++) cout << (i ? " " : "") << i + 1;
	cout << endl;
	for(int i = 0;i < k;i++){
		for(int j = 0;j < k - 1;j++){
			cout << i + 1;
			for(int l = 0;l < k - 1;l++){
				if(i) cout << " " << (j + l * (i - 1)) % (k - 1) + 2 + (k - 1) * (l + 1);
				else cout << " " << l + 2 + (k - 1) * (j + 1);
			}
			cout << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <utility>
using namespace std;
using ll = long long;
 
int main() {
	string s;
	cin >> s;
	for (int i =0; i < s.size(); i++) {
		if ((i+1) % 2 == 1) {
			if (s[i] != 'R' && s[i] != 'U' && s[i] != 'D') {
				cout << "No" << endl;
				return 0;
			}
		} else {
			if (s[i] != 'L' && s[i] != 'U' && s[i] != 'D') {
				cout << "No" << endl;
				return 0;
			}
		}
	}
	cout << "Yes" << endl;
	return 0;
}


Measured memory_bytes: 256
h,w = list(map(int,input().split()))
n = int(input())
a = list(map(int,input().split()))

ans = [[0 for i in range(w)]for j in range(h)]
x = 0
y = 0
rev = 0
for i in range(len(a)):
    while(a[i]):
        ans[y][x] = str(i+1)
        a[i] -= 1
        if rev == 1:
            if x - 1 < 0:
                rev = 0
                y += 1
            else:
                x -= 1
        else:
            if x + 1 == w:
                y += 1
                rev = 1
            else:
                x += 1
for i in range(h):
    print(' '.join(ans[i]))


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

int main() {
  ll a,b,c,k,ans;
  cin>>a>>b>>c>>k;
  if(k%2==0){
    ans=a-b;
  }else{
    ans=b-a;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
k = int(input())

ans = 0
c = 7 % k
for i in range(k + 1):
    if c % k == 0:
        ans = i
        break
    else:
        c = ((c * 10) % k + 7) % k

if i == k:
    print(-1)
else:
    print(i + 1)


Measured memory_bytes: 9156
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
#include <string>
#include <set>
using namespace std;

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

	if (A == 1)
		A = 14;
	if (B == 1)
		B = 14;

	string res;
	if (A > B)
		res = "Alice";
	else if (A < B)
		res = "Bob";
	else
		res = "Draw";
	cout << res << endl;

	return 0;
}


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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1e9
typedef long long ll;


int main() {
    int K; cin >> K;
    string S; cin >> S;

    if(S.size() <= K){
        cout << S << endl;
    }else{
        REP(i,K){
            cout << S[i];
        }
        cout << "..." << endl;
    }
    return 0;
}

Measured memory_bytes: 3512
package main

import (
	"fmt"
	"sort"
)

func lowerBound(arr []int, target int) int {
	ng := -1
	ok := len(arr)

	for ok-ng > 1 {
		mid := (ng + ok) / 2

		if arr[mid] >= target {
			ok = mid
		} else {
			ng = mid
		}
	}

	return ok
}

func main() {
	var N int
	fmt.Scan(&N)

	ls := make([]int, N)
	for i := range ls {
		fmt.Scan(&ls[i])
	}

	sort.Ints(ls)

	res := 0

	for aIdx := 0; aIdx < N-2; aIdx++ {
		for bIdx := aIdx + 1; bIdx < N-1; bIdx++ {
			a := ls[aIdx]
			b := ls[bIdx]
			overIndex := lowerBound(ls, a+b)
			res += overIndex - 1 - bIdx
		}
	}

	fmt.Println(res)
}


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

int a[20010],b[20010],p[20010];

int main(){
	int n;
	cin >> n;
	for(int i = 0 ; i < n ; i++)
		cin >> p[i], p[i]--;
		
	
	for(int i = 0 ; i < n ; i++){
		a[i] = (i+1) * 30000;
	}
	b[p[0]] = (n-p[0]) * 30000;
	
	for(int i = 1 ; i < n ; i++){
		b[p[i]]= a[p[i-1]] + b[p[i-1]] - a[p[i]] + 1;
	}
	for(int i = 0 ; i < n ; i++){
		cout << a[i];
		if( i + 1 == n ) cout << endl;
		else cout << " ";
	}
	for(int i = 0 ; i < n ; i++){
		cout << b[i];
		if( i + 1 == n ) cout << endl;
		else cout << " ";
	}

	
	
	
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
signed main(){
  int N,D,A; cin>>N>>D>>A;
  vector<pii> X(N);
  rep(i,0,N) cin>>X[i].first>>X[i].second;
  sort(ALL(X));
  int ans=0;
  queue<pii> Q;
  int sum=0;
  rep(i,0,N){
    while(Q.size()>0){
      int R=Q.front().first,S=Q.front().second;
      if(R>=X[i].first)
        break;
      Q.pop();
      sum-=S;
    }
    if(sum>=X[i].second)
      continue;
    int K=((X[i].second-sum)+A-1)/A;
    ans+=K;
    K*=A;
    sum+=K;
    int P=D*2+X[i].first;
    Q.push(make_pair(P,K));
  }
  cout<<ans<<endl;
  }






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

using namespace std;
typedef long long ll;

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define REPR(i, n) for (ll i = (n); i >= 0; i--)
#define FOR(i, m, n) for (ll i = (m); i < (n); i++)
#define FORR(i, m, n) for (ll i = (m); i >= (n); i--)
#define INF 1e9
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((ll)(x).size())
#define SORT(x) sort((x).begin(), (x).end())
#define dump(x) cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl

int main(int argc, char const *argv[])
{
    ll n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    if (s[k - 1] == 'A')
        s[k - 1] = 'a';
    else if (s[k - 1] == 'B')
        s[k - 1] = 'b';
    else if (s[k - 1] == 'C')
        s[k - 1] = 'c';
    cout << s << endl;
    return 0;
}


Measured memory_bytes: 256
if !ENV['RUBY_THREAD_VM_STACK_SIZE']
  exec({'RUBY_THREAD_VM_STACK_SIZE'=>'1000000000'}, '/usr/bin/ruby', $0)
end

N, M = gets.split.map(&:to_i)
ABs = N.times.map{gets.split.map(&:to_i)}
LRs = M.times.map{gets.split.map(&:to_i)}

as, bs = ABs.sort_by(&:first).transpose
as << 10**9 + 1
@bs = ([0] + bs + [0]).each_cons(2).map{|x, y| x^y}
lrs = LRs.map.with_index(1){|(l, r), i| [as.bsearch_index{|a| a >= l}, as.bsearch_index{|a| a > r}, i]}
@g = lrs.each_with_object(Array.new(N + 1){[]}){|(l, r, i), o| (o[l] << [r, i]; o[r] << [l, i]) unless l == r}
@ans, @d = [], Array.new(N + 1, false)

def dfs(u)
  @d[u] = true
  @g[u].each do |v, i|
    next if @d[v]
    if dfs(v)
      @bs[u] ^= 1
      @bs[v] ^= 1
      @ans << i
    end
  end
  @bs[u] == 1 ? true : false
end

(N + 1).times{|i| dfs(i) unless @d[i]}
puts @bs.inject(:+) > 0 ? -1 : [@ans.size, @ans.sort.join(' ')]

Measured memory_bytes: 209144
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



l, r = LI()
L = r.bit_length()
dp = [[[[0] * 2 for _ in range(2)] for _ in range(2)] for _ in range(L+1)]
dp[0][0][0][0] = 1


for i in range(L):
    rd = r >> L - i - 1 & 1
    ld = l >> L - i - 1 & 1
    for l_flg in range(2):
        for r_flg in range(2):
            for c in range(2):
                for ri, li in ((1, 0), (1, 1), (0, 0)):
                    if c == 0 and ri == 1 and li == 0:
                        continue
                    if (l_flg == 0 and li < ld) or (r_flg == 0 and ri > rd):
                        continue
                    dp[i + 1][l_flg or li > ld][r_flg or ri < rd][c or (ri == 1 and li == 1)] += dp[i][l_flg][r_flg][c]
                    dp[i + 1][l_flg or li > ld][r_flg or ri < rd][c or (ri == 1 and li == 1)] %= mod

ret = 0
for a in range(2):
    for b in range(2):
        for d in range(2):
            ret += dp[L][a][b][d]

print(ret % mod)





Measured memory_bytes: 10396
import bisect as bi
a, b, q = map(int, input().split())
s = [int(input()) for i in range(a)]
t = [int(input()) for i in range(b)]
u = [int(input()) for i in range(q)]

for x in u:
    c = []
    d = []
    tmp = bi.bisect_left(s, x)
    if tmp != a : c.append(s[tmp])
    if tmp != 0 : c.append(s[tmp-1])
    tmp = bi.bisect_left(t, x)
    if tmp != b : d.append(t[tmp])
    if tmp != 0 : d.append(t[tmp-1])
    ans = 2**64
    for e in c:
        for f in d:
            g = abs(x-e)
            h = abs(x-f)
            if (x-e)*(x-f) > 0:
                ans = min(ans, max(g, h))
            else:
                if g > h : g,h = h,g
                ans = min(ans, 2*g+h)
    print(ans)


Measured memory_bytes: 87896
#include <stdio.h>

int main(){
char s[3];
int count=0;
for (int i = 0; i < 3; i++) {
  scanf("%c",&s[i] );
}
for (int i = 0; i <3; i++) {
  if(s[i]=='1')count++;
}

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

return 0;



}



Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,o,n) for(long long i = o;i<n;i++)
#define oneforall ios::sync_with_stdio(false);cin.tie(0);
#define all(v) (v).begin(),(v).end()
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
#define int long long 
const long long INF=1e18;
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
typedef vector<int> vi;
typedef vector<long long> vl;
typedef long long ll;
typedef vector<pair<long, long > > vpll;
typedef vector<pair<int, int > > vpii;
#define FORR(x,arr) for(auto& x:arr)
int32_t main() {
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall 
	oneforall

	ini(n);
	ini(n1);
	vpii morty;
	int  tmp = 0;
	FOR(i,0,n){
		ini(x);
		ini(x1);
		morty.push_back({x,x1});
	}
	sort(all(morty));
	FOR(i,0,morty.size()){
		n1-=morty[i].second;
		if(n1<=0){out(morty[i].first);break;}
	}















	return 0;
}

Measured memory_bytes: 2420
#include <stdio.h>
#include <math.h>


main()
{
int a,b,d;
char c;
while(1){
	scanf("%d %c %d",&a,&c,&b);
	if(c=='?')break;
	if(c=='+')d=a+b;
	if(c=='-')d=a-b;
	if(c=='*')d=a*b;
	if(c=='/')d=a/b;
	printf("%d\n",d);
}
}


Measured memory_bytes: 2740
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define YY cout << "Yes" << endl;
#define NN cout << "No" << endl;
#define ve vector
#define pint pair<int,int>
const int INF = 1000000007;
const long double EPS = 1e-15;
const long double PI = acos(-1);
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
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; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
int solve(){
  string s;
  cin >> s;
  cout << s[0] << (int)s.size() - 2 << s[s.size() - 1] << endl;
  return 0;
}
int main(){
  // ios::sync_with_stdio(false);cin.tie(nullptr);
  // cout << fixed;cout << setprecision(16);
  solve();
  return 0;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
	int a,b,c,i,n;
	cin>> a>> b>> c;
	n=0;
	for(i=a;i<=b;i++){
		if(c%i==0){
			n++;
		}
	}
	cout<< n<<endl;
	return 0;
}

Measured memory_bytes: 1164
#include<bits/stdc++.h>
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ff(i,a,b) for(register int i=a;i>=b;--i)
#define debug(x) cerr << #x << " : " << x << " " << endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
const ll mod = 998244353;
const ll mod1 = 2e18 + 7;
const double tiaohe = 0.57721566490153286060651209;
const int inf = 0x3f3f3f3f;
ll oula(ll x) { ll res = x;f(i, 2, x / i) { if (x % i == 0) { res = res / i * (i - 1);while (x % i == 0) x /= i; } }if (x > 1) res = res / x * (x - 1);return res; }
ll quickmod(ll a, ll n, ll m) { ll s = 1;while (n) { if (n & 1) { s = s * a % m; }a = (a*a) % m;n = n / 2; }return s; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
void ex_gcd(ll a, ll b, ll &x, ll &y, ll &d) { if (!b) { d = a, x = 1, y = 0; } else { ex_gcd(b, a % b, y, x, d);y -= x * (a / b); } }
ll inv(ll t, ll p) { ll d, x, y;ex_gcd(t, p, x, y, d);return d == 1 ? (x % p + p) % p : -1; }
//double a = log(n) +tiaohe + 1.0 / (2 * n);
double eqa = (1 + sqrt(5.0)) / 2.0;
const int N = 6e5 + 5;
int t;
int a[N];
int main()
{
	//freopen("in.txt", "r", stdin);
	int n, k,x;
	while (cin >> n >> k)
	{
		f(i, 1, n)cin >> a[i];
		sort(a + 1, a + 1 + n);
		ll ans = 0;
		f(i, 1, n - k)
		{
			ans += a[i];
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 4364
n=int(input())
p_list=[-1]*n
s_list=[-1]*n
c_list=[0]*n
degree=[0]*n
depth=[0]*n
height=[0]*n
type=[0]*n
for _ in range(n):
    id,l,r=map(int,input().split())
    c_list[id]=[l,r]
    if l!=-1 and r!=-1:
        degree[id]=2
        type[id]="internal node"
        p_list[l]=id
        p_list[r]=id
        s_list[l]=r
        s_list[r]=l
    elif r!=-1:
        degree[id]=1
        type[id]="internal node"
        p_list[r]=id
        s_list[r]=l
    elif l!=-1:
        degree[id]=1
        type[id]="internal node"
        p_list[l]=id
        s_list[l]=r
    else:
        degree[id]=0
        type[id]="leaf"
root=p_list.index(-1)
type[root]="root"

pre=[]
def dsf1(v):
    pre.append(v)
    if c_list[v]!=[-1,-1]:
        if c_list[v][0]==-1:
            dsf1(c_list[v][1])
        elif c_list[v][1]==-1:
            dsf1(c_list[v][0])
        else:
            dsf1(c_list[v][0])
            dsf1(c_list[v][1])
dsf1(root)

inn=[]
def dsf2(v):
    if c_list[v][0]!=-1:
        dsf2(c_list[v][0])
    inn.append(v)
    if c_list[v][1]!=-1:
        dsf2(c_list[v][1])    
dsf2(root)

post=[]
def dsf3(v):
    if c_list[v]!=[-1,-1]:
        if c_list[v][0]==-1:
            dsf3(c_list[v][1])
        elif c_list[v][1]==-1:
            dsf3(c_list[v][0])
        else:
            dsf3(c_list[v][0])
            dsf3(c_list[v][1])
    post.append(v)
dsf3(root)
print("Preorder")
print("",*pre)
print("Inorder")
print("",*inn)
print("Postorder")
print("",*post)


Measured memory_bytes: 5620
/**
 * @author derrick20
 * Easy
 */
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String args[]) throws Exception {
        FastScanner sc = new FastScanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int N = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt() - (i + 1);
        }
        Arrays.sort(arr);
        long total = 0;
        for (int i = 1; i <= N / 2; i++) {
            total += arr[N / 2 + i + (N % 2 == 0 ? -1 : 0)] - arr[N / 2 - i];
        }
        out.println(total);
        out.close();
    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        FastScanner(FileReader s) {
            br = new BufferedReader(s);
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        String nextLine() throws IOException { return br.readLine(); }

        double nextDouble() throws IOException { return Double.parseDouble(next()); }

        int nextInt() throws IOException { return Integer.parseInt(next()); }

        long nextLong() throws IOException { return Long.parseLong(next()); }
    }
}

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

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

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

    int n = 5;
    vector <int> v (n + 1);
    for (int i = 1; i <= n; i++)
        cin >> v[i];
    for (int i = 1; i <= n; i++)
        if (not v[i])
            cout << i;
    return 0;
}


Measured memory_bytes: 3608
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef istringstream ISS;
typedef ostringstream OSS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define EACH( it, c ) for ( auto it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()
#define DRANGE( c, p ) (c).begin(), (c).begin() + p, (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define DEBUG( x ) cerr << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << ( x ) << endl

struct comp_result : binary_function< pair<double,string>, pair<double,string>, bool >
{
	bool operator ()( const pair<double,string> &a, const pair<double,string> &b ) const
	{
		if ( a.fst == b.fst )
		{
			return a.snd < b.snd;
		}
		else
		{
			return a.fst > b.fst;
		}
	}
};

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

	for ( int n; cin >> n, n; )
	{
		vector< pair<double,string> > res;
		REP( i, 0, n )
		{
			string l;
			int p, a, b, c, d, e, f, s, m;
			cin >> l >> p >> a >> b >> c >> d >> e >> f >> s >> m;

			int past = a + b + c, price = 0;
			REP( t, 0, m )
			{
				past += d + e;
				price += f * s;
			}

			res.PB( MP( 1. * ( price - p ) / past, l ) );
		}

		sort( ALL( res ), comp_result() );
		FOR( r, res )
		{
			cout << r.snd << endl;
		}
		cout << '#' << endl;
	}

	return 0;
}

Measured memory_bytes: 1224
#include "stdio.h"

int main()
{
	//まずは変数を作って初期化
	char A[40];
	char Aend=' ',Bfirst=' ',Bend=' ',Cfirst=' ';
	int counter=0;
	for (int i=0; i<40; i++) {
		A[i]=' ';
	}

	//gets()で取得
	fgets(A,40,stdin);

	for (int i=0 ; i<40; i++) {
		//空白がどこのものなのかをチェックする
		if (A[i]==' ')
			counter++;
		
		//一個目の空白をチェックしたら、Aの最後とBの最初がわかる
		if ((A[i]==' ')&&(counter==1)) {
			Aend=A[i-1];
			Bfirst=A[i+1]; 
		}
			
		//ニ個目の空白をチェックしたら、Bの最後とCの最初がわかる
		if ((A[i]==' ')&&(counter==2)) {
			Bend=A[i-1];
			Cfirst=A[i+1]; 
		}
	}

	/*
	//テスト
	printf("%s\n",A);
	printf("%c\n",Aend);
	printf("%c\n",Bfirst);
	printf("%c\n",Bend);
	printf("%c\n",Cfirst);
	*/

	//Aの最後とBの最初、Bの最後とCの最初が同じならしりとりが成立
	if ((Aend==Bfirst)&&(Bend==Cfirst))
		printf("YES");
	else
		printf("NO");

	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
using namespace std;

int main()
{
  vector<pair<char,long long> > A,B,C;
  char c;
  int a;

  while(1){
    cin>>c;
    if(c=='$')break;
    cin>>a;
    A.push_back(mp(c,a));
  }
  while(1){
    cin>>c;
    if(c=='$')break;
    cin>>a;
    B.push_back(mp(c,a));
  }
  while(1){
    cin>>c;
    if(c=='$')break;
    cin>>a;
    C.push_back(mp(c,a));
  }

  int size=A.size()-B.size()+1;
  for(int i=0;i<size;i++){
    bool flag=true;
    for(int j=0;j<B.size();j++){
      if(j==0 || j==B.size()-1){
	if(A[i+j].f!=B[j].f || A[i+j].s<B[j].s)flag=false;
      }
      else {
	if(A[i+j].f!=B[j].f || A[i+j].s!=B[j].s)flag=false;
      }
    }
    if(flag){
      for(int j=0;j<B.size();j++)A[i+j].s-=B[j].s;

      if(B.size()==1)A.insert(A.begin()+i,C.begin(),C.end());
      else A.insert(A.begin()+i+1,C.begin(),C.end());

      size+=C.size();
      for(int j=0;j<A.size();j++){
	if(A[j].s==0){
	  A.erase(A.begin()+j);
	  j--;
	  size--;
	}
      }
      for(int j=1;j<A.size();j++){
	if(A[j].f==A[j-1].f){
	  A[j-1].s+=A[j].s;
	  A.erase(A.begin()+j);
	  j--;
	  size--;
	}
      }
      break;
    }
  }

  for(int j=0;j<A.size();j++)cout<<A[j].f<<" "<<A[j].s<<" ";
  cout<<"$"<<endl;
  return 0;
}

Measured memory_bytes: 1276
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define EPS 1e-10
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
#define first_more_idx(ve, num) upper_bound(all(ve), num)-ve.begin() // idx = first_more_idx(ve,num); if(idx = ve.size()) , then not exist
#define first_lessequal_idx(ve, num) lower_bound(all(ve), num)-ve.begin()
#define pq_pair_tB priority_queue <pair<ll,ll>, vector<pair<ll,ll> > , greater<pair<ll,ll> > >
#define pq_pair_ts priority_queue <pair<ll,ll> > // only sort first param
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}
ll power(ll x, ll n){if(n == 0) return 1;return  (n%2)? x*power(x, n-1)%MOD : power(x*x%MOD, n/2);}
ll dx[]={0, 0, -1, 1};
ll dy[]={1, -1, 0, 0};// up,down,left right


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll X,Y,A,B,C;
    cin >> X >> Y >> A >> B >>C;
    
    priority_queue< ll, std::vector<ll>, std::greater<ll> > red, green;
    vector<ll> nocolor;
    
    rep(i, A){
        ll inp; cin >> inp;
        red.push(inp);
    }
    rep(i, B){
        ll inp; cin >> inp;
        green.push(inp);
    }
    rep(i, C){
        ll inp; cin >> inp;
        nocolor.pb(inp);
    }
    
    while(red.size() > X){
        red.pop();
    }
    while(green.size() > Y){
        green.pop();
    }
    
    sort(rall(nocolor));
    
    
    rep(i, nocolor.size()){
        if(nocolor[i] > red.top() and nocolor[i] > green.top()){
            if(red.top() < green.top()){
                red.pop();
                red.push(nocolor[i]);
            }else{
                green.pop();
                green.push(nocolor[i]);
            }
        } else if(nocolor[i] > red.top() ) {
            red.pop();
            red.push(nocolor[i]);
        }else if(nocolor[i] > green.top() ){
            green.pop();
            green.push(nocolor[i]);
        }
    }
    
    ll ans = 0 ;
    while(red.size() != 0){
        ans += red.top();
        red.pop();
    }
    
    while(green.size() != 0){
        ans += green.top();
        green.pop();
    }

    cout << ans << endl;
    //cout << fixed << setprecision(16) << ans << endl;
    return 0;
}


Measured memory_bytes: 3316
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

#define OUT 0
#define IN 1
#define MAX 100

class Event{
    public:
    int id, type, t;
    Event(int id=0, int type=0, int t=0):id(id), type(type), t(t){}
    bool operator < ( const Event &e) const{
	if ( t == e.t ) return type < e.type;
	return t < e.t;
    }
};

main(){
    int s = 150, n, a, b, M[MAX];
    
    while( cin >> n && n ){
	Event events[MAX*2];
	int ne = 0;
	for ( int i = 0; i < n; i++ ){
	    cin >> M[i] >> a >> b;
	    events[ne++] = Event(i, IN, a);
	    events[ne++] = Event(i, OUT, b);
	}

	sort(events, events + ne);

	bool fail = false;
	int cur = 0;

	for ( int i = 0; i < ne; i++){
	    if ( events[i].type == OUT ) cur -= M[events[i].id];
	    if ( events[i].type == IN )  cur += M[events[i].id];
	    if ( cur > s ) fail = true;
	}

	if ( fail ) cout << "NG" << endl;
	else cout << "OK" << endl;
    }
}

Measured memory_bytes: 0
#include <iostream>

bool
is_month(const int val) {
    if ((1 <= val) && (val <= 12)) {
            return true;
    }
    return false;
}

int
main(int argc, char** argv) {
    std::string S;
    std::cin >> S;

    int vin, d1, d2;
    vin = std::atoi(S.c_str());
    d1 = vin / 100;
    d2 = vin % 100;

    bool flg_m1 = is_month(d1);
    bool flg_m2 = is_month(d2);
    if (flg_m1 && flg_m2) {
        std::printf("AMBIGUOUS\n");

    } else if (!flg_m1 && flg_m2) {
        std::printf("YYMM\n");

    } else if (flg_m1 && !flg_m2) {
        std::printf("MMYY\n");

    } else {
        std::printf("NA\n");

    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>

#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_set>
#include <array>

using namespace std;


template<typename T>
void warshall_floyd(int n, vector<T> &g, vector<T> &dp) {
    for (int k = 0, kv = 0; k < n; ++k, kv += n) {
        for (int i = 0, iv = 0; i < n; ++i, iv += n) {
            for (int j = 0; j < n; ++j) {
                dp[iv + j] = min(dp[iv + j], dp[iv + k] + dp[kv + j]);
            }
        }
    }
}

int main() {
    int h, w;
    cin >> h >> w;
    int n = 10;
    vector<int> c(n * n);
    for (int i = 0, iv = 0; i < n; ++i, iv += n) {
        for (int j = 0; j < n; ++j) {
            cin >> c[iv + j];
        }
    }
    vector<int> a(n);
    fill(a.begin(), a.end(), 0);
    int value;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> value;
            if (value != -1 && value != 1) {
                ++a[value];
            }
        }
    }
    vector<int> dp = c;
    warshall_floyd(n, c, dp);
    int cost = 0;
    for (int i = 0, iv = 0; i < n; ++i, iv += n) {
        cost += dp[iv + 1] * a[i];
    }
    cout << cost << endl;

}


Measured memory_bytes: 3640
#include <iostream>
using namespace std;
 
int main(void){
    int m,f,r;
     
    while(1){
        cin >> m >> f >>r;
        if(m == -1 && f == -1 && r == -1) break;
        if(m == -1 || f == -1) cout << "F" << endl;
        else if(m+f>=80) cout << "A" << endl;
        else if(m+f>=65) cout << "B" << endl;
        else if(m+f>=50) cout << "C" << endl;
        else if(m+f>=30 && r>=50) cout <<"C" <<endl;
        else if(m+f>=30) cout <<"D" << endl;
        else cout << "F" << endl;
    }
}


Measured memory_bytes: 3092
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <set>
#include <string>
#include <vector>
#define SORT(a) sort((a).begin(), (a).end())
#define RSORT(a) sort((a).rbegin(), (a).rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define FORSTEP(i, start, end, step) for (int i = start; i < end; i += step)
#define ALL(a) a.begin(), a.end()
typedef long long ll;
using namespace std;

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

    int N, D, X;
    cin >> N >> D >> X;
    vector<int> A(N);
    REP(i, N) cin >> A[i];

    int ans = X;

    REP(i, N) {
        FOR(day, 1, D + 1) {
            if ((day - 1) * A[i] + 1 <= D)
                ans++;
        }
    }

    cout << ans << endl;

    return 0;
}

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

using namespace std;

#define fst first
#define snd second
#define mp make_pair
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef long double LD;
typedef pair<int, int> pii;

template<typename T> inline LL squ(T x) { return (LL) x * x; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }

template<typename T> inline T read() {
	T sum = 0, fg = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') fg = -1;
	for (; isdigit(c); c = getchar()) sum = (sum << 3) + (sum << 1) + (c ^ 0x30);
	return fg * sum;
}

const int maxn = 3e3 + 10;

inline int Pow(int x, int y, int mod) {
	int res = 1;
	for (; y; y >>= 1, x = squ(x) % mod) if (y & 1) res = (LL) res * x % mod;
	return res;
}

int n, mod, S[maxn][maxn], C[maxn][maxn], pw[maxn * maxn], pww[maxn];

inline void Add(int &x, int y) { (y < 0 ? y += mod : 0), x += y, (x >= mod ? x -= mod : 0); }

inline void init() {
	S[0][0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			S[i][j] = ((LL) S[i - 1][j] * j + S[i - 1][j - 1]) % mod;
	C[0][0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= i; j++)
			C[i][j] = ((j ? C[i - 1][j - 1] : 0) + C[i - 1][j]) % mod;
	pw[0] = 1;
	for (int i = 1, e = n * n; i <= e; i++) pw[i] = (pw[i - 1] << 1) % mod;
	for (int i = 0; i <= n; i++) pww[i] = Pow(2, Pow(2, i, mod - 1), mod);
}

int main() {

	n = read<int>(), mod = read<int>(), init();

	int ans = 0;
	for (int i = 0; i <= n; i++) {
		int res = 0;
		for (int j = 0; j <= i; j++) Add(res, (LL) pw[(n - i) * j] % mod * (S[i][j] + (LL) S[i][j + 1] * (j + 1) % mod) % mod);
		Add(ans, (i & 1 ? -1LL : 1LL) * C[n][i] * res % mod * pww[n - i] % mod);
	}

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

	return 0;
}

Measured memory_bytes: 106368
//code by lynmisakura.wish to be accepted!
/****************************/
#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<bitset>
#include <climits>
#include<set>
#include<bitset>
using namespace std;
/***************************/
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<pair<int,int>> vpi;

// const long long MOD = 998244353;
// const long long mod = 1000000007;
// const long long INF = 10000000000000;
 
#define itn int
#define endl "\n"
#define pb push_back
#define mp make_pair
#define ss second
#define ff first
#define mins(x,y) x = min(x,y)
#define maxs(x,y) x = max(x,y)
#define all(x) (x).begin(),(x).end()
#define Rep(n) for(int i = 0;i < n;i++)
#define rep(i,n) for(int i = 0;i < n;i++)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
 
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll qp(ll a, ll b) { ll ans = 1; do { if (b & 1)ans = 1ll * ans*a; a = 1ll * a*a; } while (b >>= 1); return ans; }
ll qp(ll a, ll b, int mo) { ll ans = 1; do { if (b & 1)ans = 1ll * ans*a%mo; a = 1ll * a*a%mo; } while (b >>= 1); return ans; }
 
#define _GLIBCXX_DEBUG
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
/**************************************************/
#define MAX_N 100010
int n,m;
vector<int> G[MAX_N];
int from[MAX_N],to[MAX_N];

int ans;
bool visited[MAX_N];
/*************************************************/
bool judge(){
   for(int i = 0;i < n;i++){
      if(!visited[i])return false;
   }
   return true;
}
void dfs(vector<vector<int>> G2,int i){
   visited[i] = true;
   int sz = G2[i].size();
   for(int j = 0;j < sz;j++){
      int x = G2[i][j];
      if(!visited[x])dfs(G2,x);
   }
}
void solve(){
   for(int i = 0;i < m;i++){
      vector<vector<int>> G2(n,vector<int>(0));
      fill(visited,visited + n,false);
      for(int j = 0;j < m;j++){
         if(j != i){
            G2[from[j]].pb(to[j]);
            G2[to[j]].pb(from[j]);
         }
      }
      dfs(G2,0);
      if(!judge()) ans++; 
   }
   cout << ans << endl;
}

int main(void){
   cin >> n >> m;
   rep(i,m){
      int a,b;cin >> a >> b;
      from[i] = --a;
      to[i] = --b;
      G[a].pb(b);
      G[b].pb(a);
   }
   solve();
   return 0;
}

Measured memory_bytes: 2688
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

A,B,C = LI()
K = I()

count = 0
while B <= A:
    count += 1
    B *= 2
while C <= B:
    count += 1
    C *= 2

if count <= K:
    print('Yes')
else:
    print('No')

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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++) cin >> a.at(i);
  
  set<pair<int, int>> like;
  int ans = 0;
  for(int i = 0; i < n; i++){
    int x = i + 1, y = a.at(i);
    if(x > y) swap(x, y);
    pair<int, int> now = {x, y};
    if(like.count(now)) ans++;
    else like.insert(now);
  }
  
  cout << ans << endl;   
}

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

int main() {
    string S;
    cin >> S;
    bool ans = true;
    for (int i = 0; i < (int)S.size(); i++) {
        if (i % 2 == 1 && S[i] == 'R') ans = false;
        else if (i % 2 == 0 && S[i] == 'L') ans = false;
    }
    cout << (ans ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int a, b, c, d;

int main () {

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

cin >> a >> b >> c;

d += min(c, a);
c = max(0, c - a);
d += min(c, b);
c = max(0, c - b);
if (c != 0)d++;
cout << d + b;

return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
//using namespace __gnu_pbds;
#define rep(i,a,b) for(i=(a);i<=(b);i++)
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int,int>
#define pb push_back
#define F first
#define S second
#define mod 1000000007
#define maxn 100005
#define inf 1e18
#define boost ios::sync_with_stdio(false);cin.tie(0)
#define fr freopen("source.txt","r",stdin),freopen("output.txt","w",stdout)
#define SET(a,b) memset(a,b,sizeof(a))
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define all(x) x.begin(), x.end()
#define ps(x,y) fixed<<setprecision(y)<<x
//template<typename T>
//using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
    return out <<  "(" << a.F << ", " << a.S << ")";
}
 
template<class A> ostream& operator << (ostream& out, const vector<A> &a) {
    out << "[";
    for (auto it = a.begin(); it != a.end(); ++it) {
        if (it != a.begin())
            out << ", ";
        out << *it;
    }
    return out << "]";
}
ll dp[maxn];
vector<ll>a;
ll n,k;
ll go(ll i){
    if(i==0) return 0;
    ll &ans=dp[i];
    if(ans!=-1) return ans;
    ans=0;
    for(auto p:a){
        if(p<=i&&go(i-p)==0){
            ans=1;
        }
    }
    return ans;
}
int main()
{
    boost;
    ll i,j,x,t,y;
    cin>>n>>k;
    for(i=0;i<n;i++){
        cin>>x;
        a.pb(x);
    }
    SET(dp,-1);
    ll ans=go(k);
    cout<<(ans==1?"First":"Second");
}

Measured memory_bytes: 4224
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define MAXN 200000
#define LL long long
#define MOD 998244353
#define Pr pair<int,int>
#define X first
#define Y second
int n,a[MAXN+5],b[MAXN+5],ans;
int pw2[MAXN+5];
char X[MAXN+5];
vector<Pr> t;
int add(int a,int b){
	return (a+b)%MOD;
}
int mul(int a,int b){
	return 1LL*a*b%MOD;
}
int sub(int a,int b){
	return (a-b+MOD)%MOD;
}
int cal(int x){
	int tmp=1;
	for(int i=1;i<=x;i++)
	b[i]=a[i],tmp=(a[i])?add(tmp,pw2[x-i]):tmp;
	for(int i=x+1;i<=n;i++)
	b[i]=b[i-x]^1;
	for(int i=1;i<=n;i++)
	if(b[i]>a[i]){tmp=sub(tmp,1);break;}
	else if(b[i]<a[i])break;
	return tmp;
}
LL read(){
	LL x=0,F=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')F=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*F;
}
int main(){
	n=read();pw2[0]=1;
	scanf("%s",X+1);
	for(int i=1;i<=n;i++){
		a[i]=(X[i]=='1');
		pw2[i]=mul(pw2[i-1],2);
	}
	for(int i=1;i<=n;i++)
	if((n%i==0)&&((n/i)%2==1)){
		int kdf=cal(i);
		for(int j=0;j<t.size();j++)
		if(i%t[j].X==0)kdf=sub(kdf,t[j].Y);
		t.push_back(Pr(i,kdf));
		ans=add(ans,mul(kdf,mul(i,2)));
	}
	printf("%d",ans);
}

Measured memory_bytes: 2816
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()
template <class T> inline bool chmin(T &a, T b) {if (a > b){a = b;return true;}return false;}
template <class T> inline bool chmax(T &a, T b) {if (a < b){a = b;return true;}return false;}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;cin>>n;
    ll ans = 0;
    for(int i=1;i<=n;i++){
        if(i%3==0 || i%5==0) continue;
        ans += i;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3652
# -*- coding: utf-8 -*-
l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k = int(input())
k -= 1

print(l[k])


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
ll x,y;
int main(void){
    cin>>x>>y;
    if(x%y==0){
        cout<<-1<<endl;
    }else{
        cout<<x<<endl;
    }
    
}


Measured memory_bytes: 3576
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    ll n,k;
    cin>>n>>k;
    ll ans = 0;
    ll mod = 1e9+7;
    for(ll i=k;i<=n+1;i++){
        ll ma = n*(n+1)/2LL - (n-i)*(n-i+1)/2LL;
        ma %= mod;
        ll mi = (i-1)*i/2LL;
        mi %= mod;
        ans += mod + ma - mi+1;
        ans %= mod;
       // cerr << i << " " << ma << " " << mi << endl;
    }
    cout << ans << endl;
    
}

Measured memory_bytes: 3688