akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(S: str):
    flag = True
    for i, s in enumerate(S):
        if i % 2 == 0:
            if s not in ["R", "U", "D"]:
                flag = False
        else:
            if s not in ["L", "U", "D"]:
                flag = False
    if flag:
        print(YES)
    else:
        print(NO)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int a[100000], b[100000], n, c[1000000];
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i]; c[a[i] + b[i]]++;
	}
	for (int i = 0; i < 999999; i++) {
		c[i + 1] += c[i] / 2; c[i] %= 2;
		if (c[i] == 1)cout << i << ' ' << 0 << endl;
	}
	return 0;
}

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

int main() {
    int n,k,x,y;
    cin >> n >> k >> x >> y;
    int count = 0;
    for(int i = 1; i < n+1; i++){
        if(i< k+1){
            count += x;
        }else{
            count += y;
        }
    }
    cout << count << endl;
    return 0;
    
}




Measured memory_bytes: 256
var
	h,w,a,s,i,j,k:Longint;
	c:array[0..9,0..9]of Longint;
begin
	read(h,w);
	for i:=0 to 9 do for j:=0 to 9 do read(c[i,j]);
	for k:=0 to 9 do for i:=0 to 9 do for j:=0 to 9 do if c[i,j]>c[i,k]+c[k,j]then c[i,j]:=c[i,k]+c[k,j];
	for i:=1 to h*w do begin
		read(a);
		if a>=0 then inc(s,c[a,1]);
	end;
	writeln(s);
end.

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    long long ans = 0;
    cin>>n;
    for(int i = 1; i < n; ++i)
    {
        int num = n - i;
        float sq = sqrt(num);
        for(int j = 1; j <= sq; ++j)
        {
            if(num % j == 0)
            {
                if(j == sq)
                {
                    ++ans;
                }
                else
                {
                    ans += 2;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3700
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
int main() {
	int n;cin>>n;
	vector<ll>  a(n),b(n),d(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	ll s1=0;
	int ns1=0;
	ll s2=0;
	vector<ll> over;
	for(int i=0;i<n;i++){
		cin>>b[i];
		d[i]=a[i]-b[i];
		if(d[i]<0){
			s1+=-d[i];
			ns1++;
		}
		if(d[i]>0){
			over.push_back(d[i]);
			s2+=d[i];
		}
	}
	sort(over.begin(),over.end());
	if(s2<s1){
		cout<<-1<<endl;
		return 0;
	}
	if(s1==0){
		cout<<0<<endl;
		return 0;
	}
	for(int i=0;i<over.size();i++){
		s1-=over[over.size()-1-i];
		ns1++;
		if(s1<=0){
			break;
		}
	}
	cout<<ns1<<endl;

	return 0;
}


Measured memory_bytes: 3196
#pragma GCC optimize "-O3"
#pragma GCC target ("avx")
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v),greater<int>())
#define SPEED ios::sync_with_stdio(false);cin.tie(0);cout<<fixed<<setprecision(12)
#define erase(i) erase(i, 1)
signed gcd(int a, int b){return b?gcd(b,a%b):a;}
signed lcm(int a, int b){return a*b/gcd(a,b);}
template<typename T> void remove(std::vector<T>& vector, unsigned int index){vector.erase(vector.begin() + index);}
//priority_queue<int, vi, greater<int> > que;//昇順
//priority_queue<int> que; // 降順

using namespace std;

const int mod=1e9+7;

signed main()
{
    SPEED;
    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    rep(i, n-2)
    {
        if(s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C')ans++;
    }
    cout << ans << endl;
    return 0;
}


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

int const MAX = 1000001;
int a[MAX + 5];

int main() {
    int n;
    cin >> n;
    rep(i, n) {
        int x;
        cin >> x;
        a[x]++;
    }

    int ans = 0;
    for (int i = 1; i < MAX; i++) {
        if (a[i] == 1) ans++;
        if (a[i] > 0) {
            for (int j = 2; i * j <= MAX; j++) {
                a[i * j] = 0;
            }
        }
    }

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


Measured memory_bytes: 7560
#ifdef _MSC_VER
#pragma warning(disable : 4996)
#include <intrin.h>
#define __builtin_popcount __popcnt
#endif

#include <limits.h>
#include <math.h>
#include <time.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <complex>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, m, n) for (int i = m; i < n; ++i)
#define FORR(i, m, n) for (int i = m - 1; i >= n; --i)
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v, n) reverse(v, v + n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout << (x) << '\n'
#define pe(x) cout << (x) << " "
#define DEBUG(x) cout << #x << ": " << x << endl
#define lb(v, n) lower_bound(v.begin(), v.end(), (n))
#define ub(v, n) upper_bound(v.begin(), v.end(), (n))
#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i, v.size()) cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template <typename T1, typename T2> inline void chmin(T1& a, T2 b) {
	if (a > b) a = b;
}
template <typename T1, typename T2> inline void chmax(T1& a, T2 b) {
	if (a < b) a = b;
}
typedef pair<int, int> pii;
typedef array<int, 3> arr3;
std::random_device rd;
std::mt19937 mt(rd());
constexpr ll MOD = 1e9 + 7;
constexpr int MAX = 200020;
const double pi = acos(-1);
constexpr double EPS = 1e-8;
constexpr ll INF = 1e18;


int dp[2][3000];
void solve() {
	string S; cin >> S;
	dp[0][0] = 0;
	ll ans = 0;
	int N = S.size();
	REP(i, N) {
		int now = i % 2, nxt = (i + 1) % 2;
		REP(j, 2019)dp[nxt][j] = 0;
		REP(j, 2019) {
			dp[nxt][(j * 10 + S[i]-'0') % 2019] += dp[now][j];
		}
		dp[nxt][S[i] - '0']++;
		ans += dp[nxt][0];
	}
	print(ans);
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	// int q; cin >> q;
	// while (q--)
	solve();
}


Measured memory_bytes: 3752
#include<stdio.h>

#define N 100000
#define Gard 10000001

typedef struct{
  int Num;
  char Spel;
}Tarot;

Tarot Qui[N];
Tarot Mer[N];

void QuickS(int ,int );
int Par(int ,int );
void Merge(Tarot *,int ,int ,int );
void MergeS(Tarot *,int ,int );

int main(){
  Tarot Mer[N];
  int i;
  int flag=0;
  int loop;
    
  scanf("%d ",&loop);
  for(i=0;i<loop;i++){
    scanf("%s %d",&Qui[i].Spel,&Qui[i].Num);
    Mer[i].Spel=Qui[i].Spel;
    Mer[i].Num=Qui[i].Num;
  }

  QuickS(0,loop-1);
  MergeS(Mer,0,loop);
  
  
  for(i=0;i<loop;i++){
    if(Qui[i].Spel!=Mer[i].Spel){
      flag=1;
      break;
    }
  }

  if(flag==0){
    printf("Stable\n");
  }

  else if(flag==1){
    printf("Not stable\n");
  }
  
  for(i=0;i<loop;i++){
    printf("%c ",Qui[i].Spel);
    printf("%d\n",Qui[i].Num);
  }

  return 0;
}

void QuickS(int zero,int set){
  int point;

  if(zero<set){
    point=Par(zero,set);
    
    QuickS(zero,point-1);
    
    QuickS(point+1,set);
    }
}

int Par(int zero,int set){
  int init;
  int j;
  Tarot last,temp;
  
  last=Qui[set];
  init=zero-1;
  
  for(j=zero;j<set;j++){
    
    if(last.Num>=Qui[j].Num){
      init+=1;
      temp=Qui[init];
      Qui[init]=Qui[j];
      Qui[j]=temp;
    }
  }
  
  temp=Qui[init+1];
  Qui[init+1]=Qui[set];
  Qui[set]=temp;
  
  return init+1;
}

void  Merge(Tarot *Mer,int lside,int center,int rside){
  int i;
  int Lrenge,Rrenge;
  Tarot Left[N/2+6],Right[N/2+6];
  int jud1,jud2;

  Lrenge=center-lside;
  Rrenge=rside-center;

  for(i=0;i<Lrenge;i++){
    Left[i]=Mer[lside+i];
  }

  for(i=0;i<Rrenge;i++){
    Right[i]=Mer[center+i];
  }

  Left[Lrenge].Num=Gard;
  Right[Rrenge].Num=Gard;
  
  jud1=0;
  jud2=0;

  for(i=lside;i<rside;i++){

    if(Left[jud1].Num<=Right[jud2].Num){
      Mer[i]=Left[jud1];
      jud1++;
    }

    else{
      Mer[i]=Right[jud2];
      jud2++;
    }
  }
}

void MergeS(Tarot *Mer,int lside,int rside){
  int center;

  if(rside>lside+1){

    center=(lside+rside)/2;

    MergeS(Mer,lside,center);

    MergeS(Mer,center,rside);

    Merge(Mer,lside,center,rside);
  }
}



Measured memory_bytes: 4056
from collections import Counter, defaultdict, deque

R, C = [int(x) for x in input().split()]
source = tuple([int(x) - 1 for x in input().split()])  # 0 indexed
dest = tuple([int(x) - 1 for x in input().split()])  # 0 indexed
grid = [input() for r in range(R)]


drdc = [(-1, 0), (0, -1), (0, 1), (1, 0)]


def getNbrGrid(node):
    r, c = node
    for dr, dc in drdc:
        nr = r + dr
        nc = c + dc
        if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != '#':
            yield nr, nc



def bfs(source, getNbr):
    q = deque([source])
    dist = {source: 0}
    while q:
        node = q.popleft()
        d = dist[node]
        for nbr in getNbr(node):
            if nbr not in dist:
                q.append(nbr)
                dist[nbr] = d + 1
    return dist


numComps = 0
compId = {}
for r in range(R):
    for c in range(C):
        if grid[r][c] != "#" and (r, c) not in compId:
            dist = bfs((r, c), getNbrGrid)
            for node in dist:
                compId[node] = numComps
            numComps += 1

if False:
    for r in range(R):
        for c in range(C):
            print(str(compId.get((r, c), ' ')).rjust(3), end="")
        print()

graph = defaultdict(set)
for r in range(R):
    for c in range(C):
        if grid[r][c] != '#':
            comp1 = compId[(r, c)]
            for dr in range(-2, 3):
                for dc in range(-2, 3):
                    nr = r + dr
                    nc = c + dc
                    if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != '#':
                        comp2 = compId[(nr, nc)]
                        graph[comp1].add(comp2)

def getNbrComp(node):
    return graph[node]


if source not in compId or dest not in compId:
    print(-1)
    exit()
sourceComp = compId[source]
destComp = compId[dest]
dist = bfs(sourceComp, getNbrComp)
if destComp not in dist:
    print(-1)
    exit()
print(dist[destComp])

Measured memory_bytes: 231300
/******************************************
* NICK : nikhilsinghh59 *
******************************************/
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define watch(x) cout << (#x) << " is " << (x) << endl
#define endl "\n"

#define PB push_back
#define F first
#define S second
#define all(c) (c).begin(),(c).end()
const int M = 1e9+7;

int main()
{   
    

    ll a , b , c , k;
    cin >> a >> b >> c >> k;

    if(a >= k) {
        cout << k;
        return 0;
    }
    ll ans=0;
    ans += a;
    k-=a;
    if(b >= k) {
        cout << ans << endl;
        return 0;
    }
    k-=b;

    ans-=k;
    cout << ans;
    
    return 0;
}

Measured memory_bytes: 3636
package main

import "fmt"

func main() {
	var N, r int
	fmt.Scan(&N)
	a := make([]int, N)
	b := make([]int, N)
	c := make([]int, N)
	for i := 0; i < N; i++ {
		fmt.Scan(&a[i], &b[i], &c[i])
	}
	var dp [3][100010]int
	dp[0][1] = a[0]
	dp[1][1] = b[0]
	dp[2][1] = c[0]
	for i := 2; i <= N; i++ {
		dp[0][i] = Max(dp[1][i-1], dp[2][i-1]) + a[i-1]
		dp[1][i] = Max(dp[0][i-1], dp[2][i-1]) + b[i-1]
		dp[2][i] = Max(dp[0][i-1], dp[1][i-1]) + c[i-1]
	}
	for i := 0; i < 3; i++ {
		r = Max(r, dp[i][N])
	}
	fmt.Println(r)

}
func Max(a, b int) int {
	if b > a {
		return b
	}
	return a
}


Measured memory_bytes: 7936
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  h, w = map(int, input().split())
  if h == 1 or w == 1:
    print(1)
  else:
    print((h*w)//2 + (h*w) % 2)

if __name__=='__main__':
  main()



Measured memory_bytes: 2940
package main

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

func main() {
	var t string
	var s = bufio.NewScanner(os.Stdin)
	s.Split(bufio.ScanWords)

	if s.Scan() {
		t = s.Text()
	}
	a, err := strconv.Atoi(t)
	if err != nil {
		fmt.Println(-1)
		return
	}

	if s.Scan() {
		t = s.Text()
	}
	b, err := strconv.Atoi(t)
	if err != nil {
		fmt.Println(-1)
		return
	}

	if a > b {
		fmt.Println(-1)
	}

	if a > 100 {
		fmt.Println(-1)
	}

	if b > 100 {
		fmt.Println(-1)
	}

	// for i := 0; i < 2000; i++ {
	// 	if (int(float64(i)*0.08) == a) && (int(float64(i)*0.10) == b) {
	// 		fmt.Println(i)
	// 	}
	// }
	// fmt.Println(-1)

	// // O(1)
	// var x = int(float64(a) / 0.08)
	// if int(float64(x)*0.10) == b {
	// 	fmt.Println(x)
	// 	return
	// }
	// fmt.Println(-1)

	// O(1)
	var x = math.Ceil(float64(b) / 0.10)
	if int(float64(x)*0.08) == a {
		fmt.Println(x)
		return
	}

	x = math.Ceil(float64(a) / 0.08)
	if int(float64(x)*0.10) == b {
		fmt.Println(x)
		return
	}

	fmt.Println(-1)

}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define fr first
#define sc second
#define r_0 return 0
#define ld long double

using namespace std;

    const ll N = 1e7 + 7;
    const ll mod = 1e9 + 7;
    const ld eps = 1e-9;

ll mp[N];

void solve(){
    int n;
    cin >> n;
    for(int i = 1; i <= 100; ++ i){
        for(int j = 1; j <= 100; ++ j){
            for(int k = 1; k <= 100; ++ k){
                ll ans = i * i + j * j + k * k + i * j + i * k + j * k;
                mp[ans] ++;
            }
        }
    }
    for(int i = 1; i <= n; ++ i){
        cout << mp[i] << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tt = 1;
    //cin >> tt;
    while(tt --){
            solve();
    }
}

/**

**/



Measured memory_bytes: 4116
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

int main(void){

    int A, B, C, X;

    scanf("%d%d%d%d", &A, &B, &C, &X);

    int ans = 0;

    for(int x = 0; x <= A; x++){
        for(int y = 0; y <= B; y++){
            for(int z = 0; z <= C; z++){
                if(500 * x + 100 * y + 50 * z == X){
                    ans++;
                }
            }
        }
    }

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

    return 0;
}

Measured memory_bytes: 1736
import sys
sys.setrecursionlimit(10**6)

def input():
  return sys.stdin.readline()[:-1]

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

link=[[] for i in range(N+1)]
for i in range(N-1):
  a, b=map(int, input().split())
  link[a].append(b)
  link[b].append(a)

px=[list(map(int, input().split())) for i in range(Q)]

counter=[0]*(N+1)
for i in range(Q):
  counter[px[i][0]]+=px[i][1]
  
def f(num, prenum=-1, p=0):
  counter[num]+=p
  for postnum in link[num]:
    if postnum==prenum:
      continue
    f(postnum, num, counter[num])
    
f(1)

print(*counter[1:])

Measured memory_bytes: 310864
# -*- coding: utf-8 -*-
n=int(input())
input_list=[list(map(int,input().split())) for i in range(n)]

can_exec = True
for i in range(len(input_list)):
    t_i = input_list[i][0]
    x_i = input_list[i][1]
    y_i = input_list[i][2]
    if (x_i + y_i) > t_i or (t_i + x_i + y_i) % 2 ==1:
        can_exec = False
        print('No')
        break
if can_exec == True:
    print('Yes')

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

int main () {
	int N, M;
	cin >> N >> M;
	int h[N];
	int good[200005];
	for (int i = 0; i < N; i++) {
		cin >> h[i];
		good[i] = true;
	}
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		if (h[a] <= h[b]) good[a] = false;
		if (h[b] <= h[a]) good[b] = false;
	}
	int ans = 0;
	for (int i = 0; i < N; i++) {
		if (good[i]) ans++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 4416
// In the name of God

#include <bits/stdc++.h>

using namespace std;

#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL);
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i, a, b) for(int i=(a); i<(b); i++)

pair<long long, long long> a[(int)1e5+5];

int main() {
	IOS
	int n, m;
	cin >> n >> m;
	rep(i, 0, n) {
		int x, y;
		cin >> x >> y;
		a[i].first = x;
		a[i].second = y;
	}
	sort(a, a+n);
	int ptr = 0;
	long long ans = 0;
	while(m) {
		if(m <= a[ptr].second) {
			ans += m*a[ptr].first;
			m=0;
		}
		else {
			m -= a[ptr].second;
			ans += a[ptr].second*a[ptr].first;
			ptr++;
		}
	}
	cout << ans;
	return 0;
}


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

using ll = long long;
using P = pair<int, int>;
using PP = pair<int, P>;
#define rep1(i,n) for (int i=1; i<=(n); i++)
#define rep0(i,n) for (int i=0; i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
#ifdef _DEBUG
string _format(string args) { string r = "", t; istringstream s(args); while (getline(s, t, ',')) r += t+":%d "; return r + "\n"; }
#define debug(...) do{printf(_format(#__VA_ARGS__).c_str(), __VA_ARGS__);}while(0)
#define FAST_IOSTREAM() do{}while(0);
#else
#define debug(...) do{}while(0)
#define FAST_IOSTREAM() do{std::ios::sync_with_stdio(false); std::cin.tie(nullptr);}while(0)
#endif

int main() {
    FAST_IOSTREAM();

    int h, w, k;
    cin >> h >> w >> k;
    char a[w][h];
    rep0(i,h) {
        string s;
        cin >> s;
        rep0(j,w) {
            a[j][i] = s[j];
        }
    }
 
    ll ans = 0;
    for(int i=0; i<(1<<(h+w));i++) {
        char s[w][h];
        rep0(y,h) { rep0(x,w) { s[x][y] = a[x][y]; } }
        rep0(y,h) {
            if ((i>>y)&1) {
                rep0(x,w) { s[x][y] = 'R'; }
            }
        }
       rep0(x,w) {
            if ((i>>(x+h))&1) {
                rep0(y,h) { s[x][y] = 'R'; }
            }
        }
        int rest = 0;
        rep0(y,h) { rep0(x,w) { if (s[x][y] == '#') rest++; }}
        //rep0(y,h) { rep0(x,w) { cout << s[x][y];} cout << endl;}
        //cout << "r:" << rest << endl;
        if (rest == k) ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3612
n,m = map(int,input().split())
base = [int(input()) for i in range(m)]
i= 0
j = 0

dp = [0]*(n+1)
if m == 0:
  base = [n+1]

if 1 == base[j]:
  dp[1] = 0
  if j < m-1:
    j = j + 1
else:
  dp[1] = 1

dp[0] = 1

for i in range(2,n+1):
  if not (i == base[j]):
    dp[i] = dp[i-1] + dp[i-2]
  elif i == base[j]:
    if j < m-1:
      j = j + 1
  
  
print(int(dp[n]%1000000007))

Measured memory_bytes: 470264
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string.h>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <math.h>
#include <algorithm>
#include <numeric>

using namespace std;

// マクロ&定数 ============================================================
typedef unsigned int uint;
typedef long long ll;
//typedef pair<int, int> P;

typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<bool> vbool;
typedef vector<string> vstring;

typedef vector<pair<int, int>> vpint;
typedef vector<pair<ll, ll>> vpll;
typedef vector<pair<double, double>> vpdouble;

typedef vector<vector<int>> vvint;
typedef vector<vector<ll>> vvll;
typedef vector<vpint> vvpint;
typedef vector<vpll> vvpll;
typedef vector<vector<double>> vvdouble;
typedef vector<vector<string>> vvstring;
typedef vector<vector<bool>> vvbool;

typedef vector<vector<vector<ll>>> vvvll;

const int c_YET = -1;
const int INF = 1e9 + 1;
const ll LLINF = 1e17 + 1;
const int DX[9] = { 0,0,1,-1, 1, 1, -1, -1, 0 }; // 4;４近傍
const int DY[9] = { 1,-1,0,0, 1, -1, 1, -1, 0 }; // 8:８近傍 9:(0,0)を含む
const ll MOD = 1e9 + 7; //10^9 + 7
const ll MAX = 1e9;
const double PI = 3.14159265358979323846264338327950288;
//========================================================================

// テーブルを作る前処理
ll comb_const = 200005;
vll fac(comb_const), finv(comb_const), inv(comb_const);
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (ll i = 2; i < comb_const; 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;
	}
}

// 二項係数計算
ll COM(ll n, ll 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() {

	////==================================
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(30);
	////==================================


	ll N, K;
	cin >> N >> K;

	K = min(K, N - 1);

	COMinit();

	ll ans = 0;
	for (int k = 0; k <= K; k++)
	{
		ll origin = N - k;
		ll maru = N - origin;
		ll bar = N - k - 1;

		//         〇　　　｜　　
		ans += (COM(maru + bar, bar) * COM(N, k)) % MOD;
		ans %= MOD;
	}


	cout << ans;




}





Measured memory_bytes: 4992
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
int N, K;
ll p[200005];
double psa[200005];
int main(){
    cin >> N >> K;
    for (int i=1; i<=N; i++){
        scanf("%lld", &p[i]);
        psa[i] = psa[i-1]+(p[i]+1)/2.0;
    }
    double sum = 0;
    for (int i=K; i<=N; i++){
        sum = max(sum, psa[i]-psa[i-K]);
    }
    printf("%.8lf\n", sum);
    return 0;
}



Measured memory_bytes: 3328
// This file is a "Hello, world!" in C++ language by GCC for wandbox.
#include <iostream>
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;

    map<string, int> counter;
    for (int i=0; i<n; i++) {
        string s;
        cin >> s;
        counter[s] += 1;
    }
    
    int maxcount = 0;
    for (const auto& e : counter) {
        int count = e.second;
        maxcount = max(maxcount, count);
    }
    for (auto it = counter.begin(); it != counter.end(); it++) {
        if (it->second == maxcount) {
            cout << it->first << endl;
        }
    }
    
   
    

}

// GCC reference:
//   https://gcc.gnu.org/

// C++ language references:
//   https://cppreference.com/
//   https://isocpp.org/
//   http://www.open-std.org/jtc1/sc22/wg21/

// Boost libraries references:
//   https://www.boost.org/doc/


Measured memory_bytes: 25216
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;

long long cnt;
int l;
int A[1000000];
int n;
vector<int> G;

// 間隔gを指定した挿入ソート
void insertionSort(int A[], int n, int g) {
  for ( int i = g; i < n; i++ ) {
    int v = A[i];
    int j = i - g;
    while ( j >= 0 && A[j] > v ) {
      A[j + g] = A[j];
      j -= g;
      cnt++;
    }
    A[j + g] = v;
  }
}

void shellSort(int A[], int n) {
  // 数列G = {1, 4, 13, 40, 121, 364, 1093, ...}を生成
  for ( int h = 1; ; ) {
    if ( h > n ) break;
    G.push_back(h);
    h = 3*h + 1;
  }

  for ( int i = G.size()-1; i >= 0; i-- )  // 逆順にG[i] = g を指定
    insertionSort(A, n, G[i]);
}

int main() {
  cin >> n;
  // より速い入力scanf関数を使用
  for ( int i = 0; i < n; i++ ) scanf("%d", &A[i]);
  cnt = 0;

  shellSort(A, n);

  cout << G.size() << endl;
  for ( int i = G.size() - 1; i >= 0; i-- ) {
    printf("%d", G[i]);
    if ( i ) printf(" ");
  }
  printf("\n");
  printf("%d\n", cnt);
  for ( int i = 0; i < n; i++ ) printf("%d\n", A[i]);

  return 0;
}


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

int main() {
    double x[3], y[3], xp, yp, a, b, c, d;
    while (cin >> x[0] >> y[0] >> x[1] >> y[1] >> x[2] >> y[2] >> xp >> yp) {
        int cnt = 0;
        for (int i=0; i<3; ++i) {
            a = x[(i+1)%3] - x[i];
            b = y[(i+1)%3] - y[i];
            c = xp - x[i];
            d = yp - y[i];
            if (0 < a * d - b * c) cnt ++;
        }
        cout << (cnt % 3 ? "NO" : "YES") << endl;
    }
    return 0;
}

Measured memory_bytes: 1216
#include<stdio.h>
int main(void){
  int a,i;
  scanf("%d",&a);
  for(i=0;i<3;i++){
    if(a%10==7){
      printf("Yes");
      return 0;
    }
    a/=10;
  }
  printf("No");
  return 0;
}

Measured memory_bytes: 1724
parseInt(x::String) = parse(Int, x)
parseInt(x::SubString{String}) = parse(Int, x)
parseInt(x::Char) = parse(Int, x)
parseInt(x::Float64) = trunc(Int, x)
parseFloat(x::String) = parse(Float64, x)
parseFloat(x::Int) = trunc(Float64, x)
parseFloat(x::SubString{String}) = parse(Float64, x)
parseFloat(x::Char) = parse(Float64, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    a,b,x=parseMap(split(readline()))
    ans=b÷x-a÷x
    if a%x==0
        ans+=1
    end
    println(ans)
end
main()

Measured memory_bytes: 166032
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;




map<long long,int> MAP;
int n;
long long a[200005],s[200005],ans;
int main()
{
	cin>>n;
	++MAP[0];
	s[0]=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		s[i]=s[i-1]+a[i];
		ans+=MAP[s[i]];
		++MAP[s[i]];
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 15872
const int LG = 21;
const int FN = 400005;
const long long MOD = 1e9 + 7;
const long long INF = 1e9;
const long long INFLL = 1e18;

#include <bits/stdc++.h>

using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

#define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define fi first
#define se second
#define re return
#define pb push_back
#define uniq(x) sort(all(x)); (x).resize(unique(all(x)) - (x).begin())

#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
#define ln cerr << __LINE__ << endl
#else
#define dbg(x) void(0)
#define ln void(0)
#endif // LOCAL

int cx[4] = {-1, 0, 1, 0};
int cy[4] = {0, -1, 0, 1};
string Yes[2] = {"No", "Yes"};
string YES[2] = {"NO", "YES"};

ll inq(ll x, ll y)
{
    if (!y) re 1 % MOD;
    ll l = inq(x, y / 2);
    if (y % 2) re l * l % MOD * x % MOD;
    re l * l % MOD;
}

ll rev(ll x)
{
    return inq(x, MOD - 2);
}

bool __precomputed_combinatorics = 0;
vector<ll> __fact, __ufact, __rev;

void __precompute_combinatorics()
{
    __precomputed_combinatorics = 1;
    __fact.resize(FN);
    __ufact.resize(FN);
    __rev.resize(FN);
    __rev[1] = 1;
    for (int i = 2; i < FN; i++) __rev[i] = MOD - __rev[MOD % i] * (MOD / i) % MOD;
    __fact[0] = 1, __ufact[0] = 1;
    for (int i = 1; i < FN; i++) __fact[i] = __fact[i - 1] * i % MOD, __ufact[i] = __ufact[i - 1] * __rev[i] % MOD;
}

ll fact(int x)
{
    if (!__precomputed_combinatorics) __precompute_combinatorics();
    return __fact[x];
}

ll cnk(int n, int k)
{
    if (k < 0 || k > n) return 0;
    if (!__precomputed_combinatorics) __precompute_combinatorics();
    return __fact[n] * __ufact[n - k] % MOD * __ufact[k] % MOD;
}

int Root(int x, vector<int> &root)
{
    if (x == root[x]) return x;
    return root[x] = Root(root[x], root);
}

void Merge(int v, int u, vector<int> &root, vector<int> &sz)
{
    v = Root(v, root), u = Root(u, root);
    if (v == u) return;
    if (sz[v] < sz[u])
    {
        sz[u] += sz[v];
        root[v] = u;
    }
    else
    {
        sz[v] += sz[u];
        root[u] = v;
    }
}

int ok(int x, int n)
{
    return 0 <= x && x < n;
}

void bfs(int v, vi &dist, vector<vi> &graph)
{
    fill(all(dist), -1);
    dist[v] = 0;
    vi q = {v};
    for (int i = 0; i < q.size(); i++)
    {
        for (auto u : graph[q[i]])
        {
            if (dist[u] == -1)
            {
                dist[u] = dist[q[i]] + 1;
                q.push_back(u);
            }
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int x, y;
    cin >> x >> y;
    cout << max(0ll, x - y);
}

/* Note:
Check constants at the beginning of the code.
    N is set to 4e5 but be careful in problems with large constant factor.
    Setting N in every problem is more effective.
Check corner cases.
    N = 1
No def int long long for now.
Add something here.
*/


Measured memory_bytes: 256
n,m,x=map(int,input().split())
ans=float('INF')
l=[]
for i in range(n):
    a=list(map(int,input().split()))
    l.append(a)
for i in range(2**n+1):
    L=[0]*(m+1)
    b=format(i,'b')
    b='0'*(n-len(b))+str(b)
    for j in range(n):
        if b[j]=='1':
            for k in range(m+1):
                L[k]+=l[j][k]
    if min(L[1:])>=x:
        ans=min(ans,L[0])
if ans!=float('inf'):
    print(ans)
else:
    print(-1)


Measured memory_bytes: 9220
import java.util.*;

public class Main {

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

            String line = scanner.next();
            int cnt = 0;
            int length = line.length();
            for(int i = 0; i < length / 2; i++){
                if(!line.substring(i, i+1).equals(line.substring(length - (i + 1), length - i))){
                    cnt++;
                }
            }
            
            System.out.println(cnt);
        }catch(Exception e){
            e.printStackTrace();
        }
    }
}


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

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

int main(){
int S,W;
cin>>S>>W;
if(S<=W)
cout<<"unsafe"<<endl;
else
{
  cout<<"safe";
}




  return 0;
}


Measured memory_bytes: 3620
n,q = map(int,input().split())
s = input()
t = [0]*(n+1)
for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2]=="AC" else 0)
for i in range(q):
    l,r = map(int,input().split())
    print(t[r-1]-t[l-1])


Measured memory_bytes: 7748
n=gets.to_i

arr=gets.split.map(&:to_i)


arr2=[0]

i=1
save=1
now=arr[0]
(n-1).times{
    
    if arr[i]==now
        save+=1
        
    else
        arr2<<save
        save=1
    
        now=arr[i]
    
    
    end
    
   i+=1 
    
}




    arr2<<n-arr2.inject(:+)


ans=0
ll=arr2.length


k=0
ll.times{
   ans+=(arr2[k])/2 
    
   k+=1
}


p ans




Measured memory_bytes: 1788
// B - Resistors in Parallel
#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[])
{
	cout.setf(ios::fixed);
	cout.setf(ios::showpoint);
	cout.precision(10);

	int n;
	cin >> n;
	vector<double> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	double ans = 0;
	for (int i = 0; i < n; i++)
		ans += 1.0 / a[i];
	ans = 1.0 / ans;

	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
	int a, b;
	int n;
	long total = 0;
	cin >> n;
	for (a= 1;a <= (n-1);a++) {
		b = (n-1) / a;
		total += b;
	}
	cout << total;
}

Measured memory_bytes: 3636
#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
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
typedef multiset<ll> S;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const int INF=1001001001;
const int mod=1000000007;
const double eps=1e-10;
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<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){a%=mod;if(b==0)return 1;if(b&1)return a*modpow(a,b-1)%mod;ll k=modpow(a,b/2);return k*k%mod;}
vi dep,par;
vvi g;
void dfs0(int i,int p,int d){
    par[i]=p;
    dep[i]=d;
    for(ll x:g[i])if(x!=p)dfs0(x,i,d+1);
}
void init(ll n){
    g=vvi(n);
    dep=vi(n);
    par=vi(n);
    rep(i,n-1){
        ll a,b;cin>>a>>b;a--;b--;
        g[a].pb(b);
        g[b].pb(a);
    }
    dfs0(0,-1,0);
}
int main(){
    ll n;cin>>n;
    vi v(n);
    rep(i,n)cin>>v[i];
    init(n);
    vi c(n),m(n);
    vp t(n);
    rep(i,n)t[i]=P(dep[i],i);
    sort(all(t));reverse(all(t));
    rep(tt,n-1){
        ll i=t[tt].se;
        ll k=v[i];
        if(g[i].size()>1){
            ll mi=min(c[i]/2,c[i]-m[i]);
            mi+=c[i]-mi*2;
            if(!isin(v[i],mi,c[i]))dame("NO");
            k=v[i]*2-c[i];
        }
        chmax(m[par[i]],k);
        c[par[i]]+=k;
    }
    if(g[0].size()>1){
        YESNO(c[0]==v[0]*2&&m[0]<=v[0]);
    }
    else{
        YESNO(c[0]==v[0]);
    }
}

Measured memory_bytes: 15232
#include<bits/stdc++.h>
#define lson root<<1
#define rson root<<1|1
using namespace std;

int n;
int a[200010];
int sum[200010];

struct node
{
	int l,r,sum;
}tr[1600080];

int push_up(int root)
{
	tr[root].sum=tr[lson].sum+tr[rson].sum;
}

int build(int root,int l,int r)
{
	if(l==r)
	{
		tr[root].sum=0;
		tr[root].l=l;
		tr[root].r=r;
		return 0;
	}
	tr[root].l=l;
	tr[root].r=r;
	int mid=(l+r)>>1;
	build(lson,l,mid);
	build(rson,mid+1,r);
	push_up(root);
}

int update(int root,int pos)
{
	if(pos==tr[root].l&&pos==tr[root].r)
	{
		tr[root].sum++;
		return 0;
	}
	int mid=(tr[root].l+tr[root].r)>>1;
	if(pos<=mid)
	{
		update(lson,pos);
	}
	else
	{
		update(rson,pos);
	}
	push_up(root);
}

int query(int root,int l,int r)
{
	if(l>r) return 0;
	if(l<=tr[root].l&&tr[root].r<=r) return tr[root].sum;
	int mid=(tr[root].l+tr[root].r)>>1;
	if(r<=mid)
	{
		return query(lson,l,r);
	}
	else
	{
		if(l>mid)
		{
			return query(rson,l,r);
		}
		else
		{
			return query(lson,l,mid)+query(rson,mid+1,r);
		}
	}
}

int check(int x)
{
	long long ans=0;
	memset(sum,0,sizeof(sum));
	for(int i=1;i<=n;i++)
	{
		sum[i]=sum[i-1]+((a[i]<=x)?1:-1);
	}
	for(int i=0;i<=n;i++)
	{
		sum[i]+=n+1;
	}
	build(1,1,200010);
	for(int i=0;i<=n;i++)
	{
		ans+=query(1,1,sum[i]-1);
		update(1,sum[i]);
	}
	return ans>=1ll*n*(n+1)/4+1;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	int l=1,r=1e9,mid;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(check(mid))
		{
			r=mid;
		}
		else
		{
			l=mid+1;
		}
		if(r-l<=1) 
		{
			mid=check(l)?l:r;
			break;
		}
	}
	printf("%d\n",mid);
//	int min1=1e9+1;
//	for(int i=1;i<=n;i++)
//	{
//		if(a[i]>=mid) min1=min(min1,a[i]);
//	}
//	printf("%d\n",min1);
}

Measured memory_bytes: 9600
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author tatsumack
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>

#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(12)

using namespace std;

template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
    for (auto& e:t) fill_v(e, v);
}

typedef pair<int, int> P;

class AApplePie {
public:
    void solve(std::istream& cin, std::ostream& cout) {
        int A, P;
        cin >> A >> P;
        cout << ((A * 3) + P) / 2 << endl;
    }
};


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    std::istream& in(std::cin);
    std::ostream& out(std::cout);

    AApplePie solver;
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    int ans = INT_MAX;
    int cur = 0;
    for (int i = 0; i < n - k + 1; ++i) {
        if (nums[i] >= 0) {
            cur = nums[i + k - 1];
        } else if (nums[i + k - 1] <= 0){
            cur = -nums[i];
        } else if (nums[i] < 0 && nums[i + k - 1] > 0) {
            cur = min(2 * -nums[i] + nums[i + k - 1], -nums[i] + 2 * nums[i + k - 1]);
        }
        ans = min(ans, cur);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<map>
#include<vector>
using namespace std;
 
int main() {
	int N, M;
	cin >> N >> M;
	vector<int> A(N);
	for (int i = 0; i < A.size(); i++)
	{
		cin >> A[i];
	}
	
	map<int, int> m;
	vector<int> SUM(N + 1);
	SUM[0] = 0;
	for (int i = 0; i < N; i++)
	{
		SUM[i + 1] = (SUM[i] + A[i]) % M;
	}
 
	long ans = 0;
	for (int i = 0; i < SUM.size(); i++)
	{
		ans += m[SUM[i]];
		m[SUM[i]]++;
	}
 
	cout << ans << endl;
}

Measured memory_bytes: 3968
#include <bits/stdc++.h>
using namespace std;
#define All(a) a.begin(), a.end()
typedef pair<long long, long long> P;
long long INF = 1e18;
int main(){
    long long N, K;
    cin >> N >> K;
    vector<long long> A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
        A[i]--;
    }
    vector<long long> to;
    to.push_back(0);
    long long t = INF;
    map<long long, long long> m;
    long long k;
    m[0] = 0;
    long long i = 1;
    while(1){
        if(t == INF)t = A[0];
        else t = A[t];
        if(m.count(t)) {
            k = t;
            break;
        }
        m[t] = i;
        i++;
        to.push_back(t);
    }
    long long u = (long long)to.size() - m[k];
    long long a = (K - (long long)to.size()) % u;
    if(K < to.size()) cout << to[K] + 1<< endl;
    else cout << to[a + m[k]] + 1 << endl;
}

Measured memory_bytes: 18680
#include<bits/stdc++.h>
#define rep(i,n) for (int i=0;i<(n);i++)
#define repd(i,a,b) for (int i=(a);i<(b);i++)
typedef long long ll;
using namespace std;
 
int main() {
    int n;cin>>n;
    vector<int>v(n);
    rep(i,n)cin >> v[i];
    sort(v.begin(),v.end());
    int ans = 0;
    rep(i,n-2){
        repd(j,i+1,n-1){
            repd(k,j+1,n){
                if(v[i]+v[j]>v[k])ans++;
            }
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
# スペース区切りの整数の入力
A, B = map(int, input().split())
S = input()

index = S.find("-")
if S.count("-") != 1:
    print("No")
    exit(0)
if index == -1:
    print("No")
    exit(0)
if len(S[:index]) != A:
    print("No")
    exit(0)
if len(S[index+1:]) != B:
    print("No")
    exit(0)

print("Yes")


Measured memory_bytes: 9120
function C168(_input) {
    var lines = _input.split("\n");
    var [a, b, H, M] = lines.shift().split(' ').map(v => v*1);
    var min = (H * 60 + M);

    const radA = (min*0.5)*(Math.PI/180);
    const radB = (M*6)*(Math.PI/180);

    var posA = {x: Math.cos(radA) * a, y: Math.sin(radA) * a};
    var posB = {x: Math.cos(radB)* b, y: Math.sin(radB) * b};
    const x = (posB.x - posA.x) * (posB.x - posA.x);
    const y = (posB.y - posA.y) * (posB.y - posA.y);

    console.log(Math.sqrt(x + y));
}
C168(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29800
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include<cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include<iostream>
#include<queue>
#include<set>
#include<string>
#include <vector>

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

using namespace std;

int main(){
	int A, B, C, X, Y, ans = 0;

	scanf("%d %d %d %d %d", &A, &B, &C, &X, &Y);
	if (A + B>2 * C){
		ans += min(X, Y)*C * 2;
		if (X > Y){
			ans += (X - Y)*min(A, 2 * C);
		}
		else{
			ans += (Y - X)*min(B, 2 * C);
		}
	}
	else{
		ans += A*X;
		ans += B*Y;
	}

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

	return 0;
}

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

int main()
{
  int N, M, P;
  while( cin >> N >> M >> P, N + M + P ) {
    int X[100];
    int sum = 0;
    for(int i=0; i<N; i++) cin >> X[i], sum += X[i] * 100;
    sum *= (100 - P);
    if( X[M-1] == 0 ) cout << 0 << endl;
    else cout << sum / X[M-1] / 100 << endl;
  }
}

Measured memory_bytes: 2984
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
using namespace std;
#define INF 2147483647
#define LINF 9223372036854775807
#define MOD 1000000007
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define ARDEB(i,X) {}
#define END {}
#endif
//typedef long long int ll;
int n,q;
string s;
char t[222222],d[222222];

int simulate(int j){
    for(int i=0;i<q;i++){
        if(t[i]!=s[j])continue;
        if(d[i]=='L')j--;
        else j++;
        if(j==-1)return -1;
        if(j==n)return 1;
    }
    return 0;
}

    
signed main(){
    
    cin>>n>>q>>s;
    rep(i,q)cin>>t[i]>>d[i];
    
    int left=-1;
    int right=n;
    while(right-left>1){
        int mid=(right+left)/2;
        if(simulate(mid)==1)right=mid;
        else left=mid;
    }
    int left2=-1;
    int right2=n;
    while(right2-left2>1){
        int mid=(right2+left2)/2;
        if(simulate(mid)==-1)left2=mid;
        else right2=mid;
    }
    //cout<<right2<<" "<<right<<endl;
	cout<<left-right2+1<<endl;
}

Measured memory_bytes: 1028
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long
int gcd(int a, int b) {
    if (b > a) return gcd(b, a);
    if (b == 0) return a;
    return gcd(b, a % b);
}

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    int ans; cin >> ans;
    rep(i, N - 1) {
        int A; cin >> A;
        ans = gcd(ans, A);
    }
    cout << ans << endl; 

    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <iomanip>
#include <sstream>

using namespace std;
using ll = long long;

// inf
constexpr ll infl = 1LL << 60;
constexpr int inf = 1 << 30;

int P[100][11];

int pcount(int i) {
    int cnt = 0;
    while (i > 0) {
        cnt += i & 1;
        i /= 2;
    }
    return cnt;
}

int main() {
    int N; cin >> N;
    vector<int> F(N);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < 10; ++j) {
            int f; cin >> f;
            F[i] |= f << j;
        }
    }

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= 10; ++j) {
            cin >> P[i][j];
        }
    }

    int ans = -inf;
    for (int i = 1; i < (1 << 10); ++i) {
        int b = 0;
        for (int j = 0; j < N; ++j) {
            b += P[j][pcount(i & F[j])];
        }
        ans = max(ans, b);
    }
    cout << ans << endl;
}

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

int main() {
  string s;
  cin >> s;
  bool ok = true;
  bool res = false;
  while (ok) {
    bool tf = false;
    int len = s.length();
    if (len >= 7 && tf == false) {
      if (s.substr(len - 7, 7) == ("dreamer")) {
        tf = true;
        s = s.substr(0, len - 7);
      }
    }
    if (len >= 6 && tf == false) {
      if (s.substr(len - 6, 6) == ("eraser")) {
        tf = true;
        s = s.substr(0, len - 6);
      }
    }
    if (len >= 5 && tf == false) {
      if (s.substr(len - 5, 5) == ("dream")) {
        tf = true;
        s = s.substr(0, len - 5);
      }
    }
    if (len >= 5 && tf == false) {
      if (s.substr(len - 5, 5) == ("erase")) {
        tf = true;
        s = s.substr(0, len - 5);
      }
    }

    if (!tf) ok = false;
    if (s.length() == 0) {
      res = true;
      break;
    }
  }
  if (res)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}

Measured memory_bytes: 512
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    P = [int(i)-1 for i in input().split()]

    par = [i for i in range(N)]
    rank = [1 for i in range(N)]

    def find_root(x):
        if par[x] == x:
            return x
        else:
            par[x] = find_root(par[x])
            return par[x]

    def is_same_group(x, y):
        return find_root(x) == find_root(y)

    def unite(x, y):
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            x, y = y, x
        rank[x] += rank[y]
        par[y] = x

    def size(x):
        return rank[find_root(x)]

    for i in range(M):
        a, b = (int(i)-1 for i in input().split())
        unite(a, b)

    ans = 0
    for i, p in enumerate(P):
        if is_same_group(i, p):
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 80396
#include<iostream>
using namespace std;
int main(){

  int a,b,c;
  char x;
  int t=0,h=0;

  while(cin>>a>>x>>b>>x>>c){
    if(a*a+b*b==c*c)
      t++;
    if(a==b)
      h++;
  }
  cout << t << endl << h << endl;
}

Measured memory_bytes: 1160