akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef vector<vector<int>> Graph;

int main() {

	int N, K;
	cin >> N >> K;
	string s;
	cin >> s;

	int now = 0;
	rep(i, s.size() - 1) {
		if (s[i] == s[i + 1])
			now++;
	}

	cout << min(N - 1, now + K * 2) << endl;

	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int a,b;
    cin >> a >> b;
    int ans = a+b;
    ans = max(ans, a-b);
    ans = max(ans, a*b);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
/*
for:
Hussien , Ayman , Emad
Abanob , George , Genawy
Ka8eem , Mosta7il , Stawro

ICPC DREAM
*/
#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned ll 
#define endl '\n'
#define mk make_pair
const double PI = acos(-1.0);
void fast_in_out() {
	std::ios_base::sync_with_stdio(NULL);
	cin.tie(NULL); cout.tie(NULL);

}
int dx[] = { 0,0,-1,1,-1,1,-1,1,0 };
int dy[] = { -1,1,0,0,-1,-1,1,1,0 };
const ld eps = 1e-9;
const int mod = 998244353;
const int N = 2e5 + 10, M = 318;
int main() {
	fast_in_out();
	//cout << fixed << setprecision(6);
	// kolo ray7 , ya 5raby
	int n; cin >> n;
	map<int, int>mp;
	for (int i = 0; i < n; i++) {
		int x; cin >> x;
		mp[x]++;
	}
	int ans = 0;
	for (auto e : mp) {
		if (e.second == e.first)
			continue;
		if (e.second > e.first)
			ans += (e.second - e.first);
		if (e.second < e.first)
			ans += e.second;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4736
#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>
#include<map>
 
 
using namespace std;
#define int long long int
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back
#define mod 1000000007

char S[100005];
int Q;
vector<char> sentou;
vector<char> matubi;


signed main(){
    scanf("%s",S);
    scanf("%lld",&Q);
    int mode=0;
    rep(i,Q){
        int T;
        scanf("%lld",&T);
        if(T==1){
            mode=(mode+1)%2;
        }else{
            int F;char C;
            scanf("%lld %c",&F,&C);
            F=(mode+F)%2;
            if(F==1){
                sentou.pb(C);
            }else{
                matubi.pb(C);
            }
        }
    }
    if(mode==0){
        rep(i,sentou.size()){
            int j=sentou.size()-1-i;
            printf("%c",sentou[j]);
        }
        printf("%s",S);
        rep(i,matubi.size()){
            printf("%c",matubi[i]);
        }
    }else{
        rep(i,matubi.size()){
            int j=matubi.size()-1-i;
            printf("%c",matubi[j]);
        }
        rep(i,strlen(S)){
            int j=strlen(S)-1-i;
            printf("%c",S[j]);
        }
        rep(i,sentou.size()){
            printf("%c",sentou[i]);
        }
    }
    printf("\n");
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define hackcyborg shresth_walia
#define ll long long
#define ld double
#define pb push_back
#define mod 1000000007
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int,null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define int long long
ll binpow(ll a,ll b,ll m=mod)
{
    ll res=1;
    while(b>0)
    {
        if(b&1)
        res=(a*res)%m;
        a=(a*a)%m;
        b/=2;
    }
    return res;
}
main()
{
    IO
    ll n;
    cin>>n;
    ll a[n];
    for(int x=0;x<n;x++)
        cin>>a[x];
    ll e=0;
    ll ans=0;
    for(int x=0;x<n;x++)
    {    if(e>a[x])
        ans+=abs(a[x]-e);
        e=max(e,a[x]);
    }
    cout<<ans;
}


Measured memory_bytes: 5172
#include<iostream>
#include<set>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;

int n,sum;

set<int> S;

int gcd(int x,int y)
{
	return y?gcd(y,x%y):x;
}

int main()
{
	scanf("%d",&n);
	int i,cnt(0);
	for(i=2;i<=30000&&cnt<n-1;++i)if(!(i&1)||!(i%3))
	{
		printf("%d ",i);
		sum+=i;
		S.insert(i);
		++cnt;
	}
	for(i=2;i<=30000;++i)
		if((sum+i)%6==0&&gcd(sum,i)!=1&&!S.count(i))
		{
			printf("%d",i);
			return 0;
		}
	return 0;
}


Measured memory_bytes: 1280
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <ctype.h>
#define MOD 2019
#define MAX(a,b) (a>b?a:b)
#define MAX3(a,b,c) MAX(a,MAX(b,c))
#define MIN(a,b) (a<b?a:b)
#define MIN3(a,b,c) MIN(a, MIN(b,c))
typedef long long lli;
int cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}


int main()
{
    lli i, j, n, a[100000],sum=0,a0,a1;
    scanf("%lld",&n);
    for(i=0; i<n; i++) {
        scanf("%lld",a+i);
        a[i] *= 2;
        sum += a[i];
    }
    sum /= 2;
    a0 = a1 = sum;
    for(i=1; i<n; i+=2) {
        a0 -= a[i];
        a1 -= a[i+1];
    }
    for(i=0; i<n-1; i+=2) {
        printf("%lld %lld ",a0,a1);
        a0 = a0 + a[i+1] - a[i];
        a1 = a1 + a[i+2] - a[i+1];
    }
    printf("%lld",a0);
    return 0;
}


Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define per1(i,n) for(int i=n;i>0;i--)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};
const int MOD = 1000000007;
using mint = Fp<MOD>;
const int MAX=500001;
mint 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;
        inv[i] = (mint)MOD - inv[MOD%i] * (MOD / i);
        finv[i] = finv[i - 1] * inv[i];
    }
}

mint 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];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    mint ans=1,b;
    rep(i,n) ans*=m-i;
    b=ans;
    mint a=1;
    COMinit();
    per1(i,n){
        ll z=1;
        if(i%2) z=-1;
        if(i<n) a*=m-i;
        ans+=a*z*COM(n,i);
    }
    cout<<ans*b;
}

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

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	long long h;
	int n;
	cin >> h >> n;
	vector<int> a(n);
	for(int i=0;i<n;i++) cin >> a[i];
	
	long long sum=0;
	for(int i=0;i<n;i++) sum+=a[i];
	if(sum>=h) cout << "Yes\n";
	else cout << "No\n";
	return 0;
}

Measured memory_bytes: 640
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
a,b,c,x,y = readInts()
c *= 2
if x > y:
    # 3 通り
    # a,b を x,y個ずつ買う
    # 2枚セットを大きいほう個買う
    # 2枚セットを小さい方買う、のこりは大きい方
    ans = min(a*x + b*y, c * x, c*y + a*(x-y))
else:
    ans = min(a*x + b*y, c*y, c*x+b*(y-x))
print(ans)


Measured memory_bytes: 10424
import java.util.*;

public class Main {

  public static void main (String[] args) {

    Scanner sc = new Scanner(System.in);
    
    int N = sc.nextInt();
    long[] T = new long[N];

    for (int i = 0; i < N; i++) {
      T[i] = sc.nextLong();
    }

    sc.close();

    long result = T[0];

    for (int i = 1; i < N; i++) {
      result = lcm(result, T[i]);
    }

    System.out.println(result);

  }

  public static long gcd(long x, long y){

    if (y == 0) {
      return x;
    }
    
    return gcd(y, x % y);
    
  }

  public static long lcm(long x, long y) {

		return x / gcd(x, y) * y;
  
  }

}

Measured memory_bytes: 23888
#include<bits/stdc++.h>
#define REP(i,n)   for(int i=0;i<(n);++i)
using namespace std;
int main(){
int a,b;
cin>>a>>b;
cout<<"100 100\n";
REP(i,100){REP(j,100)i<50?cout<<(i%2&&j%2&&--a>0?".":"#"):cout<<(i%2&&j%2&&--b>0?"#":".");
cout<<"\n";}}


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

#define ll long long
#define INF 99999999
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

int main()
{
 int A, B;
   cin >> A >> B;

   rep(i, 10000)
   {
       int ra = i * 8 /100;
       int rb = i * 1 / 10;
       if ( A == ra && B == rb )
       {
           cout << i << endl;
           return 0;
       }
   }

   cout << -1 << endl;
   return 0;
   
}


Measured memory_bytes: 256
n = int(input())
s = list(input())
Rcount = 0
Gcount = 0
Bcount = 0
cnt = 0
for i in range(len(s)):
         if s[i] == "R":
                  Rcount += 1
         elif s[i] == "G":
                  Gcount += 1
         elif s[i] == "B":
                  Bcount += 1
RGB = Rcount * Gcount * Bcount
for i in range(1,(len(s)//2)+2):
         for j in range(len(s)):
                  if i * 2 + j >= len(s):
                           break
                  else:
                           if s[j] != s[j+i] and s[j+i] != s[j+i+i] and s[j+i+i] != s[j]:
                                    cnt += 1
print(RGB - cnt)


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

int main(){
string O, E; cin >> O >> E;
for (int i = 0; i < E.size(); i++) {
    cout << O.at(i) << E.at(i);
}
if (O.size() != E.size()) {
        cout << O.at(O.size() - 1);
}
cout << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<string>blue(N);
  for (int i=0; i < N; i++){
    cin >> blue.at(i);
  }
  
  int M;
  cin >> M;
  vector<string>red(M);
  for (int i=0; i < M; i++){
    cin >> red.at(i);
  }
  
 int score = 0;
  int newscore = 0;
  for (int i=0; i < N;i++){
    for (int j=0; j < N;j++){
      if (blue.at(i) == blue.at(j)){
        newscore++;
  }
    }
    
  for (int j=0; j < M;j++){
  if (blue.at(i) == red.at(j)){
  newscore--;
  }
  	}
    
    if (newscore > score){
      score = newscore;
    }
  
    newscore = 0;
  }
  
  cout << score << endl;
}
 

Measured memory_bytes: 3632
Imports System.Collections.Generic
Imports System.Console

Module Program
    Sub Main()
        Dim N As Integer = NextInt()
        Dim max, min As Integer

        For i As Integer = 0 To N - 1
            Dim Ai As Integer = NextInt()
            If i = 0 Then
                max = Ai
                min = Ai
            Else
                max = Math.Max(max, Ai)
                min = Math.Min(min, Ai)
            End If
        Next

        WriteLine(max - min)
    End Sub

    Function NextInt() As Integer
        Return CInt(NextString())
    End Function

    Function NextString() As String
        Dim result As New List(Of Char)
        Do
            Dim tmp As Integer = Read()
            If tmp < 0 Then Exit Do
            Dim nextChar As Char = Chr(tmp)

            If Not Char.IsWhiteSpace(nextChar) Then
                result.Add(nextChar)
            ElseIf nextChar <> vbCr Then
                Exit Do
            End If
        Loop
        Return New String(result.ToArray())
    End Function

End Module


Measured memory_bytes: 20560
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
        return

    if self.parents[x] > self.parents[y]:
        x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def size(self, x):
    return -self.parents[self.find(x)]

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
  
v, e = map(int, input().split())
uf = UnionFind(v)
for i in range(e):
  a, b = map(int, input().split())
  uf.union(a-1, b-1)
  
print(uf.group_count()-1)


Measured memory_bytes: 12772
fun main(args: Array<String>) {
    val (x, y) = readLine()!!.split(" ").map { it.toInt() }
    println(x + y - gcd(x, y) + 1)
}

fun gcd(a: Int, b: Int): Int {
    if (a < b) return gcd(b, a)
    if (b == 0) return a
    return gcd(b, a % b)
}


Measured memory_bytes: 33876
#include <iostream>
#include <string>
using namespace std;
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;
	int m[2];
	for(;cin>>s,s!="#";){
		m[0]=m[1]=0;
		for(int i=1;i<s.size();i++){
			if((s[i]-'1')%3>(s[i-1]-'1')%3){
				m[0]=min(m[0]+1,m[1]);
				m[1]=1<<30;
			}else if((s[i]-'1')%3<(s[i-1]-'1')%3){
				m[1]=min(m[0],m[1]+1);
				m[0]=1<<30;
			}else{
				m[1]^=m[0],m[0]^=m[1],m[1]^=m[0];
			}
		}
		cout<<min(m[0],m[1])<<endl;
	}
}

Measured memory_bytes: 1328
import java.util.Scanner;
import java.util.Arrays;
import java.math.BigInteger;

public class Main {  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    BigInteger[] A = new BigInteger[N];
    for (int i =0; i<N; i++) {
      A[i] = sc.nextBigInteger();
    }
    Arrays.sort(A);
    BigInteger a = BigInteger.ZERO;
    BigInteger b = BigInteger.ZERO;
    int p = 100001;
    for (int i =N-1; i>0; i--) {
      if (A[i].equals(A[i-1])) {
        a = A[i];
        p = i;
        break;
      }
    }
    for (int i =N-1; i>0; i--) {
      if (i != p && i != p-1 && A[i].equals(A[i-1])) {
        b = A[i];
        break;
      }
    }
    System.out.println(a.multiply(b));  
  }
}

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

int dp[186][186][186][17];
char s[200][200];

int main()
{
	int n, m; cin>>n>>m;
	for (int i=1; i<=n; i++)
		for (int j=1; j<=m; j++) cin>>s[i][j];
		
	for (int l=1; l<=n; l++)//init
	{
		for (int i=1; i<=m; i++)
		{
			int temp=1000;
			char t= s[l][i];
			for(int j=i; j<=m; j++)
			{
				int x= l;
				while(x<=n && s[x][j]==t) x++;
				temp=min(temp, x-1);
				dp[l][i][j][0]= temp;
			}
		}
	}	
	
	if (dp[1][1][m][0]==n)
	{
		cout << 0 << endl;
		return 0;
	}
	
	for (int k=1; k<17; k++)
	{
		for (int l=1; l<=n; l++)
		{
			for (int i=1; i<=m; i++)
				for (int j=i; j<=m; j++)
				{
					int &temp= dp[l][i][j][k];
					if (dp[l][i][j][k-1]==n) temp=n;
					else temp = dp[dp[l][i][j][k-1]+1][i][j][k-1];
					int a=i, b=j;
					while(a < b)
					{
						int mid= (a+b)/2+1;
						if (dp[l][i][mid-1][k-1]<dp[l][mid][j][k-1]) b=mid-1;
						else a=mid;
					} 
					int mid=a;
					temp = max(temp, min(dp[l][i][mid-1][k-1],dp[l][mid][j][k-1]));
					mid++;
					if (mid>=i && mid<=j)temp = max(temp, min(dp[l][i][mid-1][k-1],dp[l][mid][j][k-1]));
				}
		}
		//cout << dp[1][1][m][k] << endl; 
		if (dp[1][1][m][k]==n)
		{
			cout << k << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 425088
#include<stdio.h>

#define MAX 100000

int getdepth(int);

typedef struct{
  int parent;
  int left;
  int right;
}node;

node T[MAX];

int main(){
  int i, j, sib, deg, id, k, n, depth;

  scanf("%d",&n);

  for(i=0;i<n;i++) T[i].parent = T[i].left = T[i].right = -1;

  for(i=0 ; i<n ; i++){
    
    scanf("%d%d",&id,&k);

    for(j=0 ; j<k ; j++){

      scanf("%d",&deg);

      if(j==0) T[id].left = deg;

      else T[sib].right = deg;

      sib = deg;
      T[deg].parent = id;
    }
  }

  for(i=0 ; i<n ; i++){

    depth = getdepth(i);
    //printf("here\n");
    if(depth==0) printf("node %d: parent = %d, depth = %d, root, ", i, T[i].parent, depth);

    else if(T[i].left==-1) printf("node %d: parent = %d, depth = %d, leaf, ", i, T[i].parent, depth);

    else printf("node %d: parent = %d, depth = %d, internal node, ", i, T[i].parent, depth);
    //printf("here\n");
    printf("[");

    if(T[i].left != -1){
      id = T[i].left;
      printf("%d",id);
      
      while(id != -1){
	id = T[id].right;
	
	if(id != -1) printf(", %d",id);
      }
    }

    printf("]\n");

  }
  return 0;
}

int getdepth(int i){//printf("in\n");
  int id = T[i].parent;
  int cnt = 0;

  while(id != -1){
    id = T[id].parent;
    cnt++;
    //printf("while\n");
  }

  return cnt;
}

Measured memory_bytes: 1788
#include <bits/stdc++.h> 
#define pb push_back
#define sp " "
#define sl "\n"
#define fi first
#define se second
#define mp make_pair
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define rev(a) reverse(a.begin(),a.end())
#define PI 3.141592

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;

const int N=1e5+5,mod=1000000007;
ll a;
ll b;
char x;
ll d;
int main() { 
	cin.tie(0); cout.tie(0); 
	ios_base::sync_with_stdio();
	cin>>a>>b>>x>>d;
	b=b*100+d;
	a*=b;
	a/=100;
	cout<<a;
	return 0;
}
// Recuerda limites 
// Recuerda casos especiales


Measured memory_bytes: 3624
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;
int main()
{
	int a, p;
	scanf("%d%d", &a, &p);
	printf("%d", (3 * a + p) / 2);
	return 0;
}

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

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)

using ll = long long;
using ld = long double;
ll INF = LLONG_MAX;

using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;

namespace output {
	void pr(int x) { cout << x; }
	void pr(long x) { cout << x; }
	void pr(ll x) { cout << x; }
	void pr(unsigned x) { cout << x; }
	void pr(unsigned long x) { cout << x; }
	void pr(unsigned long long x) { cout << x; }
	void pr(float x) { cout << x; }
	void pr(double x) { cout << x; }
	void pr(ld x) { cout << x; }
	void pr(char x) { cout << x; }
	void pr(const char* x) { cout << x; }
	void pr(const string& x) { cout << x; }
	void pr(bool x) { pr(x ? "true" : "false"); }
	template<class T> void pr(const complex<T>& x) { cout << x; }
	
	template<class T1, class T2> void pr(const pair<T1,T2>& x);
	template<class T> void pr(const T& x);
	
	template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
		pr(t); pr(ts...); 
	}
	template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
		pr("{",x.f,", ",x.s,"}"); 
	}
	template<class T> void pr(const T& x) { 
		pr("{"); // const iterator needed for vector<bool>
		bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
		pr("}");
	}
	
	void print() { pr("\n"); } // print w/ spaces
	template<class T, class... Ts> void print(const T& t, const Ts&... ts) { 
		pr(t); if (sizeof...(ts)) pr(" "); print(ts...); 
	}
}

using namespace output;

ll MOD = 1e9+7;

const int MAXN = 1e3+10;
vll fact (MAXN);
vll invfact (MAXN);
vll inv (MAXN);
vector<vll> precomp (MAXN, vll (MAXN));

ll binpow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        res %= MOD;
        a = a * a;
        a %= MOD;
        b >>= 1;
    }
    return res;
}

inline ll inverse(ll n) {
    return binpow(n, MOD-2);
}

inline ll choose(ll n, ll k) {
    return fact[n] * invfact[k] % MOD * invfact[n-k] % MOD;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	fact[0] = 1;
    FOR(i, 1, MAXN) fact[i] = fact[i-1] * i % MOD;

    inv[1] = 1;
    FOR(i, 2, MAXN) inv[i] = (MOD - (MOD/i) * inv[MOD%i] % MOD) % MOD;

    invfact[0] = 1;
    FOR(i, 1, MAXN) invfact[i] = invfact[i-1] * inv[i] % MOD;

	F0R(i, MAXN) F0R(j, MAXN) {
		precomp[i][j] = inverse(binpow(fact[i], j) * fact[j] % MOD);
	}

	int N, A, B, C, D; cin >> N >> A >> B >> C >> D;
	vector<vll> dp (N+1, vll (B+1));
	dp[0][0] = 1; // rem, max i
	F0R(i, N+1) {
		FOR(j, 1, B+1) {
			dp[i][j] += dp[i][j-1];
			if (A <= j && j <= B) {
				for (int x = C; j * x <= i && x <= D; ++x) {
					dp[i][j] += choose(i, j*x) * fact[j*x] % MOD * precomp[j][x] % MOD * dp[i-j*x][j-1];
					dp[i][j] %= MOD;
				}
			}
		}
	}
	print(dp[N][B]);
}

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

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define F first
#define S second
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
const int MOD = 1e9 + 7; 
const int N = 200000+10; 

int a[N]; 
int main(void) 
{
	
	#ifndef ONLINE_JUDGE
	//freopen("input.txt", "r", stdin);
	#endif

	
	int n; 
	cin >> n; 
	for (int i=1; i<=n; i++) 
		cin >> a[i]; 
	
	int ans = 1;
	int mini = a[1]; 
	for (int i=2; i<=n; i++) 
	{
		if (a[i] < mini) 
		{
			//cout << a[i] << '\n';
			mini = min(mini,a[i]); 
			ans++; 
		}
	}
	cout << ans << '\n';


	return false;   


}


Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>

void push(int);
int pop(void);

int top,S[1000];
int main(){
  int x,y;
  char a[100];

  while(scanf("%s",a)!=EOF){
    if(a[0]=='+'){
      x=pop();
      y=pop();
      push(y+x);
    }
    else if(a[0]=='-'){
      x=pop();
      y=pop();
      push(y-x);
    }
    else if(a[0]=='*'){
      x=pop();
      y=pop();
      push(y*x);
    }
    else push(atoi(a));


  }
  printf("%d\n",pop());
  return 0;
}

void push(int x){
  S[++top]=x;
}

int pop(){
  top--;
  return S[top+1];
}



Measured memory_bytes: 2048
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll linf = (1LL << 61);
const int inf = 1001001001;
const int mod = 1000000007;

int dp[100005];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	vector<int> h(n);
	rep(i, n) cin >> h[i];
	rep(i, n + 1) dp[i] = inf;
	dp[0] = 0;
	rep(i, n) {
		for (int j = k; j >= 1; --j) {
			dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[min(n - 1, i + j)]));
		}
	}
	cout << dp[n] << endl;
	return 0;
}

Measured memory_bytes: 1024
# coding: utf-8
# Your code here!
from math import factorial

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

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

for i in range(1, K + 1):
	if N - K + 1 < i:
        	print(0)
	else:
		print(cmb(K - 1,i -1) * cmb(N - K + 1, i) % (pow(10,9) + 7))


Measured memory_bytes: 3444
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=500000004;
int gcd(int a,int b){
	while(a){
		b%=a;swap(a,b);
	}
	return b;
}
int main(){
	int T;scanf("%d",&T);
	while(T--){
		int a,b;scanf("%d%d",&a,&b);
		int g=gcd(a,b);
		int A=a/g;
		int B=b/g;
		if(A%2&&B%2){
			printf("%lld %lld\n",(long long)A*B/2+1,(long long)A*B/2);
		}else{
			printf("1 1\n");
		}
	}
}

Measured memory_bytes: 2752
a, b, c = map(int, input().split())
ans = 0

while True:
    if a%2==1 or b%2==1 or c%2==1:
        print(ans)
        break
    if a == b == c:
        print(-1)
        break
    s = a // 2
    t = b // 2
    u = c // 2
    a, b, c = t+u, s+u, s+t
    ans += 1
else:
    print(ans)

Measured memory_bytes: 9092
H, W = map(int, input().split())
S = []
for i in range(H):
    S.append(input())
    
ans_W = [[-1 for i in range(W)] for j in range(H)]
for i in range(H):
    count = 0
    now = 0
    for j in range(W):
        if S[i][j] == ".":
            count += 1
        else:
            for k in range(now, min(W, now+1+count)):
                if k == j:
                    ans_W[i][k] = 0
                else:
                    ans_W[i][k] = count
            now += count+1
            count = 0
    if count != 0:
        for k in range(now, min(W, now+1+count)):
            ans_W[i][k] = count

ans_H = [[-1 for i in range(W)] for j in range(H)]
for i in range(W):
    count = 0
    now = 0
    for j in range(H):
        if S[j][i] == ".":
            count += 1
        else:
            for k in range(now, min(H, now+1+count)):
                if k == j:
                    ans_H[k][i] = 0
                else:
                    ans_H[k][i] = count
            now += count+1
            count = 0
    if count != 0:
        for k in range(now, min(H, now+1+count)):
            ans_H[k][i] = count

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, ans_H[i][j] + ans_W[i][j])
            
print(ans-1)


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

int main(){
    string s,t;
    cin >> s >> t;
    int n=s.size();
    string ans="Yes";
    for(int i=0;i<n;i++){
        if(s[i]!=t[i]){
            ans="No";
            break;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3628
d, n = gets.split.map(&:to_i)

nums = []
(0..2).each do |i|
  nums[i] = (1..(2*n)).to_a.map {|e| (100 ** i) * e }
end
nums[0].select! { |e| e % 100 != 0 }
nums[1].select! { |e| e / 100 > 0 && (e / 100) % 100 != 0 }
nums[2].select! { |e| e / 10000 > 0 && (e / 10000) % 100 != 0 }
puts nums[d][n-1]


Measured memory_bytes: 1788
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <regex>
#include <vector>

#define fix(n)          cout<<fixed<<setprecision(n)
#define rep(i,n)        for (int i = 0; i < (n); ++i)
#define sort(a)         sort((a).begin(), (a).end())
#define uniq(a)         sort(a);(a).erase(unique((a).begin(), (a).end()), (a).end())
#define reverse(a)      reverse((a).begin(), (a).end())
#define ctos(c)         string(1, (c))
#define out(d)          cout << (d)
#define outl(d)         std::cout<<(d)<<"\n"
#define YES()           cout << "YES" << endl
#define NO()            cout << "NO" << endl
#define Yes()           cout << "Yes" << endl
#define No()            cout << "No" << endl
#define ceil(x, y)      ((x + y - 1) / (y))
#define debug(x)        cerr << #x << ": " << (x) << '\n'
#define debug2(x, y)    cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v)          for (size_t _ = 0; _ < v.size(); ++_){ cerr << #v << "[" << _ << "] : " << v[_] << '\n'; }

using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;

const ll MOD = 1000000007; // 10^9 + 7
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

void solve() {
  int n; cin >> n;
  vector<int> a(n); rep(i, n) cin >> a[i], --a[i];
  vector<int> ans;

  while (a.size() > 0) {
    int pivot = -1;
    // debug(a.size());
    for (int i = a.size() - 1; i >= 0; i--) {
      if (a[i] == i) {
        // debug2(i, a[i]);
        pivot = i;
        break;
      }
    }
    if (pivot == -1) {
      outl(-1);
      return;
    }
    ans.push_back(a[pivot]);
    a.erase(a.begin() + pivot);
  }
  reverse(ans);
  for (int ai : ans) outl(ai + 1);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  fix(12);

  solve();
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <math.h>
#include<iostream>
#include <string>
using namespace std;
typedef long long ll;
#define pb pushback
#define fr(i,n) for(int i=0;i<n;i++)
#define frone(i,n) for(int i=1;i<=n;i++)
#define ifr(i,n) for(int i=n-1;i>=0;i--)


int main() {
    int n,k;
	cin >> n>>k;
    double ans;
    double kari;
    frone(i,n){
      kari=1.0;
      int kai=0;
      int j=i;
      while(j<k){
        j*=2;
        kai+=1;
      }
      fr(a,kai){
        kari/=2.0;
      }
      ans+=kari/n;
    }
    printf("%.12f\n",ans);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;
 
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()

const int mod=1e9+7;

int main(){
  int n;cin>>n;
  P ba[n];
  rep(i,n){
    int a,b;cin>>a>>b;
    ba[i]=(P(b,a));
  }
  sort(ba,ba+n);
  int cur=0;
  rep(i,n){
    if(cur+ba[i].second>ba[i].first){
      cout<<"No"<<endl;
      exit(0);
    }
    cur+=ba[i].second;
  }
  cout<<"Yes"<<endl;
}

Measured memory_bytes: 1920
#include<math.h>
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define ll long long int
#define py printf("Yes\n")
#define pn printf("No\n")
#define in cin>>
using namespace std;
const int INF = 1001001001;

int main()
{
    int a,b,tmp=0;
    in a>>b;
    if(b<10)tmp=a*10+b;
    else if(b<100)tmp=a*100+b;
    else tmp=a*1000+b;

    int hoge;
    hoge = (int)sqrt((double)tmp);
    if(hoge*hoge==tmp)py;
    else pn;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
#define REP(var, s, n) for (int var = (s); var < (n); ++var)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()

int main() {
  //
  string s;
  cin >> s;
  rep(i, s.size() - 1) {
    if (s[i] == s[i + 1]) {
      cout << "Bad" << endl;
      return 0;
    }
  }
  cout << "Good" << endl;
  return 0;
}


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

int N;
int t[1000000];

int main(){
  cin>>N;
  
  for(int i=0;i<N;i++){
    int x;
    cin>>x;
    t[x]++;

    if(t[x]>2 || (x==0&&t[x]>1) ){
      cout<<0<<endl;
      return 0;
    }
  }
  
  long long ans=1;
  long long mod=1e9+7;
  for(int i=0;i<N/2;i++){
    ans=(ans*2LL)%mod;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 640
#include <stdio.h>
 
int main () {
	int n,flag = 1;
	scanf("%d", &n);//isi space array word
	char word[n];  //terisi sesuai inputan
	scanf("%s", word);

	if (n % 2 != 0) {
		flag = 0; //kalau ganjil udh pasti salah
	}
	
	for(int i = 0; i < n / 2;i++) {     				//diloop n dibagi dua agar bisa membandingkan
		if (word[i] != word[n / 2 + i]) {  				//kalau sama arraynya print yes
			flag = 0;
		    break;										// contoh n 6 maka diloop 3kali
		}
	}													//  word[0] ==  word[3] 
	flag ? puts("Yes") : puts("No");					//	word[1] ==  word[4]
														//	word[2]	==	word[5]}
	
	return 0;
}

Measured memory_bytes: 1624
word = input()

num = int(input())
for index in range(num):
    
    code = input().split()
    instruction = code[0]
    start, end  = int(code[1]), int(code[2])

    if instruction == "replace":
        word = word[:start] + code[3] + word[end+1:]
    elif instruction == "reverse":
        reversed_ch = "".join(reversed(word[start:end+1]))
        word = word[:start] + reversed_ch + word[end+1:]
    else:
        print(word[start:end+1])


Measured memory_bytes: 5616
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, t;
  cin >>N;
  vector<int>A(N,0);
  t=N/2;
  for(int i=0; i<N; i++){
    int a;
    cin >>a;
    if(N%2==0){
      if(i%2==0) t+=i;
      else t-=i;
      A[t]=a;
    }
    else{
      if(i%2==0) t-=i;
      else t+=i;
      A[t]=a;
    }
  }
  for(int i=0; i<N; i++){
    if(i!=N-1) cout <<A[i] <<" ";
    else cout <<A[i] <<endl;    
  }
}

Measured memory_bytes: 2944
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <set>
#include <stdio.h> 
using namespace std;
	typedef long long int lli;
	const int MaxN=200005;
	#define fst first
	#define snd second
	#define mp make_pair
	lli mcd(lli a,lli b){	
		if(a==0)return b;
		return mcd(b%a,a);
	}		
	int pre[MaxN];
int main(){
	lli t,N,Q,i,j,p,q,res=0;
	cin>>N>>Q;
	string word;
	cin>>word;
	for(i=1;i<word.size();i++){
		if(word[i]=='C'&&word[i-1]=='A'){
			pre[i+1]=pre[i]+1;
		}
		else pre[i+1]=pre[i];
	}
	while(Q--){
		cin>>p>>q;
		res=pre[q]-pre[p-1];
		if(word[p-1]=='C'&&word[p-2]=='A')res-=1;
		cout<<res<<"\n";
	}
}

Measured memory_bytes: 1472
import sys
import math

mod = 10 ** 9 + 7

N = int(input())

if N <= 1:
    print(0)
    sys.exit()

# ans = comb(N, 2, exact=True) * 2 * (8 ** (N - 2)) + (9 ** N - 8 ** N) * 2
ans = 10 ** N - 8 ** N - (9 ** N - 8 ** N) * 2
print(ans % mod)



Measured memory_bytes: 83948
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
 
using namespace std;
 
const int MAX_N = int(1e6) + 10;
const long long int MOD=1e9+7;
const long long int INF=1e18;
 
 
typedef long long int ll;
typedef unsigned long long int llu;


ll max(ll a,ll b){
	return a>b?a:b;
}
int main()
{
	int a,b; cin>>a>>b;
  cout<<a*b;

}

Measured memory_bytes: 3632
#include <stdio.h>

int e[3];

void sort(int a[]){
  int i, j, v;
  for (i = 1; i < 3; i++) {
    v = a[i];
    j = i - 1;
    while (j >= 0 && a[j] > v) {
      a[j+1] = a[j];
      j--;
    }
    a[j+1] = v;
  }
}

int main(){
  int n;
  int i;

  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%d %d %d", &e[0], &e[1], &e[2]);
    sort(e);
    if (e[2]*e[2] == e[1]*e[1] + e[0]*e[0]) {
      printf("YES\n");
    }
    else {
      printf("NO\n");
    }
  }

  return 0;
}


Measured memory_bytes: 2060
#include <bits/stdc++.h> 
using namespace std; 
  
int main() {
    
    int a[5];
    int ans=0;
    for(int i=0;i<5;i++){
        cin>>a[i];
        if(a[i]==0){
            ans=i;
            break;
        }
    }
    cout<<ans+1;
    return 0;
}

Measured memory_bytes: 3620
#pragma region include
#include <stdio.h>
#include <string>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#pragma endregion
using namespace std;

#pragma region マクロ
// 配列の長さを取得する(ただし関数内ではポインタサイズに注意)
#define SIZE_OF_ARRAY(array) sizeof(array) / sizeof(*array)

// ソート
#define Sort(array, length) sort(array, array + length)
#define SortDESC(array, length) sort(array, array + length, greater<>())

// 配列の最大値、最小値取得
#define MAX_OF_ARRAY(array, length) *max_element(array, array + length)
#define MIN_OF_ARRAY(array, length) *min_element(array, array + length)
#pragma endregion

#pragma region Utility
#pragma region 配列要素の合計値を取得
template <typename T>
T getSum(T array[], int length)
{
    T sum = 0;
    for (int i = 0; i < length; i++)
    {
        sum += array[i];
    }
    return sum;
}
#pragma endregion

#pragma region ToString(int)
string ToString(int i)
{
    char buffer[1000];
    sprintf(buffer, "%d", i);
    return string(buffer);
}
#pragma endregion

#pragma region 10進数からN進数(<=10)へ変換
string convertToN(long n, int base)
{
    string ans = "";
    while(n != 0)
    {
        int temp = n % base;    // 1桁取得
        ans = ToString(temp) + ans;
        n /= base;
    }
    return ans;
}
#pragma endregion
#pragma endregion

int main()
{
    // ***  問題のpathを記載 ***
    // https://atcoder.jp/contests/abc156/tasks/abc156_b

    // 標準入力から値を取得
    int n, base;
    scanf("%d %d", &n, &base);

    // 結果出力
    string ans = convertToN(n, base);
    printf("%lu\n", ans.size());

    // 成功時は必ず0を返す
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define inf 1<<31

#define MX 100

struct node{

    int c,s,f;
    node(int _c,int _s,int _f)
    {
        c=_c;
        s=_s;
        f=_f;
    }

};

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

    int n;
    cin>>n;
    int c,s,f;
    vector<node>v;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&c,&s,&f);
        v.push_back(node(c,s,f));
    }
    LL ans=0;
    for(int i=0;i<n-1;i++)
    {
        ans=v[i].s+v[i].c;
        //cout<<i+1<<"  : "<<ans<<endl;

        for(int j=i+1;j<n-1;j++)
        {
            node p = v[j];
            if(ans<p.s)ans=p.s;
            else if(ans>p.s)
            {
                if(ans%p.f!=0)
                {
                    int tm=ans%p.f;
                    ans-=tm;
                    ans+=p.f;
                }
            }

            ans+=p.c;
            //cout<<i+1<<"  : "<<ans<<endl;
        }

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

    }
    puts("0");


    return 0;
}




Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
#include<stack>
using namespace std;
typedef long long ll;
const int maxn=200005;

int a[maxn];
int n;

int main() {
    //freopen("in.cpp","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int ret=0;
    for(int i=1;i<=n;i++)if(a[a[i]]==i)ret++;
    printf("%d\n",ret/2);
    return 0;
}


Measured memory_bytes: 640
# cf16-exhibition-final-openA - 1D Matching
import sys
input = sys.stdin.readline

def calc(x, y, total):
    MOD = 10 ** 9 + 7
    if y:
        total = (total * y) % MOD
        y -= 1
    else:
        x += 1
    return x, y, total

def main():
    N = int(input())
    A = tuple(map(int, [input() for _ in range(N)]))
    B = tuple(map(int, [input() for _ in range(N)]))
    C = sorted([(i, 1) for i in A] + [(i, 0) for i in B])
    ans, a, b = 1, 0, 0
    for i, t in C:
        if t:  # laptop
            a, b, ans = calc(a, b, ans)
        else:  # power sources
            b, a, ans = calc(b, a, ans)
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 28328
import itertools
import math
import fractions
import functools

n, m, x = map(int, input().split())

a_do = []
for i in range(n):
    a = list(map(int, input().split()))
    a_do.append(a)


nums = []
for i in range(n):
    nums.append(i)

temp = []
for i in range(1, n+1):
    for v in itertools.combinations(nums, i):
        rikaido = [0] * (m+1)
        for j in range(len(v)):
            for k in range(m+1):
                rikaido[k] += a_do[v[j]][k]

        temp.append(rikaido)

minimum = 10**20
for i in range(len(temp)):
    ok = True
    for j in range(1, m+1):
        if temp[i][j] < x:
            ok = False
    if(ok):
        minimum = min(minimum, temp[i][0])

if(minimum == 10**20):
    print(-1)
else:
    print(minimum)


Measured memory_bytes: 74016
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define DEBUG true
#ifdef ONLINE_JUDGE
#undef DEBUG
#define DEBUG false
#endif 

using namespace std;

#define MAXN ((int)1e2+5)
#define MOD ((int)1e9 + 7)
#define INF ((int)1e9 + 9)
#define ll long long
#define _ << " " <<
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define TRACE(x) if(DEBUG) cerr << #x << " = " << x << endl;
#define TRACE2(x,y) if(DEBUG) cerr << #x << " = " << x << " | " << #y << " = " << y << endl;
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pii pair<int,int>
#define mid ((l+r)/2)

int n;
priority_queue <double,vector<double>, greater<double> >q;

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin >> n;
	for (int i = 0,a; i < n; ++i)
	{
		cin >> a;
		q.push(a);
	}

	while(q.size() > 1)
	{
		double p1 = q.top();
		q.pop();
		double p2 = q.top();
		q.pop();
		
		q.push((p1 + p2) / 2);		
	}


	cout << fixed << q.top() << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()

template<class T>
static inline std::vector<T> ndvec(size_t&& n, T val) noexcept {
  return std::vector<T>(n, std::forward<T>(val));
}

template<class... Tail>
static inline auto ndvec(size_t&& n, Tail&&... tail) noexcept {
  return std::vector<decltype(ndvec(std::forward<Tail>(tail)...))>(n, ndvec(std::forward<Tail>(tail)...));
}

template<class T, class Cond>
struct chain {
  Cond cond; chain(Cond cond) : cond(cond) {}
  bool operator()(T& a, const T& b) const {
    if(cond(a, b)) { a = b; return true; }
    return false;
  }
};
template<class T, class Cond>
chain<T, Cond> make_chain(Cond cond) { return chain<T, Cond>(cond); }

int main() {
  i64 N;
  cin >> N;
  string S;
  cin >> S;

  vector<i64> A(N);
  rep(i,0,N) {
    if(S[i] == 'R') {
      A[i] = 1;
    }
    else if(S[i] == 'B') {
      A[i] = 2;
    }
    else {
      A[i] = 4;
    }
  }

  vector<vector<i64>> dp(N + 1, vector<i64>(8));
  dp[0][0] = 1;
  rep(i,0,N) {
    rep(b,0,8) {
      dp[i + 1][b] += dp[i][b];
      if(!(b & A[i])) {
        dp[i + 1][b | A[i]] += dp[i][b];
      }
    }
  }
  i64 ans = 0;
  rep(center,0,N) {
    for(i64 i = center - 1, j = center + 1; i >= 0 && j < N; i--, j++) {
      if(A[i] != A[center] && A[center] != A[j] && A[i] != A[j]) {
        ans++;
      }
    }
  }
  cout << dp[N][7] - ans << endl;
}


Measured memory_bytes: 4076
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <list>
#include <queue>
using namespace std;

int inf = (1 << 30);
int mod = 1e9 + 7;
int64_t inf64 = (1LL << 60);

template <typename T>
T gcd(T a, T b) {
    if(b == 0) return a;
    else return gcd(b, a % b);
}

template <typename T>
T lcm(T a, T b) {
    T g = gcd(a, b);
    return a / g * b;
}

bool check(vector<int> a, int index, int key){
    if(a[index] >= key) return true;
    else return false;
}

int lower_bound(vector<int> a, int key){
    int left = -1, right = a.size();
    while(right - left > 1){
        int mid = left + (left + right) / 2;
        if(check(a, mid, key)) right = mid;
        else left = mid;
    }
    return right;
}

int main(){

    int A, B, C;
    cin >> A >> B >> C;

    if((A == 5 && B == 5 && C == 7) || (A == 5 && B == 7 && C == 5) || (A == 7 && B == 5 && C == 5)) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}

Measured memory_bytes: 256
// luogu-judger-enable-o2
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<string>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
typedef long long LL;
typedef double db;
using namespace std;
template<typename T>void read(T &x) {
    char ch=getchar(); x=0; T f=1;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
}
string a,b;
int main(){
    cin>>a>>b;
    for(int i=0;i<min(a.size(),b.size());i++)
    cout<<a[i]<<b[i];
    if(a.size()>b.size())
    cout<<a[a.size()-1]<<endl;
    else
    cout<<endl;
    return 0;
}





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

using namespace std;

string A, B;
int n, sol;

int main() {
	cin >> n >> A >> B;
	sol = 2*n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (A.substr(i, n-i) == B.substr(0, j+1)) {
				sol = min(sol, 2*n-j-1);
			}
		}
	}
	cout << sol;
	return 0;
}
		


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef set<int> S;
int n,a[20];
int dfs(int idx,int A,int B){
  if(idx==n) return abs(A-B);
  return min(dfs(idx+1,A+a[idx],B),dfs(idx+1,A,B+a[idx]));
}

int main(){
  while(cin>>n,n){
    for(int i=0;i<n;i++)cin>>a[i];
    cout << dfs(0,0,0)<<endl;
  }
  return 0;
}

Measured memory_bytes: 1160