akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>

int N, sum;
int d[50 + 1];

int main(void) {
    scanf("%d", &N);
    for(int i = 0;i < N;i++) {
        scanf("%d", &d[i]);
    }

    sum = 0;
    for(int i = 0;i < N - 1;i++) {
        for(int j = i + 1;j < N;j++) {
            sum += d[i] * d[j];
        }
    }

    printf("%d\n", sum);
    
    return 0;
}

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

const ll mod = 1e9 + 7;

int main() {
    ll n, k, a[200000];
    cin >> n >> k;
    for (ll i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);
    ll ub = mod * mod, lb = -(mod * mod);
    while (ub - lb > 1) {
        ll mid = (ub + lb) / 2, cnt = 0;
        for (ll i = 0; i < n; i++) {
            if (a[i] > 0)
                cnt += upper_bound(a, a + n, (long double)mid / a[i]) - a;
            else if (a[i] < 0)
                cnt += n - (lower_bound(a, a + n, (long double)mid / a[i]) - a);
            else if (mid >= 0)
                cnt += n;
            if (a[i] * a[i] <= mid)
                cnt--;
        }
        (cnt >= 2 * k ? ub : lb) = mid;
    }
    cout << ub << endl;
}


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


int main(){

  long long int A[4][4];
  long long int i,j,k;
  for(i=1;i<=3;i++){
  for(j=1;j<=3;j++){
   scanf("%lld",&A[i][j]);
  }
}
 long long int N;
  scanf("%lld",&N);

/*
  char A[];
  scanf("%s",A);
  */

  
  long long int b[N+1];
  for(k=1;k<=N;k++){
   scanf("%lld",&b[k]);
  for(i=1;i<=3;i++){
  for(j=1;j<=3;j++){
    if(A[i][j]==b[k]){
      A[i][j]=0;
    }

  }
}

   }
for(i=1;i<=3;i++){  
if(A[1][i]==0 && A[2][i] ==0 && A[3][i]==0){
  printf("Yes");
  return(0);
}
}

for(i=1;i<=3;i++){  
if(A[i][1]==0 && A[i][2] ==0 && A[i][3]==0){
  printf("Yes");
  return(0);
}
}

if(A[1][1]==0 && A[2][2] ==0 && A[3][3]==0){
  printf("Yes");
  return(0);
}

if(A[3][1]==0 && A[2][2] ==0 && A[1][3]==0){
  printf("Yes");
  return(0);
}

printf("No");

 return(0);
 }


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

#define int ll
#define rep(i,n) for(ll i=0,i##_cond=(n);i<i##_cond;++i)
#define pb push_back
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
constexpr int inf = 1ll<<61;

struct node {
  ll v, d;
  node(ll _a, ll _b):v(_a),d(_b){}
  bool operator<(const node &n) const { return d > n.d; }
};
struct edge {
  ll to, d;
  edge(ll _to, ll _d):to(_to),d(_d){}
};
class dijkstra{
public:
  ll ans;

  dijkstra(ll s,ll t,vector<vector<edge>> &g,vector<vector<edge>> &f){ // sからtへの最短経路
    vector<vector<vector<edge>>> G(2);
    G[0] = move(g);
    G[1] = move(f);
    vvi dist(2,vi(G[0].size(),inf));
    vector<vector<bool>> visit(2,vector<bool>(G[0].size(),false));
  
    vector<priority_queue<node>> que(2);
    que[0].push(node(s,0));
    que[1].push(node(t,0));
    dist[0][s] = 0;
    dist[1][t] = 0;

    while(!que[0].empty() and !que[1].empty()){
      ll k = (que[0].top().d <= que[1].top().d)?0:1;      
      ll v = que[k].top().v, d = que[k].top().d;
      que[k].pop();

      if(visit[k^1][v]) goto L;
      visit[k][v] = true;

      rep(i, G[k][v].size()){
	auto n = G[k][v][i];
	ll tmp = d + n.d;
	if(dist[k][n.to] > tmp){
	  dist[k][n.to] = tmp;
	  que[k].push(node(n.to, tmp));
	}
      }
    }
  L:
    g = move(G[0]);
    f = move(G[1]);

    ans = inf;
    rep(i,g.size()) ans = min(ans, dist[0][i]+dist[1][i]);
  }
};

main(){
  int k; cin >> k;
  vector<vector<edge>> g(k),f(k);
  rep(i,k){
    g[i].pb(edge((i+1)%k,1));
    g[i].pb(edge((i*10)%k,0));
    
    f[(i+1)%k].pb(edge(i,1));
    f[(i*10)%k].pb(edge(i,0));
  }
  dijkstra d(1,0,g,f);
  cout << d.ans+1 << endl;
}

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

  
int main() {
  int N;
  string S;
  cin >> N >>S;
  bool f = true;
  if(N%2 == 1 ) puts("No");
  else {
	int m = N / 2 ;
    for(int i=0;i<m;i++){
      if(S[i] != S[i+m]) f = false;
    }
    if(f) puts("Yes");
    else puts("No");
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define re register
long long a[200100],b[200100],ff[210][210],gg[210][210];
char ss[100100];
int main()
{
	re int n;
	scanf("%d",&n);
	re long double f1f=0;
	re long long ans=0;
	for(re int i=1;i<=n;i++)
	{
		a[i]=0;b[i]=1;
		re int bl=0;
		scanf("%s",ss+1);
		re int nn=strlen(ss+1);
		for(re int i1=1;i1<=nn;i1++)
		{
			if(ss[i1]=='.'){bl=1;continue;}
			a[i]=a[i]*10+(ss[i1]-'0');
			if(bl)b[i]=b[i]*10;
		}
		re int f2=0,f5=0;
		while(!(a[i]%2))a[i]/=2,f2++;
		while(!(a[i]%5))a[i]/=5,f5++;
		while(!(b[i]%2))b[i]/=2,f2--;
		while(!(b[i]%5))b[i]/=5,f5--;
		ff[f2+100][f5+100]++;
		if(f2>=0&&f5>=0)ans--;
	}
	for(re int i=60;i>=-60;i--)
		for(re int j=60;j>=-60;j--)gg[i+100][j+100]=(ff[i+100][j+100]+gg[i+101][j+100]+gg[i+100][j+101]-gg[i+101][j+101]);
	for(re int i=-60;i<=60;i++)
		for(re int j=-60;j<=60;j++)ans+=ff[i+100][j+100]*gg[100-i][100-j];
	printf("%lld\n",ans/2);
}

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

int main() {
  string S;
  cin >> S;
  
  if(S=="hi" || S=="hihi" || S=="hihihi" || S=="hihihihi" || S=="hihihihihi")
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  
  return 0;
}

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

int main() {
  int count=0;
  int N;
  int X;
  cin>>X;
  while(1){
    for(int i=2;i<(int)sqrt(X)+1;i++){
      if(X%i==0){
        count++;
      }
    }
    if(count==0){
      cout<<X;
      return 0;
    }
    else{
      count=0;
      X++;
    }
  }
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int res = 0;
        for (int i = 1; i <= n; i++) {
            int a = sc.nextInt();
            if (i % 2 == 1 && a % 2 == 1) res++;
        }
        System.out.println(res);
    }
}

Measured memory_bytes: 35656
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
int n;
ll x, a[100001], ans = 0, sum;

int main() {
	cin >> n >> x;
	for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
	sum = a[0] + a[1];
	for (int i = 1; i < n; i++) {
		if (sum > x) {
			ans += sum - x;
			a[i] -= sum - x;
			if (a[i] < 0) a[i] = 0;
		}
		sum = a[i + 1] + a[i];
	}
	cout << ans << endl;
}

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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root =NIL;

Node treeMinimum(Node x){
  while(x->right!=NIL)x=x->left;
  return x;
}

Node treeSearch(Node x, int k){
  while (x!=NIL && k!=x->key){
    if(k<x->key)x=x->left;
    else x=x->right;

  }
 return x;
}

Node treeSuccessor(Node x){
  Node y;
  if(x->right!=NIL){
    return treeMinimum(x->right);
    y=x->parent;
    while (y !=NIL && x==y->right){
      x=y;
      y=y->parent;
    }
    return y;
}

}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
  if(z->left==NIL||z->right==NIL){
    y = z;
}
  else y=treeSuccessor(z);

  if(y->left !=NIL)x=y->left;
  else x=y->right;

  if(x != NIL)x->parent=y->parent;
  if(y->parent==NIL)root=x;
  else if(y==y->parent->left)y->parent=x;
  else y->parent->right;
  if(y!=z){
    z->key=y->key;
  }
}



void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL){
    y=x;
    if(z->key<x->key)x=x->left;
    else x=x->right;
  }
  z->parent=y;
  if(y==NIL)root=z;
  else if (z->key<y->key)y->left=z;
  else y->right=z;
}

void inorder(Node u){
  if(u!=NIL){
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
  }
}
void preorder(Node u){
  if(u!=NIL){
    
    printf(" %d",u->key); 
    preorder(u->left);
    preorder(u->right);

  }
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}

Measured memory_bytes: 19364
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.trim()).split("\n");
for(var I=0;I<Arr.length;I++){
   var a=Arr[I].split(",").map(Number);
   var arr=[];
   for(var i=0;i<13;i++)arr[i]=0;
      a.forEach(function(v){
      arr[v-1]++;
   });
   var copy=arr.slice();
   arr.sort(function(a,b){return b-a;});
   var ans;
   if(arr[0]>=4)ans="four card";
   else if(arr[0]==3 && arr[1]==2)ans="full house";
   else if((copy.join("")).match(/11111|1000000001111/))ans="straight";
   else if(arr[0]==3)ans="three card";
   else if(arr[0]==2 && arr[1]==2)ans="two pair";
   else if(arr[0]==2)ans="one pair";
   else ans="null";
   console.log(ans);
}

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

// macros
#define overload_rep(_1, _2 ,_3 ,name, ...) name
#define re_p(i, n) for(int i = 0; i < (n); ++i)
#define r_ep(i, x, y) for(int i = (x); i <= (y); ++i)
#define rep(...) overload_rep(__VA_ARGS__, r_ep, re_p)(__VA_ARGS__)
#define all(a) a.begin(), a.end()
#ifndef STOP_DEBUG
#define debug(...)\
    do { cerr << boolalpha << "[" << #__VA_ARGS__ << "]:";\
    debug_cerr(__VA_ARGS__); cerr << noboolalpha; } while (0)
#else
#define debug(...)
#endif

// functions
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; }
void debug_cerr(){ cerr << '\n'; }
template<class Head, class... Tail>
void debug_cerr(Head head, Tail... tail){
    cerr << ' ' << head;
    debug_cerr(tail...);
}

// cin/cout setup
struct IoSetup{
    IoSetup(){
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} iosetup;

// AtCoder Beginner Contest 143

typedef long long ll;
typedef pair<int, int> pa;
typedef pair<pa, int> ppa;
int N, M, L, Q;

struct edge{
    int to, cost;
    edge(int t, int c) : to(t) , cost(c) {}
};

vector<edge> G[310];
pa dist[310][310];

int main(){

    cin >> N >> M >> L;
    rep(i, M){
        int a, b, c;
        cin >> a >> b >> c;
        if(c > L)continue;
        a--; b--;
        G[a].push_back(edge(b, c));
        G[b].push_back(edge(a, c));
    }

    rep(start, N){
        priority_queue<ppa, vector<ppa>, greater<ppa>> que;
        rep(i, N)dist[start][i] = make_pair(2000000000, 2000000000);
        dist[start][start] = make_pair(0, 0);
        que.push(ppa(dist[start][start], start));
        while(!que.empty()){
            ppa now = que.top();
            que.pop();
            pa d = now.first;
            int v = now.second;
            if(d > dist[start][v])continue;
            for(edge e : G[v]){
                pa tmp;
                if(d.second + e.cost > L)tmp = pa(d.first + 1, e.cost);
                else tmp = pa(d.first, d.second + e.cost);
                if(chmin(dist[start][e.to], tmp)){
                    que.push(ppa(dist[start][e.to], e.to));
                }
            }
        }
    }

    cin >> Q;
    rep(i, Q){
        int s, t;
        cin >> s >> t;
        s--; t--;
        pa p = dist[s][t];
        if(p.first >= 2000000000)cout << -1 << endl;
        else cout << p.first << endl;
    }

}


Measured memory_bytes: 3020
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;}
ll LCM(ll c,ll d){return c/GCD(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
V<int> dy={-1,0,1,0},dx={0,-1,0,1};
int main(){
 ll h,w,k;
 cin>>h>>w>>k;
 V<string> s(h);
 for(int i=0;i<h;i++)cin>>s[i];
 int sy=0,sx=0;
 for(int i=0;i<h;i++){
   for(int j=0;j<w;j++){
     if(s[i][j]=='S')sy=i,sx=j;
   }
 }
 V<V<ll>> d(h,V<ll>(w,inf));
 d[sy][sx]=0;
 queue<P> q,tmp;
 q.emplace(sy,sx);
 while(q.size()){
   int y=q.front().fi,x=q.front().se;
   q.pop();
   for(int i=0;i<4;i++){
     int ny=y+dy[i],nx=x+dx[i];
     if(ny<0||ny>=h||nx<0||nx>=w){
       cout<<1<<"\n";
       return 0;
     }
     if(s[ny][nx]!='#'&&k>=d[y][x]+1){
        if(d[ny][nx]>d[y][x]+1){
          d[ny][nx]=d[y][x]+1;
          q.emplace(ny,nx);
        }
     }
   }
 }
 for(int i=0;i<h;i++){
   for(int j=0;j<w;j++){
     if(d[i][j]<=k){
       q.emplace(i,j);
       d[i][j]=0;
     }
   }
 }
 ll ans=inf;
  while(q.size()){
   int y=q.front().fi,x=q.front().se;
   q.pop();
   for(int i=0;i<4;i++){
     int ny=y+dy[i],nx=x+dx[i];
     if(ny<0||ny>=h||nx<0||nx>=w){
       chmin(ans,(d[y][x]+k-1)/k+1);
       continue;
     }
    if(d[ny][nx]>d[y][x]+1){
          d[ny][nx]=d[y][x]+1;
          q.emplace(ny,nx);
        }
   }
 }
 cout<<ans<<"\n";
}


Measured memory_bytes: 9856
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
int main(){
    ll k;
    cin>>k;
    cout<<50<<"\n";
    if(k%50==0) rep(i,50) cout<<k/50+50-1<<" ";
    else{
        rep(i,k%50) cout<<k/50+50+51-k%50-1<<" ";
        rep(i,50-k%50) cout<<k/50+50-k%50-1<<" ";
    }
    cout<<"\n";
}

Measured memory_bytes: 256
protocol InitFromString {
    init?(_ str: String)
}

extension Int: InitFromString {}
extension Int8: InitFromString {}
extension Int16: InitFromString {}
extension Int32: InitFromString {}
extension Int64: InitFromString {}
extension String: InitFromString {}

func input<T: InitFromString>() -> [T] {
    readLine()!.split(separator: " ").map(String.init).compactMap(T.init)
}

let inp: Int64 = input()[0]
print((1...inp).filter { $0 % 3 != 0 && $0 % 5 != 0 }.reduce(0, +))


Measured memory_bytes: 11520
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>

int main(void){
    std::string a,b,c;
    std::cin >> a >> b >> c;
     transform(a.begin(), a.end(), a.begin(), toupper);

     transform(b.begin(), b.end(), b.begin(), toupper);


     transform(c.begin(), c.end(), c.begin(), toupper);
    std::cout << a[0] << b[0] << c[0];
    return 0;
}




Measured memory_bytes: 256
N = int(input())
sentense = input()
count_1 = sentense.count("R")*sentense.count("G")*sentense.count("B")
count_1_and_not_2 = 0
for i in range(N):
    for j in range(i+1, N):
        k = (j-i)+j
        if k >= N:
            break
        if sentense[i] != sentense[j] and sentense[j] != sentense[k] and sentense[k] != sentense[i]:
            count_1_and_not_2 += 1

print(count_1-count_1_and_not_2)

Measured memory_bytes: 9200
#include<bits/stdc++.h>
using namespace std;
#define pb          push_back
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define endl        "\n"
#define fast        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int         long long int
#define mod         1000000007
#define test        int t;cin>>t;while(t--)
#define REP(i,a,b)  for(int i=a,i<=b;i++)
#define MAXN        300001


vi adj1[MAXN],adj2[MAXN];
int32_t main()
{
	int h,w,m;
	cin>>h>>w>>m;
	int u,v;
	set<pair<int,int>> s;
	for(int i=0;i<m;i++){
		cin>>u>>v;
		adj1[u].pb(v);
		adj2[v].pb(u);
		s.insert({u,v});
	}

	int mx1=0,mx2=0;
	int idx1=0,idx2=0;
	for(int i=1;i<=h;i++){
		if((int)adj1[i].size() > mx1){
			mx1=max(mx1,(int)adj1[i].size());
			idx1=i;
		}
	}

	int res=INT_MIN;
	for(int i=1;i<=w;i++){
		int ans;
		if((int)adj2[i].size() >= mx2){
			mx2=max(mx2,(int)adj2[i].size());
			idx2=i;
			if(s.count({idx1,idx2})){
				ans=mx1+mx2-1;
			}
			else
				ans=mx1+mx2;
		}
		res=max(ans,res);
	}

	mx1=0,mx2=0;
	idx1=0,idx2=0;

	for(int i=1;i<=w;i++){
		if((int)adj2[i].size() > mx1){
			mx1=max(mx1,(int)adj2[i].size());
			idx1=i;
		}
	}

	for(int i=1;i<=h;i++){
		int ans;
		if((int)adj1[i].size() >= mx2){
			mx2=max(mx2,(int)adj1[i].size());
			idx2=i;
			if(s.count({idx2,idx1})){
				ans=mx1+mx2-1;
			}
			else
				ans=mx1+mx2;
		}
		res=max(ans,res);
	}

	cout<<res<<endl;

	return 0;
}

Measured memory_bytes: 55128
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;
import java.util.LinkedList;

public class Main {
	public static void main(String[] args) {
		new Main();
	}

	public Main() {
		FasterScanner sc = new FasterScanner(System.in);

		int k = sc.nextInt();
		LinkedList<Long> list = new LinkedList<Long>();
		for (long i = 1; i <= 9; i++) {
			list.add(i);
		}
		long val = -1;
		while(k > 0) {
			val = list.getFirst();
			list.removeFirst();
			if (val % 10 != 0) {
				list.add(10*val + val%10 - 1);
			}
			list.add(10*val + val%10);
			if (val % 10 != 9) {
				list.add(10*val + val%10 + 1);
			}
			k--;
		}
		System.out.println(val);
				
		sc.close();
	}
	
	class FasterScanner {
		private InputStream mIs;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public FasterScanner() {
			this(System.in);
		}

		public FasterScanner(InputStream is) {
			mIs = is;
		}

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = mIs.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}

		public String nextString() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		public void close() {
			try {
				mIs.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
}


Measured memory_bytes: 33748
n, p = map(int, input().split())
a = list(map(int, input().split()))
odd = []
even = []

for i in a:
    if i & 1:
        odd.append(i)
    else:
        even.append(i)
n_odd = len(odd)
n_even = len(even)


def nCr(n, r):
    r = min(r, n - r)
    ans = 1
    denom = 1
    for i in range(1, r + 1):
        ans *= n-(i-1)
        denom *= i
    return ans//denom


# P=0の場合、evenからは任意、oddからは2の倍数個取り出す
if p == 0:
    ans = 2 ** n_even
    tmp = 0
    for i in range(0, n_odd + 1, 2):
        tmp += nCr(n_odd, i)
    ans *= tmp
else:  # P=1の場合、evenは任意、oddからは奇数個取り出す
    ans = 2 ** n_even
    tmp = 0
    for i in range(1, n_odd + 1, 2):
        tmp += nCr(n_odd, i)
    ans *= tmp

print(ans)


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

#define   ll     long long int

int main( )
{
    int h, w, i, j, k;
    string grid[55];
    cin >> h >> w;
    for (i = 0; i < h; i++) {
        cin >> grid[i];
    }
    int c = 0;
    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            if (grid[i][j] == '#' || grid[i][j] == 'c') {
                //cout << i << ' ' << j << '\n';
                if (i + 1 < h && (grid[i + 1][j] == '#' || grid[i + 1][j] == 'c')) {
                    grid[i][j] = 'c';
                    grid[i + 1][j] = 'c';
                }
                if (j + 1 < w && (grid[i][j + 1] == '#' || grid[i][j + 1] == 'c')) {
                    grid[i][j] = 'c';
                    grid[i][j + 1] = 'c';
                }
            }
            if (grid[i][j] == '#') c++;
        }
    }
    if (c == 0) {
        cout << "Yes\n";
    }
    else {
        cout << "No\n";
    }
    return 0;
}



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

using namespace std;

const int maxn = 1e5+10;

int a[maxn], b[maxn], c[maxn];

int dp[maxn][3];

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

	for (int i = 1; i <= n; i++)
		cin >> a[i] >> b[i] >> c[i];

	for (int i = 1; i <= n; i++)
	{
		dp[i][0] = a[i]+max(dp[i-1][1], dp[i-1][2]);
		dp[i][1] = b[i]+max(dp[i-1][0], dp[i-1][2]);
		dp[i][2] = c[i]+max(dp[i-1][0], dp[i-1][1]);
	}

	cout << max({dp[n][0], dp[n][1], dp[n][2]}) << "\n";
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long ul;
// for文短縮類
#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPD(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i <= (ll)(b); i++)
#define FORD(i, a, b) for (ll i = a; i >= (ll)(b); i--)
// iteratorのbeginとendをまとめて渡す
#define ALL(x) (x).begin(), (x).end()
//略
#define PB push_back  // vectorヘの挿入
#define MP make_pair  // pairのコンストラクタ
#define F first       // pairの一つ目の要素
#define S second      // pairの二つ目の要素
//出力
#define COUT(x) cout << (x) << endl
#define SCOUT(x) cout << (x) << " "
#define ENDL cout << endl
/************ Combination wtih MOD ************
const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
// preprocess for some tables
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;
  }
}
// combination
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;
}
*******************************************************/
/********** UnionFind ***************
struct UnionFInd {
vector<ll> par;
UnionFInd(ll N) : par(N) {
for (ll i = 0; i < N; i++) {
par[i] = i;
}
}
ll root(ll x) {
if (par[x] == x) return x;
return par[x] = root(par[x]);
}
void unite(ll x, ll y) {
ll rx = root(x);
ll ry = root(y);
if (rx == ry) return;
par[rx] = par[ry];
}
bool same(ll x, ll y) {
ll rx = root(x);
ll ry = root(y);
return rx == ry;
}
};
*************************************/
int main(int argc, char *argv[]) {
  // input高速化。cinとcoutの結合解除。scanfとprintfは使えない。
  cin.tie(0);
  ios_base::sync_with_stdio(0);

  ll n;
  cin >> n;
  vector<ll> a(n + 1);

  REP(i, n+1){
      if(i == 0){
          continue;
      }
      ll ai;
      cin >> ai;
      a[i] = ai;
  }

  ll ans = 0;
  REP(i, n+1){
       if(i == 0){
          continue;
      }
      if(i % 2 == 1 && a[i] % 2 == 1){
          ans += 1;
      }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3612
import math
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
mod = 10**9 + 7
def mod_factorial(n):
    ans = 1
    while n >= 2:
        ans  = (ans * n) % mod
        n -= 1
    return ans
if abs(n - m) == 1:
    print((mod_factorial(n) * mod_factorial(m)) % mod)
elif abs(n - m) == 0:
    print((mod_factorial(n) * mod_factorial(m) * 2) % mod)
else:
    print(0)

Measured memory_bytes: 3064
#include <stdio.h>


int wake(int p[],int N,int C)
{
	int i;
	int total=0;
	int amari ;
	int kaesi;

	for (i = 0; i < C; i++)
	{
		total = p[i] + total;
	}
	
	kaesi = total / (N+1);

	if (total%(N+1))
	{
		amari = 1;
	}
	else
	{
		amari = 0;
	}

	return kaesi + amari;
	
}





int main()
{
	int N, C;
	int p[100];
	int i;

	scanf("%d %d", &N, &C);

	for (i = 0; i < C; i++)
	{
		scanf("%d",&p[i]);
	}

	printf("%d\n", wake(p, N, C));

	return 0;




}







Measured memory_bytes: 2100
# まずワーシャルフロイドの表を作る
# 元の表で頂点A-Bを結ぶ距離が、ワーシャルフロイドの表で短縮されていたら、その辺は使わないで良いことになる
# この個数を数える

import sys
readline = sys.stdin.readline

import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse.csgraph import csgraph_from_dense

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

INF = 10 ** 9
G = [[INF] * N for i in range(N)]
for i in range(M):
  a,b,c = map(int,readline().split())
  G[a-1][b-1] = c
  G[b-1][a-1] = c

d = csgraph_from_dense(G, null_value=10**9)
d = floyd_warshall(d)

ans = 0
for a in range(N-1):
  for b in range(a + 1,N):
    if G[a][b] == INF:
      continue
    if G[a][b] > d[a][b]:
      ans += 1
      
print(ans)

Measured memory_bytes: 28028
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,n) for (int64_t i=0; i<(n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()




int main(){
    int n; cin>>n;
    if(n>=30) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int H,W;
  cin >> H >> W;
  
  char s[60][60] = {' '};
  for (int i=1;i<=H;i++) {
    for (int j=1;j<=W;j++) {
      cin >> s[i+1][j+1];
    }
  }
  //for (int i=1;i<=H;i++) {
  //  for (int j=1;j<=W;j++) {
  //    cout << s[i][j];
  //  }
  //  cout << endl;
  //}
    
  const char brack = '#';
  int cnt = 0;
  for (int i=1;i<=H;i++) {
    for (int j=1;j<=W;j++) {
      if ((s[i][j]==brack) &&
          (s[i-1][j  ]!=brack) &&
          (s[i+1][j  ]!=brack) && 
          (s[i  ][j-1]!=brack) &&
          (s[i  ][j+1]!=brack)   ) cnt+=1;
    }
  }
  if (cnt==0) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
 
  return 0;
}

Measured memory_bytes: 256
from functools import reduce

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

mods = []
current_sum_mod = 0


reduce(lambda s, x: (s + x)%M, A)

for a in A:
  current_sum_mod += a
  current_sum_mod %= M
  mods.append(current_sum_mod)

pairs = {}

for i, mod in enumerate(mods):
  if mod in pairs:
    pairs[mod].append(i)
  else:
    pairs[mod] = [i]


res = 0

for k, v in pairs.items():
  n = len(v)

  if k == 0:
    res += n

  res += (n*(n-1)//2)

print(res)


Measured memory_bytes: 24340
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;


struct Item
{
	int w;
	
	int v;
};
Item items[100010];

int n, w;

long long fv[100010];	//物品到达价值i时，可取得的最小重量 


bool compare(const Item &a, const Item &b)
{
	if (a.w == b.w)
		return a.v > b.v;
	else
		return a.w < b.w;
}

int main()
{
	scanf("%d%d", &n, &w);
	
	for (int i = 1 ; i <= n ; i++)
		scanf("%d%d", &(items[i].w), &(items[i].v));
		
	sort(items + 1, items + n + 1, compare);
	fv[0] = 0;
	
	for (int i = n * 1000 ; i > 0 ; i--)
		fv[i] = -1;
		
	long long maxValue = 0;
	long long newMaxValue;
	
	for (int i = 1 ; i <= n ; i++)
	{
		newMaxValue = -1;
		for (int j = maxValue ; j >= 0 ; j--)
		{
			if (fv[j] == -1)
				continue;
			
			long long curW = fv[j] + items[i].w;
			long long curV = j + items[i].v;
			
			if (curW > w)
				continue;
				
			if (fv[curV] == -1 || fv[curV] > curW)
			{
				fv[curV] = curW;
				
				if (curV > newMaxValue)
					newMaxValue = curV;
			}
		}
		
		if (maxValue < newMaxValue)
			maxValue = newMaxValue;
	}
	
	printf("%lld\n", maxValue);
	
	return 0;
}

Measured memory_bytes: 896
import numpy as np
in_list = []
for i in range(2):
    in_list.append(input())
N,S = in_list
N = int(N)

res = 0
for i in range(N-2):
    n = 1
    while True:
        j = i+n
        k = j+n
        if k > N-1: break
        res += (S[i] != S[j] and S[j] != S[k] and S[k] != S[i])
        n += 1
    
    
rgb = S.count("R") * S.count("G") * S.count("B")
print(rgb - res)


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

int main() {
  int N, A, B, C, D;
  cin >> N >> A >> B >> C >> D;
  string S;
  cin >> S;

  for (int i = A; i < C; i++) {
    if (S.at(i-1) == '#' && S.at(i) == '#') {
      cout << "No" << endl;
      return 0;
    }
  }
  for (int i = B; i < D; i++) {
    if (S.at(i-1) == '#' && S.at(i) == '#') {
      cout << "No" << endl;
      return 0;
    }
  }
  if (D < C) {
    for (int i = B; i < D+1; i++) {
      if (S.at(i-2) == '.' && S.at(i-1) == '.' && S.at(i) == '.') {
        cout << "Yes" << endl;
        return 0;
      }
    }
    cout << "No" << endl;
    return 0;
  }
  cout << "Yes" << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
int cnt[31], ans;
int main() {
	int n, m; std::cin >> n >> m;
	for(int i = 1; i <= n; ++i) {
		int k, x; std::cin >> k;
		while(k--) std::cin >> x, ++cnt[x];
	}
	for(int i = 1; i <= m; ++i) if(cnt[i] == n) ++ans;
	std::cout << ans << std::endl;
}

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

int main() {
	long long a[200005];
	long long n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	long long res = a[1]-a[0];
	long min = a[0];
	for(int i=1;i<n;i++){
		res=res<a[i]-min?a[i]-min:res;
		min=min<a[i]?min:a[i];
	} 
	cout<<res<<endl;
	
	return 0;
}

Measured memory_bytes: 4648
/*  -*- coding: utf-8 -*-
 *
 * b.cc: D: Small Multiple
 */

#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_N = 100000;
const int INF = 1 << 30;

/* typedef */

/* global variables */

int dists[MAX_N];

/* subroutines */

/* main */

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

  fill(dists, dists + n, INF);
  dists[1] = 0;

  deque<int> q;
  q.push_back(1);

  while (! q.empty()) {
    int u = q.front(); q.pop_front();
    if (u == 0) break;

    int ud = dists[u], vd = ud + 1;

    int v0 = (u * 10) % n;
    if (dists[v0] > ud) {
      dists[v0] = ud;
      q.push_front(v0);
    }

    int v1 = (u + 1) % n;
    if (dists[v1] > vd) {
      dists[v1] = vd;
      q.push_back(v1);
    }
  }

  printf("%d\n", dists[0] + 1);
  return 0;
}


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

typedef long long ll;
typedef pair<int,int> ii;
#define fore(i,a,b) for(int i=a,ggdem=b;i<ggdem;i++)
#define FIN ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define fst first
#define snd second
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)(a).size())

int main() {FIN;
    string s;
    cin>>s;
    ll b=0,res=0;
    for(char c:s) {
        if(c=='W')res+=b;
        else if (c=='B')b++;
    }
    cout<<res<<endl;
} // refreshg

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

int main()
{
    string S;
    string a = "ABC";
    string b = "ARC";
    cin >> S;
    if(S == a){
        cout << b << endl;
    }else if(S == b){
        cout << a << endl;
    }
}

Measured memory_bytes: 3632
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

int main(){
    int k,x; cin >> k >> x;
    if(k*500 >= x) cout << "Yes" << endl;
    else cout << "No" << endl;
}
    



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

const int mod = 1e9+7;

long long int fac[200010],inv[200010];

long long int mp(long long int a,long long int b){
	a%=mod;
	long long int res=1;
	while(b){
		if(b&1)	res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

long long int C(int a,int b){
	return fac[a]*inv[b]%mod*inv[a-b]%mod;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	long long int n,A,B,tmp;
	cin>>n>>A>>B>>tmp;
	fac[0]=1;
	for(int i=1;i<=200000;i++)
		fac[i]=fac[i-1]*i%mod;
	for(int i=0;i<=200000;i++)
		inv[i]=mp(fac[i],mod-2);
	A=A*mp(100-tmp,mod-2)%mod;
	B=B*mp(100-tmp,mod-2)%mod;
	long long int res=0;
	for(int i=0;i<n;i++){
		res=(res+C(n+i-1,n-1)*mp(A,n)%mod*mp(B,i)%mod*(n+i))%mod;
		res=(res+C(n+i-1,n-1)*mp(B,n)%mod*mp(A,i)%mod*(n+i))%mod;
	}
	res=res*100%mod*mp(100-tmp,mod-2)%mod;
	cout<<res<<endl;

}



Measured memory_bytes: 3328
#include <iostream>

int main() {
  using namespace std;

  int n, a, i, max = 999999999, counter;

  cin >> n;

  for (i = 0; i < n; i += 1) {
    counter = 0;
    cin >> a;
    while (a > 0 && (a % 2 == 0)) {
      a /= 2;
      counter += 1;
    }
    if (max > counter) {
      max = counter;
    }
  }
  cout << max << endl;
  return 0;
}


Measured memory_bytes: 256
//============================================================================
// Name        : hoba.cpp :)
// Author      : (O_O Diab) (Why_not) (el 3AQ)
// Version     :
// Copyright   : please, Don't touch me :(
// Description : problem in C++
// MAIN IDEA   : combinatorics NCR
//============================================================================
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define rw freopen("graphs_as_a_service.txt","r",stdin),freopen("output.txt","w",stdout);
#define pb push_back
#define F first
#define S second
#define pf push_front
#define lp(i,a,b) for (int i=a;i<=(int)b;++i)
#define lp2(i,a,b) for (int i=a;i>=b;--i)
#define f(x) return cout<<x<<"\n",0
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
#define p(x) cout<<#x<<" = { "<<x<<" } \n"
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define EPS 1e-6
// to convert string to number use int a = stoi(string);
// to convert number to string use string s = to_string(int);
#define FAST ios::sync_with_stdio(0),ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define clr(c,x) memset(c,x,sizeof(c));
using namespace __gnu_pbds;
using namespace std;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const int dx[] = { 0, 1, 0, -1, 1, -1, 1, -1 };
const int dy[] = { 1, 0, -1, 0, 1, -1, -1, 1 };
const int N = 1e5 + 10, mod = (int) 1e9 + 7, INF = 0x3f3f3f3f;
vii v[N];
ll e[N] = { }, n;
priority_queue<pll, vll, greater<pll>> pq;
void dijkstra(int node) {
	lp(i,1,n)
		e[i] = 2e16;
	pq.push( { 0, node });
	e[node] = 0;
	while (!pq.empty()) {
		pll a = pq.top();
		pq.pop();
		for (auto u : v[a.S]) {
			if (e[a.S] + u.S < e[u.F]) {
				e[u.F] = e[a.S] + u.S;
				pq.push( { e[u.F], u.F });
			}
		}
	}
}
int main() {
#ifdef ONLINE_JUDGE
	FAST
#endif
	cin >> n;
	lp(i,1,n-1)
	{
		int x, y, c;
		cin >> x >> y >> c;
		v[x].pb( { y, c });
		v[y].pb( { x, c });
	}
	int q, k;
	cin >> q >> k;
	dijkstra(k);
	while (q--) {
		int x, y;
		cin >> x >> y;
		cout << e[x] + e[y] << "\n";
	}
	return 0;
}

Measured memory_bytes: 10096
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        sb.append(sc.next());
        do {
            sb.deleteCharAt(sb.length() - 1);
            if (sb.length() % 2 != 0) continue;
            String fw = sb.substring(0, (sb.length() / 2) - 1);
            String bw = sb.substring((sb.length() / 2), sb.length() - 1);
            if (fw.equals(bw)) {
                break;
            }
        } while(true);
        System.out.println(sb.length());
    }
}


Measured memory_bytes: 21844
import java.util.Scanner;

public class Main{
 public static void main(String[] args) {
   Scanner kbd =new Scanner(System.in);
    int a=kbd.nextInt();
    int b=kbd.nextInt();
    int h=kbd.nextInt();
    int m=kbd.nextInt();

    double A=h*30+m*0.5;
    double B=m*6;
    double C=0;
    if(A-B>=0){
      C=A-B;
    }else{
      C=B-A;
    }
    if(C>180){
      C=360-C;
    }
    C=Math.toRadians(C);
    double x=b*Math.sin(C)*b*Math.sin(C);
    double y=(b*Math.cos(C)-a)*(b*Math.cos(C)-a);
    System.out.println(Math.sqrt(x+y));
 }
}

Measured memory_bytes: 36116
#include <bits/stdc++.h>
using namespace std;
void fast() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
}
void ran() {
	srand(chrono::steady_clock::now().time_since_epoch().count());
}
long long get_rand() {
	long long a = rand();
	long long b = rand();
	return a * (RAND_MAX + 1ll) + b;
}
void usaco() {
	freopen("problem.in", "r", stdin); 
	freopen("problem.out", "w", stdout);
}
// #define endl '\n'
// #define double long double
#define int long long
// int MOD = 1000 * 1000 * 1000 + 7;
// int MOD = 998244353;

signed main() {

	ran(); fast();
	
	int n;
	cin >> n;
	string s;
	cin >> s;
	int curr = n-1;
	int ops = 0;
	
	for (int i=0; i<n; i++) {
		if (s[i] == 'W') {
			// swap it with a red which is last one
			while (curr > i && s[curr] == 'W') {
				curr--;
			}
			if (curr > i) {
				// cout << i << ' ' << curr << endl;
				ops++;
				swap(s[i], s[curr]);
			}
		}
	}
	cout << ops << endl;
	// cout << s << endl;

}


Measured memory_bytes: 3796
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define N 100001

int x, y, dp[1001][1001];
char g[1001][1001];

int main(){
ios::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL);
        cin >> x>> y;
        for (int i = 0; i < x; i++)
                for (int j = 0; j < y; j++)
                        cin >> g[i][j];
        dp[0][0] = 1;
        for (int i = 1; i < x; i++) {
                if (g[0][i] == '#') dp[0][i] = 0;
                else dp[0][i] = dp[0][i - 1];
                if (g[i][0] == '#') dp[i][0] = 0;
                else dp[i][0] = dp[i - 1][0];
        }
        for (int i = 1; i < x; i++) {
                for (int j = 1; j < y; j++) {
                        if (g[i][j] == '#') { dp[i][j] = 0; continue; }
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                        dp[i][j] %= mod;
                }
        }
        cout << dp[x - 1][y - 1];
return 0;
}


Measured memory_bytes: 5120
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

  def Find_Root(self, x):
    if self.root[x] < 0:
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]

uf = UnionFind(N)
res = [0] * (N + 1)
for _ in range(M):
  u, v = map(int, input().split())
  res[u] -= 1
  res[v] -= 1
  uf.Unite(u, v)
for _ in range(K):
  u, v = map(int, input().split())
  if uf.isSameGroup(u, v):
    res[u] -= 1
    res[v] -= 1
for i in range(1, N + 1):
  res[i] += uf.Count(i) - 1
print(*res[1: ])

Measured memory_bytes: 85168
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

vector<int> KH[300001];
const int AS = 300200;
int dat[2 * AS];
void modify(int p, int value) {
	for (dat[p += AS] += value; p > 1; p >>= 1) dat[p >> 1] = max(dat[p], dat[p ^ 1]);
}
int query(int l, int r) {
	int ret = 0;
	for (l += AS, r += AS; l < r; l >>= 1, r >>= 1) {
		if (l & 1) chmax(ret, dat[l++]);
		if (r & 1) chmax(ret, dat[--r]);
	}
	return ret;
}

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


	int H, W, M;
	cin >> H >> W >> M;

	rep(i, M) {
		int h, w;
		cin >> h >> w;
		KH[h].pb(w);
		modify(w, 1);
	}

	int kotae = 0;
	rep1(i, H) {
		int tmp = KH[i].size();
		for (auto p : KH[i]) {
			modify(p, -1);
		}
		tmp += query(1, W + 1);
		for (auto p : KH[i]) {
			modify(p, 1);
		}
		chmax(kotae, tmp);
	}
	co(kotae);

	Would you please return 0;
}

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

using namespace std;
long double r;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>r;
    long double pi=acos(-1);
    cout<<setprecision(10)<<fixed<<pi*2*r;
    return 0;
}


Measured memory_bytes: 3796
#include <iostream>

using namespace std;

int main(){
	int N,A[210];
	cin >> N;
	for(int i=0;i<N;i++) cin >> A[i];
	
	int count = 0;
	
	while(1){
		bool even = true;
		for(int i=0;i<N;i++){
			if(A[i]%2 == 1) even = false;
		}
		if(!even) break;
		count++;
		for(int i=0;i<N;i++){
			A[i] /= 2;
		}
	}
	cout << count << endl;
	return 0;
}

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

int main(){
    long long n,sum=0;
    cin>>n;
    long long arr[n];
    for(long long i=0;i<n;i++){
        cin>>arr[i];
    }
    for(long long i=0;i<n;i++){
        for(long long j=i+1;j<n;j++){
            sum+=arr[i]*arr[j];
        }
    }
    cout<<sum<<endl;
}

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

void solve()
{
    int x, n;
    cin >> x >> n;

    int a[205];
    fill_n(a, 205, 1);

    int mn = INT_MAX, val;
    for(int i = 0; i<n; i++)
    {
        int c;
        cin >> c;
        a[c]--;
    }

    if(a[x])
    {
        cout << x << endl;
        return ;
    }

    int i = x-1;
    while(a[i]!=1)
    {
        i--;
    }

    int j = x+1;
    while(a[j]!=1)
    {
        j++;
    }
    if(x-i>j-x)
    {
        cout << j << endl;
    }
    else cout << i << endl;

}


int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll t;
    solve();
    return 0;
}


Measured memory_bytes: 3596
#include<bits/stdc++.h>
#define mp    make_pair
#define fi    first
#define se    second
using namespace std;
int n,m,a[55],b[5005],k,l=1,f[55];
pair<int,int> p[55];
void go(){
	while(l<=n&&p[l].fi==0)++l;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%d",a+i),p[i]=mp(a[i],i);
	sort(p+1,p+n+1);
	for(int i=n;i;--i){
		b[++k]=p[i].se;
		--p[i].fi;
	}
	go();
	while(l<=n){
		int o=b[k];
		sort(p+l,p+n+1);
		for(int i=n;i>=l;--i){
			if(p[i].se==o) continue;
			--p[i].fi;
			b[++k]=p[i].se;
		}
		sort(p+l,p+n+1);
		go();
		if(l==n){
			b[++k]=p[n].se;
			break;
		}
	}
	for(int i=k;i;--i)f[b[i]]=i;
	int la=0;
	for(int _=0;_<m;++_){
		int o=0,cnt=0;
		for(int i=1;i<=n;++i){
			if(f[i]>f[o]&&la!=i)o=i;
			if(f[i]==0)++cnt;
		}
		if(cnt||o==0){
			puts("-1");
			return 0;
		}
		la=o;
		int __=f[o];
		memset(f,0,sizeof(f));
		for(int i=k;i>__;--i)f[b[i]]=i;
	}
	printf("%d\n",k);
	for(int i=1;i<k;++i)printf("%d ",b[i]);
	printf("%d\n",b[k]);
	return 0;
}		

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#define nmax_def 110000
#define Cmax_def 2200
#define mod 1000000007
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

int main() {
	ll N;
	cin >> N;
	vl A(N);
	rep(i, N) {
		cin >> A[i];
	}
	vl Asum(3, 0);
	ll ans = 1;
	rep(i, N) {
		if (ans == 0)
			break;
		ll Atmp = A[i];
		ll anstmp = 0;
		rep(j, 3) {
			if (Asum[j] == Atmp) {
				anstmp++;
			}
		}
		ans *= anstmp;
		ans %= mod;
		if (ans == 0)
			break;
		rep(j, 3) {
			if (Asum[j] == Atmp) {
				Asum[j]++;
				break;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#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 = 305;

int n, m, a[MAXN][MAXN], cur[MAXN], cnt[MAXN], st[MAXN], tp;
set < int > s;

inline bool Chk(int mid)
{
	for (int i = 1; i <= m; i ++)
		cnt[i] = 0;
	for (int i = 1; i <= n; i ++)
		cnt[a[i][cur[i] = 1]] ++;
	int mx = 0; s.clear();
	for (int i = 1; i <= m; i ++)
		mx = max(mx, cnt[i]), s.insert(i);
	while (mx > mid && s.size())
	{
		tp = 0;
		for (int i = 1; i <= m; i ++)
			if (cnt[i] > mid)
				st[++ tp] = i;
		for (int i = 1; i <= tp; i ++)
			s.erase(st[i]);
		for (int i = 1; i <= n; i ++)
			for (; cur[i] <= m && s.find(a[i][cur[i]]) == s.end(); cur[i] ++);
		for (int i = 1; i <= m; i ++)
			cnt[i] = 0;
		for (int i = 1; i <= n; i ++)
			cnt[a[i][cur[i]]] ++;
		mx = 0;
		for (int i = 1; i <= m; i ++)
			mx = max(mx, cnt[i]);
	}
	return s.empty();
}

int main()
{
#ifdef wxh010910
	freopen("data.in", "r", stdin);
#endif
	n = Read(), m = Read();
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			a[i][j] = Read();
	int l = 1, r = n, ret = 0;
	while (l <= r)
	{
		int mid = l + r >> 1;
		if (Chk(mid))
			l = mid + 1;
		else
			ret = mid, r = mid - 1;
	}
	return printf("%d\n", ret), 0;
}


Measured memory_bytes: 640
#include<stdio.h>

int a[510][510];
int x[250010],y[250010],xx[250010],yy[250010];
int cnt;
int h,w;

void f(int a,int b,int c,int d){
	if(c>h)return;
	x[cnt]=a;
	y[cnt]=b;
	xx[cnt]=c;
	yy[cnt]=d;
	cnt++;
}
int main(){
	scanf("%d%d",&h,&w);
	for(int i=1;i<=h;i++)for(int j=1;j<=w;j++)scanf("%d",&a[i][j]);
	for(int i=1;i<=h;i++){
		if(i%2){
			for(int j=1;j<w;j++){
				if(a[i][j]%2){
					a[i][j+1]++;
					f(i,j,i,j+1);
				}
			}
			if(a[i][w]%2){
				a[i+1][w]++;
				f(i,w,i+1,w);
			}
		}else{
			for(int j=w;j>1;j--){
				if(a[i][j]%2){
					a[i][j-1]++;
					f(i,j,i,j-1);
				}
			}
			if(a[i][1]%2){
				a[i+1][1]++;
				f(i,1,i+1,1);
			}
		}
	}
	printf("%d\n",cnt);
	for(int i=0;i<cnt;i++)printf("%d %d %d %d\n",x[i],y[i],xx[i],yy[i]);
}

Measured memory_bytes: 5504