akhauriyash/Code-Regression huggingface dataset:
n, m = map(int, input().split())
h = list(map(int, input().split()))
a, b = [], []
for i in range(m):
    ai, bi = map(int, input().split())
    ai, bi = ai-1, bi-1
    a.append(ai)
    b.append(bi)

yoi = [1 for i in range(n)]
for i in range(m):
    ai, bi = a[i], b[i]
    if h[ai] > h[bi]:
        yoi[bi] = 0
    elif h[bi] > h[ai]:
        yoi[ai] = 0
    else:
        yoi[ai], yoi[bi] = 0, 0

print(sum(yoi))

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

int A[3][3];

int is_bingo(){
    int i,j;
    for(i=0;i<3;i++){
        if(A[i][i]!=0)break;
        if(i==2)return 1;
    }
    for(i=0;i<3;i++){
        if(A[i][2-i]!=0)break;
        if(i==2)return 1;
    }
    for(i=0;i<3;i++){
        for(j=0;j<3;j++){
            if(A[i][j]!=0)break;
            if(j==2)return 1;
        }
    }
    for(i=0;i<3;i++){
        for(j=0;j<3;j++){
            if(A[j][i]!=0)break;
            if(j==2)return 1;
        }
    }
    return 0;
}

void mark(int B[],int n){
    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                if(A[j][k]==B[i])A[j][k]=0;
            }
        }
    }
    return;
}

int main(){
    int i,j;
    for(i=0;i<3;i++){
        for(j=0;j<3;j++)scanf("%d",&A[i][j]);
    }
    int n;
    cin>>n;
    int B[n];
    for(i=0;i<n;i++)scanf("%d",&B[i]);
    mark(B,n);
    if(is_bingo())printf("Yes\n");
    else{printf("No\n");}
}

Measured memory_bytes: 3772
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a;
  vector<int> vec(4);
  for(int i=0; i<6; i++) {
    cin >> a;
    vec[a]++;
  }
  bool ans=true;
  for(int i=0; i<=4; i++) {
    if(vec[i]>=3) ans=false;
  }
  if(ans) cout << "YES" << endl;
  else cout << "NO" << endl;
}

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

using namespace std;

const int N = 5e5 + 10;

int n, q;
int a[N], res[N], bit[N];
vector<int> pos[N];
vector<pair<int, int>> query[N];

void update(int x, int p) { for (; x <= n; x += x & -x) bit[x] += p; }
int get(int x) { int ret = 0; for (; x; x -= x & -x) ret += bit[x]; return ret; }

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if (pos[a[i]].empty()) update(i, 1);
        pos[a[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++)
        reverse(pos[i].begin(), pos[i].end());
    for (int i = 1; i <= q; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        query[l].push_back(make_pair(r, i));
    }
    for (int i = 1; i <= n; i++) {
        for (pair<int, int> p: query[i])
            res[p.second] = get(p.first);
        update(pos[a[i]].back(), -1);
        pos[a[i]].pop_back();
        if (pos[a[i]].size()) update(pos[a[i]].back(), 1);
    }
    for (int i = 1; i <= q; i++)
        printf("%d\n", res[i]);
}


Measured memory_bytes: 58600
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;
//const int mod = 998244353;

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

    int n;
    cin >> n;
    vector<int> a(3 * n);
    rep(i, 3 * n) cin >> a[i];
    sort(all(a));
    int ans = 0;
    for (int i = 3 * n - 2; i >= n; i -= 2)
        ans += a[i];
    cout << ans << endl;
}


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


int main()
{
	string s;
	cin>>s;
	map<char,int> m;
	for(char c : s)
	{
		m[c]++;
	}
	for(char c='a';c<(char)('a'+26);c=(char)(c+1))
	{
		if(m[c]==0)
		{
			cout<<c<<endl;
			return 0;
		}
	}
	cout<<"None"<<endl;
	return 0;
}


Measured memory_bytes: 3684
N=int(input())
A=sorted(list(map(int,input().split())))
if N%2==0:
  a=0
  for i in range(int(N/2)):
    a+=A[2*i+1]-A[2*i]
else:
  a=A[0]
  for i in range(int(N/2)):
    a+=A[-(2*i+1)]-A[-(2*i+2)]
print(a)

Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <stdio.h>
#include <string.h>
#include <cstdlib>
#include <math.h>
#include <bitset>
#include <iterator>
#include <iomanip>
#include <sstream>
#include <numeric>
#define INF 2000000000
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
long long gcd(long long a,long long b){if(a%b==0){return b;}else return gcd(b,a%b);}
long long lcm(long long a,long long b){if(a==0){return b;} return a/gcd(a,b)*b;}
#define MOD 1000000007
#define sym cout<<"---------"<<endl;
#define ll long long
#define PL pair<long long, long long>
#define P pair<int,int>
#define mk make_pair
#define en endl
#define WHITE 1
#define BLACK 2
#define GRAY 1
#define RE return 0
#define int ll

int x[55];

int dp[55][55][2501];

signed main(){
  int n,a;
  cin>>n>>a;
  for(int i=1; i<=n; i++) cin>>x[i];
  
  dp[0][0][0]=1;
  for(int j=1; j<=n; j++){
    dp[j][0][0]=1;
    for(int k=1; k<=n; k++){
      for(int s=0; s<=2500; s++){
        if(s-x[j]>=0) dp[j][k][s]=max(dp[j][k][s], dp[j-1][k][s]+dp[j-1][k-1][s-x[j]]);
        else dp[j][k][s]=dp[j-1][k][s];
      }
    }
  }
  int ans=0;
  for(int i=1; i<=n; i++){
    ans+=dp[n][i][i*a];
  }
  cout<<ans<<en;
}


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

vector<int> a;

int find(int x){
    int l=0,r=a.size()-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]==x){
            a.erase(a.begin()+mid);
            return 1;
        }
        else if(a[mid]<x)l=mid+1;
        else r=mid-1;
    }
    return 0;
}

int main(void){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x;scanf("%d",&x);
        a.push_back(x);
    }
    sort(a.begin(),a.end());
    bool suc=true;
    int m;
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int x;scanf("%d",&x);
        if(!find(x))
            suc=false;
    }
    if(suc)printf("YES\n");
    else printf("NO\n");
    return 0;
}

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

template <typename T>
class BIT {
  int n;
  vector<T> bit;
public:
  BIT(int _n) {
    n = _n;
    bit = vector<T>(n+1,(T)0);
  }
  T sum(int i) {
    T s = 0;
    while(i > 0){
    s += bit[i];
    i -= i & -i;
  }
  return s;
  }
  void add(int i, T x) {
    while(i <= n){
    bit[i] += x;
    i += i & -i;
    }
  }
};

int main(){
  int n;
  cin >> n;
  int p[n];
  rep(i,n) cin >> p[i];
  BIT<int> bit(n+1);
  int ans = 0;
  rep(i,n) {
    if(bit.sum(p[i]) == 0) ans++;
    bit.add(p[i],1);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1792
X, Y = map(int, input().split())

MAX = 2 * 10 ** 6 + 1
MOD = 10 ** 9 + 7

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1
for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    
# Inverse factorial
finv = [0] * (MAX + 1)
finv[MAX] = pow(fac[MAX], MOD - 2, MOD)
for i in reversed(range(1, MAX + 1)):
    finv[i - 1] = finv[i] * i % MOD

def comb(n, k):
    if n < k or k < 0:
        return 0
    return (fac[n] * finv[k] * finv[n - k]) % MOD

mod = 10 ** 9 + 7
v1 = 2 * Y - X
v2 = 2 * X - Y
if (v1 >= 0 and v1 % 3 == 0 and v2 >= 0 and v2 % 3 == 0):
    a = v1 // 3
    b = v2 // 3
    print(comb(a + b, a))
else:
    print(0)


Measured memory_bytes: 104548
import math

N = int(input())
A = list(map(int, input().split()))
m = max(A)
c = [0] * (m+1)
for i in A:
  c[i] += 1

pairwise = True
for i in range(2,m+1,1):
  cnt = 0
  for j in range(i,m+1,i):
    cnt += c[j]
  if cnt > 1:
    pairwise = False
if pairwise:
  print("pairwise coprime")
  exit()

g = 0
for i in range(N):
  g = math.gcd(g,A[i])
if g == 1:
  print("setwise coprime")
  exit()
print("not coprime")

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

using namespace std;

typedef long long ll;

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  string S, T; cin >> S >> T;
  int slen = S.size();
  int tlen = T.size();
  if(slen < tlen){
    cout << "UNRESTORABLE" << endl;
    return 0;
  }
  bool isalr = false;
  // S already includes T
  for(int i=slen-tlen;i>=0;i--){
    if(S.substr(i, tlen) == T){
      isalr = true;
      break;
    }
  }
  if(isalr){
    for(int i=0;i<slen;i++){
      if(S[i] == '?') cout << 'a';
      else cout << S[i];
    }
    cout << endl;
    return 0;
  }
  // S can include T or not
  for(int i=slen-tlen;i>=0;i--){
    bool flag = true;
    for(int j=i;j<i+tlen;j++){
      if(S[j] != T[j-i] && S[j] != '?'){
        flag = false;
        break;
      }
    }
    if(flag){
      // S[i] ~ S[i+tlen-1]
      for(int k=0;k<=i-1;k++){
        if(S[k] == '?') cout << 'a';
        else cout << S[k];
      }
      cout << T;
      for(int k=i+tlen;k<slen;k++){
        if(S[k] == '?') cout << 'a';
        else cout << S[k];
      }
      cout << endl;
      return 0;
    }
  }
  cout << "UNRESTORABLE" << endl;
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var input = Console.ReadLine().Split();
        long L = long.Parse(input[0]);
        long R = long.Parse(input[1]);
        long ans = long.MaxValue;
        for(long i=L;i<=Math.Min(R,L+2030); i++)
        {
            for(long j = i + 1; j <= Math.Min(R, L + 2030); j++)
            {
                ans=Math.Min(ans, Math.Min((i*j)%2019,(i%2019)*(j%2019)));
            }
        }
        Console.WriteLine(ans);
    }
}


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

void fun(){
    int k , l , r;
    cin>>k;
    cin>>l>>r;
    for(int i=l;i<=r;i++){
     if(i%k==0){
         cout<<"OK"<<endl;
         return;
     }   
    }
    cout<<"NG"<<endl;
    return ;
}


int main() {
    fun();
    return 0;
}

Measured memory_bytes: 3632
N, M = map(int,input().split())
A = sorted(list(map(int, input().split())))
p = [ list(map(int, input().split())) for i in range(M) ]
p = sorted(p, reverse=True, key=lambda x: x[1])

maxv = max(A)
minv = min(A)
ans = sum(A)

if p[0][1] < minv:
    print(ans)
else:
    cnt = 0
    j = 0
    i = 0
    for x in p:
        while(i < min(j + x[0], N)):
            if x[1] > A[i]:
                ans = ans - A[i] + x[1]
                i = i+1
            else:
                break
        else:
            j = i
            if j >= N:
                break
            continue
        break
    print(ans)

Measured memory_bytes: 33944
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int n;
    long long a[110][110];
    long long sum[110][110]={};
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%lld",&a[i][j]);
            sum[i][j] = a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
        }
    }
    
    long long ans = sum[1][1];
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            
            for(int k=i+1;k<=n;k++){
                for(int l=j+1;l<=n;l++){
                    ans = max(ans,sum[k][l]-sum[i][l]-sum[k][j]+sum[i][j]);
                }
            }
            
        }
    }
    printf("%lld\n",ans);
    return(0);
}


Measured memory_bytes: 2872
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
string ch;
int dp[105][105];
int fun(int i,int j)
{
    if(i>j)
    {
        return 0;
    }
    if(dp[i][j]!=-1)
        return dp[i][j];
    int res=1e5;
    if(ch[i]==ch[j])
    {
        res=min(res,fun(i+1,j-1));
    }
    res=min(res,1+fun(i+1,j-1));
    return dp[i][j]=res;

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>ch;
    memset(dp,-1,sizeof dp);
    cout<<fun(0,ch.size()-1)<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0;i < n;i++)
#define rev(i, n) for(int i = n;i >= 0;i--)
#define repeat(i, m, n) for(int i = m;i < n;i++)
#define repeatrev(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
#define itn int

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
typedef priority_queue<int> Pr;

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int H, W;
    int a, b;
    cin >> H >> W >> a >> b;
    cout << H * W + a * b - a * W - b * H<< endl;
}

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

int main()
{
   int a,b,c,x,ans=0;
   int i,j,k;
   cin>>a>>b>>c>>x;
   
   for(i=0;i<=a;i++){
	   for(j=0;j<=b;j++){
		   for(k=0;k<=c;k++){
			   if(50*k+100*j+500*i==x){
				   ans++;
			   }
		   }
	   }
   }
   cout<<ans<<"\n";
}


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

int main(){
    int a,b,c;
    cin>>a>>b>>c;
    if(a==b and (a!=c or b!=c)){
        cout<<"Yes"<<endl;
        return 0;
    }
    if(b==c and (b!=a or c!=a)){
        cout<<"Yes"<<endl;
        return 0;
    }
    if(c==a and (c!=b or a!=c)){
        cout<<"Yes"<<endl;
        return 0;
    }
    else cout<<"No"<<endl;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
const char nl = '\n';
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> pt;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1010;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

bool grid[N][N];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int h, w; cin >> h >> w;
  auto in = [&](int x, int y) {
    return x >= 0 && x < h && y >= 0 && y < w;
  };
  queue<tuple<int, int, int>> q;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      char c; cin >> c;
      grid[i][j] = (c == '#');
      if (grid[i][j]) {
        q.emplace(i, j, 0);
        grid[i][j] = 1;
      }
    }
  }
  int ans = 0;
  while (!q.empty()) {
    int x, y, d; tie(x, y, d) = q.front(); q.pop();
    ans = d;
    for (int i = 0; i < 4; i++) {
      int nx = x+dx[i], ny = y+dy[i];
      if (!in(nx, ny) || grid[nx][ny]) continue;
      grid[nx][ny] = 1;
      q.emplace(nx, ny, d+1);
    }
  }
  cout << ans << nl;
  return 0;
}


Measured memory_bytes: 13328
using System;
class Program
{
  static void Main()
  {
    string S = Console.ReadLine();
    string T = Console.ReadLine();
    int cnt = 0;
    for (int i = 0; i < 3; i++)
    {
      if (S.Substring(i, 1) == T.Substring(i, 1))
      {
        cnt++;
      }
    }
    Console.WriteLine(cnt);
  }
}

Measured memory_bytes: 11092
def main():
    N = int(input())
    a = [0] + list(map(int, input().split()))

    b = [0] * (N + 1) 

    for i in range(N,0,-1):
        sum = 0
        for j in range(2*i, N+1, i):
            sum += b[j]
        if sum % 2 != a[i] % 2:
            b[i] = 1
    
    ans = []
    for i in range(1,N+1):
        if b[i] == 1:
            ans.append(i)
    
    print(len(ans))
    print(*ans)

main()

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

int main(){
    long long n, t, ans = 0;
    cin >> n >> t;
    
    long long cur = 0;
    
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        if(cur < x) ans += x - cur;
        cur = x + t;
    }
    cout << cur - ans;
    return 0;
}


Measured memory_bytes: 256
N , L = map(int,input().split())

original_apple_pie = 0
li = []
mi = 10e9
for i in range(N):
    tmp = L + i 
    li.append(tmp)
    original_apple_pie += tmp
    if mi > abs(tmp):
        mi = abs(tmp)
        ans = tmp

if original_apple_pie<0 and ans < 0:
    print(original_apple_pie-ans)
else:
    print(original_apple_pie-ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007 

int main() {
	ll n;
	cin>>n;
	ll ans=0,ans2=INF;
	for(ll i=0;i<n;i++){
		ll x;
		cin>>x;
		ans+=x;
		if(x%10!=0){
			ans2=min(ans2,x);
		}
	}
	cout << (ans%10!=0? ans:max(ll(0),ans-ans2));
	// your code goes here
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cstring>
#include <map>
#include <set>
#define int long long int
using namespace std;
const int MAX = 1000000007;

int dp[4000][4000];

signed main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    #ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    //  freopen("output.txt", "w", stdout);
    #endif
    
    int h, w, i, j;
    cin>>h>>w;
    string s[h];
    for(i=0;i<h;i++){
        cin>>s[i];
    }
    for(i=0;i<h;i++){
        for(j=0;j<w;j++){
            if(s[i][j]=='#')
                continue;
            if(i==0&&j==0)
                dp[i][j]=1;
            else if(i==0)
                dp[i][j]=dp[i][j-1]%MAX;
            else if(j==0)
                dp[i][j]=dp[i-1][j]%MAX;
            else{
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
                dp[i][j]=dp[i][j]%MAX;
            }
        }
    }
    cout<<dp[h-1][w-1]%MAX<<endl;
    
}


Measured memory_bytes: 32768
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int lld;

const lld mod = 1e9+7;
const lld INF = 1e9;
//const lld MAXN = 1e9;

int main()
{
	string s;
	cin >> s;

	int n = s.size();

	string sol;

	if (n % 2 ==0)    
	{
		if (s[0] == s[n-1])  //abdaca
		{
			sol = "First";
		}else
		{
			sol = "Second";
		}
	}else
	{
		if (s[0] != s[n-1])  //abgda
		{
			sol = "First";
		}else
		{
			sol = "Second";
		}
	}

	cout << sol << endl;

	return 0;
}

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

typedef long long ll;
const int INF = 1e9;
const ll LINF = 1e18;
const int mod = 1e9+7;

#define pi pair<int,int>
#define pl pair<lld,lld>

#define dump(x) cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define SANKOU(n,a,b) cout << ((n) ? (#a) : (#b) ) << endl

#define mem0(x) memset(x,0,sizeof(x))
#define fillnum(x,n) fill(begin(x),end(x),n)
#define asort(x) sort(x.begin(),x.end())
#define dsort(x,t) sort(x.begin(),x.end(),greater<t>())
#define vuniq(x) x.erase(unique(x.begin(), x.end()), x.end())

#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)

int H,W;
int Ch,Cw,Dh,Dw;
char mas[1010][1010];
int flg[1010][1010];
vector< vector<pi> > Node;
int start_num = -1;
int goal_num = -1;
int node_num = 0;
int dx[4] = {0,1,0,-1};
int dy[4] = {-1,0,1,0};

void create_Node(int x, int y, int num){
    if(x == Cw && y == Ch){
        start_num = num;
    }
    if(x == Dw && y == Dh){
        goal_num = num;
    }
    flg[y][x] = num;
    Node[num].pb(mp(x,y));
    for (int i = 0; i < 4; i++) {
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx >= 0 && nx < W && ny >= 0 && ny < H && mas[ny][nx] == '.' && flg[ny][nx] == -1){
            create_Node(nx,ny,num);
        }
    }
}

int main() {
    cin >> H >> W;
    cin >> Ch >> Cw;
    cin >> Dh >> Dw;
    Ch--; Cw--; Dh--; Dw--;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> mas[i][j];
            flg[i][j] = -1;
        }
    }
    
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if(mas[i][j] == '.' && flg[i][j] == -1){
                Node.pb(vector<pi>());
                create_Node(j,i,node_num);
                node_num++;
            }
        }
    }

    vector<int> edge[node_num];

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if(flg[i][j] != -1){
                for (int k = -2; k <= 2; k++) {
                    for (int l = -2; l <= 2; l++) {
                        int nx = j + l;
                        int ny = i + k;
                        if(nx >= 0 && nx < W && ny >= 0 && ny < H && flg[ny][nx] != -1){
                            edge[flg[i][j]].pb(flg[ny][nx]);
                        }
                    }
                }
            }
        }
    }

    for (int i = 0; i < node_num; i++) {
        vuniq(edge[i]);
    }

    bool f[node_num];
    mem0(f);
    queue<pi> que;
    que.push(mp(0,start_num));
    f[start_num] = true;
    while(!que.empty()){
        pi n = que.front();
        que.pop();
        if(n.second == goal_num){
            cout << n.first << endl;
            exit(0);
        }
        for (int i = 0; i < edge[n.second].size(); i++) {
            if(f[edge[n.second][i]] == false){
                f[edge[n.second][i]] = true;
                que.push(mp(n.first+1,edge[n.second][i]));
            }
        }
    }
    cout << "-1" << endl;
}

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

using namespace std;

int main(int argc, char *argv[]) {
    int A, B;
    cin >> A >> B;
    if (A > B) {
        cout << (A + A - 1) << endl;
    } else if (B > A)  {
        cout << (B + B - 1) << endl;
    } else  {
        cout << (A + B) << 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++)
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;

int main(){
  string s;
  cin >> s;
  int n = s.size();
  vi ans(n+1);
  s += 'R';
  int cntr = 0, cntl = 0;
  int tmp;
  rep(i,n+1){
    if(s[i] == 'R') {
      cntr++;
      if(s[i-1] == 'L'){
        if(cntl%2 == 0){
          ans[tmp] += cntl/2;
          ans[tmp-1] += cntl/2;
          cntl = 0;
        }
        else{
          ans[tmp] += cntl/2 + 1;
          ans[tmp-1] += cntl/2;
          cntl = 0;
        }
      }
    }
    else{
      cntl++;
      if(s[i-1] == 'R') tmp = i;
      if(cntr%2 == 0){
        ans[i] += cntr/2;
        ans[i-1] += cntr/2;
        cntr = 0;
      }
      else{
        ans[i] += cntr/2;
        ans[i-1] += cntr/2 + 1;
        cntr = 0;
      }
    }
  }
  rep(i,n) cout << ans[i] << " ";
}


Measured memory_bytes: 3860
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define INF INT_MAX;
typedef long long ll;
using namespace std;

int main(){
  int H,W; cin >> H >> W;
  vector<string> s(H);
  rep(i,H){
    cin >> s.at(i);
  }

  rep(i,H){
    cout << s.at(i) << endl << s.at(i) << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
 
 
template<typename T>
vector<int> build_kmp(const T &s) {
  vector<int> f(s.size());
  int fp = f[0] = -1;
  for (int i = 1; i < s.size(); ++i) {
    while (~fp && s[fp + 1] != s[i]) fp = f[fp];
    if (s[fp + 1] == s[i]) ++fp;
    f[i] = fp;
  }
  return f;
}
 
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  string s, t; cin >> s >> t;
  int m = t.size();
  while (t.size() <= s.size() * 2) t += t;
  while (s.size() <= t.size() * 2) s += s;
  auto kmp = build_kmp(t);
  int ans = 0, i = -1;
  for (auto c : s) {
    while (i != -1 and t[i + 1] != c) i = kmp[i];
    if (t[i + 1] == c) ++i;
    ans = max(ans, (i + 1) / m);
    if (i == t.size() - 1) i = kmp[i];
  }
  cout << (ans * m == t.size() ? -1 : ans) << '\n';
}


Measured memory_bytes: 19996
#include <bits/stdc++.h>
#define mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

int P, a, res[3000], b[3001], c[3001], d[3001];

int pw(int x, int y) {
	int a = 1;
	while (y) {
		if (y & 1) {
			a = a * x % P;
		}
		x = x * x % P;
		y >>= 1;
	}
	return a;
}

int modinv(int x) {
	return pw(x, P - 2);
}

int main() {
	cin >> P;
	b[0] = 1;
	for (int j = 0; j < P; ++j) {
		for (int k = P; k >= 0; --k) {
			b[k + 1] = (b[k + 1] + b[k]) % P;
			b[k] = b[k] * (P - j) % P;
		}
	}
	for (int i = 0; i < P; ++i) {
		cin >> a;
		if (a) {
			for (int j = P; j >= 0; --j) {
				c[j] = b[j];
			}
			for (int j = P - 1; j >= 0; --j) {
				d[j] = c[j + 1];
				c[j] += d[j] * i;
				c[j] %= P;
			}
			int t = 1;
			for (int j = 0; j < P; ++j) {
				if (i == j)continue;
				t *= (P + i - j);
				t %= P;
			}
			t = modinv(t);
			for (int j = 0; j < P; ++j) {
				res[j] += d[j] * t;
				res[j] %= P;
			}
		}
	}
	for (int j = 0; j < P; ++j) {
		cout << res[j];
		if (j != P - 1)cout << sp;
	}
	cout << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
template<class S, class T> inline S min_L(S a,T b){
  return a<=b?a:b;
}
template<class S, class T> inline S max_L(S a,T b){
  return a>=b?a:b;
}
inline void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
int K;
int X;
int ress;
int res[200];
int main(){
  int i, s, t;
  rd(K);
  rd(X);
  s =max_L(-1000000, X-K+1);
  t =min_L(1000000, X+K-1);
  for(i=(s);i<(t+1);i++){
    res[ress++] = i;
  }
  {
    int Q5VJL1cS;
    if(ress==0){
      putchar_unlocked('\n');
    }
    else{
      for(Q5VJL1cS=0;Q5VJL1cS<(ress-1);Q5VJL1cS++){
        wt_L(res[Q5VJL1cS]);
        wt_L(' ');
      }
      wt_L(res[Q5VJL1cS]);
      wt_L('\n');
    }
  }
  return 0;
}
// cLay varsion 20190810-2

// --- original code ---
// int K, X;
// int ress, res[200];
// {
//   int i, s, t;
//   rd(K,X);
//   s = max(-1d6, X-K+1);
//   t = min(1d6, X+K-1);
//   rep(i,s,t+1) res[ress++] = i;
//   wt(res(ress));
// }


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483647
#define INT_MAX 2147483647
#define LL_MIN (LL)-3223372036854775807
#define LL_MAX (LL)9223372036854775807
#define PI 3.14159265359

int N,K,a[200000];
LL L;
LL c[200001] = {};

LL solve(int n){ //K番目の数がn以下になる回数
	int l = 0;
	int r = K-1;
	LL ans = 0;
	int tmp = 0; //n以下の数がいくつ含まれているか
	for(int i=0; i<K; i++){
		if(a[i] <= n) tmp++;
	}
	while(l < N && r < N){
		if(tmp >= K){
			ans += N-r;
			if(a[l] <= n) tmp--;
			l++;
			continue;
		}
		r++;
		if(r < N && a[r] <= n) tmp++;
	}
	return ans;
}

int main() {
	iostream::sync_with_stdio(false);

	cin >> N >> K >> L;
	for(int i=0; i<N; i++) cin >> a[i];
	
	int l = 1;
	int r = N;
	int now = N/2;
	while(l!=r){
		LL tmp = solve(now);
		if(tmp < L){
			l = now + 1;
			now = (l+r) / 2;
		}
		if(tmp >= L){
			r = now;
			now = (l+r) / 2;
		}
	}
	cout << l << endl;


	return 0;
}



Measured memory_bytes: 3976
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const long long INF= 1e+18+1;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int main(){
  ll n,W;cin>>n>>W;
  vl w(n),v(n);
  rep(i,n)cin>>w[i]>>v[i];
  ll dp[114514];
  rep(i,100010)dp[i]=INF;
  dp[0]=0;
  rep(i,n){
    for(ll j=100010;j>=0;j--){
      if(j>=v[i])dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
    }
  }
  for(ll i=100005;i>=0;i--){
    if(dp[i]<=W){
      cout<<i<<endl;
      return 0;
    }
  }
}
  

Measured memory_bytes: 1024
import java.util.Scanner

import scala.collection.mutable
import scala.collection.mutable.ArrayBuffer

object Main extends App {
  val in = new Scanner(System.in)
  val V = in.nextInt()
  val E = in.nextInt()
  val dinitz1 = new Dinitz(V)
  val dinitz2 = new Dinitz(V)
  for (_ <- 0 until E) {
    val s = in.nextInt()
    val t = in.nextInt()
    val c = in.nextInt()
    dinitz1.addEdge(s, t, c)
    dinitz1.addEdge(t, s, c)
    dinitz2.addEdge(s, t, c)
    dinitz2.addEdge(t, s, c)
  }

  val f1 = dinitz1.maxFlow(0, V - 1)
  for {
    i <- dinitz1.graph.indices
    j <- dinitz1.graph(i).indices
    if dinitz1.graph(i)(j).cap == 0
    if dinitz2.graph(i)(j).cap == 1
  } {
    val e1 = dinitz2.graph(i)(j)
    val e2 = dinitz2.graph(e1.to)(e1.rev)
    e1.cap = 0
    e2.cap = 0
  }
  
  val f2 = dinitz2.maxFlow(0, V - 1)
  val flow = if (f1 > f2) {
    f1 - 1
  } else {
    f1
  }
  if (flow > 10000) {
    println(-1)
  } else {
    println(flow)
  }
}

class Dinitz(val V: Int) {

  class Edge(var to: Int, var cap: Long, var rev: Int)

  val graph = (for (_ <- 0 until V) yield new ArrayBuffer[Edge]()).toArray

  def addEdge(from: Int, to: Int, cap: Long): Unit = {
    graph(from).append(new Edge(to, cap, graph(to).size))
    graph(to).append(new Edge(from, 0, graph(from).size - 1))
  }

  def maxFlow(source: Int, sink: Int): Long = {
    var flow = 0L

    while (true) {
      val queue = new mutable.Queue[Int]()
      val level = Array.fill[Int](V)(-1)
      level(source) = 0
      queue.enqueue(source)
      while (queue.nonEmpty) {
        val v = queue.dequeue()
        for (e <- graph(v)) {
          if (e.cap > 0 && level(e.to) < 0) {
            level(e.to) = level(v) + 1
            queue.enqueue(e.to)
          }
        }
      }

      if (level(sink) < 0) return flow
      val iter = new Array[Int](V)

      def dfs(v: Int, t: Int, f: Long): Long = {
        if (v == t) return f

        while (iter(v) < graph(v).size) {
          val e = graph(v)(iter(v))
          if (e.cap > 0 && level(v) < level(e.to)) {
            val d = dfs(e.to, t, Math.min(f, e.cap))
            if (d > 0) {
              e.cap -= d
              graph(e.to)(e.rev).cap += d
              return d
            }
          }

          iter(v) += 1
        }
        0
      }

      var f = 1L
      while (f > 0) {
        f = dfs(source, sink, Long.MaxValue)
        flow += f
      }
    }

    throw new IllegalStateException()
  }
}

Measured memory_bytes: 369404
#include "bits/stdc++.h"

using namespace std;

using ll = long long;

template<typename T> using V = std::vector<T>;
using Vi = V<int>;
using VVi = V<V<int>>;
using Vl = V<ll>;
using VVl = V<V<ll>>;
using Vs = V<string>;

template<typename T1, typename T2> using P = std::pair<T1, T2>;
using Pii = P<int, int>;
using Pll = P<ll, ll>;
using Pdd = P<double, double>;

template<typename T1, typename T2> using M = std::map<T1, T2>;
using Mii = M<int, int>;
using Mll = M<ll, ll>;
using Msi = M<string, int>;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP2(i,s,e) for(int i=(int)(s);i<(int)(e);++i)
#define RREP(i,s,e) for(int i=(int)(s);i>=(int)(e);--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin(),ie=(c).end();i!=ie;++i)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin(),ie=(c).rend();i!=ie;++i)
#define ALL(c) (c).begin(), (c).end()

const double PI = acos(-1);
const ll MOD = 1e9+7;

ll n, m;

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

    V<V<P<int, ll>>> adj(n);
    REP(i, m) {
        int l, r; ll d; cin >> l >> r >> d;
        l--; r--;
        adj[l].push_back({r, d});
        adj[r].push_back({l, -d});
    }

    int idx = 0;
    Vl P(n, -1e18);
    queue<int> q;
    q.push(idx);
    P[idx] = 0;
    while (true) {
        int node = q.front();
        q.pop();
        for (auto x: adj[node]) {
            int v = x.first;
            ll d = x.second;
            if (P[v] == -1e18) {
                P[v] = P[node] + d;
                q.push(v);
            } else if (P[v] - P[node] != d) {
                cout << "No" << '\n';
                return 0;
            }
        }

        if (q.empty()) {
            while (idx < n) {
                if (P[idx] == -1e18) break;
                idx++;
            }
            if (idx == n) break;
            q.push(idx);
            P[idx] = 0;
        }
    }
    cout << "Yes" << '\n';

    return 0;
}


Measured memory_bytes: 13824
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/STACK:108777216")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <functional>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <bitset>
#include <queue>
#include <deque>
#include <utility>
#include <algorithm>
#include <ctime>
using namespace std;

int const MAX_N = 256 * 1024;

long long get_sum(long long x) {
	long long ans = 0;
	while (x) {
		ans += x%10;
		x/=10;
	}
	return ans;
}

int main() {
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);

	long long n;
	cin>>n;
	long long g = 0;
	while (g <= n) g = g*10 + 9;
	g /= 10;

	long long ans = get_sum(g);
	long long g2 = g+1;
	long long XX = g2 + g;
	while (XX <= n) {
		ans = max(ans, get_sum(XX));
		XX += g2;
	}

	long long QQ = n;
	string a = "";
	while (QQ) {
		a += (char) ('0' + QQ%10);
		QQ/=10;
	}
	string b = "";
	for (int i=((int) a.length())-1; i>=0; i--) b += a[i];

	for (int i=0; i<(int) b.length(); i++) {
		if (b[i] <= '0') continue;

		int sum = 0;
		for (int j=0; j<i; j++) sum += (b[j]-'0');
		
		sum += (b[i]-'0'-1);
		for (int j=i+1; j<(int) b.length(); j++) sum += 9;

		ans = max(ans, sum+0LL);
	}

	cout<<ans;

    return 0;
}

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

using namespace std;

int main(void){
    int r,g,b;

    cin >> r >> g >> b;

    if((100*r+10*g+b) % 4 == 0){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
from collections import defaultdict
import sys
MOD=998244353
N=int(input())
dlist=list(map(int,input().split()))

if dlist[0]!=0:
  print(0)
  sys.exit(0)
  
ddic=defaultdict(int)
for d in dlist:
  ddic[d]+=1
  
if ddic[0]!=1:
  print(0)
  sys.exit(0)
  
max_d=max(dlist)
answer=1
for d in range(1,max_d+1):
  if ddic[d]==0:
    print(0)
    sys.exit(0)
    
  term=pow(ddic[d-1],ddic[d],MOD)
  answer*=term
  answer%=MOD
  
print(answer)

Measured memory_bytes: 24176
#include<stdio.h>
int main(void){
	int n,a,b,i,j,flag,slash;
	int c[101]={0},d[101]={0},e[4][4]={0};
	for(i=1;i<4;i++){
		for(j=1;j<4;j++){
			scanf("%d",&a);
			c[a]=i;
			d[a]=j;
		}
	}
	scanf("%d",&n);
	while(n--){
		scanf("%d",&b);
		e[c[b]][d[b]]=1;
	}
	for(i=1;i<4;i++){
		slash*=e[i][i];
		flag=e[i][1]*e[i][2]*e[i][3];
		flag=flag?flag:e[1][i]*e[2][i]*e[3][i];
		if(flag){
			break;
		}
	}
	slash=slash?slash:e[1][3]*e[2][2]*e[3][1];
	printf(slash||flag?"Yes":"No");
	return 0;
}


Measured memory_bytes: 1732
<?php
//7
//beat
//vet
//beet
//bed
//vet
//bet
//beet

$h = STDIN;
$n = fgets($h);
//$a = explode(' ', trim(fgets($h)));
$tmp = [];
foreach (range(1, $n) as $_) {
    $s = trim(fgets($h));
    if (!isset($tmp[$s])) {
        $tmp[$s] = 1;
    } else {
        ++$tmp[$s];
    }
}

arsort($tmp);
$max = null;
$ans = [];
foreach ($tmp as $key => $val) {
    if ($max === null) {
        $max = $val;
        $ans[] = $key;
        continue;
    }
    if ($max > $val) {
        break;
    }
    $ans[]=$key;
}

sort($ans);
foreach ($ans as $a) {
    echo $a,PHP_EOL;
}



Measured memory_bytes: 29176
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;

class Program
{
    internal static void Main(string[] args) {
        var inp = ReadLine().Split(' ').Select(s => long.Parse(s)).ToList();
        var N = inp[0];
        var Y = inp[1];

        for (long i = N; i >= 0; i--) {
            for (long j = N - i; j >= 0; j--) {
                long k = N - i - j;
                if ((10000 * i) + (5000 * j) + (1000 * k) == Y) {
                    WriteLine($"{i} {j} {k}");
                    return;
                }

            }
        }
        WriteLine("-1 -1 -1");
    }
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using P = pair<int, int>;
using vec = vector<int>;
using mat = vector<vector<int>>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define endl "\n"

constexpr int MOD = 1000000007;
const int INF = 1 << 30;

int main() {
    int n;
    cin >> n;
    double res = 0;
    for (int i = 1; i <= n; i++) {
        if (i % 2) res += 1.0;
    }
    res /= n;
    cout << fixed << setprecision(10) << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <cstring>
#include <map> 
#include<set>
#include<queue>
#include <iomanip>

typedef long long ll;

#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;

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

const long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<ll, ll> P;
ll ma = 1000000000 + 7;
ll mx = 1000003;
ll h,n, w,m,t; string s;
ll R, C;
ll sy, sx, gy, gx;
char maze[20][20];
ll dis[20][20];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);
}
ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
void comb(vector<vector <ll> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (int j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j])%ma;
		}
	}
}

ll GetDigit(ll num) {
	return log10(num) + 1;
}
ll Combination(int n, int r)
{
	if (n - r < r) r = n - r;
	if (r == 0) return 1;
	if (r == 1) return n;

	vector<ll> numerator(r);
	vector<ll> denominator(r);

	for (int k = 0; k < r; k++)
	{
		numerator[k] = n - r + k + 1;
		denominator[k] = k + 1;
	}

	for (int p = 2; p <= r; p++)
	{
		int pivot = denominator[p - 1];
		if (pivot > 1)
		{
			int offset = (n - r) % p;
			for (int k = p - 1; k < r; k += p)
			{
				numerator[k - offset] /= pivot;
				denominator[k] /= pivot;
			}
		}
	}

	ll result = 1;
	for (int k = 0; k < r; k++)
	{
		if (numerator[k] > 1) result *= numerator[k];
		result %= ma;
	}

	return result;
}

ll bfs() {
	queue<P> que;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) dis[i][j] = INF;
	}
	que.push(P(sy - 1, sx - 1));
	dis[sy - 1][sx - 1] = 0;

	while (que.size() > 0) {
		P p = que.front();
		que.pop();
		if (p.first == gy - 1 && p.second == gx - 1) break;
		for (ll i = 0; i < 4; i++) {
			ll ny = p.first + dy[i];
			ll nx = p.second + dx[i];
			if (0 <= ny && ny < R && 0 <= nx && nx < C && maze[ny][nx] == '.' && dis[ny][nx] == INF) {
				que.push(P(ny, nx));
				dis[ny][nx] = dis[p.first][p.second] + 1;
			}
		}
	}
	return dis[gy - 1][gx - 1];
}
ll dp[20500];
int main() {
	ll d, x;
	cin >> n >> d >> x;
	ll res = x;
	vector<ll> a(n);
	rep(i, n) {
		cin >> a[i];
	}
	rep(i, n) {
		ll k = 0;
		for (ll j = 1; j <= d; j = k * a[i] + 1) {
			++res;
			++k;
		}
	}
	cout << res << endl;
}

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

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  long long K, X;
  cin >> K >> X;
  for (int i = -1000000; i <= 1000000; ++i) {
    if (abs(i - X) < K) cout << i << ' ';
  }
  cout << '\n';
}


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

const int mod = 1000000007;

int n;
string s;
int dp[5001][5001];

long powmod(long b, long e) {
  if (e == 0) return 1;
  if (e & 1) return powmod(b, e - 1) * b % mod;
  long t = powmod(b, e / 2);
  return t * t % mod;
}

void add(int& a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}

int main() {
  cin >> n >> s;
  
  dp[0][0] = 1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      add(dp[i + 1][max(0, j - 1)], dp[i][j]);
      add(dp[i + 1][j + 1], dp[i][j]);
      add(dp[i + 1][j + 1], dp[i][j]);
    }
  }
  cout << dp[n][s.size()] * powmod(500000004, s.size()) % mod << endl;
}

Measured memory_bytes: 98048
package main

import "fmt"

func isAllEven(arr []int) bool {
	for _, n := range arr {
		if n%2 != 0 {
			return false
		}
	}
	return true
}

func main() {
	var (
		n   int
		ans int
	)

	fmt.Scan(&n)
	as := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&as[i])
	}

	for isAllEven(as) {
		for i := 0; i < n; i++ {
			as[i] /= 2
		}
		ans++
	}
	fmt.Println(ans)
}


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

int main() {
	int n,m;
	cin>>n>>m;
	string s(m+2,'#');
	cout<<s<<endl;
	string t;
	while(n--){
		cin>>t;
		t.insert(t.begin(),'#');
		t.push_back('#');
		cout<<t<<endl;
	}
	cout<<s<<endl;
	return 0;
}

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

int main()
{
    int H, W;
    cin >> H >> W;

    vector<vector<bool>> field(H, vector<bool>(W, false));
    string A;
    int count = 0;
    queue<pair<int, int>> q_new;
    queue<pair<int, int>> q_old;
    for (int i = 0; i < H; i++)
    {
        cin >> A;
        for (int j = 0; j < W; j++)
        {
            if (A[j] == '#')
            {
                field[i][j] = true;
                q_new.push(make_pair(i, j));
                count++;
            }
            else
            {
                field[i][j] = false;
            }
        }
    }

    int ans = 0;
    int diff[4][2] = {
        {0, 1},
        {0, -1},
        {1, 0},
        {-1, 0},
    };

    while (count < H * W)
    {
        ans++;
        q_old = q_new;
        q_new = queue<pair<int, int>>();
        while (!q_old.empty())
        {
            int x_old = q_old.front().first;
            int y_old = q_old.front().second;
            q_old.pop();
            for (int i = 0; i < 4; i++)
            {
                int x_new = x_old + diff[i][0];
                int y_new = y_old + diff[i][1];
                if (x_new < 0 || H <= x_new)
                {
                    continue;
                }
                if (y_new < 0 || W <= y_new)
                {
                    continue;
                }
                if (field[x_new][y_new])
                {
                    continue;
                }
                field[x_new][y_new] = true;
                count++;
                q_new.push(make_pair(x_new, y_new));
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 10624
use std::collections::VecDeque;
use std::io::{stdin, Read};

macro_rules! parse {
    ($it: ident) => {
        $it.next().unwrap().parse().unwrap()
    };
    ($it: ident,2) => {
        (parse!($it), parse!($it))
    };
    ($it: ident,3) => {
        (parse!($it), parse!($it), parse!($it))
    };
    ($it: ident,4) => {
        (parse!($it), parse!($it), parse!($it), parse!($it))
    };
    ($it: ident, $n: expr) => {
        (&mut $it).take($n).map(|e| e.parse().unwrap()).collect();
    };
}

const M: usize = 1000000007;
fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    let mut it = s.split_whitespace();
    let (n, k): (usize, usize) = parse!(it, 2);
    let mut g = vec![vec![]; n];
    for _ in 0..(n - 1) {
        let (a, b): (usize, usize) = parse!(it, 2);
        let a = a - 1;
        let b = b - 1;
        g[a].push(b);
        g[b].push(a);
    }
    let mut q = VecDeque::new();
    q.push_back(0);
    let mut seen = vec![false; n];
    seen[0] = true;
    let mut dp = vec![0; n];
    dp[0] = k;
    let mut exist_parent = false;
    while let Some(u) = q.pop_front() {
        let mut i = 0;
        for &v in g[u].iter() {
            if !seen[v] {
                seen[v] = true;
                q.push_back(v);
                let a = k - 1 - i - if exist_parent { 1 } else { 0 };
                dp[v] = a;
                i += 1;
            }
        }
        if u == 0 {
            exist_parent = true;
        }
    }
    println!("{}", dp.iter().fold(1, |a, b| (a * b) % M));
}


Measured memory_bytes: 16636
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())
#define fi first
#define se second

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<endl;
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;
const ll inf=1e15;

ll dp[110][4][4][4];

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin>>n;
  dp[0][3][3][3]=1;
  rep(i,n)rep(j,4)rep(k,4)rep(l,4)rep(x,4){
    if(k==0 && l==2 && x==1) continue;
    if(k==0 && l==1 && x==2) continue;
    if(k==2 && l==0 && x==1) continue;
    if(j==0 && k==2 && x==1) continue;
    if(j==0 && l==2 && x==1) continue;
    (dp[i+1][k][l][x]+=dp[i][j][k][l])%=mod;
  }
  ll ans=0;
  rep(j,4)rep(k,4)rep(l,4) (ans+=dp[n][j][k][l])%=mod;
  cout<<ans<<endl;
}

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

int main()
{
    ll n, d, a;
    cin >> n >> d >> a;

    vector<pint> xh(n);
    rep(i, n) cin >> xh[i].first >> xh[i].second;
    rep(i, n) xh[i].second = (xh[i].second % a == 0) ? xh[i].second / a : xh[i].second / a + 1;

    sort(xh.begin(), xh.end());

    vector<ll> pos;
    vector<pint> num;
    ll ans = 0;
    rep(i, n)
    {
        ll &x = xh[i].first;
        ll &h = xh[i].second;

        ll l = upper_bound(pos.begin(), pos.end(), x - d - 1) - pos.begin();
        if (l != (ll)pos.size())
        {
            h = h - (ans - num[l].second);
            if (h <= 0)
                continue;
        }

        pos.emplace_back(x + d);
        ll tmp = ans;
        ans += h;
        num.emplace_back(pint(ans, tmp));
    }
    cout << ans << endl;
}

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

int main() {
    int n;
    cin >> n;
    vector<int> A(n), B(n + 1);
    for (int i = 0; i < n; i++)
        cin >> A[i];

    vector<int> C(100001);
    for (int i = 0; i < n; i++)
        C[A[i]]++;
    for (int i = 1; i <= 100001; i++)
        C[i] += C[i - 1];
    for (int i = n - 1; i >= 0; i--) {
        B[C[A[i]]] = A[i];
        C[A[i]]--;
    }

    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << " ";
        cout << B[i];
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 18936
N = int(input())
a_list = list(map(int, input().split( )))
import collections
a_c=collections.Counter(a_list)

#それを値とカウントで分ける
a_val, a_count=zip(*a_c.most_common())

ans =0
for i in range(len(a_val)):
	if a_val[i] > a_count[i]:
		ans += a_count[i]
	elif a_val[i] < a_count[i]:
		ans += a_count[i] - a_val[i]

print(ans)

Measured memory_bytes: 28400