akhauriyash/Code-Regression huggingface dataset:
package main

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

var scanner = bufio.NewScanner(os.Stdin)

func init() {
	buf := make([]byte, 0)
	scanner.Buffer(buf, 10000000000)
	scanner.Split(bufio.ScanWords)
}

func ScanText() string {
	if scanner.Scan() {
		return scanner.Text()
	}
	_, _ = fmt.Fprintf(os.Stderr, "Text not found")
	return ""
}

func ScanInt() (ret int) {
	var err error
	if scanner.Scan() {
		txt := scanner.Text()
		if ret, err = strconv.Atoi(txt); err != nil {
			_, _ = fmt.Fprintf(os.Stderr, err.Error())
		}
	}
	return
}

func main() {
	n, q := ScanInt(), ScanInt()
	s := ScanText()

	cur := 0
	t := make([]int, n)
	for i := 1; i < n; i++ {
		if s[i-1] == 'A' && s[i] == 'C' {
			cur++
		}
		t[i] = cur
	}

	var w = bufio.NewWriter(os.Stdout)
	for i := 0; i < q; i++ {
		l, r := ScanInt()-1, ScanInt()-1
		_, _ = fmt.Fprintln(w, t[r]-t[l])
	}
	_ = w.Flush()
}


Measured memory_bytes: 5416
#include<iostream>
#include<algorithm>
#include<ctime>
#include<vector>
#include<string>
#include<cmath>
#include<map>
#include<iomanip>
#include<numeric>
#include<queue>
#include<deque>
#include<cfloat>
#include<functional>
#include<tuple>
#include<math.h>
#include<bitset>
#include<stack>
#include<set>
#include<random>
#include<stdlib.h>
#define rip(i,n) for(int i=0;i<n;i++)
#define Rip(i,n) for(int i=1;i<=n;i++)
#define RIP(i,a,b) for(int i=a;i<b;i++)
#define all(V) V.begin(),V.end()
#define sec  setprecision;
#define _CRT_SECURE_NO_WARNINGS
#pragma target("avx")
#pragma optimize("O3")
#pragma optimize("unroll-loops");
constexpr double eps = 1e-9;
constexpr double pi = 3.141592653589793238462643383279;
using namespace std;
using ll = long long;
using ld = long double;
using Pa = pair<int, int>;
ll mod = 1000000007;
ll MOD = 998244353;
ll gcd(ll a, ll b)
{
	if (a % b == 0)	return(b);
	else return(gcd(b, a % b));
}
ll lcm(ll a, ll b)
{
	return a * b / gcd(a, b);
}
ll pow(ll x, ll n) {
	x %= mod;
	if (n == 0)
		return 1;
	if (n % 2 == 0)
		return (pow((x * x) % mod, n / 2) % mod);
	else
		return (x * pow(x, n - 1)) % mod;
}
bool prime(int n) {
	int i = 2;
	if (n == 2)return true;
	else if(n <= 1)return false;
	if (n % i == 0)return false;
	i = 3;
	while (i <= sqrt(n)) {
		if (n % i == 0)return false;
		i += 2;
	}
	return true;
}
signed main() {
	int a, b; cin >> a >> b;
	if (a > b)cout << a - 1;
	else cout << a << endl;
}


Measured memory_bytes: 3616
package main

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

func main() {
	var n string
	fmt.Scan(&n)
	a := NextIntArray()

	numbers := map[int]int{}
	for _, v := range a {
		numbers[v]++
	}

	overTwoTimes := map[int]int{}
	for k, v := range numbers {
		if v >= 2 {
			overTwoTimes[k] = v / 2
		}
	}

	findMax := func() int {
		max := 0
		for k, v := range overTwoTimes {
			if k > max && v > 0 {
				max = k
			}
		}
		overTwoTimes[max]--
		return max
	}

	b := findMax()
	h := findMax()
	fmt.Println(b * h)
}

// reader

var size = 100000
var rdr = bufio.NewReaderSize(os.Stdin, size)

func ReadLine() string {
	buf := make([]byte, 0, size)
	for {
		line, isPrefix, err := rdr.ReadLine()
		if err != nil {
			panic(err)
		}
		buf = append(buf, line...)
		if !isPrefix {
			break
		}
	}
	return string(buf)
}

func NextArray() []string {
	s := ReadLine()
	return strings.Split(s, " ")
}

func NextIntArray() []int {
	a := NextArray()
	na := make([]int, 0)

	for _, v := range a {
		if n, e := strconv.Atoi(v); e == nil {
			na = append(na, n)
		}
	}

	return na
}


Measured memory_bytes: 10112
#include<stdio.h>
int main(void)
{
  int n,i,sign=0;
  int a[10000];
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
    while(a[i]%2==0){
      a[i]/=2;
      sign++;
  }
  }


    printf("%d",sign);
    return 0;

}

Measured memory_bytes: 256
# 大混乱したので乱択  # これ嘘じゃないのか？？？

def main():
    import sys
    sys.setrecursionlimit(500000)
    N = int(input())
    if N==2:
        print(1)
        exit()
    E = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        E[a].append(b)
        E[b].append(a)

    def dfs(v=0, p=-1, root=0):
        cnt_child = 0
        cnt_false = 0
        res = 0
        for u in E[v]:
            if u!=p:
                cnt_child += 1
                d = dfs(u, v, root)
                res += d
                cnt_false += d == 0
        return res + max(0, cnt_false - 1)

    #for i in range(N):
    #    print(dfs(i, -1, i))

    print(max(dfs(i, -1, i) for i in sorted(range(N), key=lambda x: -len(E[x]))[:1]))

main()


Measured memory_bytes: 130156
#include<stdio.h>
#define MAX 2000001
void maxHeapify(int);

int n,a[MAX];
void maxHeapify(int i){
  int l,r,largest,temp;
  l=2*i;
  r=2*i+1;
  if(l<=n && a[l]>a[i])largest = l;
  else largest = i;
  if(r<=n && a[r]>a[largest])largest = r;
  if(largest!=i){
    temp=a[i];
    a[i]=a[largest];
    a[largest]=temp;
    maxHeapify(largest);
  }
}

int main(){
  int i;
  scanf("%d",&n);
  for(i=1;i<=n;i++)scanf("%d",&a[i]);
  for(i=n/2;i>=1;i--)maxHeapify(i);
  for(i=1;i<=n;i++){
    printf(" ");
    printf("%d",a[i]);
  }
  printf("\n");
  return 0;
}



Measured memory_bytes: 3652
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int f[105][15],p[105][15],n,ans=-(1<<30),temp,num;
    scanf("%d",&n);
    for (int i=0;i<n;i++)
        for (int j=0;j<10;j++)
            scanf("%d",&f[i][j]);
    for (int i=0;i<n;i++)
        for (int j=0;j<11;j++)
            scanf("%d",&p[i][j]);
    for (int x=1;x<1024;x++)
        {
            temp=0;
            for (int i=0;i<n;i++)
                {
                    num=0;
                    for (int j=0;j<10;j++)
                        if (x>>j&f[i][j]) num++;
                    temp+=p[i][num];
                }
            ans=max(ans,temp);
        }
    printf("%d",ans);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>
#include <climits>
#include <iterator>
#include <iomanip>
#include <stack>
#include <set>
#include <cstdio>
#include <bitset>
#include <functional>
#include <tuple>
#include <list>
#include <deque>
#include <sstream>
using namespace std;
const constexpr int INF = 1e9;
typedef pair<int, int> P;

#define FOR(i, a, n) for (ll i = (ll)a; i<(ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

typedef long long ll;
typedef vector<int> VI;

struct Less{
   bool operator()(const pair<string, int>&a, const pair<string, int>&b){
        if(a.first==b.first){
            return a.second < b.second;
        }
       return a.first < b.first;
    }
};
const constexpr ll MOD = 1e9 + 7;
struct NODE{
    ll to, cost;
};
ll Q, K; 
ll dist[100010]; //点Kからある点に到着するのにかかるコスト
vector<vector<NODE>> v(100010);
bool check[100010];
void dfs(ll pos, ll sum){
    if(check[pos]) return;
    check[pos] = true;
    dist[pos] += sum;
    for(int i=0; i<v[pos].size(); ++i){
        dfs(v[pos][i].to, v[pos][i].cost+sum);   
    }
    
    
}

int main() {
    ll N; cin >> N;
    REP(i, N-1){
        ll a, b, c; cin >> a >> b >> c;
        a--; b--;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    cin >> Q >> K;
    K--;
    for(int i=0; i<100010; ++i) dist[i]=0;
    for(int i=0; i<100010; ++i) dist[i] = false;
    dfs(K, 0);
    
    
    REP(i, Q){
        ll x, y; cin >> x >> y;
        x--; y--;
        cout << dist[x] + dist[y] << endl;
    }
	return 0;
}

Measured memory_bytes: 12800
#### import ####
import sys
sys.setrecursionlimit(10**7)
import math
from collections import defaultdict

#### 定数 ####
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,M,K = II()
val = N*M-K
ans = 'No'
for i in range(N+1):
  for j in range(M+1):
    if i*M+j*N-2*i*j==K:
      ans ='Yes'
      break
print(ans)

Measured memory_bytes: 40688
#include<iostream>
#include<variant>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<stack>
#include<queue>
#include<climits>

using namespace std;

int main(void) {
	int n = 0;
	cin >> n;
	int sum = 0;
	long long int tot = 0;
	vector<long long int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		sum = (sum + a[i]) % 1000000007;
	}
	for (int i = 0; i < n; i++) {
		sum = (1000000007 + sum - a[i]) % 1000000007;
		tot = (tot + a[i] * sum) % 1000000007;
	}
	cout << tot;
	return 0;
}

Measured memory_bytes: 4828
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=a;i<b;i++)
#define fore(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define F first
#define S second
#define INF ll(1e18)
#define MOD 998244353
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

#define MAXN 100005

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	ll a,b,c,d; cin>>a>>b>>c>>d;
	int t=0;
	while(1){
		if(!t) c-=b;
		else a-=d;
		if(a<=0){
			cout<<"No\n"; return 0;
		}
		if(c<=0){
			cout<<"Yes\n"; return 0;
		}
		t^=1;
	}
	
	return 0;
}


Measured memory_bytes: 3576
n = gets.chomp.to_i
v = gets.chomp.split.map(&:to_i)

def fetch_max(h, exclude_num: -1) 
  cnt = 0
  num = 0  # Sentinel
  h.each do |k, v|
    if k == exclude_num
      next
    end
    if v > cnt
      cnt = v
      num = k
    end
  end

  [cnt, num]
end

even = v.select.with_index { |_, i| i % 2 == 0 }
odd  = v.select.with_index { |_, i| i % 2 == 1 }

# Calculate max element of even
even_h = even.group_by { |e| e }.map { |k, v| [k, v.size] }.to_h
max_even_cnt, max_even_num = fetch_max(even_h)

# p "even num: #{max_even_num}, even cnt: #{max_even_cnt}"

# Calculate max element of odd
odd_h = odd.group_by { |e| e }.map { |k, v| [k, v.size] }.to_h
max_odd_cnt, max_odd_num = fetch_max(odd_h)

# p "odd num: #{max_odd_num}, odd cnt: #{max_odd_cnt}"

if max_even_num == max_odd_num
  # Use the next largest value of odd
  odd_cnt, _ = fetch_max(odd_h, exclude_num: max_even_num)
  # Use the next largest value of even
  even_cnt, _ = fetch_max(even_h, exclude_num: max_even_num)
  cnt = [odd_cnt + max_even_cnt, even_cnt + max_odd_cnt].max # We use max pattern
else
  cnt = max_even_cnt + max_odd_cnt
end

# p "even num: #{max_even_num}, even cnt: #{max_even_cnt}"
# p "odd num: #{max_odd_num}, odd cnt: #{max_odd_cnt}"

p (n - cnt)

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

int main(){
  int a,b;
  cin >> a >> b;
  if( a+b >23 ){
    cout << a+b-24 << endl;
  }else{
    cout << a+b << endl;
  }
  return 0;
}

Measured memory_bytes: 256
N = int(input())		#Nを入力


if 1 > N or N > 200:
	print('Nは1~200の範囲で指定してください')
	exit()

a = input()			#Aを入力
A = a.split()		#入力をスペースで区切って配列化


if len(A) != N:	#入力の数とNが合わなかったらだめ
	print('N個だけ数を入力してください')
	exit()

for i in A:
	if int(i) < 1 or int(i) > 10**9:
		print('Aは1~10^9の範囲で入力してください')
		exit()

count = []
for i in range(0, N):
	x = int(A[i])
	count.append(0)
	while x%2 == 0:	#
		count[i]+=1
		x /= 2
print(min(count))




Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
const int N=5050,mod=1e9+7;
int n,a[N],f[N],s[N],num,nn,pw[N],ans,b[N],m,g[N][N];bool fl[N];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
int main(){
    scanf("%d",&n);pw[0]=g[0][0]=1;
    for(int i=1;i<=n;i++)f[i]=i,s[i]=1,pw[i]=1ll*pw[i-1]*(n-1)%mod;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(~a[i]){
            int fx=find(i),fy=find(a[i]);
            if(fx==fy)fl[fx]=1;
            else f[fx]=fy,fl[fy]|=fl[fx],s[fy]+=s[fx];
        }
        else num++;
    }
    for(int i=1;i<=n;i++)if(f[i]==i){
        if(fl[i])(ans+=pw[num])%=mod;
        else b[++m]=s[i];
    }
    for(int i=1;i<=m;i++)
        for(int j=0;j<=i;j++)
            g[i][j]=(g[i-1][j]+(j?1ll*max(1,j-1)*g[i-1][j-1]%mod*b[i]:0))%mod;
    for(int i=2;i<=m;i++)ans=(ans+1ll*pw[m-i]*g[m][i])%mod;
    ans=(ans+1ll*pw[m-1]*(g[m][1]-m))%mod;
    cout<<((1ll*pw[m]*n-ans)%mod+mod)%mod;
    return 0;
}

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

#define ll long long
#define rep(i, n) for(ll i = 0; i < (n); i++)
ll MOD = 1e9 + 7;
int INF = 1 << 30;
ll INFL = 1LL << 60;

int main() {
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a.at(i);
    ll sum1 = 0;
    ll ans1 = 0;
    ll sum2 = 0;
    ll ans2 = 0;
    rep(i,n){
        sum1 += a.at(i);
        if(i%2 == 0){
            if(sum1 <= 0){
                ans1 += sum1*(-1) + 1;
                sum1 = 1;
            } 
        }
        else{
            if(sum1 >= 0){
                ans1 += sum1 + 1;
                sum1 = -1;
            } 
        }
    }
    rep(i,n){
        sum2 += a.at(i);
        if(i%2 == 1){
            if(sum2 <= 0){
                ans2 += sum2*(-1) + 1;
                sum2 = 1;
            } 
        }
        else{
            if(sum2 >= 0){
                ans2 += sum2 + 1;
                sum2 = -1;
            } 
        }
    }
    cout << min(ans1,ans2) << endl;
    
}


Measured memory_bytes: 1024
A = gets.to_i
B = gets.to_i
C = gets.to_i
D = gets.to_i
E = gets.to_i

ans = 10**9
[A, B, C, D, E].permutation(5).each do |dishes|
  t = dishes[0]
  dishes[1..-1].each do |dish|
    t += 10 - t % 10 if t % 10 != 0
    t += dish
  end
  ans = [ans, t].min
end
puts ans

Measured memory_bytes: 3836
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int N=5010;

ll n, m, k, u, v, x, y, t, a, b, ans;
ll dp[N][N];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	dp[1][1]=2;
	for (int m=2; m<N; m++) dp[1][m]=dp[1][m-1]*2%mod;
	for (int n=2; n<N; n++){
		dp[n][1]=dp[n-1][1]*2%mod;
		for (int m=2; m<N; m++){
			ll sum=(dp[n][m-1]-dp[n-1][m-1]*m)*2%mod;
			dp[n][m]=(dp[n-1][m]*(m+1) + dp[n-1][m-1]*(m-1) + sum)%mod;
		}
	}
	cin>>n>>m;
	if (dp[n][m]<0) dp[n][m]+=mod;
	cout<<dp[n][m]<<"\n";
	
	return 0;
}

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

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);

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

    vector<vector<int>> dp(k + 1, vector<int>(n + 1));

    for(int i = 1; i < a[1]; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            dp[i][j] = 2;
        }
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            dp[a[i]][j] = 1;
        }
    }

    for(int i = 1; i <= k; i++)
    {
        if(dp[i][1] != 0) continue;

        bool hasOne = false;
        
        for(int j = 1; j <= n; j++)
        {
            if(i - a[j] >= 1)
            {
                if(dp[i - a[j]][j] == 1)
                {
                    dp[i][j] = 2;
                }
                else
                {
                    dp[i][j] = 1;
                    hasOne = true;
                    break;
                }      
            }
            else
            {
                dp[i][j] = 2;
            }       
        }

        if(hasOne)
        {
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = 1;
            }
        }
    }

    // for(int i = 1; i <= k; i++)
    // {
    //     cout << i << ": ";
        
    //     for(int j = 1; j <= n; j++)
    //     {
    //         cout << dp[i][j] << " ";
    //     }

    //     cout << "\n";
    // }

    if(dp[k][n] == 1)
    {
        cout << "First";
    }
    else
    {
        cout << "Second";
    }
    
     
    return 0;
}

Measured memory_bytes: 46308
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 0
for i in range(N):
  ans += min(A[i]+A[i+1],B[i])
  A[i+1] -= max(0,min(A[i+1],B[i]-A[i]))
print(ans)

Measured memory_bytes: 18624
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <iomanip>
#include <climits>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<string> VS;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<PII> VPI;
typedef vector<PLL> VPL;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define pf push_front
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ub upper_bound
#define lb lower_bound

int main(){
  ll N;
  cin>>N;
  VS S(N);
  rep(i,N) cin>>S[i];
  int AC=0,WA=0,TLE=0,RE=0;
  
  rep(i,N){
    if(S[i]=="AC") AC++;
    else if(S[i]=="WA") WA++;
    else if(S[i]=="TLE") TLE++;
    else RE++;
  }
  cout<<"AC x "<<AC<<endl;
  cout<<"WA x "<<WA<<endl;
  cout<<"TLE x "<<TLE<<endl;
  cout<<"RE x "<<RE<<endl;
}


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

int main(){
    int s;
    cin >> s;
    int count=1;
    while(s!=1&&s!=2&&s!=4){
        count++;
        if(s%2) s=3*s+1;
        else s/=2;
    }

    cout << count+3 << endl;
}

Measured memory_bytes: 3620
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		double W = sc.nextDouble(), H = sc.nextDouble();
		double x = sc.nextDouble(), y = sc.nextDouble();
		boolean multi = (H % 2 == 0) && (W % 2 == 0) && (W / 2 == x) && (H / 2 == y);
		System.out.println((W * H) / 2.0 + " " + (multi ? 1 : 0));
	}
}

Measured memory_bytes: 23124
// includes
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <functional>
#include <cmath>
#include <climits>
#include <bitset>

// macros
#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for(int i=((int)(n)-1);i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())

using namespace std;

//  types
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
 
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;
const int mod = 1e9 + 7;

// solve
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 dp[10001][101];

int main(int argc, char const* argv[])
{
  string s;
  int d;
  cin >> s >> d;
  int curr = 0;
  rep(i, s.size()){
    int num = int(s[i] - '0');
    rep(j, d){
      rep(k, 10){
        int tmp = (j - k) % d;
        if(tmp < 0)tmp += d;
        dp[i+1][j] = (dp[i+1][j] + dp[i][tmp]) % mod;
      }
    }
    rep(k, num){
      dp[i+1][(curr + k) % d] = (dp[i+1][(curr + k) % d] + 1) % mod;
    }
    curr += num;
  }
  dp[s.size()][curr % d]++;
  ll res = (dp[s.size()][0] - 1) % mod;
  if(res < 0)res += mod;
  cout << res << endl;
	return 0;
}


Measured memory_bytes: 8192
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};

// head

const int N=1010000;
int n,a[N];
ll s[N],ret;
map<ll,int> val;
int main() {
	scanf("%d",&n);
	rep(i,1,n+1) scanf("%d",a+i),s[i]=s[i-1]+a[i];
	rep(i,0,n+1) val[s[i]]++;
	for (auto p:val) {
		ret=(ret+(ll)p.se*(p.se-1)/2);
	}
	printf("%lld\n",ret);
}

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

typedef long long ll;
const int MOD = 1000000007;

int main() {
    int h, w;
    cin >> h >> w;

    char c;
    vector<vector<ll>> dp(h + 2, vector<ll>(w + 2));
    for (int i = 0; i < h + 2; i++) {
        for (int j = 0; j < w + 2; j++) {
            if (i == 0 || i == h + 1 || j == 0 || j == w + 1) {
                dp[i][j] = -1;
            } else {
                cin >> c;
                dp[i][j] = (c == '#' ? -1 : 0);
            }
        }
    }

    dp[1][1] = 1;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            if (dp[i][j] <= 0) {
                continue;
            }
            if (dp[i + 1][j] >= 0) {
                dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % MOD;
            }
            if (dp[i][j + 1] >= 0) {
                dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % MOD;
            }
        }
    }

    cout << (dp[h][w] % MOD) << endl;
}

Measured memory_bytes: 8192
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#include <tuple>
#define rf(x) (x)=0;while(*p<48)im=*p=='-';while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);if(im)(x)=-(x);
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define MOD (1000000007)
#define MAXN (1005)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;

int d[MAXN];
bool isp[MAXN];
int N, Ans = 1;

int main() {
	scanf("%d", &N);
	isp[0] = isp[1] = true; for(int i = 4; i <= N; i += 2) isp[i] = true;
	for(int i = 3; i*i <= N; i += 2) if(!isp[i]) for(int j = i*i; j <= N; j += i) isp[j] = true;
	for(int i = 2; i <= N; i++) {
		for(int p = 2, n = i; 1 < n && p <= N; p++) {
			if(isp[p] || n%p) continue;
			for(; 1 < n && 0 == n%p; n /= p) d[p]++;
		}
	}
	for(int i = 2; i <= N; i++) Ans = (ll)Ans * (d[i] + 1) % MOD;
	printf("%d\n", Ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b)  for(int (i)=(a);(i)<(b);(i)++)
#define REP(i,n)    FOR(i,0,n)
#define RER(i,n)    FOR(i,0,(n+1))
#define pb          push_back
#define mp(a,b)     make_pair((a),(b))
#define mset(m,v)   memset(m,v,sizeof(m))
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;
typedef vector<pair<ll, ll> > vpll;
typedef vector<string> vs;
typedef long double ld;
const double EPS    = 1e-10;
const int INF       = 1e+9;
const double PI     = acos(-1);


auto main() -> int
{
    string a, b, c;
    cin >> a >> b >> c;

    if ( a[a.length() - 1] == b[0] && b[b.length() - 1] == c[0] ) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}



Measured memory_bytes: 256
import numpy as np

if __name__ == "__main__":
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A = sorted(A, reverse=True)
    a = np.asarray(A[:M])
    for i in a:
        if i >= sum(A)/(M*4):
            ret = "Yes"
            continue
        else:
            ret = "No"
            break
    print(ret)


Measured memory_bytes: 21016
#include <iostream>
 
int main(int , char*[])
{
        int num, min, sum = 0;
        int frames[100];
        std::cin >> num;
        for (int i = 0; i < num; i++) {
                std::cin >> frames[i];
                sum += frames[i];
        }
        min = 100*100;
        int ret = 0;
        for (int i = 0; i < num; i++) {
                int nodd;
                int diff = frames[i]*num;
                if (diff > sum) {
                        nodd = diff - sum;
                } else {
                        nodd = sum - diff;
                }
                if (nodd == 0) {
                        std::cout << i << std::endl;
                        return 0;
                }
 
                if (min > nodd) {
                        min = nodd;
                        ret = i;
                }
        }
 
        std::cout << ret << std::endl;
 
        return 0;
}


Measured memory_bytes: 256
#include <iostream>
 
using namespace std;
 
int main(){
  int N;
  int Y;
  cin >> N >> Y;

  int x,y,z;
  int tmpY;
  tmpY = Y / 1000; 

  x = tmpY / 10;
  tmpY = tmpY - x * 10;

  tmpY = tmpY / 5;
  tmpY = tmpY - tmpY * 5;

  z = tmpY / 1;
  tmpY = tmpY - z * 1;

  if(tmpY != 0){
    x = -1;
    y = -1;
    z = -1;
  }

  int right = Y/1000 - N;  
  x = right / 9;
  y = 0;
  while(1){
    if((right - 9 * x) % 4 == 0){
      y = (right - 9 * x) / 4;
      z = N - x - y;
      break;
    }
    x = x - 1;
    if(x < 0){
      y = -1;
      z = -1;
      break;
    }
  }
  
  if(z < 0){
    x = -1;
    y = -1;
    z = -1;
  } 

  cout << x << ' ' << y << ' ' << z << endl;
  
  return 0;
}

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

using namespace std;

typedef long long ll;

int main(){
        ll Q, H, S, D;
        double N;
        cin>>Q>>H>>S>>D>>N;
        ll res=0;
        D=min(D, Q*8);
        D=min(D, H*4);
        D=min(D, S*2);
        S=min(S, Q*4);
        S=min(S, H*2);
        H=min(H, Q*2);
        while(N>=2){
                N-=2;
                res+=D;
        }
        while(N>=1){
                N-=1;
                res+=S;
        }
        while(N>=0.5){
                N-=0.5;
                res+=H;
        }
        while(N>=0.25){
                N-=0.25;
                res+=Q;
        }
        cout<<res<<endl;
        return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define all(a) (a).begin(), (a).end()

int N, K;
int M = 0;

int main()
{
  scanf( "%d%d", &N, &K );

  if( K > (N-1)*(N-2)/2 )
    puts("-1");
  else
  {
    printf( "%d\n", N*(N-1)/2-K );

    rep( i, N-1 )
      printf( "%d %d\n", 1, i+2 );

    int cnt = 0;

    if( (N-1)*(N-2)/2-K > 0 ) rep( i, N-1 ) rep( j, i )
    {
      printf( "%d %d\n", i+2, j+2 );
      ++cnt;

      if( cnt+K == (N-1)*(N-2)/2 )
        return 0;
    }
  }

  return 0;
}


Measured memory_bytes: 128
fun main(args: Array<String>){
    val a = readLine()!!.split(" ")
    val N :Int = a[0].toInt()
    var X :Int = a[1].toInt()
    val m :IntArray = IntArray(N)
    var count = N - 1
    for(i in m.indices){
        m[i] = readLine()!!.toInt()
    }
    //println(m.joinToString())
    m.sort()
    //println(m.joinToString())
    for(i in 1..N-1){
        X = X - m[i]
    }
    while(X >= m[0]){
        X = X - m[0]
        count = count + 1
    }
    println(count)
}


Measured memory_bytes: 38248
n = int(input())
a = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
capa = []
for i in range(2**n):
    s = 0
    num = [0] * n
    for j in range(n):
        if (i>>j)&1:
            num[n-j-1] = 1
    for i in range(n):
        if num[i] == 1:
            s += a[i]
    capa.append(s)
for i in m:
    if i in capa:
        print("yes")
    else:
        print("no")


Measured memory_bytes: 43076
from collections import Counter
N = int(input())
S = [[0]*26 for _ in range(N)]
for i in range(N):
    for s in input():
        S[i][ord(s)-ord("a")] += 1
    S[i] = tuple(S[i])
res = 0
for value in Counter(S).values():
    res += value*(value-1)//2

print(res)

Measured memory_bytes: 181596
N, K = map(str, input().split())
D = map(str, input().split())

D = set(D)	# 集合に変換
number = {'0','1','2','3','4','5','6','7','8','9'}	# 集合
out = D^number
#print(out)


out = sorted(list(out))
res_list = []
flag = 0
for i in range(len(N)):
  if flag == 0:
    if len(set(N[i])&set(out)) == 1:
      res_list.append(N[i])
    else:
      tmp = -1
      for j in range(len(out)):
        if N[i] < out[j]:
          tmp = out[j]
          break
      if tmp == -1:
        res_list.append(out[0])
        flag = 1
      else:
        res_list.append(tmp)
        flag = 2
  elif flag == 1:
    tmp = -1
    for j in range(len(out)):
      if N[i] < out[j]:
        tmp = out[j]
        break
    if tmp == -1:
      res_list.append(out[0])
      flag = 1
    else:
      res_list.append(tmp)
      flag = 2
  elif flag == 2:
    res_list.append(out[0])
        
if flag == 1:
  res_list.append(out[0])  
res = ''
for i in range(len(res_list)):
  res += res_list[i]
print(res)        

Measured memory_bytes: 3064
def abc050_b():
    _ = int(input())
    T = list(map(int, input().split()))
    M = int(input())
    Query = [tuple(map(int, input().split())) for _ in range(M)]

    tot = sum(T)
    for p, x in Query:
        ans = tot - T[p-1] + x
        print(ans)

abc050_b()

Measured memory_bytes: 3060
A, B, m = map(int, input().split())
a, b = [list(map(int, input().split()))for i in range(2)]

ans = min(a) + min(b)
for i in range(m):
        x, y, c = map(int, input().split())
        ans = min(ans, a[x-1]+b[y-1]-c)
print(ans)


Measured memory_bytes: 18740
#include "bits/stdc++.h"
#define FR(n, max) for(int i = (n); i < (max); ++i)
using namespace std;
using ll = long long;
using l = long;
using vi = vector<int>;
using vl = vector<l>;
using vll = vector<ll>;
using vvl = vector<vector<l>>;
using vvll = vector<vector<ll>>;
using pll = pair<ll, ll>;

int main()
{
    int a, b; cin >> a >> b;
    int res;
    if (a >= 13) res = b;
    else if (a >= 6 && a <= 12) res = b / 2;
    else res = 0;

    cout << res;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define all(a) (a).begin(),(a).end()
#define X first
#define Y second
#define inf 2e9+5
using namespace std;
const int N=1e5+5;
int wt[100],val[100];
int dp[N+1];
void solve()
{
  int n,w,ans; cin>>n>>w;
  for(int i=0;i<n;i++)cin>>wt[i]>>val[i];
  memset(dp,-1,sizeof(dp)); dp[0]=0;
  for(int i=0;i<n;i++)
  {
      for(int j=N-val[i];j>=0;j--)
      {
          if(dp[j]==-1)continue;
          if(dp[j+val[i]]==-1)dp[j+val[i]]=dp[j]+wt[i];
          else dp[j+val[i]]=min(dp[j+val[i]],dp[j]+wt[i]);
      }
  }
  for(int i=1;i<=N;i++)if(dp[i]!=-1&&dp[i]<=w)ans=i;
  cout<<ans;
  return;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t; t=1;
    while(t--)solve();
    return 0;
}


Measured memory_bytes: 4396
n, m = list(map(int, input().split()))
S = [input().split() for _ in range(m)]
S = [[int(s[0]), s[1]] for s in S]
ac = [0] * n
wa = [0] * n
for s in S:
    if s[1] == 'AC':
        ac[s[0] - 1] = 1
        continue
    elif ac[s[0] - 1] == 0:
        wa[s[0] - 1] += 1
        continue
wa = [0 if ac[i] == 0 else wa[i] for i in range(n)]
ans = ' '.join(list(map(str, [sum(ac), sum(wa)])))
print(ans)


Measured memory_bytes: 89304
#include <bits/stdc++.h>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i,a,b) for (ll i=(a);i<(ll)b; i++)
#define ALL(obj) (obj).begin(),(obj).end()
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; }
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll,ll> p;
const int MOD = 1000000007;
const long long INF = 1LL<<60;

const int MAX_N = 110;
const int MAX_V = 100100;
void print(const std::vector<int>& v)
{
  std::for_each(v.begin(), v.end(), [](int x) {
    std::cout << x << " ";
  });
  std::cout << std::endl;
}
//dp[ i ][ sum_v ] := i-1 番目までの品物から価値が sum_v 以上を達成するように選んだときの、重さの総和 sum_w の最小値
int N;
ll W,weight[MAX_N],value[MAX_N];
// DPテーブル
long long dp[MAX_N][MAX_V];


int main() {
    cin >> N >> W;
    for (int i = 0; i < N; ++i) cin >> weight[i] >> value[i];

    // 初期化
    for (int i = 0; i < MAX_N; ++i) for (int j = 0; j < MAX_V; ++j) dp[i][j] = INF;

    // 初期条件
    dp[0][0] = 0;

    // DPループ
    for (int i = 0; i < N; ++i) {
        for (int sum_v = 0; sum_v < MAX_V; ++sum_v) {

            // i 番目の品物を選ぶ場合
            if (sum_v - value[i] >= 0) chmin(dp[i+1][sum_v], dp[i][sum_v - value[i]] + weight[i]);

            // i 番目の品物を選ばない場合
            chmin(dp[i+1][sum_v], dp[i][sum_v]);
        }
    }

    // 最適値の出力
    long long res = 0;
    for (int sum_v = 0; sum_v < MAX_V; ++sum_v) {
        if (dp[N][sum_v] <= W) res = sum_v;
    }
    cout << res << endl;
}

Measured memory_bytes: 86272
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String lineN = br.readLine();
		String[] lineA = br.readLine().split(" ");
		int n = Integer.parseInt(lineN);
		int[] a = new int[n];
		int min = Integer.parseInt(lineA[0]);
		int max = min;
		long sun = 0L;
		for(int i=0; i < a.length; i++){
			a[i] = Integer.parseInt(lineA[i]);
			sun = sun + a[i];
			if( max < a[i] ){
				max = a[i];
			}
			if( min > a[i] ){
				min = a[i];
			}
		}
		System.out.println(min + " " + max + " " + sun);
	}
}

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

int main() {
    int n, h, maxim = 0, m;
    cin >> n;
    int res = 0;
    for (int i=0; i<n; i++) {
        cin >> m;
        if (m>=maxim) {
            maxim = m;
            res++;
        }
    }
    cout << res;
    return 0;
}

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

int main() {
    double N;
    cin >> N;

    if (ceil(N / 1.08) < ceil((N + 1) / 1.08)) {
        cout << ceil(N / 1.08) << endl;
        return 0;
    }
    cout << ":(" << endl;
}

Measured memory_bytes: 3784
#include<iostream>
#include<vector>
#define rep(i,m,n)for(int i=(int)m;i<(int)n;i++)
using namespace std;
void so(vector<int>* c) {
	for (int i = 0; i < c->size(); i++) {
		int max = c->at(i);
		int ii = i;
		for (int j = i; j < c->size(); j++) {
			if (max < c->at(j)) {
				max = c->at(j);
				ii = j;
			}
		}
		int swap = c->at(i);
		c->at(i) = max;
		c->at(ii) = swap;
	}

}
int main() {
	int n, a=0, b=0;
	cin >> n;
	vector<int> c(n);
	for (int i = 0; i < n; i++) {
		cin >> c.at(i);
	}
	so(&c);
	for (int i = 0; i < c.size(); i++) {
		if (i % 2 == 0)a += c.at(i);
		else b += c.at(i);
	}
	cout << a - b << endl;
}

Measured memory_bytes: 3628
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#include<random>
#include<unistd.h>
//This code is written by Itst
using namespace std;

int read(){
	int a = 0; char c = getchar(); bool f = 0;
	while(!isdigit(c)){f = c == '-'; c = getchar();}
	while(isdigit(c)){
		a = a * 10 + c - 48; c = getchar();
	}
	return f ? -a : a;
}

signed main(){
#ifndef ONLINE_JUDGE
	//freopen("in","r",stdin);
	//freopen("out","w",stdout);
#endif
	int N = read(); int len = N / __gcd(3 , N);
	map < int , int > pot; vector < int > now;
	for(int i = 1 ; i <= N ; ++i){
		int t = read();
		if(++pot[t] == len){
			now.push_back(t); pot[t] = 0;
		}
	}
	if(now.size() * len != N){puts("No"); return 0;}
	if(now.size() == 1 && now[0] != 0 || now.size() == 3 && (now[0] ^ now[1] ^ now[2])){
		puts("No"); return 0;
	}
	puts("Yes");
	return 0;
}

Measured memory_bytes: 3840
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int mod = 1000000007;
int sum(int a, int b){
    if (a+b<0) return a+b+mod;
    if (a+b >= mod) return a+b-mod;
    return a+b;
}
int mult(int a, int b){
    return ((ll) a * (ll) b) % (ll) mod;
}
main()
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    if (s[0] == 'B'){
        for (int i=0; i < s.size(); i++){
            if (s[i] == 'B') s[i] = 'R';
            else s[i] = 'B';
        }
    }
    int index = -1;
    for (int i=0; i < m; i++) if (s[i] == 'B'){
        index = i;
        break;
    }
    if (index == -1){
        int dp[n][2][2];
        for (int i=0; i < n; i++) for (int j=0; j < 2; j++) for (int k=0; k < 2; k++) dp[i][j][k] = 0;
        dp[0][0][0] = 1, dp[0][1][1] = 1;
        for (int i=1; i < n; i++){
            for (int j=0; j < 2; j++) for (int k=0; k < 2; k++) for (int e=0; e < 2; e++){
                if (j==0 && e==0) continue;
                dp[i][e][k] = sum(dp[i][e][k], dp[i-1][j][k]);
            }
        }
        int ans = 0;
        for (int i=0;i<2;i++) for (int j=0;j<2;j++) if (i!=0 || j != 0) ans=sum(ans, dp[n-1][i][j]);
        cout << ans;
        return 0;
    }
    if (n%2 != 0){
        cout << 0;
        return 0;
    }
    int mx = n+1;
    if (index % 2 == 0) mx = min(mx, index+1);
    else mx = min(mx, index);
    int cnt = 0;
    for (int i=index+1; i < m; i++){
        if (s[i] == 'R') cnt++;
        else{
            if (cnt % 2 != 0) mx = min(mx, cnt);
            cnt = 0;
        }
    }
    int M = (mx+1)/2;
    //cout << mx << endl;
    int dp[n/2+1];
    dp[0] = 1;
    int ans = 0;
    int pref[n/2+2];
    pref[0] = 0;
    pref[1] = 1;
    for (int i=1; i <= n/2; i++){
        if (i < n/2){
            int brd = max((int) 0, i-M);
            dp[i] = sum(pref[i], -pref[brd]);
            pref[i+1] = sum(pref[i], dp[i]);
        }
        else{
            int brd = max((int) 0, i-M);
            for (int j=i-1; j >= brd; j--){
                int val = dp[j];
                int len = 2*(i-j)-1;
                int shift = len+1;
                ans = sum(ans, mult(shift, val));
            }
        }
    }
    cout << ans;
}


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

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
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; }
typedef long long ll;

const long long INF = 1LL << 60;

int main()
{
    int N;
    cin >> N;

    vector<int> A(N+1), B(N);

    rep(i, N + 1) {
        cin >> A[i];
    }
    rep(i, N) {
        cin >> B[i];
    }

    ll res = 0;
    res += min(B[0], A[0]);
    B[0] -= min(B[0], A[0]);

    repd(i, 1, N) {
        ll tmp = min(B[i - 1], A[i]);
        res += tmp;
        A[i] -= tmp;
        B[i - 1] -= tmp;

        tmp = min(B[i], A[i]);
        res += tmp;
        A[i] -= tmp;
        B[i] -= tmp;

    }

    res += min(B[N - 1], A[N]);

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include<utility>
#include<algorithm>

#define pan(i,n) for(int i=0;i<n;i++)
#define pans(i,n,a) for(int i=a;i<n;i++)
#define ll long long int
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define INF 1e9+7
#define PI 3.141592653
#define inf 200007
#define P pair<ll,ll>

using namespace std;

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

int main(){
    int n;
    cin>>n;
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                // int p=gcd(i,j),q=gcd(j,k),r=gcd(i,k);
                ans+=gcd(i,gcd(j,k));
            }
        }
    }
    cout<<ans;
}   

Measured memory_bytes: 3632
C = [input() for i in range(2)]

if C[0][0] == C[1][2] and C[0][1] == C[1][1] and C[0][2] == C[1][0] and C[1][0] == C[0][2] and C[1][1] == C[0][1] and C[1][2] == C[0][0]:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 38384
s = int(input())

# 8 4 2 1 4 2 1 4
# 7 22 11 34 17
a = set()


def f(n):
    return n // 2 if n % 2 == 0 else 3 * n + 1


def r(s):
    if s in a:
        print(len(a) + 1)
    else:
        a.add(s)
        s = f(s)
        r(s)


r(s)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define FOR(i,n) for(int i=0;i<n;i++)
#define SFOR(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define INF INT_MAX
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<ll,ll>P;
ll n,m;
P d[100005];
int main(){
   cin.tie(0);
   ios::sync_with_stdio(false);
   cin>>n>>m;
   ll sum=0,ans=0;
   FOR(i,n){
     cin>>d[i].F>>d[i].S;
   }
   sort(d,d+n);
   int i=0;
   while(1){
    sum+=d[i].S;
    ans+=d[i].S*d[i].F;
    if(sum>=m){
      ans-=d[i].F*(sum-m);
      break;
    }
    i++;
   }
   cout<<ans<<endl;
   return 0;
}


Measured memory_bytes: 1792
def solve():
    n = int(input())
    l = [int(i) for i in input().split()]
    count = 0
    for i in range(n-2):
        if l[i] >= l[i+1] >= l[i+2] or l[i] <= l[i+1] <= l[i+2]:
            count += 1
    return count
    
if __name__ == '__main__':
    print(solve())

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,x,y;
    long long ans;
    cin>>a>>b>>c>>x>>y;
    if((a+b)<=(2*c))
    {
        ans=(a*x)+(b*y);
    }
    else
    {
       ans=c*2*min(x,y);
       if(x>y&&a<(2*c))
       {
           ans=ans+(a*(x-y));
       }
       else if(y>x&&b<(2*c))
       {
           ans=ans+(b*(y-x));
       }
       else
       {
           ans=ans+(2*c*fabs(x-y));
       }


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


Measured memory_bytes: 256
#include <cstdio>
#include <queue>
#define int long long
using namespace std;
const int NC = 2e5 + 5;
int N, A[NC], B[NC];
int pre(int i) { return (i == 1) ? N : (i - 1); }
int nxt(int i) { return (i == N) ? 1 : (i + 1); }
struct cmp {
	bool operator()(const int &x, const int &y) { return B[x] < B[y]; }
};
priority_queue<int, vector<int>, cmp> H;
signed main() {
	scanf("%lld", &N);
	for (int i = 1; i <= N; ++i) scanf("%lld", &A[i]);
	for (int i = 1; i <= N; ++i) scanf("%lld", &B[i]);
	for (int i = 1; i <= N; ++i) if (A[i] != B[i]) H.push(i);
	int ans = 0;
	while (H.size()) {
		int tp = H.top();
		H.pop();
		int dec = (B[tp] - A[tp]) / (B[pre(tp)] + B[nxt(tp)]);
		if (dec == 0 && B[tp] != A[tp]) {
			printf("-1\n");
			return 0;
		}
		B[tp] -= dec * (B[pre(tp)] + B[nxt(tp)]);
		ans += dec;
		if (B[tp] != A[tp])
			H.push(tp);
	}
	printf("%lld\n", ans);
	return 0;
}

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

int main() {
ll n,a,b,c,d,e;
  cin>>n>>a>>b>>c>>d>>e;
  ll cnt=0;
  ll le=min(a,min(b,min(c,min(d,e))));
  
 cout<<5+(n-1)/le<<endl;
}
  
  
  

Measured memory_bytes: 256
def seconds(a):
    hour,minute,second=a.split(":")
    hour,minute,second=int(hour),int(minute),int(second)
    return(3600*hour+60*minute+second)

from itertools import accumulate
while True:
    n=int(input())
    if n==0:
        exit()
    memo=[0]*86401
    for i in range(n):
        l,r=input().split()
        l=seconds(l)
        r=seconds(r)
        memo[l+1]+=1
        if r!=86400:
            memo[r+1]-=1
    ac=list(accumulate(memo))
    print(max(ac))


Measured memory_bytes: 12580
l1 = list(map(int, input().split()))
l1 = sorted(l1)

if l1[1] - l1[0] < l1[2] - l1[1]:
    print((l1[1] - l1[0]) + (l1[2] - l1[1]))
else:
    print((l1[1] - l1[0]) + (l1[2] - l1[1]))

Measured memory_bytes: 3060
N = int(input())
A = list(map(int, input().split()))

ans = 0
pre = -1
cont = 1
for a in A:
    if a == pre:
        cont += 1
    else:
        ans += cont // 2
        cont = 1
    pre = a
if cont != 1:
    ans += cont // 2
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483648
#define INT_MAX 2147483647
#define LL_MIN -9223372036854775808
#define LL_MAX 9223372036854775807
#define ROOP() while (true)

//嘘解法検証用!!!!!
int main(){
    
    string S,T;
    cin >> S >> T;

    int s[26] = {};
    int t[26] = {};
    for(int i=0; i<T.size(); i++){
        s[S[i]-'a']++;
        t[T[i]-'a']++;
    }
    sort(s,s+26);
    sort(t,t+26);

    for(int i=0; i<26; i++){
        if(s[i] != t[i]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    
    return 0;
}


Measured memory_bytes: 776
def search(S,t):
    return _search(S,t,0,len(S)-1)

def _search(S,t,l,r):
    if l > r:
        return False
    m = (l+r)/2
    if S[m] == t:
        return True
    elif S[m] > t:
        return _search(S,t,l,m-1)
    else:
        return _search(S,t,m+1,r)


n = int(raw_input())
S = map(int,raw_input().split(' '))
q = int(raw_input())
T = map(int,raw_input().split(' '))


ret = 0
for t in T:
    if search(S,t):
        ret += 1
print ret

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

#define pb(s) push_back(s)
#define ALL(v) v.begin(), v.end()
#define ALLA(arr, sz) arr, arr + sz
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr, sz) sort(ALLA(arr, sz))
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz))
#define PI 3.14159265358979323846264338327950L


typedef long long ll;


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

    int sx,sy,tx,ty;
    cin>>sx>>sy>>tx>>ty;
    int dx=tx-sx;
    int dy=ty-sy;
    cout<<string(dx,'R')<<string(dy,'U');
    cout<<string(dx,'L')<<string(dy,'D');
    cout<<'D'<<string(dx+1,'R')<<string(dy+1,'U')<<'L';
    cout<<'U'<<string(dx+1,'L')<<string(dy+1,'D')<<'R';
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a,b,c,s;
int main(){
	cin>>a>>b>>c;
	int d=max(max(a,b),c);
	d=d*3;
	d-=a;
	d-=b;
	d-=c;
	if(d%2==0)
	s=d/2;
	else
	s=(d+3)/2;
	cout<<s;
 } 


Measured memory_bytes: 3636