akhauriyash/Code-Regression huggingface dataset:
#include  <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;

const int vmax=10010;
const int inf=1<<28;
struct edge{int to,cap,cost,rev;};
vector<edge> graph[vmax];

int dist[vmax];
int pv[vmax],pe[vmax];
typedef tuple<int,int> state;

void add_edge(int from,int to,int cap,int cost){
	graph[from].push_back({to,cap,cost,(int)graph[to].size()});
	graph[to].push_back({from,0,-cost,(int)graph[from].size()-1});
}

int min_cost_flow(int s,int t,int f,int n){
	int res=0;
	while(f>0){
		fill(dist,dist+n,inf);
		dist[s]=0;
		bool update=true;
		while(update){
			update=false;
			rep(v,n){
				if(dist[v]==inf) continue;
				rep(i,graph[v].size()){
					edge &e=graph[v][i];
					if(e.cap>0&&dist[e.to]>dist[v]+e.cost){
						dist[e.to]=dist[v]+e.cost;
						pv[e.to]=v,pe[e.to]=i;
						update=true;
					}
				}
			}
		}

		if(dist[t]==inf) return -1;

		int d=f;
		for(int v=t;v!=s;v=pv[v]) d=min(d,graph[pv[v]][pe[v]].cap);
		f-=d;
		res+=d*dist[t];

		for(int v=t;v!=s;v=pv[v]){
			edge &e=graph[pv[v]][pe[v]];
			e.cap-=d;
			graph[v][e.rev].cap+=d;
		}
	}
	return res;
}

int w[10010];
int a[10010];

int main(void){
	int m,n,k;
	cin >> m >> n >> k;
	rep(i,n) cin >> w[i];
	rep(i,k) cin >> a[i],a[i]--;

	int sum=0;
	rep(i,k){
		if(i-1>=0&&a[i]==a[i-1]) continue;
		sum+=w[a[i]];
	}

	rep(i,k-1) add_edge(i,i+1,inf,0);

	int prev[10010];
	rep(i,n) prev[i]=-1;

	rep(i,k){
		int cur=a[i];
		if(prev[cur]!=-1&&prev[cur]+1!=i) add_edge(prev[cur]+1,i,1,-w[cur]);
		prev[cur]=i;
	}
	cout << sum+min_cost_flow(0,k-1,m-1,k) << endl;
	return 0;
}

Measured memory_bytes: 2468
H,W = map(int,input().split())
S = [list(input()) for n in range(H)]
A = [["."]*(W+2)]*(H+2)

S.insert(0,(["."]*W))
S.append(["."]*W)

for h in range(H+2):
  S[h].insert(0,".")
  S[h].append(".")

for h in range(1,1+H):
  for w in range(1,1+W):
    ans=0
    if S[h][w]==".":
      ans+=S[h-1][w-1:w+2].count("#")
      ans+=S[h][w-1:w+2].count("#")
      ans+=S[h+1][w-1:w+2].count("#")
      S[h][w]=ans

for h in range(1,1+H):
  print(*S[h][1:-1],sep="")

Measured memory_bytes: 9252
#![allow(unused_imports)]

use std::{i32, i64, u32, u64, usize, f64};
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::io::{stdout, Write, BufWriter};
use std::mem::{swap};
use maplit::*;
use proconio::marker::{Isize1, Usize1, Bytes, Chars};

#[proconio::fastout]
fn main() {
    proconio::input!(
        h: usize,
        w: usize,
        grid: [Chars; h],
    );
    let mut s = 0usize;
    for a in grid.into_iter().flatten() {
        if a == '#' { s += 1; }
    }
    if s == h + w - 1 { println!("Possible"); }
    else { println!("Impossible"); }
}


Measured memory_bytes: 2204
#include <stdio.h>

int main(void){
    int k, a, b;
    int ret = 0;

    scanf("%d %d %d", &k, &a, &b);
    
    for(int i = a; i <= b; ++i){
        if((i % k) == 0){
            ret = 1;
            break;
        }
    }

    if(ret == 1) printf("OK\n");
    else printf("NG\n");

    return 0;
}

Measured memory_bytes: 1632
n = int(input())
a = [0] * 5
for i in range(n):
  s = input()
  if s[0] == "M":
    a[0] += 1
  elif s[0] == "A":
    a[1] += 1
  elif s[0] == "R":
    a[2] += 1
  elif s[0] == "C":
    a[3] += 1
  elif s[0] == "H":
    a[4] += 1

res = 0
res += a[0] * a[1] * a[2]
res += a[0] * a[1] * a[3]
res += a[0] * a[1] * a[4]
res += a[0] * a[2] * a[3]
res += a[0] * a[2] * a[4]
res += a[0] * a[3] * a[4]
res += a[1] * a[2] * a[3]
res += a[1] * a[2] * a[4]
res += a[1] * a[3] * a[4]
res += a[2] * a[3] * a[4]
print(res)

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

using namespace std;

int main() {
    int N;
    cin >> N;
    map<int, int> mp;
    for (int i = 0; i < N; ++i) {
        int d;
        cin >> d;
        mp[d]++;
    }

    int M;
    cin >> M;
    for (int i = 0; i < M; ++i) {
        int t;
        cin >> t;
        if (mp[t] < 1) {
            cout << "NO" << endl;
            return 0;
        } else {
            mp[t]--;
        }
    }
    cout << "YES" << endl;
    return 0;
}


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

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 = 1LL << 60;
long long dp[101][4][4][4];

int main() {
    int N; cin >> N;
    dp[0][3][3][3] = 1;
    int mod = 1'000'000'007;

    for(int len = 0; len < N; len++) {
        for(int i = 0; i < 4; i++) {
            for(int j = 0; j < 4; j++) {
                for(int k = 0; k < 4; k++) {
                    if(dp[len][i][j][k] == 0) continue;
                    for(int a = 0; a < 4; a++) {
                        if(a == 2 && i == 1 && j == 0) continue;
                        if(a == 2 && i == 0 && j == 1) continue;
                        if(a == 1 && i == 2 && j == 0) continue;
                        if(a == 2 && i == 1 && k == 0) continue;
                        if(a == 2 && j == 1 && k == 0) continue;
                        dp[len+1][a][i][j] += dp[len][i][j][k];
                        dp[len+1][a][i][j] %= mod;
                    }
                }
            }
        }
    }

    int ans = 0;
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++) {
            for(int k = 0; k < 4; k++) {
                 ans += dp[N][i][j][k];
                ans %= mod;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
  int n, x, t;
  cin >> n >> x >> t;

  long long ans = ceil(n*1.0/x)*t;

  cout << ans;

  return 0;
}


Measured memory_bytes: 3616
#include "bits/stdc++.h"
using namespace std;


//wierd debugging stuff
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
//end of weird debugging stuff
using ll = long long;
using vi = vector<int>;
using ii = pair<int,int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
#define FASTER ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define invec(v) for(auto& x : v)cin>>x;
#define Test int T;cin>>T;while(T--)
#define REP(i,j,k) for(int i=(j);(i)<(k);(i)++)
#define Time()	cerr <<'\n' << clock() * 1000 / CLOCKS_PER_SEC << "ms\n"
#define SZ(x) (int)x.size();
#define all(x) x.begin,x.end()
// no change 

//const int MxN = 1e9+5;

int main() {
	string s;
	cin>>s;
	if(s[1] == 'B')s[1]='R';
	else s[1] = 'B';
	cout<<s;
	
	
	
	
}


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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define ld long double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll h; cin>>h;
    ll cnt=0;
    while(h/2){
        h/=2;
        cnt++;
    }
    ll ans=1;
    rep(i,cnt+1){
        ans*=2;
    }
    ans--;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
N,M = [int(x) for x in input().split()]

food_list=list(range(1,M+1))

for n in range(N):
  input_list=[int(x) for x in input().split()]
  Ans_list = input_list[1:]
  
  Check_list=[x for x in Ans_list if x in food_list]
  food_list = Check_list
  
print(len(Check_list))

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

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

const long long mod = 998244353;

// auto mod int
struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }

int main(){
    int n, k;
    cin >> n >> k;
    vi l(k), r(k);
    rep(i, k) cin >> l[i] >> r[i];
    vector<mint> dp(n+2);
    dp[1] = 1; dp[2] = -1;
    for (int h=1; h<n+1; ++h) {
        dp[h] += dp[h-1];
        rep(i, k) {
            dp[min(n+1,h+l[i])] += dp[h];
            dp[min(n+1,h+r[i]+1)] -= dp[h];
        }
    }
    cout << dp[n] << endl;
    return 0;
}


Measured memory_bytes: 4816
s = input()

for i in range(len(s)):
    if s[i] == "A":
        a = i
        break

s2 = s[-1:0:-1]
for j in range(len(s2)):
    if s2[j] == "Z":
        z = len(s)-1-j
        break

print(z-a+1)


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

int main(){
  string S;
  cin >> S;
  if(S == "Sunny") cout << "Cloudy" << endl;
  else if(S == "Cloudy") cout << "Rainy" << endl;
  else cout << "Sunny" << endl; 
}


 
 
 

Measured memory_bytes: 256
n=int(input())
s=[input() for i in range(n)]
m=int(input())
t=[input() for i in range(m)]
s2=dict()
t2=dict()
for i in range(n):
    if s[i] in s2:
        s2[s[i]]+=1
    else:
        s2[s[i]]=1
        t2[s[i]]=0
for i in range(m):
    if t[i] in t2:
        t2[t[i]]+=1
    else:
        t2[t[i]]=1
ans=0
for i in s2:
    ans=max(s2[i]-t2[i],ans)
print(ans)


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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << setprecision(20) << fixed;
  int N;
  cin >> N;
  vector<int> A(N);
  map<int, int> m;
  long long ans = 0;
  for(int i = 0; i < N; i++) cin >> A[i];
  //*
  for(int i = 1; i < N; i++){  
    int x = (A[0] + A[i]) - i;
    m[x]++;
  }
  int a = 0;
  ans += m[0];
  for(int i = 1; i < N; i++){  
    int x = (A[0] + A[i]) - i;
    m[x]--;
    a = -1 * ((A[i] - A[0]) + i);
    ans += m[a];
  }
  cout << ans <<endl;
  //*/
}


Measured memory_bytes: 21072
#include <stdio.h> // C++???????????????
#include <string.h> // c++???????????????
#include <math.h> // c++???????????????
#include <stdlib.h>
#include <iostream>
#include <string>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;

#define H 100
#define W 100
#define MAX(a,b) ((a>b)?(a):(b))

typedef long long int lli;

int main(void) {
	int h, w;
	int i, j,k;
	char f[H][W];
	int m[H][W];
	scanf("%d %d", &h, &w);

	for (i = 0; i < h; i++) {
		scanf("%s", f[i]);
		for (j = 0; j < w; j++) {
			m[i][j] = -1;
		}
	}

	for (i = 0; i < w; i++) {
		for (j = 0; j < h; j++) {
			for (k = w-1; k >=0; k--) {
				if (f[j][k] == 'c' && m[j][k] == -1) {
					m[j][k] = i;
				}
				if (f[j][k] == 'c') {
					if (k == w - 1)f[j][k] = '.';
					else {
						f[j][k + 1] = 'c';
						f[j][k] = '.';
					}
				}
			}
		}
	}

	for (i = 0; i < h; i++) {
		for (j = 0; j < w; j++) {
			if (j != w - 1)printf("%d ", m[i][j]);
			else printf("%d", m[i][j]);
		}
		printf("\n");
	}

	return 0;
}

Measured memory_bytes: 1244
#include<stdio.h>
#define N -1
#define MAX 100001
 
struct Node{
  int p,l,r;
};
 
struct Node T[MAX];
int A[MAX];
 
int dep(int);
int sib(int);
int deg(int);
int hei(int);
 
main(void){
  int P;
  int n;
  int i;
   
  scanf("%d",&n);
   
  for(i=0;i<n;i++){
    T[i].p=T[i].l=T[i].r=N;
  }
   
  for(i=0;i<n;i++){
    scanf("%d",&P);
    scanf("%d %d",&T[P].l,&T[P].r);
    T[T[P].l].p=P;
    T[T[P].r].p=P;
  }
   
  for(i=0;i<n;i++){
    A[i]=dep(i);
  }
   
  for(i=0;i<n;i++){
    printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, ",i,T[i].p, sib(i), deg(i),A[i],hei(i));   
    if(T[i].p==N) printf("root\n");
    else if(T[i].l!=N||T[i].r!=N)printf("internal node\n");
    else printf("leaf\n");
  }
  return 0;
}
 
 
int dep(int i){
  int c=0;
  while(T[i].p!=N){
    c=c+1;
    i=T[i].p;
  }
  return c;
}
 
 
int sib(int i){
  if(T[i].p==N) return N;
  if(T[T[i].p].r==i) return T[T[i].p].l;
  if(T[T[i].p].l==i) return T[T[i].p].r;
}
 
int deg(int i){
  int c=0;
  if(T[i].l!=N) c=c+1;
  if(T[i].r!=N) c=c+1;
  return c;
}
 
int hei(int i){
  int hl=0;
  int hr=0;
  if(T[i].l!=N) hl=hei(T[i].l)+1;
  if(T[i].r!=N) hr=hei(T[i].r)+1;
   
  if(hl<hr) return hr;
  else return hl;
}

Measured memory_bytes: 616
#include <stdio.h>
int main(void){
  int a,b,c;
  scanf("%d %d %d",&a,&b,&c);
  if(a<c){
    if(c<b){
      printf("Yes");
    }else{
      printf("No");
    }
  }else if(a>c){
    if(c>b){
      printf("Yes");
    }else{
      printf("No");
    }
  }else{
    printf("No");
  }
  return 0;
}

Measured memory_bytes: 128
MOD = int(1e9 + 7)
N = int(input())
A = list(map(int, input().split()))
rui = [A[0]]
for i in range(1,len(A)):
  rui.append((rui[-1]+A[i]) % MOD)


res = 0
for i in range(len(A)):
  res += A[i]*(rui[-1]-rui[i]) % MOD
  
print(res % MOD)
  

Measured memory_bytes: 31604
package main

import (
	"fmt"
)

func main() {
	var a,b,ans string
	fmt.Scan(&a,&b)
	
	if a == "H" { 
		if b == "H" { //HH
			ans = "H"
		} else { //HD
			ans = "D"
		}
	} else if a == "D" {
		if b == "H" { //DH
			ans = "D"
		} else { //DD
			ans = "H"
		}
	}
	fmt.Println(ans)
}

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


#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()

#define int long long

#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second

#define mod 1000000007

template <typename T>
void print(T x)
{
	std::cout << x <<" " ;
}


template <typename T>
void println(T x)
{
	std::cout << x << "\n";
}

signed main(void) {
	int h;
	cin >> h;
	if(h%2==0)	print(h / 2);
	else print(h / 2+1);
	
}

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

int main() {
  int c[3][3];
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      cin >> c[i][j];
    }
  }

  int a[3], b[3];
  a[0] = 0;
  for (int i = 0; i < 3; i++) {
    b[i] = c[0][i] - a[0];
  }
  for (int i = 0; i < 3; i++) {
    a[i] = c[i][0] - b[0];
  }

  bool ans = true;
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      if (a[i] + b[j] != c[i][j]) {
        ans = false;
        break;
      }
    }
  }

  cout << (ans ? "Yes" : "No") << endl;
}

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

struct hoge{
	int num, timem, times;
};

int main(){
	int n, c, m1, s1, m2, s2, m3, s3, m4, s4;
	hoge set[1000000];
	while(1){
		cin >>n;
		if(n == 0) break;
		for(int i = 0; i < n; i++){
			cin >>c >>m1 >>s1 >>m2 >>s2 >>m3 >>s3 >>m4 >>s4;
			set[i].num = c;
			set[i].timem = m1 + m2 + m3 + m4;
			set[i].times = s1 + s2 + s3 + s4;
			if(set[i].times >= 60){
				set[i].timem += set[i].times / 60;
				set[i].times %= 60;
			}
		}
		
		for(int i = 0; i < (n - 1); i++){
			for(int j = (i + 1); j < n; j++){
				if(set[j].timem < set[i].timem){
					swap(set[i].num, set[j].num);
					swap(set[i].timem, set[j].timem);
					swap(set[i].times, set[j].times);
				} else if(set[j].timem == set[i].timem){
					if(set[j].times < set[i].times){
						swap(set[i].num, set[j].num);
						swap(set[i].timem, set[j].timem);
						swap(set[i].times, set[j].times);
					}
				}
			}
		}
		
		cout <<set[0].num <<endl <<set[1].num <<endl <<set[n - 2].num <<endl;
	}
	return 0;
}

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


int main(){
    int count=0;
    char s[4];
    cin >>s;
    for(int i=0;i<3;i++){
        if(s[i]=='1') count+=1;
    }
    printf("%d\n",count);
}

Measured memory_bytes: 256
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] p = new int[n];
		int[] q = new int[n];
		for (int i = 0; i < n; i++) {
			p[i] = sc.nextInt();
		}
		for (int i = 0; i < n; i++) {
			q[i] = sc.nextInt();
		}

		int a = dfs(0, p, new HashSet<>(), false);
		int b = dfs(0, q, new HashSet<>(), false);
		System.out.println(Math.abs(a - b));
	}

	private static int dfs(int current, int[] a, Set<Integer> s, boolean smaller) {
		if (s.size() == a.length) return 1;
		int n = a.length;

		int x = 0;
		for (int i = 1; i <= n; i++) {
			if (a[current] < i && !smaller) continue;
			if (s.contains(i)) continue;
			s.add(i);
			x += dfs(current + 1, a, s, smaller || (a[current] > i));
			s.remove(i);
		}

		return x;
	}

}


Measured memory_bytes: 28436
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
MOD = 998244353
fac = [1, 1]
inv = [0, 1]
finv = [1, 1]
N,M,K = map(int,input().split())
for i in range(2, N+1):
    fac.append(fac[-1] * i % MOD)
    inv.append(MOD - inv[MOD%i] * (MOD//i) % MOD)
    finv.append(finv[-1] * inv[-1] % MOD) 
def comb_mod(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m
s = 0
for i in range(K+1):
    s += M*pow(M-1,N-1-i,MOD)*comb_mod(N-1,i,MOD)
    s %= MOD
print(s%MOD)

Measured memory_bytes: 50552
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int N,X;
    cin>>N>>X;
    vector<int> L(N);
    for(int i=0;i<N;++i)cin>>L[i];
    int ans = 1;
    int sum = 0;
    for(int i=0;i<N;++i){
        sum += L[i];
        if(sum<=X) ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cstring>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

int main() {
	int N, W; cin >> N >> W;
	vector<int> w(N);
	for (int i = 0; i < N; i++) cin >> w[i];
	sort(w.begin(), w.end(), greater<int>());
	vector< vector<ll> > dp(N + 1, vector<ll>(W + 1));
	fill(dp[0].begin(), dp[0].end(), 1);
	for (int i = 0; i < N; i++)
		for (int j = 0; j <= W; j++) {
			dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % 1000000007;
			int _j = j + w[i];
			if (_j <= W) dp[i + 1][_j] = (dp[i + 1][_j] + dp[i][j]) % 1000000007;
		}
	sort(w.begin(), w.end());
	vector<int> s(N + 1);
	for (int i = 0; i < N; i++) s[i + 1] = s[i] + w[i];
	ll ans = 0;
	if (s[N] <= W) ans = 1;
	for (int i = 0; i < N; i++) {
		ll x = 0;
		if (W - s[i] >= 0) x += dp[N - i - 1][W - s[i]];
		if (W - s[i] - w[i] >= 0) x -= dp[N - i - 1][W - s[i] - w[i]];
		ans = (ans + x) % 1000000007;
	}
	cout << (ans + 1000000007) % 1000000007 << endl;
}

Measured memory_bytes: 16844
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define x first
#define y second
#define ndl '\n'
#define mp make_pair
#define pb push_back
#define up_b upper_bound
#define low_b lower_bound
#define sz(x) (int)x.size()
#define bit __builtin_popcount
#define all(x) x.begin(),x.end()

using namespace std;
using namespace __gnu_pbds;

template<typename T> using indexed_set=tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<int,ull> piu;
typedef vector<vector<int>> matrix;

const ll INF=1e18+123;
const ld EPS=1e-9;
const int inf=1e9+123;
const int MOD=1e9+7;
const int N=5e5+123;
const int M=1e6+123;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};

bool b[N];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vector<int>ans;
    for(int it=1;it<=n;it++){
        for(int i=sz(a);i;i--){
            if(i==a[i-1]){
                a.erase(a.begin()+i-1);
                ans.pb(i);
                break;
            }
        }
    }
    reverse(all(ans));
    if(sz(a))cout<<-1;
    else{
        for(int x : ans)cout<<x<<ndl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr long long MOD = 1000000007;
constexpr long long INF = 1LL << 60;
const long double PI = acosl(-1.0);
constexpr long double EPS = 1e-11;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main(){
    ll a, b;
    cin >> a >> b;
    cout << max({a + b, a - b, a * b}) << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int n;
  scanf("%d",&n);
  double a,b=0,c=0,i;
  for(i=0;i<n;i++){
  scanf("%d",&a);
  b+=a;
  if(a>=c) c=a;
  }
  //printf("%d",c);
  b-=c;
  if(c>=b)printf("No\n");
  else printf("Yes\n");
}

Measured memory_bytes: 128
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main (String[] args) {
        Scanner input = new Scanner(System.in);
        
        while (input.hasNext()) {
            int N = input.nextInt();
            int[] h = new int[N];
            
            for (int i = 0; i < h.length; ++i) {
                h[i] = input.nextInt();
            }
            
            int[] cost = new int[h.length];
            cost[0] = 0;
            cost[1] = Math.abs(h[1] - h[0]);
            
            for (int i = 2 ; i < h.length; ++i) {
                cost[i] = Math.min(cost[i - 1] + Math.abs(h[i] - h[i - 1]), cost[i - 2] + Math.abs(h[i] - h[i - 2]));
            }
            
            System.out.println(cost[cost.length - 1]);
        }
    }
}


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

int a,b,c;
int main(){
  cin >> a >> b >> c;
  if (b < c){
    if (c-b <= a){
      cout << 2*b+(c-b);
    }
    else{
      cout << 2*b + a +1;
    }
  }
  else{
    cout << b+c;
  }
  
  return 0;
}
    
   

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define BIT(n) (1LL << (n))
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPB(i, n) for (int i = 0; i < BIT(n); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORA(i, n) for (auto &&i : n)
#define FORS(i, m, n) for (int i = m; i <= n; i++)
#define DEBUG(x) cerr << #x << ": " << x << "\n"
#define PRINTALL(V)                                                            \
  for (auto v : (V)) {                                                         \
    cerr << v << " ";                                                          \
  }                                                                            \
  cerr << "\n";
#define ALL(v) v.begin(), v.end()
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define epb emplace_back
#define int long long
using namespace std;
template < class T > bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template < class T > bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template < class T > using vec = std::vector< T >;
template < class T > void print(const T &x) { cout << x << "\n"; }
const int MOD = 1000000007, INF = 1061109567;
const double EPS = 1e-10, PI = acos(-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
signed main() {
  cin.tie(0), ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int H, W, N;
  cin >> H >> W >> N;
  vec< int > a(N);
  REP(i, N) { cin >> a[i]; }
  vec< vec< int > > T(H, vec< int >(W));
  int k = 0;
  REP(i, H) {
    REP(j, W) {
      if (a[k] == 0) {
        k++;
      }
      T[i][i % 2 == 0 ? j : (W - 1 - j)] = k + 1;
      a[k]--;
    }
  }
  REP(i, H) {
    REP(j, W) { cout << T[i][j] << " "; }
    cout << "\n";
  }
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//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; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

int main(){
    int N, M, X, Y; cin >> N >> M >> X >> Y;
    vector<int> x(N+1), y(M+1);
    for(int i=0; i<N; i++) cin >> x[i];
    x[N] = X;
    for(int i=0; i<M; i++) cin >> y[i];
    y[M] = Y;

    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    // for(int i=0; i<N+1; i++) printf("%d ", x[i]); cout << endl;
    // for(int i=0; i<M+1; i++) printf("%d ", y[i]); cout << endl;

    if(x[N] < y[0]) cout << "No War" << endl;
    else cout << "War" << endl;
}

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

using namespace std;

int main(){
    int x, y, a, b, c;
    cin >> x >> y >> a >> b >> c;
    vector<int64_t> P(a), Q(b), R(c);
    copy_n(istream_iterator<int64_t>(cin), a, P.begin());
    copy_n(istream_iterator<int64_t>(cin), b, Q.begin());
    copy_n(istream_iterator<int64_t>(cin), c, R.begin());
    nth_element(P.begin(), P.begin() + x, P.end(), greater<int64_t>());
    nth_element(Q.begin(), Q.begin() + y, Q.end(), greater<int64_t>());

    for (int i = 0; i < x; i++)
        R.push_back(P[i]);

    for (int i = 0; i < y; i++)
        R.push_back(Q[i]);

    nth_element(R.begin(), R.begin() + x + y, R.end(), greater<int64_t>());
    cout << accumulate(R.begin(), R.begin() + x + y, 0L) << endl;
}

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

int main(){
    int N,M,sum=0;
    cin >> N >> M;
    for(int i=0; i<M; i++){
        int x;
        cin >> x;
        sum+=x;
    }
    if(sum<=N){
        cout << N-sum << endl;
    }
    else{
        cout << -1 << endl;
    }
}

Measured memory_bytes: 3636
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<utility>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<math.h>
#include <map>
using namespace std;
typedef long long int ll;
#define repi(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,a) repi(i,0,a)
#define all(u) u.begin(),u.end()
#define pl pair<ll,ll>
#define fi first
#define se second
#define mod 1000000007
#define inf 1<<30
#define mp(a,b) make_pair(a,b)
#define len(u,N) u.begin(),u.begin()+N

ll N;
string s1;
string s2;


int main() {
    cin >> N;
    cin >> s1;
    cin >> s2;
    ll res = 1;
    ll active = 0;
    ll pre = 0;
    if (s1[active] == s2[active]){
        res *= 3;
        active++;
        pre = 0;
    }
    else{
        res *= 6;
        active += 2;
        pre = 1;
    }
    res %= mod;
    while(active < N){
        if (s1[active] == s2[active]){
            if (pre == 0){
                res *= 2;
                active++;
                pre = 0;
            }
            else{
                active++;
                pre = 0;
            }
        }
        else{
            if (pre == 0){
                res *= 2;
                active+=2;
                pre = 1;
            }
            else{
                res *= 3;
                active+=2;
                pre = 1;
            }
        }
        res %= mod;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MAX_N = 5e5+5;

string s;
ll ar[MAX_N];

void input() {
	cin >> s;
}

ll plu(ll to) {
	ll sum = 0;
	for(ll i=0;i<=to;i++) sum += i;
	return sum;
}

void solve() {
	ll n = s.size();
	vector<ll> ar;
	char c = s[0];
	ll cnt = 1;
	for(ll i=1;i<s.size();i++) {
		if(c == s[i]) cnt++;
		else {
			ar.push_back(cnt);
			cnt = 1;
			c = s[i];
		}
	}
	if(cnt>=1) {
		ar.push_back(cnt);
	}
	ll ars = (ll)ar.size();
	ll sum = 0;
	if(s[0]=='<') {
		for(ll i=0;i<ars-1;i+=2) {
			if(ar[i] < ar[i+1]) {
				ll key = ar[i];
				ll key2 = ar[i+1];
				sum += plu(key-1);
				sum += plu(key2);
			}else{
				ll key = ar[i];
				ll key2 = ar[i+1];
				sum += plu(key);
				sum += plu(key2-1);
			}
		}
	} else {
		sum += plu(ar[0]);
		for(ll i=1;i<ars-1;i+=2) {
			if(ar[i] < ar[i+1]) {
				ll key = ar[i];
				ll key2 = ar[i+1];
				sum += plu(key-1);
				sum += plu(key2);
			}else{
				ll key = ar[i];
				ll key2 = ar[i+1];
				sum += plu(key);
				sum += plu(key2-1);
			}
		}
	}
	if(ar.size()%2 == 1) {
		if(s[0]=='<') sum += plu(ar[ar.size()-1]);
	}
	if(ar.size()%2==0) {
		if(s[0]=='>') sum += plu(ar[ar.size()-1]);
	}
	cout << sum << endl;
}

int main(){
	input();
	solve();
}

Measured memory_bytes: 3068
#include<algorithm>
#include<iostream>
#include<stdio.h>
#include<iostream>
#include<stdio.h>
#include<vector>
#include<set>
#include<string>
#include<iomanip>
#include<queue>
#include<functional>
#include<cmath>
#include<map>
#include<tuple>
#define rep(i,n) for(int i=0; i<(int)n; i++)//n回繰り返す
#define rrep(i,n)for(int i=n-1;i>=0;i--)
#define REP(i,n) for (int i = 1; i <= (int)n; i++)//i=1からi=nまで
#define RREP(i,n)for(int i=n;i>=1;i--) 
using namespace std;
using ll = long long;
using P = pair<int, int>;
using graph = vector<vector<int>>;
const ll mod = pow(10, 9) + 7;
const int INF = 1e9;
const ll LINF = 1e18;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main() {
    int A, B, C; cin >> A >> B >> C;
    int K; cin >> K; int ans = 0;
    if (K <= A) {
        cout << K << endl;
    }
    else {
        if (K - A <= B) {
            cout << A << endl;
        }
        else {
            cout << A - (K - A - B) << endl;
        }
    }
}








   


Measured memory_bytes: 3632
#n=int(input())
n,m=map(int,input().split())
#pl=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

acdic={}
wadic={}
for i in range(n):
    acdic[i+1]=False
    wadic[i+1]=0

acnum=0
wanum=0
for i in range(m):
    p,s=map(str,input().split())
    p=int(p)
    if s=="AC" and acdic[p]==False :
        acnum+=1
        acdic[p]=True
        wanum+=wadic[p]
    else:
        wadic[p]=wadic[p]+1

print("{0} {1}".format(acnum,wanum))



Measured memory_bytes: 24212
import java.util.*;

public class Main {
        public static void main(String args[]) {
                Scanner sc = new Scanner(System.in);
                int x = sc.nextInt();
                int y = sc.nextInt();
                double a = (x + y) / 2.0;
                System.out.println((int)Math.ceil(a));
        }
}


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

using namespace std;
using ll = long long;

int main()
{
    ll a, b;
    cin >> a >> b;
    ll ans =(a + b);
    if (ans % 2 == 0){
        cout << ans / 2;
    } else {
        cout << "IMPOSSIBLE";
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;   
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define PI 3.14159265
#define ll long long
#define ld long double
#define vi vector<int>
#define pb push_back
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 300000000000000001
#define infx 9223372036854775806
#define all(c) c.begin(),c.end()
#define mk(x,yy) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define eb emplace_back
#define ff first
#define ss second
#define re return
// #define endl "\n"
#define max2(x,y)           (x>y)?x:y
#define min2(x,y)           (x<y)?x:y
#define mid(s,e)               (s+(e-s)/2)
#define mini                   INT_MIN
#define maxo                   INT_MAX
#define rep(i,a,b) for(int i=a;i<(int)(b);++i)
#define read(a,n) for(int i=0;i<n;i++)cin>>a[i]
#define show(a,n) for(int i=0;i<n;i++)cout<<a[i]<<' ';cout<<endl
#define ene cout<<"\n";

ll gcd(ll a, ll b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);  
      
}
ll power(ll x,  ll y, ll p) 
{ 
    ll res = 1;      // Initialize result 
  
    x = x % p;  // Update x if it is more than or  
                // equal to p 
  
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res*x) % p; 
  
        // y must be even now 
        y = y>>1; // y = y/2 
        x = (x*x) % p;   
    } 
    return res; 
} 
 
bool compr(std::vector<ll> a, std::vector<ll> b)
{
    if(a[0]==b[0])
        return a[1]<b[1];
    else
        return a[0]<b[0];
}

bool comp(std::vector<ll> a, std::vector<ll> b)
{
    if(a[1]==b[1]&&a[2]==b[2])
        return a[0]<b[0];
    else if(a[1]==b[1])
        return a[2]>b[2];
    else
        return a[1]<b[1];
}

double head[3000][3000];
int main()
{
    #ifdef SHIVANSH 
     freopen("input.txt","r",stdin);
     freopen("output.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    double a[n];
    for(ll i=0;i<n;i++)
    {
        cin>>a[i];
    }
    head[0][0] = 1-a[0];
    head[0][1] = a[0];
    for(ll i=1;i<n;i++)
    {
        for(ll j=0;j<=i+1;j++)
        {
            head[i][j] = head[i-1][j] * (1.0-a[i]);
            if(j>0)
                head[i][j] += head[i-1][j-1]*a[i];
        }
    }
    double ans = 0;
    for(ll i=n/2+1;i<=n;i++)
        ans+=head[n-1][i];
    cout<<fixed<<setprecision(10);
    cout<<ans<<endl;
}

Measured memory_bytes: 49912
#include <cstdio>
int a,b;
int main()
{
	scanf("%d%d",&a,&b);
	if(a==b)printf("%d",0);
	else 
	{
		if((a+b)%2==0)
			printf("%d",(a+b)/2);
		else printf("IMPOSSIBLE");
	}
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <string>

namespace Mylib{
    using namespace std;
    
    bool checkFiBu(int a){
        if(a%2!=0)return true;//検査対象外return
        if(a%3==0||a%5==0)return true;//検査OKreturn
        return false;//検査NGreturn
    }
    
}

int main(void){
    using namespace std;
    int N;
    cin >> N;
    int A[N];
    for(int i=0;i<N;i++)cin >> A[i];
    bool flag=true;
    
    for(int x:A){
        if(Mylib::checkFiBu(x)){
            
        }else{
            flag=false;
        }
    }
    if(flag==true){
        cout << "APPROVED" << endl;
    }else{
        cout << "DENIED" << endl;
    }
    
    return 0;

}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define int long long
#define p (int)(1e9 + 7)

int MOD(int a){
	a %= p;
	return a >= 0 ? a : a + p;
}

int power(int a, int N){
	if(N == 0){
		return 1;
	}
	else if(N % 2 == 0){
		return power(MOD(a * a), N / 2);
	}
	else{
		return MOD(a * power(a, N - 1));
	}
}

int inverse(int a){
	return power(a, p - 2);
}

int max(int a, int b){
	return a >= b ? a : b;
}

signed main(){
	int H, W, K, i, j, max_HW;
	scanf("%lld%lld%lld", &H, &W, &K);
	max_HW = max(H, W);
	char **s = (char **)malloc(sizeof(char *) * max_HW);
	for(i = 0; i < max_HW; i++){
		s[i] = (char *)malloc(sizeof(char) * (max_HW + 1));
	}
	for(i = 0; i < H; i++){
		scanf("%s", s[i]);
	}
	if(K == 0){
		printf("1\n");
		return 0;
	}
	int f_yoko = 0, f_tate = 0;
	for(i = 0; i < H; i++){
		if(s[i][0] == '#' && s[i][W - 1] == '#'){
			f_yoko = 1;
		}
	}
	for(j = 0; j < W; j++){
		if(s[0][j] == '#' && s[H - 1][j] == '#'){
			f_tate = 1;
		}
	}
	if(f_yoko == 1 && f_tate == 1){
		printf("1\n");
		return 0;
	}
	if(f_tate == 1){
		char tmp;
		for(i = 0; i < max_HW; i++){
			for(j = 0; j < max_HW; j++){
				if(i < j){
					tmp = s[i][j];
					s[i][j] = s[j][i];
					s[j][i] = tmp;
				}
			}
		}
		H ^= W;
		W ^= H;
		H ^= W;
	}
/*	for(i = 0; i < H; i++){
		for(j = 0; j < W; j++){
			printf("%c", s[i][j]);
		}
		printf("\n");
	}
*/	int x = 0, a = 0, b = 0, c = 0;
	for(i = 0; i < H; i++){
		int x_sub = 0;
		for(j = 0; j < W; j++){
			if(s[i][j] == '#'){
				x_sub++;
			}
		}
		int e = 0;
		for(j = 1; j < W; j++){
			if(s[i][j - 1] == '#' && s[i][j] == '#'){
				e++;
			}
		}
		if(x_sub == W){
			c++;
		}
		else{
/*			if(x_sub == 0){
				int O = 0;
				printf("%lld\n", H % O);
			}
*/			a += x_sub - e;
			if(s[i][0] == '#' && s[i][W - 1] == '#'){
				a -= 2;
				b++;
			}
		}
		x += x_sub;
	}
/*	if(a == 0 && b == 0 && c > 0 && f_yoko == 1 && f_tate == 0){
		int O = 0;
		printf("%lld\n", H % O);
	}
*/
//	printf("(x, a, b, c) = (%lld, %lld, %lld, %lld)\n", x, a, b, c);
	if(f_yoko == 0 && f_tate == 0){
		printf("%lld\n", power(x, K - 1));
	}
	else if(a == 0 && b == 0){
		printf("%lld\n", power(c, K - 1));
	}
	else{
		printf("%lld\n", MOD(MOD((a + b) * power(x, K - 1) + (x - (a + 2 * b + c)) * power(b + c, K - 1)) * inverse(x - (b + c))));
	}
	return 0;
}

Measured memory_bytes: 1152
#include <stdio.h>

int main(void)
{
        int a,b,w,s;
        scanf("%d%d%d",&w,&a,&b);

        s=a-b;
        if(s<0)s=-s;
        if(s<=w)printf("0\n");
        else printf("%d\n",s-w);
        return 0;
}


Measured memory_bytes: 1732
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

N = read_a_int()
A = read_ints()
# 直属の部下だから簡単
cnt = Counter(A)
for i in range(1, N + 1):
    print(cnt[i])


Measured memory_bytes: 123784
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = pair<ll, ll>;
const int INF = 0x3f3f3f3f;
int main() {
  int n, m;
  cin >> n >> m;
  if (m < n)
    cout << "No" << endl;
  else
    cout << "Yes" << endl;
}

Measured memory_bytes: 3576
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll cnt;
char s[200001] ;
inline ll read()
{
	char c=getchar();int a=1;ll ans=0;
	for(;c<'0'||c>'9';c=getchar())if(c=='-')a=-1;
	for(;c>='0'&&c<='9';c=getchar())ans=ans*10+int(c)-48;
	return a*ans;
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%s",&s);
	int ans=strlen(s);
	int nn=ans;
	char stan[200001];int top=0;
	for(int i=0;i<nn;i++)
	{
		if(s[i]=='T')
		{
			if(stan[top]=='S')
			{
				top--;
			}
			else
			{
				stan[++top]='T';
			}
		}
		else 
		{
			stan[++top]='S';
		}
	}
	/*
	for(int i=0;i<nn-1;i++)
	{
		int po=i+1;
		while(s[po]=='0')po++;
		if(po>nn)break;
		if(s[i]=='S'&&s[po]=='T')
		{
			ans-=2;
			s[i]=s[po]='0';
			int opp=i;
			i-=2;
			if(i<=(-2))
			{
				i=po;
			}
		}
	}
	*/
	cout<<top<<endl;
	return 0;
}
//SSTSTSTTSS 

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mod 1000000007
#define ll long long int
#define pi 3.141592653589793238

int main(){
	int x;
    cin>>x;
    cout<<!x<<endl;
    return 0;
}




Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
int n,m,i,a[1005];
float sum=0;


int main()
{
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++)scanf("%d",&a[i]);
	sort(a,a+n);//钻空子，它不要求输出第几项 
	
	for(i=0;i<n;i++)
		sum=sum+a[i];

	if (4*m*a[n-m]>=sum)printf("Yes");
	else printf("No");

	return 0;
}

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

ll mpow(ll a, ll b){
	if(b==0){
		return 1;
	}else if(b%2==0){
		ll memo = mpow(a,b/2);
		return memo*memo%MOD;
	}else{
		return mpow(a,b-1) * a % MOD;
	}
}

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

int main(void){
	int r;
	cin>>r;
	cout<<3*r*r<<endl;
	return 0;
}


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

int main() {
    int n, d;
    cin >> n >> d;
    set<int> res;
    for (int i = 1; i < 10000; i++) res.emplace(i * i);
    vector<vector<int>> a(n, vector<int>(d));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < d; j++) {
            cin >> a[i][j];
        }
    }
    
    auto check = [&] (int s, int t) {
        int dist = 0;
        for (int i = 0; i < d; i++) {
            dist += (a[s][i] - a[t][i]) * (a[s][i] - a[t][i]);
        }
        return (res.count(dist));
    };
    
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            ans += check(i, j);
        }
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 768
#include"bits/stdc++.h"
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;

void Main(){
    int n; cin >> n;
    
    int cnt = 0;
    rep(i, n){
        int x; cin >> x;
        if(((i+1)&1) && (x&1)) cnt++;
    }
    cout << cnt << endl;
    return;
}

int main(){
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}

Measured memory_bytes: 3624
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <queue>

using namespace std;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool dp[2][51][51][4];
bool fie[52][52][4];
int n,sx,sy,t;

int main(void){
	scanf("%d%d%d%d",&n,&sx,&sy,&t);
	memset(fie,false,sizeof(fie));
	for(int i=0;i<n;i++){
		int ax,ay,bx,by;
		scanf("%d%d%d%d",&ax,&ay,&bx,&by);
		if(ax>bx)swap(ax,bx);
		if(ay>by)swap(ay,by);
		if(ax==bx){
			fie[ay][ax][1]=true;
			for(int j=ay+1;j<by;j++){
				fie[j][ax][1]=true;
				fie[j][ax][3]=true;
			}
			fie[by][ax][3]=true;
		}else{
			fie[ay][ax][0]=true;
			for(int j=ax+1;j<bx;j++){
				fie[ay][j][0]=true;
				fie[ay][j][2]=true;
			}
			fie[ay][bx][2]=true;
		}
	}
	int prev=0,now=1;
	memset(dp,false,sizeof(dp));
	for(int i=0;i<4;i++){
		dp[0][sy][sx][i]=true;
	}
	for(int i=0;i<t;i++){
		int d,dir;
		char di;
		scanf("%d %c",&d,&di);
		if(di=='E')dir=0;
		if(di=='N')dir=1;
		if(di=='W')dir=2;
		if(di=='S')dir=3;
		for(int dd=0;dd<d;dd++){
			for(int j=0;j<=50;j++){
				for(int k=0;k<=50;k++){
					for(int l=0;l<4;l++){
						if(dp[prev][j][k][l]){
							for(int m=0;m<4;m++){
								if((m+2)%4==l)continue;
								int nx=k+dx[l],ny=j+dy[l];
								if(nx<0 || ny<0)continue;
								if(!fie[j][k][l] || !fie[ny][nx][m])continue;
								if(dd<d-1 || dir==m || dir==l)dp[now][ny][nx][m]=true;
							}
						}
					}
				}
			}
			swap(now,prev);
			memset(dp[now],false,sizeof(dp[now]));
		}
	}
	for(int j=0;j<=50;j++){
		for(int i=0;i<=50;i++){
			if(dp[prev][i][j][0] || dp[prev][i][j][1] || dp[prev][i][j][2] || dp[prev][i][j][3]){
				printf("%d %d\n",j,i);
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1064
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<bitset>
#include<math.h>
using namespace std;
#define INF 110000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<int,int> P;


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

  for(int i=1;i<=N;i++){
    if(i<=K) continue;
    //cout<<i<<endl;
    ans+=(N+1)/i*(i-K);
    int temp=(N+1)%i-K;
    if(temp>0) ans+=temp;
    //cout<<(N+1)/i*(i-K)<<" "<<temp<<endl;
    
  }
  if(K==0) ans-=N;
  cout<<ans<<endl;
}


Measured memory_bytes: 256