akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <stack> // s.top()
#include <bitset>
#include <queue> // s.front()
using namespace std;

typedef long long Int;
typedef pair<Int,Int> P;

#define INF10 10000000000
#define INF5 100000
#define EPS 1e-10
#define MOD 1000000007


int main() {
	string s = "aeiou";
	char ipt;

	cin >> ipt;
	for (int i = 0; i < 5; i++) {
		if (ipt == s[i]) {
			cout << "vowel" << endl;
			return 0;
		}
	}
	cout << "consonant" << endl;



	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;
constexpr double PI = 3.14159265358979323846;
constexpr int di[] = {0, 0, 1, -1};
constexpr int dj[] = {1, -1, 0, 0};

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

    string s;
    cin >> s;

    set<char> st;
    map<char, int> mp;

    REP(i, s.size())
    {
        st.insert(s[i]);
        mp[s[i]]++;
    }

    if (st.size() != 2)
    {
        cout << "No" << endl;
    }
    else
    {
        bool check = true;
        for (auto i : mp)
            if (i.second != 2)
                check = false;

        if (check)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <string>
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <math.h>
 
using namespace std;
int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
 
	int x,y;
    string s;
	cin >> x >> s;
    y = s.size();
    if(y>x){for(int i=0;i<x;i++){cout << s[i];}cout << "...";}else{cout << s;}
  
}

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

using namespace std;

typedef pair<int, int> pi;
pi best[300050];
int n, A[300050];

inline pi merge(pi a, pi b){
	int temp[4] = {a.first, a.second, b.first, b.second};
	sort(temp, temp+4);
	return pi(temp[2], temp[3]);
}
void printbits(int x){
	for(int k = n-1; k>=0; k--) if((x>>k)&1) printf("1"); else printf("0"); printf("\n");
}

int main(){
//	freopen("orplusmax.in", "r", stdin);
	cin >> n;
	for(int i = 0; i<(1<<n); i++) cin >> A[i];
	for(int i = 0; i<(1<<n); i++) best[i] = pi(A[i], 0);
	for(int k = 0; k<n; k++){
//		printf("%d:\n", k);
		for(int i = 0; i<(1<<n); i++){
			if(!((i>>k)&1)){
//				printbits(i);
				best[i|(1<<k)] = merge(best[i|(1<<k)], best[i]);
			}
		}
//		printf("\n");
	}
	int ans = 0;
//	for(int i = 0; i<(1<<n); i++) printf("%d: %d %d\n", i, best[i].first, best[i].second); printf("\n");
	for(int i = 1; i<(1<<n); i++){ ans = max(ans, best[i].first + best[i].second); cout << ans << "\n"; }
}


Measured memory_bytes: 6144
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Math;

class Program{
  public static void Main(){

    var input = Console.ReadLine().Split();
    int a = int.Parse(input[0]);
    int b = int.Parse(input[1]);
    int c = int.Parse(input[2]);
    
    bool d = false;
    
    for(int i=0; i<a; i++){
      if((i*b+c) % a == 0){
        d = true;
        break;
      }
    }
    
    if(d) Console.WriteLine("YES");
    else Console.WriteLine("NO");

  }
}

Measured memory_bytes: 13140
import java.util.Scanner;

public class Main {

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

		    int n = sc.nextInt();
		    int m = sc.nextInt();
		    String s = sc.next();
		    String t = sc.next();
		    
		    int gcd = gcd(n,m);
		    int count = 0;
		    for(int i = 0; i < gcd; i++) {
		    	if(s.substring(0+(i*(n/gcd)),1+(i*(n/gcd))).equals(t.substring(0+(i*(m/gcd)), 1+(i*(m/gcd))))) {
		    		count++;
		    	}
		    }
		    if(count == gcd) {
		    	long nlong = n;
		    	long mlong = m;
		    	long gcdlong = gcd;
		    	System.out.println(nlong * mlong /gcdlong);
		    }else {
		    	System.out.println(-1);
		    }
		    
		    
		    sc.close(); }
	
	public static  int gcd(int a, int b) {
	    if (a < b) {
	        int tmp = a;
	        a = b;
	        b = tmp;
	    }

	    int r = -1;
	    while (r != 0) {
	        r = a % b;
	        a = b;
	        b = r;
	    }

	    return a;    
	}

}


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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2019/03/02  Problem: ABC 101 C / Link: http://abc101.contest.atcoder.jp/tasks/abc101_c  ----- */


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

	LL N, K; cin >> N >> K;
	vector<LL> a(N);
	for (int i = 0; i < N; ++i) {
		cin >> a[i];
	}

	LL ans = (N-1+K-1-1)/(K-1);
	
	
	cout << (ans) << "\n";

	return 0;
}


Measured memory_bytes: 1024
N = gets.chomp.to_i
a = []
a = gets.split("")
cnt = 0
max = 0
for i in 0..N-1
  if a[i] == "I"
    cnt = cnt + 1
  elsif a[i] = "D"
    cnt = cnt - 1
  end
  if max <= cnt
    max = cnt 
  end
end
puts max
  

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

int main()
{
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++)
	{
	    cin>>a[i];
	}
	int dp[n+1]={};
	dp[1]=0;
	dp[2]=abs(a[1]-a[0]);
	for(int i=3;i<=n;i++)
	{
	    dp[i]=min(dp[i-1]+abs(a[i-1]-a[i-2]),dp[i-2]+abs(a[i-1]-a[i-3]));
	}
	cout<<dp[n];
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void A(){
    int x;
    cin>>x;
    if(x>=30) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}
void B(){

}
void C(){

}
void D(){

}
void E(){

}
void F(){

}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    A();
    return 0;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
template<class T> inline bool chmin(T&a, T b){if(a > b){a = b; return true;}else{return false;}}
template<class T> inline bool chmax(T&a, T b){if(a < b){a = b; return true;}else{return false;}}
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1.0)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    string a, b, ans;
    cin >> a >> b;
    if(a.size() != b.size())ans = (a.size() > b.size() ? "A" : "B");
    else{
        ans = "C";
        rep(i, a.size()){
            int A = a[i] - '0';
            int B = b[i] - '0';
            if(A == B)continue;
            ans = ans = (A > B ? "A" : "B");
            break;
        }
    }
    if(ans == "A")cout << "GREATER" << endl;
    if(ans == "B")cout << "LESS" << endl;
    if(ans == "C")cout << "EQUAL" << endl;
}

Measured memory_bytes: 3640
#include "iostream"
#include "algorithm"
#include "string"
#include "vector"
#include "cmath"
#include "bitset"
#include "queue"
#include "functional"
#include "map"
#include "unordered_map"
#include "set"
#include "stack"

#define rep(n) for (int i = 0; i < n; ++i)
#define REP(n,i) for (int i = 0; i < n; ++i)
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define nyan "(=^･ω･^=)"
#define mkp make_pair
#define P pair<ll, ll>
typedef long long ll;
using namespace std;

int n, m, p;
map<int, int>prime;
ll ans;

ll pw(int x, int n) {
	ll y = 1;
	ll p = x;
	while (n != 0) {
		if (n % 2) {
			y = y*p%mod;
			n = n - 1;
		}
		else {
			p = p*p%mod;
			n = n / 2;
		}
	}
	return y;
}
ll modinv(ll x) {
	return pw(x, mod - 2);
}


ll c(int x, int y) {
	ll a = 1, b = 1;
	rep(y) {
		a *= x - i;
		a %= mod;
	}
	rep(y) {
		b *= i + 1;
		b %= mod;
	}
	b = modinv(b);
	return a*b%mod;
}

int main() {
	cin >> n >> m;
	p = 2;
	while (m != 1) {
		while (m%p == 0) {
			++prime[p];
			m /= p;
		}
		++p;
	}
	ans = 1;
	for (auto it = prime.begin(); it != prime.end(); ++it) {
		ans *= c(it->second + n - 1, n - 1);
		ans %= mod;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int a = sc.nextInt();
		int b = sc.nextInt();
		int h = sc.nextInt();
		
		// 計算
		long result = 0;
		result = (a+b)*h/2;
		
		// 出力
		System.out.println(result);
	}
	
	public static class Scanner {
		private BufferedReader br; private StringTokenizer tok;
		public Scanner(InputStream is) throws IOException { br = new BufferedReader(new InputStreamReader(is));}
		private void getLine() throws IOException { while(!hasNext()) tok = new StringTokenizer(br.readLine());}
		private boolean hasNext() { return tok != null && tok.hasMoreTokens();}
		public String next() throws IOException { getLine(); return tok.nextToken();}
		public int nextInt() throws IOException { return Integer.parseInt(next());}
		public long nextLong() throws IOException { return Long.parseLong(next());}
		public double nextDouble() throws IOException { return Double.parseDouble(next());}
	}
}


Measured memory_bytes: 21204
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;

int main(void){
    int n; cin >> n;
    vector<int> d(n);
    for (int i = 0; i < n; i++)
    {
        cin >> d[i];
    }
    sort(d.begin(), d.end());
    cout << d[n/2] - d[n/2-1] << endl;
}

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

int main(){
	char s[3];
	int i;
	for(i=0; i<3; i++){
		cin >> s[i];
	}
	for(i=0; i<3; i++){
		if(s[i]=='7'){
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}


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

using namespace std;using f64 = double;using i64=long long;using u64=unsigned long long;
template<typename T> using Arr=vector<T>;
#define hfor(v, s, e) for(int v=(s);(s)<=v&&v<(e);++v)//half-opened range
#define hfori(v, s, e) for(int v=(e)-1;(s)<=v&&v<(e);--v)//inversion
#define hforo(v, s, e) int v=(s);for(;(s)<=v&&v<(e);++v)//out declaration
#define hforoi(v, s, e) int v=(e)-1; for(;(s)<=v&&v<(e);--v)
#define cfor(v, s, e) hfor(v,(s),(e)+1)//closed range
#define cfori(v, s, e) hfori(v,(s),(e)+1)
#define cforo(v, s, e) hforo(v,(s),(e)+1)
#define cforoi(v, s, e) hforoi(v,(s),(e)+1)
#define rep(v,x) hfor(v,0,(x))
#define repi(v,x) hfori(v,0,(x))
#define repo(v,x) hforo(v,0,(x))
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define pushb push_back
#define pushf push_front
#define popb pop_back
#define popf pop_front
#define empl emplace
#define emplb emplace_back
#define emplf emplace_front
#define fi first
#define se second
#define cxp constexpr
#define PQ std::priority_queue

#ifndef DEBUG
	#pragma GCC optimize ("Ofast")
	auto __PRE_RUN__=(ios::sync_with_stdio(0), cin.tie(0), cout.tie(0),(cout<<fixed<<setprecision(11)), 0);
#endif

template<typename T> cxp T inf() { return numeric_limits<T>::max() / 2; }
auto mapf(auto a, auto f){for(auto& x:a)x=f(x); return a;}
int rd(int lb, int ub){static mt19937 rng(time(0)^i64(new int)); return uniform_int_distribution<int>(lb, ub-1)(rng);}
int rd(int ub=inf<int>()){return rd(0,ub);}
const f64 pi=acosl(-1);
#define endl '\n'//not interactive?
#define int i64//MLE?
using pint = pair<int,int>;
using tint = tuple<int,int,int>;

const int dirs[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int n,m;
bool safe(int y, int x){return 0<=y&&y<n and 0<=x&&x<m;}

signed main(){
	int k; cin>>n>>m>>k;
	int sy,sx,ey,ex;
	cin>>sy>>sx>>ey>>ex;sy--,sx--,ey--,ex--;
	string a[n];
	rep(i,n)
		cin>>a[i];
	bool vis[n][m]{}, nav[n][m]{};
	queue<pint> q;
	q.push({sy,sx});
	vis[sy][sx]=nav[sy][sx]=true;
	int d=0;
	while(sz(q)){
		int qsz=sz(q);
		Arr<pint> buf;
		while(qsz--){
			auto z=q.front();
			if(z==pint{ey,ex}){
				cout<<d<<endl;
				return 0;
			}
			q.pop();

			for(auto d:dirs){
				cfor(i,1,k){
					int ny=z.fi+d[0]*i;
					int nx=z.se+d[1]*i;
					if(safe(ny,nx) and a[ny][nx]=='.' and !vis[ny][nx]){
						if(!nav[ny][nx])
							q.push({ny,nx}), buf.pushb({ny,nx}), nav[ny][nx]=true;
					}else
						break;
				}
			}
		}
		for(auto i:buf)
			vis[i.fi][i.se]=true;
		d++;
	}
	cout<<-1<<endl;

	return 0;
}




Measured memory_bytes: 11240
s = input()
if len(s) == 1:
    print(0)
else:
    r = 0
    f = s[0]
    for i in s[1:]:
        if i == f:
            r += 1
            f = '1' if i == '0' else '0'
        else:
        	f = i
    print(r)

Measured memory_bytes: 3188
import math
def floorm(a, b, n):
  ans = math.floor((a*n)/b) - a*(math.floor(n/b))
  return ans

  
a, b, n = map(int, input().split())
if(b>n):
  print(floorm(a, b, n))
else:
  print(floorm(a, b, b-1))


Measured memory_bytes: 9184
S = input()
sform = int(S[:2])
slatt = int(S[2:])

if sform <= 12 and sform >= 1:
    if slatt <= 12 and slatt >= 1:
        print('AMBIGUOUS')
    else:
        print('MMYY')

else:
    if slatt <= 12 and slatt >= 1:
        print('YYMM')
    else:
        print('NA')

Measured memory_bytes: 9124
n = int(input())
a_list = []
[a_list.append(int(input())) for i in range(5)]
a_min = min(a_list)
if n%a_min == 0:
    btlneck = n//a_min
else:
    btlneck = n//a_min + 1

print(4 + btlneck)

Measured memory_bytes: 2940
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    A=LI()
    if len(set(A))==2:
        print("Yes")
    else:
        print("No")
if __name__ == '__main__':
    main()

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

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

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

const int MAX = 510000;
const int MOD = 1000000007;

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

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

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


int main(void){
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    COMinit();
    int N; cin >> N;
    int cnt[N+1] = {};
    int fst, snd;
    int A[N+1];
    rep(i, N+1){
        int a; cin >> a;
        cnt[a]++;
        A[i] = a;
        if(cnt[a] == 2){
            snd = i;
            rep(j, i) if(A[j] == A[i]) fst = j; 
        }
    }

    for(int k = 1; k <= N+1; k++){
        ll res = COM(N+1, k);
        //fstの左側と右側から合わせてk-1個取る
        ll choice = fst + (N - snd);
        res = (res - COM(choice, k-1)) % MOD;
        if(res < 0) res += MOD;
        cout << res << "\n";
    }
    return 0;
}


Measured memory_bytes: 13952
#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 2019
#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 200005

ll add(ll a,ll b)
{
	a+=b;a%=MOD;
	if(a<0) a+=MOD;
	return a;
}
ll mult(ll a, ll b)
{
	a%=MOD; b%=MOD;
	ll ans=(a*b)%MOD;
	if(ans<0) ans+=MOD;
	return ans;
}
ll pw(ll a, ll b)
{
	ll r=1;
	while(b){
		if(b&1) r=mult(r,a);
		a=mult(a,a);
		b>>=1;
	}
	return r;
}
ll inverse(ll a)
{
	return pw(a,MOD-2);
}

int n;
string s;

vi dp[2019];
ll rem[MAXN];
ll ans=0;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin>>s;
	n=s.length();
	
	for(int i=n-1;i>=0;i--){
		rem[i]=add(mult(s[i]-'0',pw(10,n-1-i)),rem[i+1]);
		dp[rem[i]].pb(i);
	}
	
	for(int i=0;i<2019;i++) sort(dp[i].begin(),dp[i].end());
	
	for(int i=0;i<n;i++){
		if(rem[i]==0) ans++;
		ans+=dp[rem[i]].end()-upper_bound(dp[rem[i]].begin(),dp[rem[i]].end(),i);
	}
	cout<<ans<<'\n';
	
	return 0;
}


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

const ll INF = 1LL << 62;
const double PI = acos(-1);
const double eps = 1e-10;

int main() {
  ll a, b;
  cin >> a >> b;
  rep(i, 3) {
    if (a != i + 1 && b != i + 1) {
      cout << i + 1 << endl;
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 3536
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb push_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef multiset<ll> S;
typedef priority_queue<ll> PQ;
typedef priority_queue<P,vector<P>,greater<P>> SPQ;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;
const double pi=3.14159265358979323846;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<endl;}
template<class T> void outvp(T v){rep(i,v.size())outp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> void outvv(T v){rep(i,v.size()){rep(j,v[i].size()){if(j)cout<<' ';cout<<v[i][j];}cout<<endl;}}
int main(){
    ll n,m,a,b,c,d;cin>>n>>m>>a>>b>>c>>d;
    ll i=(a-c)*n,j=(b-d)*m;
    if(i+j==0)out("infinity");
  	else if(i>0&&i+j>0)out(0);
    else if(i<0&&i+j<0)out(0);
    else{
        ll ans=((abs(i)/abs(i+j))+1)*2;
        if(((abs(i))%(abs(i+j)))==0)ans--;
        out(ans-1);
    }
}


Measured memory_bytes: 256
def myAnswer(K:int,N:int,A:list) -> int:
   distance=[]
   pre = A.pop(0)
   MIN = pre
   for a in A:
      distance.append(a - pre)
      pre = a
   distance.append(MIN + K - A[-1])
   distance.sort()
   return sum(distance[:N - 1])

def modelAnswer():
   tmp=1
def main():
   K,N = map(int,input().split())
   A = list(map(int,input().split()))
   print(myAnswer(K,N,A[:]))


if __name__ == '__main__':
   main()

Measured memory_bytes: 26444
N = gets.to_i
a = gets.chomp.split.map(&:to_i).each_slice(2).map{|n|n.first}
ans = 0

(0..N/2-1).each do |i|
  if a[i]%2==1
    ans += 1
  end
end

if N%2==1 && a[N/2]%2==1
  ans += 1
end

puts ans

Measured memory_bytes: 14220
#include <bits/stdc++.h>
 
using namespace std;
 
vector< int > g[100000];
int dist[100000], ans[100000];
 
void dfs1(int idx, int par)
{
  for(int &to : g[idx]) {
    if(to == par) continue;
    dfs1(to, idx);
    dist[idx] = max(dist[idx], dist[to] + 1);
  }
}
 
void dfs2(int idx, int d_par, int par)
{
  vector< pair< int, int > > d_child;
  // d_child.emplace_back(0, -1);
  for(int &to : g[idx]) {
    if(to == par) d_child.emplace_back(d_par + 1, to);
    else d_child.emplace_back(dist[to] + 1, to);
  }
  sort(d_child.rbegin(), d_child.rend());
  ans[idx] = d_child[0].first;
  for(int &to : g[idx]) {
    if(to == par) continue;
    dfs2(to, d_child[d_child[0].second == to].first, idx);
  }
}
 
int main()
{
  int N;
  cin >> N;
  for(int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
 
  if(N == 2) {
    cout << 1 << endl << 1 << endl;
    return (0);
  }
 
  int root = 0;
  for(int i = 0; i < N; i++) if(g[i].size() >= 2) root = i;
  dfs1(root, -1);
  dfs2(root, 0, -1);
  for(int i = 0; i < N; i++) {
    cout << (N - 1) * 2 - ans[i] << endl;
  }
}

Measured memory_bytes: 26524
import java.util.Scanner;
import java.util.HashMap;
import java.util.List;
import java.util.Arrays;
import java.util.ArrayList;
import java.lang.Math;

public class Main {

    private static Scanner sc = new Scanner(System.in);

    private static int mod = (int) 10e9 + 7;

    public static void main(String[] args) {
        int k = sc.nextInt();
        int x = sc.nextInt();
        for (int i = x -  k + 1; i < x + k; i++) {
            System.out.println(i);
        }
    }

    private static int maxInt(int[] array) {
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (max < array[i]) max = array[i];
        }
        return max;
    }

    private static long maxLong(long[] array) {
        long max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (max < array[i]) max = array[i];
        }
        return max;
    }

    private static int minInt(int[] array) {
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (min > array[i]) min = array[i];
        }
        return min;
    }

    private static long minLong(long[] array) {
        long min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (min > array[i]) min = array[i];
        }
        return min;
    }

}


Measured memory_bytes: 25044
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
using namespace std;
int main() {
	string s;
	cin >> s;
	int n = s.size();
	long long ans = 0, ans1 = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'B') {
			ans1++;
		}
		else {
			ans += ans1;
		}
	}
	cout << ans << endl;
}
	

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

namespace ConsoleApp55
{
    class Program
    {
        static int N, M, Q;
        static List<int[]> list = new List<int[]>();
        static void Main(string[] args)
        {

            var l = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
             N = l[0];
            M = l[1];
            Q = l[2];
            for ( var i = 0; i< Q; i++)
            {
                list.Add(Console.ReadLine().Split(' ').Select(int.Parse).ToArray());
            }
        

         /*   for ( var i = 1; i< 1000; i++)
            {
                var r = check(N * i, ab);
                if (r== 1)
                {
                    Console.WriteLine("OK");
                    return;
                }
                
            }*/


            var list2 = createList(M);
            var ret = 0;
            foreach( var i in list2)
            {
               var r =  chekc(i, list);
             //   Console.WriteLine(r);
                if ( ret < r)
                {
                  
                    ret = r;
                }
            }

            Console.WriteLine(ret);


        }

        static List<List<int>> createList (int M)
        {
            var ret = new List<List<int>>();
            
            var ba = new List<int>() { };
         

         return   createList2( M, ba, 1, 0);




        }
        static List<List<int>> createList2(int M ,List<int> b , int idx , int cnt)
        {
            List<List<int>> ret = new List<List<int>>();
            if (cnt == N)
            {
                //b.Add(M);
                ret.Add(b);
                return ret;
            }
           for ( var i = idx; i< M+1 ; i++)
            {
                var n = new List<int>(b);
                n.Add(i);
                ret.AddRange(createList2(M, n, i , cnt + 1));
            }
            return ret;
        }

        static int chekc( List<int> l, List<int[]> data)
        {
            var ret = 0;
            foreach( var i in data)
            {
            
                if ( l[i[1]-1] - l[i[0]-1] == i[2]){
                    ret = ret + i[3];
                }
            }
            return ret;
        }
        
      
    }
}


Measured memory_bytes: 52524
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Math;

namespace CSharp
{
    static class Program
    {
        static void Main(string[] args)
        {
            ReadString();
            var X = ReadIntArray();

            int ans = int.MaxValue;
            for (int p = 0; p <= 101; p++)
            {
                int value = 0;

                foreach (var x in X)
                {
                    value += (x - p) * (x - p);
                }

                ans = Min(ans, value);
            }

            Console.WriteLine(ans);
        }

        #region Helpers

        static int[] ReadIntArray() => Console.ReadLine().Split().Select(s => int.Parse(s)).ToArray();
        static long[] ReadLongArray() => Console.ReadLine().Split().Select(s => long.Parse(s)).ToArray();

        static int[] ReadLineIntArray(int count) => Enumerable.Repeat(0, count).Select(_ => int.Parse(Console.ReadLine())).ToArray();
        static long[] ReadLineLongArray(int count) => Enumerable.Repeat(0, count).Select(_ => long.Parse(Console.ReadLine())).ToArray();

        static string ReadString() => Console.ReadLine();
        static int ReadInt() => int.Parse(Console.ReadLine());
        static long ReadLong() => long.Parse(Console.ReadLine());

        static void ReadInt(out int first)
        {
            var array = ReadIntArray();
            first = array[0];
        }

        static void ReadInt(out int first, out int second)
        {
            var array = ReadIntArray();
            first = array[0];
            second = array[1];
        }

        static void ReadInt(out int first, out int second, out int third)
        {
            var array = ReadIntArray();
            first = array[0];
            second = array[1];
            third = array[2];
        }

        static void ReadInt(out int first, out int second, out int third, out int fourth)
        {
            var array = ReadIntArray();
            first = array[0];
            second = array[1];
            third = array[2];
            fourth = array[3];
        }

        static void ReadLong(out long first)
        {
            var array = ReadLongArray();
            first = array[0];
        }

        static void ReadLong(out long first, out long second)
        {
            var array = ReadLongArray();
            first = array[0];
            second = array[1];
        }

        static void ReadLong(out long first, out long second, out long third)
        {
            var array = ReadLongArray();
            first = array[0];
            second = array[1];
            third = array[2];
        }

        static void ReadLong(out long first, out long second, out long third, out long fourth)
        {
            var array = ReadLongArray();
            first = array[0];
            second = array[1];
            third = array[2];
            fourth = array[3];
        }

        #endregion
    }
}

Measured memory_bytes: 13268
#include <iostream>
#include <numeric>
#include <vector>
#include <cmath>
#include <map>
using namespace std; 
int main(){
    int a,s; cin >> a >> s;
    int sum = 0;
    for (int i=0;i<s;i++){
        int d; cin >> d;
        sum+=d;
    }
    if (a<=sum){
        cout << "Yes" <<"\n";
    }
    else cout << "No" << "\n";
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define maxn 105
char s[maxn],t[maxn];
int main(){
	int n;scanf("%d%s%s",&n,s,t);
	for(int i=0;i<n;i++)putchar(s[i]),putchar(t[i]);
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long m = sc.nextLong();

        long ans = solve(n, m);
        System.out.println(ans);
    }

    static long solve(long n, long m) {
        // 数列が作れないパターン
        if (Math.abs(n - m) > 1) {
            return 0;
        }

        long ans = 0;
        if (n == m) {
            // 犬猿同値
            long inu = kaijo(n);
            long sal = kaijo(m);
            ans = inu * sal * 2;
        } else {
            if (n > m) {
                long sentou = kaijo(n);
                long other = kaijo(m);
                ans = sentou * other;
            } else {
                long sentou = kaijo(m);
                long other = kaijo(n);
                ans = sentou * other;
            }
        }
        return ans % 1000000007;
    }

    static long kaijo(long n) {
        long ret = 1;
        for (int i = 1; i <= n; i++) {
            ret *= i;
            ret %= 1000000007;
        }
        return ret;
    }
}


Measured memory_bytes: 21972
N, A, B, C, D = map(int, input().split(' '))
S = input()
blocks = [i+1 for i, s in enumerate([s for s in S]) if s == '#']

if '##' in S[A-1:C] or '##' in S[B-1:D]:
    print('No')
elif C < D:
    if S[C-1] == '.' and S[D-1] == '.':
        print('Yes')
    else:
        print('No')
else:
    if '...' in S[max(0, B - 2):D+1]:
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 7952
import java.util.*;
import java.io.*;

class Main{
    public static void main(String[] args){
        FastScanner fsc=new FastScanner();
        long n=fsc.nextLong(), m=fsc.nextLong();
        fsc.close();
        if(n==1){
            if(m==1) System.out.println(1);
            else System.out.println(m-2);
        } else if(m==1){
            System.out.println(n-2);
        } else{
            System.out.println(n*m-(n+m-2)*2);
        }
    }
    static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte(){
            if(ptr<buflen) return true;
            else{
                ptr = 0;
                try{
                    buflen = in.read(buffer);
                }
                catch(IOException e){
                    e.printStackTrace();
                }
                if(buflen<=0) return false;
            }
        return true;
        }
        private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
        private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
        public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public long nextLong() {
            if (!hasNext()) throw new NoSuchElementException();
            long n = 0;
            boolean minus = false;
            int b = readByte();
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            if (b < '0' || '9' < b) throw new NumberFormatException();
            while(true){
                if ('0' <= b && b <= '9') {
                    n *= 10;
                    n += b - '0';
                }
                else if(b == -1 || !isPrintableChar(b)) return minus ? -n : n;
                else throw new NumberFormatException();
                b = readByte();
            }
        }
        public int nextInt() {
            long nl = nextLong();
            if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
            return (int) nl;
        }
        public double nextDouble() { return Double.parseDouble(next());}
        public void close(){
            try{in.close();}
            catch(IOException e){e.printStackTrace();}
        }
    }
}


Measured memory_bytes: 21204
N, Q = list(map(int, input().split()))
S = input()
c = 0
cl = [0 for i in range(N)]
cr = [0 for i in range(N)]
for i in range(0, N-1):
  cl[i+1] = cl[i]
  if S[i:i+2]=="AC":
    c += 1
    cl[i+1] += 1
for i in range(N-1, 0, -1):
  cr[i-1] = cr[i]
  if S[i-1:i+1]=="AC":
    cr[i-1] += 1
for i in range(Q):
  li, ri = list(map(int, input().split()))
  print(c-cl[li-1]-cr[ri-1])

Measured memory_bytes: 8644
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<n; ++i)
#define all(x) begin(perm),end(perm)
#define showall(obj) for(auto x:obj)cout<<x<<endl;
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
typedef vector<int> vint;
typedef vector<ll> vll;
const int inf = 100100100;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
    int A,B,M;
    cin>>A>>B>>M;
    vint a(A); vint b(B);
    rep(i,A)cin>>a[i];
    rep(i,B)cin>>b[i];
    vint x(M);vint y(M); vint c(M);
    rep(i,M)cin>>x[i]>>y[i]>>c[i];

int ans = inf;
    rep(i,M){
        ans = min(ans, a[--x[i]]+b[--y[i]]-c[i]);
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    ans = min(ans,a[0]+b[0]);
   cout<<ans<<endl; return 0;
}


Measured memory_bytes: 2176
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <limits.h>
#include <cmath>
#include <queue>
#include <map>
#include <iomanip>
#include <random>
#include <fstream>
#define rep(i, n) for (int i = 0; i < n; i++)
#define PI 3.14159265358979323846
#define MOD 1000000007
using namespace std;
using ll = long long;

const int MAX = 1000000;

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

// テーブルを作る前処理
void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++){
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

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

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

template <class T> struct cord{
  T x,y;
};

template <class T> double dist(cord<T> a, cord<T> b){
  T dx=a.x-b.x;
  T dy=a.y-b.y;
  return sqrt(dx*dx+dy*dy);
}

int main()
{

  //cout << fixed << setprecision(10);

  string s1,s2,s3; cin >> s1 >> s2 >> s3;
  cout << (char)toupper(s1[0]) << (char)toupper(s2[0]) << (char)toupper(s3[0]);

  return 0;
}


Measured memory_bytes: 256
// 二分探索木の挿入
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>

using namespace std;

#define MAX_N 30
//const int NIL = -1;

typedef struct node
{
    // 節点の値
    int key;
    // 節点の親
    struct node *parent;
    // 節点の左の子
    struct node *left;
    // 節点の右の子
    struct node *right;
}Node;

// グローバル変数の定義
Node *Tree;

void preorderTreeWalk(Node *Tree);
void inorderTreeWalk(Node *Tree);
void postorderTreeWalk(Node *Tree);

void insert(Node *new_Element);

int main(void)
{

    int n, num;
    char str[10];

    cin >> n;

    for(int i = 0; i < n; i++)
    {
    	// 命令を取得
        scanf("%s", str);

        if( str[0] == 'i' )
        {
        	// --- 挿入の命令の時 ---

        	scanf("%d", &num);

            Node *newNode = new Node;

            newNode->key = num;
            newNode->parent = NULL;
            newNode->left = NULL;
            newNode->right = NULL;

            insert(newNode);
        }
        else
        {
        	// --- 表示の命令 ---

            inorderTreeWalk(Tree);
            printf("\n");
            preorderTreeWalk(Tree);
            printf("\n");
        }
    }

    return 0;
}

// 二分探索木の挿入関数
void insert(Node *new_Element)
{
    Node *tree, *parent;

    // 追加する要素の親
    parent = NULL;
    // 木の先頭アドレス
    tree = Tree;

    while( tree != NULL )
    {
    	parent = tree;

        if( new_Element->key < tree->key )
        {
            // 左の子へ移動
        	tree = tree->left;
        }
        else
        {
            // 右の子へ移動
        	tree = tree->right;
        }
    }

    // 追加する要素の親を設定
    new_Element->parent = parent;

    if( parent == NULL )
    {
        // 木が空の時
    	new_Element->parent = NULL;
        // 木が空のなので, 実体を入れる
        Tree = new_Element;

    }
    else if( new_Element->key < parent->key )
    {
        // 左の子にする
    	parent->left = new_Element;
    }
    else
    {
        // 右の子にする
    	parent->right = new_Element;
    }

    return;
}

// 先行順巡回
// 根節点、左部分木、右部分木の順で節点を巡回
void preorderTreeWalk(Node *Tree)
{
    if( Tree == NULL )
    {
    	return;
    }

    printf(" %d", Tree->key);
    preorderTreeWalk(Tree->left);
    preorderTreeWalk(Tree->right);

    return;
}

int pre_right = 0;

// 中間順巡回
// 左部分木、根節点、右部分木の順で節点を巡回
void inorderTreeWalk(Node *Tree)
{

    if( Tree == NULL )
    {
    	return;
    }

    inorderTreeWalk(Tree->left);
    printf(" %d", Tree->key);
    inorderTreeWalk(Tree->right);

    return;
}

// 後行順巡回
// 左部分木、右部分木、根節点の順で節点を巡回
void postorderTreeWalk(Node *Tree)
{

    if( Tree == NULL )
    {
    	return;
    }

    postorderTreeWalk(Tree->left);
    postorderTreeWalk(Tree->right);
    printf(" %d", Tree->key);

    return;
}



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

int main(){
    string s,t;
    cin >> s >> t;
    int a,b;
    cin >> a >> b;
    string u;
    cin >> u;
    if(u==s)cout << a-1 << " " << b << endl;
    else cout << a << " " << b-1 << endl;
    return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
// clang-format off
#define FOR(i, n) for (int i=0; i<(int)n; ++i)
#define RFOR(i, n) for (int i=n-1; i>=0; --i)
#define OUTV(x) FOR(j,x.size()) cerr<<x[j]<<(x.size()-j-1?' ':'\n');
#define OUTM(x) FOR(i,x.size()) {OUTV(x[i])}
#define BLE cerr<<"BLE"<<endl;
#define DEBUG(x) cerr<<"DEBUG: "<<#x<<" = "<<x<<endl;
#define PB push_back
#define MP make_pair
// clang-format on
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  //  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

  int n;
  cin >> n;
  double Y = 0.;
  for (int i = 0; i < n; ++i) {
    double x;
    string coin;
    cin >> x >> coin;
    if (coin == "BTC") {
      Y += 380000 * x;
    } else {
      Y += x;
    }
  }
  printf("%.10lf\n", Y);

  return 0;
}

Measured memory_bytes: 256
n = int(input())
s = input()
r = s.count("R");g = s.count("G");b = s.count("B")
count = r*g*b
for j in range(n):
  for i in range(j):
    if (k:=2*j-i)<n:
      if s[i]!=s[k]!=s[j]!=s[i]:
        count-=1   
print(count)


Measured memory_bytes: 9192
def main():
    a, b = map(int, input().split())
    if a > 0:
        print('Positive')
    elif a <= 0 and b >= 0:
        print('Zero')
    else:
        cnt = b - a + 1
        if cnt%2 == 0:
            print('Positive')
        else:
            print('Negative')

if __name__ == "__main__":
    main()


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

using namespace std;

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

const int N = 2e5 + 5;
const int mod = 1e9 + 7;

inline int mul(int x,int y) {
  return (ll) x * y % mod;
}

int add(int x,int y) {
  return x + y >= mod ? x + y - mod : x + y;
}

int n,a[N],sum[N],dp[N],b[N],sz;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> sz;
  for (int i = 1 ; i <= sz ; i++)
    cin >> b[i];
  for (int i = 1 ; i <= sz ; i++)
    if (b[i] != b[i - 1])
      a[++n] = b[i]; 
  dp[n + 1] = 1;
  for (int i = n ; i >= 1 ; i--) {
    dp[i] = add(dp[i],dp[i + 1]);
    dp[i] = add(dp[i],sum[a[i]]);
    sum[a[i]] = add(sum[a[i]],dp[i + 1]);
  }
  cout << dp[1] << endl;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; //10^19 < 9223372036854775807
typedef unsigned long long ull; //10^20 < 18446744073709551615

#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 

#define MOD 1000000007

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

    vector<int> A(N+1,0);
    for (int i = 1; i < N; i++) {
        ll x;
        cin >> x;
        A[x]++;
    }

    for (int i = 1; i <= N; i++) {
        cout << A[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 4048
import math

def  nCr(n,r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))



N = int(input())

A = list(map(int,input().split()))


dic = {}
now = 0

dic[0] = 1

for i in range(N):

    now += A[i]

    if now not in dic:
        dic[now] = 1

    else:
        dic[now] += 1

ans = 0
for i in dic:

    if dic[i] > 1:
        ans += nCr(dic[i],2)

#print (dic)
print (ans)



Measured memory_bytes: 111184
#include <iostream>
#include <vector>
#include <set>
#include <cstring>
using namespace std;

class D{
public:
  int t, s, e, n, w, b;
  D(){}
  D(int _t, int _s, int _e, int _n, int _w, int _b){
    t = _t; s = _s; e = _e; n = _n; w = _w; b = _b;
  }
  D moveEast(){
    return D(w, s, t, n, b, e);
  }
  D moveNorth(){
    return D(s, b, e, t, w, n);
  }
  D moveRight(){
    return D(t, e, n, w, s, b);
  }
};

vector<D> allState(){
  vector<D> res;
  D d(1, 2, 3, 5, 4, 6);

  for(int i = 0; i < 6; i++){
    for(int j = 0; j < 4; j++){
      res.push_back(d);
      d = d.moveRight();
    }
    if(i < 4)  d = d.moveNorth();
    if(i == 3) d = d.moveEast();
    if(i == 4) d = d.moveEast().moveEast();
  }

  return res;
}

set<int> ans;
vector<D> v;
vector<D> t[7][7][7]; //[top][south][west]
D s[4][4][4]; //[z][y][x]

void show(){
  for(int i = 0; i < 4; i++){
    for(int j = 0; j < 4; j++){
      for(int k = 0; k < 4; k++){
        printf("[%d][%d][%d] t:%d, s:%d, w:%d\n", i,j,k,s[i][j][k].t, s[i][j][k].s, s[i][j][k].w);
      }
    }
  }
}

int calc(){
  int res = 0;
  for(int i = 1; i < 4; i++){
    for(int j = 1; j < 4; j++){
      res += s[i][j][3].e;
    }
  }
  return res;
}

void dfs(int cnt){
  if(cnt == 27){
    int tmp = calc();
    ans.insert(tmp);
    return;
  }

  int x = cnt % 3 + 1;
  int y = (cnt / 3) % 3 + 1;
  int z = cnt / 9 + 1;

  int tval = s[z - 1][y][x].t;
  int sval = s[z][y - 1][x].s;
  int wval = s[z][y][x - 1].w;

  for(int i = 0; i < t[tval][sval][wval].size(); i++){
    s[z][y][x] = t[tval][sval][wval][i];
    dfs(cnt + 1);
  }
}

int main(){
  v = allState();
  for(int i = 0; i < v.size(); i++){
    for(int tflg = 0; tflg < 2; tflg++){
      for(int sflg = 0; sflg < 2; sflg++){
        for(int wflg = 0; wflg < 2; wflg++){
          t[tflg ? v[i].t : 0][sflg ? v[i].s : 0][wflg ? v[i].w : 0].push_back(v[i]);
        }
      }
    }
  }

  int T;
  cin >> T;

  while(T--){
    memset(s, 0, sizeof(s));

    for(int i = 1; i <= 3; i++){
      for(int j = 1; j <= 3; j++){
        int x;
        cin >> x;
        s[0][4 - i][j].t = x;
      }
    }
    for(int i = 1; i <= 3; i++){
      for(int j = 1; j <= 3; j++){
        int x;
        cin >> x;
        s[i][0][j].s = x;
      }
    }

    ans.clear();
    dfs(0);

    if(ans.size() == 0){
      cout << "0\n";
    }
    else{
      for(set<int>::iterator iter = ans.begin(); iter != ans.end(); iter++){
        if(iter != ans.begin()) cout << " ";
        cout << (*iter);
      }
      cout << endl;
    }
  }
}

Measured memory_bytes: 0
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {

    Scanner sc = new Scanner(System.in);
    int x = sc.nextInt();
    int y = sc.nextInt();
 
 //   System.out.println(calc(2,3));
 
    while(x != 0 && y != 0){
        if(x >= y){
            x = calc(x, y);
        }else{
            y = calc(y, x);
        }
    }
    //System.out.println(x + " " + y);
    if(x == 0){
        System.out.println(y);
    }else{
        System.out.println(x);
    }
   
    }
    
    public static int calc(int a, int b){
        return a % b;
    }
}


Measured memory_bytes: 26288
N = int(input())
h = list(map(int, input().split()))

INF = 10 ** 9
dp = [INF] * N
dp[0] = 0
dp[1] = abs(h[1] - h[0])

def chmin(a, b):
    if a > b:
        return b
    else:
        return a
        
for i in range(2, N):
    dp[i] = chmin(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]))
    dp[i] = chmin(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]))

print(dp[-1])

Measured memory_bytes: 13924
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<list>
#include<cstdint>
#include<numeric>

using namespace std;

using uif=uint_fast64_t;
using ll=long long int;

int main(void){

  uif n;
  cin>>n;

  vector<ll> a(n);
  vector<ll> b(n);
  vector<ll> c(n);
  vector<ll> d(n);
  uif a_sum=0;
  uif b_sum=0;

  for(uif i=0;i<n;i++){
    cin>>a[i];
    a_sum+=a[i];
  }
  for(uif i=0;i<n;i++){
    cin>>b[i];
    b_sum+=b[i];
    c[i]=0;
    d[i] = a[i]-b[i];
  }
  //ll a_sum=accumulate(a.begin(),a.end(),0);
  //ll b_sum=accumulate(b.begin(),b.end(),0);
  //cout << a_sum << "," << b_sum << endl;
  if( a_sum < b_sum ){
    cout << -1 << endl;
    return 0;
  }
  else{
    sort(d.begin(),d.end());
    if(d[0] >= 0){
      cout << 0 << endl;
      return 0;
    }
    else{
      ll cnt=0;
      ll neg=0;
      for(uif i=0;i<n;i++){
        if(d[i]<0){
          neg+=d[i];
          cnt++;
        }
        else{
          break;
        }
      }
      for(uif i=d.size()-1;i>0;i--){
        if(neg<0){
          neg+=d[i];
          cnt++;
        }
        else{
          break;
        }
      }
      cout << cnt << endl;
    }
  }

  return 0;
}


Measured memory_bytes: 3328