akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Linq;
using System.Collections.Generic;
using System.Text;



class B
{
    static int[,] G;
    static internal int n;
    const int INFTY = int.MaxValue;
    public static void Main() {
        n = int.Parse(Console.ReadLine());
        G = new int[n, n];
        for(int i = 0; i < n; i++) {
            for(int j=0;j<n; j++) {
                G[i, j] = INFTY;
            }
        }
        for (int i = 0; i < n; i++) {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
            for(int j = 0; j < input[1]; j++) {
                G[input[0], input[2 + j * 2]] = input[3 + j * 2];
            }
        }
        dijkstra();
    }

    public static void dijkstra() {
        var d = Enumerable.Repeat(INFTY, n).ToArray();
        var parent = Enumerable.Repeat(-1, n).ToArray();
        var Color = Enumerable.Repeat("WHITE", n).ToArray();
        d[0] = 0;
        Color[0] = "GRAY";
        while (true) {
            int mincost = INFTY;
            int u = -1;
            for (int i = 0; i < n; i++) {
                if (Color[i] != "BLACK" && d[i] < mincost) {
                    mincost = d[i];
                    u = i;
                }
            }
            if (u==-1) {
                break;
            }
            Color[u] = "BLACK";
            for (int v = 0; v < n; v++) {
                if (Color[v] != "BLACK" && G[u, v] != INFTY) {
                    if (d[u]+G[u,v] < d[v]) {
                        d[v] = d[u] + G[u, v];
                        parent[v] = u;
                        Color[v] = "GRAY";
                    }
                }
            }
            
        }
        for (int i = 0; i < n; i++) {
            Console.WriteLine(i + " " + (d[i] == INFTY ? -1 : d[i]));
        }
    }
}


Measured memory_bytes: 18292
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<assert.h>
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fo(i,a,b) for(int i=(a);i<=(b);++i)
#define fd(i,b,a) for(int i=(b);i>=(a);--i)
#define mset(a,x) memset(a,x,sizeof(a))
template<typename T> bool chkmin(T &a,const T &b) {return b<a?a=b,1:0;}
template<typename T> bool chkmax(T &a,const T &b) {return b>a?a=b,1:0;}
using namespace std;
typedef long long ll;
int read(){int n=0,p=1;char ch;for(ch=getchar();ch<'0' || ch>'9';ch=getchar())if(ch=='-') p=-1;for(;'0'<=ch && ch<='9';ch=getchar()) n=n*10+ch-'0';return n*p;}
const int N=2005,M=8e6,mo=1e9+7;
ll qmi(ll x,ll n)
{
	ll t=1;
	for(x%=mo;n;n>>=1,x=x*x%mo) if(n&1) t=t*x%mo;
	return t;
}
ll fac[M+5],inv[M+5],f[N][N];
ll C(ll m,ll n){return fac[m]*inv[n]%mo*inv[m-n]%mo;}
void inc(ll &x,ll y){x=(x+y)%mo;}
int n,m;
ll calc(ll m,ll n)
{
	return C(m+n-1,m-1);
}
int main()
{
	fac[0]=inv[0]=1;fo(i,1,M) fac[i]=fac[i-1]*i%mo;
	inv[M]=qmi(fac[M],mo-2);
	fd(i,M-1,1) inv[i]=inv[i+1]*(i+1)%mo;
	n=read(),m=read();
	if(m==1) return puts("1"),0;
	f[0][0]=1;
	fo(i,0,n)
	{
		fo(j,0,i)
		{
			if(j<i) inc(f[i][j+1],f[i][j]);
			inc(f[i+1][j],f[i][j]*calc(j+i*(m-1)+1,m-2)%mo);
		}
	}
	printf("%lld\n",f[n][n]*fac[n]%mo);
	return 0;
}

Measured memory_bytes: 155136
#include<iostream>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int A, B;
	cin >> A >> B;
	if (A + B > 4) {
		cout << 1 << endl;
	}
	else if (A + B > 3) {
		cout << 2 << endl;
	}
	else if (A + B == 3) {
		cout << 3 << endl;
	}


	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
using P = pair<ll,ll>;
constexpr ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REPS(i,n) for(ll (i)=1;(i)<=(n);(i)++)
#define RREP(i,n) for(ll (i)=(n-1);(i)>=0;(i)--)
#define RREPS(i,n) for(ll (i)=(n);(i)>0;(i)--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());

template<class T> inline void chmin(T& a, T b){
    if (a > b){
        a = b;
    }
}

template<class T> inline void chmax(T& a, T b){
    if (a < b){
        a = b;
    }
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(12);
    ll N;
    string S;
    cin >> N >> S;
    map<pair<string,string>,ll> m1;
    REP(i,1 << N){
        string A,B;
        ll C = i;
        REP(l,N){
            if(C % 2 == 1){
                A += S[l];
            }else{
                B += S[l];
            }
            C >>= 1;
        }
        reverse(ALL(A));
        reverse(ALL(B));
        m1[mp(B,A)]++;
    }
    map<pair<string,string>,ll> m2;
    REP(i,1 << N){
        string A,B;
        ll C = i;
        REP(l,N){
            if(C % 2 == 1){
                A += S[l+N];
            }else{
                B += S[l+N];
            }
            C >>= 1;
        }
        m2[mp(A,B)]++;
    }
    ll ans = 0;
    for(auto itr = m1.begin();itr != m1.end();itr++){
        ans += m2[itr->F]*(itr->S);
    }
    cout << ans << "\n";
}

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

using i64 = int64_t;

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> v;
    for(int i=0;i<n;++i){
        int a;
        cin >> a;
        v.push_back(a);
    }
    sort(v.begin(), v.end());
    vector<pair<int, int>> vp;
    int idx = 0, cnt = 1;
    while(idx < n){
        while(idx < n-1 && v[idx] == v[idx+1]){
            idx++; cnt++;
        }
        vp.emplace_back(cnt, v[idx]);
        cnt = 1;
        idx++;
    }
    sort(vp.begin(), vp.end());
    /*for(auto e: vp){
        cout << e.first << " " << e.second << endl;
    }*/
    int ans = 0;
    for(int i=0;i<(int)vp.size()-k;++i)ans += vp[i].first;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3188
#include <iostream>
#include<algorithm>
using namespace std;
struct node
{
    int t1;
    int val;
};
node a[10];
bool cmp(node x , node y)
{
    return x.t1 > y.t1;
}
int main()
{

    int t=0;
    for(int i=1;i<=5;i++)
    {
        cin>>a[i].val;
        a[i].t1 = a[i].val%10;
    }
    int bad = 0,bad_t=-1;
    sort(a+1,a+6,cmp);
    for(int i=1;i<=5;i++)
    {
        t += a[i].val;
        if(t%10!=0 && i<5){
            t = 10*(t/10) + 10;
        }
        if(a[i].t1 > 0){
            bad = a[i].val;
            bad_t = i;
        }
        //cout<<t<<endl;
    }
    if(bad_t == -1)
        cout<<t<<endl;
    else
    {
        if(bad_t == 5)
            cout<<t<<endl;
        else
        {
            int bad1 = 10*(bad/10)+10;
            //cout<<"bad1"<<bad1<<endl;
            t = t -bad1 + bad;
            cout<<t<<endl;
        }

    }
   // cout<<t<<endl;
    //cout << "Hello world!" << endl;
    return 0;
}


Measured memory_bytes: 256
import heapq

N, M = map(int, input().split())
A_B = []
for i in range(N):
    a, b = map(int, input().split())
    heapq.heappush(A_B, (a, b))

count = 0
price = 0
while count < M:
    a_b = heapq.heappop(A_B)
    count += a_b[1]
    price += a_b[1] * a_b[0]

print(price - (count-M)*a_b[0])

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

using namespace std;

typedef long long int64;
const int mod = 1e9 + 7;

inline int64 modPow(int64 x, int64 n)
{
  if(n == 0) return (1);
  int64 ret = modPow(x, n / 2);
  (ret *= ret) %= mod;
  if(n & 1) (ret *= x) %= mod;
  return (ret);
}

inline int64 modInv(int64 a)
{
  return (modPow(a, mod - 2));
}

int64 fact[202020], rfact[202020];

inline int64 modCombination(int p, int q)
{
  if(fact[0] == 0) {
    fact[0] = rfact[0] = 1;
    for(int i = 1; i < 202020; i++) {
      fact[i] = fact[i - 1] * i % mod;
      rfact[i] = modInv(fact[i]);
    }
  }
  if(q < 0 || p < q) return (0);
  return (fact[p] * rfact[q] % mod * rfact[p - q] % mod);
}

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }

  bool unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k)
  {
    return (-data[find(k)]);
  }
};

int main()
{
  int N, X, Y, C[200000], W[200000];
  vector< pair< int, int > > vs[200000];

  cin >> N >> X >> Y;
  for(int i = 0; i < N; i++) {
    cin >> C[i] >> W[i];
    --C[i];
    vs[C[i]].emplace_back(W[i], i);
  }


  UnionFind tree(N);
  vector< pair< int, int > > vv;
  for(int i = 0; i < N; i++) {
    if(vs[i].empty()) continue;
    sort(begin(vs[i]), end(vs[i]));
    for(int j = 1; j < vs[i].size(); j++) {
      if(vs[i][0].first + vs[i][j].first <= X) {
        tree.unite(vs[i][0].second, vs[i][j].second);
      }
    }
    vv.emplace_back(vs[i][0]);
  }

  if(vv.size() == 1) {
    cout << 1 << endl;
    return (0);
  }

  sort(begin(vv), end(vv));
  for(int i = 0; i < N; i++) {
    if(C[vv[0].second] != C[i]) {
      if(vv[0].first + W[i] <= Y) {
        tree.unite(vv[0].second, i);
      }
    } else {
      if(vv[1].first + W[i] <= Y) {
        tree.unite(vv[1].second, i);
      }
    }
  }

  modCombination(0, 0);

  map< int, int > mp[200000];
  for(int i = 0; i < N; i++) {
    ++mp[tree.find(i)][C[i]];
  }

  int64 sz = 1;
  for(int i = 0; i < N; i++) {
    if(tree.find(i) == i) {
      int all = 0;
      for(auto &p : mp[i]) (all += p.second) %= mod;
      int64 ret = fact[all];
      for(auto &p : mp[i]) (ret *= rfact[p.second]) %= mod;
      (sz *= ret) %= mod;
    }
  }
  cout << sz << endl;
}

Measured memory_bytes: 34676
l = list()
for i in range(5):
    l.append(int(input()))

a=int(input())
count=0

for i in range(5):
    for j in range(5):
        if l[i]-l[j]>a:
            count+=1
if count>0:
    print(":(")
else:
    print("Yay!")

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

int main()
{
    string s;
    int k;
    cin >> s >> k;
    int n = s.size();
    int count=0;
    for(int i=0;i<n;i++){
        if(s[i]=='1'){
            count++;
        }
        else{
            break;
        }
    }
    if(k<=count){
        cout<<1<<endl;
    }
    else{
        cout<<s[count]<<endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

int main() {
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i){
        cin >> v[i];
    }
    int ans = 1;
    for(int i = 0; i < n; ++i){
        ans *= 3;
    }
    int cur = 1;
    for(int i = 0; i < n; ++i){
        if(v[i] % 2 == 0){
            cur *= 2;
        }
    }
    cout << ans - cur << endl;
    return 0;
}

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

#define MAX 10000001
bool prime[MAX]={};
int yo[MAX]={};
int main(){

  prime[1] = true; prime[2] = false;
  for(int i=3;i<MAX;i++){
    if(!prime[i])
      for(int j=2;i*j<MAX;j++){
	prime[i*j] = true;
      }
  }
  
  for(int i=13;i<MAX;i++){
    if(!prime[i-8] && !prime[i-6] && !prime[i-2] && !prime[i]){
      yo[i] = i; 
    }
    else
      yo[i] = yo[i-1];
  }
  int n;
  while(1){
    cin >> n;
    if(n == 0) break;
    cout << yo[n] <<"\n";
  }  
}

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

int main() {
  int n, x, l, count = 0;
  scanf("%d", &n);
  vector<P> rs;
  rep(i, n) {
    scanf("%d %d", &x, &l);
    rs.push_back({x+l, x-l});
  }
  sort(rs.begin(), rs.end());
  int a = -100100100;
  for (auto r: rs) {
    if (a <= r.second) {
      a = r.first;
      count++;
    }
  }
  printf("%d\n", count);
  return 0;
}


Measured memory_bytes: 1400
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int a = scanner.nextInt(),b = scanner.nextInt();
		if(a == 1){
			a = 14;
		}
		if(b == 1){
			b = 14;
		}
		if(a < b){
			System.out.println("Bob");
		}else if(b < a){
			System.out.println("Alice");
		}else{
			System.out.println("Draw");
		}
	}

}


Measured memory_bytes: 22356
N = int(input())
A_list = list(map(int, input().split()))

zero_count = 0
minus_count = 0
total = 0
minimum = abs(A_list[0])
for i in range(len(A_list)):
    if A_list[i] == 0:
        zero_count += 1
    elif A_list[i] < 0:
        minus_count += 1

    total += abs(A_list[i])
    if A_list[i] != 0:
        minimum = min(minimum, abs(A_list[i]))
#   print("total:{} min:{} zero:{} minus:{}".format(total, minimum, zero_count, minus_count))

if minus_count % 2 == 0 or zero_count > 0:
    print(total)
else:
    print(total - minimum*2)


Measured memory_bytes: 14412
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(ll i=num, i##_len=(n); i<i##_len; ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define print(x) cout << (x) << endl;
#define sz(x) int(x.size())
 
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const ll LLINF = 1LL<<60;
const int INF = 1<<29;
const int MOD = 1000000007;
 
void add(long long &a, long long b) {
  a += b;
  if (a >= MOD) a -= MOD;
}
 
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};


int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    ll N, Z, W; cin >> N >> Z >> W;
    vector<ll> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    ll ans = abs(W - a[N-1]);
    if (N > 1) chmax(ans, abs(a[N-2] - a[N-1]));
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#define N 100

using namespace std;

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

	int A[N], n, cnt = 0;

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

	for(int i = 0; i < n; ++i) {
		for(int j = n-1; j > i; --j) {
			if(A[j] < A[j-1]) {
				int tmp = A[j];
				A[j] = A[j-1];
				A[j-1] = tmp;

				++cnt;
			}
		}
	}

	for(int i = 0; i < n; ++i) {
		if(i != 0) {
			cout << " ";
		}
		cout << A[i];
	}
	cout << endl;

	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 1200
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<string>

using namespace std;
int main(){
int N;
cin >>N;
int A[100001]={};//０で初期化、各値の数
int a;
for(int i=0;i<N;i++){
    cin >>a;
    A[a]++;//a階にあるをたす。
}
long long sum;
long long ans=A[0]+A[1];
for(int i=1;i<100000;i++){
sum=A[i-1]+A[i]+A[i+1];
ans=max(sum,ans);
}



cout << ans <<endl;


 return 0;
}
/*
7
3 1 4 1 5 9 2

4




*/

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <climits>

constexpr int SINT_MAX = std::numeric_limits<int>::max();
constexpr int SINT_MIN = std::numeric_limits<int>::min();

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

template<class T>
T choose(bool b, T t, T f)
{
    if (b) return t;
    else return f;    
}

const char *YesNo(bool b)
{
    return choose(b, "Yes", "No");
}

const char *YESNO(bool b)
{
    return choose(b, "YES", "NO");
}

template<template<class...> class ContT, class ValueT, size_t Dim>
struct vec_type
{
    using type = ContT<typename vec_type<ContT, ValueT, Dim-1>::type>;
};

template<template<class...> class ContT, class ValueT>
struct vec_type<ContT, ValueT, 0>
{
    using type = ValueT;
};

template<class ValueT, size_t Dim = 1>
using vec_t = typename vec_type<std::vector, ValueT, Dim>::type;


template<class ValueT, size_t Dim, class = typename std::enable_if<Dim == 0>::type>
auto make_vec(ValueT value = ValueT()) -> ValueT
{
    return value;
}

template<class ValueT, size_t Dim, class... Rest>
auto make_vec(size_t size0, Rest... rest)
{
    auto vec = make_vec<ValueT, Dim-1>(rest...);
    return std::vector(size0, vec);
}

int diffabs(int l, int r)
{
    if (l < r) return r-l;
    else return l-r;    
}


///////////////////////////////////////////////////

int main()
{
    ll A, V, B, W, T;
    cin >> A >> V >> B >> W >> T;

    ll dx = (A < B ? B - A : A - B);
    ll dv = V - W;

    bool ans = (dx == 0 || dv * T >= dx);
    cout << YESNO(ans) << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD = 998244353,MaxN = 300003;
LL n,a,b,k;

template<typename T> inline T gcd(T a,T b) {
    T r;
    while (b) {r=a%b;a=b;b=r;}
    return a;
}
template<typename T> inline LL lcm(const T& a,const T& b) { return (LL)a*b/gcd(a,b); }
template<typename T> T exgcd(const T& a,const T& b,T& x,T& y) {
    if (!b) return x=1,y=0,a;
    T g=exgcd(b,a%b,y,x);
    y=y-(a/b)*x;
    return g;
}
inline LL fastpow(LL a,LL p) {
    LL ret=1;
    while (p) {
        if (p&1) ret=ret*a%MOD;
        p>>=1;a=a*a%MOD;
    }
    return ret;
}
inline LL inv(const LL& x) {return fastpow(x,MOD-2);}

LL fac[MaxN],ifac[MaxN];

inline LL C(const int& n,const int& m) {return fac[n]*ifac[m]%MOD*ifac[n-m]%MOD;}

int main() {
    scanf("%lld%lld%lld%lld",&n,&a,&b,&k);
    if (n*a+n*b<k) return puts("0"),0;
    LL x,y,g;
    g=exgcd(a,b,x,y);
    if (k%g) return puts("0"),0;
    x*=k/g;y*=k/g;
    LL t=lcm(a,b),dx=t/a,dy=t/b;
    if (x<y) swap(a,b),swap(x,y),swap(dx,dy);
    if (y<0) {
        LL d=(-y+dy-1)/dy;
        y+=dy*d;
        x-=dx*d;
    }
    if (x>n) {
        LL d=(x-n+dx-1)/dx;
        x-=dx*d;
        y+=dy*d;
    }
    if (x>n || y>n) return puts("0"),0;
    fac[0]=fac[1]=1;
    for (int i=2;i<=n;++i) fac[i]=(fac[i-1]*i)%MOD;
    ifac[n]=inv(fac[n]);
    for (int i=n-1;i>=0;--i) ifac[i]=(ifac[i+1]*(i+1))%MOD;
    LL ans=0;
    while (x>=0 && y<=n) {
        ans+=C(n,x)*C(n,y)%MOD;
        ans%=MOD;
        x-=dx,y+=dy;
    }
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 5116
#include<iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <algorithm>

using namespace std;
int main()
{

	int i, j, N, A, B, tmp;
	A = 0;
	B = 0;
	int T[100] = { 0 };

	cin >> N;

	for (i = 0; i < 100; i++) {
		cin >> T[i] ;
	}

	for (i = 0; i < N; ++i) {
		for (j = i + 1; j < N; ++j) {
			if (T[i] < T[j]) {
				tmp = T[i];
				T[i] = T[j];
				T[j] = tmp;
			}
		}
	}

	j = 1;

	for (i = 0; i < N; i++) {
		j = j + 1;
		if(j%2 == 0){
			A = A + T[i];
		}
		else {
			B = B + T[i];
		}
		
	}

	A = A - B;
	
	cout << A;

	
	return 0;
}

Measured memory_bytes: 256
n = int(input())
cnt = 0

if n % 2 != 0:
    for x in range(1, n//2+1):
        if n % x == 0:
            cnt += n // x -1
        else:
            cnt += n // x 

else:
    for x in range(1,n//2):
        if n % x == 0:
            cnt += n // x -1
        else:
            cnt += n // x 

cnt += n // 2
print(cnt)

Measured memory_bytes: 63108
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <algorithm>
#include <bitset>
#include <complex>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include <cassert>
#include <functional>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template<typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

int N;
char L[SIZE];
ll dp[SIZE][2];

int main() {

  scanf("%s", L);
  N = strlen(L);

  dp[0][0] = 1;

  for (int i=0; i<N; i++) {
    if (L[i] == '0') {
      dp[i+1][0] = dp[i][0]; //00
      dp[i+1][1] = dp[i][1] * 3 % mod; //00, 01, 10
    } else {
      dp[i+1][0] = dp[i][0] * 2 % mod; //01, 10
      dp[i+1][1] = (dp[i][1] * 3 + dp[i][0]) % mod; // 00, 01, 10 / 00
    }
  }

  ll ans = (dp[N][0] + dp[N][1]) % mod;

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1920
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <string.h>
#include <math.h>
using namespace std;
#define ll long long                                    // long long省略
#define pb push_back                                    // push_back省略
#define mp make_pair                                    // make_pair省略
#define fi first                                        // first省略
#define se second                                       // second省略
#define itn int                                         // int誤字保険
#define count cout                                      // cout誤字保険
#define vecotr vector                                   // vector誤字保険
#define opt() cin.tie(0); ios::sync_with_stdio(false)   // 入出力速度改善

#define rep(i,l,r)for(ll i=(l);i<(r);i++)               // 範囲[l, r)で刻み1のfor文(順方向)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))         // 範囲[l, r)で刻みkのfor文(順方向)
#define rrep(i,l,r)for(ll i=(r-1);i>=(l);i--)           // 範囲[l, r)で刻み1のfor文(逆方向)
#define rrepp(i,l,r,k)for(ll i=(r-1);i>=(l);i-=(k))     // 範囲[l, r)で刻みkのfor文(逆方向)
#define all(x) (x).begin(), (x).end()                   // vectorのポインタ位置指定用
#define max(p,q)((p)>(q)?(p):(q))                       // max拡張
#define min(p,q)((p)<(q)?(p):(q))                       // min拡張
#define bit(n,m)(((n)>>(m))&1)                          // 変数nのm番目のbitを取り出す

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

int dy[]={0, 0, 1, -1};                                 // 4方向近傍
int dx[]={1, -1, 0, 0};                                 // 4方向近傍


/*
   upll : (a<b)なら-1, (a=b)なら0, (a>b)なら1
 downll : (a<b)なら1, (a=b)なら0, (a>b)なら-1

 const void* a : 型を縛らずにconstをつける(=変数aが読み込み専用の変数であることを明示する)
        (ll*)a : 変数aがconst long long *型であると明示する
*/
// int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
// int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
// void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
// void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}

#define INF ((1LL<<62)-(1LL<<31))
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p) pom(a,p-2,p)

int main() {
    long long N; cin >> N;
    long long res = INF;
    for (long long a = 1; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long b = N/a;
        res = min(res, b-1+a-1);
    }
    cout << res << endl;
}

Measured memory_bytes: 256
from collections import Counter

def main():

    S = list(input())
    head = S.pop(0)
    cList = []
    flag  = False
    flag1 = False
    flag2 = False

    if head == 'A':
        flag = True
    
    for i,j in enumerate(S[1:-1]):
        if j=='C':
            cList.append(i+1)
    if len(cList)==1:
        flag1=True
        S.pop(cList[0])
        
    if ''.join(S).islower():
        flag2 = True
    
    if flag and flag1 and flag2:
        print('AC')
    else:
        print('WA')


    
if __name__== "__main__":
    main() 











Measured memory_bytes: 38484
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include<algorithm>
#include<sstream>
#include<iomanip>


using namespace std;

const long long MOD_CONST = 1000000007;


int main() {

	int n;
	cin >> n;
	vector<long long> x(n);
	vector<long long> d(n);
	for (int i = 0; i < n; i++) {
		cin >> x[i];
		if (i > 0) {
			d[i - 1] = x[i] - x[i - 1];
			
		}
	}
	vector<long long>inv_mod(n);
	inv_mod[1] = 1;
	for (int i = 2; i < n; i++) {
		inv_mod[i] = (MOD_CONST - (inv_mod[MOD_CONST%i] * (MOD_CONST/i) % MOD_CONST))%MOD_CONST;
		
	}

	vector<long long> facto(n);
	facto[0] = 1;
	for (int i = 1; i < n; i++) {
		facto[i] = (facto[i - 1] * i)%MOD_CONST;
	}

	vector<long long> a(n);
	for (int i = 1; i < n; i++) {
		a[i] = (facto[n - 1] * inv_mod[i]) % MOD_CONST;
		
	}
	
	vector<long long> cnt(n);
	
	for (int i = 1; i < n; i++) {
		cnt[i] = (cnt[i - 1] + a[i]) % MOD_CONST;
		
	}
	

	long long sum = 0;
	for (int i = 1;i < n; i++) {
		sum = (sum + (cnt[i] * d[i - 1]) % MOD_CONST) % MOD_CONST;
	}

	cout << sum << endl;
}

Measured memory_bytes: 4992
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeSet;

import org.omg.Messaging.SyncScopeHelper;

public class Main {
	Scanner sc = new Scanner(System.in);
	public static void main(String[] args){
		new Main();
	}
	public Main(){
		new Test_100().doIt();
	}
	class Test_100{
		void doIt() {
			String strA = sc.next();
			String strB = sc.next();
			String strC = sc.next();
			int A = strA.length();
			int B = strB.length();
			int C = strC.length();
			if(strA.substring(A-1, A).equals(strB.substring(0, 1))) {
				if(strB.substring(B-1,B).equals(strC.substring(0, 1))) {
					System.out.println("YES");
				}else {
					System.out.println("NO");
				}
			}else {
				System.out.println("NO");
			}
		}
	}
}


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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	vector<bool>a(1e6+1,false);
	vector<int>b(1e6+1,0);
	for(int i=0;i<n;++i){
		int A; cin>>A;
		a.at(A)=true;
		++b.at(A);
	}
	for(int i=0;i<a.size();++i){
		if(a.at(i)){
			for(int j=i+i;j<a.size();j+=i){
				a.at(j)=false;
			}
		}
	}
	int ans=0;
	for(int i=0;i<a.size();++i){
		if(a.at(i)&&b.at(i)==1)++ans;
	}
	cout<<ans<<"\n"s;
}

Measured memory_bytes: 7164
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int num = 10001, num1 = 101;
int dp[num1][num];
int w[num1], v[num1];
int n, W;
int main() {
	cin >> n >> W;
	for (int i = 0; i < n; i++)
		cin >> v[i] >> w[i];
	memset(dp, 0, sizeof(dp));
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= W; j++) {
			if (w[i] > j) dp[i + 1][j] = dp[i][j];
			else dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i]);
		}
	cout << dp[n][W] << endl;
	return 0;
}

Measured memory_bytes: 7048
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

H, W = map(int, input().split())
S = [input() for _ in range(H)]

for i in range(H):
    for j in range(W):
        ok = False
        for dy, dx in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            y = i + dy
            x = j + dx
            if y < 0 or y >= H or x < 0 or x >= W:
                continue
            if S[i][j] == '.':
                ok = True
                continue

            if S[y][x] == '#':
                ok = True
        if not ok:
            print("No")
            exit()
print("Yes")



Measured memory_bytes: 9236
import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        long f = 0;

        for(int i = 0; i < N; i++){
            f += sc.nextInt() - 1;
        }

        System.out.println(f);
    }
}


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

public class Main {
  private static char getLastChar(String s) {
    return s.charAt(s.length() - 1);
  }
  
  private static boolean solve(String[] abc) {
    return getLastChar(abc[0]) == abc[1].charAt(0) && getLastChar(abc[1]) == abc[2].charAt(0);
  }
  
  private static void execute(ContestReader reader, PrintWriter out) {
    String[] abc = reader.next(3);
    out.println(solve(abc) ? "YES" : "NO");
  }
  
  public static void main(String[] args) {
    ContestReader reader = new ContestReader(System.in);
    PrintWriter out = new PrintWriter(System.out);
    execute(reader, out);
    out.flush();
  }
}

class ContestReader {
  private BufferedReader reader;
  private StringTokenizer tokenizer;
  
  ContestReader(InputStream in) {
    reader = new BufferedReader(new InputStreamReader(in));
  }
  
  public String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }
  
  public int nextInt() {
    return Integer.parseInt(next());
  }
  
  public long nextLong() {
    return Long.parseLong(next());
  }
  
  public double nextDouble() {
    return Double.parseDouble(next());
  }
  
  public String[] next(int n) {
    String[] array = new String[n];
    for (int i = 0; i < n; i++) {
      array[i] = next();
    }
    return array;
  }
  
  public int[] nextInt(int n) {
    int[] array = new int[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextInt();
    }
    return array;
  }
  
  public long[] nextLong(int n) {
    long[] array = new long[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLong();
    }
    return array;
  }
  
  public double[] nextDouble(int n) {
    double[] array = new double[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextDouble();
    }
    return array;
  }
  
  public char[] nextCharArray() {
    return next().toCharArray();
  }
  
  public int[][] nextInt(int n, int m) {
    int[][] matrix = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextInt();
      }
    }
    return matrix;
  }
  
  public long[][] nextLong(int n, int m) {
    long[][] matrix = new long[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextLong();
      }
    }
    return matrix;
  }
  
  public double[][] nextDouble(int n, int m) {
    double[][] matrix = new double[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextDouble();
      }
    }
    return matrix;
  }
  
  public char[][] nextCharArray(int n) {
    char[][] matrix = new char[n][];
    for (int i = 0; i < n; i++) {
      matrix[i] = next().toCharArray();
    }
    return matrix;
  }
}


Measured memory_bytes: 23252
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> V;
#define rep(cnt,e) for(ll cnt=0;cnt<e;cnt++ )
#define allsort(X) sort(X.begin(),X.end())

typedef pair<ll,ll> P;
const ll mod = 1e9+7;
const ll INF = INT64_MAX;






ll i,j,k;


int main(){
    string S;
    cin>>S;
    rep(i,3)cout<<S[i];
    cout<<endl;
}

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

int main() {
    int ans = 0;
    int N;
    cin >> N;
    vector<int> B(N - 1);
    for(int i = 0; i < N - 1; i++) {
        cin >> B[i];
    }
    vector<int> A(N, 1000000);
    for(int i = N - 2; i >= 0; i--) {
        A[i + 1] = min(A[i + 1], B[i]);
        A[i] = min(A[i], B[i]);
    }
    ans = accumulate(A.begin(), A.end(), 0);
    cout << ans << endl;
}

Measured memory_bytes: 3600
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int N = Integer.parseInt(s.nextLine());
        List<Integer> hs = Arrays.asList(s.nextLine().split(" ")).stream().map(Integer::parseInt)
                .collect(Collectors.toList());
        int count = 0;
        for (int i = 0; i < N;) {
            if (hs.get(i) == 0) {
                i++;
                continue;
            }
            for (int j = i; j < N; j++) {
                if (hs.get(j) == 0) {
                    break;
                }
                hs.set(j, hs.get(j) - 1);
                // System.out.println("ひいたあと" + hs);
            }
            count++;
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 29012
#include <iostream>
#include <vector>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <regex>
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int,int>;
using pl4 = pair<ll,ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using vvs = vector<vs>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vpl4 = vector<pl4>;
using vvpl4 = vector<vpl4>;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define rFOR(i,a,b) for(int i=(b);i>=(a);i--)
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) sort((a).rbegin(),(a).rend())
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end())
#define PREVP(a) prev_permutation((a).begin(),(a).end())
#define NEXTP(a) next_permutation((a).begin(),(a).end())
#define yn(a) cout <<((a)?"yes":"no")<<endl;
#define Yn(a) cout <<((a)?"Yes":"No")<<endl;
#define YN(a) cout <<((a)?"YES":"NO")<<endl;
#define Say(a) cout <<(a);
#define Sal(a) cout <<(a)<<endl;
#define dbg(a) cout <<(#a)<<": "<<(a)<<endl;
#define a2l(a) ((ll)(a-97))
#define A2l(a) ((ll)(a-65))
#define l2a(a) ((char)(a+97))
#define l2A(a) ((char)(a+65))
#define dNum2(a) ((llabs(a)==0)?(1):((ll)(log2(double(llabs(a))))+1))
#define dNum10(a) ((llabs(a)==0)?(1):((ll)(log10(double(llabs(a))))+1))

#define int ll

const ll MOD = 1e9+7;
const string alpha = "abcdefghijklmnopqrstuvwxyz";
const string ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}
ll min(ll a, ll b){if(a>=b) return b;if(a<b) return a;}
ll max(ll a, ll b){if(a>=b) return a;if(a<b) return b;}

ll dSum10(ll n){
    ll m=0;
    FOR(i,0,dNum10(n)-1){
        m+=(ll)((llabs(n)%(ll)(pow(10.0,(double)(i+1))))/(ll)(pow(10.0,(double)i)));
    }
    return m;
}

ll isP(ll n){
    if(n<=1) return 0;
    FOR(i,2,(ll)sqrt(n)){
        if(n%i==0) return 0;
    }
    return 1;
}

ll BinS(vll a,ll b){
    ll min=0,max=a.size()-1,mid=0;;
    while(1){
        mid=(min+max)/2;
        if(a[min]==b) return min;
        if(a[mid]==b) return mid;
        if(a[max]==b) return max;
        if(max-min<=2) return -1;
        if(a[mid]<b) min=mid;
        if(a[mid]>b) max=mid;
    }
}

//seiki
//#include <regex>
/*bubun*/
//regex_search("u32", regex("[0-9]"));      // true
/*kanzen*/
//regex_match("u32", regex("(i|u)\\d+"));   // true

signed main() {
    
    ll N,K;
    cin >>N>>K;
    vll A(N);
    FOR(i,0,N-1){
        cin >>A[i];
    }
    Sal((ll)((N-1)/(K-1))+((N-1)%(K-1)!=0));
    
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;
const ll INF = 1e16;

void solver(ull &N, ull &M, ull &ans){

    ull loc_N = N, loc_M = M;
    ull S_req;
    S_req = loc_N*2;
    
    if(S_req <= loc_M){
        ans += loc_N;
        loc_M -= S_req;

        ans += loc_M/4;
    }
    else{
        ans += loc_M/2;
    }
    return;
}

int main(){

    ull N, M;
    cin >> N >> M;

    ull ans{};
    solver(N, M, ans); 

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

Measured memory_bytes: 3628
/**
  * @brief atcoder
  * @author yao
  */
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <utility>
#include <algorithm>
#include <functional>
#include <climits>
#define ft first
#define sd second
#ifdef DBG
#   define dbg_pri(x...) fprintf(stderr,x)
#else
#   define dbg_pri(x...) 0
#   define NDEBUG
#endif //DBG
#include <cassert>

typedef unsigned int uint;
typedef long long int lli;
typedef unsigned long long int ulli;

int main()
{
    int n;
    lli a, b, x;
    scanf("%d%lld%lld", &n, &a, &b), x = a^b;
    for(int i=2; i<n; ++i)
    {
        lli k;
        scanf("%lld", &k), x^=k;
    }
    lli ans = 0;
    while(x)
    {
        lli k = LLONG_MAX;
        for(lli i=1ll<<62;i;i>>=1)if(i&x)
        {
            k = std::min(i-1&a,i-1&~b)+1;
            break;
        }
        if(k>=a) break;
        x ^= a^b;
        a-=k, b+=k, ans+=k;
        x ^= a^b;
    }
    if(x) return puts("-1"), 0;
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 1692
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class T> istream& operator>>(istream& is,vector<T>& v) { for(T& t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream& os,const vector<T>& v) { for(T t:v){os<<t<<" ";} os<<"\n"; return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
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;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n;
    cin >> n;
    vi d(n);
    cin >> d;
    sort(all(d));
    cout << d[n/2]-d[n/2-1] << endl;
}

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

ll modPow(ll a, ll n) {
  if (n == 0) return 1; // 0乗にも対応する場合
  if (n == 1) return a % MOD;
  if (n % 2 == 1) return (a * modPow(a, n - 1)) % MOD;
  ll t = modPow(a, n / 2);
  return (t * t) % MOD;
}


int main(){
  ll X,Y;
  cin >> X >> Y;
  if(abs(X-Y)<2){
    cout << "Brown" << endl;
  }else{
    cout << "Alice" << endl;
  }
  
  
                     
                     
    
 
      
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
#define REP(i, n) for (Int i = 0, max_i = (n); i < max_i; i++)
#define REPI(i, a, b) for (Int i = (a), max_i = (b); i < max_i; i++)
#define ALL(obj) begin(obj), end(obj)
#define RALL(obj) rbegin(obj), rend(obj)
#define fi first
#define se second
using ii = pair<Int, Int>;
template <class T> inline bool chmax(T& a, const T& b) {
    if (a >= b) return false;
    a = b;
    return true;
}
template <class T> inline bool chmin(T& a, const T& b) {
    if (a <= b) return false;
    a = b;
    return true;
}
struct SetupIO {
    SetupIO() { cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }
} setup_io;

template <template <class, class...> class TT, class... Args>
ostream& operator<<(ostream& out, TT<Args...> const& cont) {
    for (auto&& elem : cont) out << elem << " ";
    return out;
}
template <class T> ostream& operator<<(ostream& out, const vector<vector<T>>& vs) {
    for (auto&& v : vs) cout << v << endl;
    return out;
}
template <class T1, class T2> ostream& operator<<(ostream& out, pair<T1, T2> const& val) {
    return (out << "{" << val.first << " " << val.second << "}");
}

void dump_func() { cerr << endl; }
template <class Head, class... Tail> void dump_func(Head&& h, Tail&&... t) {
    cerr << h << (sizeof...(Tail) == 0 ? "" : ", "), dump_func(forward<Tail>(t)...);
}
#ifdef _MY_DEBUG
#define dump(...)                                                                                                    \
    cerr << "/* " << #__VA_ARGS__ << " [" << __LINE__ << ":" << __FUNCTION__ << "]" << endl, dump_func(__VA_ARGS__), \
        cerr << "*/\n\n";
#else
#define dump(...)
#endif

/**
 *    author:  knshnb
 *    created: CREATED_TIMESTAMP
 **/

signed main() {
    Int n, K;
    cin >> n >> K;
    vector<Int> a(n + 1);
    REP(i, n) cin >> a[i + 1], a[i + 1]--;
    REP(i, n)(a[i + 1] += a[i]) %= K;
    map<Int, Int> mp;
    Int ans = 0;
    REP(i, n + 1) {
        if (i - K >= 0) mp[a[i - K]]--;
        ans += mp[a[i]];
        mp[a[i]]++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 14336
#include <iostream>

int main()
{
	int h, w;
	std::cin >> h >> w;
	for( int i = 0; i < w + 2; i++ ) {
		std::cout << '#';
	}
	std::cout << std::endl;

	for( int i = 0; i < h; i++ ) {
		for( int j = 0; j < w; j++ ) {
			if( j == 0 ) {
				std::cout << '#';
			}

			char a;
			std::cin >> a;
			std::cout << a;

			if( j == w - 1 ) {
				std::cout << '#' << std::endl;
			}
		}
	}

	for( int i = 0; i < w + 2; i++ ) {
		std::cout << '#';
	}
	std::cout << std::endl;

	return 0;
}


Measured memory_bytes: 256
use std::io::Read;
use std::collections::{VecDeque, HashSet};

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: usize = iterator.next().unwrap().parse().unwrap();
    let m: usize = iterator.next().unwrap().parse().unwrap();
    let p: Vec<usize> = (0..n).map(|_| iterator.next().unwrap().parse::<usize>().unwrap() - 1).collect();
    let mut graph: Vec<Vec<usize>> = vec![Vec::new(); n];
    for _ in 0..m {
        let xi: usize = iterator.next().unwrap().parse().unwrap();
        let yi: usize = iterator.next().unwrap().parse().unwrap();
        graph[xi - 1].push(yi - 1);
        graph[yi - 1].push(xi - 1);
    }

    let mut ans: usize = 0;
    let mut visited: Vec<bool> = vec![false; n];
    for i in 0..n {
        if visited[i] {
            continue;
        }
        let mut q: VecDeque<usize> = VecDeque::new();
        q.push_back(i);
        visited[i] = true;
        let mut nodes = HashSet::new();
        let mut numbers = HashSet::new();
        nodes.insert(i);
        numbers.insert(p[i]);
        if i == p[i] {
            ans += 1;
        }
        while let Some(u) = q.pop_front() {
            for &node in &graph[u] {
                if visited[node] {
                    continue;
                }
                q.push_back(node);
                visited[node] = true;
                let number = p[node];
                if node == number {
                    ans += 1;
                }
                if numbers.contains(&node) {
                    ans += 1;
                }
                if nodes.contains(&number) {
                    ans += 1;
                }
                numbers.insert(number);
                nodes.insert(node);
            }
        }
    }
    ans.to_string()
}


Measured memory_bytes: 13600
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <limits.h>
#include <iostream>

using namespace std;

int main()
{
	long long i, j = 0, ans[30] = { 0 }, N;
	cin >> N;

	if (N == 0) {
		cout << 0 << endl;
		return 0;
	}

	for (i = 0; N!=0; i++) {
		if (N < 0) {
			ans[i] = -N % 2;

			if (-N % 2)
				N = (-N / 2) + 1;
			else
				N = -N / 2;
		}
		else {
			ans[i] = N % 2;
			N /= -2;
		}

		j++;
	}

	for (i = j-1; i>=0; i--)
		cout << ans[i];

	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<stdio.h>
using namespace std;
int main(void){
    // Here your code !
float n,a=0,b=0;
cin>>n;
a=n;
b=n;
while(cin>>n){
cin>>n;
if(n>=a) a=n;
else if(n<b) b=n;
}
printf("%.1f\n",a-b);
return 0;
}

Measured memory_bytes: 1236
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  long long N;
  cin >> N;
  vector<long long> A(100009);
  for(int i=1;i<=N;i++){cin >> A[i];}
  long long count=0;
  for(int i=1;i<N;i++){
    if(A[i]<=A[i+1]){count+=A[i]; A[i+1]-=A[i];}
    else{
      count+=A[i]/2;
      if(A[i]%2==1 && A[i+1]>0){count++; A[i+1]--;}
    }
  }
  count+=A[N]/2;
  cout << count << endl;
}

Measured memory_bytes: 1152
// The moment you think of giving up you have already lost the battle
#include <iostream>
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long int ll;
typedef long double dl;
#define PI  3.14159265358979323846
#define Mod 1000000007
ll fast(ll n,ll a,ll m)
{
    if(n==0)
        return 1;
    else if(n==1)
        return a;
    else
    {
        ll r=fast(n/2,a,m);
        if(n%2==0)
        {
            return (((r%m)*(r%m))%m);
        }
        else
        {
            return (((((r%m)*a)%m)*r)%m);
        }
    }
}

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

}


Measured memory_bytes: 3628
N=int(input())
A=list(map(int,input().split()))
x=sum(A)
y=10**19
a=0
for i in range(N):
    a+=A[i]
    if y>abs(x-2*a):#2区間の差
        y=abs(x-2*a)
        
    else:
        break

print(y)

Measured memory_bytes: 25508
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <cassert>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s); sin>>v; return v;}
template<class T> inline string toString(T x) {ostringstream sout; sout << x; return sout.str();}
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define EACH(t,i,c) for(t::iterator i=(c).begin(); i!=(c).end(); ++i)
const double EPS = 1e-10;
const double PI = acos(-1.0);


typedef vector<pii> vp;


int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
int main(){
	int n;
	while(cin>>n,n){
		map<pii,vp> g;
		map<pii,vi> type;
		map<pii,int> hf;
		REP(i,n){
			int x,y;
			char d;
			cin>>x>>y>>d;
			int dir=(d=='x'?2:3);
			pii c=make_pair(y,x);
			pii n=make_pair(y+dy[dir],x+dx[dir]);

			g[c]=vp();
			type[c]=vi();
			g[c].push_back(n);
			type[c].push_back(1);
			hf[c]=-1;

			g[n]=vp();
			type[n]=vi();
			g[n].push_back(c);
			type[n].push_back(1);
			hf[n]=-1;

			REP(j,2){
				REP(k,4){
					pii base=(j==0?c:n);
					pii neighbor=make_pair(base.first+dy[k],base.second+dx[k]);
					if(EXIST(g,neighbor)&&find(ALL(g[base]),neighbor)==g[base].end()){
						g[base].push_back(neighbor);
						type[base].push_back(0);
						g[neighbor].push_back(base);
						type[neighbor].push_back(0);
					}
				}
			}
		}

		bool ok=true;
		queue<pii> q;
		for(map<pii,vp>::iterator it=g.begin();it!=g.end();it++){
			if(hf[(*it).first]==-1){
				q.push((*it).first);
				hf[(*it).first]=0;
				while(!q.empty()){
					pii cur=q.front();q.pop();
					int cur_hf=hf[cur];
					REP(i,g[cur].size()){
						pii next=g[cur][i];
						int next_hf=(cur_hf+type[cur][i])%2;
						if(hf[next]==-1){
							hf[next]=next_hf;
							q.push(next);
						}else if(hf[next]==next_hf){
						}else{
							ok=false;
							goto end;
						}
					}
				}
			}
		}
end:
		cout<<(ok?"Yes":"No")<<endl;
	}
}

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

inline int sosu(int x)
{
  int i=2;
  while(i<x)
  {
    if(x%i==0)
      return 0;
    i++;
  }
  return 1;
}

int main()
{
  int x;
  cin >> x;
  while(1)
  {
    if(sosu(x)==1)
    {
      cout << x << endl;
      break;
    }
    x++;
  }
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main (void) {
    int a, b;
    int t;

    scanf ("%d %d", &a, &b);

    if (a<b) {
        t = a;
        a = b;
        b = t;
    }
    
    for (; a%b!=0;) {
        t = a%b;
        a = b;
        b = t;
    }

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

    return 0;
}


Measured memory_bytes: 2064