akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9 + 7;

int r (int a, int b) {
	return (a + b - 1) / b;
}

signed main () {
	int n, d, a;
	cin >> n >> d >> a;
	vector < pair < int, int > > gays(n);
	for (pair < int, int > &p: gays) 
		cin >> p.first >> p.second;
	sort(gays.begin(), gays.end());
	long long ans = 0;
	queue < pair < int, int > > pipes;
	long long dmg = 0;
	for (int i = 0; i < n; ++i) {
		int x = gays[i].first, h = gays[i].second;
		if (dmg) {
			h -= dmg;
			while (!pipes.empty() && pipes.front().first == i) {
				dmg -= pipes.front().second;
				pipes.pop();
			}
			if (h > 0) {
				int j = prev(lower_bound(gays.begin(), gays.end(), make_pair(x + 2 * d, inf))) - gays.begin();
				if (i == j)
					ans += r(h, a);
				else {
					ans += r(h, a);
					dmg += a * r(h, a);
					pipes.push(make_pair(j, a * r(h, a)));
				}
			}
		}
		else {
			int j = prev(lower_bound(gays.begin(), gays.end(), make_pair(x + 2 * d, inf))) - gays.begin();
			if (i == j)
				ans += r(h, a);
			else {
				ans += r(h, a);
				dmg += a * r(h, a);
				pipes.push(make_pair(j, a * r(h, a)));
			}
		}
	}
	cout << ans << '\n';
}


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

long long check_divide(long long N) {
    long long res = 1;
    long long div = pow(N, 0.5);
    while (div > 1) {
        if (N % div == 0) {
            return div;
        }
        div--;
    }
    return 1;
}

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

    long long div = check_divide(n);
    
    cout << div + n / div - 2 << endl;

    return 0;
}

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

string make_ans(string s, string t, int cur){
    string ans = "";
    for(int i=0; i<s.size(); i++){
        if(s[i] == '?') ans += 'a';
        else ans += s[i];
    }
    for(int i=0; i<t.size(); i++){
        ans[cur + i] = t[i];
    }
    return ans;
}

int main() {
    string s,t; cin >> s >> t;
    int cur = -1;
    for(int i=0; i<s.size()-t.size()+1; i++){
        string sub = s.substr(i,t.size());
        //cout << sub << endl;
        for(int j=0; j<t.size(); j++){
            if(sub[j] != t[j] && sub[j] != '?') break;
            if(j == t.size() -1) cur = i;
        }
    }
    if(cur < 0) cout << "UNRESTORABLE" << endl;
    else cout << make_ans(s,t,cur) << endl;
}

Measured memory_bytes: 3624
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <queue>
#include <set>
#include <map>
#include <stack>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

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


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

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

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

int N[4];

int main()
{
    REP(i, 3)
    {
        int a, b;
        cin >> a >> b;
        N[--a]++;
        N[--b]++;
    }

    REP(i, 4)
    {
        if (N[i] > 2)
        {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

Measured memory_bytes: 256
//People only find me interesting because they can't tell whether I'm serious or not

#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
typedef long long int ll;
typedef double db;
//typedef __int128 s128;
//typedef __uint128_t u128;
//typedef unsigned long long u64;
#define int long long int
#define P 998244353
#define Q 1000000006
#define sz(a) (ll)a.size()
#define lt(a) (ll)a.length()
#define pll pair<ll,ll>
#define f(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define bac(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define mll map<ll,ll>
#define umll unordered_map<ll,ll>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define teevra_gati ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define N 100005
#define PI 3.14159265359
#define inf LLONG_MAX
using namespace __gnu_pbds;
using namespace std;

void solve(){
    ll n,m;
    cin>>n>>m;
    cout<<n*m<<endl;

}
signed main() {
    teevra_gati
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    
    solve();

    return 0;
}

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

#define int long long
#define double long double

#define REP(i, b) for(int i = 0; i < (b); i++)
#define REPS(i, b) for(int i = 1; i <= (b); i++)
#define ALL(v) (v).begin(), (v).end()

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

using namespace std;

using pi = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vb = vector<bool>;
using vpi = vector<pi>;
using vvi = vector<vi>;
using vvb = vector<vb>;

const int INF = 1e16;
const int MOD = 1e9+7;

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

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

signed main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    int N; cin >> N;
    vi p(N+1);
    vvi m(N+1, vi(N+1));
    REP(i, N) cin >> p[i] >> p[i+1];

    REPS(i, N) m[i][i] = 0;
    for(int l = 2; l <= N; l++)
    {
        for(int i = 1; i <= N-l+1; i++)
        {
            int j = i+l-1;
            m[i][j] = INF;
            for(int k = i; k <= j-1; k++)
            {
                chmin(m[i][j], m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]);
            }
        }
    }
    cout << m[1][N] << endl;
}


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

#define rep(i, cc, n) for (int i = cc; i < n; ++i)

using namespace std;

const int nmax = 8;
bool graph[nmax][nmax];

int dfs(int v, int N, bool visited[nmax])
{
    bool all_visited = true;

    rep(i, 0, N)
    {
        if (visited[i] == false)
            all_visited = false;
    }

    if (all_visited)
    {
        return 1;
    }
    int ret = 0;
    rep(i, 0, N)
    {
        if (graph[v][i] == false)
        {
            continue;
        }
        if (visited[i])
        {
            continue;
        }

        visited[i] = true;
        ret += dfs(i, N, visited);
        visited[i] = false;
    }

    return ret;
}
int main()
{
    int N, M;
    cin >> N >> M;
    rep(i, 0, M)
    {
        int A, B;
        cin >> A >> B;
        A--;
        B--;
        graph[A][B] = graph[B][A] = true;
    }

    bool visited[nmax];
    rep(i, 0, N)
    {
        visited[i] = false;
    }

    visited[0] = true;
    cout << dfs(0, N, visited) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if (a + b == c + d)
    cout << "Balanced" << endl;
  else if (a + b < c + d)
    cout << "Right" << endl;
  else
    cout << "Left" << endl;

  
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
  int k, s;
  int i;
  int j;
  int count=0;

  scanf("%d %d", &k, &s);

  for(i=0; i<=s && i<=k; i++){
    for(j=0; j<=k && j<=s-i; j++){
      if(s-(i+j)<=k){
        count++;
      }
    }
  }

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

  return 0;
}


Measured memory_bytes: 128
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long x = sc.nextLong();
    long y = sc.nextLong();
    long ans1 = 0;
    long ans2 = 0;
    long ans3 = 0;
    long ans4 = 0;
    long x1 = x;
    long x2 = -1 * x;
    long y1 = y;
    long y2 = -1 * y;
    if (x1 <= y1) {
      ans1 = Math.abs(y1 - x1);
    } else {
      ans1 = Long.MAX_VALUE;
    }
    if (x2 <= y1) {
      ans2 = Math.abs(y1 - x2) + 1;
    } else {
      ans2 = Long.MAX_VALUE;
    }
    if (x1 <= y2) {
      ans3 = Math.abs(y2 - x1) + 1;
    } else {
      ans3 = Long.MAX_VALUE;
    }
    if (x2 <= y2) {
      ans4 = Math.abs(y2 - x2) + 2;
    } else {
      ans4 = Long.MAX_VALUE;
    }
    long ans = Math.min(Math.min(ans1, ans2), Math.min(ans3, ans4));
    System.out.println(ans);
  }
}


Measured memory_bytes: 22996
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys  # {{{
import os
import time
import re
from pydoc import help
import string
import math
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools
# }}}

# pre-defined{{{
sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
ALPHABETS = [chr(i) for i in range(ord('a'), ord('z')+1)]  # can also use string module
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]
from inspect import currentframe
# }}}

def solve():
    s = input()
    if s == "ABC":
        print("ARC")
    else:
        print("ABC")

    return 0

if __name__ == "__main__":# {{{
    solve()

# vim: set foldmethod=marker: }}}


Measured memory_bytes: 75428
#include <iostream>
#include <fstream>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <iterator>
#include <ext/pb_ds/assoc_container.hpp>

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

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

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

map<ll,int>w;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    ll s=0,x,ans=0;
    w[0]=1;
    for(int i=1;i<=n;i++){
        cin>>x;
        s+=x;
        s%=m;
        ans+=w[s];
        w[s]++;
    }
    cout<<ans;
    return 0;
}


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

const int MAX_N = (int)55555 + 5;

int n;

bool arr[MAX_N];
vector<int> ans;

void eratosthenes() {
  for (int i = 0; i < MAX_N; i++) arr[i] = true;
  for (int i = 2; i < sqrt(MAX_N); ++i) {
    if (arr[i]) {
      for (int j = 0; i * (j + 2) < MAX_N; j++){
        arr[i *(j + 2)] = false;
      }
    }
  }
}

int main(void) {
  // Here your code !
  scanf("%d", &n);
  eratosthenes();

  for (int i = 2; i < MAX_N; ++i) {
    if (arr[i] && (i % 5) == 1) ans.push_back(i);
    if (ans.size() >= n) break;
  }

  for (auto e: ans) printf("%d ", e);
  printf("\n");

	return 0;
}

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

int main(){
  int N;
  string S;
  cin>>N>>S;
  bool ans=true;
  if(N==1){
    cout<<"No"<<endl;
    ans=false;
  }
  for(int i=0;i<N/2;i++){
    if(N%2!=0){
      cout<<"No"<<endl;
      ans =false;
      break;
    }else if(S.at(i)!=S.at(N/2+i)){
      cout<<"No"<<endl;
      ans =false;
      break;
    }
  }
  if(ans){
    cout<<"Yes"<<endl;
  }
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
#define rep(i,n) for(lint (i)=0;(i)<(n);(i)++)
#define repp(i,m,n) for(lint (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(lint (i)=(n-1);(i)>=0;(i)--)
#define INF (1ll<<60)
#define all(x) (x).begin(),(x).end()
const lint MOD =1000000007;
const lint MAX = 1000000;
using Graph =vector<vector<lint>>;
typedef pair<lint,lint> P;
typedef map<lint,lint> M;
 
lint fac[MAX], finv[MAX], inv[MAX];
 
void COMinit() 
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (lint i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
long long COM(lint n, lint k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 
lint primary(lint num)
{
    if (num < 2) return 0;
    else if (num == 2) return 1;
    else if (num % 2 == 0) return 0;
 
    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return 0;
        }
    }
 
    return 1;
}
   long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
    lint lcm(lint a,lint b){
        return a/__gcd(a,b)*b;
    }
     lint gcd(lint a,lint b){
        return __gcd(a,b);
    } 

  int main(){      
    lint a,b,c,k;
    cin>>a>>b>>c>>k;
    if(k<=a){
        cout<<k<<endl;
        return 0;
    }
    k-=a;
    if(k<=b){
        cout<<a<<endl;
        return 0;
    }
    k-=b;
    if(k<=c){
        cout<<a-k<<endl;
        return 0;
    }
    cout<<a-c<<endl;
      }
      
    

  
          
  

Measured memory_bytes: 3680
#include<stdio.h>
#include<string.h>
#define M 1046537
#define NIL (-1)
#define L 14


 char H[M][L];

 int getChar(char ch){
     if (ch=='A')return 1;
     else if (ch=='C')return 2;
     else if (ch=='G')return 3;
     else if (ch=='T')return 4;
     else return 0;
     }

 long long getKey(char str[]){
     long long sum=0,p=1,i;
     for(int i=0;i<strlen(str);i++){
           sum+=p*(getChar(str[i]));
           p*=5;
           }
     return sum;
     }

 int h1(int x){
     return x%M;
     }

 int h2(int x){
     return 1+(x%(M-1));
     }

 int find(char str[]){
     long long x,i,h;
     x=getKey(str);
     for(i=0;;i++){
         h=(h1(x)+i*h2(x))%M;
         if(strcmp(H[h],str)==0)return 1;
         else if(strlen(H[h])==0)return 0;
         }
     return 0;
     }

 int insert(char str[]){
     long long x,i,h;
     x=getKey(str);
     for(i=0;;i++){
         h=(h1(x)+i*h2(x))%M;
         if(strcmp(H[h],str)==0)return 1;
         else if(strlen(H[h])==0){
             strcpy(H[h],str);
             return 0;
             }
         }
     return 0;
     }

 int main(){
     int i,n,h;
     char str[L],com[9];
     scanf("%d",&n);
     for(i=0;i<n;i++){
         scanf("%s%s",com,str);
         if(com[0]=='i'){
            insert(str);
            }
         else{
              if(find(str))printf("yes\n");
              else printf("no\n");
              }
         }
     return 0;
     }




Measured memory_bytes: 15960
#include <stdio.h>

int max(int a,int b){
  if(a > b){
    return a;
  }
  return b;
}

int main(void){
  int n;
  scanf("%d", &n);

  int a[n][3], dp[n][3];
  for (int i = 0; i < n; i++) {
    scanf("%d%d%d", &a[i][0], &a[i][1], &a[i][2]);
    dp[i][0] = a[i][0];
    dp[i][1] = a[i][1];
    dp[i][2] = a[i][2];
  }

  for (int i = 1; i < n; i++) {
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 3; k++) {
        if(j == k) continue;
        dp[i][j] = max(dp[i-1][k]+a[i][j], dp[i][j]);
      }
    }
  }

  printf("%d\n", max(max(dp[n-1][0], dp[n-1][1]), dp[n-1][2]));

  return 0;
}

Measured memory_bytes: 2560
# coding=utf-8

n = int(input())
number_list = list(map(int, input().split()))

max_value = max(number_list)
middle = max_value/2
number_list.remove(max_value)

diff_list = [abs(element-middle) for element in number_list]
nearest = number_list[diff_list.index(min(diff_list))]
print("{0} {1}".format(max_value, nearest))


Measured memory_bytes: 14060
use v5.18; # strict say state
use warnings;
use List::Util qw(reduce first max min sum0);

chomp (my ($n, $m) = split / /, <STDIN>);
my $ans = 0;
if ($n * 2 >= $m) {
  $ans = int($m / 2);
} else {
  $ans = $n;
  $m -= $n * 2;
  $ans += int($m / 4);
}
say $ans;

Measured memory_bytes: 768
import collections
n = int(input())
v = list(map(int, input().split()))

l_odd = []
l_even = []
for i, value in enumerate(v, 1):
  # 偶数番目と奇数番目の要素のリストをそれぞれつくる
  if i % 2 == 1:
    l_odd.append(value)
  else:
    l_even.append(value)

# それぞれのリストで一番たくさん出てくる要素の数を数える
co = collections.Counter(l_odd).most_common(2)
ce = collections.Counter(l_even).most_common(2)

if co[0][0] == ce[0][0]:
  if len(co) == 1:
    print(int(n/2))
  else:
    print(n - co[0][1] - max(co[1][1], ce[1][1]))
else:
  print(n - co[0][1] - ce[0][1])


Measured memory_bytes: 15972
n = int(input())
al = list(map(int, input().split()))

a_s = sorted(al, reverse=True)

ali = 0
bob = 0
count = 0

for a in a_s:
    count += 1
    if count %2 != 0:
        ali += a
    else:
        bob += a

print(ali-bob)

Measured memory_bytes: 3060
/*
  三角形(三角形の２辺a,bとその間の角Cから、その三角形の面積S、周の長さL,
  aを底辺としたときの高さhを求めるプログラム)
  2018/03/09
*/

#include<stdio.h>
#include<math.h>

int main(void)
{
  int a,b,C;/*c:辺の長さ、C:角の大きさ*/
  double c,rad;
  double s,l,h;

  scanf("%d %d %d",&a,&b,&C);
  rad = ((double)C*M_PI)/180.0;
  s = (a * b * sin(rad))/2.0;
  c = sqrt(pow((double)a,2) + pow((double)b,2)-(double)(2*a*b)*cos(rad));
  l = a+b+c;
  h = (2*s)/(double)a;
  printf("%f\n%f\n%f\n",s,l,h);
  return 0;
}


Measured memory_bytes: 2108
#include<stdio.h>
#include<stdlib.h>
int main(){
  int i,count[26]={0};
  char now;

//  printf("%c\n",now);

  while( scanf("%c",&now)!=EOF){
//    printf("flag %c\n",now);
    for(i=0;i<26;i++){
      if(now=='a'+i || now=='A'+i )count[i]++;
    //    printf("flag2 %c\n",now);
    //    printf("flag3 %c\n",now);
    }
  }

  for(i=0;i<26;i++){
    printf("%c : %d\n",'a'+i,count[i]);
  }
  return 0;
}

Measured memory_bytes: 1752
package main

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

func main() {
	sc := bufio.NewScanner(os.Stdin)
	n := stdin(sc)
	R := make([]int, n)
	for i := 0; i < n; i++ {
		R[i] = stdin(sc)
	}

	min_v := R[0]
	max_v := math.MinInt32
	for i := 1; i < n; i++ {
		diff := R[i] - min_v
		if diff > max_v {
			max_v = diff
		}
		if R[i] < min_v {
			min_v = R[i]
		}
	}
	fmt.Println(max_v)
}

func stdin(sc *bufio.Scanner) int {
	sc.Scan()
	num, _ := strconv.Atoi(sc.Text())
	return num
}



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

#define int long long

using namespace std;
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
static const ll maxLL = (ll)1 << 62;
const ll MOD=1000000007,INF=1e18;
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};

int n,a[300030];

signed main(){
    cin>>n;
    rep(i,0,n*3){
        cin>>a[i];
    }
    sort(a,a+n*3,greater<int>());
    int ans=0;
    rep(i,1,n+1){
        ans+=a[i*2-1];
    }
    cout<<ans<<endl;
    
    
    
    
    
    
    
    
    
    
    
    
    return 0;
}

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

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))

#define INF 2e9
#define INF_LL 1LL<<60
#define ll long long
#define MOD 1e9+7
#define MAX_V
const double PI=3.14159265358979323846;

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain; 

//Combination Table
ll C[51][51]; /* C[n][k] -> nCk */

void comb_table(int N) {
    REP(i, N+1) REP(j, i+1) {
        if(j == 0 || j == i) {
            C[i][j] = 1LL;
        } else {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]);
        }
    }
}

int main(){
    int n, a, b;
    cin >> n >> a >> b;
    vector<ll> v(n);
    REP(i, n) cin >> v[i];

    comb_table(n);

    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());

    double ans1 = 0;
    ll ans2 = 0;

    REP(i, a) {
        ans1 += v[i];
    }
    ans1 /= a;

    int n_num = 0, a_num = 0; 

    /* n個のなかからv[a-1]となるものの個数を調べる */
    REP(i, n) {
        if(v[i] == v[a-1]) n_num++;
    }

    /* a個のなかからv[a-1]となるものの個数を調べる */
    REP(i, a) {
        if(v[i] == v[a-1]) a_num++;
    }

    //cout << a_num << " " << n_num << endl;

    if(v[0] != v[a-1]) {
        cout << ans1 << endl << C[n_num][a_num] << endl;
    } else {
        ll ans_2 = 0;
        REPN(i, a_num, min(b, n_num)+1) {
            ans_2 += C[n_num][i];
        }
        cout << ans1 << endl << ans_2 << endl;
    }

    
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
/**
 * @author saiyo
 *
 */
public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scan = new Scanner(System.in);
		//int x = scan.nextInt();
		//int y = scan.nextInt();
		
		//Seisu s = new Seisu(x, y);
		//s.kouyaku();

		int con = scan.nextInt();
		
		int[] num = new int[con];
		for(int i = 0; i < con; i++){
			num[i] = scan.nextInt();
		}
		//Seisu s = new Seisu(num);
		//System.out.println(s.getProfit());
		
		//s.countSosu();
		///*
		Sort s = new Sort(num);
		int cnt = s.babbleSort();
		s.printSort();
		System.out.println(cnt);
		//*/
	}

}

class Seisu{
	private int x, y;
	private int snum[];
	
	Seisu(int x, int y){
		if(x >= y){
			this.x = x;
			this.y = y;
		}else{
			this.x = y;
			this.y = x;
		}
		
	}
	
	Seisu(int snum[]){
		this.snum = new int[snum.length];
		for(int i = 0; i < snum.length; i++){
			this.snum[i] = snum[i];
		}
	}
	
	public int getProfit(){
		int fstM = this.snum[0], sa, maxProfit = this.snum[1] - this.snum[0];
		for(int i = 1; i < this.snum.length; i++){
			sa = this.snum[i] - fstM;
			if(fstM > this.snum[i]){
				fstM = this.snum[i];
			}
			if(sa > maxProfit){
				maxProfit = sa;
			}
			
		}
		return maxProfit;
	}
	
	public void countSosu(){
		int con = 0;
		for(int nu: this.snum){
			con += isSosu(nu);
		}
		System.out.println(con);
	}
	
	public int isSosu(int num){
		for(int i = 2; i < Math.sqrt(num) + 1; i++){

			if(num % i == 0 && num != 2){
				return 0;
			}
			
		}
		return 1;
	}
	
	public void kouyaku(){
		System.out.println(modSeisu(this.x, this.y));
	}
	
	
	public int modSeisu(int x, int y){
		if(x % y == 0){
			return y;
		}else{
			return modSeisu(y , x % y);
		}
	}
}

class Sort{
	private int[] sorted;
	
	Sort(int[] sorted){
		this.sorted = new int[sorted.length];
		for(int i = 0; i < sorted.length; i++){
			this.sorted[i] = sorted[i];
		}
	}
	
	public int babbleSort(){
		boolean flag = true;
		int nullBox, cnt = 0;
		while (flag){
			flag = false;
			for(int i = this.sorted.length -1; i >= 1; i--){
				if(this.sorted[i] < this.sorted[i - 1]){
					nullBox = this.sorted[i];
					this.sorted[i] = this.sorted[i - 1];
					this.sorted[i - 1] = nullBox;
					flag = true;
					cnt++;
				}
			}
		}
		return cnt;
	}
	
	public void insertionSort(){
		int v, j;
		for(int i = 1; i < this.sorted.length; i++){
			v = this.sorted[i];
			j = i - 1;
			while(j >= 0 && this.sorted[j] > v){
				this.sorted[j + 1] = this.sorted[j];
				j--;
			}
			this.sorted[j + 1] = v;
			printSort();
		}
	}
	
	public void printSort(){
		for(int i  = 0; i < this.sorted.length - 1; i++){
			System.out.print(this.sorted[i] + " ");
		}
		System.out.println(this.sorted[this.sorted.length - 1]);
	}
}



Measured memory_bytes: 26376
#include<bits/stdc++.h>
using namespace std;
int main() {
	int N, M; cin >> N >> M;
	int X[M];
	for (int i = 0; i < M; i++) {
		cin >> X[i];
	}
	sort(X, X + M);
	int def[M - 1];
	for (int i = 1; i < M; i++) {
		def[i-1] = X[i] - X[i - 1];
	}
	sort(def, def + M - 1);
	long long ans = 0;
	for (int i = 0; i < M - N; i++) {
		ans += def[i];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <algorithm>     //sort,二分探索,など
#include <bitset>        //固定長bit集合
#include <cmath>         //pow,logなど
#include <complex>       //複素数
#include <deque>         //両端アクセスのキュー
#include <functional>    //sortのgreater
#include <iomanip>       //setprecision(浮動小数点の出力の誤差)
#include <iostream>      //入出力
#include <iterator>      //集合演算(積集合,和集合,差集合など)
#include <map>           //map(辞書)
#include <numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include <queue>         //キュー
#include <set>           //集合
#include <stack>         //スタック
#include <string>        //文字列
#include <unordered_map> //イテレータあるけど順序保持しないmap
#include <unordered_set> //イテレータあるけど順序保持しないset
#include <utility>       //pair
#include <vector>        //可変長配列

using namespace std;
typedef long long ll;

//マクロ
#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPD(i, n) for (ll i = (ll)(n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define FORD(i, a, b) for (ll i = (a); i >= (b); i--)
#define ALL(x) (x).begin(), (x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size())      //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 1000000007    //10^9+7
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define MAXR 100000 //10^5:最大のrange(素数列挙などで使用)

// debug
#define DEBUG(x) cout << #x << ": " << x << endl
#define DEBUG2(x, y) cout << #x << ": " << x << " " << #y << ": " << y << endl
#define DEBUG_VEC(v)   \
  cout << #v << ":";   \
  REP(i, v.size())     \
  cout << " " << v[i]; \
  cout << endl
#define DEBUG_ARR(v, n) \
  cout << #v << ":";    \
  REP(i, n)             \
  cout << " " << v[i];  \
  cout << endl

signed main()
{
  ll N;
  cin >> N;

  ll ans = 0;
  ll min_val = INF;
  REP(i, N)
  {
    ll pi;
    cin >> pi;
    // pi が min value だったら increment.
    if (min_val > pi)
    {
      min_val = pi;
      ans++;
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int n,i;
  scanf("%d",&n);
  char s[n];
  for(i=0;i<n;i++)
    scanf("%*c%c",&s[i]);
  for(i=0;i<n;i++)
    if(s[i]=='Y'){
      puts("Four");
      return 0;
    }
  puts("Three");
  return 0;
}


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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){


}

Node treeMaximum(Node x){


}

Node treeSearch(Node u, int k){
  if(u == NIL)return NIL;
  else if(k == u->key)return u;
  else if(k < u->key)return treeSearch(u->left,k);
  else return treeSearch(u->right,k);

}

Node treeSuccessor(Node x){


}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y



}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL){
    y = x;
    if(z->key < x->key)
      x = x->left;
    else
      x = x->right;
  }

  z->parent = y;

  if(y == NIL)
    root = z;
  else if(z->key < y->key)
    y->left = z;
  else
    y->right = z;

}

void inorder(Node u){
  if(u->left != NIL)
    inorder(u->left);
  printf(" %d",u->key);
  if(u->right != NIL)
    inorder(u->right);  

}
void preorder(Node u){
  printf(" %d",u->key);
  if(u->left != NIL)
    preorder(u->left);
  if(u->right != NIL)
    preorder(u->right);

}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}



Measured memory_bytes: 20440
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int n, m, f[1000], x;
	while (cin >> n >> m && n != 0) {
		int pos = 0, ans = 0;
		for (int i = 0; i < n; ++i) {
			cin >> f[i];
		}
		while (m--) {
			cin >> x;
			pos += x;
			ans++;
			if (pos >= n - 1)
				break;
			pos += f[pos];
			if (pos >= n - 1)
				break;
		}
		while (m--) {
			cin >> x;
		}

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

Measured memory_bytes: 2944
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <utility>
#include <complex>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <deque>
#include <tuple>
#include <bitset>
#include <limits>
#include <algorithm>
#include <array>
#include <random>
#include <complex>
#include <regex>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef complex<ld> compd;
#define quickIO()	{cin.tie(0);	cout.sync_with_stdio(false);}
#define reach(i,a)	for(auto i:a)
#define rep(i,n)	for(int i=0;i<((int)n);i++)
#define REP(i,n)	for(int i=0;i<=((int)n);i++)
#define srep(i,a,n)	for(int i=a;i<((int)n);i++)
#define SREP(i,a,n)	for(int i=a;i<=((int)n);i++)
#define rrep(i,n)	for(int i=n-1;i>=0;i--)
#define RREP(i,n)	for(int i=n;i>=0;i--)
#define all(a)	(a).begin(),(a).end()
#define mp(a,b)	make_pair(a,b)
#define mt	make_tuple
#define pb	push_back
template<typename T> istream & operator >> (istream & is, vector<T> & vec) {
	for (T& x : vec)	is >> x;
	return is;
}
template<typename T> ostream& operator << (ostream & os, vector<T> & vec) {
	os << "[";
	rep(i, vec.size())	os << (i ? ", " : "") << vec[i];
	os << "]";
	return os;
}
template<typename T> istream & operator >> (istream & is, pair<T, T> & p) {
	is >> p.first >> p.second;
	return is;
}
template<typename T> ostream& operator << (ostream & os, pair<T, T> & p) {
	os << p.first << " " << p.second;
	return os;
}
int bitcnt(ll x) {
	x = ((x & 0xAAAAAAAAAAAAAAAA) >> 1) + (x & 0x5555555555555555);
	x = ((x & 0xCCCCCCCCCCCCCCCC) >> 2) + (x & 0x3333333333333333);
	x = ((x & 0xF0F0F0F0F0F0F0F0) >> 4) + (x & 0x0F0F0F0F0F0F0F0F);
	x = ((x & 0xFF00FF00FF00FF00) >> 8) + (x & 0x00FF00FF00FF00FF);
	x = ((x & 0xFFFF0000FFFF0000) >> 16) + (x & 0x0000FFFF0000FFFF);
	x = ((x & 0xFFFFFFFF00000000) >> 32) + (x & 0x00000000FFFFFFFF);
	return x;
}
int bitcnt(int x) {
	x = ((x & 0xAAAAAAAA) >> 1) + (x & 0x55555555);
	x = ((x & 0xCCCCCCCC) >> 2) + (x & 0x33333333);
	x = ((x & 0xF0F0F0F0) >> 4) + (x & 0x0F0F0F0F);
	x = ((x & 0xFF00FF00) >> 8) + (x & 0x00FF00FF);
	x = ((x & 0xFFFF0000) >> 16) + (x & 0x0000FFFF);
	return x;
}
ll sqrtll(ll x) {
	ll left = 0, right = x;
	rep(i, 100) {
		ll mid = (left + right) >> 1;
		if (mid * mid <= x)	left = mid;
		else	right = mid;
	}
	return left;
}
ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a % b);
}
#define debug(x)	printf("Case #%d: ", x)
#define DEBUG 0
const ld infl = 1e100;
const ll mod = 1e9 + 7;
const ld eps = 1e-9;
const ll inf = 1e18;
const int dx[] = { 1,0,-1,0,0 };
const int dy[] = { 0,1,0,-1,0 };

ll pow2[61];

int main() {
	ll w, h, x, y;	cin >> w >> h >> x >> y;
	printf("%.15lf ", w * h / 2.0);
	cout << (w == x * 2 && h == y * 2) << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
int a[N],b[N],n,m,k,ans;
signed main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		a[i]+=a[i-1];
	}
	for(int i=1;i<=m;i++)
	{
		cin>>b[i];
		b[i]+=b[i-1];
	}
	for(int l=0,r=m;l<=n;l++)
	{
		if(a[l]>k)
			break;
		while(a[l]+b[r]>k)
			r--;
		ans=max(ans,l+r);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 6764
from typing import Tuple, List
from heapq import heappush, heappop


def max_value(max_weight: int, items: List[Tuple[int, int]]) -> float:
    def _cost(weight: int, value: int, i: int) -> Tuple[int, float]:
        # Use value as negative cost
        for j in range(i, n):
            v, w = items[j]
            if (weight + w > max_weight):
                return (-value, -value - (v / w) * (max_weight - weight))
            weight += w
            value += v
        return (-value, -value * 1.0)

    n = len(items)
    items.sort(key=lambda x: x[0] / x[1], reverse=True)
    u, c = _cost(0, 0, 0)
    heap = [(c, u, 0, 0, 0)]
    maxcost = u
    while heap:
        cost, upper, weight, value, i = heappop(heap)
        if (cost > maxcost):
            break
        if (i < n):
            v, w = items[i]
            if (weight + w <= max_weight):
                heappush(heap, (cost, upper, weight + w, value + v, i + 1))
            u, c = _cost(weight, value, i + 1)
            if (c < maxcost):
                if (u < maxcost):
                    maxcost = u
                heappush(heap, (c, u, weight, value, i + 1))

    return -maxcost


if __name__ == '__main__':
    N, W = map(lambda x: int(x), input().split())
    items: List[Tuple[int, int]] = []

    for _ in range(N):
        v, w = map(lambda x: int(x), input().split())
        items.append((v, w))

    print(max_value(W, items))



Measured memory_bytes: 7220
using System;
class c
{
    static void Main()
    {
        var s = Console.ReadLine();
        var one = 0;
        for (int i = 0; i < s.Length; i++) if (s[i] == '1') one++; else break;
        var k = long.Parse(Console.ReadLine());
        Console.WriteLine(k <= one ? '1' : s[one]);
    }
}

Measured memory_bytes: 11092
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<iomanip>
using namespace std;

int main(){
    int s,k,a=0;
    cin>>k>>s;
    for(int i=0;i<=k;i++){
        for(int j=0;j<=k;j++){
            if(s-i-j<=k&&s-i-j>=0){
                a++;
            }
        }
    }
    cout<<a<<endl;

    return 0;
}


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

char t[110];
int end, cnt=1;

int main()
{
	scanf("%s", t);
	
	end = strlen(t);
	std::sort(t, t+end);
	
	for(int i=end-1; i>=1; i--)
	{
		if(t[i]==t[i-1]) cnt++;
		else
		{
			if(cnt%2)	break;
			cnt = 1;
		}
	}

	if(cnt%2) printf("No\n");
	else printf("Yes\n");
	
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <math.h>
#include <bitset>
#include <cmath>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <random>
using namespace std;
typedef long long int ll;
#define repe(i,s,n)for(ll i = s;i<=n;i++)
#define rep_r(i,s,n)for(ll i = n-1;i>s;i--)
#define rep_re(i,s,n)for(ll i = n-1;i>=s;i--)
ll MOD = 1e9 + 7;

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

#define rep_re(i,s,n)for(ll i = n-1;i>=s;i--)
#define rep(i,s,n)for(ll i = s;i<n;i++)
#define repe(i,s,n)for(ll i = s;i<=n;i++)
#define rep(i,s,n)for(ll i = s;i<n;i++)

int a[200001] = {};
int main()
{
    ll k, n; cin >> k >> n;
    rep(i, 0, n) {
        cin >> a[i];
    }

    ll ans = 1e10;
    rep(i, 0, n) {
        ll x = 0, y = 0;
        if (i == 0) {
             x = a[i] + k - a[i + 1];
             y = a[n-1] - a[i];
        }
        else if (i == n - 1) {
            x = a[i]-a[0];
            y = a[i - 1] + k - a[i];
        }
        else {
             x = a[i - 1] + k - a[i];
             y = a[i] + k - a[i + 1];

        }
        ans = min(ans, min(x, y));
    }

    cout << ans << endl;

    return 0;
}


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

int main() {
  string s;
  cin >> s;
  int n = s.size();
  for(int i=0;i<n;i++){
    if(s[i] != s[n-1-i]){cout << "No" << endl;return 0;}
  }
  for(int i=0;i<(n-1)/2;i++){
    if(s[i] != s[(n-1)/2-1-i]){cout << "No" << endl;return 0;}
  }
  for(int i=(n+1)/2;i<n;i++){
    if(s[i] != s[n+(n+1)/2-1-i]){cout << "No" << endl;return 0;}
  }
  cout << "Yes" << endl;
}


Measured memory_bytes: 256
'''
Created on 2020/08/23

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  N=int(pin())
  ans=0
  for i in range(1,N+1):
    ans+=((N//i)*(N//i+1)*i)//2
  print(ans)
  return
main()

Measured memory_bytes: 63124
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <sstream>
#include <string>
using namespace std;

#define loop(i,a,b) for(int i=(a);i<int(b);i++)
#define rep(i,b) loop(i,0,b)

using namespace std;
typedef vector<int> vi;

int main(){
    int len = 10000000+10;
    vi isp(len);
    rep(i,len)isp[i]=i;
    isp[0]=isp[1]=0;
    for(int i=2;i<len;i++){
        if(isp[i]==0)continue;
        for(int j=i+i;j<len;j+=i){
            isp[j]=0;
        }
    }
    isp.erase(remove(isp.begin(),isp.end(),0),isp.end());
    vector<int> ans;
    for(int i=3;i<(int)isp.size();i++){
        if(isp[i]==isp[i-1]+2 &&
           isp[i]==isp[i-2]+6 &&
           isp[i]==isp[i-3]+8) ans.push_back(isp[i]);
    }

    int n;
    while(cin>>n && n){
        int l = 0;
        int r = ans.size();
        while(l+1<r){
            int m=(l+r)/2;
            if(ans[m] <= n){
                l = m;
            }else{
                r = m;
            }
        }
        cout << ans[l] << endl;
    }
}

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

using namespace std;

#define ll long long
#define MAX 100005
ll n, mod;
ll ans[MAX];
vector<ll> prefix[MAX], suffix[MAX];
vector<ll> adj[MAX];

void dfs(ll u, ll p)
{
    ans[u] = 1;
    for(ll i=0; i<adj[u].size(); i++){
        ll v = adj[u][i];
        if(v != p){
            dfs(v, u);
            ans[u] = ans[u] * (1+ans[v]);
            ans[u] = ans[u]%mod;
            prefix[u].push_back(ans[u]);
        }
    }
    ll c = 1;
    for(ll i=adj[u].size()-1; i>=0; i--){
        ll v = adj[u][i];
        if(v != p){
            c = c * (1+ans[v]);
            c = c%mod;
            suffix[u].push_back(c);
        }
    }
    reverse(suffix[u].begin(), suffix[u].end());
}

void dfs2(ll u, ll par, ll prop)
{
    ans[u] = ans[u]*(1+prop);
    ans[u] = ans[u]%mod;
    vector<ll> V;
    for(int i=0; i<adj[u].size(); i++){
        if(adj[u][i] == par) continue;
        else V.push_back(adj[u][i]);
        /*ll p = 1, s = 1;
        if(id != 0) p = p * prefix[u][id-1];
        if(id != adj[u].size()-1) s = s * suffix[u][id+1];
        ll val = (p*s)%mod;
        val = ((1+prop)*val)%mod;
        id++;
        dfs2(adj[u][i], u, val);*/
    }
    for(int i=0; i<V.size(); i++){
        ll p = 1, s = 1;
        if(i != 0) p = p * prefix[u][i-1];
        if(i != V.size()-1) s = s * suffix[u][i+1];
        ll val = (p*s)%mod;
        val = ((1+prop)*val)%mod;
        dfs2(V[i], u, val);
    }
}

int main()
{
    scanf("%lld %lld", &n, &mod);
    if(n == 1){
        cout << 1;
        return 0;
    }
    for(int i=1; i<n; i++){
        ll u, v;
        scanf("%lld %lld", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, -1);
    dfs2(1, -1, 0);
    for(int i=1; i<=n; i++) printf("%lld\n", ans[i]);
}


Measured memory_bytes: 26752
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S):
    if S == N:
        return N + 1

    def f(b, n):
        if n < b:
            return n
        return f(b, n//b) + n % b

    for b in range(2, int(math.sqrt(N)) + 1):
        s = f(b, N)
        if s == S:
            return b

    cnd = []
    for p in range(1, int(math.sqrt(N))+1):
        b = (N - S) // p + 1
        if b < 2:
            continue
        s = f(b, N)
        if s == S:
            cnd.append(b)

    if cnd:
        return min(cnd)

    return -1


def main():
    N = read_int()
    S = read_int()

    print(slv(N, S))


if __name__ == '__main__':
    main()


Measured memory_bytes: 5556
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;}
ll LCM(ll c,ll d){return c/GCD(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
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; }
ll n,k,l,r;
V<ll> a;
V<ll> top[41],back[41];
void make1(int now,ll cnt,ll val){
    if(now==(n+1)/2){
        if(cnt<=k)top[cnt].emplace_back(val);
        return ;
    }
    make1(now+1,cnt+1,val+a[now]);
    make1(now+1,cnt,val);
}
void make2(int now,ll cnt,ll val){
    if(now==n){
        if(cnt<=k)back[cnt].emplace_back(val);
        return ;
    }
    make2(now+1,cnt+1,val+a[now]);
    make2(now+1,cnt,val);
}
int main(){
    cin>>n>>k>>l>>r;
    a.resize(n);
    for(int i=0;i<n;i++)cin>>a[i];
    make1(0,0,0);
    make2((n+1)/2,0,0);
    for(int i=0;i<=k;i++){
        sort(all(back[i]));
    }
    ll ans=0;
    for(int i=0;i<=k;i++){
        for(ll v:top[i]){
            ans+=upper_bound(all(back[k-i]),r-v)-lower_bound(all(back[k-i]),l-v);
        }
    }
    cout<<ans<<"\n";
}


Measured memory_bytes: 23432
#include<bits/stdc++.h>
#define FLASH cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
#define pb push_back
#define int long long
#define fr(i,a,b) for(int i=a;i<b;i++)
#define mod 1000000007
#define FILEIO freopen("/home/aman/Desktop/Kachda/input.txt", "r", stdin); freopen("/home/aman/Desktop/Kachda/output.txt", "w", stdout);
#define pii pair<int, int>
using namespace std;

int n;

signed main()
{
	
 	FLASH

	
	cin>>n;
	vector<pair<string, pii> >v[n + 1]; 

	fr(i, 1, n + 1){
		string s;
		int p;
		cin>>s>>p;
		v[i].pb({s, {-p, i}});
		
	} 	

	sort(v + 1, v + n + 1);
	fr(i, 1, n + 1){
		cout<<v[i][0].second.second<<'\n';
	}

	
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define sz(v) (int)v.size() 
#define all(v) v.begin(), v.end()
void dbg_out() { cerr << "\b\b]\n"; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){ cerr << H << ", "; dbg_out(T...);}
#define watch(...) cerr << "[" << #__VA_ARGS__ << "]: [", dbg_out(__VA_ARGS__)


/****************************** CODE IS HERE ***********************************/


int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    string s; cin >> s;
    string t; cin >> t;
    int n = sz(s);
    int m = sz(t);

    vector <vector<int>> dp(n+1, vector<int> (m+1, 0));
    for (int i = n-1; i >= 0; --i) {
        for (int j = m-1; j >= 0; --j) {
            dp[i][j] = max(dp[i+1][j], dp[i][j+1]);
            if (s[i] == t[j])
                dp[i][j] = max(dp[i][j], 1 + dp[i+1][j+1]);
        }
    }

    // cout << dp[0][0];
    string ans;
    for (int i = 0, j = 0; i < n and j < m; ) {
        if (dp[i][j] == dp[i+1][j]) i++;
        else if (dp[i][j] == dp[i][j+1]) j++;
        else {
            ans += s[i];
            i++; j++;
        }
    }
    cout << ans; 

    return 0;
}
/*

Here I created bottom up solution using the most intutive and straight forward recurrence relation.
That recurrence relation are usually used for top down, becuz base case is at large point, not at small point.
As I told many times, you can use any type of recurrece for top down and bottom up. Topdown and bottom depends on 
how you start to construct the soluion.
topdown, moving from f(current state) => f(next state) (which is not known yet) & call goes on and on until base hits.
bottom up, moving from f(current state) => f(previous state) (already calculated)
So, here I am using bottom, and at start my alreay known solution is base case.

Recurrence relation:
f(i, j) => max{
                f(i+1, j),       0 <= i < n
                f(i, j+1),       0 <= i < m
                1 + f(i+1, j+1), 0 <= i < n && 0 <= j < m
                0,               i >= n or j >= m  base case
            }
Then we get the solution at f(0, 0)

My other submission of same problem using other kind of recurrence which is very known for that problem.
https://atcoder.jp/contests/dp/submissions/14399464

*/

Measured memory_bytes: 35584