akhauriyash/Code-Regression huggingface dataset:
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
const ll MOD = 1e9 + 7 ;
ll INF=1e9+10;
string a,b;
ll dp[3010][3010];
string ans="";
ll dfs(ll x,ll y){
	if(x>=a.size()||y>=b.size())return 0;
	if(dp[x][y]!=-1)return dp[x][y];
	ll choice1=0;
	ll choice2=0;
	ll choice3=0;
	if(a[x]==b[y]){
		choice1=1+dfs(x+1,y+1);
	}
	else{
		choice2=dfs(x+1,y);
		choice3=dfs(x,y+1);
	}
	return dp[x][y]=max({choice1,choice2,choice3});
}
void build(ll x,ll y){
	if(x>=a.size()||y>=b.size())return;
	// if(dp[x][y]!=-1)return dp[x][y];
	ll choice1=0;
	ll choice2=0;
	ll choice3=0;
	if(a[x]==b[y]){
		choice1=1+dfs(x+1,y+1);
	}
	else{
		choice2=dfs(x+1,y);
		choice3=dfs(x,y+1);
	}
	ll solve=dfs(x,y);
	if(solve==choice2){
		build(x+1,y);
	}
	else if(solve==choice3){
		build(x,y+1);
	}
	else{
		ans+=a[x];
		build(x+1,y+1);
	}
}
int main(){
	fastio;
	memset(dp,-1,sizeof dp);
	cin>>a>>b;
	dfs(0,0);
	build(0,0);
	cout<<ans<<endl;
}

Measured memory_bytes: 71296
#include <iostream>
#include <vector>

using namespace std;

int main(void) {
    vector<int> a(5);
    for (int i = 0 ; i < 5 ; i ++)cin>>a[i];
    for (int i = 0 ; i < 5 ; i ++) {
        if(a[i] == 0) {
            cout<<i + 1<<endl;
        }
    }
}

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

#define MAXN (100010)
#define MAXD (15)

int n, m, q;
int col[MAXN], v[MAXN], d[MAXN], c[MAXN];;
bool vis[MAXN][MAXD];
std::vector<int> vec[MAXN];

void paint(int u, int d, int c){
	if(vis[u][d]) return;
	vis[u][d] = true;
	if(!col[u]) col[u] = c;
	if(!d) return;
	paint(u, d - 1, c);
	for(auto v : vec[u]){
		paint(v, d - 1, c);
	}
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++ i){
		int a, b;
		scanf("%d%d", &a, &b);
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	scanf("%d", &q);
	for(int i = 1; i <= q; ++ i){
		scanf("%d%d%d", v + i, d + i, c + i);
	}
	for(int i = q; i >= 1; -- i){
		paint(v[i], d[i], c[i]);
	}
	for(int i = 1; i <= n; ++ i){
		printf("%d\n", col[i]);
	}
	return 0;
}

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

int main() {
	// your code goes here
	long long int a,b,c,d;
	long long p,q,r,s,t=0,ans;
	cin>>a>>b>>c>>d;
	p=a*c;
	q=a*d;
	r=b*c;
	s=b*d;
	ans=max(p,max(q,(max(r,s))));
	if((a<=0 && b>=0) && (c<=0 && d>=0)){
		ans=max(ans,t);
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cstdlib>
#include <cstdio>
#include <stack>
#include <queue>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> d(n,0);
	for(int i = 0; i < n; i++) {
		cin >> d[i];
	}

	int ans = 0;
	for(int i = 0; i < n-1; i++) {
		for(int j = i+1; j < n; j++) {
			ans += d[i]*d[j];
		}
	}
	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define F first
#define S second
#define pb push_back
#define mp make_pair

const int MOD = 1000000007;
const int N = 1e5 + 18;


int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#endif
    int t = 1;
    //cin >> t;
    while (t--) {
        //for (int tt = 1; tt <= t; tt++) {
        int n;
        cin >> n;
        cout<<(n+1)/2;
    }
    return 0;

}




Measured memory_bytes: 3644
data=[]
for i in range(1,30001):
    if i%2==0 or i%3==0:
        data.append(i)
k=int(input())
if k==3:
    print(*[2,5,63])
elif k==4:
    print(*[2,5,20,63])
elif k==5:
    print(*[2,5,20,63,30])
else:
    ans=data[:k]
    sm=sum(ans)
    if sm%6==2:
        ans[4]=30000
    elif sm%6==3:
        ans[5]=30000
    elif sm%6==5:
        ans[5]=29998
    print(*ans)

Measured memory_bytes: 4684
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int 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;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

struct hoge{ll a,b;};
bool comp(hoge xx,hoge y){
    if(xx.a<y.a)return true;
    if(xx.a==y.a){
        return xx.b<y.b;
    }
    return false;
}

hoge x[100010];
ll h,w,n;

bool find(ll c,ll d){
    hoge hog;hog.a=c;hog.b=d;
    ll L=0;
    ll R=n-1;
    ll mid;
    while(R-L>1){
        mid=(R+L)/2;
        if(comp(hog,x[mid])){
            R=mid;
        }else{
            L=mid;
        }
    }
    if(hog.a==x[L].a && hog.b==x[L].b)return true;
    if(hog.a==x[R].a && hog.b==x[R].b)return true;
    if(R<n-1)if(hog.a==x[R+1].a && hog.b==x[R+1].b)return true;
    return false;
    
}

int main(){
    cin>>h>>w>>n;
    rep(i,0,n-1)cin>>x[i].a>>x[i].b;
    sort(x,x+n,comp);
    bool bol[5][5];
    ll ans[10];rep(i,0,9)ans[i]=0;
    ll counter;
    if(n==0){
        cout<<(h-2)*(w-2)<<endl;
        rep(i,1,9){
            cout<<0<<endl;
        }
        return 0;
    }
    rep(i,0,n-1){
        rep(sx,-2,2)rep(sy,-2,2){
            if(x[i].a+sx>=1 && x[i].a+sx<=h && x[i].b+sy>=1 && x[i].b+sy<=w){
                bol[sx+2][sy+2]=find(x[i].a+sx,x[i].b+sy);
            }else{
                bol[sx+2][sy+2]=false;
            }
        }
        rep(sx,-1,1)rep(sy,-1,1){
            if(x[i].a+sx-1>=1 && x[i].a+sx+1<=h && x[i].b+sy-1>=1 && x[i].b+sy+1<=w){
                counter=0;
                rep(tx,-1,1)rep(ty,-1,1){
                    if(bol[sx+tx+2][sy+ty+2])counter++;
                }
                ans[counter]++;
            }
        }
    }
    ll sum=0;
    rep(i,1,9){
        ans[i]/=i;
        sum+=ans[i];
    }
    ans[0]=(h-2)*(w-2)-sum;
    rep(i,0,9){
        cout<<ans[i]<<endl;
    }
    /*
    rep(i,1,h){
        rep(j,1,w){
            cout<<find(i,j)<<' ';
        }
        cout<<endl;
    }*/
    
    
    return 0;
}


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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true){
            final int n = Integer.parseInt(br.readLine());
            if (n == 0) { break; }
            
            Map<String, Long> data = new HashMap<>();
            Map<String, Long> out = new HashMap<>();
            for (int i=1; i <= n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String e = st.nextToken();
                Long p = Long.parseLong(st.nextToken());
                Long q = Long.parseLong(st.nextToken());
                Long total = data.getOrDefault(e, 0L) + p * q;
                data.put(e, total);
                if (total >= 1_000_000L) {
                    if (out.putIfAbsent(e, total) == null) {
                        System.out.println(e);
                    }
                }
            }
            if (out.isEmpty()) {
                System.out.println("NA");
            }
        }
    }
}

Measured memory_bytes: 26176
#include <stdio.h>

int main()
{
    int A, B;
    scanf("%d%d", &A, &B);
    
    if(A==1 && B==2) {
        printf("3");
    } else if(A==1 && B==3) {
        printf("2");
    } else if(A==2 && B==3) {
        printf("1");
    } else if(A==2 && B==1) {
        printf("3");
    } else if(A==3 && B==1) {
        printf("2");
    } else if(A==3 && B==2) {
        printf("1");
    }
    return 0;
}


Measured memory_bytes: 128
import itertools
def I(): return int(input())
N = I()
ans = 0
kouho = set()
for i in range(1,10):
    for x in itertools.product('357',repeat=i):
        kouho.add(x)
for x in kouho:
    if len(set(x))==3 and int(''.join(x))<=N:
        ans += 1
print(ans)

Measured memory_bytes: 8684
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int m = Integer.parseInt(sc.next());
        int d = Integer.parseInt(sc.next());

        double prob = 0;
        if (d==0) prob=(double)1/n;
        else prob=(double)2*(n-d)/n/n;
        System.out.println(prob*(m-1));
    }
}

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

#define REP(i, n) for(int (i)=0;(i)<(n);++(i))
#define REPV(iter, v) for(auto (iter)=(v).begin(); (iter)!=(v).end();++(iter))
#define ALL(v) (v).begin(),(v).end()

#define MOD 1000000007

using namespace std;

typedef long long ll;

const int MAX = 2001;
ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main()
{
    ll N, K;
    cin >> N >> K;

    COMinit();

    for (int i = 1; i <= K; ++i)
    {
        ll ans;
        if (i == 1)
        {
            ans = N - K + 1;
        }
        else
        {
            if (i - 1 <= N - K)
            {
                ll sum = 0;
                for (int j = i - 1; j <= N - K; ++j)
                {
                    sum = (sum + (COM(j - 1, i - 2) * (N - K - j + 1)) % MOD) % MOD;
                }
                ans = (COM(K - 1, i - 1) * sum) % MOD;
            }
            else
            {
                ans = 0;
            }
            
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 256
n = gets.chomp.split(" ").map(&:to_i)

count = 0
for i in n[1]..(n[0] + 1) do
    min = (i - 1)* i / 2
    max = (n[0] * 2 - i + 1) * i / 2
    sa = max - min + 1    
     
    count = (count + sa) % (10**9 + 7)

end
puts count 

Measured memory_bytes: 14324
#include <stdio.h>

int main()
{
	int n, k, x=1;
	
	scanf("%d %d", &n, &k);
	
	while(n--){
		if(x < k) x *= 2;
		else x += k;
	}
	
	printf("%d", x);
	
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
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; }
const long long INF = 1LL << 60;
 
typedef pair<ll,ll> pairs;
vector<pairs> p;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
#define MAX_N 1000100
bool x[MAX_N];
ll num[MAX_N];
ll fibl[MAX_N]={0};
 
ll fib(ll a){
    if (fibl[a]!=0)return fibl[a];
    if (a==0){
        return 0;
    }else if (a==1){
        return 1;
    }
    return fibl[a]=fib(a-1)+fib(a-2);
}
 
ll eratosthenes(ll n) {
    int p = 0;
    for (ll i=0; i<=n; ++i) x[i] = true;
    x[0] = x[1] = false;
    for(int i=2; i<=n; ++i) {
        if(x[i]) {
            p++;
            for(int j=2*i; j<=n; j+=i) x[j] = false;
        }
        
        num[i] = p;
    }
    return p;
}
 
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}
 
ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

int main(){
    ll a,b;
    cin >> a >> b;
    
    if (a >= 13)cout << b << endl;
    else if (a>=6 && 12>=a)cout << b/2 << endl;
    else cout << 0 << endl;
    
    
    return 0;
}



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

#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i++)
#define rep_d( i, n, m ) for(int i = ( n ) - 1; i >= ( m ); i--)
#define sort_asc( X ) sort(( X ).begin(), ( X ).end())
#define sort_desc( X ) sort(( X ).begin(), ( X ).end(), greater <>())
#define endl "\n"

template <class T> bool chmax( T& a, T b );
template <class T> bool chmin( T& a, T b );
int* eratosthenes( int N );
bool bit_search( int pattern, int N );
void initialize( void );

const ll INF = 1LL << 60;
const int k_mod = 1e9 + 7;
template <typename T, typename K> struct P {
	T a; K b;
};
typedef struct {
	vector <int> to;
	int cost;
} edge;

int main( void ){
	// initialize();
	ll N;
	cin >> N;
	ll cnt = 0, sum = 100;
	while(sum < N){
		cnt++;
		sum =sum*1.01;
	}
	cout << cnt << endl;
}

template <class T> bool chmax( T& a, T b ) {
	if (a < b){
		a = b; return true;
	}
	return false;
}
template <class T> bool chmin( T& a, T b ) {
	if (a > b){
		a = b; return true;
	}
	return false;
}
int* eratosthenes( int N ){
	int* prime_array = new int[ N + 1 ];
	int lim = N;
	prime_array[ 0 ] = 0;
	prime_array[ 1 ] = 0;
	rep( i, 2, N + 1 ){
		prime_array[ i ] = 1;
	}
	rep( i, 2, lim ){
		if (prime_array[ i ] == 0)
			continue;
		lim = N / i;
		for(int j = i * 2; j < N + 1; j += i){
			prime_array[ j ] = 0;
		}
	}
	return prime_array;
}
bool bit_search( int pattern, int N ){
	int cnt = 0;
	rep( bit, 0, N ){
		if (pattern & ( 1 << bit )){
			cnt++;
		}
	}
	return true;
}
void initialize( void ){
	cout << fixed << setprecision( 10 );
}


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

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

    cin >> a >> b >> c;

    int j=0;

    for (int i = a; i <= b; i++ ) {
        if (c % i == 0) {
            j = j + 1;
        }
    }
    cout<< j <<endl;

    return 0;
}


Measured memory_bytes: 3092
#include<iostream>

using namespace std;

int main(){
    int H, W, A, B;
    cin >> H >> W >> A >> B;
    for(int i=1; i<=H; i++){
        for(int j=1; j<=W; j++){
            if((i<=B && j<=A) || (i>B && j>A)){
                cout << 0;
            } else{
                cout << 1;
            }
        }
        cout << endl;
    }
    
}

Measured memory_bytes: 3584
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;

int N;
int dist[2010] = {},s[2010] = {},dp_max[2010] = {},dp_min[2010] = {};
//s[n]:nを根とする部分木に含まれるコマの数
//num[n]:nを根とする部分木における、nからの深さの和
//dp[n]:nを根とする部分木のみで操作を完結させるときの操作回数の最大値
string S;
vector<vector<int>> v(2010);

void dfs(int n,int m){
    for(auto x:v[n]){
        if(x==m) continue;
        dist[x] = dist[n]+1;
        dfs(x,n);
        s[n] += s[x];
    }
    if(S[n]=='1') s[n]++;
}

void dfs2(int n,int m){
    int sum = 0;
    for(auto x:v[n]){
        if(x==m) continue;
        dfs2(x,n);
        sum += dp_max[x]+s[x];
        dp_max[n] += dp_max[x]+s[x];
    }
    for(auto x:v[n]){
        if(x==m) continue;
        dp_min[n] = max(dp_min[n],dp_min[x]+s[x]-(sum-dp_max[x]-s[x]));
    }
    if(dp_min[n]<0) dp_min[n] = (dp_min[n]%2==0? 0:1);
}

int main(){
    cin >> N >> S;
    int a,b;
    for(int i=0;i<N-1;i++){
        cin >> a >> b;
        a--; b--;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    int inf = 1e9,ans = inf;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            dist[j] = 0;
            s[j] = 0;
            dp_max[j] = 0;
            dp_min[j] = 0;
        }
        dfs(i,-1);
        int sum = 0;
        for(int j=0;j<N;j++) if(S[j]=='1') sum += dist[j];
        if(sum%2==1) continue;
        dfs2(i,-1);
/*        cerr << i+1 << " dp_max:";
        for(int j=0;j<N;j++) cerr << dp_max[j] << " ";
        cerr << endl;
        cerr << i+1 << " dp_min:";
        for(int j=0;j<N;j++) cerr << dp_min[j] << " ";
        cerr << endl;
*/        if(dp_min[i]==0) ans = min(ans,sum/2);
    }
    cout << (ans!=inf? ans:-1) << endl;
}

Measured memory_bytes: 512
#include <iostream>

#include<vector>

#include<string>

#include<algorithm>

#include<cmath>

#include<cstdlib>

#include<utility> 

#include<cstdio> 

#define vii vector< pair<int,int> >

#define vi vector<int>

#define INF 1000000007

#define ff first

#define ss second

#define lli long long int

#define ulli unsigned long long int

using namespace std;

int main() {

 ios_base::sync_with_stdio(false);

    cin.tie(NULL);

  double d,t,s;

  cin>>d>>t>>s;

  if(d/s<=t)

  cout<<"Yes";

  else cout<<"No";

  cout<<endl;

}

Measured memory_bytes: 3716
n, a, b, c, d = map(int, input().split())
 
S = input()
x = [0]
 
for s in S:
    if s == '#':
        x.append(1)
    else:
        x.append(0)
 
flag = 0
 
for i in range(a, c):
    if x[i] + x[i+1] == 2:
        flag = 1
for i in range(b, d):
    if x[i] + x[i+1] == 2:
        flag = 1
 
flag2 = 1
 
if c > d:
    for i in range(b-1, d):
        if x[i] + x[i+1] + x[i+2] == 0:
            flag2 = 0
else:
    flag2 = 0
 
if flag + flag2 == 0:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 5008
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
vector<pair<int, int>> to[100010];
bool visited[100010];
ll dist[100010];

int main() {
    int n;
    cin >> n;
    vector<ll>a(n);
    rep(i, 0, a.size()) {
        cin >> a[i];
    }
    ll money = 1000;
    rep(i, 0, a.size()-1) {
        if(a[i] < a[i+1]) {
            ll cnt = money/a[i];
            money += (a[i+1] - a[i]) * cnt;
        }
    }
    cout << money << endl;
    return 0;
}


Measured memory_bytes: 5984
#include <iostream>
#include <vector>
using namespace std;
int main(void){
    int n,i,ans=0,x=0;
    cin >> n;
    vector<int> h(n);
    for(i=0;i<n;i++) cin >> h[i];
    for(i=0;i<n;i++){
        if(x<h[i]){
            ans+=h[i]-x;
            x = h[i];
        }
        else x = h[i];
    }
    cout << ans;
}

Measured memory_bytes: 256
//    .------------------------------------------------------------.
//    |   _  __   ___    ___    ___   _  _    ___     _     _  _   |
//    |  | |/ /  / _ \  |   \  |_ _| | \| |  / __|   /_\   | \| |  |
//    |  | ' <  | (_) | | |) |  | |  | .` | | (_ |  / _ \  | .` |  |
//    |  |_|\_\  \___/  |___/  |___| |_|\_|  \___| /_/ \_\ |_|\_|  |
//    |             ___    ___     _     _  _    ___               |
//    |            / _ \  | _ \   /_\   | \| |  / __|              |
//    |           | (_) | |   /  / _ \  | .` | | (_ |              |
//    |            \___/  |_|_\ /_/ \_\ |_|\_|  \___|              |
//    |                 ___   ___    ___    ___                    |
//    |                | _ ) | __|  / __|  / _ \                   |
//    |                | _ \ | _|  | (_ | | (_) |                  |
//    |                |___/ |___|  \___|  \___/                   |
//    |                                                            |
//    |------------------------------------------------------------|
//    |                      .------------.                        |
//    |                      | KerakTelor |                        |
//    |                      |------------|                        |
//    |                      | 2019-10-08 |                        |
//    |                      '------------'                        |
//    '------------------------------------------------------------'

#include <bits/stdc++.h>

#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("tune=native")

#define vec vector
#define prq priority_queue
#define fi first
#define se second

using namespace std;

using ll=long long;
using ld=long double;

//    .-----------------------------------------.
//    |        ___   _   _    ___   ___         | 
//    |       | _ ) | | | |  / __| / __|        | 
//    |       | _ \ | |_| | | (_ | \__ \        | 
//    |       |___/  \___/   \___| |___/        | 
//    |  ___   ___    ___    ___    _  _   ___  | 
//    | | _ ) | __|  / __|  / _ \  | \| | | __| |
//    | | _ \ | _|  | (_ | | (_) | | .` | | _|  | 
//    | |___/ |___|  \___|  \___/  |_|\_| |___| |
//    |                                         | 
//    '-----------------------------------------'

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    vec<vec<bool>> gr(n,vec<bool>(m));
    for(int i=0;i<n;++i)
    {
        getchar();
        for(int j=0;j<m;++j)
            gr[i][j]=getchar()=='#';
    }
    vec<vec<int>> dp(n+1,vec<int>(m+1));
    const int mod=1e9+7;
    dp[1][1]=1;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(!gr[i-1][j-1])
                dp[i][j]=((dp[i][j]+dp[i-1][j])%mod+dp[i][j-1])%mod;
    printf("%d\n",dp[n][m]);
}



Measured memory_bytes: 4352
/*
 * 2577.cc: Dowsing Machine
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_H = 50;
const int MAX_W = 50;
const int MAX_D = 10;
const int MAX_N = 50;

const int INF = 1 << 30;

const int dxs[] = {1, 0, -1, 0}, dys[] = {0, -1, 0, 1};

/* typedef */

typedef pair<int,int> pii;

/* global variables */

string flds[MAX_H];
int rs[MAX_D], xs[MAX_N], ys[MAX_N], ss[MAX_N];
int cs[MAX_H][MAX_W];
bool rcs[MAX_H][MAX_W];

/* subroutines */

/* main */

int main() {
  int h, w, d, n;
  cin >> h >> w >> d >> n;

  int sx, sy;
  for (int y = 0; y < h; y++) {
    cin >> flds[y];
    for (int x = 0; x < w; x++)
      if (flds[y][x] == 'D') {
	sx = x; sy = y;
	flds[y][x] = '.';
      }
  }

  for (int i = 0; i < d; i++) cin >> rs[i];

  for (int i = 0; i < n; i++) {
    int xi, yi, si;
    cin >> xi >> yi >> si;
    
    int r1 = (si >= d) ? INF : rs[si];
    int r0 = (si <= 0) ? -1 : rs[si - 1];
    //printf("%d: (%d,%d):%d = %d,%d\n", i, xi, yi, si, r0, r1);
    
    for (int y = 0; y < h; y++)
      for (int x = 0; x < w; x++)
	if (flds[y][x] == '.' &&
	    xi - r1 <= x && x <= xi + r1 && yi - r1 <= y && y <= yi + r1 &&
	    ! (xi - r0 <= x && x <= xi + r0 && yi - r0 <= y && y <= yi + r0))
	  cs[y][x]++;
  }

  memset(rcs, 0, sizeof(rcs));
  rcs[sy][sx] = true;

  queue<pii> q;
  q.push(pii(sx, sy));

  while (! q.empty()) {
    pii u = q.front(); q.pop();
    int &ux = u.first, &uy = u.second;

    for (int di = 0; di < 4; di++) {
      int vx = ux + dxs[di], vy = uy + dys[di];
      if (vx >= 0 && vx < w && vy >= 0 && vy < h &&
	  flds[vy][vx] == '.' && ! rcs[vy][vx]) {
	rcs[vy][vx] = true;
	q.push(pii(vx, vy));
      }
    }
  }

  int gn = 0, ok = 0, ng = 0;
  for (int y = 0; y < h; y++)
    for (int x = 0; x < w; x++)
      if (cs[y][x] == n) {
	gn++;
	if (rcs[y][x]) ok++;
	else ng++;
      }
  //printf("gn=%d, ok=%d, ng=%d\n", gn, ok, ng);

  if (gn == 0) cout << "Broken" << endl;
  else if (ng == 0) cout << "Yes" << endl;
  else if (ok == 0) cout << "No" << endl;
  else cout << "Unknown" << endl;
  
  return 0;
}

Measured memory_bytes: 1240
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define vi vector <int>
#define vl vector <ll>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d",x)
#define plld(x) printf("%lld",x)
#define pds(x) printf("%d ",x)
#define pllds(x) printf("%lld ",x)
#define pdn(x) printf("%d\n",x)
#define plldn(x) printf("%lld\n",x)
#define INF 2e9
#define INFLL 4e18
using namespace std;
ll powmod(ll base,ll exponent,ll mod){ // with mod < 1e9
	ll ans=1;
	while(exponent){
		if(exponent&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		exponent/=2;
	}
	return ans;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
const int upperlimit = 1e6+1;
const int mod = 1e9+7;
ll dp[upperlimit][3];
int arr[upperlimit];
int main() {
	int n,num;
	sd(n);
	ll ans=-INFLL;
	num=n/2;
	for(int i = 1; i <= n; i++) sd(arr[i]);
	for(int i = 0; i <= n; i++) for(int j = 0; j < 3; j++) dp[i][j]=-INFLL;
	dp[0][0]=0;dp[1][0]=arr[1];dp[2][0]=arr[2];
	for(int i = 3; i <= n; i++){
		for(int j = 0; j < 3; j++){
			for(int k = 0; k <= j; k++){
				if(i-k<2) break;
				dp[i][j]=max(dp[i][j],dp[i-k-2][j-k]+arr[i]);
			}
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 3; j++){
			if(int((i+1-j)/2)==num){
				ans=max(ans,dp[i][j]);
			}
		}
	}
	plld(ans);
	return 0;
}

Measured memory_bytes: 9300
while True:
    N = int(input())
    if N == 0: break
    W,H = map(int,input().split())
    fld = [[0 for w in range(W)] for h in range(H)]
    for i in range(N):
        x,y = map(lambda s:int(s)-1,input().split())
        fld[y][x] = 1
    cums = [[0 for w in range(W+1)] for h in range(H+1)]
    for y in range(H):
        for x in range(W):
            cums[y+1][x+1] = fld[y][x] + cums[y][x+1] + cums[y+1][x] - cums[y][x]
    S,T = map(int,input().split())
    ans = 0
    for y in range(H-T+1):
        for x in range(W-S+1):
            ans = max(ans, cums[y+T][x+S] - cums[y+T][x] - cums[y][x+S] + cums[y][x])
    print(ans)

Measured memory_bytes: 5928
n,w=map(int,input().split())
dp = [[0 for i in range(w+1)] for j in range(n+1)]
for i in range(1,n+1):
  wi,vi=map(int,input().split())
  for wb in range(w+1):
    if wb < wi:
      dp[i][wb] = dp[i-1][wb]
    else:
      dp[i][wb] = max(dp[i-1][wb],dp[i-1][wb-wi]+vi)
print(dp[n][w])

Measured memory_bytes: 171400
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        int n = s.length;
        for (char c = 'a' ; c <= 'z' ; c++) {
            boolean flg = true;
            for (int j = 0 ; j < n ; j++) {
                if (s[j] == c) flg = false;
            }
            if(flg) {
                System.out.println(c);
                return;
            }
        }
        System.out.println("None");

    }

}

Measured memory_bytes: 26696
import java.util.*;
public class Main
{
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    int N = sc.nextInt();
	    int op= N%10;
	    if(op==2|| op==4||op==5||op==7||op==9){
	        System.out.println("hon");
	    }
	    if(op==0|| op==1||op==6||op==8){
	        System.out.println("pon");
	    }
	   	if(op==3){
	        System.out.println("bon");
	    }
	}
}

Measured memory_bytes: 35704
function main(input) {
  input = input.split("\n");
  var values = input.map(function(v) { return parseInt(v); });

  var min = Number.MAX_VALUE, val = -Number.MAX_VALUE;
  var N = values[0];
  for (var i = 1; i <= N-1; i++) {
    if (min >= values[i]) {
      min = values[i];
    }
    if (values[i+1] - min >= val) {
      val = values[i+1] - min;
    }
  }
  console.log(val);
  return val;
}
main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 36976
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define INF 1e9

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

    int n;
    cin >> n;

    int ans = 0;
        int x = 1;
    for (int i = 0; i < 3; i++) {
        int buf = n % 10;
        if (buf == 1) ans += x * 9;
        else if (buf == 9) ans += x * 1;
        else ans += x * buf;
        n /= 10;
        x *= 10;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int w, h, x, y, r;
    cin>>w>>h>>x>>y>>r;
    if((x+r)>w || (x-r)<0 || (y+r)>h || (y-r)<0 || x<0 || y<0) cout<<"No";
    else cout<<"Yes";
    cout<<"\n";
    return 0;
}


Measured memory_bytes: 3092
import sys
input = sys.stdin.readline
from heapq import *
N, Q = map(int, input().split())

X = []
for _ in range(N):
    s, t, x = map(int, input().split())
    X.append((s-x,t-x,x))

X = sorted(X, key = lambda x: x[0])
D = [int(input()) for _ in range(Q)]
i = 0
j = 0
A = []
B = []
C = []
for q in range(Q):
    while i < len(X) and D[q] >= X[i][0]:
        a, b, x = X[i]
        heappush(A, (x, b))
        heappush(B, (b, x))
        i += 1
    while len(B) and B[0][0] <= D[q]:
        b, x = heappop(B)
        heappush(C, (x, b))
    while len(C) and len(A) and C[0][0] == A[0][0]:
        heappop(A)
        heappop(C)
    print(A[0][0] if A else -1)

Measured memory_bytes: 126560
n = int(input())
a = []
xy = [[] for i in range(n)]
for i in range(n):
    ai = int(input())
    a.append(ai)
    for j in range(ai):
        xyi = list(map(int, input().split()))
        xy[i].append(xyi)
res = 0
for i in range(2 ** n):
    flag = [(1 if i & 2 ** b == 2 ** b else 0) for b in range(n)]
    outs = 0
    for j in range(n):
        if flag[j] == 1:
            for k in range(a[j]):
                x, y = xy[j][k]
                x -= 1
                if flag[x] != y:
                    outs = 1
                    break
    if outs == 0:
        res = max(sum(flag), res)

print(res)



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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef pair<pii, pii> piipii;

#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define eb emplace_back

int a[500005], cur[500005];
ll dp[500005];
int main(){
    int n, d;
    scanf("%d%d", &n, &d);
    cur[0] = d;
    for(int i=1;i<=n;i++){
        scanf("%d", &a[i]);
        if(cur[i-1]-a[i] >= 0) cur[i] = cur[i-1] - a[i];
        else if(-(cur[i-1]-a[i]) <= cur[i-1]) cur[i] = -(cur[i-1] - a[i]);
        else cur[i] = cur[i-1];
    }
    dp[n] = 1;
    for(int i=n-1;i>=1;i--){
        if(2*dp[i+1] <= a[i+1]) dp[i] = dp[i+1];
        else dp[i] = dp[i+1] + a[i+1];
    }
    int q;
    scanf("%d", &q);
    while(q--){
        int x;
        scanf("%d", &x);
        if(cur[x-1] >= dp[x]) printf("YES\n");
        else printf("NO\n");
    }
}

Measured memory_bytes: 9728
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ll s,c;
    cin >> s >> c;
    if(s >= c){
        cout << c / 2 << endl;
        return 0;
    }
    else
    {
        ll sum = s;
        c -= s * 2;
        sum += c / 4;
        cout << sum << endl;
    }
    
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;
//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; }
template<class T> inline bool chmin(T a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL << 60;
typedef long long int ll ;


#define INF 2000000000

int main(void){
    
    int N;
    int A[100];
    int res=1;
    cin >> N;
    
    for(int i=0;i<N;i++){
        cin >> A[i];
    }
    
     for(int i=0;i<N;i++){
        
        if(A[i]%2 == 0) {
            if( A[i]%3 != 0 && A[i]%5 != 0 ) {
                cout << "DENIED" << endl ;
                return 0;
            }
        }
        
    }
    
    cout << "APPROVED" << endl;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
string s, t;
int mem[N][N];
char dir[N][N];
int main(){
   cin>>s>>t;
   int sz1 = s.size() + 1;
   int sz2 = t.size() + 1;
   stack<char>res;
   for(int i = 1; i < sz1; i++)
   {
     for(int j = 1; j < sz2; j++)
     {
       if(s[i - 1] == t[j - 1])
       {
         mem[i][j] = mem[i - 1][j - 1] + 1;
         dir[i][j] = 'd';
       }
       else{
         mem[i][j] = max(mem[i - 1][j], mem[i][j - 1]);
         if(mem[i - 1][j] > mem[i][j - 1])
         {
           dir[i][j] = 'l';
         }
         else{
           dir[i][j] = 'u';
         }
       }
     }
   }
   int i = s.size(), j = t.size();
   while(i > 0 && j > 0)
   {
     if(dir[i][j] == 'd')
     {
       i--, j--;
       res.push(s[i]);
     }
     else if(dir[i][j] == 'l')
     {
       i--;
     }
     else{
       j--;
     }
   }
   while(res.size())
   {
     cout<<res.top();
     res.pop();
   }
   cout<<endl;
   return 0;
}


Measured memory_bytes: 149120
import java.util.Scanner

object Main {
  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)
    val n, m = sc.nextInt()
    val a = List.fill(n)(sc.nextInt())
    val count = a.count(c => c >= a.sum * 1.0 / (4 * m))
    if (count >= m) println("Yes") else println("No")
  }
}

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

#define int long long

int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];
  vector<int> pref(n);
  const int MOD = 1e9 + 7;
  pref[0] = a[0];
  for (int i = 1; i < n; i++) {
    pref[i] += pref[i - 1] + a[i];
    pref[i] %= MOD;
  }
  // const int MOD = 1e9 + 7;
  int res = 0;
  for (int i = 0; i < n; i++) { 
    res += (a[i] % MOD * (pref[n - 1] - pref[i]) % MOD) % MOD;
    res %= MOD;
  }   
  cout << (res + MOD) % MOD << '\n';
  return 0;
}


Measured memory_bytes: 6364
#include <iostream>
using namespace std;
typedef long long ll;
int main( void )
{
  ios::sync_with_stdio(false);
  ll N, A, B, C, D;
  cin >> N >> A >> B >> C >> D;
  ll X = A - B;
  ll a = -N+1;
  ll b = 0;
  for( int i=0; i<N; i++ ){
    if( (a*D + b*C) <= X && X <= (a*C+b*D) ){
      cout << "YES" << endl;
      return 0;
    }
    a++;
    b++;
  }
  cout << "NO" << endl;
}

Measured memory_bytes: 256
h,w = gets.split.map &:to_i
sum = 0
s = h.times.map{
  gets.chomp.chars.map{|c|
    f = c==?.
    sum+=1 if f
    f
  }
}

q = [0]
used = [false]*(h*w)
used[0] = true
dis = [0]*(h*w)

nex = [0,1,0,-1]
ney = [1,0,-1,0]

while q.size!=0
  now = q.shift
  nowx = now%w
  nowy = now/w
  4.times{|i|
    x = nowx + nex[i]
    y = nowy + ney[i]
    t = y*w+x
    if 0<=x && x<w && 0<=y && y<h && s[y][x] && !used[t]
      q << t
      used[t] = true
      dis[t] = dis[now]+1
    end
  }
end

p (dis[-1]!=0)? sum-dis[-1]-1 : -1

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

int main(){
    int k;
    string s;
    cin>>k>>s;
    
    if(s.size()<=k)
        cout<<s<<"\n";
    else{
        for(int i=0;i<k;i++)
            cout<<s[i];
        cout<<"...\n";
    }
    
    return 0;
}

Measured memory_bytes: 3612
#include <iostream>
#include <algorithm>
#include <string>
#define rep(i, a, n) for(int i = a;i < n;i++)
#define repe(i, a, n) for(int i = a;i <= n;i++)
#define repr(i, a, n) for(int i = a;i > n;i--)
using namespace std;


int main(){
	int a, b;
	cin >> a >> b;

	int cnt = 0;
	string n, m;
	repe(i, a, b){
		n = to_string(i);
		m = n;
		rep(j, 0, n.size()){
			m[j] = n[n.size() - j - 1];
		}
		if(n == m) cnt++;
	}

	cout << cnt << endl;

	return 0;
}

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


flag = True
if not C[0][0] - C[0][1] == C[1][0] - C[1][1] == C[2][0] - C[2][1]:
    flag = False
if not C[0][1] - C[0][2] == C[1][1] - C[1][2] == C[2][1] - C[2][2]:
    flag = False


print("Yes" if flag is True else "No")


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

using namespace std;

int main() {
  int a;
  bool ans1 = false, ans2 = false;
  
  cin >> a;
  
  int format1 = a % 100;
  int format2 = (a / 100);
  
  if (1 <= format1 && format1 <= 12) {
    ans1 = true;
  }
  
  if (1 <= format2 && format2 <= 12) {
    ans2 = true;
  }
  
  if (ans1 && ans2) {
    cout << "AMBIGUOUS" << endl;
  } else {
    if (ans1) {
      cout << "YYMM" << endl;
    } else if (ans2) {
      cout << "MMYY" << endl;
    } else {
      cout << "NA" << endl;
    }
  }
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define int long long
#define all(a) a.begin(), a.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e15;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k, ans = 0;
    cin >> n >> k;
    for(int b = k + 1; b <= n; b++){
        int tmp = n / b * (b - k) + max(0LL, n % b - k + 1);
        if(k == 0) tmp--;
        ans += tmp;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cout << #x << " = " << (x) << endl;
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; }
//#define int long long

vector<ll> pFactorization(ll n) {
    vector<ll> ret;
    for(ll i=2; i*i<=n; i++) {
        if(n % i == 0) {
            ret.push_back(i);
            while(n % i == 0) n /= i;
        }
    }
    if(n != 1) ret.push_back(n);
    return ret;
}

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

void solve() {
	ll a, b; cin >> a >> b;
    ll g = gcd(a, b);
    vector<ll> G = pFactorization(g);
    
    int ans = G.size();
    cout << ans + 1 << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init();
	solve();
	//cout << "finish" << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		int D = sc.nextInt();

		if(A + B > C + D) {
			System.out.println("Left");
		}else if(A + B < C + D) {
			System.out.println("Right");
		}else if(A + B == C + D) {
			System.out.println("Balanced");
		}
	}
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define mset(x, y) memset(x, y, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;

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

inline int Read()
{
	int x = 0, f = 1, c = getchar();
	for (; !isdigit(c); c = getchar())
		if (c == '-')
			f = -1;
	for (;  isdigit(c); c = getchar())
		x = x * 10 + c - '0';
	return x * f;
}

const int MAXN = 100005;

int n, m, rta = 1, rtb, f[MAXN], siz[MAXN], sic[MAXN];
bool cir[MAXN], col[MAXN];
vector <int> adj[MAXN]; 
LL ans;

inline int Find(int x)
{
	while (x ^ f[x])
		x = f[x] = f[f[x]];
	return x;
}

inline void Dfs(int x, int p)
{
	sic[x] = col[x], siz[x] = 1, cir[x] = x == rtb;
	for (auto y : adj[x])
		if (y ^ p)
			col[y] = col[x] ^ 1, Dfs(y, x), siz[x] += siz[y], sic[x] += sic[y], cir[x] |= cir[y];
}

int main()
{
#ifdef wxh010910
	freopen("data.in", "r", stdin);
#endif
	n = Read(), m = Read();
	if (n & 1)
		return puts("-1"), 0;
	for (int i = 1; i <= n; i ++)
		f[i] = i;
	for (int i = 1, x, y; i <= m; i ++)
	{
		x = Read(), y = Read();
		if (Find(x) ^ Find(y))
			f[Find(x)] = Find(y), adj[x].pb(y), adj[y].pb(x);
		else
			rta = x, rtb = y;
	}
	Dfs(rta, 0);
	if (m == n - 1)
	{
		if (sic[1] << 1 ^ n)
			return puts("-1"), 0;
		for (int i = 1; i <= n; i ++)
			ans += abs(siz[i] - sic[i] - sic[i]);
		return printf("%lld\n", ans), 0;
	}
	if (col[rtb])
	{
		if (sic[rta] << 1 ^ n)
			return puts("-1"), 0;
		vector <int> tmp;
		for (int i = 1; i <= n; i ++)
			if (cir[i])
				tmp.pb(siz[i] - sic[i] - sic[i]);
			else
				ans += abs(siz[i] - sic[i] - sic[i]);
		sort(tmp.begin(), tmp.end());
		for (auto x : tmp)
			ans += abs(x - tmp[tmp.size() / 2]);
		return printf("%lld\n", ans), 0;
	}
	int c = sic[rta] - (n >> 1);
	ans = abs(c);
	for (int i = 1; i <= n; i ++)
		if (i ^ rta)
			if (cir[i])
				ans += abs(siz[i] - sic[i] - sic[i] + c);
			else
				ans += abs(siz[i] - sic[i] - sic[i]);
	return printf("%lld\n", ans), 0;
}


Measured memory_bytes: 11004
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define repr(e,x) for(auto& e:x)
using namespace std;
typedef long long ll;
typedef long double ld;

int N;

int main(){
    cin>>N;

    if(N/10==9 || N%10==9){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 3608
#include "bits/stdc++.h"
using namespace std;
const int MOD = 1e9 + 7;
typedef long long lint;
const int INF =1e7;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repi(i, k, n) for (int i = (k); i < (int)(n); ++i)
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()
#define pb push_back
int main(){
    int a, b;
    cin >> a >> b;
    cout << (a - 1) * (b - 1) << endl;
    return 0;
}

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

using namespace std;

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

    for(int att = 0; att < n; att++) {
        int balls[10];      // ボールのリスト
        stack<int> r, l;    // 筒の状態をプールするstack
        bool isOK = true;   // 分配可能フラグ
        
        for(auto b : balls) {
            cin >> b;
            
            if(!isOK) continue;
            if      (r.empty() || r.top() < b)  { r.push(b); }
            else if (l.empty() || l.top() < b)  { l.push(b); }
            else                                { isOK = !isOK; }
        }
        cout << (isOK ? "YES" : "NO") << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3104
n, m, c = map(int, input().split())
b = list(map(int, input().split()))
a = []
cnt = 0
for i in range(n):
	a = list(map(int, input().split()))
	wa = 0
	for j in range(m):
		wa += a[j]*b[j]
	if wa+c > 0:
		cnt += 1
print(cnt)

Measured memory_bytes: 3060
N, T = map(int, input().split())
t = list(map(int, input().split()))

# N, T= 4, 1000000000
# t = [0, 1000, 1000000, 1000000000]
# N, T = 9, 10
# t = [0, 3, 5, 7, 100, 110, 200, 300, 311]

total_time = 0
for i in range(N - 1):
    if t[i] + T < t[i + 1]:
        total_time += T
    else:
        total_time += t[i + 1] - t[i]
print(total_time + T)


Measured memory_bytes: 25196
using namespace std;

#include <cstdio>
#include <cstdint>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>

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

    long long int     X = 0;
    cin >> X;
    long long int     M = 100;
    // double  MD = 100.0;
    int     year = 0;

    while(M < X){
        year ++;
        M = M*1.01;
        // MD = MD*1.01;
        // M = (long long int)MD;
    }
    int ans = year;
    cout << ans << "\n";
    return 0;
    
}

Measured memory_bytes: 3648
from itertools import accumulate
n = int(input())
A = (list)(map(int, input().split()))
B = (list)(map(int, input().split()))
A_sum = (list)(accumulate(A))
B_sum = (list)(accumulate(reversed(B)))
print(max(A_sum[i]+B_sum[n-i-1] for i in range(n)))


Measured memory_bytes: 3060
// This amazing code is by Eric Sunli Chen.
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;
template<typename T> void get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'; t=getchar());
	if(t=='-')neg=true,t=getchar();
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) get1(a),get1(b)
#define get3(a,b,c) get1(a),get2(b,c)
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

int n,a[100111];
map<int,int> cnt;
int main()
{
	get1(n);
	for(int i=1;i<=n;i++)
	{
		get1(a[i]);
		cnt[a[i]]++;
		cnt[a[i]-1]++;
		cnt[a[i]+1]++;
	}
	int mx=0;
	for(auto i:cnt)mx=max(mx,i.ss);
	printendl(mx);
	return 0;
}

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

void push(int a);
int pop(void);

int top;
int stack[200];


int main(void)
{
  int m,n;
  char data[100];

  while(scanf("%s",data) != -1){

    if(data[0] == '+'){
      m = pop();
      n = pop();
      push(m+n);
      
    } else if (data[0] == '-'){
      n = pop();
      m = pop();
      push(m-n);
      
    } else if(data[0] == '*'){
      m = pop();
      n = pop();
      push(m*n);
      
    } else {
      push(atoi(data));
    }
  }

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

  return 0;
}




void push(int a){
  ++top;
  stack[top] = a;
}


int pop(void){
  top--;
  return stack[top+1];
}




Measured memory_bytes: 2108
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int N,M,S,T,u,v,D;
vector<pair<int,int>>G[1<<17];
long mod=1e9+7,a[1<<17],b[1<<17],c[1<<17],d[1<<17];
priority_queue<pair<long,int>>P;
void calc(int S,long*d,long*w)
{
	for(int i=w[S]=1;i<=N;)d[i++]=-1e18;
	P.push({d[S]=0,S});
	while(P.size())
	{
		long c=P.top().first,u=P.top().second;
		P.pop();
		if(d[u]==c)for(pair<int,int>p:G[u])
		{
			long v=p.first,nxt=c-p.second;
			if(d[v]<nxt)w[v]=w[u],P.push({d[v]=nxt,v});
			else if(d[v]==nxt)(w[v]+=w[u])%=mod;
		}
	}
}
main()
{
	cin>>N>>M>>S>>T;
	for(;cin>>u>>v>>D;G[v].push_back({u,D}))G[u].push_back({v,D});
	calc(S,a,b);calc(T,c,d);
	long ans=b[T]*b[T],t=a[T];
	for(u=0;u++<N;)
	{
		if(2*a[u]==t)ans-=b[u]*b[u]%mod*d[u]%mod*d[u]%mod;
		for(pair<int,int>p:G[u])if(2*a[u]>t&&2*a[v=p.first]<t&&a[u]+c[v]-p.second==t)ans-=b[u]*b[u]%mod*d[v]%mod*d[v]%mod;
	}
	cout<<(ans+mod)%mod;
}


Measured memory_bytes: 14448