akhauriyash/Code-Regression huggingface dataset:
#![allow(unused_imports)]
#![allow(unused_macros)]
use itertools::Itertools;
use std::cmp::{max, min};
use std::collections::*;
use std::i64;
use std::io::{stdin, Read};
use std::usize;

trait ChMinMax {
    fn chmin(&mut self, other: Self);
    fn chmax(&mut self, other: Self);
}
impl<T> ChMinMax for T
where
    T: PartialOrd,
{
    fn chmin(&mut self, other: Self) {
        if *self > other {
            *self = other
        }
    }
    fn chmax(&mut self, other: Self) {
        if *self < other {
            *self = other
        }
    }
}

#[allow(unused_macros)]
macro_rules! parse {
    ($it: ident ) => {};
    ($it: ident, ) => {};
    ($it: ident, $var:ident : $t:tt $($r:tt)*) => {
        let $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
    ($it: ident, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
    ($it: ident, $var:ident $($r:tt)*) => {
        let $var = parse_val!($it, usize);
        parse!($it $($r)*);
    };
}

#[allow(unused_macros)]
macro_rules! parse_val {
    ($it: ident, [$t:tt; $len:expr]) => {
        (0..$len).map(|_| parse_val!($it, $t)).collect::<Vec<_>>();
    };
    ($it: ident, ($($t: tt),*)) => {
        ($(parse_val!($it, $t)),*)
    };
    ($it: ident, u1) => {
        $it.next().unwrap().parse::<usize>().unwrap() -1
    };
    ($it: ident, $t: ty) => {
        $it.next().unwrap().parse::<$t>().unwrap()
    };
}

use std::num::Wrapping;

fn solve(s: &str) {
    let mut it = s.split_whitespace();
    let p = Wrapping(1_000_000_007usize);
    parse!(it, n: usize);
    let s: Vec<_> = it
        .next()
        .unwrap()
        .chars()
        .map(|x| Wrapping(x as usize))
        .collect();
    let mut hv = BTreeMap::new();
    let mut ok = 0;
    let mut ng = n;
    'outer: while ng - ok > 1 {
        hv.clear();
        let m = (ok + ng) / 2;
        let mut h = Wrapping(0usize);
        for i in 0..m {
            h = h * p + s[i];
        }
        let mut t = Wrapping(1);
        for _ in 0..m {
            t *= p;
        }

        hv.insert(h, 0);
        for i in 0..(n - m) {
            h = h * p + s[i + m] - s[i] * t;
            if let Some(j) = hv.get(&h) {
                if i - j + 1 >= m {
                    ok = m;
                    continue 'outer;
                }
            } else {
                hv.insert(h, i + 1);
            }
        }
        ng = m;
    }
    println!("{}", ok);
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}


Measured memory_bytes: 2296
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())
print(N * (N - 1) // 2 + M * (M - 1) // 2)



Measured memory_bytes: 38384
#include<iostream>

using namespace std;

int main()
{
  
  int k,x;
  cin >> k >> x;
  int ans = 500*k;
  if(ans >= x)
  {
    cout << "Yes" << "\n";
  
  }
  else
      cout << "No" << "\n";
  
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main {

	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);

		int str1 = scan.nextInt();
		String str = scan.next();
		int str2 = scan.nextInt();
		
		while(!str.equals("?")){
			int x = 0;
			if((str.equals("+"))){
				x = str1 + str2;
				System.out.println(x);
			}else if((str.equals("-"))){
				x = str1 - str2;
				System.out.println(x);
			}else if((str.equals("*"))){
				x = str1 * str2;
				System.out.println(x);
			}else if((str.equals("/"))){
				x = str1 / str2;
				System.out.println(x);
			}
			str1 = scan.nextInt();
			str = scan.next();
			str2 = scan.nextInt();

		}
		
	}
}

Measured memory_bytes: 26272
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <math.h>
#include <set>

using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

static const double PI = 3.1415926535897932384626433;

///////////////////////////
////Prime Creator//////////
///////////////////////////
//bool Prime[100001] = {};
//void createPrime() {
//	ll n = 100001;
//	rep(i, 0, n) Prime[i] = true;
//	Prime[0] = false;
//	Prime[1] = false;
//	rep(i, 2, n) {
//		if (Prime[i]) {
//			rep(j, 2, n) {
//				if (j*i >= n)break;
//				Prime[j*i] = false;
//			}
//		}
//	}
//}
///////////////////////////
///////////////////////////

/////////////////////////
//Warshal Floyid/////////
/////////////////////////
//initialize`
//rep(i, 0, N)rep(j, 0, N) wf[i][j] = 1 << 29;
//static const ll WF_MAX = 300;
//ll wf[WF_MAX][WF_MAX];
//void WarshalFloyid(int size) {
//	rep(k, 0, size)rep(i, 0, size)rep(j, 0, size)wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j]);
//}

static const ll LL_MAX = (ll)1 << 55;
static const ll WF_MAX = 300;
ll wf[WF_MAX][WF_MAX];
void WarshalFloyid(int size) {
	repe(k, 1, size)repe(i, 1, size)repe(j, 1, size)wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j]);
}

ll N, M, R;
ll r[9];
bool b[201] = {};

bool check() {
	bool ok = true;
	repe(i, 1, R) {
		ok &= b[r[i]];
	}
	return ok;
}

ll minC = LL_MAX;
void dfs(int n, ll sum) {
	if (check()) {
		minC = min(minC, sum);
		return;
	}
	repe(i, 1, R) {
		ll T = r[i];
		if (T != n) {
			if (!b[T]) {
				b[T] = true;
				dfs(T, sum + wf[n][T]);
				b[T] = false;
			}
		}
	}
}

int main() {
	cin >> N >> M >> R;
	repe(i, 1, R) cin >> r[i];

	repe(i, 1, N)repe(j, 1, N) wf[i][j] = LL_MAX;

	rep(i, 0, M) {
		ll a, b, c; cin >> a >> b >> c;
		wf[a][b] = c;
		wf[b][a] = c;
	}

	WarshalFloyid(N);

	repe(i, 1, R) {
		ll T = r[i];
		b[T] = true;
		dfs(T, 0);
		b[T] = false;
	}
	cout << minC << endl;
	return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const ll INF = 1LL << 60;



int main(){
    int n, m;
    cin >> n >> m;
    for(int i=0; i<m; i++){
        int a;
        cin >> a;
        n -= a;
        if(n < 0){
            cout << -1 << endl;
            return 0;
        }
    }
    cout << n << endl;
   

}

Measured memory_bytes: 3500
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao Twitter/QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 10e16
#define MOD 1000000007
#define mod 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}

//---------------------------------------------------------------------------
long long modpow(long long a, long long n) {//a^n(MOD)を求める
    long long res = 1;
    while (n > 0) {
         if (n & 1) res = res * a % MOD;
         a= a * a % MOD;//次の準備
         n >>= 1;
      }
 return res;
}
//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????        memset()!!!!!!!!!!!!       ペナを減らせ!!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    int a,b,c;cin>>a>>b>>c;
    if(a+c==b||a+b==c||b+c==a)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------









Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

ll gcd(ll a,ll b){
  if(b == 0) return a;
  return gcd(b , a % b);
}

ll mod(ll a){
  return (a % 1000000007);
}

ll lcm(ll a,ll b){
  return (a*b)/gcd(a,b);
}

ll nCr(ll n,ll r){
  if(r == 1) return n;
  else if(r == 0) return 1;
  else return nCr(n-1,r-1)*n/r;
}

int main(){
  ll n,m; cin >> n >> m; vl checkx(m); vl checky(m);
  vl stux(n); vl stuy(n); vl stucheck(n);
  
  rep(i,n){
    cin >> stux[i] >> stuy[i];
  }
  
  rep(i,m){
    cin >> checkx[i] >> checky[i];
  }
  
  rep(i,n){
    ll mindis = 1e17;
    rep(j,m){
      if(mindis > abs(stux[i]-checkx[j])+abs(stuy[i] -checky[j])){
        mindis = abs(stux[i]-checkx[j])+abs(stuy[i]-checky[j]);
        stucheck[i] = j+1;
      }
    }
  }
  
  for(ll x : stucheck){
    cout << x << endl;
  }
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,l,n) for(size_t i=l; i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using mii = map<int,int>;
using pii = pair<int,int>;
using vpii = vector<pair<int,int>>;
using ti3 = tuple<int,int,int>;

int main(){
  ll n; cin>>n;
  vi v(n); REP(i,n) cin>>v[i];
  sort(v.begin(),v.end());
  ld sum=v[0];
  REP(i,n-1){
    sum=(v[i+1]+sum)/2;
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+100;
int n;
int a[maxn][3];
int dp[maxn][3];
int main(){
    scanf("%d",&n);
    for (int i=0;i<n;i++){
        scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
    }
    tie(dp[0][0],dp[0][1],dp[0][2]) = make_tuple(a[0][0],a[0][1],a[0][2]);
    for (int i=1;i<n;i++){
        for (int j=0;j<3;j++){
            for (int jj =0;jj <3;jj ++){
                if (j != jj){
                    dp[i][j] = max(dp[i][j],dp[i-1][jj] + a[i][j]);
                }
            }
        }
    }
    cout<<max(max(dp[n-1][0],dp[n-1][1]),dp[n-1][2])<<endl;
    return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
#define sc scanf
#define itn int
#define STR clock_t startTime = clock();
#define END clock_t endTime = clock();cout << double(endTime - startTime) / CLOCKS_PER_SEC *1000<< "ms" << endl;
using namespace std;
const int N=1e6+5;
const long long mod=1e9+7;
const long long mod2=998244353;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=x*(a/b);}
int main(){
    ll A,B;
    cin>>A>>B;
    ll g=__gcd(A,B);
    int ans=1;
    for(ll i=2;i*i<=g;i++){
        if(g%i==0){
            ans++;
            while(g%i==0)g/=i;
        }
    }
    if(g>1)ans++;
    o(ans);
}

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

int main(){
    int n;
    cin >> n;
    double x;
    string s;
    double sum = 0.0;
    for(int i = 0; i < n; i++){
        cin >> x >> s;
        if(s == "JPY"){
            sum += x;
        }else{
            sum += x / 1.0 * 380000.0;
        }
    }
    cout << fixed << setprecision(10);
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<numeric>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>

#define rep(i,n) for(int i=0;i<n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define rp(i,c) rep(i,(c).size())
#define fr(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl

using namespace std;

typedef unsigned long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf=1<<28;
const double INF=1e12,EPS=1e-9;

int w,h,p;
ll hash[1001][1001],tmp[101][101],base[1001][1001];
bool img[1000][1000],ptn[100][100],ptn2[100][100];
char in[1001];

void mirror(){
	rep(i,p)rep(j,p/2)swap(ptn[i][j],ptn[i][p-1-j]);
}
void rot(){
	rep(i,p)rep(j,p)ptn2[i][j]=ptn[i][j];
	rep(i,p)rep(j,p)ptn[i][j]=ptn2[p-1-j][i];
}
inline int calcbit(char c){
	int bit;
	if('A'<=c&&c<='Z')bit=c-'A';
	else if('a'<=c&&c<='z')bit=c-'a'+26;
	else if('0'<=c&&c<='9')bit=c-'0'+52;
	else if(c=='+')bit=62;
	else if(c=='/')bit=63;
	else assert(0);
	return bit;
}

int main()
{
	base[0][0]=1;
	const ll tate=1000000007, yoko=7;
	rep(i,1000)rep(j,1000)if(i||j)
	base[i][j]=i?base[i-1][j]*tate:base[i][j-1]*yoko;
	
	while(scanf("%d%d%d ",&w,&h,&p),w){
		memset(img,0,sizeof(img));
		rep(i,h){
			fgets(in,1000,stdin);
			rep(j,(w-1)/6+1){
				int bit=calcbit(in[j]);
				rep(k,6)img[i][j*6+k]=bit&1<<5-k; //debug!!!
			}
		}
		rep(i,p){
			fgets(in,1000,stdin);
			rep(j,(p-1)/6+1){
				int bit=calcbit(in[j]);
				rep(k,6)ptn[i][j*6+k]=bit&1<<5-k;
			}
		}
		rep(i,h)rep(j,w){
			hash[i+1][j+1]=(img[i][j]+1)*base[i][j]+hash[i][j+1]+hash[i+1][j]-hash[i][j];
		}
		set<ll> patterns;
		rep(it,8){
			memset(tmp,0,sizeof(tmp));
			rep(i,p)rep(j,p){
				tmp[i+1][j+1]=(ptn[i][j]+1)*base[i][j]+tmp[i][j+1]+tmp[i+1][j]-tmp[i][j];
			}
			patterns.insert(tmp[p][p]);
			rot();
			if(it==3)mirror();
		}
		vector<ll> pattern(all(patterns));
		
		int ans=0;
		rep(i,h-p+1)rep(j,w-p+1){
			ll tmp=hash[i+p][j+p]-hash[i][j+p]-hash[i+p][j]+hash[i][j];
			rep(k,pattern.size()){
				ll tmp2=pattern[k]*base[i][j];
				if(tmp==tmp2)ans++;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 17000
#include <bits/stdc++.h>
#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define PRINT(x) cout << (x) << "\n"
using namespace std;
using ll = long long; using pint = pair<int, int>; using pll = pair<ll, ll>;
template<typename T> auto compare = [](T x, T y) -> bool{return (x < y);};
const int MOD = 1000000007;

int N, A[200010];
map<int, int> mp;

signed main(){
    cin >> N;
    REP(i, N) cin >> A[i];
    sort(A, A + N);
    A[N] = INT32_MAX;
    ll ans = 0;
    REP(i, N){
        bool ok = true;
        for(int j = 1; j * j <= A[i]; j++){
            if(!ok) break;
            if(A[i] % j == 0){
                if(mp[j] > 0) ok = false;
                if(mp[A[i] / j] > 0) ok = false;
            }
        }
        if(ok && A[i] < A[i + 1]){
            ans++;
            // cerr << A[i] << endl;
        }
        mp[A[i]]++;
    }
    PRINT(ans);
    return 0;
}

Measured memory_bytes: 33216
IDENTIFICATION                   DIVISION.
PROGRAM-ID.                      ABC_077_B.
ENVIRONMENT                      DIVISION.
DATA                             DIVISION.
WORKING-STORAGE                  SECTION.
    01 N      PIC 9(10).
    01 ans    PIC X(10).
    01 ZS     PIC Z(11).
    01 DUMMY  PIC X(1).

PROCEDURE                        DIVISION.
MAIN.
    ACCEPT N.

    COMPUTE N = FUNCTION SQRT(N).

    COMPUTE N = N ** 2.

    MOVE N TO ZS.

    PERFORM UNANS.

    DISPLAY ans(1:FUNCTION STORED-CHAR-LENGTH(ans)).
    STOP RUN.

UNANS                            SECTION.
    UNSTRING
        ZS DELIMITED BY ALL SPACE
        INTO DUMMY ans
    END-UNSTRING.


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

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

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

struct edge { int to, cost; };

const ll INF = 1e15;
const ll MAX_V = 100000;

int V, E;
int s;

vector<edge> G[MAX_V];
ll d[MAX_V];

//??????????????\?????????????????????????????????
void dijkstra(int s){
  priority_queue< P, vector<P>, greater<P> > que;
  rep(i, V) d[i] = INF;
  d[s] = 0;
  que.push(P(0, s));

  while(!que.empty()){
    P p = que.top(); que.pop();
    int stand_v = p.second;
    if(p.first > d[stand_v]) continue; //?????§??????????????????????????§?????£???
    rep(i, G[stand_v].size()){
      edge e = G[stand_v][i];
      if(d[stand_v] + e.cost < d[e.to]){
	d[e.to] = d[stand_v] + e.cost;
	que.push(P(d[e.to], e.to));
      }
    }
  }
}

int main(){
  cin >> V >> E >> s;
  rep(i, E){
    int tmp_s, tmp_t, tmp_d;
    cin >> tmp_s >> tmp_t >> tmp_d;
    G[tmp_s].push_back((edge){tmp_t, tmp_d});
  }

  dijkstra(s);

  rep(i, V){
    if(d[i] < INF) cout << d[i] << endl;
    else cout << "INF" << endl;
  }

  return 0;
}

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

int main() {
    double n, score[1100], sum;
    double avr, var, dev;
    cout << fixed << setprecision(12);
    while (true) {
        cin >> n;
        if (!n) {
            break;
        }
        sum = 0, var = 0;
        for (int i = 0; i < n; ++i) {
            cin >> score[i];
            sum += score[i];
        }
        avr = sum / n;
        for (int i = 0; i < n; ++i) {
            var += pow(score[i] - avr, 2);
        }
        dev = sqrt(var / n);
        cout << dev << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[101][101][500];

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

int main() {
    ll N, W;
    cin >> N >> W;
    vector<ll> w(N), v(N);
    for (int i = 0; i < N; i++) {
        cin >> w[i] >> v[i];
    }
    ll base = w[0];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k <= 300; k++) {
                ll gap = w[i] - base;
                chmax(dp[i + 1][j + 1][k + gap], dp[i][j][k] + v[i]);
                chmax(dp[i + 1][j][k], dp[i][j][k]);
            }
        }
    }
    ll ans = 0;
    for (int j = 0; j * base <= W; j++) {
        for (int k = 0; k <= 300; k++) {
            if (W < j * base + k) break;
            chmax(ans, dp[N][j][k]);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 39680
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }

    static class Task {
    	int N, L;
    	
        void solve(InputReader in, PrintWriter out) {
        	N = in.nextInt();
        	L = in.nextInt();
        	
        	int total = 0;
        	int minDiff = Integer.MAX_VALUE;
        	for (int i = 0; i < N; ++i) {
        		int taste = L + i;
        		total += taste;
        		if (Math.abs(minDiff) > Math.abs(taste)) {
        			minDiff = taste;
        		}
        	}
        	
        	out.println(total - minDiff);
        }
    }
    
    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

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

        int nextInt() { return Integer.parseInt(next()); }
        
        int[] nextIntArray(int n) {
        	int[] arr = new int[n];
        	for (int i = 0; i < n; ++i) {
        		arr[i] = nextInt();
        	}
        	return arr;
        }

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

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


Measured memory_bytes: 21460
// A to Z String
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    string s;
    int Aidx, Zidx;
    cin >> s;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == 'A') {
            Aidx = i;
            break;
        }
    }
    reverse(s.begin(), s.end());
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == 'Z') {
            Zidx = s.size() - i;
            break;
        }
    }
    cout << (Zidx - Aidx) << endl;
}

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

int main() {
  int n,m;
  cin >> n >> m;
  int maxL = 1, minR = n;
  rep(i,m) {
    int l,r;
    cin >> l >> r;
    maxL = max(maxL, l);
    minR = min(minR, r);
  }
  int ans = minR + 1 - maxL;
  ans = max(ans,0);
  cout << ans << endl;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const int maxV = 90010;
const int maxN = 1e5+10;
const int inf = 0x3f3f3f3f;
const ll MOD = 1e9+7;
const ll INF = 1000000000000000010LL;
#define X first
#define Y second



int n,m,k;
vector<int> v[maxN];
int sz[maxN];
int f[maxN];
int tot;
int vis[maxN];
int ans[maxN];
void dfs(int x,int cnt)
{
	f[x] = cnt;
	sz[cnt]++;
	vis[x] = 1;
	for(auto y:v[x])
	{
		if(vis[y])continue;
		dfs(y,cnt);
	}
}
int main() {	
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	tot = 1;
	for(int i=1;i<=n;i++)
	{
		if(vis[i] == 0)
		{
			dfs(i,tot);
			tot++;
		}
	}
	unordered_map<int,unordered_map<int,int> > mp;
	for(int i=1;i<=k;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(f[x] == f[y])
		{
			ans[x]--;
			ans[y]--;	
		}	
	}
	
	for(int i=1;i<=n;i++)
	{
		int sum = sz[f[i]];
		sum = sum - 1 - v[i].size();
		ans[i] += sum;
	}
	for(int i=1;i<n;i++)
	{
		printf("%d ",ans[i]);
	}
	printf("%d\n",ans[n]);
	return 0;
}

Measured memory_bytes: 7936
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<n;++i)

using namespace std;

typedef complex<double> C;

namespace std {
  bool operator < (const C& a, const C& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}
//??????
double cross(const C& a, const C& b) {
  return imag(conj(a)*b);
}
//??????
double dot(const C& a, const C& b) {
  return real(conj(a)*b);
}

int ccw(C a, C b, C c) {
  b -= a; c -= a;
  if (cross(b, c) > 0)   return +1;       // counter clockwise
  if (cross(b, c) < 0)   return -1;       // clockwise
  if (dot(b, c) < 0)     return +2;       // c--a--b on line
  if (norm(b) < norm(c)) return -2;       // a--b--c on line
  return 0;
}

vector<C> convex_hull(vector<C> ps) {
  int n = ps.size(), k = 0;
  sort(ps.begin(), ps.end());
  vector<C> ch(2*n);
  for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull
    while (k >= 2 && (ccw(ch[k-2], ch[k-1], ps[i]) == 0 || ccw(ch[k-2], ch[k-1], ps[i]) == -1)) --k;
  for (int i = n-2, t = k+1; i >= 0; ch[k++] = ps[i--]) // upper-hull
    while (k >= t && (ccw(ch[k-2], ch[k-1], ps[i]) == 0 || ccw(ch[k-2], ch[k-1], ps[i]) == -1)) --k;
  ch.resize(k-1);
  return ch;
}

int main()
{
    int n;
    cin >> n;
    vector<C> vec,res,bf;
    map<C,int> mp;
    rep(i,n){
        int x,y;
        cin >> x >> y;
        vec.push_back(C(x,y));
    }
    res = convex_hull(vec);
    rep(i,res.size()){
        mp[res[i]] = i;
    }
    bf = res;
    sort(bf.begin(),bf.end(),[](C c1,C c2){return imag(c1) == imag(c2)?real(c1) < real(c2):imag(c1) < imag(c2);});
    int st = mp[bf[0]];
    cout << res.size() << "\n";
    rep(i,res.size()){
        cout << real(res[(st+i)%res.size()]) << " " << imag(res[(st+i)%res.size()]) << "\n";
    }
    return 0;
}

Measured memory_bytes: 12848
#include<bits/stdc++.h>
using namespace std;
int n,a[100005],x,y,deg[100005];
int fir[100005],nxt[200005],to[200005],cnt=0;
int f[100005],root;

int read(){
	int x=0;char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}

void shit(){
	puts("YES");exit(0);
}

void fuck(){
	puts("NO");exit(0);
}

void dfs(int x,int F){
	int sum=0,maxn=0,res,use,son=0;
	for(int i=fir[x];i;i=nxt[i]){
		if(to[i]==F) continue;
		dfs(to[i],x);
		maxn=max(f[to[i]],maxn);
		sum+=f[to[i]];
		son++;
	}
	if(!son){
		f[x]=a[x];
		return;
	}
	res=sum-maxn;
	if(x!=root){
		if(a[x]>sum) fuck();	
		if(res<maxn) use=res;
		else use=sum/2;
		if(use<sum-a[x]) fuck();
		f[x]=2*a[x]-sum;
		if(f[x]<0) fuck();
	}
	else{
		if(sum%2==1) fuck();
		if(res<maxn) fuck();
		if(sum/2!=a[x]) fuck();
	}
}

int main(){
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<n;i++){
		x=read(),y=read();
		deg[x]++,deg[y]++;
		to[++cnt]=y,nxt[cnt]=fir[x],fir[x]=cnt;
		to[++cnt]=x,nxt[cnt]=fir[y],fir[y]=cnt;
	}
	if(n==2){
		if(a[1]==a[2]) shit();
		else fuck();
	}
	for(int i=1;i<=n;i++) if(deg[i]>1) root=i;
	dfs(root,0);
	shit();
	
	return 0;
}

Measured memory_bytes: 10496
package main

import (
	"fmt"
	"math"
)

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

	var c int
	for 0 < H {
		H /= 2
		c++
	}
	// 塁乗
	r := int(math.Pow(2, float64(c)))
	fmt.Println(r - 1)
}


Measured memory_bytes: 512
X, Y, A, B, C = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

p = sorted(p)[-X:]
q = sorted(q)[-Y:]
r = sorted(r)
a = p+q+r
a.sort(reverse=1)
ans = a[:X+Y]
print(sum(ans))


Measured memory_bytes: 23328
n = int(input())
box = []
box.append(list(map(int, input().split())))
box1 = box[0]  
tibi = min(box1)
ans = 0

#判定
if tibi!=1:
  print(-1)
else:
  num = 0
  for i in range(len(box1)):
    if box1[i]==(num+1):
      num += 1
      continue
    else:
      ans += 1
  print(ans)

Measured memory_bytes: 24744
#include<bits/stdc++.h>
using namespace std;
int main(){
  int sx,sy,tx,ty,x,y;
  cin>>sx>>sy>>tx>>ty;
  x=tx-sx;
  y=ty-sy;
  for(int i=0;i<x;i++) cout<<'R';
  for(int i=0;i<y;i++) cout<<'U';
  for(int i=0;i<x;i++) cout<<'L';
  for(int i=0;i<=y;i++) cout<<'D';
  for(int i=0;i<=x;i++) cout<<'R';
  for(int i=0;i<=y;i++) cout<<'U';
  cout<<"LU";
  for(int i=0;i<=x;i++) cout<<'L';
  for(int i=0;i<=y;i++) cout<<'D';
  cout<<'R';
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()

ll mpow(ll a, ll b){
	if(b==0) return 1;
	else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
	else return mpow(a,b-1) * a % MOD;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
	if(kaijo_memo.size() > n) return kaijo_memo[n];
	if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
	while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
	return kaijo_memo[n];
}
ll nCr(ll n, ll r){
	if(n < r || r < 0) return 0;
	ll ret = 1;
	ret *= kaijo(n); ret %= MOD;
	ret *= mpow(kaijo(r), MOD-2); ret %= MOD;
	ret *= mpow(kaijo(n-r), MOD-2); ret %= MOD;
	return ret;
}

int main(void){
	int n;
	cin>>n;
	string s;
	vector<ll> hash;
	rep(i,n){
		cin>>s;
		vector<char> s_;
		rep(j,s.size()){
			s_.push_back(s[j]);
		}
		sort(all(s_));
		ll code = 0;
		rep(j,s.size()){
			code += pow(26,j) * (s_[j] - 'a');
		}
		hash.push_back(code);
	}
	hash.push_back(LINF);
	sort(all(hash));
	ll ans = 0;
	ll count = 0;
	rep(i,n){
		if(hash[i] == hash[i+1]){
			count++;
		}else{
			ans += (count+1) * count / 2;
			count = 0;
		}
	}
	cout<<ans<<endl;

	return 0;
}


Measured memory_bytes: 1400
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int R = sc.nextInt();

		if (N >= 10) {
			System.out.println(R);
		} else {
			System.out.println(R + 100 * (10 - N));
		}

	}
}


Measured memory_bytes: 23124
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
#include<vector> 

typedef long long ll;
using namespace std;

#define N 1123456 
int getint(){
	int f=1,x=0; char ch=getchar();
	while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return f*x;
}
#define mod 1000000007ll
int n; 
int a[N];
ll fac[N];
int main(){
	n=getint();
	fac[0]=1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
	int tot=0,mn=1; 
	ll ans=1; int m=n; 
	for(int i=1;i<=n;i++){
		int x=getint();
//		cout<<x<<"===="<<mn<<endl;
		if(x>=mn){
			++tot; mn+=2; 
		} else {
			++tot; ans=ans*tot%mod; 
//			cout<<tot<<endl; 
			tot--;
			m--; 
		}
	}
	ans=ans*fac[m]%mod;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1024
#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>
using namespace std;

#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)
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
	string s;
	ll k; 
	cin>>s>>k;
	rep(i,s.size()){
		if(s[i]!='1'){
			cout<<s[i]<<endl;
			return 0;
		}
		if(i == k-1){
			cout<<s[i]<<endl;
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 256
n = int(raw_input())
a = map(int, raw_input().split())

def left_list(a):
  i = 1
  left_sum = a[0] + a[1]
  left_1 = a[0]
  left = []
  left.append([a[0], a[1]])
  for j in range(2, n-2):
    left_sum += a[j]
    while 2 * (left_1 + a[i]) <= left_sum:
      left_1 += a[i]
      i += 1
    diff = left_sum - 2 * left_1
    diff_1 = 2 * (left_1 + a[i]) - left_sum
    if diff_1 < diff:
      left_1 += a[i]
      i += 1
    left.append([left_1, left_sum-left_1])
  # print(left)
  return left

left_t = left_list(a)
a = a[::-1]
right_t = left_list(a)
right_t = right_t[::-1]
res = sum(a)
for x, y in zip(left_t, right_t):
  diff = max(max(x), max(y)) - min(min(x), min(y))
  if diff < res:
    res = diff
print(res)


Measured memory_bytes: 85860
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>; 
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1001001001LL;
constexpr long long LINF = 1001001001001001001;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
    int n, k; cin >> n >> k;
    int mx = -1, GCD;
    rep(i, n){
        int a; cin >> a;
        if(i==0)GCD = a;
        else{
            GCD = __gcd(GCD, a);
        }
        chmax(mx, a);
    }
    if(k > mx || k % GCD)cout << "IMPOSSIBLE" << ln;
    else cout << "POSSIBLE" << ln;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) (v).begin(),(v).end()
#define out(a) cout << (a) << endl
using namespace std;
using ll = long long;
int main(){
    int a, b, c;
    cin >> a >> b >> c;
    for (int i=1; i<=b; i++){
        int d = a * i % b;
        if (d == c){
            out("YES");
            return 0;
        }
    }
    out("NO");
    return 0;
}

Measured memory_bytes: 256
while true
	num=gets.to_i
	break if num == 0
	a=[[0,0]]
	count = 0
	(num-1).times{|t|
		n,d = gets.split(" ").map{|e|e.to_i}
		point = a[n]
		a.push [point[0]-1,point[1]] if d == 0
		a.push [point[0],point[1]-1] if d == 1
		a.push [point[0]+1,point[1]] if d == 2
		a.push [point[0],point[1]+1] if d == 3
	}
	maxh=maxw=minh=minw=0
	a.each{|e|
		maxw = e[0] if e[0] > maxw
		minw = e[0] if e[0] < minw
		maxh = e[1] if e[1] > maxh
		minh = e[1] if e[1] < minh
	}
	puts "#{maxw-minw+1} #{maxh-minh+1}"
end

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

int main(){
  int n,a[110000],now=1;
  cin>>n;
  for(int i=1;i<=n;i++) cin>>a[i];
  for(int i=1;i<=n;i++){
    if(a[now]==2){cout<<i; return 0;}
    now=a[now];
  }
  cout<<"-1";



}


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

using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); ++i)
double const PI = 3.1415926535897932384626433;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if (a * c <= b)
        cout << c << endl;
    else if (a * c > b)
        cout << b / a << endl;
    return 0;
}

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

#define Mset(s, n)      memset(s, n, sizeof(s))
#define Rp0(i, m)       for(int i = 0; i < m; ++i)
#define Rpd(i, m, l)    for(int i = l; i >= m; --i)
#define Rp1(i ,m)       for(int i = 1; i <= m; i++)
#define All(a)          (a).begin(), (a).end()
#define Lwb             lower_bound
#define Upb             upper_bound
#define Sz(a)           int((a).size())
#define u_map           unordered_map
#define Exist(a, b)     (find(All(a), (b)) != (a).end())
#define Sort(x)         sort(All(x))
#define Gsort(x)        sort(All(x), greater<typeof(*((x).begin()))>())
#define Unique(v)       Sort(v); (v).resize(unique(ALL(v)) - (v).begin())
#define Max(a, b, c)    max(a, max(b, c))

#define fi              first
#define se              second
#define pb              push_back
#define pf              push_front
#define is              insert
#define ooi             INT_MAX
#define ool             LLONG_MAX
#define ll              long long
#define ull             unsigned ll
#define ld              long double
#define pii             pair<int, int>
#define vi              vector<int>
#define vpii            vector<pii>

const ll MOD = (ll) 1e9 + 7;
const ld PI = acos((ld) -1);
inline int Get_bit(int x, int k){return (x >> (k - 1)) & 1;}
inline ll Gcd(ll a, ll b) {ll r; while(b){ r = a % b; a = b; b = r;} return a;}
inline ll Lcm(ll a, ll b) {return a / Gcd(a, b) * b;}
inline ll Pow(ll n, ll k) {ll r = 1; for(; k; k >>= 1, n = n * n % MOD){if(k & 1) r = r * n % MOD;} return r;}
const int base = 311;


const int N = 5e3 + 5;
ll n, m, k, ans, q, s, t;
ll a[N];

void Solve(){
    cin >> n >> m;
    cout << max(0LL, n - 2 * m);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(6);
    Solve();
}



Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	long long ans=0x3f3f3f3f;
	int n;
	long long x[103];
	cin>>n;
	long long i;
	for(i=1;i<=n;i++) cin>>x[i];
	sort(x+1,x+1+n);
	int j;
	for(i=x[1];i<=x[n];i++)
	{
		long long res=0;
		for(j=1;j<=n;j++)
		{
			res=res+(x[j]-i)*(x[j]-i);
		}
		ans=min(ans,res);
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
using namespace std;
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define INF 1145141919364364
#define int long long
#define all(vec) vec.begin(),vec.end()
#define P pair<int,int>
#define S second
#define F first
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
bool prime(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x%i == 0)return false;
	}
	return true;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}


int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}

int n, m, a[2000], b[2000];
int dp[2010][2010];

signed main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)cin >> a[i];
	for (int j = 0; j < m; j++)cin >> b[j];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i - 1] == b[j - 1]) {
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + 1;
			}
			else {
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
			}
			dp[i][j] += mod;
			dp[i][j] %= mod;
		}
	}
	cout << (dp[n][m] + 1) % mod << endl;
}

Measured memory_bytes: 31744
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <sstream>
#include <tuple>
#include <vector>

using namespace std;
using namespace chrono;

#ifdef DEBUG
	#define LOCAL_INPUT_FILE
#else
	//~ #define USE_FILE_IO
#endif

#ifdef USE_FILE_IO
	#define INPUT_FILE "input.txt"
	#define OUTPUT_FILE "output.txt"
	#define cin ____cin
	#define cout ____cout
	ifstream cin(INPUT_FILE);
	ofstream cout(OUTPUT_FILE);
#else
	#ifdef LOCAL_INPUT_FILE
		#define cin ____cin
		ifstream cin("input.txt");
	#endif
#endif

const int infinity = (int)1e9 + 42;
const int64_t llInfinity = (int64_t)1e18 + 256;
const int module = (int)1e9 + 7; 
const long double eps = 1e-8;

mt19937_64 randGen(system_clock().now().time_since_epoch().count());

inline void raiseError(string errorCode) {
	cerr << "Error : " << errorCode << endl;
	exit(42);
}

signed main() {
	#ifndef USE_FILE_IO
		ios_base::sync_with_stdio(false);
	#endif
	int n, m; cin >> n >> m;
	vector<string> v(n);
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
	}
	vector< vector<int> > d(n, vector<int>(m, infinity));
	d[0][0] = (v[0][0] == '#');
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (i != n-1) d[i+1][j] = min(d[i+1][j], d[i][j] + (v[i][j] == '.' && v[i+1][j] == '#'));
			if (j != m-1) d[i][j+1] = min(d[i][j+1], d[i][j] + (v[i][j] ==  '.' && v[i][j+1] == '#'));
		}
	}
	
	//~ for (int i = 0; i < n; ++i) {
		//~ for (int j = 0; j < m; ++j) {
			//~ cout << d[i][j] << " ";
		//~ }
		//~ cout << endl;
	//~ }
	
	cout << d.back().back() << endl;
	return 0;
}


Measured memory_bytes: 384
#include<iostream>
using namespace std;
#define ll long long
const ll mod=1000000007;
ll h,w,dp[1007][1007];

char s[1007][1007];

ll dfs(ll x,ll y){
	if(x==h&&y==w)return 1;
	if(dp[x][y]!=-1)return dp[x][y];
	ll sum=0;
	if(s[x+1][y]=='.'&&x+1<=h){
		sum=(sum+dfs(x+1,y))%mod;
	}
	if(s[x][y+1]=='.'&&y+1<=w){
		sum=(sum+dfs(x,y+1))%mod;
	}
	return dp[x][y]=sum;
}

int main(){
	scanf("%lld%lld",&h,&w);
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			dp[i][j]=-1;
		}
	}
	for(int i=1;i<=h;i++){
		scanf("%s",s[i]+1);
	}
	
	printf("%lld\n",dfs(1,1));
}

Measured memory_bytes: 12572
#include<bits/stdc++.h>
#define rep(i,f,n) for(ll i=(f); (i) < (n); i++)
#define repe(i,f,n) for(ll i=(f); (i) <= (n); i++)
using namespace std;
using ll = long long;
#define MOD (ll)1000000007
#define PI 3.14159265359
#define debug(x) cout<<#x<<" :: "<<x<<"\n";
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\n";
#define debug3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\n";
#define P pair<int, int>
#define dvec vector<vector<ll>>
//printf("%.10f\n")
//cout << fixed << setprecision(10);
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;}
ll INF = 1e+18;
int iINF = 1e9;


int main()
{
  int H, W, K; cin >> H >> W >> K;
  vector<string> tmp(H);
  rep(i, 0, H) cin >> tmp[i];
  vector<vector<string>> G(H, vector<string>(W));
  rep(i, 0, H){
    rep(k, 0, W){
      G[i][k] = tmp[i][k];
    }
  }
  
  ll ans = 0;
  for(int bit = 0; bit < (1 << H); ++bit){
    for(int bit2 = 0; bit2 < (1 << W); ++bit2){
      ll cnt = 0;
      rep(i, 0, H){
        rep(k, 0, W){
          if(!(bit2 & (1 << k)) && !(bit & (1 << i)) && G[i][k] == "#") ++cnt;
        }
      }
      if(cnt == K) ++ans;
    }
  }
  cout << ans << endl;

}


Measured memory_bytes: 3656
package main

import (
	"bufio"
	"fmt"
	"os"
	"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
}

var g [][]int
var val []int

func dfs(p, c, sum int) {
	val[c] += sum

	for _, v := range g[c] {
		if v != p {
			dfs(c, v, val[c])
		}
	}
}

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

	n, q := nextInt(), nextInt()
	g = make([][]int, n)
	val = make([]int, n)
	for i := 0; i < n-1; i++ {
		a, b := nextInt(), nextInt()
		a--
		b--

		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}

	for i := 0; i < q; i++ {
		p, x := nextInt(), nextInt()
		p--
		val[p] += x
	}

	dfs(-1, 0, 0)

	for i := 0; i < n; i++ {
		fmt.Printf("%d ", val[i])
	}

	fmt.Println()
}


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

ll f(ll x) {
  if (x == 1) return 1;
  ll a = f(x/2);
  return a*2+1;
}

int main() {
  ll h;
  cin >> h;
  cout << f(h) << endl;
  return 0;
}

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

void funcA()
{
	int T, X;
	cin >> T >> X;
	// Xt=T
	cout << static_cast<double>(T) / X;
}

int main()
{
	int N;
	vector<int> Li;
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		int L;
		cin >> L;
		Li.emplace_back(L);
	}
	int Lmax = *std::max_element(Li.begin(), Li.end());
	int sum = std::accumulate(Li.begin(), Li.end(), 0);
	if (sum - Lmax > Lmax)
	{
		cout << "Yes";
	}
	else
	{
		cout << "No";
	}
	return 0;
}

Measured memory_bytes: 256
n=int(input())
spot=[]
for i in range(n):
    spot.append([int(i) for i in input().split()])

ans=0

def kaijyo(n):
    if n==1:
        return 1
    return n*kaijyo(n-1)



for i in range(n-1):
    for j in range(i+1,n):
        a=spot[i]
        b=spot[j]
        dis=((a[0]-b[0])**2+(a[1]-b[1])**2)**0.5
        ans+=dis*kaijyo(n-1)*2
        
print(ans/kaijyo(n))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define se second
#define fi first
#define pb push_back

int main() {

//	freopen("in.txt", "r", stdin);

	int a, b, c;
	cin >> a >> b >> c;
	int l = 1, r = c;
	ll ans = b;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (a + b >= mid - 1) {
			ans = mid + b;
			l = mid + 1;
		} else
			r = mid - 1;
	}
	cout << ans << endl;

	return 0;
}


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

using namespace std;

#define REP(i, n)   for(int i = 0; i < (n); i++)
#define REPS(i, n)  for(int i = 1; i <= (n); i++)
#define RREP(i, n)  for(int i = (n)-1; i >= 0; i--)
#define RREPS(i, n) for(int i = (n); i > 0; i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define mt make_tuple
#define pb push_back

using ll  = long long;
using pi  = pair<int, int>;
using pl  = pair<ll, ll>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vs  = vector<string>;
using vb  = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;

const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const ll  INFL = 1e18;
const double PI = 3.141592653589793;
const double EPS = 1e-9;

template<class T> bool chmax(T &a, const T &b) { if(a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if(a > b) { a = b; return true; } return false; }

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

    int x; cin >> x;
    if(x == 0) cout << 1 << endl;
    else cout << 0 << endl;
}

Measured memory_bytes: 3648
n = int(input())
s = ['']*n
for i in range(n):
    s[i] = input()
m = int(input())
t = ['']*m
for i in range(m):
    t[i] = input()

ans = 0
for w in set(s):
    m = s.count(w) - t.count(w)
    ans = max(ans, m)

print(ans)

Measured memory_bytes: 3064
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

int main()
{
	char a,b,c;
	char d,e,f;
	scanf("%c%c%c",&a,&b,&c);
	scanf(" %c%c%c",&d,&e,&f);
	if(a==f&&b==e&&c==d)
		printf("YES\n");
	else
		printf("NO\n");
}

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

using namespace std;

typedef long long ll;

const int mx = (int) 1e3 * 100 + 5;
const int inf = (int) 1e9 + 778;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, w;
	cin >> n >> w;
	vector<long long> dp(mx + 1, inf);
	dp[0] = 0;
	for (int t = 0; t < n; t++) {
		int x, y;
		cin >> x >> y;
		// weight, value
		for (long long i = mx - y; i >= 0; i--) {
			// look at dp[i] for result
			// working on dp[i + this.value
			dp[i + y] = min(dp[i + y], dp[i] + (ll) x);
		}
	}
	for (int i = mx; i >= 0; i--) {
		if (dp[i] <= w) {
			cout << i << '\n';
			break;
		}
	}
	return 0;
}

/*
- minimize the weight but maximize the value
dp[value] = total weight required to aquire
that value
- make sure dp[value] <= weight given.
dp[0] = 0
*/


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

typedef long long LL;

const int N=100000;

int n,m;

void into(){
  scanf("%d%d",&n,&m);
}

int ans;

void Get_ans(){
  for (int i=1;i<=n;++i)
	for (int j=1;j<=m;++j){
	  int x=j/10,y=j%10;
	  ans+=x>=2&&y>=2&&x*y==i;
	  //if (x>=2&&y>=2&&x*y==i) printf("%d %d %d\n",i,x,y);
	}
}

void work(){
  Get_ans();
}

void outo(){
  printf("%d\n",ans);
}

int main(){
  into();
  work();
  outo();
  return 0;
}

Measured memory_bytes: 3824