akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define vi vector<int>
#define pb(a) push_back(a)
#define all(a) (a).begin(), (a),end()
#define debug(x) cout << "debug " << x << endl;
using namespace std;

int main(){
    string inp;
    while(getline(cin, inp)){
        if(inp.size() == 1 && inp[0] == '.') break;
        string str;
        rep(i,inp.size()){
            if(inp[i] == '(' || inp[i] == ')' || inp[i] == '[' || inp[i] == ']'){
                str+=inp[i];
            }
        }
        while(str.size()){
            string copy = str;
            rep(i,str.size() - 1){
                if((str[i] == '(' && str[i + 1] == ')') || (str[i] == '[' && str[i + 1] == ']')){ 
                    str.erase(i,2);
                    break;
                }
            }
            if(copy == str) break;
        }
        if(str.empty()) cout << "yes" << endl;
        else cout << "no" << endl;
    }
}

Measured memory_bytes: 1200
#include <iostream>
using namespace std;
int main() {
	int N, H, W;
	cin >> N >> H >> W;
	int cnt = 0;
	for (int i = 0; i < N; ++i) {
		int h, w;
		cin >> h >> w;
		if (h >= H && w >= W) {
			++cnt;
		}
	}
	cout << cnt << endl;
	return 0;
}

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

int c[3][3], solve[6];

int main(){
    for(int i = 0; i<9; ++i){
        cin >> c[i/3][i%3];
    }
    solve[0] = 0;
    for(int i = 0; i<3; ++i){
        solve[3+i] = c[0][i];
    }
    solve[1] = c[1][0]-solve[3]; solve[2] = c[2][0]-solve[3];
    //for(auto x : solve)cout << x << endl;
    //cout << endl << endl;
    for(int i = 1; i<3; ++i){
        for(int j = 1; j<3; ++j){
            if(c[i][j] != (solve[i]+solve[j+3])){ cout << "No" << endl; return 0;}
        }
    }
    cout << "Yes" << endl; return 0;
}

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

using namespace std;

void fuckit(){
	cout << "NO\n";
	exit(0);
}

int main(){
	string str;
	cin >> str;
	string S = "AKIHABARA";
	if(str.size() > S.size()) fuckit();
	int ptr = 0;
	for(int i = 0; i < str.size(); ++i){
		if(ptr == S.size()) fuckit();
		if(str[i] == 'A'){
			if(S[ptr] != 'A') fuckit();
			else ++ptr;
		}
		else{
			while(ptr < S.size() && S[ptr] == 'A') ++ptr;
			if(ptr == S.size()) fuckit();
			if(S[ptr] != str[i]) fuckit();
			++ptr;
		}
	}
	if(ptr + 1 < S.size()) fuckit();
	cout << "YES\n";
	return 0;
}


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

#define for_(i,a,b) for(int i=a;i<b;++i)
#define ALL(a) a.begin(),a.end()
#define INIT(a,b) memset(a,b,sizeof(a))
using lint = long long int;

int R, C, K;
lint v[3003][3003];
lint dp[3003][3003][4];

template<typename T> void maxUpdate(T& a, T b) { a = max(a, b); }

int main() {
    cin >> R >> C >> K;
    INIT(v, 0);
    for_(i,0,K) {
        int r, c;
        lint v_tmp;
        cin >> r >> c >> v_tmp;
        v[r - 1][c - 1] = v_tmp;
    }

    INIT(dp, 0);
    dp[0][0][0] = 0;
    dp[0][0][1] = v[0][0];
    for_(r,0,R) for_(c,0,C) for_(k,0,4) {
        // leave
        if (r + 1 < R) maxUpdate(dp[r + 1][c][0], dp[r][c][k]);
        if (c + 1 < C) maxUpdate(dp[r][c + 1][k], dp[r][c][k]);
        // take
        if (r + 1 < R) maxUpdate(dp[r + 1][c][1], dp[r][c][k] + v[r + 1][c]);
        if (c + 1 < C and k + 1 < 4) maxUpdate(dp[r][c + 1][k + 1], dp[r][c][k] + v[r][c + 1]);
    }

    lint ans = 0;
    for_(k,0,4) maxUpdate(ans, dp[R - 1][C - 1][k]);
    cout << ans << endl;
}

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

using namespace std;


const int INF = 1e9 + 5;

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K ;

    cin >> N >> K;

    vector<int> vi(N);

    for(int i = 0; i < N; ++i){
        cin >> vi[i];
    }


    /*

    vector<int> dp(K+1, INF);
    dp[0] = 0;
    cout << "bye" << "\n";

    for(int i = 1; i < N ; ++i){
        
        dp[ i % (K+1)] = INF;
        for(int j = i-1 ; j >= max(i-K, 0); --j ){
            // dp[i % (K +1)] = INF;

            dp[i % (K+1)] = min (dp[i % (K+1)] , abs(vi[i] - vi[j]) + dp[j % (K+1)]);
            // cout << " i is " << i << " and dp of " << i % (K+1) << " is " << dp[i % (K+1)] << "\n";
        }
    }

*/

    vector<int> dp(N,INF);
    dp[0] = 0;

    for(int i = 0; i < N ; ++i){
        
        for(int j = i+1; j <= i+K; ++j){
            if (j < N) {
                dp[j ] =  min(dp[j ]  , abs(vi[i] - vi[j]) + dp[i]);
            }
        }
    }



/*
    
    for(int i : dp){
        cout << i << " ";
    }
    cout << "\n";
*/
    

    cout << dp[ (N-1)] << "\n";
    
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>



#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define all(x) (x).begin(),(x).end()

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 (b<a) { a=b; return 1; } return 0; }

typedef long long ll;

using namespace std;

struct sushi{ll x,c;};

template <class Monoid>
class SegmentTree
{
public:
  using Func = function<Monoid(Monoid, Monoid)>;
  const Func F;
  const Monoid M1;
  ll sz;
  vector<Monoid> seg;

  SegmentTree(ll n,const Func fu, const Monoid &m1): F(fu) , M1(m1) {init(n);}
  void init(ll n)
  {
      sz= 1;
      while (sz < n) sz *= 2;
      seg.assign(sz * 2, M1);
  }
  void update(ll k,const Monoid &x)
  {
    k+=sz;
    seg[k]=x;
    while(k>>=1)
    {
      seg[k]=F(seg[k*2],seg[k*2+1]);
    }
  }
  Monoid query(ll l,ll r)
  {
    Monoid L=M1,R=M1;
    l+=sz;r+=sz;
    for(;l<r;l>>=1,r>>=1)
    {
      if(l&1)L=F(L,seg[l++]);
      if(r&1)R=F(seg[--r],R);
    }
    return F(L,R);
  }
};
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,c;
  cin>>n>>c;
  vector<sushi>l(n+2),r(n+2);
  rep(i,n)
  {
    ll x,v;
    cin>>x>>v;
    l[i+1]={x,v};
    r[n-i]={c-x,v};
  }
  l[n+1]={c,0};
  r[n+1]={c,0};
  l[0]={0,0};
  r[0]={0,0};
  vector<ll>suml(n+3),sumr(n+3);
  rep(i,n+2)
  {
    suml[i+1]=suml[i]+l[i].c;
    sumr[i+1]=sumr[i]+r[i].c;
  }
  SegmentTree<ll> stl(n+3,[](ll a,ll b){return max(a,b);},0),stl2(n+3,[](ll a,ll b){return max(a,b);},0);
  rep(i,n+2)
  {
    stl.update(i,suml[i+1]-l[i].x);
    stl2.update(i,suml[i+1]-2*l[i].x);
  }
  rep(i,n+1);//cout<<stl2.query(i,i+1)<<" ";
  //cout<<endl;

  ll res=0;
  rep(i,n+1)
  {
    ll tr=r[i].x;
    ll id=lower_bound(all(l),(sushi){tr,0},[&](sushi a,sushi b){return a.x<b.x;})-l.begin();
    ll tres=sumr[i+1];
    if(id<=n-i)
    {
      tres+=max(stl2.query(0,id)-tr,stl.query(id,n-i+1)-2*tr);
    }
    else
    {
      tres+=stl2.query(0,n-i+1)-tr;
    }
    chmax(res,tres);
    //cout<<i<<" "<<id<<endl;
    //cout<<sumr[i+1]<<endl;
    //cout<<tres<<endl;
  }
  cout<<res<<endl;


  return 0;

}


Measured memory_bytes: 9088
def q2():
    N = int(input())
    data = {}
    judges = ['AC', 'WA', 'TLE', 'RE']
    for j in judges:
        data[j] = 0

    for i in range(N):
        j = input()
        data[j] += 1

    for j in judges:
        print(f'{j} x {data[j]}')


q2()


Measured memory_bytes: 9136
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cstdlib>
#include <set>
#include <utility>
#include <climits>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>

#define ll long long
#define ull unsigned long long
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	map<ll, int> m;
	cin >> n;
	
	ll res = 0;
	for (int i = 1, a; i <= n; ++i) {
		cin >> a;
		res += m[i - a];
		++m[i + a];
	}
	cout << res;
}

Measured memory_bytes: 26232
A, B, M = map(int, input().split())

price_A = list(map(int, input().split()))
price_B = list(map(int, input().split()))

ans = min(price_A)+min(price_B)

for m in range(M):
  x, y, c = map(int, input().split())
  p1 = price_A[x-1] + price_B[y-1] - c
  if p1 <= ans: ans=p1

print(ans)

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


int main(void) {
  int n;
  cin >> n;
  vector<vector<int>> a(2,vector<int>(n));
  rep(i,2){
    rep(j,n){
      cin >> a.at(i).at(j);
    }
  }
  vector<int> p(n+1,0);
  vector<int> q(n+1,0);
  rep(i,n) {
    p[i+1] = p[i]+a[0][i];
    q[i+1] = q[i]+a[1][i];
  }
  int cnt = 0;
  rep(i,n){
    int t = p[i]+q[n]-q[i-1];
    if (i==0) t += a.at(0).at(0);
      
    cnt = max(cnt,t);
    
  }
  cout << cnt << endl;
  
               
   
}

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

using i64=int64_t;

#define rep(i,x,y) for(i64 i=i64(x),i##_max_for_repmacro=i64(y); i<i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif
 
const int inf=1.01e9;
const i64 inf64=4.01e18;
const double eps=1e-9;
 
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

void solve(){
    string s;
    cin >> s;

    int count[26]={};
    rep(i,0,s.size()) ++count[s[i]-'a'];

    int odd=0;
    rep(i,0,26) if('a'+i!='x' and count[i]%2) ++odd;

    if(odd>1){
        cout << -1 << endl;
        return;
    }

    int l=0,r=s.size()-1,ans=0;
    while(l<=r){
        if(s[l]==s[r]){
            ++l;
            --r;
            continue;
        }
        if(s[l]=='x'){
            ++l;
            ++ans;
            continue;
        }
        if(s[r]=='x'){
            --r;
            ++ans;
            continue;
        }
        cout << -1 << endl;
        return;
    }

    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


Measured memory_bytes: 512
function main(input) {
  let [N, S, K] = input.split("\n");
  [N,K] = [N,K].map(v => parseInt(v));
  console.log(S.replace(new RegExp(`[^${S[K-1]}]`, "g"), "*"));
}
main(require("fs").readFileSync("/dev/stdin", "utf8").trim());


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

using namespace std;

int n, q, k, a[2002], y, sol;

int main()
{
  sol = 2000000000;
  cin >> n >> k >> q;
  for (int i = 1; i <= n; i++)
    cin >> a[i];
  for (int i = 1; i <= n; i++) {
    int x = a[i];
    vector<vector<int> >v;
    for (int j = 1; j <= n; j++) {
      if (a[j] < x) continue;
      vector<int>s;
      while (j <= n && a[j] >= x) {
        s.push_back(a[j]);
        j++;
      }
      sort (s.begin(), s.end());
      if (s.size() >= k)
        v.push_back(s);
    }
    priority_queue<pair<int, int>,  vector<pair<int, int>>, greater<pair<int, int>> >pq;
    int poz[2002];
    memset(poz, 0, sizeof(poz));
    for (int j = 0; j < v.size(); j++) {
      pq.push({v[j][0], j});
    }
    bool ok = 1;
    for (int j = 1; j <= q; j++) {
      if (pq.empty()) {ok = 0; break;}
      else {
        int p = pq.top().second;
        y = pq.top().first;
        pq.pop();
        if (v[p].size() - poz[p] - 1 >= k) {
          poz[p]++;
          pq.push({v[p][poz[p]], p});
        }
      }
    }
    if (ok)
      sol = min(sol, y - x);
  }
  cout << sol;
  return 0;
}


Measured memory_bytes: 256
if __name__ == '__main__':
    N = int(input())
    A = sorted({i: int(input()) for i in range(N)}.items(), key=lambda x: x[1])
    for index in range(N):
        if not A[-1][0] == index:
            print(A[-1][1])
        else:
            print(A[-2][1])
            
                

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

using namespace std;

const int N=1e6+3;

const double eps=0.000000001;

#define pb push_back
#define all(x) (x).begin(),(x).end()
typedef long long ll;

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

const int inf=1e9,mod=1e9+7;

int n,m,b[N],k,q,u,v,x,y,tc,c,l,r,ans;

char s[N];

void IO(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	#ifndef ONLINE_JUDGE
		freopen("test.txt","r",stdin);
	#endif
}

pair<int,int> a[N];

ll pre[N];

bool cmp(int x,pair<int,int> &a){
    return a.first>x;
}

int main(){
	//IO();
	ll ans=0;
	int D,A;
	scanf("%d%d%d",&n,&D,&A);
	for(int i=0;i<n;i++)
		scanf("%d%d",&a[i].first,&a[i].second);
	sort(a,a+n);
	for(int i=0;i<n;i++){
        if (i)
            pre[i]+=pre[i-1];
        a[i].second-=pre[i];
        if (a[i].second<=0)
            continue;
        int p=upper_bound(a,a+n,a[i].first+D*2,cmp)-a;
        ll rounds=(a[i].second+A-1)/A;
        pre[p]-=(ll)rounds*A;
        pre[i]+=(ll)rounds*A;
        ans+=rounds;
	}
	printf("%lld",ans);
}


Measured memory_bytes: 5888
def euclid(A, B):
    c2 = 0
    for a,b in zip(A,B):
        c2 += (a-b)**2
    return c2**0.5

N, D = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]

cnt = 0
for i in range(N):
    for j in range(i+1,N):
        c = euclid(X[i], X[j])
        if c.is_integer():
            cnt += 1
print(cnt)

Measured memory_bytes: 38384
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>

using namespace std;
using ll =long long;
using vi = vector<int>; 
using vvi = vector<vi>; 
using vl = vector<ll>; 
using vvl = vector<vl>; 
using vs = vector<string>;
using vvs = vector<vs>; 
using vc = vector<char>;
using vvc = vector<vc>; 
using vb = vector<bool>;
using vvb = vector<vb>; 

#define rep(i,n) ;for( int i =0; i < n ; i ++)
#define all(a) a.begin(),a.end()
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i=a;i<b;i++)
#define pri(a)  printf("%.14lf\n",a);
#define sz(a) ((int)a.size())
#define MOD 1000000007
bool is_int_lround(double x){
  return std::lround(x)==x;
}
ll keta(ll x){
  ll n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}

ll conbi(int n,int m){
  
  cin>>n>>m;
  vector<ll> a(100);
  a[0] =1;
  for(int i=0;i<14;i++){
    a[i+1]=a[i]*(i+1);
  }
  return a[n] /(a[m] *a[n-m]);
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;//繰り返し二乗法
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll kaijoMOD(ll x){
  ll z=1;
  if(x==0){
    return 1;
  }
  while(x>0){
    z *=x;
    z %=MOD;
    x--;
  }
  return z;
}
ll div_num(ll n){
  vl div(n+1,1);
  for(ll i=2;i*i<=n;i++){ 
    while(n%i==0){
      n /=i;
      div[i]++;
    }
  }
  if(n!=1)div[n]++;
  ll num=1;
  for(ll i=0;i<=n;i++){
    num*=div[i];
  }
  return num;
}
vector<ll> divisor(ll n) {
  vector<ll> ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

int keta_wa(int x){
  int tot=0;
  while(x>0){
    tot +=x%10;
    x/=10;
  }
  return tot;
}
long long lopow(ll a, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a ;
        a = a * a ;
        n >>= 1;
    }
    return res;
}


//vc alp ={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
//vc Alp ={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
//cout<<""<<endl;

int main(){
ll X;cin>>X;
  for(ll x =-500;x<=500;x++){
    for(ll y=-500;y<=500;y++){
      if(x*x*x*x*x -y*y*y*y*y==X){
        cout<< x <<" "<<y<<endl;
        return 0;
      }
      
    }
  }
  
  
}






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

namespace ABC134
{
    class Program
    {
        static void Main(string[] args)
        {
            var r = int.Parse(Console.ReadLine());
            Console.WriteLine(3 * r * r);
        }
    }
}


Measured memory_bytes: 13140
#include <stdio.h>
#include <iostream>
#include <vector>
#include <assert.h>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <sstream>
#include <memory.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef long long ll;
int main()
{
	int n;
	scanf("%d", &n);
	vector<int> v(n);
	ll s = 0;
	for (int i = 0; i < n; ++i) {
		scanf("%d", &v[i]);
		s += v[i];
	}
	ll res = 1e18;
	ll cur = 0;
	for (int i = 0; i + 1 < n; ++i) {
		cur += v[i];
		res = min(res, abs(cur - (s - cur)));
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define mp make_pair
#define pque priority_queue
#define endl '\n'
typedef vector <int> 	vi;
typedef pair <int, int> ii;
typedef vector <vi > 	vvi;
typedef vector <ii > 	vii;

const int N = 1e5 + 5, mod = 1e9 + 7, inf = 1e18 + 7;

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, a, b;
	cin >> n;
	if (n == 1) cout << "Hello World";
	else{
	    cin >> a >> b;
	    cout << a + b;
	}
}

/*
INPUT:


OUTPUT:


*/

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include <algorithm> 
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
#define ll long long
#define rep(i,n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define F first
#define S second
#define pb push_back
#define pu push
#define COUT(x) cout<<(x)<<"\n"
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,vector<ll>,greater<ll>>
#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define mp make_pair
#define sz(x) (ll)(x).size()
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MOD = 1000000007LL;
const ll INF = 1LL << 60;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vstr = vector<string>;
using vc = vector<char>;
using vvc = vector<vc>;
template<class T> inline bool chmax(T& a, T b) { 
 if (a < b) { a = b; return true; } return false; 
}
template<class T> inline bool chmin(T& a, T b) {
 if (a > b) { a = b; return true; } return false; 
}
ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
int main(){
  ll n;
  cin>>n;
  vll a(n);
  rep(i,n) cin>>a[i];
  sort(all(a));
  ll ans=0;
  vll b(1000001);
  rep(i,n){
    if(i){
      if(a[i]==a[i-1]) continue;
    }
    if(b[a[i]]==0) {
      ans++;
      if(i+1<n){
        if(a[i]==a[i+1]) ans--;
      }
    }
    ll now=1;
    while(now*a[i]<1000001){
      b[now*a[i]]=1;
      now++;
    }
  }
  COUT(ans);
}


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

int p, q, a;

//cèÌXebv, »ÝÌóµ, ßÌoHîñ
//cèÌPÊª, Iñ¾ªê(²×nßél), ±±ÜÅÌa(ªq,ªê)
int solve(int n, int s, int fracC, int fracM) {
	int count = 0;
	for (int i = s; fracM * i <= a; i++) {//ð1:PÊªÌªêÌÏªaÈº
		//EÓÌa(±±ÜÅÌªÌa)ª¶Ó(âèÌª)ð´¦êÎ»ÌTõÍÅ¿Øé
		// p/q = fracC/fracM + 1 / i
		// ÊªµÄ
		int left = p * fracM * i;
		int right = fracC * q * i + q * fracM;
		if (left < right) continue;
		if (left == right) {//ðÌêÂð­©I
			count++;
			continue;
		}
		if (n != 1) {
			count += solve(n - 1, i, fracC * i + fracM, fracM * i);
		}
	}
	return count;
}

int main() {
	while (1) {
		int n;
		cin >> p >> q >> a >> n;
		if (!(p || q || a || n)) break;
		cout << solve(n, 1, 0, 1) << endl;
	}
	return 0;
}

Measured memory_bytes: 868
#include<stdio.h>

int main(void)
{
    
    int n, max, min, diff, j, i;
    
    scanf("%d", &n);
    
    int R[n];
    
    for(i =0 ; i<n; i++)
    {
        scanf("%d", &R[i]);
    }
    
    max = R[1]-R[0];
    min = R[0];
    
    for(j=1; j<n; j++)
    {
        diff = R[j]-min;
        
       if(max < diff)
       {
           max =diff;
       }
       
       if(min > R[j])
       {
           min = R[j];
       }
       
    }
    
    printf("%d\n", max);
    
    return 0;
    
}


Measured memory_bytes: 2572
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 100001;
string num;
int dp[10001][101][2];
int D;
int solve(int in, int rem, bool tight){
  if(in == num.size())
    return rem == 0 ? 1 : 0;
  int& res = dp[in][rem][tight];
  if(res != -1)
    return res;
  res = 0;

  for(int i = 0;i <= 9;i++){
    if(tight && i > num[in] - '0')
      break;

    res = (1ll * res + solve(in + 1, (rem + i) % D, tight && num[in] - '0' == i)) % MOD;
  }
  return res;
}

int main()
{
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
  cin >> num >> D;
  memset(dp, -1, sizeof(dp));
  cout << (solve(0, 0, 1) - 1 + MOD) % MOD;
  return 0;
}



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

int main() {
  
  int K, N, ans;
  cin >> K >> N;
  vector<int> dif(N);
  
  for (int i=0; i<N; i++) cin >> dif.at(i);

  ans=K-dif.at(N-1)+dif.at(0);
  
  for (int i=1; i<N; i++) {
    ans=max(ans,dif.at(i)-dif.at(i-1));
  }
  
  ans=K-ans;
  cout << ans << endl;
}

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

int main(){
    ll N,D; cin>>N>>D;
    ll ans=0;
    for (ll i = 0; i < N; i++){
        ll x,y; cin>>x>>y;
        ll dis=x*x+y*y;
        if(D*D>=dis){
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3540
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
int main(){
	int ara[3];
	for(int i= 0; i<3;i++){
		scanf("%d",&ara[i]);
	}
	sort(ara,ara+3);
	int x=0;
	x = abs(ara[0] - ara [1]);
	x+= abs(ara[1] - ara[2]);
	printf("%d\n",x);
	return 0;



}

Measured memory_bytes: 256
st1 = input()
st2 = input()
key1 = list(st1)
key2 = list(st2)

def az_count(s):
	ss = []
	ss.append(s.count('a'))
	ss.append(s.count('b'))
	ss.append(s.count('c'))
	ss.append(s.count('d'))
	ss.append(s.count('e'))
	ss.append(s.count('f'))
	ss.append(s.count('g'))
	ss.append(s.count('h'))
	ss.append(s.count('i'))
	ss.append(s.count('j'))
	ss.append(s.count('k'))
	ss.append(s.count('l'))
	ss.append(s.count('n'))
	ss.append(s.count('m'))
	ss.append(s.count('o'))
	ss.append(s.count('p'))
	ss.append(s.count('q'))
	ss.append(s.count('r'))
	ss.append(s.count('s'))
	ss.append(s.count('t'))
	ss.append(s.count('u'))
	ss.append(s.count('v'))
	ss.append(s.count('w'))
	ss.append(s.count('x'))
	ss.append(s.count('y'))
	ss.append(s.count('z'))
	return ss

t = az_count(key1)
t1 = az_count(key2)

t.sort()
t1.sort()
if t == t1:
	print("Yes")
else:
	print("No")

Measured memory_bytes: 6960
#include <iostream>

using namespace std;

int main()
{
    long int a, b, x;
    cin >> a >> b >> x;
    
    long int ans = 0;
    if( a % x != 0 ) a += x - (a % x);
    if( b % x != 0 ) b -= (b % x);
    ans = b/x - a/x + 1;
    
    if( ans < 0 ) cout << 0 << endl;
    else cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 256
import sys
#input = sys.stdin.readline

def main():
    s=list(input())
    n=len(s)
    ans='Yes'
    for i in range((n-1)//2):
        if s[i]!=s[n-1-i]:
            ans='No'
            break
        if s[i]!=s[(n-1)//2-1-i]:
            ans='No'
            break
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m; i<n; i++)
#define co(n) cout << n << endl
using namespace std;
int main(){
  int a, b;
  cin >> a >> b;
  if((a+b)%2==1) co((a+b)/2+1);
  else co((a+b)/2);
  
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int solve(int A[]);
int min(int a,int b);
void sort(int B[]);
#define MAX 10000
int A[MAX],B[MAX],T[MAX+1];
int n,s;

int main(void){
	int i;
	scanf("%d",&n);
	int A[n];
	s=MAX;
	for(i=0;i<n;i++){
		scanf("%d",&A[i]);
		s=min(s,A[i]);
	}
	
	int ans=solve(A);
	
	printf("%d\n",ans);
	return 0;
}


int solve(int A[]){
	
	int ans=0;
	int V[MAX];
	for(int i=0;i<n;i++){
		B[i]=A[i];
		V[i]=0;
	}
	
	sort(B);
	
	for(int i=0;i<n;i++){
		T[B[i]]=i;
	}
	for(int i=0;i<n;i++){
		if(V[i]==1){
			continue;
		}
		int cur=i;
		int S=0;
		int m=MAX;
		int an=0;
		
		while(1){
			V[cur]=1;
			an++;
			int v=A[cur];
			m=min(m,v);
			S+=v;
			cur=T[v];
			if(V[cur]){
				break; 
			}
		}
		ans+=min(S+(an-2)*m,m+S+(an+1)*s);
		
	}
	
	return ans;
	
}

int min(int a,int b){
    if(a<b){
    	return a;
    }
    return b;
}

void sort(int A[]){
	int f=1;
	int tmp;
	while(f==1){
		f = 0;
		for(int j=n-1;j>=1;j--){
			if(A[j]<B[j-1]){
				tmp=A[j-1];
				A[j-1]=A[j];
				A[j]=tmp;
				f=1;
			}
		}
	}
}


Measured memory_bytes: 2144
S = [[i for i in input()] for j in range(3)]
S_sum = len(S[0])+len(S[1])+len(S[2])
turn_num = ["a", "b", "c"]

turn = "a"
for i in range(S_sum):
    idx = turn_num.index(turn)
    if len(S[idx]) == 0:
        if turn == "a":
            print("A")
        elif turn == "b":
            print("B")
        else:
            print("C")
        break
        
    turn = S[idx].pop(0)

Measured memory_bytes: 3064
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    long long n, m, v, p;
    cin >> n >> m >> v >> p;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end(), greater<long long>());

    int left = 0, right = n;
    while (right - left > 1) {
        int mid = (left + right) / 2;

        long long s = 0;
        for (int i = 0; i < n; i++) {
            if (i < p - 1 || mid <= i) {
                s += m;
            } else {
                s += a[mid] + m - a[i];
            }
        }

        if (a[mid] + m >= a[p - 1] && s >= m * v) {
            left = mid;
        } else {
            right = mid;
        }
    }

    cout << left + 1 << endl;
}


Measured memory_bytes: 1024
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <set>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    vll wh(n+1);
    REP(i,n){
        ll a;
        cin >> a;
        wh[a] = i;
    }
    set<ll> s;
    s.insert(-1);
    s.insert(n);
    ll ans = 0;
    for(ll i = 1;i<=n;i++){
        ll now = wh[i];
        ll r,l;
        auto itr = s.lower_bound(now);
        r = *itr;
        itr--;
        l = *itr;
        ans+= i*(r-now)*(now-l);
        s.insert(now);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 11264
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(), (x).end()
#define PI 3.14159265358979323846264338327950L
using namespace std;
typedef long long ll;
typedef long double ld;
int main() {
    string s,t;
    cin>>s>>t;
    int n=s.size(),ans=0;
    rep(i,n){
        if(s[i]!=t[i]) ans++;
    }
    cout<<ans;
}

Measured memory_bytes: 3832
using System;
using System.Linq;

namespace Structure_and_Class
{
    class Dice_II
    {
        static void Main(string[] args)
        {
            var dice = new Dice2(Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray());
            var q = int.Parse(Console.ReadLine());
            for (int i = 0; i < q; i++)
            {
                var token = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
                dice.ShowRight(token[0], token[1]);
            }
        }
    }

    public class Dice2
    {
        int[] label = new int[6];

        private int[,] rightmap;

        public Dice2(int[] label)
        {
            this.label = label;
        }

        public void ShowRight(int up, int front)
        {
            int upIndex=0;
            int frontIndex=0;
            for (int i = 0; i < label.Length; i++)
            {
                if (label[i] == up) upIndex = i;
                else if (label[i] == front) frontIndex = i;
            }
            rightmap = new int[,]{
                {-1, 2, 4, 1, 3,-1},
                { 3,-1, 0, 5,-1, 2},
                { 1, 5,-1,-1, 0, 4},
                { 4, 0,-1,-1, 5, 1},
                { 2,-1, 5, 0,-1, 3},
                {-1, 3, 1, 4, 2,-1}
            };
            Console.WriteLine(label[rightmap[upIndex, frontIndex]]);
        }
    }
}

Measured memory_bytes: 9600
open System

// prelude
let readStr () = stdin.ReadLine()

let read f () = readStr() |> f
let reads f () = readStr().Split() |> Array.map f

let pair = function
| [|a; b|] -> (a, b)
| _ -> failwith "owatta"

let triple = function
| [|a; b; c|] -> (a, b, c)
| _ -> failwith "owatta"

let readPair f g () =
  let (a,b) = readStr().Split() |> pair
  (f a, g b)

let readTriple f g h () =
  let (a,b,c) = readStr().Split() |> triple
  (f a, g b, h c)

let inc n = n + 1
let dec n = n - 1

let inline flip f a b = f b a
let rec fix f = fun x -> (f (fix f)) x

module Option =
  let getOr defaultValue = function
  | Some x -> x
  | None -> defaultValue

module Array =
  let modify (arr: _ []) i f =
    arr.[i] <- f arr.[i]

module Array2D =
  let modify (arr: _ [,]) i j f =
    arr.[i, j] <- f arr.[i, j]

// start
let [|A; B; C; D|] = reads int ()

let rec takahashi a c = if c<=B then "Yes" else aoki a (c-B)
and aoki a c = if a<=D then "No" else takahashi (a-D) c

takahashi A C |> printfn "%s"

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

using namespace std;

using int64 = long long;

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

  int h, w;
  cin >> h >> w;
  vector<vector<int>> board(h, vector<int>(w));
  for (int y = 0; y < h; y++) {
    string line;
    cin >> line;
    for (int x = 0; x < w; x++) {
      if (line[x] == '#') board[y][x] = 1;
    }
  }

  vector<vector<int>> l_table(h, vector<int>(w));
  vector<vector<int>> r_table(h, vector<int>(w));
  vector<vector<int>> u_table(h, vector<int>(w));
  vector<vector<int>> d_table(h, vector<int>(w));
  for (int y = 0; y < h; y++) {
    for (int x = 0; x < w; x++) {
      if (board[y][x] == 1) l_table[y][x] = 0;
      else if (x > 0) l_table[y][x] = l_table[y][x - 1] + 1;
      else l_table[y][x] = 1;

      if (board[y][x] == 1) u_table[y][x] = 0;
      else if (y > 0) u_table[y][x] = u_table[y - 1][x] + 1;
      else u_table[y][x] = 1;
    }
  }
  for (int y = h - 1; y >=0; y--) {
    for (int x = w - 1; x >= 0; x--) {
      if (board[y][x] == 1) r_table[y][x] = 0;
      else if (x + 1 < w) r_table[y][x] = r_table[y][x + 1] + 1;
      else r_table[y][x] = 1;

      if (board[y][x] == 1) d_table[y][x] = 0;
      else if (y + 1 < h) d_table[y][x] = d_table[y + 1][x] + 1;
      else d_table[y][x] = 1;
    }
  }

  int ans = 0;
  for (int y = 0; y < h; y++) {
    for (int x = 0; x < w; x++) {
      int local = l_table[y][x] + r_table[y][x] + u_table[y][x] + d_table[y][x]
          - 3;
      ans = max(ans, local);
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 78848
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll a, b, n;
  cin >> a >> b >> n;
  ll x = min(n, b - 1);
  cout << a * x / b << endl;
}

Measured memory_bytes: 3600
package main;

import "fmt"

func main() {
	var a, b int
	fmt.Scan(&a, &b)

	if (a <= 0 && b >= 0) {
		fmt.Println("Zero")
	} else if a > 0 && b > 0 {
		fmt.Println("Positive")
	} else {
		if (b - a) % 2 == 1 {
			fmt.Println("Positive")
		} else {
			fmt.Println("Negative")
		}

	}
}

Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
using namespace std;

template<typename A, typename B> bool chmin(A &a, const B &b){ return b < a && (a = b, true); }
template<typename A, typename B> bool chmax(A &a, const B &b){ return a < b && (a = b, true); }

int main(){
  int n,m,i,sum = 0;
  cin >> n >> m;
  int a[m];
  for ( i = 0; i < m; i++){
    cin >> a[i];
    sum += a[i];
  }
  if (0 > n - sum){
    cout << "-1\n";
  }
  else{
    cout << n - sum << '\n';
  }
  return 0;
}

Measured memory_bytes: 3604
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


struct Info{
	void set(int arg_row,int arg_col){
		row = arg_row;
		col = arg_col;
	}
	int row,col;
};

struct Data{
	Data(int arg_row,int arg_col,int arg_cost){
		row = arg_row;
		col = arg_col;
		cost = arg_cost;
	}
	bool operator<(const struct Data &arg) const{
		return cost > arg.cost;
	}
	int row,col,cost;
};

int H,W,N;
int diff_row[4] = {-1,0,0,1},diff_col[4] = {0,-1,1,0};
int min_dist[1000][1000];
char base_map[1000][1001];
Info info[10];

bool rangeCheck(int row,int col){
	if(row >= 0 && row <= H-1 && col >= 0 && col <= W-1)return true;
	else{
		return false;
	}
}

int calc(int goal){

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++)min_dist[row][col] = BIG_NUM;
	}

	min_dist[info[goal-1].row][info[goal-1].col] = 0;

	priority_queue<Data> Q;
	Q.push(Data(info[goal-1].row,info[goal-1].col,0));

	int adj_row,adj_col;

	while(!Q.empty()){

		if(Q.top().row == info[goal].row && Q.top().col == info[goal].col){
			return Q.top().cost;
		}else if(Q.top().cost > min_dist[Q.top().row][Q.top().col]){
			Q.pop();
		}else{

			for(int i = 0; i < 4; i++){
				adj_row = Q.top().row+diff_row[i];
				adj_col = Q.top().col+diff_col[i];

				if(rangeCheck(adj_row,adj_col) == false || base_map[adj_row][adj_col] == 'X')continue;

				if(min_dist[adj_row][adj_col] > Q.top().cost+1){
					min_dist[adj_row][adj_col] = Q.top().cost+1;
					Q.push(Data(adj_row,adj_col,min_dist[adj_row][adj_col]));
				}
			}

			Q.pop();
		}
	}

}

int main(){

	scanf("%d %d %d",&H,&W,&N);

	for(int row = 0; row < H; row++){
		scanf("%s",base_map[row]);
		for(int col = 0; col < W; col++){
			if(base_map[row][col] >= '1' && base_map[row][col] <= '9'){
				info[base_map[row][col]-'0'].set(row,col);
			}else if(base_map[row][col] == 'S'){
				info[0].set(row,col);
			}
		}
	}

	int ans = 0;

	for(int i = 1; i <= N; i++)ans += calc(i);

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

	return 0;
}



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

int main() {
  int n, k;
  cin >> n >> k;
  int r, s, p;
  cin >> r >> s >> p;

  vector<char> t(n);
  rep(i, n) cin >> t[i];

  for (int i = k; i < n; i++) {
    if (t[i] == t[i - k]) t[i] = 'x';
  }

  ll ans = 0;
  rep(i, n) {
    switch (t[i]) {
      case 'r':
        ans += p;
        break;
      case 's':
        ans += r;
        break;
      case 'p':
        ans += s;
        break;
    }
  }

  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <complex>

using namespace std;

int compare(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

long comb(int n, int r) {
    long u = 1, d = 1;
    int i;

    for (i = n; i >= n - r + 1; i--) {
        u *= i;
    }
    for (i = 1; i <= r; i++) {
        d *= i;
    }

    return u / d;
}

int main(void) {
    int n;
    int i;
    int a[100000];
    int diff;

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (i = n; i < 100000; i++) a[i] = 1000000000;
    qsort(a, n, sizeof(int), compare);

    diff = a[0];
    for (i = 1; i < n; i++) {
        if (abs(a[n - 1] / 2.0 - a[i - 1]) > abs(a[n - 1] / 2.0 - a[i])) {
            diff = a[i];
        }
    }
    printf("%d %d", a[n - 1], diff);

    return 0;
}

Measured memory_bytes: 892
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val w = sc.nextInt()
    val wv = (0 until n).map { sc.next().toInt() to sc.next().toLong() }
    println(edpcD(n, w, wv))
}

fun edpcD(n: Int, w: Int, wv: List<Pair<Int, Long>>): Long {
    val dp = mutableListOf<LongArray>()
    for (i in 0..n) {
        dp.add(LongArray(w + 1) { 0 })
    }
    for (i in 0 until n) {
        for (j in 1..w) {
            if (j - wv[i].first >= 0) {
                dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - wv[i].first] + wv[i].second)
            }
            dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j])
        }
    }
    return dp[n][w]
}

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

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

    map<char, char> mp;
    mp['A'] = 'T';
    mp['C'] = 'G';
    mp['T'] = 'A';
    mp['G'] = 'C';

    char b;
    cin >> b;
    cout << mp[b] << endl;

    return 0;
}

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

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

 
int main()
{
	cin.tie(0); cout.tie(0);
    int n,m; cin>>n>>m;
	string ar[n];
	for(int i=0;i<n;i++) cin>>ar[i];
	ll dp[n+1][m+1];
	for(int i=0;i<n+1;i++){
		for(int j=0;j<m+1;j++) dp[i][j]=0;
	}
	dp[1][1]=1;
	for(int i=2;i<n+1;i++){
		if(ar[i-1][0]!='#')
			dp[i][1]=dp[i-1][1];
	}
	for(int i=2;i<m+1;i++){
		if(ar[0][i-1]!='#')
			dp[1][i]=dp[1][i-1];
	}
	for(int i=2;i<n+1;i++){
		for(int j=2;j<m+1;j++){
			if(ar[i-1][j-1]=='.'){
				dp[i][j]=dp[i-1][j]%mod+dp[i][j-1]%mod;
				dp[i][j]%=mod;
			}
		}
	}
	cout<<dp[n][m]<<endl;
	return 0;
}


Measured memory_bytes: 9088
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define debug(var) do{cout << #var << " : "; view(var);}while(0)
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
template<class T> void view(T e) {cout << e << endl;}
template<class T> void view(const vector<T> &v) {for(const auto &e : v){cout << e << " ";} cout << endl;}
template<class T> void view(const vector<vector<T>> &vv) {for(const auto &v : vv){view(v);}}
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

vint dx = {1,0,-1,0};
vint dy = {0,1,0,-1};

int main() {
    int h, w; cin >> h >> w;
    vector<string> field(h);
    rep(i,h) cin >> field[i];
    queue<P> q;
    rep(i,h)rep(j,w) if (field[i][j] == '#') q.push(P(i,j));
    int ans = 0;
    while (true) {
        if (q.empty()) {ans--; break;}
        queue<P> tmp_q;
        while (!q.empty()) {
            int x = q.front().second;
            int y = q.front().first;
            q.pop();
            rep(i,4) {
                int n_x = x + dx[i];
                int n_y = y + dy[i];
                if (n_x >= 0 && n_x < w && n_y >= 0 && n_y < h && field[n_y][n_x] != '#') {
                    field[n_y][n_x] = '#';
                    tmp_q.push(P(n_y,n_x));
                }
            }
        }
        swap(q,tmp_q);
        ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 13220
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

C = Counter(A)
S = set(A)

# l = list(combinations())

# for s in S:
#     C[s]
total = 0
for s in S:
    total += C[s] * (C[s] - 1) // 2
# print(total)

for i, a in enumerate(A):
    # before = C[a]
    exc = total - C[a] * (C[a] - 1) // 2
    a_num = C[a] - 1
    now = exc + a_num * (a_num - 1) // 2
    print(now)



Measured memory_bytes: 35024
N = int(input())
A = input().split(' ')
B = input().split(' ')
C = input().split(' ')

total = sum(int(b) for b in B)
pre_ai = -1
for i in range(1, N + 1):
    ai = int(A[i - 1])
    if ai == pre_ai + 1:
        total += int(C[pre_ai - 1])
    pre_ai = ai

print(total)

Measured memory_bytes: 3064
import sys
from collections import Counter

input = sys.stdin.readline
N = int(input())
S = input().strip()

counter = Counter(S)
if len(counter) < 3:
    print(0)
    sys.exit()

exclude = 0
max_w = N // 2
for w in range(1, max_w+1):
    for i in range(N):
        if N <= i + 2*w:
            continue
        if S[i] != S[i+w] and S[i] != S[i+2*w] and S[i+w] != S[i+2*w]:
            exclude += 1
# print(exclude)

print(counter["R"] * counter["G"] * counter["B"] - exclude)

Measured memory_bytes: 74552
#![allow(unused_imports)]
#![allow(unused_variables)]
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(deprecated)]

use std::cell::{Cell, Ref, RefCell, RefMut};
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;
use std::usize;

const MOD_10_9_7: u64 = 1_000_000_007;
const INF: i64 = 1_000_000_000_000;
const MIN_INF: i64 = -1_000_000_000_000;

/// FYI: https://github.com/vain0x/scan-bench
#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($t:ty) =>
        (rl().parse::<$t>().unwrap());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

fn rl() -> String {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    buf.trim_right().to_owned()
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}

#[allow(unused_macros)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn main() {
    let (a, b) = read!(i32, i32);
    println!("{}", max(a + b, max(a - b, a * b)));
}


Measured memory_bytes: 4352
#!/usr/bin/python3

n, m = list(map(int, input().split()))
br = []
r = {}
for i in range(m):
    a, b = input().split()
    br.append((a, b))
    try:
        r[a].append(b)
    except KeyError:
        r[a] = []
        r[a].append(b)
    try:
        r[b].append(a)
    except KeyError:
        r[b] = []
        r[b].append(a)

done = {}

def s(node):
    if done[node] == 1:
        return
    done[node] = 1
    for i in r[node]:
        if node in down and i in down:
            continue
        s(i)

def chk():
    for i in r.keys():
        done[i] = 0
    s('1')
    for i in done.keys():
        if done[i] == 0:
            return False
    return True

nbr = 0
for i in br:
    down = i
    if chk() == False:
        nbr += 1

print(nbr)

Measured memory_bytes: 3064
n,m=gets.split.map(&:to_i)
arrs=Array.new(n){Array.new()}
wa=0
ac=0

m.times do |i|
  x,tmp = gets.chomp.split
  arrs[x.to_i-1] << tmp
end

arrs.each do |arr|
  next if arr.uniq == ["WA"]
  arr.each do |a|
    if a=="AC"
      ac+=1
      break
    else
      wa+=1
    end
  end
end
puts "#{ac} #{wa}"


Measured memory_bytes: 16764
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 端点を間違えないように気をつけること!
#define FOR(i, m, n) for (ll i = (ll)(m); i <= (ll)(n); i++)
#define RFOR(i, m, n) for (ll i = (ll)(m); i >= (ll)(n); i--)
// 割り算をするときは自作関数syou,amariを使うこと!
// 入力は変数を宣言した直後に入れること!

int main()
{
    ll A, B;
    cin >> A >> B;
    cout << max({A + (A - 1), A + B, B + (B - 1)}) << endl;
}

Measured memory_bytes: 256
from itertools import product

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

cakes = []
for _ in range(N):
    cakes.append(list(map(int, input().split())))

def _eval1(op):
    def _eval2(x):
        return eval(''.join(['{}{}'.format(op[i], x[i]) for i in range(3)]))

    return _eval2

answer = 0
for op in product('+-', repeat=3):
    answer = max(answer, sum([abs(sum([cake[j] for cake in sorted(cakes, key=_eval1(op))[:M]])) for j in range(3)]))

print(answer)

Measured memory_bytes: 3400
import statistics

n=int(input())
a = [[int(i) for i in input().split()] for j in range(n)]
min=[i[0] for i in a]
max=[i[1] for i in a]
if n%2==0:
    print(int(statistics.median(max)*2-statistics.median(min)*2)+1)
else:
    print(int(statistics.median(max)-statistics.median(min))+1)
    

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

int main() {
    int N;
    cin>>N;
    int A[N];
    for(int i=0;i<N;++i){
        cin>>A[i];
    }
    bool ans = true;
    for(int i=0;i<N;++i){
        if(A[i]%2==0){
            if(A[i]%3!=0 & A[i]%5!=0)ans = false;
        }
    }
    if(ans)cout<<"APPROVED"<<endl;
    else cout<<"DENIED"<<endl;
}


Measured memory_bytes: 256
use proconio::input;
use proconio::marker::*;
use proconio::fastout;

#[fastout]
fn main() {
  input! {
    h : usize, w : usize, k : usize,
  };
  input! {
    c : [Chars; h],
  };

  let mut res = 0usize;
  for rows in 0..(1 << h) {
    for cols in 0..(1 << w) {
      let mut cnt = 0;
      for i in 0..h {
        if rows & (1 << i) != 0 {
          for j in 0..w {
            if cols & (1 << j) != 0 {
              if c[i][j] == '#' {
                cnt += 1;
              }
            }
          }
        }
      }
      if cnt == k {
        res += 1;
      }
    }
  }
  
  println!("{}", res);
}


Measured memory_bytes: 2180
import math

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

list_coordinates = [ [ int(i) for i in input().split() ] for j in range(N) ]

list_distance_between_pts = []


for i in range(N-1):
	for j in range(i+1, N):
		distance_square = 0
		for l in range(D):
			distance_square += (list_coordinates[i][l] - list_coordinates[j][l])**2
		
		distance = math.sqrt(distance_square)
		
		if distance.is_integer() == True:
			list_distance_between_pts.append(distance)

count_interger_distance = len(list_distance_between_pts)

print(count_interger_distance)

Measured memory_bytes: 3064