akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

//全部の場合を考慮すればN項の数列に関して2^N-1回の思考が必要だとわかるため、それを利用する。

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n=sc.nextInt();  //与えられる数列の項数を入力
    int power=(int)Math.pow(2,n)/1;  //2^Nの計算をする(intに直す)
    int sum;
    String binary;
    int array[]=new int[n];  //10進数を2進数に変換した場合の1or0を格納する配列
    int array1[]=new int[n];  //与えられた数列の各項の値を格納する配列
    for(int i=0;i<n;i++){
      array1[i]=sc.nextInt();  //入力で与えられる数列の各項の値を配列に格納
    }
    int q=sc.nextInt();  //問題として与えられる数値の個数を入力
    int answer[]=new int[q];  //答えが出るか(yesかnoか)を数字として控えておく配列
    int array2[]=new int[q];  //問題として与えられる数値を格納する配列
    for(int i=0;i<q;i++){
      array2[i]=sc.nextInt();  //入力で与えられる問題の各数値を配列に格納
      answer[i]=0;  //あらかじめ全ての数字が作れなかった(noだった)と仮定して格納
    }
    for(int i=0;i<power-1;i++){
      sum=0;  //数列の和を控えておく変数
      binary=Integer.toBinaryString(i+1+power);  //10進数の1+2^N～2^(N+1)-1を2進数に変換
      for(int j=0;j<n;j++){
        if(binary.charAt(j+1)=='0') array[j]=0;
        else if(binary.charAt(j+1)=='1') array[j]=1;
        //上述の範囲設定<1+2^N～2^(N+1)-1>はN+1桁の2進数として保存しておき下N桁を切り取るため
      }
      for(int j=0;j<n;j++){
        sum+=(array[j]*array1[j]);  //array[]の要素は0か1のみなのでこれは足すorNotを意味する
        for(int k=0;k<q;k++){
          if(array2[k]==sum)answer[k]=1;  //ここで和と問題を比較し,正解(yes)なら1を控える
        }
      }
    }
    for(int i=0;i<q;i++){
      if(answer[i]==1) System.out.println("yes");  //結果を控える配列の数字に応じて
      else System.out.println("no");               //yes or no を出力する
    }
    sc.close();
  }
}


Measured memory_bytes: 60376
#include<stdio.h>
int main(void){
    char ab;
    while(1){
        scanf("%c",&ab);
        if(ab=='\n')break;
    if(islower(ab)){
        ab=toupper(ab);
        printf("%c",ab);
    }else if(isupper(ab)){
        ab=tolower(ab);
        printf("%c",ab);
    }else{
        printf("%c",ab);
    }
    }printf("\n");
return 0;
}

Measured memory_bytes: 524
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define int ll
//#define double ld
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
ifstream in("input.txt");ofstream out("output.txt");
const int inf=1e18;
const int mod=1e9+7;
int n,k;
vector<int> vec;
vector<vector<int> > dp;
vector<int> pref;
void calcPref(int ind)
{
    pref.assign(k+1,0);
    pref[0]=dp[ind][0];
    for(int i=1;i<=k;i++)
    {
        pref[i]=pref[i-1]+dp[ind][i];
        pref[i]%=mod;
    }
}
int getPref(int l,int r)
{
    int ff;
    if(r>k)
    {
        ff=pref[k];
    }
    else
        ff=pref[r];
    if(l-1<0)
        return ff;
    return (ff+mod-pref[l-1])%mod;
}
signed main()
{
    faster;
    cin>>n>>k;
    vec.resize(n);
    pref.resize(k+1);
    for(int i=0;i<n;i++)
        cin>>vec[i];
    dp.resize(n+1,vector<int>(k+1));
    dp[0][k]=1;
    for(int i=1;i<=n;i++)
    {
        calcPref(i-1);
        for(int j=0;j<=k;j++)
        {
            dp[i][j]=getPref(j,j+vec[i-1]);
            dp[i][j]%=mod;
        }
    }
    cout<<dp[n][0];
    return 0;
}





















Measured memory_bytes: 81024
a, b, c, d = list(input())
op = '+-'
for op1 in op:
    for op2 in op:
        for op3 in op:
            ans = a + op1 + b + op2 + c + op3 + d
            # print(eval(ans))
            if eval(ans) == 7:
                print('{}=7'.format(ans))
                break
        else:
            continue
        break
    else:
        continue
    break


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

int p[101];
int M[101][101];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i < n + 1; i++) {
		cin >> p[i - 1] >> p[i];
	}
	for (int i = 1; i < n + 1; i++)M[i][i] = 0;
	for (int i = 2; i < n + 1; i++) {
		for (int j = 1; j + i - 1 < n + 1; j++) {
			int k = j + i - 1;
			M[j][k] = (1 << 21);
			for (int t = j; t < k; t++) {
				M[j][k] = min(
					M[j][t] + M[t + 1][k] + p[j - 1] * p[t] * p[k],
					M[j][k]
				);
			}
		}
	}
	cout << M[1][n] << endl;
}


Measured memory_bytes: 3120
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

bool dfs(int y, int x, int c, int gy, int gx, vector<vector<int> > &field){
    if(field[y][x] != c) return false;
    if(y==gy && x==gx) return true;
    field[y][x] = 0;
    for(int i=0; i<4; i++){
        if(dfs(y+dy[i], x+dx[i], c, gy, gx, field)) return true;
    }
    return false;
}

int main(){
    while(1){
        int w,h;
        cin >> w >> h;
        if(w==0) break;

        int sx,sy, gx,gy, n;
        cin >> sx >> sy >> gx >> gy >> n;
        vector<vector<int> > b(h+2, vector<int>(w+2, 0));
        for(int i=0; i<n; i++){
            int c,d,x,y;
            cin >> c >> d >> x >> y;
            for(int r=0; r<2; r++){
                b[y][x] = b[y+1][x] = b[y][x+1] = b[y+1][x+1] = c;
                if(d == 0){
                    x += 2;
                }else{
                    y += 2;
                }
            }
        }

        if(b[sy][sx] == 0 || !dfs(sy, sx, b[sy][sx], gy, gx, b)){
            cout << "NG" << endl;
        }else{
            cout << "OK" << endl;
        }
    }
    return 0;
}


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

#define min(x,y) ((x)>=(y))?(y):(x)
#define max(x,y) ((x)<=(y))?(y):(x)

int dp[110][110][110][110] = {0};
int row[110][110] = {0};
int col[110][110] = {0};

int main() {
	int d, down, H, i, j, k, l, left, r, right, u, up, W, x, y; 
	char a[110][110];
	scanf("%d%d", &H, &W);
	for (i=0;i<H;i++) scanf("%s", &a[i]);

	for (i=0;i<H;i++) { for (j=0;j<W;j++) {
		if (a[i][j] == 'E') {
			x = j; y = i;
		}
	} }
//	printf("Exit: %d %d\n", y, x);

	for (j=0;j<=W;j++) col[0][j] = 0;
	for (i=1;i<=H;i++) for (j=1;j<=W;j++) {
		col[i][j] = col[i-1][j] + (a[i-1][j-1] == 'o');
	}
	for (i=0;i<=H;i++) row[i][0] = 0;
	for (i=1;i<=H;i++) for (j=1;j<=W;j++) {
		row[i][j] = row[i][j-1] + (a[i-1][j-1] == 'o');
	}

	dp[0][0][0][0] = 0;
	for (l=0;l<=x;l++) { for (u=0;u<=y;u++) { for (r=0;r<W-x;r++) { for (d=0;d<H-y;d++) {
//		printf("%d %d %d %d\n", l, u, r, d);
		up = max(y-u,d);
		down = min(y+d,H-u-1);
		left = max(x-l,r);
		right = min(x+r,W-l-1);
//		printf("%d %d %d %d\n", up, down, left, right);
		if (l+1 <= x && l+r < x) dp[l+1][u][r][d] = max(dp[l][u][r][d] + col[down+1][x-l] - col[up][x-l], dp[l+1][u][r][d]);
		else dp[l+1][u][r][d] = max(dp[l][u][r][d], dp[l+1][u][r][d]);
//		printf("dp[%d][%d][%d][%d] = %d\n", l+1, u, r, d, dp[l+1][u][r][d]);
		if (u+1 <= y && u+d < y) dp[l][u+1][r][d] = max(dp[l][u][r][d] + row[y-u][right+1] - row[y-u][left], dp[l][u+1][r][d]);
		else dp[l][u+1][r][d] = max(dp[l][u][r][d], dp[l][u+1][r][d]);
//		printf("dp[%d][%d][%d][%d] = %d\n", l, u+1, r, d, dp[l][u+1][r][d]);
		if (x+r+1 < W && l+r < W-x-1) dp[l][u][r+1][d] = max(dp[l][u][r][d] + col[down+1][x+r+2] - col[up][x+r+2], dp[l][u][r+1][d]);
		else dp[l][u][r+1][d] = max(dp[l][u][r][d], dp[l][u][r+1][d]);
//		printf("dp[%d][%d][%d][%d] = %d\n", l, u, r+1, d, dp[l][u][r+1][d]);
		if (y+d+1 < H && u+d < H-y-1) dp[l][u][r][d+1] = max(dp[l][u][r][d] + row[y+d+2][right+1] - row[y+d+2][left], dp[l][u][r][d+1]);
		else dp[l][u][r][d+1] = max(dp[l][u][r][d], dp[l][u][r][d+1]);
//		printf("dp[%d][%d][%d][%d] = %d\n", l, u, r, d+1, dp[l][u][r][d+1]);
	} } } }
//	printf("dp[%d][%d][%d][%d] = %d\n", x, y, W-x-1, H-y-1, dp[x][y][W-x-1][H-y-1]);
	printf("%d\n", dp[x][y][W-x-1][H-y-1]);

	return 0;
}


Measured memory_bytes: 113536
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
using namespace std;


typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
	v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
	stringstream ss;
	ss << f;
	ss >> t;
}


#define REP(i,n) for(int i=0;i<int(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define RALL(v) (v).rbegin(),(v).rend()
#define PB push


#define MOD 1000000009LL
#define EPS 1e-8

int nums[ 3 ] = { 1, 6, 9 };
int dp[ 100001 ];

int dfs( int n )
{
	if( n == 0 ) return 0;
	if( dp[ n ] != ( 1 << 30 ) ) return dp[ n ];

	REP( i, 3 )
	{
		REP( j, n )
		{
			int m = n - pow( nums[ i ], j + 1 );
			if( m < 0 ) break;

			dp[ n ] = min( dp[ n ], dfs( m ) + 1 );

			if( nums[ i ] == 1 ) break;
		}
	}

	return dp[ n ];
}

int main()
{
	int N;
	cin >> N;
	REP( i, N + 1 ) dp[ i ] = 1 << 30;
	cout << dfs( N ) << endl;
	return 0;
}


Measured memory_bytes: 6912
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> LP;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int op(int a, int b){return max(a,b);}

int e(){return 0;}

int main(){
    int N, K;
    cin >> N >> K;
    vector<int> a(N);
    rep(i,N)cin >> a[i];
    segtree<int, op, e> seg(8000000);
    vector<int> ans(N);
    rep(i,N){
        ans[i] = seg.prod(max(0, a[i]-K), a[i] + K + 1) + 1;
        seg.set(a[i], ans[i]);
    }
    int res = 0;
    rep(i,N)res = max(res, ans[i]);
    cout << res << endl;
}

//class rmq_seg{
//    const int MAX_SEG;
//    ll seg_len;
//    vector<ll> segtree;
//    public:
//        rmq_seg(int N, int def) : MAX_SEG(30000000), segtree(MAX_SEG), seg_len(1){
//            while(seg_len < N)seg_len *= 2;
//            rep(i,MAX_SEG)segtree[i] = def;
//        }
//
//        void update(ll l, ll r, ll k){
//        	l += seg_len-1;
//        	r += seg_len-1;
//        	while(l<r){
//        		if(l % 2 == 1){segtree[l] = max(segtree[l], k); ++l;}
//        		l /= 2;
//        		if(r % 2 == 1){segtree[r-1] = max(segtree[r-1], k); --r;}
//        		r /= 2;
//        	}
//        }
//
//        ll get(ll k){
//            k += seg_len-1;
//            ll res = 0;
//            while(k > 0){
//                res = max(res, segtree[k]);
//                k /= 2;
//            }
//            return res;
//        }
//};
//
//int main(){
//    ll N, K;
//    cin >> N >> K;
//    vector<ll> a(N);
//    rep(i,N)cin >> a[i];
//    rmq_seg seg(8000000, 0);
//    vector<int> ans(N,0);
//    rep(i,N){
//        ans[i] = seg.get(a[i]+1) + 1;
//        seg.update(max(1LL, a[i] - K + 1), a[i] + K + 2LL, ans[i]);
//    }
//    cout << ans[N-1] << endl;
//    return 0;
//}
//

Measured memory_bytes: 101236
sx, sy, tx, ty=map(int, input().split())
print('R'*(tx-sx)+'U'*(ty-sy)+'L'*(tx-sx)+'D'*(ty-sy)+'D'+'R'*(tx-sx+1)+'U'*(ty-sy+1)+'LU'+'L'*(tx-sx+1)+'D'*(ty-sy+1)+'R')

Measured memory_bytes: 3060
n, m = gets.split.map(&:to_i)
a = gets.split.map { |s| s.to_i >> 1 }

b = a[0] ^ (a[0] - 1)

if a.any? { |i| i ^ (i - 1) != b }
  puts 0
  exit
end

slcm = a.inject(1, :lcm)

puts (m / slcm + 1) / 2


Measured memory_bytes: 12676
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+1;
std::vector<int> edge[N];
int mi = 1e9;
pair<int,int> nd;
pair<int,int> cend_1;
int par[N];

int main(){
  long long a,b,c,d;
  cin >> a>> b>>c>>d;
  cout<<max(b*d, max(b*c, max(a*c, a*d)))<<endl;
  return 0;
}


Measured memory_bytes: 5988
# coding: utf-8

answer = 0


def calc(leftnum, sum, tempsum , is_insert):

    hitoketa = leftnum % 10
    leftnum = int(leftnum / 10)

    if tempsum == 0:
        tempsum = hitoketa
    else:
        tempsum = int(str(hitoketa) + str(tempsum))

    if is_insert:
        sum += tempsum
        tempsum = 0

    if leftnum == 0:
        if is_insert:
            global answer
            answer += sum
        return

    calc(leftnum, sum, tempsum, True)
    calc(leftnum, sum, tempsum, False)

if __name__ == '__main__':
    inp = int(input())
    calc(inp, 0, 0, True)
    calc(inp, 0, 0, False)
    print(answer)

Measured memory_bytes: 3064
# -*- coding: utf_8 -*-

level = False
def debug(v):
    if level:
        print(v)

n = int(input())
a = []

for i in range(n):
    v = input().split()
    v.pop(0)
    v.pop(0)
    a.append([int(x) for x in v])

debug(a)

for i in range(0, n):
    v = a[i]
    for j in range(n):
        if (j + 1) in v:
            print(str(1), end="")
        else:
            print(str(0), end="")
        if j != n - 1:
            print(" ", end="")
    print()

Measured memory_bytes: 9048
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
#define MOD 1e9+7

int main(){
    int h,w;
    cin >> h >> w;
    int n;
    cin >> n;
    vi a(n);
    rep(i,n) cin >> a[i];
    vi temp;
    rep(i,n){
        rep(j,a[i]){
            temp.push_back(i+1);
        }
    }
    vector<vi> ans(h,vi(w));
    int sum=0;
    rep(i,h){
        if(i%2==0){
            rep(j,w){
                ans[i][w-1-j]=temp[sum];
                sum++;
            }
        }else{
            rep(j,w){
                ans[i][j]=temp[sum];
                sum++;
            }
        }
    }
    rep(i,h){
        rep(j,w){
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
}

Measured memory_bytes: 3724
#include "bits/stdc++.h"
#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl
using namespace std;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define vss vector< vector<string> >
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
#define pb push_back
template<class T> void print(const T& x){cout << x << endl;}
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
typedef long long ll;
const int inf = 1000000001;
const ll INF = 1e18 * 4;

struct SegmentTree {
    private:
        vl arr;
        ll size;
        ll n;
        vl value;
    public:
        SegmentTree(vl array){
            arr = array; 
            size = calc_size(arr);
            n = (size + 1) / 2;
            value = vl(size, 0); // custom
        }

        ll calc_size(vl array){
            int i = 1;
            while(i < array.size()) i <<= 1;
            return (i << 1) - 1;
        }

        void update(ll i, ll x){
            i += n - 1;
            value[i] = x;
            while(i > 0){
                i = (i-1) / 2;
                value[i] = value[2*i+1] || value[2*i+2];
            }
        }

        ll query(ll l, ll r){
            return _query(l, r+1, 0, 0, n);
        }
    
        ll _query(ll l, ll r, ll node_i, ll node_l, ll node_r){
            if(node_r <= l || r <= node_l) return 0; // custom
            if(l <= node_l && node_r <= r) return value[node_i];
            ll c1 = _query(l, r, 2 * node_i + 1, node_l, (node_l + node_r) / 2);
            ll c2 = _query(l, r, 2 * node_i + 2, (node_l + node_r) / 2, node_r);
            return c1 || c2;
        }
        void print(){
            DEBUG_VEC(value);
        }
};

int main(){
    ll N; cin >> N;
    string S; cin >> S;
    ll Q; cin >> Q;

    vector<SegmentTree> trees(26, SegmentTree(vl(N, 0)));

    for(int i=0; i<S.length(); i++){
        int j = (S[i] - 'a');
        trees[j].update(i, 1);
    }
    int t, l, r;
    char c;
    vi ans;
    rep(k, 0, Q){
        cin >> t;
        if(t == 1){
            cin >> l >> c;
            l--;
            trees[S[l] - 'a'].update(l, 0); 
            S[l] = c;
            trees[c - 'a'].update(l, 1);
        } else {
            cin >> l >> r;
            l--; r--;
            ll cnt = 0;
            rep(i, 0, 26){
                cnt += (trees[i].query(l, r) > 0);
            }
            ans.pb(cnt);
        }
    }
    rep(i, 0, ans.size()) cout << ans[i] << endl;
    return 0;
}



Measured memory_bytes: 331456
#include <stdio.h>

#define H 250

void print(int);

int A[H],h;

int main(){

  int i;

  scanf("%d",&h);

  for(i=1; i<=h ; i++){
    scanf("%d",&A[i]);
  }

  for(i=1; i<=h ; i++){
    print(i);
  }

  return 0;

}


void print(int k){


  printf("node %d: key = %d, ",k,A[k]);

  if(k/2 >= 1) printf("parent key = %d, ",A[k/2]);
  if(k*2 <= h) printf("left key = %d, ",A[k*2]);
  if(k*2+1 <= h) printf("right key = %d, ",A[k*2+1]);

  printf("\n");
}

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

if n == 2:
    print(x[1])
    print(x[0])
else:
    y = sorted(x)
    m1 = y[int(n/2)-1]
    m2 = y[int(n/2)]
    if m1 == m2:
        for _ in range(n):
            print(m1)
    else:
        for i in range(n):
            if x[i] <= m1:
                print(m2)
            elif x[i] >= m2:
                print(m1)


Measured memory_bytes: 25224
import itertools as it
while 1:
  n = input()
  if n==0: break
  A = sorted(set([pow(i,2,n) for i in range(1,n)]))[::-1]
  C = [0]*n
  for a,b in it.combinations(A,2): C[a-b] += 2
  D = C[::-1]
  for i in range(n/2): print C[i+1]+D[i]

Measured memory_bytes: 5528
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

int[] calc(int N, int Y) {
    // x + y + z = N
    // 10,000 * x + 5,000 * y + 1,000 * z = Y
    // 上を 10,000 倍して、下から引くと、
    // 5,000 * y + 9,000 * z = 10,000 * N - Y
    // y をループ回して固定化して、z を求める:
    // z = (10,000 * N - Y - 5,000 * y) / 9,000

    for (int y = 0; y <= N; y++) {
        int z = 10000 * N - Y - 5000 * y;
        if (z < 0 || z % 9000 != 0) continue;

        z /= 9000;
        int x = N - (y + z);
        if (x >= 0)
            return [x, y, z];
    }
    return [-1, -1, -1];
}

void main() {
    int N, Y; scan(N, Y);

    auto ans = calc(N, Y);
    writeln(ans.map!(text).join(" "));
}


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

using namespace std;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;

const ll mod=(1e9)+7;
const ll inf=1e16; 

#define rep(i,m,n) for(ll i=m;i<n;i++)
#define repr(i,m,n) for(ll i=m;i>=n;i--)
#define all(x) x.begin(),x.end()

ll h,w,k;
vs s;
vvll a;
ll num=0;

void search(ll l, ll r){
  vll column;
  rep(i,l,r+1){
    rep(j,0,w) if(s[i][j]=='#') {
      column.emplace_back(j);
    }
  }
  sort(all(column));
  
  rep(j,0,column.size()){
   ll v1=0,v2=w-1;
   if(j>=1) v1=column[j-1]+1;
   if(j<column.size()-1) v2=column[j];
   num++;
   rep(i,l,r+1) {
     rep(j,v1,v2+1) a[i][j]=num; 
  }
  }
  
}

void solve(){
  cin >> h >> w >> k;
  s.resize(h);
  a.resize(h,vll(w,-1));
  vll row;
  rep(i,0,h) {
    cin >> s[i];
   rep(j,0,w) if(s[i][j]=='#'){
     row.emplace_back(i);
     break;
   }
  }
  
  rep(i,0,row.size()){
   ll v1=0,v2=h-1;
   if(i>=1) v1=row[i-1]+1;
   if(i<row.size()-1) v2=row[i];
   search(v1,v2); 
  }
  
  
  rep(i,0,h){
    rep(j,0,w-1) cout << a[i][j] << " "; 
    cout << a[i][w-1] << endl;
  }
  
}

int main(){
   cin.tie(nullptr);
  ios::sync_with_stdio(false);
  solve();
}


Measured memory_bytes: 1664
#include "iostream"
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <math.h>
#include <cctype>
#include <stack>
#include <vector>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <iomanip>
using namespace std;
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007


int main(int argc, char const *argv[]) {
  string S;
  std::cin >> S;
  int n=S.size();
  ll ans=0;
  for(int bit=0; bit < (1<<n-1); bit++){
    ll sum=0;
    ll a=S[0]-'0';
    for(int j=0; j<n-1; j++){
      if(bit & (1<<j)){//j番目のフラグが立っていたらそこまでの数を足す
        sum+=a; a=0;//aを0にして1桁から再スタート
      }
      a=10*a+(S[j+1]-'0');//桁を上げていく
    }
    sum+=a;//最後の分
    ans+=sum;
  }

  std::cout << ans << '\n';
  return 0;
}


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

int main(void){
  int a, b, c, max;

  cin >> a >> b >> c;


  if ( ((a + b) == c)
    || ((a + c) == b)
    || ((b + c) == a)) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }

  return 0;
}

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();
		while (sc.hasNext()) {
			if (sc.next().equals("Y")) {
				System.out.println("Four");
				System.exit(0);
			}
		}
		System.out.println("Three");
	}
}


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

int main()
{
	int k,a,b;
	cin>>k>>a>>b;
	for(int i=a;i<=b;i++){
		if(i % k == 0){
			cout<<"OK"<<endl;	
			return 0;
		}
	}
	cout<<"NG"<<endl;
	return 0;
}

Measured memory_bytes: 3636
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
 		Scanner sc = new Scanner(System.in);
 		String s = sc.next();
 		char[] arr = s.toCharArray();
 		int count =0;
 		int idxA =0;
 		int idxZ =0;

 		for(int i=0; i<arr.length; i++){
 			if(arr[i] =='A'){
 				idxA = i;
 				break;
 			}
 		}
 		for(int j = s.length()-1; j>=0; j--){
 			if(arr[j] =='Z'){
 				idxZ = j;
 				break;
 			}
 		}
 		System.out.println(idxZ - idxA + 1);
 	}
} 

Measured memory_bytes: 30084
#include<bits/stdc++.h>
using namespace std;
int main()
{   
	long long  m,n,r,t;
	cin>>m>>n;
	t=m*n;
	do{
		r=m%n;
		m=n;
		n=r;
	}while(r!=0);
	cout<<t/m<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_ll.hpp>
//typedef boost::multiprecision::cpp_ll ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
string alp="abcdefghijklmnopqrstuvwxyz";
//#define endl "\n"
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);


int main(){
    ll k;cin>>k;
    ll n;cin>>n;
    ll a[n];rep(i,0,n-1)cin>>a[i];
    ll b[n];
    rep(i,0,n-2){
        b[i]=a[i+1]-a[i];
    }
    b[n-1]=k-a[n-1]+a[0];
    sort(b,b+n);
    cout<<k-b[n-1]<<endl;
    
    return 0;
}






Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PI pair<P,int>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}
int Mplus(int x,int y) {return (x+y)%M;}
int Msub(int x,int y) {return (x-y+M)%M;}
int Mmul(int x,int y) {return (x*y)%M;}


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

  int n;
  double t,a;
  cin>>n>>t>>a;
  int it=-1;
  double s=inf;
  rep(i,n){
    double h;
    cin>>h;
    if(s>abs(a-(t-h*0.006))){
      s=abs(a-(t-h*0.006));
      //cout<<s<<endl;
      it=i+1;
    }
  }

  cout<<it<<endl;


}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int a, b, c, i, na, nb, nc;

int main()
{
    cin >> a >> b >> c;
    for(i=0; i<=100000; ++i)
    {
        if(a%2==1 || b%2==1 || c%2==1)
        {
            cout << i << '\n';
            return 0;
        }

        na = (b+c)/2;
        nb = (a+c)/2;
        nc = (a+b)/2;
        a = na, b = nb, c = nc;
    }

    cout << -1 << '\n';

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c;
  cin >> a >> b >> c;
  vector<int> A(100000);
  for(int i = 0;i<=a;i++){
    for(int j = 0;j<=b;j++){
      for(int l = 0;l<=c;l++){
        A.at(i*500+j*100+l*50)++;
      }
    }
  }
  int ob;
  cin >> ob;
  cout << A.at(ob) << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <array>
#include <cstdint>
#include <functional>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <utility>
#include <vector>

#define INF 1000000000
#define MOD 1000000007
#define rep(i,a,b) for(uint32 i = (a); i < (b); ++i)
#define bitget(a,b) (((a) >> (b)) & 1)
#define ALL(x) (x).begin(),(x).end()
#define C(x) std::cout << #x << " : " << x << std::endl
#define scanf scanf_s

using int32 = std::int_fast32_t;
using int64 = std::int_fast64_t;
using uint32 = std::uint_fast32_t;
using uint64 = std::uint_fast64_t;



int main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	uint32 n, a, b;
	std::string s;
	std::cin >> n >> a >> b >> s;
	
	rep(i, 0, n) {
		if (s[i] == 'a') {
			if (a + b) {
				std::cout << "Yes\n";
				if (a) {
					--a;
				}
				else {
					--b;
				}
			}
			else {
				std::cout << "No\n";
			}
		}
		else if (s[i] == 'b') {
			if (b) {
				std::cout << "Yes\n";
				--b;
			}
			else {
				std::cout << "No\n";
			}
		}
		else {
			std::cout << "No\n";
		}
	}
	return 0;
}

Measured memory_bytes: 848
x,k,d = gets.split(" ").map(&:to_i)

min_steps = x.abs / d
min1 = x - min_steps * d * (x>0 ? 1 : -1)
min2 = min1 + d * (min1>0 ? -1 : 1)

if k < min_steps then
    puts (x - k * d * (x>0 ? 1 : -1)).abs
elsif k == min_steps then
    puts min1.abs
else
    puts (k - min_steps) % 2 == 0 ? min1.abs : min2.abs
end


Measured memory_bytes: 14256
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <deque>
#define pb push_back
#define mod 1000000007
#define all(x) x.begin(),x.end()
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef pair<ll,ll> pll;

int hako[11];
int main(void){
  int a,b,c;
  cin>>a>>b>>c;
  hako[a]++;
  hako[b]++;
  hako[c]++;
  if(hako[5]==2&&hako[7]==1) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  return 0;
}

Measured memory_bytes: 384
N = int(input())
data = [input().split() for i in range(N)]

# unique cities list
a = list(set(list(data[i][0] for i in range(N))))
a.sort()

for i in a:
    # score list
    temp=list(map(int, [data[x][1] for x in range(N) if data[x][0]==i]))
    temp.sort(reverse=True)
    temp=map(str,temp)
    for y in temp:
        print(data.index([i,y])+1)


Measured memory_bytes: 3064
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N, K = map(int, input().split())
A = list(map(int, input().split()))

acc = [0] * (N + 1)
for i in range(1, N + 1):
    acc[i] = acc[i - 1] + A[i - 1] - 1
    acc[i] %= K

mp = defaultdict(int)
ans = 0
for j in range(N + 1):
    if j >= K:
        mp[acc[j - K]] -= 1
    ans += mp[acc[j]]
    mp[acc[j]] += 1
print(ans)

Measured memory_bytes: 42808
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <deque>
#include <cstdio>
#include <cmath>
#include <complex>
#include <iostream>
#include <iterator>

using namespace std;

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

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

typedef vector<double> vd;
typedef vector<vd> vvd;

int main()
{
	double s[2];
	int num[2][4] = {{0}};
	while(scanf("%lf%lf", &s[0], &s[1]) != EOF){
		const double bound[] = {0.2, 0.6, 1.1};
		rep(i, 2)
			num[i][upper_bound(bound, bound+3, s[i])-bound]++;
	}
	rep(i, 4)
		printf("%d %d\n", num[0][3-i], num[1][3-i]);

	return 0;
}

Measured memory_bytes: 0
#include<stdio.h>
int a,b,ans=0;
int main()
{
scanf("%d %d",&a,&b);
for(int i=(int)(a/100);i<=(int)(b/100);i++)
{
int t=i*100+(i/100)+10*((i/10)%10);
if(t>=a&&t<=b) ans++;
}
printf("%d\n",ans);
return 0;
}


Measured memory_bytes: 128
#include <iostream>
using namespace std;
int main(){
int a,b,c,d;
cin >> a >> b >>c >>d;
int AB,CD;
AB = a+b;
CD = c+d;
if(AB==CD){
  cout << "Balanced" << endl;
}
else if(AB>CD){
  cout << "Left" << endl;
}
else if(AB<CD){
  cout << "Right" << endl;
}
  }


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <complex>
#include <bitset>
#include <functional>

using namespace std;
using ll=long long int;

int main() {
    string s;
    cin >> s;
    int n = s.size();

    bool e = true;
    for (int i = 0; i < n; i += 2) {
        if (s[i] == 'L') e = false;
    }

    bool o = true;
    for (int i = 1; i < n; i += 2) {
        if (s[i] == 'R') o = false;
    }

    if (e && o) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
// We only fail when we stop trying
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define endl '\n'
#define D(x) cerr << #x << " = " << (x) << '\n'
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

const int N = 200001;
const int M = 2019;

string s;
int fr[M];

int main()
{
  ios::sync_with_stdio(false);
  cin >> s;
  long long ans = 0;
  int p = 1;
  int r = 0;
  fr[0]++;
  for(int i = sz(s) - 1; i >=0 ; i--) {
    int cur = s[i] - '0';
    r = (r + cur * p) % M;
    ans += fr[r];
    fr[r]++;
    p = (p * 10) % M;
  }
  cout << ans << endl;
  return 0;
}


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

typedef long long ll;
const long double pi = acos(-1);
ll X1,Y1,X2,Y2,n,a[200020],d[200020],len;
map<ll,ll> x,y;

int main(){
    ios::sync_with_stdio(false);
    cin >> X1 >> Y1 >> X2 >> Y2 >> n;
    if(X2 < X1){
        swap(X1,X2);
        swap(Y1,Y2);
    }
    for(int i = 1,u,v;i <= n;++i){
        cin >> u >> v;
        x[u] = v;
        y[v] = u;
    }
    long double qc = 5.0 * pi, ans = 0.0;
    if(X1 == X2){
        int p = min(Y1,Y2), q = max(Y1,Y2);
        ans = 100.0 * (q - p);
        if(x.count(X1) && x[X1] > p && x[X1] < q) ans += 2*qc - 20.0;
        cout << fixed << setprecision(12) << ans << endl;
        return 0;
    }
    if(Y1 == Y2){
        int p = min(X1,X2), q = max(X1,X2);
        ans = 100.0 * (q - p);
        if(y.count(Y1) && y[Y1] > p && y[Y1] < q) ans += 2*qc - 20.0;
        cout << fixed << setprecision(12) << ans << endl;
        return 0;
    }

    ll cnt = 0, mny = min(Y1,Y2), mxy = max(Y1,Y2);
    ans = 100.0 * (X2 - X1 + mxy - mny);
    for(auto p: x){
        if(p.first < X1 || p.first > X2) continue;
        if(p.second >= mny && p.second <= mxy) a[++cnt] = (Y1 < Y2 ? 1 : -1) * p.second;
    }

    for(int i = 1;i <= cnt;++i) d[i] = 1e12;
    for(int i = 1;i <= cnt;++i){
        int pos = lower_bound(d+1,d+1+len,a[i]) - d;
        if(pos == len + 1) len++;
        d[pos] = a[i];
    }

    ans -= 20*len - pi * (5 * len);
    if(len > min(X2 - X1,mxy - mny)) ans += qc;

    cout << fixed << setprecision(12) << ans << endl;

    return 0;
}


Measured memory_bytes: 28416
//2019.4.13 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-15
#define RG register
inline int read(){
    res s=0,ch=getchar();
    bool w=0;
    while(ch<'0'||ch>'9'){if(ch=='-')w=1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return w?-s:s;
}
inline LL Read(){
    RG LL s=0;
    res ch=getchar();
    bool w=0;
    while(ch<'0'||ch>'9'){if(ch=='-')w=1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return w?-s:s;
}
inline void swap(res &x,res &y){
    x^=y^=x^=y;
}
namespace MAIN{
    int n;
    int a[20+10];
    int ans=1;
    inline void MAIN(){
        n=read();
        for(res i=1;i<=n;i++)a[i]=read();
        res now=a[1];
        for(res i=2;i<=n;i++){
            if(now>a[i])continue;
            ans++,now=a[i];
        }
        printf("%d\n",ans);
    }
}
int main(){
    MAIN::MAIN();
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int main(){
	int H, W, i, j;
	scanf("%d%d", &H, &W);
	char **S = (char **)malloc(sizeof(char *) * (H + 2));
	int **A = (int **)malloc(sizeof(int *) * (H + 2));
	for(i = 0; i <= H + 1; i++){
		S[i] = (char *)malloc(sizeof(char) * (W + 2));
		A[i] = (int *)malloc(sizeof(int) * (W + 2));
		for(j = 0; j <= W + 1; j++){
			A[i][j] = 0;
		}
		if(i == 0 || i == H + 1){
			for(j = 0; j <= W + 1; j++){
				S[i][j] = '.';
			}
		}
		else{
			scanf("%s", &S[i][1]);
			S[i][0] = '.';
			S[i][W + 1] = '.';
		}
	}
	for(i = 1; i <= H; i++){
		for(j = 1; j <= W; j++){
			if(S[i][j] == '#'){
				A[i - 1][j - 1]++;
				A[i - 1][j]++;
				A[i - 1][j + 1]++;
				A[i][j - 1]++;
				A[i][j + 1]++;
				A[i + 1][j - 1]++;
				A[i + 1][j]++;
				A[i + 1][j + 1]++;
			}
		}
	}
	for(i = 1; i <= H; i++){
		for(j = 1; j <= W; j++){
			if(S[i][j] == '#'){
				printf("#");
			}
			else{
				printf("%d", A[i][j]);
			}
		}
		printf("\n");
	}
	return 0;
}

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

int main(){
  char a,b;cin >> a >> b;
  if(a>b)cout<<">";
  else if(a<b)cout<<"<";
  else cout<<"=";
}

Measured memory_bytes: 256
import java.util.*;
import java.math.BigInteger;

public class Main {
  
  public static void main(String[] args) {
    
    Scanner scan = new Scanner(System.in);
    long N = scan.nextLong();
    long limit = (long) Math.pow(10,18);
    BigInteger product = new BigInteger("1");
    boolean smaller = true;
    
    for (int i = 1; i <= N; i++) {
      long A_i = scan.nextLong();
      
      if (A_i == 0) {
        System.out.println(0);
        return;
      }
      
      if (smaller) {
          product = product.multiply(BigInteger.valueOf(A_i));
      }
      
      if (smaller && product.compareTo(BigInteger.valueOf(limit)) == 1) {
        smaller = false;
      }  
    }
    
    if (smaller) {
      System.out.println(product);
    }
    
    else {
      System.out.println(-1);
    }
  }
}


Measured memory_bytes: 60656
#include<iostream>
#include<vector>
#include<string>
#define rep(i,n) for(i = 0;i < n;i++);
using std::cout;
using std::cin;
using std::endl;
typedef long long ll;

int main() {
	double l;
	cin >> l;
	printf("%15.10f", l * l * l / 27);
	return 0;
}

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

int main(){
    int n;cin>>n;
    if(n/100000==1) cout<<99999-9000-90<<endl;
    else if(n/10000!=0) cout<<n-9000-90<<endl;
    else if(n/1000!=0) cout<<999-90<<endl;
    else if(n/100!=0) cout<<n-90<<endl;
    else if(n/10!=0) cout<<9<<endl;
    else cout<<n<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(), (x).end())
#define ALL(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define reps(i, m, n) for (ll i = m; i < n; i++)
#define repr(i, m, n) for (ll i = m; i >= n; i--)
#define de(x) cout << #x << "=" << x << endl;
template <class T> bool maxi(T &a, const T &b) {
    if (a < b) { a = b; return 1;} return 0;}
template <class T> bool mini(T &a, const T &b) {
    if (b < a) { a = b; return 1;} return 0;}
#define dame {cout<< "-1" <<"\n"; return;}
#define INF2 1000000000000000037
#define INF  1000000007
#define MOD  1000000007
using namespace std;
using ll = long long;
using ld = long double;
using P  = pair<ll,ll>;
//--GLOBAL---------------------------------
ll modpow(ll a, ll n=MOD-2, ll mod=MOD){ // a^n % MOD の計算
    ll res = 1;
    while (n > 0){
        if(n & 1) res = res * a % mod;
        a = a * a  % mod;
        n >>= 1;
    }
    return res;
}

const ll MAX = 202020;
ll fac[MAX], finv[MAX], inv[MAX];
void cinit() { // O(nlogn)
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    reps(i, 2, MAX){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
ll c(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;
}
//--MAIN-----------------------------------
void Main() {
    ll N,A,B; cin>>N>>A>>B;
    ll ans=modpow(2,N)-1;
    cinit();
    ll aa=1;
    repr(i,N,N-A+1){
        aa*=i;
        aa%=MOD;
    }
    reps(i,1,A+1){
        aa*=inv[i];
        aa%=MOD;
    }
    ll bb=1;
    repr(i,N,N-B+1){
        bb*=i;
        bb%=MOD;
    }
    reps(i,1,B+1){
        bb*=inv[i];
        bb%=MOD;
    }
    ans-=aa+bb;
    ans+=MOD+MOD;
    ans%=MOD;
    
    cout<< ans <<"\n";



}

//--START----------------------------------
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
}
//-----------------------------------------


Measured memory_bytes: 4992
s= input()
n = len(s) - 1
total = 0

import itertools
li = list(itertools.product({0, 1}, repeat=n))
for i in range(len(li)):
    start = 0
    for j in range(n+1):
        if j == n:
            total += int(s[start:n+1])
        elif li[i][j] == 1:
            total += int(s[start:j+1])
            start = j+1

        else:
            pass

print(total)

Measured memory_bytes: 3064
n, m= map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]
cd = [list(map(int, input().split())) for i in range(m)]
for i in ab:
    l = []
    for j in cd:
        l.append(abs(i[0] - j[0]) + abs(i[1] - j[1]))
    print(l.index(min(l)) + 1)

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

using namespace std;
#define ll long long
#define ld long double
#define rep(i,h) for(int i = 0; i < h; ++i)
#define rep1(i,h) for(int i = 0; i <= h; ++i)
#define rep2(i,k,h) for(int i = k; i < h; ++i)
#define rep3(i,k,h) for(int i = k; i <= h; ++i)
#define INF LONG_LONG_MAX // long long INF
#define inf INT_MAX // int inf

typedef pair<int,int> int_pair;
typedef pair<string,string> string_pair;


int main() {
    int h,w;
    cin >> h >> w;
    vector<int> dx{-1,1,0,-1,1,-1,0,1};
    vector<int> dy{1,1,1,0,0,-1,-1,-1};
    vector<string> s(h+5);
    rep(i,h) cin >> s.at(i);

    rep(i,h) {
        rep(j,w) {
            if (s.at(i)[j] == '#') continue;
                int cnt = 0;
                for(int k = 0; k < 8; k++) {
                    int x = j + dx[k];
                    int y = i + dy[k];
                    if(0 <= x && x < w && 0 <= y && y < h && s.at(y)[x] == '#') {
                        cnt++;
                    }
                    s.at(i)[j] = '0' + cnt; // s is string
            }
        }
    }
    for(int i = 0; i < h; i++) {
        cout << s.at(i) << endl;
    }

    return 0;
}



Measured memory_bytes: 256
package main

import (
  "bufio"
  "container/list"
  "fmt"
  "os"
  "strconv"
  "strings"
)

func main() {
  input := Input{bufio.NewReaderSize(os.Stdin,100)}
  n,m := input.NextInts()
  s := input.NextLine()
  xa := make([]int,n)
  xb := make([]int,n)
  set := make(map[Pair]struct{})
  g := make([][]int,n)
  for i:=0;i<m;i++ {
    a,b := input.NextInts()
    a,b = a-1,b-1
    if _,ok := set[Pair{a,b}];ok { continue }
    set[Pair{a,b}] = struct{}{}
    set[Pair{b,a}] = struct{}{}
    g[a] = append(g[a],b)
    g[b] = append(g[b],a)
    if s[b:b+1] == "A" {
      xa[a]++
    } else {
      xb[a]++
    }
    if s[a:a+1] == "A" {
      xa[b]++
    } else {
      xb[b]++
    }
  }
  queue := list.New()
  for i:=0;i<n;i++ {
    if xa[i] == 0 || xb[i] == 0 { queue.PushBack(i) }
  }
  cnt := 0
  for queue.Len() > 0 {
    u,_ := queue.Remove(queue.Front()).(int)
    cnt++
    for _,v := range g[u] {
      ng := xa[v] != 0 && xb[v] != 0
      if s[u:u+1] == "A" {
        xa[v]--
      } else {
        xb[v]--
      }
      if ng && (xa[v] == 0 || xb[v] == 0) { queue.PushBack(v) }
    }
  }
  if cnt == n {
    fmt.Println("No")
  } else {
    fmt.Println("Yes")
  }
}

type Pair struct { x,y int }

type UnionFind struct { par,rank,size []int }
func NewUnionFind(n int) UnionFind {
  par := make([]int,n)
  rank := make([]int,n)
  size := make([]int,n)
  for i:=0;i<n;i++ { par[i],size[i] = i,1 }
  return UnionFind{par,rank,size}
}
func(u UnionFind) Find(i int) int {
  if u.par[i] == i { return i }
  u.par[i] = u.Find(u.par[i])
  return u.par[i]
}
func(u UnionFind) Same(i,j int) bool { return u.Find(i) == u.Find(j) }
func(u UnionFind) Unite(i,j int) {
  i,j = u.Find(i),u.Find(j)
  if i == j { return }
  if u.rank[i] < u.rank[j] {
    u.par[i] = j
    u.size[j] += u.size[i]
  } else {
    u.par[j] = i
    u.size[i] += u.size[j]
    if u.rank[i] == u.rank[j] { u.rank[i]++ }
  }
}
func(u UnionFind) Size(i int) int { return u.size[u.Find(i)] }

type Input struct { reader *bufio.Reader }
func(i *Input) NextLine() string {
  var buffer []byte
  for {
    line,isPrefix,err := i.reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer,line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func(i *Input) NextInts() (int,int) {
  s := strings.Fields(i.NextLine())
  x,_ := strconv.Atoi(s[0])
  y,_ := strconv.Atoi(s[1])
  return x,y
}

Measured memory_bytes: 46720
from collections import defaultdict

N,M = map(int, input().split())

"""考え方
普通にやる
"""

ans_ac = 0
ac_p_set = set()
wa_dict = defaultdict(int)

for m in range(M):
  p,s = input().split()
  
  # 既に正解していたらスキップ
  if p in ac_p_set:
    continue
  
  # acの場合は、過去にacしていなかったら正解数を1増やす
  if s == 'AC':
    ac_p_set.add(p)
    ans_ac += 1
  # 不正解の場合は、「まだ正解していない」かつ「最終的には一回は正解する」場合に計上する
  else:
    wa_dict[p] += 1
    

ans_wa = sum(wa_dict[i] for i in ac_p_set)
print(ans_ac,ans_wa)

Measured memory_bytes: 25176
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    int N;
    cin >> N;
    vector<ll> a(N + 1), b(N);
    for (int i = 0 ; i < N + 1; i++) cin >> a[i];
    for (int i = 0 ; i < N; i++) cin >> b[i];

    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    ll ans = 0;
    ll tmpA, tmpB;
    for (int i = 0; i < N; i++) {
        tmpB = b[i], tmpA = a[i];
        a[i] = max(a[i] - b[i], 0LL);
        b[i] = max(b[i] - tmpA, 0LL);
        ans += tmpB - b[i];
        if (b[i] > 0) {
            tmpB = b[i], tmpA = a[i + 1];
            a[i + 1] = max(a[i + 1] - b[i], 0LL);
            b[i] = max(b[i] - tmpA, 0LL);
            ans += tmpB - b[i];
        }
    }
    cout << ans << '\n';
}


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

template <class Abel> struct BIT {
    const Abel UNITY_SUM = 0;                       // to be set
    vector<Abel> dat;
    
    /* [1, n] */
    BIT(int n) : dat(n + 1, UNITY_SUM) { }
    void init(int n) { dat.assign(n + 1, UNITY_SUM); }
    
    /* a is 1-indexed */
    inline void add(int a, Abel x) {
        for (int i = a; i < (int)dat.size(); i += i & -i)
            dat[i] = dat[i] + x;
    }
    
    /* [1, a], a is 1-indexed */
    inline Abel sum(int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i)
            res = res + dat[i];
        return res;
    }
    
    /* [a, b), a and b are 1-indexed */
    inline Abel sum(int a, int b) {
        return sum(b - 1) - sum(a - 1);
    }
    
    /* debug */
    void print() {
        for (int i = 1; i < (int)dat.size(); ++i) cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

const int INF = 1<<30;
int N, Q;
string S;

void solve() {
    vector<BIT<int>> pls(26, BIT<int>(N+10));
    for (int i = 0; i < N; ++i) pls[S[i]-'a'].add(i+1, 1);
    while (Q--) {
        int type; cin >> type;
        if (type == 1) {
            int ind; char nc; cin >> ind >> nc; --ind;
            auto pc = S[ind];
            S[ind] = nc;
            pls[pc - 'a'].add(ind+1, -1);
            pls[nc - 'a'].add(ind+1, 1);
        }
        else {
            int l, r; cin >> l >> r; --l;
            int res = 0;
            for (int c = 0; c < 26; ++c) if (pls[c].sum(l+1, r+1)) ++res;
            cout << res << endl;
        }
    }
}

int main() {
    cin >> N >> S >> Q;
    solve();
}

Measured memory_bytes: 53636
#include <bits/stdc++.h>
using namespace std;
int main() {

  deque<int> a;
  int q;
  cin >> q;
  while (q--) {
    int op;
    cin >> op;
    if (op == 0) {
      int d, x;
      cin >> d >> x;
      if (d == 0)
        a.push_front(x);
      else
        a.push_back(x);
    } else if (op == 1) {
      int p;
      cin >> p;
      cout << a[p] << endl;
    } else {
      int d;
      cin >> d;
      if (d == 0)
        a.pop_front();
      else
        a.pop_back();
    }
  }

  return 0;
}


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

using namespace std;

typedef long long LL;
const int MAXN=800000+100;
LL dp[MAXN],h[MAXN],a[MAXN],bit[MAXN],d[MAXN],ans;
LL n;

LL lowbit(LL x){
	return x&-x;
}

LL query(LL x){
	LL ret=0;
	for(int j=x;j>0;j-=lowbit(j)){
		ret=max(ret,bit[j]);
	}
	return ret;
}

void change(LL i,LL x){
	for(int j=i;j<=n;j+=lowbit(j)){
		bit[j]=max(bit[j],x);
	}
}

int main(){
	cin>>n;
	for(LL i=1;i<=n;i++){
		cin>>h[i];
	}
	for(LL i=1;i<=n;i++){
		cin>>a[i];
	}
	for(LL i=1;i<=n;i++){
		LL tmp=query(h[i]-1);
		dp[i]=tmp+a[i];
		change(h[i],dp[i]);
		ans=max(ans,dp[i]);
	}
	cout<<ans<<endl;
	return 0;
}
/*
5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000
*/

Measured memory_bytes: 8448
#include<stdio.h>
int main(void){
  char *s="python3 -c\""
"from bisect import*\n"
"A,B=abs,bisect\n"
"a,b,q,*l=map(int,open(0).read().split())\n"
"f=2**60\n"
"s,t=[-f]+l[:a]+[f],[-f]+l[a:a+b]+[f]\n"
"for x in l[a+b:]:\n"
"  m=f\n"
"  i,j=B(s,x),B(t,x)\n"
"  for v in s[i-1:i+1]:\n"
"    for w in t[j-1:j+1]:\n"
"      m=min(m,A(x-v)+A(v-w),A(x-w)+A(w-v))\n"
"  print(m)\n"
"\"";
  system(s);
  return 0;
}            

Measured memory_bytes: 39008