akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
#define sz(x) ((int)(x).size())
using namespace std;
ll getmul(ll n){
    int m1=10,m2=0;
    while(n>0){
        int k=n%10;
        m2=max(m2,k);
        m1=min(m1,k);
        n=n/10;
    }
    return m1*m2;
}
int main(){
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     ll int k;
     string s;
     cin>>k>>s;
     if(sz(s)<=k)
         cout<<s<<endl;
     else{
         string j=s.substr(0,k);
         cout<<j<<"..."<<endl;
     }
 return 0;
}

Measured memory_bytes: 3656
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i, n) for(int i=(n); i>=0; --i)
#define FOR(i, n, m) for(int i=(m), i##_len=(n); i<i##_len; ++i)
#define EACH(i, v) for(const auto& i : v)
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class Value>using vec = vector< Value >;
using ll = long long;
using P = pair< long long, long long >;
#define fi first
#define se second
#define el endl
#pragma endregion


void Main();

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

void Main(){
    char c;
    cin >> c;
    if('a'<=c && c<= 'z'){
        cout << 'a' << el;
    }else{
        cout << 'A' << el;
    }
    // Failed to predict input format
}




Measured memory_bytes: 3568
import java.util.Scanner;
import java.util.Arrays;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] q = new long[n];
		long sum=0;
		for(int i = 0; i < n; i++){
			long a = sc.nextLong();
			long b = sc.nextLong();
			q[i]=a+b;
			sum-=b;
		}
		Arrays.sort(q);
		for(int i=n-1; i>=0; i-=2){
			sum+=q[i];
		}
		System.out.println(sum);
	}
}

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

int main(){
  int n,i;
  cin >> n;
  if(n == 1){
    i = 1;
  }
  else if(2<=n&&n<=3){
    i=2;
  }
  else if(4<=n&&n<=7){
    i=4;
  }
  else if(8<=n&&n<=15){
    i=8;
  }
  else if(16<=n&&n<=31){
    i=16;
  }
  else if(32<=n&&n<=63){
    i=32;
  }
  else {
    i=64;
  }
  
  cout << i << endl;
}

Measured memory_bytes: 256
# C
N = int(input())
H = list(map(int, input().split()))
flag = True
tmp = H[N-1]
for i in range(N-1, 0, -1):
    if H[i - 1] - H[i] > 1:
        flag = False
    elif H[i - 1] - H[i] == 1:
        H[i - 1] -= 1
    else:
        pass
    if flag == False:
        break
if flag:
    print("Yes")
else:
    print("No")

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

using namespace std;

#define mod 1000000007
#define ll long long int
#define mk make_pair
#define pb push_back
#define xx first
#define yy second
#define ar array

double pi=3.141592653589793238;
const int M = 1e9+7;
const int Nmax=5005;
const int MM = 1e7+1;
const int N=200010;

int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T=1;
//cin>>T;
while(T--){
ll n,k;
cin>>n>>k;
ll arr[n];
ll m=1;
for(int i=0;i<n;i++){
    cin>>arr[i];
}
for(int i=k;i<n;i++){
    if(arr[i]>arr[i-k])cout<<"Yes\n";
else cout<<"No\n";
}
}
return 0;
}


Measured memory_bytes: 5164
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FFOR(i,a,b) for(int i=(a);i<=(b);i++)
#define REP(i,b) FOR(i,0,b)
#define RREP(i,b) FFOR(i,1,b)
#define PB push_back
#define F first
#define S second
#define BE(c) c.begin(),c.end()
using namespace std;
typedef long long LL;
typedef LL ut;
typedef long double ld;
typedef pair<ut,ut> pr;
typedef vector<pr> Vpr;
typedef vector<ut> VI;
typedef pair<ut,pr> ppr;
typedef priority_queue<pr,Vpr, greater<pr> > PQ;
const int SIZE=5+3*1e+4;
const ut INF=1<<30;
const ld eps=1e-6;
const LL mod=7+1e+9;

int main() {
	int N, K, ng[10] = {0};
	cin >> N >> K;
	REP(i,K){
		int d;
		cin >> d;
		ng[d] = true;
	}
	FOR(i,N,100001){
		int t = i;
		bool ok = true;
		while(1){
			if(t == 0){
				break;
			}
			int m = t % 10;
			t /= 10;
			if(ng[m]){
				ok = false;
				break;
			}
		}
		if(ok){
			cout << i << endl;
			break;
		}
	}
    return 0;
}


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

int main(){
  int a, b;
  cin >> a >> b;
  
  float c;
  c = (a+b)%2;
  float d, e;
  d = a;
  e = b;
  cout << (d+e)/2 + c/2 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int MAX_N = 20;
int A[MAX_N];
P xy[MAX_N][MAX_N];

int main()
{
	int N,x,y;
	cin >> N;
	rep(i,N)
	{
		cin >> A[i];
		rep(j,A[i])
		{
			cin >> x >> y;
			x--;
			xy[i][j] = P(x,y);
		}
	}

	int ans = 0;

	for (int bits = 0; bits < (1 << N); ++bits)
	{
		//cout << "bits:" << bits << endl;
		bool flag = true;
		rep(i,N)
		{
			if ((1 << i) & bits)
			{
				//cout << "checking:" << i << endl;
				rep(j,A[i])
				{
					if (xy[i][j].second != ((1 << xy[i][j].first) & bits) >> xy[i][j].first)
					{
						flag = false;
						//cout << bits << ":false " << ((1 << xy[i][j].first) & bits) << " " << xy[i][j].second << endl;
					}
				}
			}
		}

		if (flag)
		{
			int cnt = 0;
			rep(i,N)
			{
				if ((1 << i) & bits) cnt++;
			}
			//cout << bits << ":true cnt:" << cnt << endl;
			ans = max(ans,cnt);
			//cout << ans << endl;
		}
	}

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

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main(void)
{
	int N, L = 0;
	char W[100][11];
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%s", W[i]);

	}
	for (int i = 0; i < N-1; i++) {	
		L = strlen(W[i]);
		if (W[i][L-1] != W[i+1][0]) {
			printf("No");
			return 0;
		}
	}
	for (int i = 1; i < N; i++) {
		for (int j = 0; j < i; j++) {
			if (strcmp(W[i],W[j])==0) {
				printf("No");
				return 0;
			}
		}
	}
	printf("Yes");
	return 0;
}

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


int main()
{
    int i,j,N;
    int* arr;
    int sum=0;
    scanf("%d",&N);
    
    arr = (int*)malloc(sizeof(int));
    
    for(i=0;i<N;i++)
    {
        scanf("%d",&arr[i]);
    }
    
    
    for(i=0;i<N;i++)
    {
        for(j=i+1;j<N;j++)
        {
            sum += arr[i]*arr[j];
        }
    }

    printf("%d",sum);
    return 0;
}

Measured memory_bytes: 128
#include<iostream>//动态规划剪枝是么从dp0开始
#include<cmath>
#include<algorithm>
#include<string>//stl和数据结构应该一起训练
#include<memory.h>
using namespace std;
int dp[1001][1001];//模拟三种操作，首先分析题目看看能不能模拟操作
int n;
int solve(string a,string b)
{	
	int len1=a.size(),len2=b.size();
	for(int i=0;i<=len1;i++)
		dp[i][0]=i;
	for(int j=0;j<=len2;j++)
		dp[0][j]=j;
	for(int i=1;i<=len1;i++)
		for(int j=1;j<=len2;j++)
			if(a[i-1]==b[j-1])
			dp[i][j]=dp[i-1][j-1];
			else
				dp[i][j]=min(dp[i-1][j]+1,min(dp[i-1][j-1]+1,dp[i][j-1]+1));

return dp[len1][len2];
}
int main()
{
	string a,b;
	cin>>a>>b;
	cout<<solve(a,b)<<endl;
	return 0;
}


Measured memory_bytes: 7136
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
#define MOD int(1e9 + 7)

int main()
{
    long long N, M;
    vector<vector<long long>> A;

    cin >> N >> M;
    for (long long i = 0; i < N; i++)
    {
        vector<long long> tmp;
        for (long long j = 0; j < 3; j++)
        {
            long long t;
            cin >> t;
            tmp.push_back(t);
        }
        A.push_back(tmp);
    }

    long long max_v = 0;
    for (long long i = -1; i <= 1; i += 2)
    {
        for (long long j = -1; j <= 1; j += 2)
        {
            for (long long k = -1; k <= 1; k += 2)
            {
                vector<vector<vector<long long>>> dp(N + 1, vector<vector<long long>>(M + 1, vector<long long>(3, 0)));
                for (long long l = 1; l < N + 1; l++)
                {
                    for (long long m = 1; m <= M; m++)
                    {
                        long long eat_v = 0;
                        long long neat_v = 0;
                        eat_v += i * (dp[l - 1][m - 1][0] + A[l - 1][0]);
                        eat_v += j * (dp[l - 1][m - 1][1] + A[l - 1][1]);
                        eat_v += k * (dp[l - 1][m - 1][2] + A[l - 1][2]);
                        neat_v += i * (dp[l - 1][m][0]);
                        neat_v += j * (dp[l - 1][m][1]);
                        neat_v += k * (dp[l - 1][m][2]);

                        if (l == m || eat_v > neat_v)
                            for (long long n = 0; n < 3; n++)
                                dp[l][m][n] = dp[l - 1][m - 1][n] + A[l - 1][n];
                        else
                            for (long long n = 0; n < 3; n++)
                                dp[l][m][n] = dp[l - 1][m][n];
                    }
                }
                max_v = max(max_v, i * dp[N][M][0] + j * dp[N][M][1] + k * dp[N][M][2]);
            }
        }
    }

    cout << max_v << endl;
}

Measured memory_bytes: 55168
#include<bits/stdc++.h>
#define ll long long

int take() {
    int n;
    scanf("%d",&n);
    return n;

}
double ttake() {
    double n;
    scanf("%lf",&n);
    return n;
}
ll takes() {
    ll n;
    scanf("%lld",&n);
    return n;

}
#define M 3001
#define Int take()
#define Dnt ttake()
#define LL takes()

#define fr(n) for(int i=1;i<=n;i++)
#define rfr(n) for(int i=n;i>=1;i--)
int cas;
#define print printf("Case %d:",++cas)
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define mk  make_pair
#define fill(x,v) memset(x,v,sizeof x)
using namespace std;

bool approximatelyEqual(float a, float b, float epsilon) {
    return fabs(a - b) <= ( (fabs(a) < fabs(b) ? fabs(b) : fabs(a)) * epsilon);
}

bool essentiallyEqual(float a, float b, float epsilon) {
    return fabs(a - b) <= ( (fabs(a) > fabs(b) ? fabs(b) : fabs(a)) * epsilon);
}

bool definitelyGreaterThan(float a, float b, float epsilon) {
    return (a - b) > ( (fabs(a) < fabs(b) ? fabs(b) : fabs(a)) * epsilon);
}

bool definitelyLessThan(float a, float b, float epsilon) {
    return (b - a) > ( (fabs(a) < fabs(b) ? fabs(b) : fabs(a)) * epsilon);
}
//////////////////////////////////////////


int main(){
    ll n=LL,p;
    int d=0;
    p=n;
    while(p){
        d+=(p%10);
        p/=10;
    }

    if(n%d) puts("No");
    else puts("Yes");

    return 0;
}



Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

int main() {
    ll a, b;
    cin >> a >> b;
    cout << max(max(a + b, a - b), a * b) << endl;
    return 0;
}


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

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

#define rep(i, n) for (int i = 0; i < n; i++)
#define rep_op(i, a, n) for (int i = a; i < n; i++)
#define rep_d(j, n) for (int j = n; j >= 0; j--)
#define rep_d_op(j, n, a) for (int j = n; j >= a; j--)

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

const int MOD = 1000000007;

const vector<int> dx = {1, 0};
const vector<int> dy = {0, 1};
const ll INF = 1LL << 60;

// int max = *std::max_element(vec.begin(), vec.end());
// int sum = accumulate(list, list + size, 0);

int GCD(int a, int b) { return b ? GCD(b, a % b) : a; }

bool is_prime(int x)
{
    if (x <= 1)
    {
        return false;
    }
    for (int i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    int x;
    cin >> x;
    while (!is_prime(x))
    {
        x++;
    }
    cout << x << endl;
}


Measured memory_bytes: 256
n = int(input())
a = map(int, input().split())
is_ok = True
for num in a:
    if num % 2 == 0:
        if num % 3 == 0 or num % 5 == 0:
            # print('ok', num)
            continue
        else:
            # print('ng', num)
            is_ok = False
            break

if is_ok:
    print('APPROVED')
else:
    print('DENIED')


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

#define llint long long int

int main(void){

  llint a, b;
  std::cin >> a >>b;

  if((a-b)%2 == 0){
    llint res = (a+b)/2;
    std::cout << res << std::endl;
  }else{
    std::cout << "IMPOSSIBLE" << std::endl;
  }
  return 0;
}


Measured memory_bytes: 256
# https://atcoder.jp/contests/abc157/tasks/abc157_e
# セグメント木
# 各文字をビットに対応させる(セグ木を26本持っても良い)
import sys
read = sys.stdin.readline
from functools import reduce


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


class SqrtDecomposedList:
    def __init__(self, ls, segfunc, identity_element):
        from math import sqrt, ceil
        from copy import copy
        self.f = segfunc  # queryのfunction
        self.ide = identity_element
        self.n = len(ls)
        self.ls = copy(ls)
        self.b = ceil(sqrt(self.n))
        self.bucket = [self.ide] * (self.b + 1)
        self._build()

    def _build(self):
        for d in range(self.b):
            self.bucket[d] = reduce(
                self.f, self.ls[(d * self.b):((d + 1) * self.b)], self.ide)
        # for i, v in enumerate(self.ls):
        #     self.bucket[i // self.b] = \
        #         self.f(v, self.bucket[i // self.b])

    def __getitem__(self, idx):
        return self.ls[idx]

    def update(self, i, x):
        '''i番目の要素をxに更新する O(√n)'''
        self.ls[i] = x
        s = i // self.b * self.b
        t = s + self.b
        # print(i, self.b, i // self.b, s, t)
        self.bucket[i // self.b] = reduce(self.f,
                                          self.ls[s:t], self.ide)

    def query(self, l, r):
        '''半開区間[l,r)で指定すること O(√n)'''
        if r - l < 2 * self.b:
            return reduce(self.f, self.ls[l:r])
        l_bucket = (l - 1) // self.b + 1
        r_bucket = r // self.b  # 半開区間なのでこれでいい
        ret = reduce(self.f, self.bucket[l_bucket:r_bucket], self.ide)
        ret = self.f(
            reduce(self.f, self.ls[l:(l_bucket * self.b)], self.ide),
            ret)
        ret = self.f(
            reduce(self.f, self.ls[(r_bucket * self.b):r], self.ide),
            ret)
        return ret


def segfunc(x, y):
    # 処理したい内容
    return x | y


def moji_to_bit(a):
    return 1 << (ord(a) - ord('a'))


def bit_to_sum(n):
    return sum([(n >> i) & 1 for i in range(n.bit_length())])


N = read_a_int()
S = read()[:-1]
S_bit = [moji_to_bit(s) for s in S]

# build segment tree
st = SqrtDecomposedList(S_bit, segfunc, 0)

Q = read_a_int()
for q in range(Q):
    com, a, b = read().split()
    if int(com) == 1:
        i, c = int(a) - 1, b
        st.update(i, moji_to_bit(c))
    else:
        l, r = int(a) - 1, int(b)
        print(bit_to_sum(st.query(l, r)))


Measured memory_bytes: 78232
N=int(input())
X=[list(map(int,input().split())) for i in range(N)]
A=[0]
B=[0]
C=[0]
for i in range(N):
  a=X[i][0]+max(B[-1],C[-1])
  b=X[i][1]+max(A[-1],C[-1])
  c=X[i][2]+max(B[-1],A[-1])
  A+=[a]
  B+=[b]
  C+=[c]
print(max(A[-1],B[-1],C[-1]))

Measured memory_bytes: 42544
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define pb push_back
#define ll long long
#define ld long double
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define X first
#define Y second
#define fr(i,a,n) for(int i=a;i<n;i++)
#define frr(i,n,a) for(int i=n;i>=a;i--)
#define mod 1000000007
#define fi ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define ordered_set_pair tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update>



int n;
int a[100005],b[100005];


bool fun(ll p)
{
    ll k= ((ll)n* (n+1))/2 ;
   ll bnd=(k>>1) + (k%2);
    ordered_set_pair st;
    fr(i,0,n)
    {
        if(a[i]>=p)
        b[i]=1;
        else
        b[i]=-1;
    }
    st.insert({0,0});
    st.insert({b[0],1});
    ll ans=0,cnt=2;
    if(b[0]<0)
    ans=1;
    fr(i,1,n)
    {
        b[i]+=b[i-1];
        st.insert({b[i],i+1});
        cnt++;
      
        ans+=cnt-1-st.order_of_key({b[i],i+1});
    }
   
    return (k-ans)>= bnd;
}

int main()
{
    cin>>n;
   fr(i,0,n)
   {
    cin>>a[i];
    
   }

   ll s=0,e=1e9+12,ans=-1;
   while(e-s>1)
   {
      ll mid=(s+e)>>1;
      
      if (fun(mid))
      {
         s=mid;
      
      }
      else
      e=mid;
   }
  
   cout<<s;
}

Measured memory_bytes: 10560
a = list(map(int,input().split()))
N = a[0]
M = a[1]

list = []
for i in range(M):
  a,b=input().split()
  list.append((int(a), b))

bool_ac = []
ac_sum = 0
wa = []
wa_sum = 0
for i in range(N):
  bool_ac.append(0)
  wa.append(0)


for i in range(M):
  j = list[i][0] - 1
  if list[i][1] == "AC" and bool_ac[j] != 1:
    bool_ac[j] = 1
    ac_sum += 1
    wa_sum += wa[j]
  elif list[i][1] == "WA":
    if bool_ac[j] == 0:
      wa[j] += 1

print(ac_sum, end=" "), print(wa_sum)

Measured memory_bytes: 20532
import sys
n = int(input())
x = list(map(int, input().split()))

min = 100
max = 0
for i in range(n):
  if min > x[i]:
    min = x[i]
  if max < x[i]:
    max = x[i]

best = sys.maxsize
for i in range(min, max+1, 1):
  now = 0
  for j in range(n):
    now = now + (x[j] - i)**2
  if best > now:
    best = now
print(best)
    
    

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

#define mt make_tuple
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sqr(x) ((ll)(x) * (x))

int main()
{
    string s;

    cin >> s;

    char prvi = '0';
    char drugi = '1';

    string prviS = "";
    string drugiS = "";

    int n = s.size();

    for(int i = 0; i < n; i++)
    {
        prviS += prvi;
        drugiS += drugi;
        swap(prvi, drugi);
    }

    int brojac1 = 0, brojac2 = 0;

    for(int i = 0; i < n; i++)
    {
        if(s[i] != prviS[i])brojac1++;
        if(s[i] != drugiS[i])brojac2++;
    }

    cout << min(brojac1, brojac2) << '\n';

    return 0;
}


Measured memory_bytes: 768
N = int(input())
p = list(map(int, input().split()))
 
# 条件はN=O(10^5)よりO(N)で解く
# 二重ループをすると、O(N^2)で間に合わない
# 累積和の問題（ABC-154-Dとか）と同じ発想が使える！
 
# 具体的にO(N)で解くために、最初に各iに対して、i番目までの最小値を求めておく
m = [0]*(N)
m[0] = p[0]
for i in range(1, N):
  m[i] = min(m[i-1], p[i])

# 各iまでの最小値とi番目の値を比較し、最小値の方が大きければよい
ans = 1
for i in range(1, N):
  if m[i-1] >= p[i]: ans += 1

print(ans)

Measured memory_bytes: 32220
necessity = [2, 5, 5, 4, 5, 6, 3, 7, 6]
n, m = gets.split.map(&:to_i)
nums = gets.split.map(&:to_i)
nums.delete(4) if nums.include?(1)
nums.delete(2) if nums.include?(3) || nums.include?(5)
nums.delete(3) if nums.include?(5)
nums.delete(6) if nums.include?(7) || nums.include?(9)
nums.delete(9) if nums.include?(7)
nums.delete(5) if nums.include?(1) && nums.include?(7)
nums.delete(8) if nums.include?(1) && nums.include?(5)
num_sticks = nums.map { |n| [n, necessity[n - 1]] }
num_sticks.sort! { |a, b| (a[1] <=> b[1]).nonzero? || b[0] <=> a[0] }
selected_nums = Hash.new(0)
reduced_sticks = [(n - 30), 0].max
first_num, first_stick = num_sticks.first
div, mod = reduced_sticks.divmod(first_stick)
selected_nums[first_num] += div
rest_sticks = n - (reduced_sticks - mod)
queue = [[rest_sticks, selected_nums]]
options = []
until queue.empty?
  rest, selected = queue.shift
  if rest == 0
    options << selected
  else
    num_sticks.each do |num, stick|
      rest_dup = rest
      selected_dup = selected.dup
      if rest_dup >= stick
        rest_dup -= stick
        selected_dup[num] += 1
        queue << [rest_dup, selected_dup]
      end
    end
  end
end

ans = []
if options.size > 30
  options = options[-30..-1]
end
options.each do |hash|
  tmp = []
  hash.each do |k, v|
    v.times { tmp << k }
  end
  ans << tmp.sort { |a, b| b <=> a }.join.to_i
end
puts ans.max


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

int main(void){
    int a, b;
    cin >> a >> b;
    
    int cnt = 0;
    int i;
    for(i = a; i <= b; i++){
        if(i / 10000 == i % 10 && i / 1000 % 10 == i / 10 % 10){
            cnt++;
        }
    }
    
    cout << cnt << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int main(){
  int N;
  cin >> N;
  string S;
  cin >> S;
  string T;
  char c = 'W';
  for (int i = 0; i < N * 2; i++){
    if (S[i] != c){
      T += 'L';
      c = 'B' + 'W' - c;
    } else {
      T += 'R';
      c = 'B' + 'W' - c;
    }
  }
  int cnt = 0;
  for (int i = 0; i < N * 2; i++){
    if (T[i] == 'L'){
      cnt++;
    }
  }
  if (cnt != N){
    cout << 0 << endl;
  } else {
    int L = 0;
    long long ans = 1;
    for (int i = 0; i < N * 2; i++){
      if (T[i] == 'L'){
        L++;
      } else {
        ans *= L;
        ans %= MOD;
        L--;
      }
    }
    for (int i = 1; i <= N; i++){
      ans *= i;
      ans %= MOD;;
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 3908
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<numeric>
#include<utility>
#include<unordered_map> //hash map

#define rep(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define rrep(i,a,n) for(int (i)=(a);(i)>=(n);(i)--)

#define INF 1000000000
#define MOD 1000000007

typedef  long long ll;

using namespace std;

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;
}

double euclid_distance(double a,double b){
    return sqrt(a*a+b*b);
}

ll gcd(ll  a,ll b){
    ll r;
    if(a < b){
        ll tmp;
        tmp = a;
        a = b;
        b = tmp;
    }
    while(r = a % b){
        a = b;
        b = r;
    }
    return b;
}

void Integer_factorization(long long int b,long long int n){
    long long int a = 2;
    long long int count = 0;
    long long int ans = 1;
    long long int ndash = n;
    if(b == 1) cout << n << endl;
    else{
    while(ndash >= a*a){
        if(n % a  == 0){
            count++;
            n/=a;

        if(count % b == 0){
            ans *= a;
        }
        }else{a++;count = 0;}
    }

    cout<<  ans << endl;
    }
}

ll r_fuct[2000];
ll fuct[2000];

//MOD逆元
void conb(ll n,ll k){
    fuct[0] = 1;
    for(int i = 1;i < k+1;i++){
        fuct[i] *= fuct[i-1]%MOD;
        
        ll b = MOD, u = 1, v = 0;
        ll value = fuct[i];
        while (b) {
            ll t = value / b;
            value -= t * b;
            swap(value, b);
            u -= t * v;
            swap(u, v);
        }
        u %= MOD;
        if (u < 0) u += MOD;
        r_fuct[i] = u;
    }
}

ll factrial(ll n){
    if(n == 0) return 1;
    ll p = factrial(n-1)*n%MOD;
    return p;
}

//MOD逆元
ll farmat(ll n,ll p){    
    if(p == 0) return 1;
    else if(p == 1) return n%MOD;
    ll d = farmat(n,p/2);
    if(p%2 == 0){
        return (d*d)%MOD;
    }else{
        return ((n*d)%MOD*d)%MOD;
    }
}

ll conbination(ll n,ll k){
    ll a = factrial(n);
    ll b = factrial(k);
    ll c = factrial(n-k);
    return (a*farmat(b,MOD-2)%MOD*farmat(c,MOD-2))%MOD;
}

int n;
int memo[10000000];

int fib(int i){
    if(i <= 1) return i;
    if(memo[i] != 0) return memo[i];
    return memo[i] = fib(i-1)+fib(i-2);
}

ll dig(ll n){
    ll d = 0;
    while(n != 0){
        n/=10;
        d++;
    }
    return d;
}
map<char,int> a;
void solve() {
    int n;
    cin >> n;
    cout << n*(n+1)/2 << endl;
    

}


int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);
	solve();
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int answer = 0;
		for(int i=1; i<=a; i++) {
			answer += i;
		}
		System.out.println(answer);
	}
}


Measured memory_bytes: 35748
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N = I()
d = III()

d.sort()
x1 = d[N//2-1]
x2 = d[N//2]

print(x2-x1)

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

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

ll lcm(ll a, ll b) {
    ll g = gcd(a, b);
    return a / g * b;
}


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

    cout << lcm(A, B) << endl;

}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <sstream>
#include <vector>
using namespace std;

#define REP2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define REP(i, n) REP2(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define FOREACH(i, c) for(auto i = (c).begin(); i != (c).end(); ++i)
#define BIT(n, m) (((n) >> (m)) & 1)

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

const ll inf = 1e15;
const ll mod = 1000 * 1000 * 1000 + 7;
const double eps = 1e-9;

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

template <typename T> ostream &operator<<(ostream &out, const vector<T> &v) {
  out << "[";
  REP(i, v.size()){
    if (i > 0) out << ", ";
    out << v[i];
  }
  out << "]";
  return out;
}



int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<int> > G(N);
  REP(i, M){
    int a, b;
    cin >> a >> b; a--, b--;
    G[a].push_back(b);
    G[b].push_back(a);
    // cout << a << " " << b << endl;
  }

  vector<int> color(N, -1);
  map<int, int> diffs;


  ll S = 0;
  REP(i, N) if (color[i] == -1){
    queue<int> que;
    que.push(i);
    color[i] = 0;
    vector<int> count(2, 0);

    
    while (!que.empty()){
      int v = que.front(); que.pop();
      // cout << v << endl;

      count[color[v]]++;
      for (int w : G[v]){
        if (color[w] == color[v]) {
          cout << -1 << endl;
          return 0;
        } else if (color[w] == -1){
          color[w] = 1 - color[v];
          que.push(w);
        }
      }
    }
    diffs[abs(count[1] - count[0])]++;
    S += *min_element(ALL(count));
  }
  vector<int> dp(2 * N + 1, -1);
  dp[0] = 0;
  for (const auto &p : diffs){
    REP(j, 2 * N + 1){
      if (dp[j] >= 0){
        dp[j] = p.second;
      } else if (j < p.first || dp[j - p.first] <= 0){
        dp[j] = -1;
      } else {
        dp[j] = dp[j - p.first] - 1;
      }
    }
  }
  ll res = 0;
  REP(i, 2 * N + 1) if (dp[i] != -1){
    ll A = S + i;
    ll B = N - A;
    // cout << A << " "<< B << endl;
    res = max(res,  A * B - M);
  }
  cout << res << endl;
  
  return 0;
}

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


int main() {
  int a,b,c;
  cin >> a>>b>>c;
  if(a==b&&b==c){
    cout<<1<<endl;
  }
  else if(a!=b&&a!=c&&b!=c){
    cout<<3<<endl;
  }
  else{
    cout<<2<<endl;
  }
  
}





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

using namespace std;
#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__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

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

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; }

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  int ind = -1;
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

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

  ll suma = 0;
  rep(i, n-1){
    suma += a[i];
    if(2*suma < a[i+1]){
      ind = i;
    }
  }

  cout << n - ind - 1 << endl;


  return 0;
}


Measured memory_bytes: 1024
import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    A = iss()
    B = iss()
    C = iss()
    print(A[0]+B[1]+C[2])

if __name__ == '__main__':
    main()


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

int main() {
    long long n, x;
    cin >> n >> x;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a.at(i);
    }

    long long ans = 0;
    for (int i = 0; i < n - 1; i++) {
        if (a.at(i) + a.at(i + 1) > x) {
            ans += min(a.at(i + 1), a.at(i) + a.at(i + 1) - x);
            a.at(i + 1) -= min(a.at(i + 1), a.at(i) + a.at(i + 1) - x);

            if (a.at(i) + a.at(i + 1) > x) {
                ans += a.at(i) + a.at(i + 1) - x;
                a.at(i) -= a.at(i) + a.at(i + 1) - x;
            }
        }
    }
    cout << ans << endl;
}   

Measured memory_bytes: 1024
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long ll;

const int N=1e5+5,Mo=1e9+7;

int n,cnt[26];
char st[N];

int main() {
	scanf("%d",&n);
	scanf("%s",st+1);
	fo(i,1,n) cnt[st[i]-'a']++;
	int ans=1;
	fo(i,0,25) ans=(ll)ans*(cnt[i]+1)%Mo;
	(ans+=Mo-1)%=Mo;
	printf("%d\n",ans);
	return 0;
}

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

int a, b, c, d;

int ans = 0;

int32_t main() {
	cin >> a >>b >> c >> d;
	a--;
	ans = b - a;
	ans -= b / c;
	ans += a / c;
	ans -= b / d;
	ans += a / d;
	ans -= a / (c * d / __gcd(c, d));
	ans += b / (c* d / __gcd(c, d));
	cout << ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[100009];
void END(){
  cout<<-1<<endl;
  exit(0);
}
main(){

  cin>>n;

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

  if(a[0]!=2)
  {
    cout<<-1<<endl;
    exit(0);
  }

  int l=2,r=3;


  for(int i=1;i<n;i++)
  {
    int p = a[i];

    //cout<<l<<r<<endl;

    if(!(p<=r)||(l/p==r/p&&(l%p!=0)&&(r%p!=0)))
    {
      cout<<-1<<endl;
      return 0;
    }


    else if(l>=p&&(l%p==0))l=((l-1)/p+1)*p;
    else l=(l/p+1)*p;


    r=(r/p)*p+(p-1);
  }
  cout<<l<<' '<<r<<endl;
}


Measured memory_bytes: 1024
#include"bits/stdc++.h"
using namespace std;
int main(){
	int a,b;
	cin>>a>>b;
	vector<string> x;
	x.push_back(string(b+2,'#'));
	char temp;
	for(int i=0;i!=a;++i){
		string str("#");
		for(int j=0;j!=b;++j){
			cin>>temp;
			str+=temp;
		}
		str+='#';
		x.push_back(str);
	}
	x.push_back(string(b+2,'#'));
	for(auto i:x){
		for(auto j:i)
			cout<<j;
		cout<<endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define ll long long
#define ull unsigned long long
#define dd double
#define oo 1001007000
#define ff float
#define ooo 4223352036854775007
#define iii pair<ll,ll>
#define vii vector<ll>
#define viii vector<iii>
#define sss pair<str,str>
#define str string
#define sii set<ll>
#define siii set<iii>
#define r0 return 0
#define pb push_back
#define sz size
using namespace std;

const char E='\n';
const int N=100005;
const int NN=3005;
const ll md=998244353;


ll dp[NN][NN];
ll a, b, c, d;

ll calc(ll x, ll y){
	if (dp[x][y] != -1) return dp[x][y];
	if ((x > c) || (y > d)) return dp[x][y] = 0;
	if ((x == c) && (y == d)) return dp[x][y] = 1;
	dp[x][y] = ((calc(x + 1, y) * y) + (calc(x, y + 1) * x) - calc(x + 1, y + 1) * x * y);
	dp[x][y] %= md;
	dp[x][y] += md;
	if (dp[x][y] > md)
        dp[x][y] -= md;

	return dp[x][y];
}

int main(){
    cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
	for (ll i = 0; i < NN; i++)
        for (ll j = 0; j < NN; j++)
        dp[i][j] = -1;
	cin >> a >> b >> c >> d;
	cout << calc(a, b) << E;
	r0;
}


/*







*/


Measured memory_bytes: 74356
#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define _ ios::sync_with_stdio(0);cin.tie(0);

using namespace std;

typedef long long ll;

const int MAX = 1e5+5;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int main(){_
	int n;
	cin >> n;
	string s;
	cin >> s;
	char b = '1';
	int ans = 0;
	for(int i = 0; i < n; i++){
		if(s[i] != b){
			ans++;
			b = s[i];
		}
	}
	cout << ans << endl;
}


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

signed main(void)
{
	int n;
	double ans;

	cin >> n;
	ans = 0;
	rep(i, n)
	{
		double x;
		string u;
		cin >> x >> u;
		if (u == "JPY")
			ans += x;
		else if (u == "BTC")
			ans += x * 380000.0;
	}
	cout << fixed << setprecision(4) << ans << endl;
	return 0;
}


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


int main() {
    string S;
    cin >> S;
    int countC = 0;
    int count = 0;
    if (S[0] == 'A' && (S[1] <= 'z' && S[1] >= 'a') && 
    (S[S.size() - 1] <= 'z' && S[S.size() - 1] >= 'a')) {
        for (int i = 2; i < S.size() - 1; i++) {
            if (S[i] == 'C') {
                countC++;
            }
            if (S[i] >= 'a' && S[i] <= 'z') {
                count++;
            }
        }
        if (countC == 1 && count == S.size() - 4) {
            cout << "AC" << endl;
        }
        else {
            cout << "WA" << endl;
        }
    }
    else {
        cout << "WA" << endl;
    }
}



Measured memory_bytes: 3600
function Main(s) {
  var s = s.split("\n")[0].split(" ").map(e => Number(e));
  var x = new Set(), y = new Set();
  for(var i = 0; i <= s[5]; i++) {
    for(var j = 0; j <= s[5]; j++) {
      if ((100 * s[0] * i) + (100 * s[1] * j) <= s[5]) {
        x.add((100 * s[0] * i) + (100 * s[1] * j));
      }
      if ((s[2] * i) + (s[3] * j) <= s[5]) {
        y.add((s[2] * i) + (s[3] * j));
      }
    }
  }
  var s_water = s[0] * 100;
  var sugar = 0;
  var max = 0;
  var flag = false;
  for(var i of x.values()) {
    for(var j of y.values()) {
      if ((100 * j) / (i + j) > max && s[4] * (i / 100) >= j && i + j <= s[5]) {
        max = (100 * j) / (i + j);
        s_water = i + j, sugar = j;
        if (s[4] * (i / 100) === j) {
          flag = true;
          break;
        }
      }
    }
    if (flag) break;
  }
  console.log(s_water, sugar)
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 24468
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define fastcin ios_base::sync_with_stdio(false)

typedef long long ll;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);

int main (void) {
  	fastcin;
  	string n;
  	cin >> n;
  	int cnt = 0;
  	for(int i=0;i<n.size();i++)
  		if(n[i] == '1')
  			cnt++;

  	cout << cnt << endl;

  
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> b;
long long ans;
int main (){
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int t;
		cin>>t;
		b.push_back(t-i);
	}
	sort(b.begin(),b.end());
	for(int i=0;i<n;i++)
		ans+=abs(b[i]-b[(n-1)/2]);
	cout<<ans;
	return 0;
}

Measured memory_bytes: 1400
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define _GLIBCXX_DEBUG
#define INF 100000010
using namespace std;
const int mod = 1000000007;


int main() {
 
  int64_t N,M,ans=0;
  cin>>N>>M;
  vector<int> A(N+1);

  for(int i=1; i<=N; i++){
    cin>>A[i];
    }
  vector<vector<int> > B(N+1,vector<int>(0));
  for(int i=0; i<M; i++){
      int a,b;
      cin>>a>>b;
      B[a].push_back(b);
      B[b].push_back(a);
  }
  for(int i=1; i<=N; i++){
    if(B[i].size()==0){ans++;continue;}
    for(int j=0; j<B[i].size(); j++){
      if(A[i]<=A[B[i][j]]){break;}
      if(j==B[i].size()-1)ans++;
    }
  }

  //sort(A.begin(),A.end());
  //for (int i = 0; i < N; i++) { maximum = max(maximum , A[i]);}
  //for (int i = 0; i < N; i++) { minimum = min(minimum , A[i]);}
  cout <<ans<< endl;
}

Measured memory_bytes: 8716
using System;

public class hello
{
    public static void Main()
    {
        while (true)
        {
            var n = int.Parse(Console.ReadLine().Trim());
            if (n == 0) break;
            var dp = new int[n + 1, 4];
            for (int i = 0; i < n + 1; i++)
                for (int j = 0; j < 4; j++) dp[i, j] = int.MaxValue;
            dp[0, 0] = 0;
            var p = new int[n]; var t = new int[n];
            for (int i = 0; i < n; i++)
            {
                string[] line = Console.ReadLine().Trim().Split(' ');
                p[i] = int.Parse(line[0]);
                t[i] = int.Parse(line[1]);
            }
            getAns(dp, p, t);
        }
    }
    public static void getAns(int[,] dp, int[] p, int[] t)
    {
        var n = p.Length;
        if (p[0] > t[0]) { Console.WriteLine("NG 1"); goto end; }
        else dp[1, 1] = p[0];
        var ngi = int.MaxValue;
        for (int i = 1; i < n; i++)
        {
            var ok = false;

            for (int j = 1; j <= 3; j++)
            {

                if (dp[i, j] != int.MaxValue)
                {
                    if (j <= 2 && checkGet(p, t, i - 1, j))
                    {
                        dp[i + 1, j + 1] = Math.Min(dp[i + 1, j + 1], dp[i, j] + Math.Abs(p[i] - p[i - 1]));
                        ok = true;
                    }
                    if (checkGoHome(p, t, i - 1, j))
                    {
                        dp[i + 1, 1] = Math.Min(dp[i + 1, 1], dp[i, j] + p[i] + p[i - 1]);
                        ok = true;
                    }
                }
            }
            if (!ok) ngi = Math.Min(ngi, i);
        }
        getAns2(dp, p, ngi);
        end:;
    }
    public static void getAns2(int[,] dp, int[] p, int ngi)
    {
        var n = dp.GetLength(0);
        var ok = false;
        var ans = int.MaxValue;
        for (int i = 0; i < 4; i++)
            if (dp[n - 1, i] != int.MaxValue)
            {
                ans = Math.Min(ans, dp[n - 1, i]);
                ok = true;
            }
        if (ok) { Console.WriteLine("OK {0}", p[n - 2] + ans); return; }
        else { Console.WriteLine("NG {0}", ngi + 1); return; }
    }
    public static bool checkGoHome(int[] p, int[] t, int i, int b)
    {
        var nt = p[i] * (b + 1) + p[i + 1];
        return nt <= t[i + 1] - t[i];
    }
    public static bool checkGet(int[] p, int[] t, int i, int b)
    {
        var L = Math.Abs(p[i + 1] - p[i]);
        var nt = L * (b + 1);
        return nt <= t[i + 1] - t[i];
    }
}


Measured memory_bytes: 8048
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

var (
	n int
	M [MAX][MAX]int
)

const MAX = 100
const WHITE = 0
const GRAY = 1
const BLACK = 2

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Scan()
	n, _ = strconv.Atoi(sc.Text())

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			sc.Scan()
			c, _ := strconv.Atoi(sc.Text())
			if c != -1 {
				M[i][j] = c
			} else {
				M[i][j] = math.MaxInt64
			}

		}
	}
	prim()
}

func prim() {
	var u int
	var minv int
	var d [MAX]int
	var p [MAX]int
	var color [MAX]int

	for i := 0; i < n; i++ {
		d[i] = math.MaxInt64
		p[i] = -1
		color[i] = WHITE
	}

	d[0] = 0

	for {
		minv = math.MaxInt64
		u = -1
		for i := 0; i < n; i++ {
			if minv > d[i] && color[i] != BLACK {
				u = i
				minv = d[i]
			}
		}

		if u == -1 {
			break
		}

		color[u] = BLACK

		for v := 0; v < n; v++ {
			if color[v] != BLACK && M[u][v] != math.MaxInt64 {
				if d[v] > M[u][v] {
					d[v] = M[u][v]
					p[v] = u
					color[v] = GRAY
				}
			}
		}
	}
	sum := 0
	for i := 0; i < n; i++ {
		if p[i] != -1 {
			sum += M[i][p[i]]
		}
	}
	fmt.Println(sum)

}



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

#define ll long long int
#define rep(i, a, n) for (ll i = a; i < n; i++)
#define repm(i, a, n) for (ll i = a; i >= n; i--)
#define INF 1e9
#define LINF 1e17
#define MOD (int)(1e9 + 7)
#define mod (int)(1e9 + 7)
#define pi 3.141592653589
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vd vector<double>
#define vb vector<bool>
#define vs vector<string>
#define vii vector<vector<int>>
#define vllll vector<vector<ll>>
#define ALL(a) (a).begin(), (a).end()

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

void print(bool f)
{
    cout << (f ? "Yes" : "No") << endl;
}

void Print(bool f)
{
    cout << (f ? "YES" : "NO") << endl;
}

int main(void)
{
    ll n;
    cin >> n;

    ll sum = 0;
    rep(i, 1, sqrt(n) + 1)
    {
        if (n % i != 0)
            continue;
        ll d[2] = {i, n / i};
        rep(i, 0, 2) if (d[i] != 1 && n / (d[i] - 1) == n % (d[i] - 1)) sum += d[i] - 1;
    }
    cout << sum << endl;
}

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

ll dp[101010][4];
char c[4]={'A','B','C','?'};

int main(){
  string S; cin>>S;
  dp[0][0]=1;
  int n=S.length();
  rep(i,n) rep(j,4){
    if(S[i]==c[j]){
      if(j!=3){
        (dp[i+1][j+1]+=dp[i][j])%=MOD;
        rep(k,4) (dp[i+1][k]+=dp[i][k])%=MOD;
      }else{
        rep(k,3) (dp[i+1][k+1]+=dp[i][k])%=MOD;
        rep(k,4) (dp[i+1][k]+=dp[i][k]*3)%=MOD;
      }
    }
  }
  cout<<dp[n][3]<<endl;
  return 0;
}


Measured memory_bytes: 3584
#include <iostream>
using namespace std;
#define MOD 1000000007

long long dp[1<<21];

int main(){
    int N;
    cin >> N;
    int a[21][21];
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            cin >> a[i][j];

    for(int i=0; i<N; i++)
        if(a[0][i])
            dp[1<<i] = 1;

    for(int j=0; j<(1<<N); j++){
        int i = __builtin_popcount(j);
        for(int k=0; k<N; k++){
            if(j&(1<<k)) continue;
            if(!a[i][k]) continue;
            dp[j|(1<<k)] = (dp[j|(1<<k)] + dp[j]) % MOD;
        }
    }
    
    cout << dp[(1<<N)-1] << endl;
    return 0;
}

Measured memory_bytes: 16640
import sys
sys.setrecursionlimit(10**7)

def modinv(a,m=10**9+7):
    if a==0: return 1
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

def cur(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        else:
            par[x]=p
            descend[p]+=cur(x)
    neighbor[p].remove(par[p])
    return descend[p]

def cur2(p):
    for x in neighbor[p]:
        ans[x]=ans[p]*descend[x]*modinv(n-descend[x])%mod
        cur2(x)

mod=10**9+7
n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[0]*(n+1)

for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].append(b)
    neighbor[b].append(a)
neighbor[1].append(0)
cur(1)

ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i*modinv(descend[i])%mod
ans[1]=ans1
cur2(1)
for i in range(1,n+1):
    print(ans[i])


Measured memory_bytes: 141652
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        try {
            // 標準入力
            InputStreamReader isr = new InputStreamReader(System.in);
            BufferedReader br = new BufferedReader(isr);
            String str = br.readLine();
            for (int i = 1; i < str.length(); i++) {
                String tmpStr = str.substring(0, str.length() - i);
                int tmpLen = tmpStr.length();
                if (tmpLen % 2 != 0) {
                    continue;
                }
                String tmp1 = tmpStr.substring(0, tmpLen / 2);
                String tmp2 = tmpStr.substring(tmpLen / 2, tmpLen);
                if (tmp1.equals(tmp2)) {
                    System.out.println(tmpLen);
                    break;
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
           }
    }
}

Measured memory_bytes: 21332
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <random>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int) n; i++)

int main() {
    int x; cin >> x;
    int ans = 1;
    for (int b = 2; b <= sqrt(x); b++) {
        int pm = b;
        for (int p = 2; ; p++)
        {
            if (pow(b,p) <= x) {
                pm = pow(b,p);
            } else {
                break;
            }
        }
        ans = max(ans, pm);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<iomanip>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;
using namespace std;

int main(){
	string s;
	cin>>s;
	int ans=0;
	lol(i,s.size())ans+=(s[i]=='1');
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256