akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const double PI=3.14159265358979;
const ll INF= pow(10,18);
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main() {
  ll n;
  cin >> n;
  vl a(n);
  rep(i,n){
    cin >> a[i];
  }
  vl cnt(10);
  rep(i,n){
    if(a[i]<3200)
      cnt[a[i]/400]++;
    else
      cnt[8]++;
  }
  ll MIN=0;
  rep(i,8){
    if(cnt[i]!=0){
      MIN++;
    }
  }
  cout << max((ll)1,MIN) << " " << MIN+cnt[8] << endl;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力(スペース改行関係なし)
		int n = sc.nextInt();
		int k = sc.nextInt();
     	int sum = 0;
		List<Integer> allNum = new ArrayList<>();
        for(int i = 0; i < n ; i++){
          int p = sc.nextInt();
          allNum.add(p);
        }
      
        Collections.sort(allNum);
      	for(int j = 0;j < k ; j ++){
        	sum += allNum.get(j);
        }

		System.out.println(sum);
		
	}
}

Measured memory_bytes: 38712
m, n = gets.split.map(&:to_i)

dimensions = (0..n).map { (0..m).map { [0, Float::INFINITY] } }

(1..m).each do |i|
    k = gets.to_i
    k.times do
        gets =~ /(\d+) ([<>])= (\d+)/
        d, c, x = $1.to_i, $2, $3.to_i
        if c == ?<
            dimensions[d][i][1] = x if x < dimensions[d][i][1]
        else
            dimensions[d][i][0] = x if x > dimensions[d][i][0]
        end
        if dimensions[d][i][1] < dimensions[d][i][0]
            puts 'No'
            exit
        end
    end
end

require 'set'
require 'tsort'

class Hash
    include TSort
    alias tsort_each_node each_key
    def tsort_each_child(u)
        self[u].each {|v| yield v}
    end
end

g = {}
(1..m).each {|i| g[i] = Set.new}

(1..n).each do |d|
    (1..m).to_a.combination(2) do |i, j|
        u, v = dimensions[d][i], dimensions[d][j]
        g[i] << j if u[1] < v[0]
        g[j] << i if v[1] < u[0]
    end
end

begin
    g.tsort
    puts 'Yes'
rescue
    puts 'No'
end

Measured memory_bytes: 9836
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = s; i < (ll)(n); i++)
typedef long long ll;
typedef vector<vector<ll>> vvl;
typedef vector<ll> vl;
typedef vector<vector<char>> vvc;
typedef vector<char> vc;
typedef pair<ll,ll> pll;
ll max(ll x,ll y){
if(x>y)return x;
else return y;
}
ll min(ll x,ll y){
  return x+y-max(x,y);
}


int main() {
  string s;
  cin >> s;
  int n=s.size();
  if(n==1){
    if(s[0]=='A'||s[0]=='T'||s[0]=='C'||s[0]=='G')cout << 1 << endl;
    else cout << 0 << endl;
    return 0;
  }
  int count=0;
  rep(i,n-1){
    string t;
    rep2(j,i,n){
      if(s[j]=='A'||s[j]=='T'||s[j]=='C'||s[j]=='G'){
        int aaa=j-i+1;count=max(count,aaa);
      }else{
        break;
      }
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
def mat_dot(one, two, mod):
	return [[sum([(one[i][k]*two[k][j])%mod for k in range(max(len(two), len(one[0])))])%mod for j in range(len(two[0]))] for i in range(len(one))]

def mat_pow(mat, exp, mod):
	size = len(mat)
	res = [[0 for _ in range(size)] for _ in range(size)]
	for i in range(size):
		res[i][i] = 1
	cnt = 0
	while (1<<cnt) <= exp:
		if (exp>>cnt)&1:
			res = mat_dot(res, mat, mod)
		mat = mat_dot(mat, mat, mod)
		cnt += 1
	return res

while True:
	n, m, a, b, c, t = map(int, input().split())
	if n == 0:
		break
	s = list(map(int, input().split()))
	mt = [[0 for _ in range(n)] for _ in range(n)]
	for i in range(n):
		if i > 0:
			mt[i][i-1] = a
		mt[i][i] = b
		if i < n-1:
			mt[i][i+1] = c
	mt = mat_pow(mt, t, m)
	ans = [sum(s[j] * mt[i][j] for j in range(n)) % m for i in range(n)]
	print(*ans)


Measured memory_bytes: 5876
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
long long n;
long long a[1123456];
signed main() {
	long long n;
	cin >> n;
	long long i;
	bool bol = false;
	long long t =1123456;
	if (n == 1) {
		cout << 0 << endl;
		return 0;
	}
	for (i = 2; i <= t; i++) {
		while (n % i == 0) {
			n /= i;
			a[i]++;
			bol = true;
		}
	}
	long long ans = 0, cnt;
	if (!bol)cout << 1 << endl;
	else {
		for (i = 2; i < 1123400; i++) {
			if (a[i]) {
				cnt = 1;
				while (a[i] >= 0) {
					a[i] -= cnt;
					cnt++;
				}
				ans += cnt - 2;
			}
		}
		if (n == 1)
			cout << ans << endl;
		else cout << ans + 1 << endl;
	}
	return 0;
}

Measured memory_bytes: 3644
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>

#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 FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<endl;
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define int long long
#define all(x) (x).begin(), (x).end()

using namespace std;

const int MAX = 1010;
const int MOD = (ll)1000000000 + 7;
const ll INF = 1e17;
const double pi = acos(-1);
const double EPS = 1e-10;
//小さいほうから取り出すpriority queue
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
typedef pair<int, int>P;

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


long long nCr(long long n, long long r) {
	if (r > n / 2) r = n - r; // because C(n, r) == C(n, n - r)
	long long ans = 1;
	long long i;

	for (i = 1; i <= r; i++) {
		ans *= n - r + i;
		ans /= i;
	}

	return ans;
}	
signed main() {
	int N, K; cin >> N >> K;
	if (K > N) {
		print(0);
	}
	else {
		print(N - K + 1);
	}
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
   long long n,a,b; cin>>n>>a>>b;
   long long num=n/(a+b);
   //cout<<num<<endl;
   long long amari=n%(a+b);
   //cout<<amari<<endl;
   long long mina=min(a,amari);
   long long ans=a*num+mina;
   cout<<ans<<endl;
   return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
ll a, b, c;
ll X;
int solve()
{
    ll cnt = 0;
    for(ll i = 0; i <= a; i ++)
    {
        for(ll j = 0; j <= b; j ++)
        {
            for(ll l = 0; l <= c; l ++)
            {
               ll ks = i * 500 + j * 100 + l * 50;
                if(ks == X) cnt ++;
            }
        }
    }
    return cnt;
}
int main()
{
    cin >> a >> b >> c >> X;
    cout << solve();
}


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

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

const ll MOD = 1e9+7;
// const ll MOD = 998244353;
const ll INF = 1ll<<60;

#define FOR(i,a,b) for (ll i=(a);i<(ll)(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define DEBUG(x) ;
#define DEBUG(x) std::cerr << #x << " : " << (x) << std::endl;

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

long long modpow(const long long a, const long long n, const long long mod)
{
        if (n == 0) return 1;
        long long t = modpow(a, n / 2, mod);
        (t = t * t) %= mod;
        if (n & 1)
			(t = t * a) %= mod;
        return t;
}


int main(int argc, char **argv)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll N; cin >> N;
	vector<ll> C(N); REP(i, N) cin >> C[i];
	sort(ALL(C), greater<ll>());

	ll res{0};
	REP(i, N)
		(res += (C[i] * (i + 2)) % MOD) %= MOD;

	(res *= modpow(2, 2*N-2, MOD)) %= MOD;
	std::cout << res << std::endl;
	return 0;
}


Measured memory_bytes: 4692
#include <iostream>

int main(int argc, const char * argv[]) {
    
    while (1) {
        
        long long int n, x ;
        
        std::cin >> n >> x ;
        if (n==0&&x==0) break ;
        
        int count = 0 ;
        
        for (long long int i=n; i>0; i--) {
            for (long long int j=i-1; j>0; j--) {
                for (long long int k=j-1; k>0; k--) {
                    count += ( i + j + k == x) ;
                }
            }
        }
        
        printf("%d\n", count) ;
        
    }
    
    return 0 ;
}




Measured memory_bytes: 3228
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long ,long long>pll;

ll gcd(ll a, ll b) {return (!b ? a : gcd(b, a % b));}
ll lcm(ll a, ll b) {return ((a*b)/gcd(a,b));}
bool cmp(int a,int b){return a>b;}

const ll mod = 1e9 + 7;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;
const ld pi = 3.141592653589793;

 long long modpow(long long n, long long k,long long mod)
{
if (k == 0) return 1;
long long r = modpow(n * n % mod, k >> 1, mod);
if (k & 1) r = r * n % mod;
return r;
}

void solve(){
     int x;
     cin >> x;
     if(x) cout << 0;
     else cout << 1;
}

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

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

int main()
{
  string S;
  cin >> S;
  
  int eat = 0;
  for(int i = 0; i < S.size(); i++)
  {
    if(S.at(i) == '+')
      eat++;
    else if(S.at(i) == '-')
      eat--;
  }
  
  cout << eat << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
char map[110][110];
bool ins[110][110];
int ans[110];
int qwq[110];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++){
	  	while(map[i][j]!='#'&&map[i][j]!='.') scanf("%c",&map[i][j]);
		if(map[i][j]=='#') ins[i][j]=1;
		if(map[i][j]=='.') ins[i][j]=0;	  	
		ans[i]+=ins[i][j];
		qwq[j]+=ins[i][j];
	  }

//	for(int i=1;i<=n;i++) printf("%d ",ans[i]);puts("");
//	for(int i=1;i<=m;i++) printf("%d ",qwq[i]);puts("");
	
	for(int i=1;i<=n;i++){
		if(ans[i]==0) continue;
		for(int j=1;j<=m;j++)
		  if(qwq[j]!=0) printf("%c",map[i][j]); 
		puts("");
	}
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.util.function.*;
 
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    long[] A = new long[N];
    for (int i = 0; i < N; i++) A[i] = sc.nextLong();
    sc.close();

    long mod = 1000000007L;
    long[] cmb = new long[N - K + 1];
    cmb[0] = 1;
    for (int i = 1; i <= N - K; i++)
      cmb[i] = modDiv(cmb[i - 1] * (K + i - 1), i, mod);

    Arrays.sort(A);
    long ans = 0;
    for (int i = 0; i < N - K + 1; i++) {
      ans -= (A[i] * cmb[N - K - i]) % mod;
      ans %= mod;
      ans += (A[N - 1 - i] * cmb[N - K - i]) % mod;
      ans %= mod;
    }

    if (ans < 0) ans += mod;
    System.out.println(ans);
  }

  private static long modDiv(long a, long b, long mod) {
    return (a % mod) * modInv(b, mod) % mod;
  }

  private static long modInv(long x, long mod) {
    return modPow(x, mod - 2, mod);
  }

  private static long modPow(long b, long e, long mod) {
    long ans = 1;
    long x = b % mod;
    for (long y = e; y != 0; y >>= 1) {
      if ((y & 1) == 1) ans = (ans * x) % mod;
      x = (x * x) % mod;
    }
    return ans;
  }
}

Measured memory_bytes: 50316
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>
#include <queue>
#include <string>

#define REP(i,n) for (int i = 0; i < (n); i++)
#define FOR(i,s,n) for (int i = (s); i < (n); i++)
#define ALLOF(c) c.begin(), c.end()
#define RANGEOF(c,i,n) c.begin() + (i), c.begin() + (i) + (n)
#define EPS 1e-9
#define INF 1000000000
using namespace std;

template <class T> T read() { T t; cin >> t; return t; }
template <class T> vector<T> read(int n) { vector<T> v; REP(i,n) { v.push_back(read<T>()); } return v; }
template <class T> vector<vector<T>> read(int n, int m)
{
	vector<vector<T>> v;
	REP(i,n) { v.push_back(read<T>(m)); }
	return v;
}

template <class T> void write(const T &t) { cout << t << endl; }
template <class T> void write(const T &t, const T &t2) { cout << t << ' ' << t2 << endl; }
template <class T> void write(const vector<T> &v)
{
	ostringstream ss; 
	for (auto x : v) ss << x << ' ';
	auto s = ss.str();
	cout << s.substr(0, s.length() - 1) << endl;
}

struct _Reader { template <class T> _Reader operator ,(T &rhs) { cin >> rhs; return *this; } };
#define READ(t,...) t __VA_ARGS__; _Reader(), __VA_ARGS__

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

/// template end ///

void solve()
{
	READ(int, datasets);
	REP(dataset, datasets)
	{
		READ(int, initial, years, n);
		int best = 0;
		REP(i, n)
		{
			READ(int, mode);
			READ(double, rate);
			READ(int, cost);
			int base = initial;
			int current = initial;
			REP(y, years)
			{
				current += (mode ? current : base) * rate - cost;
				base -= cost;
			}
			best = max(best, current);
		}
		write(best);
	}
}

Measured memory_bytes: 1236
package main

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

func main(){
	r := bufio.NewReader(os.Stdin)
	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()

	var R, G, B, N int
	fmt.Fscan(r, &R, &G, &B, &N)
	ans := 0
	for i:= 0; i * R<= N; i++{
		for j:=0; j*B + i*R <= N; j++{
			sum := N - (i*R + j*B)
			if sum >= 0 && sum % G == 0{
				ans++
			}
		}
	}
	fmt.Fprintln(w, ans)
}

Measured memory_bytes: 1876
n = int(raw_input())
R = []
R.append(int(raw_input()))
minv = R[0]
maxv = -1 * 10**9
for j in xrange(1,n):
    R.append(int(raw_input()))
    maxv = max(maxv,R[j]-minv)
    minv = min(minv,R[j])
print maxv

Measured memory_bytes: 10452
package main

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

type state struct {
	pi int
	pj int
	ln int
	ch byte
}

func solve(s, t string) string {
	n1 := len(s)
	n2 := len(t)
	dp := make([][]state, n1+1)
	for i := range dp {
		dp[i] = make([]state, n2+1)
	}

	for i:=1; i<=n1; i++ {
		si := s[i-1]
		for j:=1; j<=n2; j++ {
			tj := t[j-1]
			if si == tj {
				s := state{ch: si}
				s.pi = i-1
				s.pj = j-1
				s.ln = dp[i-1][j-1].ln+1
				dp[i][j] = s
			} else {
				s := state{}
				if dp[i-1][j].ln < dp[i][j-1].ln {
					s.pi = i
					s.pj = j-1
					s.ln = dp[i][j-1].ln
				} else {
					s.pi = i-1
					s.pj = j
					s.ln = dp[i-1][j].ln
				}
				dp[i][j] = s
			}
		}
	}

	rs := []byte{}
	i, j := n1, n2
	for i!=0 || j!=0 {
		if dp[i][j].ch != 0 {
			rs = append(rs, dp[i][j].ch)
		}
		i, j = dp[i][j].pi, dp[i][j].pj
	}

	i, j = 0, len(rs)-1
	for i < j {
		rs[i], rs[j] = rs[j], rs[i]
		i++
		j--
	}

	return string(rs)
}

func readLineNum(bf *bufio.Reader) int {
	line, _ := bf.ReadString('\n')
	line = strings.Trim(line, "\n")
	N, _ := strconv.Atoi(line)
	return N
}

func readLineNums(bf *bufio.Reader) []int {
	line, _ := bf.ReadString('\n')
	line = strings.Trim(line, "\n")
	fields := strings.Split(line, " ")
	nums := []int{}
	for _, field := range fields {
		num, _ := strconv.Atoi(field)
		nums = append(nums, num)
	}
	return nums
}

func readLineStrs(bf *bufio.Reader) []string {
	line, _ := bf.ReadString('\n')
	line = strings.Trim(line, "\n")
	return strings.Split(line, " ")
}

func main() {
	bf := bufio.NewReader(os.Stdin)
	s := readLineStrs(bf)[0]
	t := readLineStrs(bf)[0]
	fmt.Println(solve(s, t))
}


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

const vector<int> dx = {-1, 1, 0, 0};
const vector<int> dy = {0, 0, -1, 1};

int main()
{
    int H, W;
    cin >> H >> W;
    vector<string> s(H);
    for (int i = 0; i < H; i++)
    {
        cin >> s.at(i);
    }

    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            char sij = s.at(i).at(j);
            if (sij == '.')
            {
                continue;
            }

            bool has_n = false;
            for (int k = 0; k < 4; k++)
            {
                int in = i + dy.at(k), jn = j + dx.at(k);
                if (0 <= in && in < H && 0 <= jn && jn < W)
                {
                    if (s.at(in).at(jn) == '#')
                    {
                        has_n = true;
                    }
                }
            }
            if (!has_n)
            {
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;
int main(void){
  int a,b,c,k;
  cin>>a>>b>>c>>k;
  int f(1);
  int max(a);
  if(max<b){
    max=b;
    f=2;
  }
  if(max<c){
    max=c;
    f=3;
  }
  int t=pow(2,k);
  if(f==1){
    cout<<a*t+b+c<<endl;
  }else if(f==2){
    cout<<a+b*t+c<<endl;
  }else{
    cout<<a+b+c*t<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<list>
#include<queue>
#include<functional>
#include<limits.h>
#include<string.h>
#include<algorithm>
#define int long long
#define mod 1000000007
using namespace std;

int p(int a, int b) {//aのb乗
	if (b < 0)return 0;
	if (b == 0)return 1;
	int c = 1;
	while (b > 1) {
		if (b & 1)c = c*a%mod;
		a = a*a%mod;
		b >>= 1;
	}
	return a*c%mod;
}
signed main() {
	string s; cin >> s;
	int ans = 0;
	int a = 0, b = 0, c = 0, d = 0;//A B C ?
	int e = 0, f = 0, g = 0, h = 0;//A B C ?
	for (char i : s) {
		switch (i)
		{
		case 'A':a++; break;
		case 'B':b++; break;
		case 'C':c++; break;
		case '?':d++; break;
		}
	}
	for (char i : s) {
		if (i == 'B') {
			ans += e*(c - g) % mod*p(3, d) % mod;
			ans += e*(d - h) % mod*p(3, d - 1) % mod;
			ans += h*(c - g) % mod*p(3, d - 1) % mod;
			ans += h*(d - h) % mod*p(3, d - 2) % mod;
		}
		if (i == '?') {
			ans += e*(c - g) % mod*p(3, d-1) % mod;
			ans += e*(d - h-1) % mod*p(3, d - 2) % mod;
			ans += h*(c - g) % mod*p(3, d - 2) % mod;
			ans += h*(d - h-1) % mod*p(3, d - 3) % mod;
		}
		switch (i)
		{
		case 'A':e++; break;
		case 'B':f++; break;
		case 'C':g++; break;
		case '?':h++; break;
		}
	}
	cout << ans%mod << endl;
}

Measured memory_bytes: 512
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>

#include <bits/stdc++.h>
#include <cmath>
#include <limits>

using namespace std;

//b以上の最初の要素の位置を返す。ない場合は-1
//vはソート済であること。あと、&v でなくvだと引数コピーが発生するので遅い。
int lbound(vector<long long>&v, long long b){
	int s = 0, e = v.size() - 1;
	int l = v.size();
	int m;
	while(e - s > 1){
		m = (s + e) / 2;
		if(v[m] >= b){
			e = m;
		}
		else{
			s = m;
		}
	}
	if(v[max(s - 1, 0)] >= b) return max(s - 1, 0);
	else if(v[s] >= b) return s;
	else if(v[min(s + 1, l - 1)] >= b) return min(s + 1, l - 1);
	else return -1;
}

//bより大きいの最初の要素の位置を返す。ない場合は-1
//vはソート済であること。あと、&v でなくvだと引数コピーが発生するので遅い。
int ubound(vector<long long>&v, long long b){
	int s = 0, e = v.size() - 1;
	int l = v.size();
	int m;
	while(e - s > 1){
		m = (s + e) / 2;
		if(v[m] <= b){
			s = m;
		}
		else{
			e = m;
		}
	}
	if(v[max(s - 1, 0)] > b) return max(s - 1, 0);
	else if(v[s] > b) return s;
	else if(v[min(s + 1, l - 1)] > b) return min(s + 1, l - 1);
	else return -1;
}

int main(int argc, char* argv[]){
	cin.tie(0);
	ios::sync_with_stdio(false);

	long long N;
	vector<long long> A, B, C;

	cin >> N;
	for(int i = 0; i < N; i++){
		long long v;
		cin >> v;
		A.push_back(v);
	}
	sort(A.begin(), A.end());

	for(int i = 0; i < N; i++){
		long long v;
		cin >> v;
		B.push_back(v);
	}
	sort(B.begin(), B.end());
	
	for(int i = 0; i < N; i++){
		long long v;
		cin >> v;
		C.push_back(v);
	}
	sort(C.begin(), C.end());

	//Bの要素bを軸に見る。
	//bについては {bより小さいAの要素の個数} *  {bより大きいCの要素の個数}で算出できる。
	long long ans = 0;
	for(int i = 0; i < N; i++){ //B.size() = N;
		long long numA = (long long) lbound(A, B[i]); //b以上の最初の要素の位置
		long long numC = (long long) ubound(C, B[i]); //bより大きい最初の要素の位置
		if(numA == 0 || numC == -1){
			continue;
		}
		if(numA == -1){
			numA = N;
		}
		ans += (numA * (N - numC)) ; //C.size() = N;
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 3316
def insertionSort(a, n)
  printf("%s\n",a.join(" "))
  for i in 1..n-1 do
    v = a[i]
    j = i-1
    while j >= 0 && a[j] > v do
      a[j+1] = a[j]
      j -= 1
    end
    a[j+1] = v
    printf("%s\n",a.join(" "))
  end
end

n = gets.chomp.to_i
a = gets.chomp.split(" ").map{|x| x.to_i}
insertionSort(a,n)


Measured memory_bytes: 6916
N = int(input())
s = [int(input()) for i in range(N)]
s.sort()
ans = sum(s)

if ans % 10 != 0:
    print(ans)
    exit()
else:
    for i in s:
        if (ans - i) % 10 != 0:
            print(ans - i)
            exit()
        else:
            continue

print(0)

Measured memory_bytes: 2940
#ifndef TEMPLATE_HPP
#define TEMPLATE_HPP
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())
using namespace std;
using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> void amax(T &x, T y) { x = max(x, y); }
template <typename T> void amin(T &x, T y) { x = min(x, y); }
template <typename T> T power(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
template <typename T, typename U> vector<U> make_vector(T&& n, U&& val) { return vector<U>(forward<T>(n), forward<U>(val)); }
template <typename T, typename... Args> decltype(auto) make_vector(T&& n, Args&&... args) { return vector<decltype(make_vector(forward<Args>(args)...))>(forward<T>(n), make_vector(forward<Args>(args)...)); }
const int INF = 1001001001;
const i64 LINF = 1001001001001001001ll;
const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
#endif

void solve() {
  int x;
  cin >> x;
  int ans = 8 - (x / 200 - 2);
  cout << ans << endl;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(16);
  cerr << fixed << setprecision(16);
  solve();
  return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define vi vector<int>
#define vb vector<bool>
#define pii pair<int,int>
#define mod 1000000007
#define ss second
#define ff first
#define vpii vector<pii>
#define vvi vector<vi>
#define pb push_back
#define vs vector<string>
#define all(x) x.begin(),x.end()
#define mii map<int,int>
const int inf=0x3f3f3f3f3f3f3f3f;
void print(vi &v){
    for(int i=0;i<v.size();i++)cout<<v[i]<<" ";
    cout<<endl;
}
int power(int a,int b){
    int res = 1;
    while(b!=0){
        if(b&1){
            res *= a; 
        }
        a = (a * a);
        b = (b / 2);
    }
    return res;
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    t = 1;
    while(t--){
        int k,n,i;
        cin>>k>>n;
        vi v(n);
        for(i=0;i<n;i++)cin>>v[i];
        int mini = inf;
        mini = min(mini,v[n-1]-v[0]);
        mini = min(mini,k-(v[1]-v[0]));
        for(i=1;i<n-1;i++){
        	mini = min(mini,min(k-(v[i]-v[i-1]),k-(v[i+1]-v[i])));
        }
        mini = min(mini,k-(v[n-1]-v[n-2]));
        cout<<mini<<endl;
    }
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define ll long long
#define inf int(1e9+7)
using namespace std;

string a,b;
int l,l1;
bool ok;
int main(){
	cin>>a;
	cin>>b;
	l=a.length();
	l1=b.length();
	if (l1-1==l) {
		ok=true;
		for (int i=0;i<l;i++) if (a[i]!=b[i]) ok=false;
	}
	if (ok==true) cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}

Measured memory_bytes: 3624
#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
int n;
unsigned long long f[60],g[60],x,ans;
void dfs(int a){
	if (a==0){
		if (x==1) ans++;
		return;
	}
	if (x){
		x--;
		if (x>=f[a-1]){
			x-=f[a-1];
			ans+=g[a-1];
			if (x){
				x--;
				ans++;
				if (x>=f[a-1]) ans+=g[a-1];else dfs(a-1);
			}
		}else dfs(a-1);
	}
}
int main(){
	scanf("%d%llu",&n,&x);
	f[0]=g[0]=1;
	fo(i,1,n){
		f[i]=f[i-1]*2+3;
		g[i]=g[i-1]*2+1;
	}
	dfs(n);
	printf("%llu\n",ans);
	return 0;
}

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

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

	int ans=1;
	while(n>0){
		if(ans*2>ans+k)ans+=k;
		else ans*=2;

		n--;
		
	}

	cout<<ans<<endl;

	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 ll long long
#define uint unsigned int
#define ull  unsigned long long
#define pb push_back
#define mk make_pair
#define ins insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define X first
#define Y second
#define umap unordered_map
#define speed() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define setvalue(d,s,e,n) for(int qwe = s; qwe < e; ++qwe) d[qwe] = n
#define mset multiset
#define pqueue priority_queue
   
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
        
const int  N = 2e5 + 314;
const int INF = 1e9;
const double PI = acos(-1);
const int MOD = 1e9 + 7;
const double eps = 1e-9; 

void solve(){
    ll n;
    cin >> n;
    vector <ll> v;
    for(ll i = 2; i * i <= n; ++i) {
        if(n % i == 0) {
            v.pb(i);
            if(i != n / i)
                v.pb(n / i);
        }
    }
    v.pb(n); 
    vector <ll> f;
    ll m = n - 1;
    set <ll> s;
    for(ll i = 1; i * i <= m; ++i) {
        if(m % i == 0){
            if(i != 1){
                f.pb(i);
            }
            if(m / i != i)
                f.pb(m / i);
        }
    }
    for(int i = 0; i < f.size(); ++i) {
        ll cur = m / f[i]; 
        if(n % cur == 1){
            s.ins(cur);
        }
        cur = f[i];
        if(n % cur == 1){
            s.ins(cur);
        }
    }
    for(int i = 0; i  < v.size(); ++i) {
        ll g = n;
        while(g % v[i] == 0){
            g /= v[i];
        }
        if(g == 1 || g % v[i] == 1){
            s.ins(v[i]);
        }
    }
    
    cout << s.size();
}
 
int main(){
    // speed();
    int t = 1;
    // cin >> t;
    while(t--)solve();
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main() {
    int a,b;
    while(cin >> a >> b) {
        if(a * b == 15) {
            printf("*\n");
//            printf("%d×%d=15.\n",a,b);
        } else if(a + b == 15) { 
            printf("+\n");
//            printf("%d+%d=15.\n",a,b);
        } else {
            printf("x\n");
//            printf("%d+%d=%d and %d×%d=%d, neither of which is 15.\n",
//                   a,b,a + b,a ,b,a * b);
        }
    }
    return 0;
}


Measured memory_bytes: 256
import os
import sys
from collections import Counter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N = int(sys.stdin.buffer.readline())

ans = np.full((N, N), '.', dtype='U1')


def check():
    qualities = []
    board = np.full((N + 2, N + 2), '.', dtype='U1')
    board[1:-1, 1:-1] = ans
    for row in board[1:-1]:
        q = 0
        for a, b in zip(row, row[1:]):
            q += a != b and b != '.'
        qualities.append(q)
    for col in board.T[1:-1]:
        q = 0
        for a, b in zip(col, col[1:]):
            q += a != b and b != '.'
        qualities.append(q)
    if len(Counter(qualities).keys()) == 1:
        return qualities[0]
    else:
        return -1


def ps(ans, q):
    print(q)
    print('\n'.join(map(lambda r: ''.join(r), ans)))


def dfs(i):
    h = i // N
    w = i % N
    c = chr(ord('a') + i % 26)
    if i == N ** 2:
        q = check()
        if q > 0:
            ps(ans, q)
        return
    if w < N - 1 and ans[h, w] == ans[h, w + 1] == '.':
        ans[h, w] = c
        ans[h, w + 1] = c
        dfs(i + 1)
        ans[h, w] = '.'
        ans[h, w + 1] = '.'
    if h < N - 1 and ans[h, w] == ans[h + 1, w] == '.':
        ans[h, w] = c
        ans[h + 1, w] = c
        dfs(i + 1)
        ans[h, w] = '.'
        ans[h + 1, w] = '.'
    dfs(i + 1)


s3 = '''
aa.
..f
..f
'''.strip()

s4 = '''
abcc
abgg
iikl
mmkl
'''.strip()

s5 = '''
aacce
ffh.e
..hno
p..no
pvvxx
'''.strip()

s6 = '''
a..abb
a..a.f
.hhggf
yzza..
y.xa..
ddx.hh
'''.strip()

s7 = '''
aa.ee.f
d.bb..f
de..cc.
.e..ghh
j.zzg..
jbc....
.bc..kk
'''.strip()

if N <= 2:
    print(-1)
    exit()
if N == 3:
    print(s3)
    exit()


def fill(h, w, rows: str):
    for i, row in enumerate(rows.split('\n')):
        ans[h + i, w:w + len(row)] = list(row)


i = 0
n = N
while n >= 8:
    fill(i, i, s4)
    i += 4
    n -= 4
if n == 7:
    fill(i, i, s7)
if n == 6:
    fill(i, i, s6)
if n == 5:
    fill(i, i, s5)
if n == 4:
    fill(i, i, s4)
print('\n'.join(map(lambda r: ''.join(r), ans)))


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

string S;
ll d,ans;

int main(void){
    cin >> S;
    rep(i,1<<3){
        ans =S[0] - 48;
        rep(j,3){
            d = (i>>j)&1;
            if(d)ans+=S[j+1]-48;
            else ans -=S[j+1]-48;
        }
        if(ans==7){
            cout << S[0];
            rep(j,3){
                d = (i>>j)&1;
                if(d) cout <<"+";
                else cout << "-";
                cout << S[j+1];
            }
            cout << "=7"<<endl;
            return 0;
        }
    }
    //char x = '0';
    //cout << (ll)x << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int i,a;
	double b,k,sum=0;
	scanf("%d",&a);
	for(i=0;i<a;i++)
	{
		scanf("%lf",&b);
		sum=sum+(1/b);
	}
	k=1/sum;
	printf("%lf\n",k);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mk make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pii pair<ll,ll>
#define vvll vector< vector<ll> >
#define pb push_back
#define sz(v) (v).size()
#define inf 1e16
#define md 1000000007
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define tel(a){cout<<a<<"\n";}
#define tell(a,b){cout<<a<<" | "<<b<<"\n";}
#define telll(a,b,c){cout<<a<<" | "<<b<<" | "<<c<<"\n";}
#define teln(v,n){cout<<"v- ";rep(i,0,n)cout<<v[i]<<" ";cout<<"\n";}
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define M 1000010

int main(){
	IOS;
	ll n;cin>>n;
	cout<<n*n*n;
	
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <algorithm>
#include <cmath>
#include <climits>
#include <iomanip>

using namespace std;

typedef long long ll;

int main() {
    int n;  cin >> n;
    int **a = new int*[2];
    int **c = new int*[2];
    for (int i = 0; i < 2; i++) {
        a[i] = new int[n];
        c[i] = new int[n];
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
            if (j > 0)
                c[i][j] = c[i][j-1]+a[i][j];
            else 
                c[i][j] = a[i][j];
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        if (i == 0) {
            sum = c[1][n-1] + a[0][0];
        }

        else {
            sum += c[0][i] + c[1][n-1] - c[1][i-1];
        }

        ans = max(ans, sum);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
n = int(input())
a = [list(map(int, input().split())) for _ in range(2)]

x = a[0][0] + sum(a[1])
m = x
for i in range(n-1):
    x = (x - a[1][i] + a[0][i+1])
    m = max(m, x)
print(m)

Measured memory_bytes: 3064
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
	int N,M,x;
	long sum=0;
	cin >> N>>M;
	for (int i = 0; i < M; ++i)
	{
		cin >> x;
		sum += x;
	}
	
	if (N - sum < 0)
		cout << -1 << endl;
	else
		cout << N - sum;
	return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define rep(i, n) for(i = 0; i < (n); i++)
#define chmax(x, y) x = max(x, y)
#define MOD 1000000007
#define INF 1 << 30

using namespace std;
typedef long long ll;
typedef pair<int, int> pp;

int main(void) {
	int num, i, j, t, ans = 0, x;
	cin >> num >> t;
	vector<vector<int>> dp(num + 1, vector<int>(t, 0));
	vector<pp> a(num);
	rep(i, num) {
		cin >> a[i].first >> a[i].second;
	}
	sort(a.begin(), a.end());
	rep(i, num) {
		rep(j, t) {
			x = j + a[i].first;
			if (x < t)
				dp[i + 1][x] = dp[i][j] + a[i].second;
			chmax(dp[i + 1][j], dp[i][j]);
		}
		chmax(ans, dp[i][t - 1] + a[i].second);
	}
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 35584
#include<bits/stdc++.h>
using namespace std;
int n;
double ans;
double a,c=380000.0;
string b;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		cin>>a>>b;
		if(b=="BTC") ans+=a*c;
		else ans+=a;
	}
	printf("%.5lf\n",ans);
	
	return 0;
}

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

int main(){
    int num;
    cin >> num;
    
    if(num < 1200) cout << "ABC" << endl;
    else if(num < 2800) cout << "ARC" << endl;
    else cout << "AGC" << endl;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner(System.in);
		long n = sc.nextLong(), k = sc.nextLong();
		if(n == k) {
			System.out.println(0);
		}else if(n < k) {
			if(2*n < k) {
				System.out.println(n);
			}else {
				System.out.println(k-n);
			}
		}else {
			if(n%k == 0) {
				System.out.println(0);
			}else {
				System.out.println(smaller(n,k));
			}
		}
	}
	
	static long smaller(long a, long b) {
		long t = a/b;
		long ans = Math.min(a-b*t, b*(t+1)-a);
		return ans;
	}
	
	static class FastScanner {
		private BufferedReader reader = null;
	    private StringTokenizer tokenizer = null;
	    public FastScanner(InputStream in) {
	        reader = new BufferedReader(new InputStreamReader(in));
	        tokenizer = null;
	    }

	    public String next() {
	        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
	            try {
	                tokenizer = new StringTokenizer(reader.readLine());
	            } catch (IOException e) {
	                throw new RuntimeException(e);
	            }
	        }
	        return tokenizer.nextToken();
	    }

	    public String nextLine() {
	        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
	            try {
	                return reader.readLine();
	            } catch (IOException e) {
	                throw new RuntimeException(e);
	            }
	        }

	        return tokenizer.nextToken("\n");
	    }

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

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

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

	    public int[] nextIntArray(int n) {
	        int[] a = new int[n];
	        for (int i = 0; i < n; i++)
	            a[i] = nextInt();
	        return a;
	    }

	    public long[] nextLongArray(int n) {
	        long[] a = new long[n];
	        for (int i = 0; i < n; i++)
	            a[i] = nextLong();
	        return a;
	    }
	}
}

Measured memory_bytes: 21204
#include "stdio.h"
#include "iostream"
using namespace std;

int main()
{
	int a, b, c, d, e, f;
	cin >> a >> b >> c >> d;
	if (a < c)
		e = c;
	else e = a;
	if (b < d)
		f = b;
	else f = d;
	if (e > f)
		cout << "0";
	else cout << f - e;
	return 0;
}

Measured memory_bytes: 256
#include <stdlib.h>
#include <cmath>
#include <cstdio>
#include <cstdint>
#include <string>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
using namespace std;

int main(){
  long long A,B,M;
  cin >> A >> B >> M;
  vector<long long> a(A);
  vector<long long> b(B);
  for(int i=0; i<A; i++) cin >> a.at(i);
  for(int i=0; i<B; i++) cin >> b.at(i);
  vector<vector<long long>> m(M, vector<long long>(3));
  for(int i=0; i<M; i++) cin >> m.at(i).at(0) >> m.at(i).at(1) >> m.at(i).at(2);

  map<long long,map<long long,long long>> m_map;
  for(int i=0;i<M;i++){
    m_map[m.at(i).at(0)][m.at(i).at(1)]=
      max(m.at(i).at(2),m_map[m.at(i).at(0)][m.at(i).at(1)]);
  }

  long long min_a=*std::min_element(a.begin(), a.end());
  long long min_b=*std::min_element(b.begin(), b.end());
  long long min_p=min_a+min_b;

  for(int i=0;i<A;i++){
    if(m_map.count(i+1)==1){
      for(auto tmp : m_map.at(i+1)){
	auto b_in=tmp.first;
	long long tmp_p=a.at(i)+b.at(b_in-1)-tmp.second;
	min_p=min(min_p,tmp_p);
      }
    }
  }

  /*
  for(long long i=0;i<A;i++){
    for(long long j=0;j<B;j++){
      long long tmp_p=a.at(i);
      tmp_p += b.at(j);
      if(m_map.count(i+1)==1 && m_map.at(i+1).count(j+1)==1)
	tmp_p -= m_map.at(i+1).at(j+1);
      min_p=min(min_p,tmp_p);
    }
  }
  */
  
  cout << min_p << endl;
  return 0;
}


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

using namespace std;
typedef long long ll;





//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define RALL(x) (x).rbegin(),(x).rend() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F firstw

#define S second
#define seq vector
#define READLINE(vec,time) for(int indexofvec=0;indexofvec<time;indexofvec++)cin>>vec[indexofvec]
#define VPRINT(vec) for(auto i : vec){cout << i<<" ";}cout<<endl;
#define lambda []
#define clambda [=]
#define reflambda [&]

template<typename A,typename B,class functype>
void select(vector<A>& in,vector<B>& out,functype func){
    out.resize(in.size());

    for(int i =0;i<in.size();i++){
        out[i]=func(in[i]);
    }


}








signed main(){

    string L;
    cin >>L;
    int len =L.length();
    vector<ll>dpl(len);
    vector<ll>dpc(len);
    dpc[0] = 2;
    dpl[0] = 1;

    for(int i =1;i<len;i++){

        if(L[i]=='1'){
            dpc[i]=(dpc[i-1]*2)%MOD;
            dpl[i] += ((dpl[i-1]*3)%MOD+ dpc[i-1])%MOD;
        }else if (L[i]=='0')
        {
            dpc[i]=(dpc[i-1]%MOD);
            dpl[i] += (dpl[i-1]*3)%MOD;
        }else{
            abort();
        }
    }

    cout << (dpc[len-1]+dpl[len-1])%MOD << endl;

}

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

void solve() {
	int l;
	cin >> l;

	int n = 1, cnt = 1;
	vector<vector<int> > res;
	while ((cnt << 1) <= l) {
		res.push_back({n, n + 1, 0});
		res.push_back({n, n + 1, 1 << (n - 1)});
		n++;
		cnt <<= 1;
	}

	for (int i = 0; i < n - 1; i++)
		if (l & (1 << i)) {
			res.push_back({i + 1, n, cnt});
			cnt += 1 << i;
		}

	cout << n << " " << res.size() << endl;
	for (auto x: res)
		cout << x[0] << " " << x[1] << " " << x[2] << endl;
}

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define SORTR(v,n) sort(v, v+n, greater<int>());
#define SORTPairSecond(v, n) sort(v, v+n, pairCompareSecond);
#define int long long    // %d=>%lld, 1<<n  => 1LL<<n
#define pb push_back

using namespace std;
typedef long long ll;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> piii;
typedef pair<ll, pll> plll;
bool pairCompareSecond(const pii& firstEl, const pii& secondEl) {
    return firstEl.second > secondEl.second;
}

const ll MOD = 1000000007;
const int INF = 1000000007;
// const int INF = 0x3f3f3f3f;
// const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll LLINF = 1LL << 50;
const double PI = acos(-1);
const double EPS = 0.000000001;

// 10^5の二次元配列は持てない．許されるのは計10^7くらいまで．

struct edge{int to,cost;};

const int MAX_V = 100000;
vector<edge> G[MAX_V];
int V,E;
int s,t,c;

int d[MAX_V];

const int MAX_q = 100000;
int q, k, x[MAX_q],y[MAX_q];

int dijkstra(int s){

    priority_queue<pii,vector<pii>,greater<pii> > que;
    fill(d,d+V,LLINF);
    d[s] = 0;
    que.push(pii(d[s],s));

    while(!que.empty()){
        pii p = que.top();
        que.pop();
        int v = p.second;
        if (d[v] < p.first)
            continue;
        for(int i = 0;i < G[v].size();i++){
            edge e = G[v][i];
            if(d[e.to] > d[v] + e.cost){
                d[e.to] = d[v] + e.cost;
                que.push(pii(d[e.to],e.to));
            }
        }
    }
}

signed main(){


    cin >>V;
    E = V-1;
    for(int i = 0;i < E;i++){
        cin >> s>>t>>c;
        G[s-1].pb((edge){t-1,c});
        G[t-1].pb((edge){s-1,c});
    }

    cin >>q>>k;
    for(int i = 0;i < q;i++){
        cin>>x[i]>>y[i];
    }

    dijkstra(k-1);

    for(int i = 0;i < q;i++){
        cout<< d[x[i]-1]+d[y[i]-1]<< endl;
    }
}

Measured memory_bytes: 12656
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,x,n) for(int i=x;i<n;i++)
#define mod 1000000007 //10^9+7
#define INF 1000000000000 //10^12
#define F first
#define S second
#define P pair<int,int>
#define all(vec) vec.begin(),vec.end()
int n;
int a[300000];
int nl[300000],nr[300000];
int ans=0;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(i+a[i]<=n)nl[i+a[i]]++;
        if(i-a[i]>=1)nr[i-a[i]]++;
    }
    for(int i=1;i<=n;i++){
        ans+=nl[i]*nr[i];
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 8244
import collections
import itertools
n, k = map(int, input().split())
c = collections.Counter(input()[0] for _ in range(n))
for r in itertools.count(0):
    if len(c) < k:
        print(r)
        break
    c2 = collections.Counter(x for x, n in c.most_common(k))
    c -= c2

Measured memory_bytes: 3444
#include <stdio.h>

// 入力文字列の大文字小文字を入れ替えて出力
int main()
{
	char achInputStr[1200] = { 0 };
	int iDiff = 'a' - 'A';
	int iCnt;

	// 改行以外を読み込み
	scanf("%[^\n]", achInputStr);

	for (iCnt = 0; achInputStr[iCnt] != '\0'; iCnt++)
	{
		if (achInputStr[iCnt] >= 'A' && achInputStr[iCnt] <= 'Z')	// 大文字
		{
			printf("%c", achInputStr[iCnt] + iDiff);
		}
		else if (achInputStr[iCnt] >= 'a' && achInputStr[iCnt] <= 'z')	// 小文字
		{
			printf("%c", achInputStr[iCnt] - iDiff);
		}
		else
		{
			printf("%c", achInputStr[iCnt]);
		}
		
	}
	printf("\n");

	return 0;
}


Measured memory_bytes: 2036
import java.util.*;
public class Main{
    static Scanner kbd = new Scanner(System.in);
    public static void main(String[] args){
	while(kbd.hasNext()){
	    int n = kbd.nextInt();  // n人の委員がいて、
	    int q = kbd.nextInt();  // q人が過半数
	    if(n!=0 && q!=0){
		int[] date = new int[100];
		//会議の候補日は1日後以上100日後未満

		while(n!=0){
		    //委員一人一人について、
		    int s = kbd.nextInt(); // s日分の予定が空いていて、
		    while(s!=0){
			int a = kbd.nextInt(); // 具体的にはa日が可
			date[a]++;
			s--;
		    }
		    n--;
		}

		int ans = 0;
		for(int i=0; i<date.length; i++){
		    //その日に集まれる人数が過半数qを超えていて、かつ最も多い日を探す
		    if(date[i]>=q && date[ans]<date[i])
			ans = i;  //答えとして出力するのは人数
		}
		//過半数を超えていない限り、ansは0のまま
		System.out.println(ans);
	    }
	}
    }
}

Measured memory_bytes: 62740
N = int(input())
mon = list(map(int,input().split()))
hero = list(map(int,input().split()))

ans = 0
for i in range(N):
  if mon[i] >= hero[i]:
    ans += hero[i]
  else:
    tem = mon[i+1]
    mon[i+1] = max(0,mon[i+1]-(hero[i]-mon[i]))
    ans += mon[i]+tem-mon[i+1]
    
print(ans)
  

Measured memory_bytes: 19116
#include<bits/stdc++.h>
#define int long long
#define maxn 200000
#define mod 1000000007
#define FLASH cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
#define FILEIO freopen("/home/aman/Desktop/Kachda/input.txt", "r", stdin); //freopen("/home/aman/Desktop/Kachda/output.txt", "w", stdout);
using namespace std;

int power(int a, int b, int m)
{
    int ans = 1;
    a %= m;
    while(b){
        if(b & 1) ans = (ans * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return ans;
}

int n, dp[maxn + 1], sz[maxn + 1], fac[maxn + 1], dp1[maxn + 1];
vector <int> v[maxn + 1];

int C(int n, int r){
	if(r > n or r < 0) return 0;
	int ans = fac[n];
	ans *= power((fac[r]*fac[n - r])%mod, mod - 2, mod);
	ans %= mod;
	return ans;
}

void dfs0(int node, int par){
	dp[node] = dp1[node] = 1;
	sz[node] = 1;
	for(auto x: v[node]){
		if(x == par) continue;
		dfs0(x, node);
		sz[node] += sz[x];
	}
}

void dfs1(int node, int par){
	dp[node] *= fac[sz[node] - 1];
	for(auto x: v[node]){
		if(x == par) continue;
		dfs1(x, node);
		dp[node] *= (dp[x]*power(fac[sz[x]], mod - 2, mod))%mod;
		dp[node] %= mod;
	}
}

void dfs2(int node, int par){
	if(node == 1)
		dp1[node] = dp[node];
	else{
		dp1[node] = ((dp1[par]*power(dp[node], mod - 2, mod))%mod)*fac[sz[node]];
		dp1[node] %= mod;
		dp1[node] *= power(fac[n - sz[node]], mod - 2, mod);
		dp1[node] %= mod;
		dp1[node] *= fac[n - sz[node] - 1];
		dp1[node] %= mod;
		for(auto x: v[node]){
			if(x == par) continue;
			dp1[node] *= (dp[x]*power(fac[sz[x]], mod - 2, mod))%mod;
			dp1[node] %= mod;
		}
	}

	for(auto x: v[node]){
		if(x == par) continue;
		dfs2(x, node);
	}
}
signed main()
{
   
    FLASH

    fac[0] = 1;
    for(int i = 1; i <= maxn; i++) fac[i] = (i*fac[i - 1])%mod;

    cin>>n;
    for(int i = 1;  i < n; i++){
    	int a, b;
    	cin>>a>>b;
    	v[a].push_back(b);
    	v[b].push_back(a);
    }

    dfs0(1, 0);
    dfs1(1, 0);
    dfs2(1, 0);
    for(int i = 1; i <= n; i++)cout<<dp1[i]<<'\n';
}

Measured memory_bytes: 20976