akhauriyash/Code-Regression huggingface dataset:
/*
  Author - KISHAN TIWARI
  Dream bigger. Do bigger.
  Wake up with determination. Go to bed with satisfaction.
*/
//Sometimes later becomes never. Do it now.
#include<bits/stdc++.h>
using namespace std;
#define ll           long long
#define f(i,a,b)     for(ll i=a;i<b;i++)
#define mod          1000000007
#define fi           first
#define se           second
#define pa           pair <ll,ll>
#define mp           make_pair
#define pb           push_back
#define ve           vector<ll>
#define vep          vector< pa >
#define all(a)       a.begin(), a.end()
#define sz(x)        (ll)x.size()
#define c(t)         cout<<t<<"\n"
using namespace std;
vector<ll> v[200001],a(200001,0);
void dfs(ll c,ll p)
{
    f(i,0,v[c].size())
    {
        if(v[c][i]==p)
        continue;
        a[v[c][i]]+=a[c];
        dfs(v[c][i],c);
    }
    
}
void solve()
{  ll n,q;
cin>>n>>q;
f(i,0,n-1)
{
    ll x,y;
    cin>>x>>y;
    v[x].pb(y);
    v[y].pb(x);
}
f(k,0,q)
{
    ll p,x;
    cin>>p>>x;
    a[p]+=x;
}
dfs(1,0);
f(i,1,n+1)
cout<<a[i]<<" ";
cout<<"\n";
}
int main()
{
    ios::sync_with_stdio(true);
   //freopen ("input.txt","r",stdin);
   //freopen ("output.txt","w",stdout);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
    //cin>>t;
    while(t--)
    {

        solve();
    }
return 0;
}


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


using namespace std;
typedef long long ll;

#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VP vector<pair<int,int>>
#define VPP vector<pair<int,pair<int,int>>>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define fore(i,a) for(auto &i:a)
typedef pair <int, int> P;
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

const int  INF = 1 << 29;
const ll INFL = 1LL << 60;
const ll mod = 1000000007;


ll pow_mod(ll n, ll k, ll m) {
	ll r = 1;
	for (; k > 0; k >>= 1) {
		if (k & 1)r = (r*n) % m;
		n = (n*n) % m;
	}
	return r;
}

const int MAX = 2010000;
long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod%i] * (mod / i) % mod;
		finv[i] = finv[i - 1] * inv[i] % mod;
	}
}

long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}

long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}


int main() {
	COMinit();

	ll r1, r2, c1, c2;
	cin >> r1 >> c1 >> r2 >> c2;

	ll ans = 0;

	FOR(i, r1, r2 + 1) {
		ll cur;
		cur = c2 + 1;
		cur *= COM(c2 + i + 1, i);
		cur %= mod;
		cur -= c1 * COM(c1 + i, i);
		cur += c1 * mod;
		cur %= mod;
		cur *= modinv(i + 1, mod);
		cur %= mod;
		ans += cur;
		ans %= mod;
	}
	cout << ans << endl;

}

Measured memory_bytes: 47488
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
        ifstream in("input.txt");
        //ofstream out("output.txt");
        #define cin in
        //#define cout out
#endif
int const MAXN=110, MAXK=100100, M=1000000007;
int n, k, c[MAXN], dp[MAXK][MAXN], prefix[MAXK][MAXN];
void compute_prefix(int col){
	int current=0;
	for(int row=0;row<=k;row++){
		prefix[row][col]=(dp[row][col]%M+current%M)%M;
		current+=(dp[row][col]%M);
		current%=M;
	}
}
int sum(int start, int end, int where){
	if(start==0) return prefix[end][where];
	int res=prefix[end][where]-prefix[start-1][where];
	if(res<0) res+=M;
	return res;
}
void print(){
	cout<<"DP state:\n";
	for(int i=0;i<=k;i++){
		for(int j=0;j<n;j++)
			cout<<dp[i][j]<<" ";
		cout<<"\n";
	}
	cout<<"Prefix Sums:\n";
	for(int i=0;i<=k;i++){
		for(int j=0;j<n;j++)
			cout<<prefix[i][j]<<" ";
		cout<<"\n";
	}
}
int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++)
		cin>>c[i];
	for(int col=n-1;col>=0;col--){
		if(col==n-1){
			for(int row=0;row<=c[col];row++)
				dp[row][col]=1;
		}
		else{
			for(int row=0;row<=k;row++){
				int start=0, end=min(row,c[col]);
				int add=max(0,row-c[col]);
				start+=add, end+=add;
				dp[row][col]=sum(start,end,col+1);
			}
		}
		compute_prefix(col);
	}
	cout<<dp[k][0];
}

Measured memory_bytes: 86272
from sys import stdin

input = stdin.readline



def solve():
    Y, X, K = map(int, input().split())
    c = [inp for inp in stdin.read().splitlines()]
    res = 0
    for ymask in range((1<<Y) - 1):
        for xmask in range((1<<X) - 1):
            cnt = 0
            for y in range(Y):
                for x in range(X):
                    if ymask & (1<<y) == 0 and xmask & (1<<x) == 0 and c[y][x] == '#':
                        cnt += 1
            if cnt == K:
                res +=1
    print(res)



if __name__ == '__main__':
    solve()


Measured memory_bytes: 73884
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<ll> vvll;
#define sort(v) sort(v.begin(), v.end())
#define rev(r) reverse(r.begin(), r.end())
#define cout(cc) cout << cc << endl

int main() {
  int64_t N,A,B,aa,t;
  aa=0;
  cin >> N >> A >> B;
  for(int i=1;i<=N;i++){
  	t=0;
    int bb=i;
    while(bb>0){
      t+=bb%10;
      bb/=10;
    }
    if(A<=t &&t<=B) aa+=i;
  }
  cout(aa);
}


Measured memory_bytes: 256
#include <iostream>
#include<algorithm>
using namespace std;
int main(){
    int a[3];
    cin>>a[0]>>a[1]>>a[2];
    sort(a,a+3,greater<int>());
    if(a[0]==7&&a[1]==5&&a[2]==5)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}


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

int main(){
	double t[10], a, b;
	char c;
	while(cin >> t[0] >> c){
		for(int i = 1;i< 10;i++){cin >> t[i] >> c;t[i] += t[i-1];}
		cin >> a >> c >> b;
		double tmp = t[9]/(a+b)*a;
		int ans = 1;
		while(tmp > t[ans-1])ans++;
		cout << ans << endl;
	}
	return 0;
}

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

using namespace std;

#define REP(i,m) for(ll i=0; i<m; i++)
#define FOR(i,n,m) for(ll i=n; i<m; i++)
#define INF 1000000007
#define INFL (1LL << 60)
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define SORT(v) sort(ALL(v))
#define pb push_back
#define ll long long int
#define P pair<ll, ll>

int main(){
    int n, m;
    cin >> n >> m;
    priority_queue<int> que;
    REP(i, n){
        int a;
        cin >> a;
        que.push(a);
    }
    REP(i, m){
        int t = que.top(); que.pop();
        t /= 2;
        que.push(t);
    }
    ll ans = 0;
    while(!que.empty()){
        int t = que.top(); que.pop();
        ans += t;
    }
    cout << ans << endl;
}

Measured memory_bytes: 892
#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
#define mod 1000000007

using namespace std;

int niz[110];
int main()
{
	int n;
	ll k;
	cin >> n >> k;
	vector<ll> dp(k + 2);
	for (int i = 1; i <= n; i++)
		cin >> niz[i];
	dp[0] = 1;
	for (int i = 1; i <= k; i++)
		dp[i] += dp[i - 1];
	for (int i = 1; i <= n; i++)
	{
		int l = niz[i] + 1;
		vector<ll> curr(k + 2, 0);
		curr[0] = 1;
		for (int j = 1; j <= k; j++)
		{
			curr[j] = curr[j - 1];
			curr[j] += dp[j];
			if (j >= l)
				curr[j] -= dp[j - l];
			curr[j] %= mod;
			if (curr[j] < 0)
				curr[j] += mod;
		}
		dp = curr;
	}
	if (k == 0)
		cout << 1 << endl;
	else
		cout << (dp[k] - dp[k - 1] + mod) % mod << endl;
}


Measured memory_bytes: 1792
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;
constexpr double pi = acos(-1);
constexpr double EPS = 1e-10;

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

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

    int n; cin>>n;
    vector<double> a(n);
    double sum = 0;
    for(int i=0; i<n; i++){
        cin>>a[i];
        a[i] = 1. * 1 / a[i];
        sum += a[i]; 
    }

    printf("%.10f\n", 1. * 1 / sum);
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace c
{
    class Program
    {
        static void Main(string[] args)
        {
            char[] s = Console.ReadLine().ToCharArray();
            int k = int.Parse(Console.ReadLine());
            for (int i = 0; i < s.Length; i++)
            {
                if (s[i] == 'a') continue;
                if ('z' - s[i] < k)
                {
                    k -= ('z' - s[i] + 1);
                    s[i] = 'a';
                }
            }
            k %= 26;
            if (s[s.Length - 1] + k <= 'z')
            {
                s[s.Length - 1] = (char)(s[s.Length - 1] + k);
            }
            else
            {
                s[s.Length - 1] = (char)(s[s.Length - 1] + k - 26);
            }
            Console.WriteLine(s);
        }
    }
}


Measured memory_bytes: 3288
D=int(input())
c=list(map(int,input().split()))
s=[list(map(int,input().split())) for _ in range(D)]

last=[0]*26


for d in range(1,D+1):
    ans=0
    for choice in range(1,27):
        ans_tmp=0
        ans_tmp+=s[d-1][choice-1]
        last[choice-1]=d
        for i in range(26):
            ans_tmp-=c[i]*(d-last[i])
        if ans_tmp>ans:
            case=choice
            ans=ans_tmp
    last[case-1]=d
    print(case)

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

int main() {
  int mt[10];

  for(int i=0;i<10;i++) cin >> mt[i];

  sort(mt,mt+10);

  for(int i=9;i>=7;i--) cout << mt[i] <<endl;

  return 0;

}

Measured memory_bytes: 1176
#include <iostream>

using namespace std;

int main(){
    int a[3];
    int c5 = 0;
    int c7 = 0;
    for(int i=0; i<3; ++i){
        cin >> a[i];
        if(a[i]==5) c5++;
        else if(a[i]==7) c7++;
    }
    if(c5==2 && c7==1) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;

}

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

int main(){
  int N, K; cin >> N >> K;
  int L[55];
  for(int i = 0; i < N; i++) cin >> L[i];
  
  sort(L, L + N, greater<int>());
  int ans = 0;
  for(int i = 0; i < K; i++){
    ans += L[i];
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main (void) {
  
  int N,A[100];
  float B[100];  //逆数の配列//
  
  //入力//
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
  }
  
  //逆数の総和をaとする//
  float a = 0.0;
  for (int i = 0; i < N; i++) {
    B[i] = 1 / (float)A[i];
    a += B[i];
  }
  
  //逆数の総和の逆数をbとする//
  float b = 1 / a;
  
  //出力//
  printf("%f", b);
  
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
long long mo = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }

ll a[51] = {};
ll p[51] = {};

ll solve(ll N, ll X){
    if(X >= a[N] - 1){
        return p[N];
    }else if(a[N]-1 > X && X > a[N]/2 + 1){
        return p[N-1] + 1 + solve(N-1, X-a[N-1]-2);
    }else if(X == a[N]/2 + 1){
        return p[N-1] + 1;
    }else if(a[N]/2 + 1 > X && X > 1){
        return solve(N-1, X-1);
    }else if(X == 1 && N == 0){
        return 1;
    }else{
        return 0;
    }
}

int main(){
    ll N,X;
    cin >> N >> X;
    a[0] = 1;
    p[0] = 1;
    rep(i,50){
        a[i+1] = 2*a[i] + 3;
        p[i+1] = 2*p[i] + 1;
    }
    cout << solve(N,X) << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

using std::string;
using std::vector;
using std::set;
using std::multiset;
using std::unordered_set;
using std::map;
using std::multimap;
using std::unordered_map;
using std::pair;
using std::cin;
using std::cout;

using boost::multiprecision::cpp_int;
using cpp_dec_float_1000 = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000>>;

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

constexpr char CRLF  = '\n';
constexpr char SPACE = ' ';
constexpr char VECTOR_COUT_SEPARATOR = SPACE;
constexpr ll INF = 1000'000'007;
constexpr int MOD = 1000'000'007;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> std::ostream& operator<< (std::ostream& os, const std::vector<T>& vc) { for(auto it = vc.begin(); it != vc.end(); ++it) { if (std::next(it) == vc.end()) os << *it; else os << *it << VECTOR_COUT_SEPARATOR; } return os; }
template<class T1, class T2> inline std::ostream & operator<< (std::ostream & os, const std::pair<T1, T2> & p) { return os << p.first << ' ' << p.second; }
template<class T> T modinv(T a, T m) { T b = m, u = 1, v = 0; while (b) { T t = a / b; a -= t * b; boost::swap(a, b); u -= t * v; boost::swap(u, v); } u %= m; if (u < 0) u += m; return u; }

struct Tmp
{
public:
  Tmp(int N);
};

Tmp::Tmp(int N){}

void solve(void)
{
  int N; cin >> N;
  string s; cin >> s;
  for (int i = 0; i < (int)s.size(); ++i) {
    s[i] += N;
    if (s[i] > 'Z') {
      s[i] -= ('Z' - 'A' + 1);
    }
  }
  cout << s << CRLF;
  return;
}

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

  solve();

  return 0;
}


Measured memory_bytes: 256
fun main(args : Array<String>) {
    val n = readLine()!!.toLong()
    val nn = divisor(n)

    var min = n-1
    for (i in nn) {
        if (n % i == 0L) {
            val mov = (i-1) + (n / i)-1
            if (mov < min) min = mov
        }
    }

    println(min)
}

fun divisor(value : Long) : List<Long> {
    val max = Math.sqrt(value.toDouble()).toLong()
    return (1..max)
        .filter { value % it == 0L }
        .map { listOf(it, value / it) }
        .flatten()
        .sorted()
}

Measured memory_bytes: 46188
import java.io.*;
import java.util.*;

class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().split(" ");
		int n = Integer.parseInt(str[0]);
		int[] a = new int[n];
		str = br.readLine().split(" ");
		for(int i = 0; i < n; i++) a[i] = Integer.parseInt(str[i]);
		str = br.readLine().split(" ");
		int m = Integer.parseInt(str[0]);
		str = br.readLine().split(" ");
		boolean flag = true;
		for(int i = 0; i < m; i++){
			int b = Integer.parseInt(str[i]);
			if(Arrays.binarySearch(a, b) < 0) flag = false;
		}
		if(flag) System.out.println(1);
		else System.out.println(0);
	}
}



Measured memory_bytes: 67724
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		char c[][] = new char[H][W];
		for (int i=0;i<H;i++) {
			String str = sc.next();
			for (int j=0;j<str.length();j++) {
				c[i][j] = str.charAt(j);
			}
		}
		for (int i=0;i<H;i++) {
			boolean isBlack= false;
			boolean kaigyou = false;
			for (int j=0;j<W;j++) {
				isBlack= false;
				for (int k=0;k<H;k++) {
					if (c[k][j]=='#') {
						isBlack = true;
						break;
					}
				}
				if (isBlack==false) {
					continue;
				}
				isBlack= false;
				for (int k=0;k<W;k++) {
					if (c[i][k]=='#') {
						isBlack = true;
						break;
					}
				}
				if (isBlack==true ) {
					System.out.print(c[i][j]);
					kaigyou = true;
				}
			}
			if (kaigyou==true) {
				System.out.println();
			}
		}
	}
}

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

int main() {
  ll x,y;
  cin >> x >> y;
  int ans = 0;
  while(x <= y){
    x *= 2;
    ans++;
  }
  cout << ans << endl;
}

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

int main(){
    ll x;
    cin >> x;
    int y = 0;
    ll m = 100;
    while(m < x){
        m += (double)0.01 * m;
        y++;
    }
    cout << y << endl;
    return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

int n, arr[100100], k;
bool vis[100100];
int dp[100100];

int func( int pos ) {
  if ( pos == n ) return 0;
  if (vis[pos]) return dp[pos];
  vis[pos] = 1;
  int res = 1e9;
  for (int i = 1; i <= k; ++i) {
    if ( pos + i <= n ) 
      res = min(res, func(pos + i) + abs(arr[pos] - arr[pos + i]));
  }
  return dp[pos] = res;
}

int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) cin >> arr[i];
  cout << func(1) << endl;
  return 0;
}

Measured memory_bytes: 5760
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
using namespace std;


int deg[114514];
int main(void)
{
	int n,m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i)
	{
		int a, b;
		cin >> a >> b;
		--a; --b;
		deg[a]++; deg[b]++;
	}
	for (int i = 0; i < n; ++i)
	{
		if (deg[i] % 2)
		{
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
	return 0;
}


Measured memory_bytes: 640
#include<cassert>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int N;

int cnt = 0;
char query(int pos) {
    assert(cnt < 20);
    cnt++;

    printf("%d\n", pos);
    fflush(stdout);
    static char buf[11];
    scanf("%s", buf);
    return *buf;
}

void MAIN() {
    scanf("%d", &N);
    int left = 0, right = N;
    char left_v = query(0);
    if (left_v == 'V') {
	return;
    }

    while (right - left > 2) {
	int mid = (left + right) / 2;
	char t = query(mid);
	if (t == 'V') {
	    return;
	}  else {
	    bool odd = (mid - left + 1) & 1;
	    bool same = (left_v == t);
	    if (odd == same) {
		left = mid;
		left_v = t;
	    } else {
		right = mid;
	    }
	}
    }

//    eprintf("OK\n");
    query(left+1);
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 852
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: u128,
        a: u128,
        b: u128,
        c: u128,
        d: u128,
        e: u128,
    }

    let mut min_ae = a;
    min_ae = std::cmp::min(min_ae, b);
    min_ae = std::cmp::min(min_ae, c);
    min_ae = std::cmp::min(min_ae, d);
    min_ae = std::cmp::min(min_ae, e);

    println!("{}", 5u128 + (n - 1) / min_ae);
}


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

#define pb push_back
#define lob lower_bound
#define upb upper_bound
#define ff first
#define ss second
#define beg begin()
#define en end()
#define rbeg rbegin()
#define ren rend()
#define mem(a,b) memset(a,b,sizeof a)
#define mem0(a) memset(a,0,sizeof a)
#define mem1(a) memset(a,1,sizeof a)
#define memm(a) memset(a,-1,sizeof a)


typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
//~ const int tam=1000;
const int inf=(int)1e9;

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    int n,t;
    cin>>n>>t;
    int cost=inf,tim=-1;
    for(int i=0; i<n;++i){
		int x,y;
		cin>>x>>y;
		if(x<cost&&y<=t){
			cost=x;
		}
	}
	
	if(cost==inf){
		cout<<"TLE";
	}else cout<<cost;
	cout<<endl;
    
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
//const ll MOD = ;
ll mod(ll A, ll M) {return (A % M + M) % M;}
const ll INF = 1LL << 60;
template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
ll divceil(ll A, ll B) {return (A + (B - 1)) / B;}
ll myctoi(char C) {return C - '0';}
char myitoc(ll N) {return '0' + N;}
#define FINALANS(A) {cout << (A) << '\n'; exit(0);}

int main()
{
  const long double PI = acosl(-1);

  long double a, b, x;
  cin >> a >> b >> x;

  long double ans0 = atan2l(2 * a * a * b - 2 * x, a * a * a) * 180.0 / PI;
  long double ans1 = atan2l(a * b * b, 2 * x) * 180.0 / PI;
  cout << fixed << setprecision(10);
  if (a < b / (tanl(ans1 * PI / 180.0)))
    cout << ans0 << endl;
  else
    cout << ans1 << endl;

  cerr << fixed << setprecision(10);
  //cerr << PI << endl;
  //cerr << b / (tanl(ans1) * PI / 180.0) << endl;
  //cerr << ans0 << " " << ans1 << endl;

  //cerr << (long double)((2 * b - a * tanl(ans * PI / 180.0)) * a / 2) << " ";
  //cerr << (long double)(x / a) << endl;
}

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

int main(){
    int N;
    cin >> N;
    vector<string> S(N);
    vector<int64_t> C(N);
    vector<int> sz(N);
    for(int i=0; i<N; i++){
        cin >> S[i] >> C[i];
        sz[i] = S[i].size();
    }

    static int64_t dp[50][21][50][21];
    const int64_t INF = 5e18;
    for(int i=0; i<N; i++) for(int a=0; a<=20; a++) for(int j=0; j<N; j++) for(int b=0; b<=20; b++) dp[i][a][j][b] = INF;
    using V = tuple<int64_t, int, int, int, int>;
    priority_queue<V, vector<V>, greater<V>> que;
    for(int i=0; i<N; i++) for(int j=0; j<N; j++){
        dp[i][0][j][sz[j]] = C[i]+C[j];
        que.emplace(C[i]+C[j], i, 0, j, sz[j]);
    }

    while(que.size()){
        auto [d, i, a, j, b] = que.top(); que.pop();
        if(d > dp[i][a][j][b]) continue;
        if(a == sz[i]){
            for(int s=0; s<N; s++){
                if(d+C[s] < dp[s][0][j][b]){
                    dp[s][0][j][b] = d+C[s];
                    que.emplace(d+C[s], s, 0, j, b);
                }
            }
        }else if(b == 0){
            for(int s=0; s<N; s++){
                if(d+C[s] < dp[i][a][s][sz[s]]){
                    dp[i][a][s][sz[s]] = d+C[s];
                    que.emplace(d+C[s], i, a, s, sz[s]);
                }
            }
        }else if(S[i][a] == S[j][b-1]){
            if(d < dp[i][a+1][j][b-1]){
                dp[i][a+1][j][b-1] = d;
                que.emplace(d, i, a+1, j, b-1);
            }
        }
    }

    int64_t ans = INF;
    for(int i=0; i<N; i++) for(int j=0; j<=sz[i]; j++){
        ans = min(ans, dp[i][j][i][j] - C[i]);
        if(j) ans = min(ans, dp[i][j-1][i][j] - C[i]);
    }
    if(ans > INF/2) ans = -1;
    cout << ans << endl;
    return 0;
}


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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(n);(i)++)
#define repr(i,n) for(int (i)=(n)-1;(i)>=0;(i)--)
#define all(v) (v).begin(),(v).end()
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define pb push_back
#define mod 1000000007
#define inf 1000000000
#define llinf 1000000000000000


typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int,int> pint;
typedef pair<ll,ll> pll;
typedef vector<pint> vpint;



int main(){
    int n;
    cin>>n;
    vint a(n);
    vint ans;
    rep(i,n)cin>>a[i];
    rep(i,n){
        bool check=false;
        repr(j,a.size()){
            if(a[j]==j+1){
                ans.pb(a[j]);
                a.erase(a.begin()+j);
                check=true;
                break;
            }
        }
        if(check==false){
            cout<<-1<<endl;
            return 0;
        }
    }
    reverse(all(ans));
    rep(i,n)cout<<ans[i]<<endl;
}

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

int main() {
  int H,W;
  cin >> H >> W;
  
  vector<string> A(H);
  vector<string> B(W+2,"#");
  
  //最上のシャープ
  for (int i = 0; i < B.size(); ++i) {
    cout << B[i];
  }
  cout << endl;
  
  //真ん中のシャープとstring
  for (int i = 0; i < H; ++i) {
    cin >> A[i];
    cout << '#' << A[i] << '#' << endl;
  }
  
  //一番下のシャープ
  for (int i = 0; i < B.size(); ++i) {
    cout << B[i];
  }
  cout << endl;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &&x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define INSEG(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void PSUM(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    cin >> A;

    vector<int> cnt(61);
    REP(i, N) {
        REP(j, 61) {
            if (A[i] >> j & 1) {
                cnt[j]++;
            }
        }
    }
    int ans = K;
    bool less = false;
    REPR(i, 60) {
        if (K >> i & 1) {
            int x = cnt[i];
            int y = N - x;
            if (x > y) {
                ans ^= 1LL << i;
                less = true;
            }
        } else {
            if (less) {
                int x = cnt[i];
                int y = N - x;
                if (x < y) {
                    ans ^= 1LL << i;
                }
            }
        }
    }

    int S = 0;
    REP(i, N) {
        S += A[i] ^ ans;
    }
    cout << S << endl;
    return (0^_^0);
}



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

int main() {
    long long n,k;
    cin >> n >> k;
    vector<long long> a(n);
    for(long long i=0;i<n;i++){
        cin >> a.at(i);
    }
    long long x=0;
    for(long long i=0;i<n;i++){
      for(long long j=i+1;j<n;j++){
        if(a[i]>a[j]){
          ++x;
        }
      }
    }
    long long y=0;
    for(long long i=0;i<n;i++){
      for(long long j=0;j<n;j++){
        if(a[i]>a[j]){
          ++y;
        }
      }
    }
    long long s=k*(x%1000000007)+((k*(k-1)/2)%1000000007)*(y%1000000007);
    s=s%(1000000007);
    cout << s << endl;
}


Measured memory_bytes: 256
#include<cstdio>

void solve(int n, int y);

int main(void){
    int n, y;

    scanf("%d %d", &n, &y);

    solve(n, y);

    return 0;
}

void solve(int n, int y){
    y /= 1000;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n - i; j++){
            if(i * 10 + j * 5 + (n - i - j) == y){
                printf("%d %d %d\n", i, j, n - i - j);
                return;
            }
        }
    }

    printf("-1 -1 -1\n");
}

Measured memory_bytes: 128
#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <map>

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;        

int inputValue(){
    int a;
    cin >> a;
    return a;
};

template<typename T>
void inputArray(T* p, int a){
    rep(i, a){
        cin >> p[i];
    }
};

void inputVector(vector<int> * p, int a){
    rep(i, a){
        int input;
        cin >> input;
        p -> push_back(input);
    }
}

template <typename T>
void output(T a, int precision = 0) {
    if(precision > 0){
        cout << setprecision(precision)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}

int N;
string s;
#define wolf 'W'
#define sheep 'S'

char reverse(char org) {
    if (org == wolf) return sheep;
    return wolf;
}


string solve(char first, char second) {
    string ans(1, first);
    ans += second;
    repd(i, 1, N+1) {
        if (s[i] == 'o') {
            if (ans[i] == wolf) {
                ans += reverse(ans[i-1]);
            } else {
                ans += ans[i-1];
            }
        } else {
            if (ans[i] == wolf) {
                ans += ans[i-1];
            } else {
                ans += reverse(ans[i-1]);
            }
        }
    }
    if (ans[0] == ans[N] && ans[1] == ans[N+1]) {
        ans.pop_back();
        ans.pop_back();
        return ans;
    } else {
        return "-1";
    }
}

int main(int argc, const char * argv[]) {
    N = inputValue();
    cin >> s;
    s += s[0];

    string ans;
    ans = solve(wolf, wolf);
    if (ans.compare("-1") != 0) {
        output(ans);
        return 0;
    }
    ans = solve(wolf, sheep);
    if (ans.compare("-1") != 0) {
        output(ans);
        return 0;
    }
    ans = solve(sheep, wolf);
    if (ans.compare("-1") != 0) {
        output(ans);
        return 0;
    }
    ans = solve(sheep, sheep);
    output(ans);
    return 0;
}


Measured memory_bytes: 796
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x)+modulo)%modulo)
#define Inf 1000000000
vector<int> ans;
void bfs(int start,auto &E){
	vector<int> dis(E.size(),Inf);
	dis[start] = 0;
	queue<int> Q;
	Q.push(start);
	
	while(Q.size()!=0){
		int from = Q.front();
		Q.pop();
		for(int i=0;i<E[from].size();i++){
			int to = E[from][i];
			if(dis[to]==Inf){
				Q.push(to);
				dis[to] = dis[from]+1;
			}
		}
	}
	
	for(int i=start+1;i<E.size();i++){
		ans[dis[i]-1]++;
	}
}

int main(){
	
	int N,X,Y;
	cin>>N>>X>>Y;
	X--;Y--;
	
	vector<vector<int>> E(N,vector<int>());
	
	for(int i=0;i<N-1;i++){
		E[i].push_back(i+1);
		E[i+1].push_back(i);
	}
	
	E[X].push_back(Y);
	E[Y].push_back(X);
	
	ans.resize(N-1,0);
	
	for(int i=0;i<N;i++){
		bfs(i,E);
	}
	
	for(int i=0;i<N-1;i++)cout<<ans[i]<<endl;
	
    return 0;
}


Measured memory_bytes: 384
use 5.018;
use utf8;
use strict;
use warnings;
use feature qw/say/;
use List::Util qw/min max/;

chomp(my $N = <STDIN>);
chomp(my $as = <STDIN>);
my @as = map { $_ + 0 } split(/ /, $as);
my $max = max(@as);
my $min = min(@as);

my $score = min map { calc_score($_, @as) } ($min..$max);
say($score);

sub calc_score {
    my ($res, @as) = @_;
    my $score = 0;
    $score += ($_ - $res) ** 2 for @as;
    $score;
}


Measured memory_bytes: 896
//intのオーバーフローに気をつけろ,AGCはだいたいlongにしておけ
//毎回余りを求めることでオーバーフローしなくなる
//nextLineよりnextだ
//charは''で囲うんだぞ
//読み込みは先に全部やっておけ
//for文を回す回数に気をつけろ

import java.util.Scanner;

public class Main {

	public static void main(String args[]) throws InterruptedException {
		    Scanner sc = new Scanner(System.in);
		    
		    int x = sc.nextInt();
		    int wa = sc.nextInt();
		    int ans = 0;
		    
		    for(int i = 0; i <= x;i++) {
		    	for(int j = 0; j <= x; j++) {
		    		if(0 <= wa-i-j && wa-i-j <= x ) {
		    			ans++;
		    		}
		    	}
		    }
		    System.out.println(ans);
		    sc.close(); }

	public static void saiki(int a, String b) {
		//再帰コーディングのお手本

		if(a == 0) {
			System.out.println(b);
		}else {
			for(char ch = 'a'; ch <= 'c'; ch++) {
				saiki(a-1,b + ch);
			}
		}
	}

	public static  int gcd(int a, int b) {
	    if (a < b) {
	        int tmp = a;
	        a = b;
	        b = tmp;
	    }

	    int r = -1;
	    while (r != 0) {
	        r = a % b;
	        a = b;
	        b = r;
	    }

	    return a;
	}
}


Measured memory_bytes: 21716
#define	_USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <string>
using namespace std;
int main(){
	
	int c[6];
	int m[6]={1,5,10,50,100,500};
	long long s=0;
	int f=0;
	for(int i=0;i<6;i++){
		cin>>c[i];
		s+=m[i]*c[i];
	}
		
	if(s>=1000)
		f=1;
	
	cout<<f<<endl;
	
	
	

}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using ll = long long;
using P = pair<ll, ll>;
const long double PI = acos(-1.0L);
ll GCD(ll a, ll b) { return b?GCD(b, a%b):a; }
ll LCM(ll a, ll b) { return a/GCD(a, b)*b; }

int n, m, p;

int main() {
    while(1) {
        cin >> n >> m >> p;
        if(n == 0 && m == 0 && p == 0) break;
        vector<int> x(n, 0);
        int sum = 0;
        for(int i = 0; i < n; ++i) {
            cin >> x[i];
            sum += (x[i]*100);
        }
        int money = sum*(100-p)/100;
        if(x[m-1] == 0) cout << 0 << endl;
        else cout << money/x[m-1] << endl;
    }
}


Measured memory_bytes: 3088
package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)

	n := nextInt()
	a := make([]int, n)
	m := map[int]int{}
	for i := 0; i < n; i++ {
		a[i] = nextInt()
		m[a[i]]++
	}

	// fmt.Println(a)
	// fmt.Println(m)

	s := keys(m)
	sort.Sort(sort.Reverse(sort.IntSlice(s)))

	if len(s) >= 2 {
		fmt.Println(s[0] * s[1])
	} else {
		fmt.Println(0)
	}

}

func keys(m map[int]int) []int {
	ks := []int{}
	for k, v := range m {
		if v >= 2 && v < 4 {
			ks = append(ks, k)
		}
		if 4 <= v {
			ks = append(ks, k)
			ks = append(ks, k)
		}
	}
	return ks
}


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

#define ll long long
#define ld long double

#define pii pair<int, int>
#define pci pair<char, int>
#define pcc pair<char, char>

#define vi vector <int>
#define vll vector<long long>
#define vld vector<long double>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>

#define vvi vector<vi>
#define vvll vector<vll>
#define vvld vector<vld>
#define vvb vector<vb>
#define vvc vector<vc>
#define vvs vector<vs>

#define vpii vector<pii>
#define vpci vector<pci>
#define vpcc vector<pcc>

#define all(v) (v).begin(), (v).end()
#define allrev(v) (v).rbegin(), (v).rend()
#define allcomp(v) (v).begin(), (v).end(), comp
#define allrevcomp(v) (v).rbegin(), (v).rend(), comp

const int MOD = 1e9 + 7;
const ld pi = 3.1415926535897932384626433832;

#define line cout<<"\n";
#define fast ios_base::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0);

const int MAX = 1e5;

void solve(int test_case){

    ll n, q, a, b, c;
    cin >> n;

    ll sum = 0;
    vi v(MAX);

    for(int i = 0; i < n; i++){
        cin >> a;
        v[a]++;
        sum += 1ll *  a;
    }

    cin >> q;

    for(int i = 0; i < q; i++){
        cin >> b >> c;
        v[c] += v[b];
        sum += 1ll * (c - b) * v[b];
        v[b] = 0;
        cout << sum;
        line;
    }
}

int main(){
    fast
    int test = 1;
    //cin>>test;
    for(int i = 1; i <= test; i++){
        solve(i);
    }
    return 0;
}


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

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

typedef long long LL;

int main(){
  int n;
  cin >> n;
  vector<int> a(n),b(n),c(n);
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  for(int i=0;i<n;i++){
    cin >> b[i];
  }
  for(int i=0;i<n;i++){
    cin >> c[i];
  }
  sort(a.begin(),a.end());
  sort(b.begin(),b.end());
  sort(c.begin(),c.end());
  vector<LL> kosuu(n,0);
  LL ans=0;
  int i,j;
  j=n-1;
  for(i=n-1;i>=0;i--){
    for(;b[i]<c[j]&&j>=0;j--);
    kosuu[i]=(LL)(n-1-j);
  }
  for(int i=n-2;i>=0;i--){
    kosuu[i]=kosuu[i]+kosuu[i+1];
  }
  j=n-1;
  for(i=n-1;i>=0;i--){
    for(;a[i]<b[j]&&j>=0;j--);
    ans+=(j!=n-1?kosuu[j+1]:0);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2176
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		Integer[] count = new Integer[N];
		for (int i = 0; i < count.length; i++)
			count[i] = 0;
		for (int i = 0; i < count.length; i++) {
			count[sc.nextInt() - 1]++;
		}
		Arrays.sort(count, Comparator.reverseOrder());
		int ans = N;
		for (int i = 0; i < K; i++) {
			ans -= count[i];
		}
		System.out.println(ans);
		sc.close();
	}
}

Measured memory_bytes: 82984
#include<iostream>
#include<string>
#include<vector>
#define MAX 200000
using namespace std;

const int mod = 2019;
int dp[2020];

//aC2を返す
int choose(int a){
    int ans;
    ans = a*(a - 1)/2;

    return ans;
}

int main(){
    string s;
    cin >> s;
    int sl = s.size(); //sのサイズ
    //cout << sl << endl;
    //sの累積和を入れる
    vector<int> t(sl),tt(sl); //累積和
    long long ten = 1; //10の累乗
    long long ss; //s.at(i)のlong long 型

    //cout << endl;

    for(int i = sl - 1;i >= 0;i--){
        ss = (s.at(i) - '0');
        t.at(i) = (ten*ss)%mod;
        ten *= 10;
        ten = ten%mod;
        //cout << i << ":";
        //cout << ten << " ";
        //cout << t.at(i) << endl;
    }

    //累積
    tt.at(0) = t.at(0);
    dp[tt.at(0)]++;
   // cout << tt.at(0) << endl;
    for(int i = 1;i < sl;i++){
        tt.at(i) = (tt.at(i - 1) + t.at(i))%mod;
        //cout << tt.at(i) << endl;
        dp[tt.at(i)]++;
    }

    //mod2019の値が等しいものを見つける

    int ans = dp[0];

    for(int i = 0;i < mod;i++){
        if(dp[i] >= 2){
            ans += choose(dp[i]);
            //cout << "aaa" << endl;
        }
    }

    cout << ans << endl;



    return 0;
}


Measured memory_bytes: 5176
#pragma region kyomukyomupurin

/**
 *    author  : 𝒌𝒚𝒐𝒎𝒖𝒌𝒚𝒐𝒎𝒖𝒑𝒖𝒓𝒊𝒏
 *    created : 2020-04-26 20:40:04
 **/

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

using int64 = long long;

template <class T>
using binary_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) {
  return os << '(' << p.first << ", " << p.second << ')';
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
  int flag = 0;
  for (auto e : vec) os << (flag++ ? ", " : "{") << e;
  return os << (vec.empty() ? "{}" : "}");
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& st) {
  int flag = 0;
  for (auto e : st) os << (flag++ ? ", " : "{") << e;
  return os << (st.empty() ? "{}" : "}");
}

template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::map<T, U>& mp) {
  int flag = 0;
  for (auto e : mp) os << (flag++ ? ", " : "{") << e;
  return os << (mp.empty() ? "{}" : "}");
}

template <class T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
  for (T& e : vec) is >> e;
  return is;
}

#define all(_) begin(_), end(_)
#define rall(_) rbegin(_), rend(_)

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

void debug_out() { std::cerr << '\n'; }

template <class Head, class... Tail>
void debug_out(Head&& head, Tail&&... tail) {
  std::cerr << head;
  if (sizeof...(Tail) != 0) std::cerr << ", ";
  debug_out(std::forward<Tail>(tail)...);
}

#pragma endregion kyomukyomupurin

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

  int n; cin >> n;
  set<string> st;

  while (n--) {
    string s; cin >> s;
    st.emplace(s);
  }

  cout << st.size() << endl;

  return 0;
}

Measured memory_bytes: 19240
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)
typedef long long int i64;
typedef pair<int, int> pint;
string s;
bool dp[501][501];
bool used[501][501];
bool dfs(int l, int r) {
    if(l > r) return 0;
    if(used[l][r]) return dp[l][r];
    used[l][r] = true;
    if(l == r) return dp[l][r] = true;
    if(s[l] != 'm' || s[r - 1] != 'w') return false;
    REP(i, l + 1, r - 1) {
        if(s[i] == 'e') {
            bool a = dfs(l + 1, i);
            bool b = dfs(i + 1, r - 1);
            if(a && b) {
                dp[l][r] = true;
                break;
            }
        }
    }
    return dp[l][r];
}
int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    memset(dp, 0, sizeof(dp));
    memset(used, 0, sizeof(used));
    cin >> s;
    if(dfs(0, s.length())) cout << "Cat" << endl;
    else cout << "Rabbit" << endl;
    return 0;
}

Measured memory_bytes: 1688
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

void b()
{
	int n;
	cin >> n;
	vector<int> w(n);
	for (int i = 0; i < n; i++) {
		cin >> w[i];
	}

	int min = 1000000;
	for (int i = 0; i < n; i++) {
		int sumLeft = 0;
		for (int j = 0; j < i; j++) {
			sumLeft += w[j];
		}
		int sumRight = 0;
		for (int j = i; j < n; j++) {
			sumRight += w[j];
		}
		int val = abs(sumLeft - sumRight);
		if (val < min) {
			min = val;
		}
	}

	cout << min << endl;
}

int main()
{
	b();
}


Measured memory_bytes: 256
N,M=map(int,input().split())
H=list(map(int,input().split()))
links=[[] for i in range(N)]
for i in range(M):
  A,B=map(int,input().split())
  A-=1
  B-=1
  links[A].append(B)
  links[B].append(A)
ans=0
for i in range(N):
  flag=True
  for j in links[i]:
    if H[i]<=H[j]:
      flag=False
      break      
  if flag:
    ans+=1
print(ans)

Measured memory_bytes: 29356
#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

struct E{
	long long int x,y;
	bool operator<(const E& e1)const{
		if(x!=e1.x)return x<e1.x;
		return y<e1.y;
	}
};
int n;
std::map<E,long long int> ms;

long long int f(long long int h,long long int cx,long long int cy,long long int x,long long int y){
	return max(h-abs(cx-x)-abs(cy-y),(long long int)0);
}

long long int f2(long long int l,long long int r,long long int cx,long long int cy){
  long long int m=(l+r)/2;
  int d1=0,u1=0,hit1=0;
  for( auto i = ms.begin(); i != ms.end() ; ++i ) {
      E e1=i->first;
      long long int h2=i->second;
      long long int h3=f(m,cx,cy,e1.x,e1.y);
      if(h2<h3){
      	u1++;
      }else if(h2>h3){
      	d1++;
      }else{
      	hit1++;
      }
  }
  if(d1==0&&u1==0){
  	return m;
  }else if(l==r){
  	return -1;
  }else if(d1>0 && u1>0){
  	return -1;
  }else if(u1>0){
  	return f2(l,m,cx,cy);
  }else{
  	return f2(m+1,r,cx,cy);
  }
}


int main() {
	// your code goes here
	cin>>n;
	for(int i=0;i<n;i++){
		E e1;
		long long int h1;
		cin>>e1.x>>e1.y>>h1;
		ms[e1]=h1;
	}
	long long int ans=-1;
	int ansx,ansy;
	for(int x=0;x<=100;x++){
		for(int y=0;y<=100;y++){
			long long int t=f2(0,2000000000,x,y);
			if(t!=-1){
				ansx=x;
				ansy=y;
				ans=t;
				break;
			}
		}
		if(ans!=-1)break;
	}
	cout<<ansx<<" "<<ansy<<" "<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 888
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    vector<int> cnt(n+1);
    rep(i,n)cnt[i+1]=(s[i]=='#');
    rep(i,n)cnt[i+1]+=cnt[i];
    int ans=inf;
    rep(i,n+1){
        cerr<<2*cnt[i]+(n-i)-cnt[n]<<endl;
        ans=min(ans,2*cnt[i]+(n-i)-cnt[n]);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1412
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>

#define rep(a, b, c) for (int a = b; a < (c); a++)
#define repe(a, b, c) for (int a = b; a <= (c); a++)
#define repr(a, b, c) for (int a = b; a > (c); a--)
#define repre(a, b, c) for (int a = b; a >= (c); a--)

using namespace std;
typedef pair<int, int> P;

int main() {
    while (true) {
        int X, Y, Z;
        cin >> X >> Y >> Z;
        if (X == 0 && Y == 0 && Z == 0) break;
        int Vx[X];
        rep(i, 0, X) cin >> Vx[i];

        P events[Y];
        rep(i, 0, Y) {
            events[i] = P(0, 0);
        }
        rep(i, 0, Z) {
            int N, E, A;
            cin >> N >> E >> A;
            switch (E) {
                case 1:
                    events[N].first = A;
                    break;
                case 2:
                    events[N].second = A;
                    break;
                case 3:
                    events[N].second = -A;
                    break;
            }
        }

        vector< vector<double> > dp(Y + 1, vector<double>(5001, 0));
        dp[0][0] = 1;
        rep(i, 0, Y) {
            rep(j, 0, X) {
                int next_index = min(i + events[i].first + Vx[j], Y);
                rep(k, 0, 5001) {
                    int money = max(0, k + events[i].second);
                    dp[next_index][money] += dp[i][k] / (double)X;
                }
            }
        }

        double ans = 0;
        rep(i, 0, 5001) {
            ans += dp[Y][i] * i;
        }
        cout << (int)ans << endl;
    }
    return 0;
}

Measured memory_bytes: 4860