akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
public class Main {
 
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		int k=stdIn.nextInt();
		int a=stdIn.nextInt();
		int b=stdIn.nextInt();
		int x=0;
		
		for(int i = a;i<=b;i++) {
			if(i%k==0) {
				x=1;
				break;
			}
		}
		
		if(x==1) {
			System.out.println("OK");
		}
		else {
			System.out.println("NG");
		}
 
	}
 
}

Measured memory_bytes: 35636
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

int main() {
  int x, y, s;
  while (scanf("%d %d %d", &x, &y, &s) > 0 && x && y && s) {
    x += 100; y += 100;
    int ans = 0;
    FOR(i, 1, s - 1) {
      FOR(j, 1, s- 1) {
        int v1 = i * x / 100;
        int v2 = j * x / 100;
        if (v1 + v2 != s) { continue; }
        int sum = i * y / 100 + j * y / 100;
        ans = max(ans, sum);
      }
    }
    printf("%d\n", ans);
  }
}

Measured memory_bytes: 1188
#include <stdio.h>

//Compiler version gcc  6.3.0

int main()
{
  long long int n;
  long long int count=0,max=0,i,k,j;
  scanf("%lld",&n);
  long long int a[n];
  for(i=0;i<n;i++)
    scanf("%lld",&a[i]);
  for(i=0;i<n-1;i++)
  {
    k=i;
    j=i+1;
      while(a[k]>=a[j])
      {
        k++;
        count++;
        j++;
      }
    if(count>max)
      max=count;
    count=0;
  }
  printf("%lld",max);
  return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
/*
1(1)=0

2(1)=0
2(2)=1

3(1)=0
3(2)=2
3(3)=1

4(1)=0
4(2)=1
4(3)=2
4(4)=1

15(1) =0 
15(2) =4 1111 //Bit探索と一緒
15(3) =3 120
15(4) =6 33
15(5) =3 30
15(6) =5 23
15(7) =3 21
15(8) =8 17
15(9) =7 16
15(10)=6 15
15(11)=5 14
15(12)=4 13
15(13)=3 12
15(14)=2 11
15(15)=1
15(16)=15

16(1) =0
16(2) =1 10000
16(3) =4 121
16(4) =1 100
16(5) =4 31
16(6) =6 24
16(7) =4 22
16(8) =2 20
16(9) =8 17
16(10)=7 16
16(11)=6 15
16(12)=5 14
16(13)=4 13
16(14)=3 12
16(15)=2 11
16(16)=1 10
16(17)=16

(N+1)/2までは解答は出る。最小とは限らない

Nたしかめるの間に合わない
Mでふやしていっても、結局N
root(N)まで全探索
root(N)以降は、絶対2桁
f(N,S)=pb+q
pとqを求める。
p<root(N)だから探索できる
p+q=S
5だとして
pとqを0からroot(N)未満まで探索？

15
1
が15じゃない

*/
int main(){
  ll N,S; cin>>N>>S;
  if(N==S){
    cout<<N+1<<endl;
    return 0;
  }
  if(S>N){
    cout<<-1<<endl;
    return 0;
  }
  ll end=sqrt(N);
  for(ll i=2; i<=end; i++){
    ll ii=N,tmp=0;
    while(ii>0){
      tmp+=ii%i;
      ii/=i;
    }
    if(tmp==S){
      cout<<i<<endl;
      return 0;
    }
  }
  //b=root(n)以降 N=pb+q, p,q<b, s=p+q, N=pb+(s-p); p,bが動く
  //N=pb+(s-p) >= pb > p^2, p<b
  //pからbが決まる？ああ、きまる
  //10の位はなるべく大きいほうがbが小さい
  for(ll p=min(end,S); p>0; p--){
    ll n=N-(S-p);
    if(n%p>0) continue;
    ll b=n/p;
    if(b<=end || S-p>=b) continue;
    cout<<b<<endl;
    return 0;
  }
  cout<<-1<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define lf long double
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef pair <ll,ll> ii;
typedef vector <ll> vi;
typedef vector <ii> vii;
typedef vector <bool> vb;
typedef vector <vector <ll> > vv;
typedef vector <vector <vector<ll> > > vvv;
typedef vector <string> vs;
typedef vector <lf> vf;
#define tr1(x) cerr << #x << ": " << x << endl
#define tr2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl
#define tr3(x,y,z) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trv(a) cerr<<#a<<":\n";for(ll zz=0;zz<a.size();zz++) cerr<<a[zz]<<" ";cerr<<endl
#define mod 1000000007ll
#define inf 9999999999999999ll

void solve()
{
    int n,k;
    cin>>n>>k;
    ll min_val;
    ll max_val;
    ll ans = 0;
    for(int i = k ; i <= n+1 ; i++)
    {
        min_val = (1ll*(i-1)*(i))/2;
        max_val = (1ll*(i)*(2ll*n-i+1))/2;
        // cout<<max_val<<" "<<min_val<<endl;
        ans += (max_val-min_val+1)%mod;
    }
    ans %= mod;
    cout<<ans<<endl;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    // cin>>t;
    t = 1;
    while(t--)
    solve();
    return 0;
}


Measured memory_bytes: 3660
#include<string>
#include<iostream>
#include<vector>

using namespace std;

vector<string> split(const string& s, char delim) {
    int left = 0;
    auto v = vector<string>();
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == delim) {
            v.push_back(s.substr(left, i - left));
            left = i + 1;
        }
    }
    v.push_back(s.substr(left,s.size() - left));
    return v;
}

int main()
{
    while(1) {
        string s1, s2;
        cin >> s1 >> s2;
        if (s1 == ".") break;
        if (s1 == s2) { cout << "IDENTICAL" << endl; continue; }
        auto v1 = split(s1, '"');
        auto v2 = split(s2, '"');
        if (v1.size() != v2.size()) { cout << "DIFFERENT" << endl; continue; }
        int mis = 0; int cost = 2;
        for (int i = 0; i < v1.size(); ++i) {
            if (v1[i] != v2[i]) mis += cost;
            cost = cost == 2 ? 1 : 2;
        }
        cout << (mis > 1 ? "DIFFERENT" : "CLOSE") << endl;
    }
}



Measured memory_bytes: 3164
#include<stdio.h>
#include<string.h>

int main(){
  int i,r,n,a[16384],sig;
  while(scanf("%d",&n),n!=0){
    sig=0;r=0;
    for(i=0;i<n;i++){scanf("%d",&a[i]);sig+=a[i];}
    for(i=0;i<n;i++){
      if(a[i]*n<=sig){r++;}
    }
    printf("%d\n",r);
  }
  return 0;
}



Measured memory_bytes: 2028
#include <stdio.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef vector<vector<int>> v2int;
typedef vector<ll> vll;
typedef vector<vector<ll>> v2ll;
typedef list<int> liint;
typedef pair<int, int> pint;
const int INF = int(2e9);
const ll LINF = ll(2e9) * ll(2e9);
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b) { a > b ? : a = b; }
template<class T, class C> void chmin(T& a, C b) { a < b ? : a = b; }



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    double L;
    cin >> L;
    
    double x = L / 3.0;

    double ans = x * x * x;
    printf("%30.15f\n", ans);
    return 0;
}

Measured memory_bytes: 256
n, x = [int(i) for i in input().split()]
l = [int(i) for i in input().split()]

cnt = 0
di = 0

if sum(l) < x or sum(l) is x:
  print(n + 1)
else:
  for i, li in enumerate(l, 1):
    di += li
    if di > x:
      i -= 1
      break
    if di is x:
      break
    
  print(i+1)


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


Measured memory_bytes: 2104
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>

using namespace std;

int main() {
  int a,b;
  cin >> a >> b;
  if(a < 10 & b < 10) cout << a*b << endl;
  else cout << -1 << endl;
}

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

int main() {
  int N;
  cin >> N;
  vector<int>vec(N);
  vector<long long>ans;
  for(int i=0; i<N; i++){
    cin >> vec.at(i);
  }
  sort(vec.begin(), vec.end()); 
  for(int j=vec.at(0);j<=vec.at(N-1);j++){
    int X=0;
    for(int k=0; k < N; k++){
      X += (vec.at(k)-j)*(vec.at(k)-j);
    }
    ans.push_back(X);
  }
  sort(ans.begin(), ans.end());
  cout << ans.at(0) << endl;
}


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

namespace AtCoder_Grand_Contest_026
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(System.Console.ReadLine());
            string[] a = System.Console.ReadLine().Split(' ');
            int X = 0;

            for (int i = 0; i < N-1; i++)
            {
                if(a[i] == a[i+1])
                {
                    X = X + 1;
                    i++;
                }
            }
            System.Console.Write(X);
        }
    }
}


Measured memory_bytes: 13140
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>

int main()
{
    long A,B,K;
    std::cin >> A >> B >> K;
    long As,Bs;
    if((A-K)>0){
        As=A-K;
        Bs=B;
    }else{
        As=0;
        if(B-(K-A)>=0){
            Bs=B-(K-A);
        }else{
            Bs=0;
        }
    }
    std::cout << As << " " << Bs << std::endl;
    return 0;
}

Measured memory_bytes: 256
n,m = list(map(int,input().split()))
ac = 0
wa = 0
y = {i:0 for i in range(1,n+1)}
z = {i:0 for i in range(1,n+1)}

for _ in range(m):
  p,s = input().split()
  p = int(p)
  if not y[p] and s == 'WA':
    z[p] += 1
  elif not y[p] and s == 'AC':
    ac += 1
    y[p] += 1

for i in range(1,n+1):
  if y[i]:
    wa += z[i]

print(ac,wa)

Measured memory_bytes: 27368
const main = (input) => {
  const rows = input.split('\n');
  const [...ary1] = rows[1].split(' ');
  const [...ary2] = ary1;
  let sum = 0;
  ary1.forEach( (a1, i1) => {
    ary2.forEach( (a2, i2) => {
      if(i1 !== i2) {
        sum += (a1 * a2);
      }
    });
  });
  console.log(sum / 2);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 7372
N = int(input())
X = [int(i) for i in input().split()]

X_sort = sorted([[i,v] for i,v in enumerate(X)], reverse=True, key=lambda x: x[1
])
ans = [0] * N
for i in range(N):
    ans[X_sort[i][0]] = X_sort[(N//2)-(i>=(N//2))][1]
        
for a in ans:
    print(a)

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

using namespace std;
using ll = long long;

int main(){
    int n; cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; i++){
        int count = 0;
        if(i % 2 != 0){
            for(int j = 1; j <= n; j++){
                if(i % j == 0) count++;
            }
            if(count == 8) ans++;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int
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;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const ll MOD = 1000000007;
const double EPS = 1e-9;
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;

#define MAX_NCK 101010
ll f[MAX_NCK], rf[MAX_NCK];

// (a/b)%P の場合は，(a%P)*modinv(b)%P とする
ll modinv(ll a) {
    ll b = MOD, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= MOD;
    if (u < 0) u += MOD;
    return u;
}

bool isinit = false;

void init() {
    f[0] = 1;
    rf[0] = modinv(1);
    for(int i = 1; i < MAX_NCK; i++) {
        f[i] = (f[i - 1] * i) % MOD;
        rf[i] = modinv(f[i]);
    }
}

ll nCk(int n, int k) {
    if(!isinit) {
        init();
        isinit = 1;
    }
    ll nl = f[n]; // n!
    ll nkl = rf[n - k]; // (n-k)!
    ll kl = rf[k]; // k!
    ll nkk = (nkl * kl) % MOD;

    return (nl * nkk) % MOD;
}

int main(void) {
    
    int n,k;
    cin>>n>>k;
    vi a(n);
    rep(i,n)cin>>a[i];
    Sort(a);

    ll ans=0;
    for(int i=n-1;i>=0;i--){
        if(i<k-1)break;
        ans+=nCk(i,k-1)%MOD*a[i]%MOD;
        ans%=MOD;
    }
    reverse(all(a));

    for(int i=n-1;i>=0;i--){
        if(i<k-1)break;
        ans-=nCk(i,k-1)*a[i]%MOD;
        ans=(ans+MOD)%MOD;
    }

    fin(ans);

}


Measured memory_bytes: 2176
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>

using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> pint;

int main() {
  int N; cin>>N;
  int sum = 0;
  vector<int> L(N);
  REP(i,N) {
    cin>>L[i];
    sum	+= L[i];
  }
  sort(L.begin(), L.end());
  bool ok = L[N-1] < sum - L[N-1];
  cout << (ok ?	"Yes" :	"No") << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define int long long
#define double long double
#define mod 1000000007
#define fi first
#define se second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 1000000000000000000
#define endl '\n'
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; }
using namespace std;

signed main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin>>n;
    vector<int> p(n),a(n),b(n);
    rep(i,n){
        cin>>p.at(i);
        a.at(i)=i+1;
        b.at(i)=n-i;
    }
    for(int i=1; i<n; i++){
        for(int j=p.at(i)-1; j<n; j++){
            a.at(j)+=i;
        }
        for(int j=p.at(i)-1; j>=0; j--){
            b.at(j)+=i;
        }
    }
    rep(i,n-1)cout<<a.at(i)<<' ';
    cout<<a.back()<<endl;
    rep(i,n-1)cout<<b.at(i)<<' ';
    cout<<b.back()<<endl;
}

Measured memory_bytes: 1152
n=int(input())
a=list(map(int,input().split()))
data=[0]*(10**5+2)
for u in a:
    if u==0:
        data[0]+=1
        data[1]+=1
    else:
        data[u-1]+=1
        data[u]+=1
        data[u+1]+=1
print(max(data))

Measured memory_bytes: 52780
AL="abcdefghijklmnopqrstuvwxyz"
keta=[0,26, 702, 18278, 475254, 12356630, 321272406, 8353082582, 217180147158, 5646683826134, 146813779479510, 3817158266467286, 99246114928149462, 2580398988131886038]
kata=[1, 26, 676, 17576, 456976, 11881376, 308915776, 8031810176, 208827064576, 5429503678976, 141167095653376, 3670344486987776, 95428956661682176]
n=int(input())
for i in range(12):
    if(n<=keta[i]):
        s=i
        sn=n-keta[s-1]
        break

def check(n,zn):
    tani = kata[zn]
    for i in range(1,27):
        if(tani*i>=n):
            moji=AL[i-1]
            n-=tani*(i-1)
            break
    return (n,moji)

for i in range(s-1,-1,-1):
    (sn,a)=check(sn,i)
    print(a,end="")
    


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

const int MAX = 10000000;
const int MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
  int x, y;
  cin >> x >> y;
  // x = 99999;
  // y = 99999;

  if ((x+y) % 3 != 0) {
    cout << 0 << endl;
  }
  else {
    COMinit();
    int total = (x+y) /3 ;
    int move_a = total * 2 - x;
    // cout << total << endl << move_a << endl;
    ll ans = COM(total, move_a);

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

Measured memory_bytes: 234624
ENV[Z='RUBY_THREAD_VM_STACK_SIZE']||exec({Z=>'50000000'},'ruby',$0)
def f(v,c)
	s=m=H[v].size==1?A[v-1]:0
	H[v].map{|e|
		next if e==c
		s+=n=f(e,v)
		m=[m,n].max
		return -1if n<0		
	}
	x=2*A[v-1]-s
	s<x||x<2*m-s ?-1:x
end
G=->{gets.split.map &:to_i}
n,_=G[]
A=G[]
H=Hash.new{|h,k|h[k]=[]}
(n-1).times{x,y=G[];H[x]<<y;H[y]<<x}
puts f(1,0)==0?:YES: :NO

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

int main(){
	int N;cin>>N;
    int *a = new int [N+1];
    int *b = new int [N+1];
    for(int i=1;i<=N;i++){
    	cin>>a[i];
    	b[a[i]]=i;
	}
    for(int i=1;i<N;i++)
    cout<<b[i]<<" ";
    cout<<b[N]<<endl;
	return 0;
}

Measured memory_bytes: 1536
import java.util.*;
import java.io.*;
import java.math.BigInteger;

class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String S = sc.next();
        int min = N + 1;
        int[] s1 = new int[N];
        int[] s2 = new int[N];
        for(int i = 0; i < N; i++) {
            if(S.charAt(i) == 'W') s1[i]++;
            else s2[i]++;
        }
        for(int i = 0; i < N-1; i++) {
            s1[i+1] += s1[i];
            s2[N - i - 2] +=  s2[N - i - 1];
        }

        for(int i = 0; i < N; i++) {
            min = Math.min(min,s1[i] + s2[i] - 1);
        }
        System.out.println(min);





    }
}

Measured memory_bytes: 30824
#include <bits/stdc++.h>
#define rep(i,n) for(int64_t i=0;i < (int64_t)(n);i++)
#define invrep(i,n) for(int64_t i=n-1;i >= 0L;i--)
#define positiverep(i,n) for(int64_t i=1;i <= (int64_t)(n);i++)
using namespace std;

//////全探索したいときに開けよ////////
vector<vector<int>> fspattern;
vector<int> fspattern_draft;
int fspcnt = 0;

void setfspattern_core(int floor,int number,int degree){
  if(floor==degree){
    fspattern.at(fspcnt) = fspattern_draft;
    fspcnt++;
  }else{
    rep(i,number){
      fspattern_draft.at(floor) = i;
      setfspattern_core(floor+1,number,degree);
    }
  }
}

void setfspattern(int number,int degree){
  int64_t array_num = 1;
  rep(i,degree){
    array_num *= number;
  }
  fspattern = vector<vector<int>>(array_num,vector<int>(degree));
  fspattern_draft = vector<int>(degree);
  setfspattern_core(0,number,degree);
}

//////nCrのmodを求めたいときに開けよ/////////
//int64_t univMod = 1000000007;
//int64_t factnum = 100000
//vector<int64_t> modfact(factnum);
//vector<int64_t> modinvfact(factnum);

/*void setmodfact(){
  for(int i=0;i<factnum;i++){
    if(i == 0){
      modfact.at(i) = 1;
    }else{
      modfact.at(i) = (modfact.at(i-1)*i)%univMod;
    }
  }
}

int64_t calcmodpower(int64_t a,int64_t n){
  int64_t res = 1;
  while(n != 0){
    if(n & 1){
      res = (res * a) % univMod;
    }
    a = (a*a) % univMod;
    n = n >> 1;
  }
  return res;
}

int64_t calcinverse(int64_t n){
	return calcmodpower(n,univMod-2);
}

void setmodinvfact(){
  for(int i=0;i<factnum;i++){
    if(i==0){
      modinvfact.at(i) = 1;
    }else{
      modinvfact.at(i) = calcmodpower(modfact.at(i),univMod-2);
    }
  }
}

int64_t calcmodcomb(int64_t n,int64_t r){
  return (((modfact.at(n)*modinvfact.at(r))%univMod)*modinvfact.at(n-r))%univMod;
}

int64_t calcmodpositive(int64_t n){
  return (n + ((abs(n)+univMod-1)/univMod)*univMod)%univMod;
}
  
    */


/*
int64_t calcGCD(int64_t a,int64_t b){
	int64_t p = a;
	int64_t q = b;
	int64_t c = a%b;
	while(c != 0){
		p = q;
		q = c;
		c = p%q;
	}
	return q;
}
*/

int main(){
  int64_t k,n;
  cin >> n >> k;
  vector<int64_t> h(n);
  rep(i,n){
    cin >> h.at(i);
  }
  sort(h.begin(),h.end());
  reverse(h.begin(),h.end());
  int64_t sum = 0;
  if(k >= n){
    cout << 0 << endl;
  }else{
    for(int64_t i = k;i < n;i++){
      sum += h.at(i);
    }
cout << sum << endl;
  }
}

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

using namespace std;

const int MAX_H=2005;

string maze[MAX_H];
int row_sum[MAX_H][MAX_H];
int column_sum[MAX_H][MAX_H];

int main(){
  int H,W;
  cin>>H>>W;
  for(int i=0;i<H;i++)cin>>maze[i];
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(maze[i][j]=='.' && j==0)row_sum[i][j]=1;
      else if(maze[i][j]=='.')row_sum[i][j]=row_sum[i][j-1]+1;
      else if(maze[i][j]=='#')row_sum[i][j]=0;
    }
    for(int j=W-1;j>=1;j--){
      if(row_sum[i][j]!=0 && row_sum[i][j-1]!=0)row_sum[i][j-1]=row_sum[i][j];
    }
  }
  for(int j=0;j<W;j++){
    for(int i=0;i<H;i++){
      if(maze[i][j]=='.' && i==0)column_sum[i][j]=1;
      else if(maze[i][j]=='.')column_sum[i][j]=column_sum[i-1][j]+1;
      else if(maze[i][j]=='#')column_sum[i][j]=0;
    }
    for(int i=H-1;i>=1;i--){
      if(column_sum[i][j]!=0 && column_sum[i-1][j]!=0)column_sum[i-1][j]=column_sum[i][j];
    }
  }
  int ans=0;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      ans=max(row_sum[i][j]+column_sum[i][j]-1,ans);
    }
  }
  cout<<ans<<endl;
  
}


Measured memory_bytes: 35712
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<(n);i++)
#define rep2(i,a,n) for(int i=a;i<n;i++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
const int mod =1000000007;
int main(){
    int n;string s;
    cin>>n>>s;
    int ans = 0 ;
    rep(i,1000){
        string w =to_string(i);
        if(w.length()==1){
            w="00"+w;
        }
        if(w.length()==2){
            w='0'+w;
        }
        bool f1=false,f2=false,f3=false;
        rep(j,n){
            if(w[0]==s[j]&&!f1){
                f1=true;
                continue;
            }
            if(w[1]==s[j] && f1 && !f2){
                f2=true;
                continue;
            }
            if(w[2]==s[j]&&f2)f3=true;
        }
        if(f3)ans++;

    }
    cout<<ans<<endl;

}


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

const int INF = 1 << 30;
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 N, K;
int dp[100005][3]; //---- dp[i+1][j+1]: i日目に行動jを取る場合の、最大の幸福度
int happiness[100005][3];
 
int main(){
    for (int i = 0; i < 100005; i++){
        for(int j = 0; j <=2; ++j){
            dp[i][j] = 0;
        }
    }
    cin >> N;
    rep(i,N) cin >> happiness[i+1][0] >> happiness[i+1][1] >> happiness[i+1][2];
   
    for(int j = 0; j <=2; ++j) dp[1][j] = happiness[1][j];

    for(int i=1; i<N; ++i){
        for(int j=0; j<=2; ++j){
            chmax(dp[i+1][j], dp[i][(j+1)%3] + happiness[i+1][j]);
            chmax(dp[i+1][j], dp[i][(j+2)%3] + happiness[i+1][j]);
        }
    }
    cout << max(max(dp[N][0], dp[N][1]), dp[N][2]);
	return 0;
}

Measured memory_bytes: 2560
import sys
import re

N = int(sys.stdin.readline().strip())
start_b = 0
end_a = 0
both = 0
contains = 0

for _ in range(N):
    line = sys.stdin.readline().strip()
    pattern = r"AB"
    matchedList = re.findall(pattern, line)
    
    #if line.find("AB") != -1:
    contains += len(list(matchedList))
    if line[0] == "B" and line[-1] == "A":
        both += 1
    elif line[0] == "B":
        start_b += 1
    elif line[-1] == "A":
        end_a += 1

count = contains
count += max(0, both-1)

if both == 0:
    count += min(end_a, start_b)
elif end_a != 0 and start_b != 0:
    count += 2
    count += min(end_a-1, start_b-1)
elif not (end_a == 0 and start_b == 0):
    count += 1
print(count)
    


Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <utility>

using namespace std;

int maxn = 1000;
int n = 1001;
int tree[1000];
int fib[1000];

int root(int a);
bool is_same_set(int p, int q);
void joint(int x, int y);
void makefib(int maxn);

int main()
{
    makefib(1000);
    int v, d, res;
    while (cin >> v)
    {
        if (cin.eof())
            break;
        cin >> d;

        for (int i = 0; i < maxn; i++)
        {
            tree[i] = i;
        }
        for (int i = 0; i < v; i++)
        {
            for (int j = i; j < v; j++)
            {
                if (abs(fib[i] - fib[j]) < d)
                {
                    joint(i, j);
                }
            }
        }
        res = 0;
        for (int i = 0; i < v; i++)
        {
            if (root(i) == i)
            {
                res++;
            }
        }
        cout << res << endl;
    }

    return 0;
}

void makefib(int maxn)
{
    fib[0] = 2;
    fib[1] = 3;

    for (int i = 2; i < maxn; i++)
    {
        fib[i] = (fib[i - 1] + fib[i - 2]) % n;
    }
}

int root(int a)
{
    if (tree[a] == a)
    {
        return a;
    }
    else
    {
        tree[a] = root(tree[a]);
        return tree[a];
    }
}

bool is_same_set(int p, int q)
{
    return root(p) == root(q);
}

void joint(int x, int y)
{
    tree[root(x)] = root(y);
}



Measured memory_bytes: 3104
use proconio::input;
use proconio::marker::{Chars, Usize1};
use std::iter::Iterator;
use std::collections::HashSet;
use std::cmp::*;
use itertools::Itertools;

#[allow(unused_macros)]
macro_rules! max {
    ($x:expr) => {
      $x
    };
    ($x:expr, $($xs:tt)+) => {
      max($x,max!($($xs)+))
    };
  }
  
  #[allow(unused_macros)]
  macro_rules! min {
    ($x:expr) => {
      $x
    };
    ($x:expr, $($xs:tt)+) => {
      min($x,min!($($xs)+))
    };
  }

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
    input! {
    n: i64,
    a: [i64;n],
    q:i64,
    }

    let mut sum : i64 = a.iter().sum();
    let mut cnt = vec![0;100001];

    for i in a {
      cnt[i as usize] += 1;
    }


    for _ in 0..q {
      input!{
        b:i64,
        c:i64,
      }


      sum = sum + ((c - b) * cnt[b as usize]);

      cnt[c as usize] += cnt[b as usize];
      cnt[b as usize] = 0;

      println!("{}", sum);

    }



}


Measured memory_bytes: 5220
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll ;
#define rep(i, a, b) for (int i = a ; i <= b; ++ i) 
using namespace std ;

ll a, b, r ;

int main() {
	scanf("%lld%lld", &a, &b) ;
	if (a == b) {
		printf("1\n") ;
		return 0 ; 
	}
	for (int i = 60; i >= 0; -- i) {
		if ((a >> i) != (b >> i)) {
			r = i ;
			break ;
		}
	}
	a &= (1LL << (r + 1)) - 1, b &= (1LL << (r + 1)) - 1 ;
	ll ans = (1LL << r) - a ;
	ll lx = 1LL << r, rx = lx ;
	bool flg = false ;
	for (int i = r - 1; i >= 0; -- i) {
		if ((b >> i) & 1LL) flg = true ;
		if (flg) rx += 1LL << i ;
	}
	ll ly = lx + a, ry = (lx << 1) - 1 ;
	if (rx < ly) ans += rx - lx + 1 + ry - ly + 1 ; else
		ans += ry - lx + 1 ;
	printf("%lld\n", ans) ;
	return 0 ; 
}

Measured memory_bytes: 256
{-# OPTIONS_GHC -O2 -funbox-strict-fields #-}
{-# LANGUAGE BangPatterns #-}

import           Control.Applicative
import           Control.Monad
import           Control.Monad.Primitive
import           Control.Monad.ST
import qualified Data.Vector.Generic.Mutable as GM
import qualified Data.Vector.Unboxed         as U
import qualified Data.Vector.Unboxed.Mutable as UM

main :: IO ()
main = do
    [n, _] <- map read.words <$> getLine
    coins <- map read.words <$> getLine
    print $ solve n coins

inf :: Int
inf = 0x3f3f3f3f

solve :: Int -> [Int] -> Int
solve n coins = runST $ do
    dp <- UM.replicate (n+1) inf
    UM.write dp 0 0
    forM_ coins $ \coin ->
        for coin (UM.length dp) $ \i -> do
            x <- (+1) <$> UM.unsafeRead dp (i-coin)
            unsafeModify dp i (min x)
    UM.read dp n

-------------------------------------------------------------------------------
rep, rev :: Monad m => Int -> (Int -> m ()) -> m ()
rep !n = U.forM_ $ U.generate n id
rev !n = U.forM_ $ U.iterateN n (subtract 1) (n - 1)
for :: Monad m => Int -> Int -> (Int -> m ()) -> m ()
for !s !t = U.forM_ $ U.generate (t - s) (+s)
{-# INLINE rep #-}
{-# INLINE rev #-}
{-# INLINE for #-}

unsafeModify :: (PrimMonad m, GM.MVector mv a)
             => mv (PrimState m) a -> Int -> (a -> a) -> m ()
unsafeModify v i f = GM.unsafeRead v i >>= GM.unsafeWrite v i . f
{-# INLINE unsafeModify #-}

Measured memory_bytes: 4156
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] B = new int[N-1];
		Arrays.setAll(B, i->sc.nextInt());
		
		int ans = B[0] + B[N-2];
		for (int i=0; i<N-2; i++) {
			ans += Math.min(B[i], B[i+1]);
		}
		System.out.println(ans);
	}
}

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

typedef long long ll;
typedef pair<int, int> P;

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, n, a) for(int i = (a); i >= (n); i--)
#define mod 1e9+7
#define int ll

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
  int n;
  cin >> n;
  int a[100001];
  rep(i, 0, n) cin >> a[i];
  sort(a, a + n);
  int sum1 = 0, sum2 = 0;
  int fi = n / 2, si = n - 1;
  int f = 1;
  rep(i, 0, n - 1) {
    sum1 += a[si] - a[fi];
    if(f) {
      if(fi == n / 2) fi = -1;
      fi++;
    }else {
      si--;
    }
    f = !f;
  }
  fi = 0, si = n / 2;
  f = 0;

  rep(i, 0, n - 1) {
    sum2 += a[si] - a[fi];
    if(f) {
      fi++;
    }else {
      if(si == n / 2) si = n;
      si--;
    }
    f = !f;
  }
  cout << max(sum1, sum2) << endl;
}


Measured memory_bytes: 1024
let [| m; d |] = stdin.ReadLine().Split(' ') |> Array.map int
let mutable acc = 0
for m' = 1 to m do
    for d' = 1 to d do
        let ( d10, d1 ) = d'/10, d'%10
        if d1 >= 2 && d10 >=2 && d10 * d1 = m' then 
            acc <- acc + 1
printfn "%d" acc

Measured memory_bytes: 13916
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#include <time.h>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
typedef vector<ll> vll;
typedef vector< vector<ll> > matrix;
#define REP(i, x, y) for(ll i = (ll)x; i < (ll)y; i++)
#define DREP(i, x, y, d) for(ll i = (ll)x; i < (ll)y; i += (ll)d)
#define PER(i, x, y) for(ll i = (ll)x; i > (ll)y; i--)
#define DPER(i, x, y, d) for(ll i = (ll)x; i > (ll)y; i -= (ll)d)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-12;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll H, W, N;
    cin >> H >> W >> N;
    ll sr, sc;
    cin >> sr >> sc;
    ll rem[4];
    rem[0] = sr - 1;
    rem[1] = H - sr;
    rem[2] = sc - 1;
    rem[3] = W - sc;
    char c[4] = {'U', 'D', 'L', 'R'};
    char tc[4] = {'D', 'U', 'R', 'L'};
    string S, T;
    cin >> S >> T;
    bool ok = true;
    REP(i, 0, N) {
        REP(j, 0, 4) {
            if (S[i] == c[j]) {
                rem[j]--;
            }
            if (rem[j] < 0) {
                ok = false;
            }
            if (T[i] == tc[j]) {
                rem[j]++;
                if (j <= 1) {
                    rem[j] = min(rem[j], H - 1);
                } else {
                    rem[j] = min(rem[j], W - 1);
                }
            }
        }
    }
    if (ok) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}


Measured memory_bytes: 920
#include<bits/stdc++.h>
using namespace std; 
#define ll long long int
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
#define INF LLONG_MAX
#define PI acos(-1)
#define MOD 1e9 + 7
#define N 1e5 + 10
struct dish
{
	ll rem,t;
};
bool cmp(dish a,dish b)
{
	return(a.rem>b.rem);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	char x;
	cin>>x;
	if(x=='A')
		cout<<"T";
	if(x=='T')
		cout<<"A";
	if(x=='C')
		cout<<"G";
	if(x=='G')
		cout<<"C";
}	

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

int main() {
  int N,A,S;
  
  cin >> N >> A;
  S = N % 500;
  
  if (S <= A) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(long long i=0; i<(n); i++)
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 n,p,q; cin>>n>>p>>q;
    vector<ll> c(n);
    rep(i,n) cin>>c[i];
    rep(i,n) c[i] += p * i;
    sort(c.begin(), c.end(), greater<ll>());
    vector<ll> csum(n+1);
    csum[0] = 0;
    rep(i,n) csum[i+1] = csum[i] + c[i];
    ll res = -1e18;
    for(ll k = 0; k <= n; k++){
        ll tmp = csum[n-k] + p*q*k;
        tmp += p * k * (k-1);
        chmax(res, tmp);
    }
    cout << res - p*n*(n-1)/2 << endl;
    return 0;
}


Measured memory_bytes: 10748
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int mod = 1e9+7;
const int MAX = 510000;
const int V = 100005;
ll dy[8] = {1,0,-1,0,1,-1,1,-1};
ll dx[8] = {0,1,0,-1,1,-1,-1,1};
const double pi = acos(-1);
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << endl;}
#define INT_MAX 1e9+7


int main(){
    ll n,k; cin >> n >> k;
    vl a(n);
    rep(i,n) cin >> a[i], a[i]--;
    ll s = 0;
    vl sum(n);
    map<ll,ll> mp;
    rep(i,n){
        sum[i] = s + a[i];
        sum[i] %= k;
        s = sum[i];
    }
    rep(i,min(n,k-1)){
        mp[sum[i]]++;
    }
    s = 0;
    ll ans = 0;
    rep(i,n){
        ans += mp[s];
        mp[sum[i]]--;
        s = sum[i];
        if(i+k-1<n) mp[sum[i+k-1]]++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 15872
import java.util.*;


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

    int N = scanner.nextInt();
    int K = scanner.nextInt();
    int[] p = new int[N]; 
    for (int i=0; i<N; i++){
      p[i] = scanner.nextInt();
    }

    Arrays.sort(p);
    int sum = 0;

    for(int i =0; i<K; i++){
      sum += p[i];
    }
   System.out.println(sum);
    scanner.close();
    return;
    

  }
}


Measured memory_bytes: 38928
#include <stdio.h>

void shuffle(int a[], int n, int p, int c) {
  int b[50] = {0}, i;
  for (i = 0; i < c; i++)
    b[i] = a[i + p - 1];
  for (i = p - 2; i >= 0; i--)
    a[i + c] = a[i];
  for (i = 0; i < c; i++)
    a[i] = b[i];
}

int main(void) {
  int a[50], n, r, p, c, i;

  while (1) {
    scanf("%d %d", &n, &r);
    if (n == 0 && r == 0) break;

    for (i = 0; i < n; i++)
      a[i] = n - i;

    while (r--) {
      scanf("%d %d", &p, &c);
      shuffle(a, n, p, c);
    }
    printf("%d\n", a[0]);
  }
  return 0;
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
using namespace std;
const int k=1e18;
int main()
{
int n;
  cin>>n;
  
  long long arr[n];
  long long ans=1;
  for(int i=0;i<n;i++)
  {
    cin>>arr[i];
  }
  int count=0;
  for(int i=0;i<n;i++)
  {
      if(arr[i]==0)
      count++;
  }
  if(count>0)
  {
      cout<<0;
      return 0;
  }
  for(int i=0;i<n;i++)
  {
 
    if(arr[i]<= 1000000000000000000/ans)
    {
      ans*=arr[i];
    }
    else
    {
        
        cout<<-1;
        return 0;
    }
  }
 cout<<ans;
  
}


Measured memory_bytes: 4320
#define _USE_MATH_DEFINES
 
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
 
using namespace std;
 
typedef pair<int, int> P;
 
vector<int> G[1000000];
vector<P> bridge;
vector<int> articulation;
int ord[1000000], low[1000000];
bool vis[1000000];
 
void dfs(int v, int p, int &k)
{
	vis[v] = true;
	
	ord[v] = k++;
	low[v] = ord[v];
	
	bool isArticulation = false;
	int ct = 0;
	
	for (int i = 0; i < G[v].size(); i++){
		if (!vis[G[v][i]]){
			ct++;
			dfs(G[v][i], v, k);
			low[v] = min(low[v], low[G[v][i]]);
			if (~p && ord[v] <= low[G[v][i]]) isArticulation = true;
			if (ord[v] < low[G[v][i]]) bridge.push_back(make_pair(min(v, G[v][i]), max(v, G[v][i])));
		}
		else if (G[v][i] != p){
			low[v] = min(low[v], ord[G[v][i]]);
		}
	}
	
	if (p == -1 && ct > 1) isArticulation = true;
	if (isArticulation) articulation.push_back(v);
}
 
int main(){
	
	int V, E;
	cin >> V >> E;
	
	for(int i = 0; i < E; i++){
		int v1, v2;
		cin >> v1 >> v2;
		G[v1].push_back(v2);
		G[v2].push_back(v1);
	}
	
	int k = 0;
	for (int i = 0; i < V; i++){
		if (!vis[i]) dfs(i, -1, k);
	}
	
	sort(bridge.begin(), bridge.end());
	sort(articulation.begin(), articulation.end());
	/*
	for (int i = 0; i < articulation.size(); i++){
		cout << articulation[i] << endl;
	}
	
	//cout << endl;
	*/
	for (int i = 0; i < bridge.size(); i++){
		cout << bridge[i].first << " " << bridge[i].second << endl;
	}
	
	return 0;
}


Measured memory_bytes: 28200
//
//  respect the past, embrace the future
//

#include  <algorithm>
#include  <iostream>
#include  <climits>
#include  <cstdlib>
#include  <cstring>
#include  <cmath>
#include  <cstdio>
#include  <unordered_map>
#include  <map>
#include  <set>
#include  <stack>
#include  <string>
#include  <vector>
#include  <queue>

using namespace :: std;

using vpll = vector <pair <long long, long long> >;
using pll = pair <long long, long long>;
using vll = vector <long long>;
using ll = long long;

#define W (ll) (5e3 + 7)
#define N (ll) (2e6 + 7)
#define M (ll) (1e9 + 7)
#define INF (ll) (2e18)
#define int long long
#define F first
#define S second

inline void fastInputOutput () {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
}

inline void ReadWriteFromFile () {
  freopen("../in.txt", "r", stdin);
  freopen("../out.txt", "w", stdout);
}

int a[N], bits[W][2];

int32_t main (int32_t argc, char *argv[]) {
  fastInputOutput();
  // ReadWriteFromFile();
  
  int n, ans = 0;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    vector <int> v;
    int a;
    cin >> a;
    for (int i = 0; i < 64; i++) {
      v.push_back(a & 1);
      a >>= 1;
    }
    int k = v.size();
    for (int i = 0; i < k; i++)
      bits[i][v[i]]++;
    v.clear();
  }
  for (int i = 0; i < 64; i++) {  
    int cur = (bits[i][0] % M) * (bits[i][1] % M) % M;
    for (int j = 0; j < i; j++)
      cur = (cur + cur) % M;
    ans = (ans + cur) % M;
  }
  cout << ans;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <array>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <math.h>
#include <queue>
#include <stdio.h>
using namespace std;
using i64 = int64_t;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep2(i, x, n) for(int i=x;i<n;++i)

int main()
{    
    int n;
    cin >> n;
    vector<int> x(n);
    rep(i,n) cin >> x[i];

    multimap<int,int> y;
    rep(i,n) y.insert({x[i],i});
    
    vector<int> z(n);
    auto itr = y.begin();
    int b0 = next(y.begin(),n/2-1)->first;
    int b1 = next(y.begin(),n/2  )->first;
    rep(i,n)
    {
        if(i < n/2)
            z[itr->second] = b1;
        else
            z[itr->second] = b0;
        ++itr;
    }

    rep(i,n) cout << z[i] << endl;
    return 0;
}

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

int main() {
    long long x;
    cin >> x;

    long long y = 100;
    int count = 0;
    while(true) {
        y += y / 100;
        count++;
        if(y >= x) break;
    }

    cout << count << endl;

    return 0;
}    

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define rep(i, n) for (int i=0; i<(int)(n); i++)
typedef long long ll;


int main() {
    ll n;
    cin >> n;
    map<ll, ll> mp;
    vector<ll> vec;
    rep(i, n){
        ll num;
        cin >> num;
        vec.push_back(num);
        mp[num]++;
    }
    ll sum;
    for(ll i=(ll)(1); i<=n; i++){
        sum += mp[i]*(mp[i]-(ll)(1))/(ll)(2);
    }
    rep(i, n){
      	ll before = (ll)(mp[vec[i]])*((ll)(mp[vec[i]])-(ll)(1))/(ll)(2);
      	ll after = ((ll)(mp[vec[i]])-(ll)(1))*((ll)(mp[vec[i]])-(ll)(2))/(ll)(2);
    	ll res = sum-before+after;
        cout << res << endl;
    }
    return 0;
}

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

int main()  
{  
    int a,b,c;
    int s;
    cin>>a>>b>>c;
    s=a+b+c;
    if(s>=22)
        cout<<"bust"<<endl;
    else
        cout<<"win"<<endl;


    return 0;  
}  
  


Measured memory_bytes: 3584
//author-abhijit dey
 //Welcome to my code. btw I hate coding 😉
#include <bits/stdc++.h>
using namespace std;
#define     ff first
#define     ss second
#define     pb push_back
#define     mp make_pair
#define     INF 1000000005
#define     MOD 1000000000
#define     ninf -1000000000
#define     all(c) c.begin(), c.end()
#define     tinput long long int t;cin>>t;
#define     mem(a,x) memset(a,x,sizeof a)
#define     for0(i,n) for(long long int i=0;i<n;i++)
#define     pi 3.141592653589793238462643383279502884
#define     fori(i,a,n) for(long long int i=a;i<n;i++)
#define     forxy(i,x,y) for(int i=x;i<=y;i++)
#define     rfor(i,n) for(long long int i=n-1;i>=0;i--)
#define     ainput for(int i=0; i<n; i++) cin>>a[i];
#define     fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

typedef     long long int ll;
typedef     vector<long long int>vll;
typedef     vector<vector<int> >vvll;
typedef     pair<long long int,long long int>pr;
typedef     vector<pair<long long int,long long int> >vp;

inline long long  min2(long long  a, long long  b)  {return (a)<(b)?(a):(b);}
inline long long  max2(long long  a, long long  b)  {return (a)>(b)?(a):(b);}
inline long long  max3(long long  a, long long  b, long long  c)    {return (a)>(b)?((a)>(c)?(a):(c)):((b)>(c)?(b):(c));}
inline long long  min3(long long  a, long long  b, long long  c)    {return (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c));}
using namespace std::chrono;
string S,T;
vector<char>s(3001),t(3001);

ll dp[3001][3001];
ll fun(ll i,ll j)
{
    ll left=0,right=0;
    if(i==S.length()+1 or j==T.length()+1)return 0;
    if(dp[i][j]!=-1)return dp[i][j];
    if(s[i]==t[j])
    {
        left=1+fun(i+1,j+1);
        right=1+fun(i+1,j+1);
    }
    else 
    {
        left=fun(i+1,j);
        right=fun(i,j+1);
    }
    dp[i][j]=max(left,right);
    return dp[i][j];
}
void path(ll i,ll j)
{
    if(i==S.length()+1 or j==T.length()+1)return;
    ll ans=fun(i,j);
    if(s[i]==t[j])
    {
        cout<<s[i];
        return path(i+1,j+1);
    }
    else
    {
        if(ans==fun(i+1,j))return path(i+1, j);
        else if(ans==fun(i,j+1))return path(i, j+1);
    }
}
void process()
{
    cin>>S>>T;
    for(ll i=1;i<=S.length();i++)s[i]=S[i-1];
    for(ll i=1;i<=T.length();i++)t[i]=T[i-1];
    memset(dp,-1,sizeof(dp));
    ll len=fun(1,1);
    path(1,1);
}
int main()
{
    fastio;
    //tinput;
    //while(t--)
        process();
}


Measured memory_bytes: 70912
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define printVec(v) printf("{"); for (const auto& i : v) { std::cout << i << ", "; } printf("}\n");
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; }
//Get the highest value and key from a map.
template<typename KeyType, typename ValueType>
std::pair<KeyType,ValueType> get_max( const std::map<KeyType,ValueType>& x ) {
  using pairtype=std::pair<KeyType,ValueType>;
  return *std::max_element(x.begin(), x.end(), [] (const pairtype & p1, const pairtype & p2) {
        return p1.second < p2.second;
  });
}
using namespace std;
using P = pair<int,int>;
using ll = long long;
const ll INF = 1LL<<60;

int main() {
  int n1, n2, n3;
  cin >> n1 >> n2 >> n3;

  if (n1 + n2 + n3 >= 22) {
    cout << "bust" << endl;
  } else {
    cout << "win" << endl;
  }

  return 0;
}


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

#define lli long long int
#define LLI(n) lli n; scanf("%lld", &n);
#define STR(n) string n; cin >> s;
#define Sort(n) sort(n.begin(), n.end());
#define Reve(n) reverse(n.begin(), n.end());
#define yes puts("Yes");
#define no puts("No");
#define C45(n) (n + 1) / 2

//素数
bool IsPrime(lli num)
{
  if (num < 2) return false;
  else if (num == 2) return true;
  else if (num % 2 == 0) return false;
  long double sqrtNum = sqrt(num);
  for (lli i = 3; i <= sqrtNum; i += 2)
  {
    if (num % i == 0)return false;
  }
  return true;
}
//各桁の和
lli Sum(lli n)
{
  lli sum=0;
  if (n<0) return 0;
  while (n>0)
  {
    sum += n%10;
    n /= 10;
  }
  return sum;
}

int main(void)
{
  lli flag = 0;
  STR(s)
  for(lli i = 0;i < s.size();i++) {
    if(s.at(i) == '1') {
      flag++;
    }
  }
  cout << flag << endl;
  return 0;
}


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

using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin>>s;
    int n=s.length();
    if(s[n-1]!='s')
    {
         s=s+'s';
    }
    else
    {
         s=s+'e';
         s=s+'s';
    }
    cout<<s<<endl;
    
	return 0;
}

Measured memory_bytes: 3648
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

int main()
{
  int n, k;
  cin >> n >> k;
  vector<ll> vs(n);
  for(int i = 0; i < n; i++)
  {
	cin >> vs[i];
  }
  vector<ll> accum(n + 1);
  vector<ll> accum_pos(n + 1);
  accum[0] = 0;
  accum_pos[0] = 0;
  for(int i = 1; i <= n; i++)
  {
	accum[i] = accum[i - 1] + vs[i - 1];
	accum_pos[i] = accum_pos[i - 1] + (vs[i - 1] > 0 ? vs[i - 1] : 0);
  }

  ll ans = 0;
  for(int i = k; i <= n; i++)
  {
	ans = max(ans,
			  (accum_pos[i - k]) +
			  (accum[i] - accum[i - k] > 0 ? accum[i] - accum[i - k] : 0) +
			  (accum_pos[n] - accum_pos[i]));
	// cerr << accum_pos[i - k] << ", " << (accum[i] - accum[i - k] > 0 ? accum[i] - accum[i - k] : 0) << ", " << (accum_pos[n] - accum_pos[i]) << endl;
  }
  cout << ans << endl;
}


Measured memory_bytes: 2560