akhauriyash/Code-Regression huggingface dataset:
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

//constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
constexpr long long int MOD = 998244353;
constexpr long double EPS = 1e-8;

long long int N, M, K, L, R, H, W;
//int N, M, K, L, R, H, W;

long long int power(long long int x, long long int n, long long int M) {
	long long int ret = 1;
	long long int by = x;
	while (n) {
		if (n & 1) {
			ret *= by;
			ret %= M;
		}
		by *= by;
		by %= M;
		n >>= 1;
	}
	return ret;
}

class XorShift {
	unsigned int x, y, z, w, t;
public:
	XorShift() {
		x = 133553533;
		y = 314867339;
		z = 664298413;
		w = 999999937;
		t = 0;
	}
	unsigned int rand() {
		t = x ^ (x << 11);
		x = y;
		y = z;
		z = w;
		w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
		return w & 0x7fffffff;
	}
};

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


	string s;
	cin >> N;
	cin >> s;
	bool one = false;
	for (auto i : s) {
		if (i == '2')one = true;
	}
	vector<long long int>two(N + 1, 0);
	for (int i = 2; i <= N; i++) {
		int box = i;
		two[i] = two[i - 1];
		while (box % 2 == 0) {
			box >>= 1;
			two[i]++;
		}
	}
	if (one) {
		long long int ans = 0;
		for (int i = 0; i <= N - 2; i++) {
			int add = two[N - 2] - two[i] - two[N - 2 - i];
			if (abs((int)s[i] - (int)s[i + 1]) % 2 == 1 && !add)ans++;
		}
		if (ans & 1) {
			cout << 1 << endl;
			return 0;
		}
		cout << 0 << endl;
		return 0;
	}
	else {
		long long int ans = 0;
		for (int i = 0; i <= N - 2; i++) {
			int add = two[N - 2] - two[i] - two[N - 2 - i];
			if (abs((int)s[i] - (int)s[i + 1]) == 2 && !add)ans++;
		}
		if (ans & 1) {
			cout << 2 << endl;
			return 0;
		}
		cout << 0 << endl;
		return 0;
	}
}

Measured memory_bytes: 9416
n = int(input())
A = list(map(int, input().split()))

def merge(A, left, mid, right):
    num = 0 # the number of inversion between two subarrays L and R    
    n1 = mid - left
    n2 = right - mid
    L = [0]*(n1+1)
    R = [0]*(n2+1)
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    L[n1] = float("inf")
    R[n2] = float("inf")
    i = 0
    j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            num += n1 - i
            A[k] = R[j]
            j += 1
    return num
            
def merge_sort(A, left, right):
    if not(left + 1 < right):
        num = 0
    else:
        mid = (left + right)//2
        num_left = merge_sort(A, left, mid)
        num_right = merge_sort(A, mid, right)
        num_merge = merge(A, left, mid, right)
        num = num_left + num_right + num_merge
    return num

num = merge_sort(A, 0, n)
print(num)


Measured memory_bytes: 27480
package main

import (
	"fmt"
)

func main() {
	var a, b int
	fmt.Scan(&a, &b)

	if (a+b)%3 == 0 || a%3 == 0 || b%3 == 0 {
		fmt.Println("Possible")
	} else {
		fmt.Println("Impossible")
	}
}


Measured memory_bytes: 512
import math

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

priceA_min = math.ceil(A / 0.08)
priceA_max = math.ceil((A + 1) / 0.08)
priceB_min = math.ceil(B / 0.1)
priceB_max = math.ceil((B + 1) / 0.1)

priceAs = []
if priceA_min != priceA_max:
    price = priceA_min
    while True:
        if price >= priceA_max:
            break
        priceAs.append(price)
        price += 1
else:
    priceAs.append(priceA_min)

priceBs = []
if priceB_min != priceB_max:
    price = priceB_min
    while True:
        if price >= priceB_max:
            break
        priceBs.append(price)
        price += 1
else:
    priceBs.append(priceB_min)

P = False
for i in range(len(priceAs)):
    for j in range(len(priceBs)):
        if priceAs[i] == priceBs[j]:
            print(priceAs[i])
            P = True
            break
    if P == True:
        break
if P == False:
    print(-1)


Measured memory_bytes: 3064
def setM():
    k = K2 // 2
    while k:
        m = int(("1" * (K2 - k) + "0" * (K2 + k)) * 3001, 2)
        M.append((k, m, ~m, (1 << K2 + k) % P))
        k //= 2

def modp(n):
    for k, m, tm, a in M:
        n = (n & tm) + ((n & m) >> K2 + k) * a
    return n

K = 64
K2 = K // 2
P = 998244353
mm = (1 << K * 3001) - 1
mmm = (1 << K) - 1
M = []
setM()
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += 1
    s += s << a * K
    s &= mm
    s = modp(s)
    ans += (s >> S * K) & mmm

print(ans % P)

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

using namespace std;
using ll = long long;

int main(){
  ll h;
  cin >> h;
  cin.ignore();

  // 増殖しない場合

  ll h_cpy = h;
  ll cnt = 0;
  while(h_cpy != 0){
    h_cpy /= 2;
    ++cnt;
  }

  #ifdef DBG
  cout << "cnt = " << cnt << endl;
  #endif

  ll sum = 0;
  ll dam = 1;
  for(ll i = 0; i < cnt; i++){
    #ifdef DBG
    cout << "dam = " << dam << endl;
    #endif
    sum += dam;
    dam *= 2;
  }

  cout << sum << endl;
  return 0;
}


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

using namespace std;

int main(void) {
    string s;
    cin >> s;
    int cnt = 0;
    for (int i = 0; i < s.length(); ++i) {
        if (i < s.length() - 1) {
            if (s[i] != s[i + 1]) cnt++;
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 3764
using System;
using System.Linq;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.ReadLine();
            var arr = Console.ReadLine().Split().Select(s=>int.Parse(s)).ToArray();
            Console.WriteLine(arr.Max()-arr.Min());
        }
    }
}


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


int main(){

    string s;
    int K;
    cin>>s;
    cin>>K;
    set<string>st;
    for(int i=0;i<s.size();i++){
        string str="";
        for(int j=0;j<5 && i+j<s.size();j++){
            str+=s[i+j];
            st.insert(str);
        }
    }
    vector<string>ans;
    for(auto it=st.begin();ans.size()<K;it++){
        ans.push_back(*it);
    }
    cout<<ans[K-1]<<endl;
    
    return 0;
}

Measured memory_bytes: 1664
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define lch a[n].lc
#define rch a[n].rc
using namespace std;
const int mo=998244353;
const int maxn=1e6+10;
int n,root,topt,nt[maxn];
struct da{int lc,rc,ma;}a[4*maxn];
long long dp[maxn];
struct daa{int x,d;}v[maxn];
inline bool cmp(daa aa,daa bb){return aa.x<bb.x;}
void build_tree(int &n,int l,int r)
{
	n=++topt; a[n].ma=-1; if (l==r) return;
	int mid=(l+r)>>1;
	build_tree(lch,l,mid); build_tree(rch,mid+1,r);
}
inline void updata(int n){a[n].ma=max(a[lch].ma,a[rch].ma);}
void tree_add(int n,int l,int r,int lc,int k)
{
	if (l==r) {a[n].ma=k; return;}
	int mid=(l+r)>>1;
	if (lc<=mid) tree_add(lch,l,mid,lc,k);else tree_add(rch,mid+1,r,lc,k);
	updata(n);
}
int qury(int n,int L,int R,int l,int r)
{
	if (L==l && R==r) return a[n].ma;
	int mid=(L+R)>>1;
	if (r<=mid) return qury(lch,L,mid,l,r);
	else if (l>=mid+1) return qury(rch,mid+1,R,l,r);
	else return max(qury(lch,L,mid,l,mid),qury(rch,mid+1,R,mid+1,r));
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d",&v[i].x,&v[i].d);
	sort(v+1,v+n+1,cmp); build_tree(root,1,n);
	for (int i=n;i>=1;i--)
	{
		int l=i+1,r=n,lc=-1;
		while (l<=r)
		{
			int mid=(l+r)>>1;
			if (v[mid].x<v[i].x+v[i].d) {lc=max(lc,mid); l=mid+1;}else r=mid-1;
		}
		if (lc==-1) nt[i]=i;else nt[i]=qury(root,1,n,i+1,lc);
		tree_add(root,1,n,i,nt[i]);
	}
	dp[n+1]=1;
	for (int i=n;i>=1;i--) dp[i]=(dp[i+1]+dp[nt[i]+1])%mo;
	printf("%lld\n",dp[1]);
return 0;
}
/*
3
-1 10
3 3
6 5
*/

Measured memory_bytes: 14080
#include <bits/stdc++.h>
#define rep(i,a,n)  for (int i=(int)(a); i<=(int)(n); ++i)
#define rrep(i,a,n) for (int i=(int)(a); i>=(int)(n); --i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) rep(i, x.size()) cerr << x[i] << (i == x.size() - 1 ? "\n" : " ")
#define all(x) x.begin(),x.end()
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = ((1LL << 30) + (1LL << 29));
const int MOD = 1000000007;

//=============================
int N,M,K;
string S,T;
vector<int> A;
vector<int> B;
//=============================
void input()
{
    cin>>N>>M;

}
//=============================
void func(){}
bool pal(int i){
    debug(i);
    bool ret=true;
    for(int ketasu=4; ketasu; ketasu -= 2){
        int l = i/pow(10,ketasu);
        // debug(ketasu);
        // debug(l);
        // debug(i%10);
        if (i%10 != (int)(i/pow(10,ketasu))){
            return false;
        }
        i -= l*pow(10,ketasu);
        i /= 10;
        //debug(i);
    }
    return ret;
}
//=============================
void solve()
{
    int ans = 0;
    rep(i,N,M){
        if (pal(i))ans++;
    }
    cout<<ans<<endl;

}
//=============================
signed main()
{
    input();
    solve();
    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

################ DANGER ################
test = ""
test = \
"""

"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################  
        
n = int(input2())

def primes(n):
    ps = [2]
    for odd in range(3, n + 1, 2):
        for p in ps:
            if odd % p == 0:
                break
            if p ** 2 > odd:
                ps.append(odd)
                break
    return ps


def isprime(n):
    last = int(n**.5)
    for m in primes(last):
        if n % m == 0:
            return False
    return True


if n in primes(n):
    print(n)
else:
    i = n
    while not isprime(i):
        i += 1
    print(i)




Measured memory_bytes: 3304
//2017-10-19
//miaomiao
//I lack delicious yogurt
//
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
#define For(i, a, b) for(int i = (a); i <= (int)(b); ++i)
#define N (100+5)

int a[N], tot[N];

int main(){
	int n;

	scanf("%d", &n);
	For(i, 1, n) scanf("%d", &a[i]);
	
	sort(a+1, a+n+1);
	if(a[n] != a[n-1] || a[1] < (a[n]+1)/2){puts("Impossible"); return 0;}
	For(i, 1, n) ++tot[a[i]];
	
	int mn = (a[n]+1) / 2;
	if(!(a[n] & 1) && tot[mn] != 1){puts("Impossible"); return 0;}
	if( (a[n] & 1) && tot[mn] != 2){puts("Impossible"); return 0;}

	For(i, mn+1, a[n]) if(tot[i] < 2){
		puts("Impossible"); return 0;
	}
	
	puts("Possible");

	return 0;
}

Measured memory_bytes: 256
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;

const ll max_n = 100000;
ll par[max_n];
ll rnk[max_n];

void init(ll n){
  REP(i,n){
    par[i] = i;
    rnk[i] = 0;
  }
}

ll find(ll x){
  if(par[x]==x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(ll x, ll y){
  x = find(x);
  y = find(y);
  if(x==y) return;
  if(rnk[x]<rnk[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(rnk[x]==rnk[y]) rnk[x]++;
  }
}

bool same(ll x, ll y){
  return find(x)==find(y);
}

ll num[max_n];

int main(){
  ll n,m;
  cin >> n >> m;
  REP(i,n){
    ll p;
    cin >> p;
    num[p-1]=i;
  }
  init(n);
  REP(i,m){
    ll x,y;
    cin >> x >> y;
    unite(x-1,y-1);
  }
  ll ans = 0;
  REP(i,n){
    if(find(i)==find(num[i])) ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;


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

    int H,M;
    cin >> H >> M;
    char a[H][M];
    rep(i,H){
        rep(j,M){
            cin >> a[i][j];
        }
    }
    bool z[H]={},z1[M]={};
    rep(i,H){
        rep(j,M){
            if(a[i][j]=='#') {
                z[i]=true;
                z1[j]=true; 
            }
        }
    }
    rep(i,H){
        if(z[i]){
            rep(j,M){
                if(z1[j]){
                    cout << a[i][j];
                }
            }
            cout << endl;
        }
    }


}


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

using namespace std;

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

    int a[M], b[M];
    pair<int, int> c[M];
    for(int i=0; i<M; i++){
        cin >> a[i] >> b[i];
        int k = 0;
        for(int j=0; j<b[i]; j++){
            int t;
            cin >> t;
            t--;
            k |= 1<<t;
        }
        c[i] = make_pair(k, a[i]);
    }

    int dp[(1<<N)+1];
    const int inf = 1000000005;
    for(int j=0; j<(1<<N); j++){
        dp[j] = inf;
    }
    dp[0] = 0;

    for(int i=0; i<(1<<N); i++){
        for(int j=0; j<M; j++){
            int k = c[j].first | i;
            dp[k] = min(dp[k], dp[i]+c[j].second);
        }
    }

    if(dp[(1<<N)-1] == inf) cout << -1 << endl;
    else cout << dp[(1<<N)-1] << endl;

    return 0;
}

Measured memory_bytes: 256
N, L = map(int, input().split())
ll = []
l = []
a = 0
for i in range(L, L+N):
    ll.append(i)
    if i < 0 :
        i = -i
        a = 1
    l.append(i)

minl = min(l)
if a == 1 :
    minl = -minl
    print(sum(ll)-minl)
else :
    print(sum(ll)-minl)

Measured memory_bytes: 3064
n, m = map(int, input().split())
a = [(1, int(x)) for x in input().split()]

for i in range(m):
    x, y = map(int, input().split())
    a.append((x, y))

a.sort(key=lambda x:x[1], reverse=True)
res = 0

for j, k in a:
    while j > 0 and n > 0:
        res += k
        j -= 1
        n -= 1
print(res)


Measured memory_bytes: 31960
n, a, b = gets.split.map(&:to_i)
na = 0
nb = 0
gets.chomp.each_char{|c|
  if case c
  when "a"
    if na + nb < a + b
      na += 1
      true
    else false end
  when "b"
    if na + nb < a + b && nb < b
      nb += 1
      true
    else false end
  else
    false
  end then
    puts "Yes"
  else
    puts "No"
  end
}


Measured memory_bytes: 2428
n,m,q=map(int,input().split())
def dfs(seq):
    u=0
    if len(seq)==n:
        ans=0
        for a,b,c,d in data:
            if seq[b-1]-seq[a-1]==c:
                ans+=d
        return ans
    else:
        for i in range(seq[-1],m+1):
            seq_next=seq.copy()
            seq_next.append(i)
            u=max(u,dfs(seq_next))
        return u

data=[]
for _ in range(q):
    A=list(map(int,input().split()))
    data.append(A)
print(dfs([1]))


Measured memory_bytes: 9196
import java.util.*;
 
class Main{
    public static void main(String[] args){
		
		Scanner scan = new Scanner(System.in);
		int c = scan.nextInt();
		int r = scan.nextInt();
		int[][] arr1 = new int[c][r];
		int[][] arr2 = new int[c+1][r+1];
		int sum = 0;
		//???????????????
		for(int i=0; i<c; i++){
			for(int j=0; j<r; j++){
				int p = scan.nextInt();
				arr1[i][j] = p;
				arr2[i][j] = p;
			}
		}
		//??????????¨????????´?
		for(int i=0; i<c; i++){
			for(int j=0; j<r; j++){
				sum += arr2[i][j];
			}
			arr2[i][r] = sum;
			sum = 0;
		}
		//??????????¨????????´?
		for(int i=0; i<r+1; i++){
			for(int j=0; j<c; j++){
				sum += arr2[j][i];
			}
			arr2[c][i] = sum;
			sum = 0;
		}
		//???????????????
		for(int i=0; i<c+1; i++){
			for(int j=0; j<r+1; j++){
				System.out.print(arr2[i][j]);
				if(j < r){
				System.out.print(" ");
				}
			}
			System.out.println("");
		}
    }
}

Measured memory_bytes: 42540
#include<stdio.h>
int main() {
  int sp = 0, a, data[11] = {0};
  while(scanf("%d", &a) != EOF) {
    if(a == 0) {
      printf("%d\n", data[sp]);
      sp--;
    }else {
      sp++;
      data[sp] = a;
    }
  }
  return 0;  
}

Measured memory_bytes: 600
N = gets.to_i
# 1 3 5 7 15 21 35 105
# 1 3 5 9 15 27 45 135
#1は確定
# ~17で３つ選ぶ
arr = []
[3, 5, 7, 9, 11, 13].combination(3){|a,b,c| arr<<[a,b,c] }
count = 0
for i in 0..arr.length-1 do
  all = arr[i][0]*arr[i][1]*arr[i][2]
  if all <= N
    count += 1
  end
end

puts count

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

ll n,p,ans,cur,cnt[10010],i,t=1;
string s;
int main(){
    cin>>n>>p>>s;
    if(p==2 || p==5){
        for(int i=0;i<n;i++)
            if((s[i]-'0')%p==0) ans+=i+1;
    }
    else{
        cnt[0]=1;
        for(int i=n-1;i>=0;i--){
            cur=(cur+(s[i]-'0')*t)%p;
            ans+=cnt[cur]++;
            t=t*10%p;
        }
    }
    cout<<ans;
	return 0;
}


Measured memory_bytes: 644
#include<stdio.h>

int main(){
	int i,c,a,n,q,ans;
	scanf("%d",&q);
	while(q--){
		ans=0;
		scanf("%d%d%d",&c,&a,&n);
		while(1){
			if(c>0 && a>0 && n>0){
				c--;a--;n--;
			}
			else if(c>1 && a>0){
				c-=2;a--;
			}
			else if(c>2)c-=3;
			else break;
			ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 600
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
    int a,b,k;
    cin>>a>>b>>k;
    int waru[100],kazu;
    kazu=0;
    for(int i=min(a,b);i>=1;i--){
        if(a%i==0&&b%i==0){
            kazu++;
            waru[kazu]=i;
        }
    }
    cout<<waru[k]<<endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <iostream>
#include <random>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

using std::cin;
using std::cerr;
using std::cout;
using std::endl;
using std::make_pair;
using std::pair;
using std::stack;
using std::string;
using std::unordered_set;
using std::vector;
using std::lower_bound;
using std::upper_bound;

int main(int argc, char* argv[]) {
  vector<int> a(9);
  for (int j = 0; j < 9; ++j) {
    cin >> a[j];
  }
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    int b;
    cin >> b;
    for (int j = 0; j < 9; ++j) {
      if (a[j] == b) {
        a[j] = 0;
      }
    }
  }

  for (int i = 0; i < 3; ++i) {
    if ((a[i * 3] == 0 && a[i * 3 + 1] == 0 && a[i * 3 + 2] == 0)
        || (a[i] == 0 && a[i + 3] == 0 && a[i + 6] == 0)) {
      cout << "Yes";
      return 0;
    }
  }
  if ((a[0] == 0 && a[4] == 0 && a[8] == 0) || (a[2] == 0 && a[4] == 0 && a[6] == 0)) {
    cout << "Yes";
    return 0;
  }
  cout << "No";

  return 0;
}


Measured memory_bytes: 256
def run(N, M, A):
    '''
    Aiが10^5なので、searchを以下に変えられる
    サイズ10**5のリストで、その満足度を持つ数の件数を事前計算しておけばO(1)で求められる
    '''
    A = sorted(A, reverse=True)
    cnt_A = [len(A)]
    pre_a = 0
    cnt_dict_A = {}
    for a in sorted(A):
        cnt_dict_A[a] = cnt_dict_A.get(a, 0) + 1
    next_cnt = cnt_A[-1]
    for a in sorted(cnt_dict_A.keys()):
        cnt_A.extend([next_cnt]*(a-pre_a))
        pre_a = a
        next_cnt = cnt_A[-1]-cnt_dict_A[a]
    right = A[0] * 2
    left = 0
    while left <= right:
        X = (left + right) // 2
        # 左手の相手がaで、満足度がX以上となる組合せの数
        cnt = 0
        for a in A:
            # cnt += search(A, X - a)
            if X - a <= A[0]:
                if X - a >= 0:
                    cnt += cnt_A[X - a]
                else:
                    cnt += cnt_A[0]
        if cnt >= M:
            res = X
            left = X + 1
        else:
            right = X - 1
    X = res
    # Xが決まったので、累積和で組合せの数分の値を求める
    sum_A = [0]
    for a in sorted(A):
        sum_A.append(sum_A[-1] + a)
    sum_cnt = 0
    ans = 0
    for a in A:
        cnt = search(A, X - a)
        sum_cnt += cnt
        if cnt > 0:
            ans += cnt * a + sum_A[-1] - sum_A[-cnt-1]
    if sum_cnt > M:
        ans -= X * (sum_cnt - M)
    return ans


def search(A, X):
    '''
    AのリストからX以上となる数値がいくつか探す
    Aはソート済み(降順)
    二分探索で実装O(logN)
    leftとrightはチェック未
    middleはループ終了後チェック済み
    '''
    left = 0
    right = len(A) - 1
    res = 0
    while left <= right:
        middle = (left + right) // 2
        if A[middle] >= X:
            res = middle + 1
            left = middle + 1
        else:
            right = middle - 1
    return res


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    print(run(N, M, A))


if __name__ == '__main__':
    main()


Measured memory_bytes: 23628
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
const double PI=3.14159265358979323846;
const in MOD = 1000000007;
const in INF=1<<30;
using P=pair<int,int>;
vector<int> dx={0,1,-1,0};
vector<int> dy={1,0,0,-1};

vector<int> par(0);
vector<int> depth(0);
void init(int n){
   par.resize(n);
   depth.resize(n,0);
   rep(i,n) par[i]=i;
}

int find(int n){
   if(par[n]==n) return n;
   return par[n]=find(par[n]);
}

void unite(int x,int y){
   x=find(x);
   y=find(y);
   if(par[x]==par[y]) return;
   if(depth[x]<depth[y]) par[x]=par[y];
   else{
      par[y]=par[x];
   if(depth[x]==depth[y]) depth[x] ++;
   }
}

bool same(int x,int y){
   return find(x)==find(y);
}

int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(10);
    int n,k,l;
    cin>>n>>k>>l;
    init(n);
    int p,q;
    rep(i,k){
       cin>>p>>q;
       p --;
       q --;
       unite(p,q);
    }
    vector<P> x(n);
    rep(i,n) x[i].first=find(i);
    init(n);
    rep(i,l){
       cin>>p>>q;
       p --;
       q --;
       unite(p,q);
    }
    rep(i,n) x[i].second=find(i);
    map<P,int> z;
    rep(i,n){
      if(!z.count(x[i])) z[x[i]]=1;
      else z[x[i]] ++;
    }
    rep(i,n) cout<<z[x[i]]<<" ";

}

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

int main() {
  int X;
  cin >> X;
  int a = X%100;
  int b = a/5 + ((a%5==0) ? 0:1);
  int c=X/100;
//  cout << a << " " << b << " " << c << endl;
  if (c>=b)
    cout << "1" << endl;
  else
    cout << "0" << endl;

}


Measured memory_bytes: 256
#pragma warning(disable:4996)
#include <bits/stdc++.h>

using namespace std;

//macro
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) FOR(i,0,n)
#define each(i, ctn) for (auto &&i : (ctn))
#define all(a) (a).begin(),(a).end()
#define EPS (1e-8)
#define equals(a,b)(fabs((a)-(b))<EPS)

using ll = long long;
using ull = unsigned long long;
using vb = vector<bool>;
using vi = vector<int>;
using vll = vector<ll>;
using vs = vector<string>;
using vvb = vector<vb>;
using vvi = vector<vi>;
using vvll = vector<vll>;
//func
template<typename A, typename T>void assign2d(A&arr, ll H, ll W, T t) { arr.resize(H); REP(i, H) arr[i].assign(W, t); }
template<class T> ostream &operator<<(ostream &os, const vector<T> &v) { int n = v.size(); REP(i, n)os << v[i] << (i == n - 1 ? "" : " "); return os; }
template <class T = int> inline T IN() { T x; cin >> x; return x; }
template<class T> inline void OUT(const T &x) { cout << x << "\n"; }
struct pre_ { pre_() { cin.tie(nullptr); ios::sync_with_stdio(false); /*cout << fixed << setprecision(12);*/ } } pre__;


bool IsPrime(int num)
{
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false;
	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			return false;
		}
	}
	return true;
}

template<class T = int>
struct CumulativeSum1D
{
	vector<T> data;
	CumulativeSum1D(int N) { data.resize(N + 1); }
	inline void add(int i, T x)
	{
		data[i] += x;
	}

	void build()
	{
		for (int i = 1; i < data.size(); i++) {
			data[i] += data[i - 1];
		}
	}

	inline T query(int i, int j) { return data[j] - data[i - 1]; }
};

int main() {
	int Q;
	cin >> Q;
	vb x(100010);
	vi c(100010, 0);
	CumulativeSum1D<> cs1d(100010);
	REP(i, 100001) {
		x[i] = IsPrime(i);
	}
	//cs1d.add(2, 1);
	cs1d.add(3, 1);
	REP(i, 25000) {
		if (x[1 + 4 * i] && x[(2 + 4 * i) / 2]) {
			cs1d.add(1 + 4 * i, 1);
		}
	}

	cs1d.build();
	REP(i, Q) {
		int l, r;
		cin >> l >> r;
		OUT(cs1d.query(l, r));
	}
	return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<ll, ll>>;
// ceil() 切り上げ, floor() 切り捨て
// next_permutation(all(x))

int		main(void)
{
	string n;
	cin >> n;
	int ans = 0;
	for (int i = 0; i < 4; i++)
	{
		if (n[i] == '2')
			ans++;
	}
	cout << ans << endl;
}



Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
d=dict()
for i in range(n):
  if a[i] not in d:
    d[a[i]]=1
  else:
    d[a[i]]+=1
d=sorted(list(d.items()))
if n%2:
  for i in range(len(d)):
    if i==0:
      if d[i][0]!=0 or d[i][1]!=1:
        print(0)
        exit()
    else:
      if d[i][0]!=i*2 or d[i][1]!=2:
        print(0)
        exit()
  print(pow(2,len(d)-1,mod))
else:
  for i in range(len(d)):
    if d[i][0]!=2*i+1 or d[i][1]!=2:
      print(0)
      exit()
  print(pow(2,len(d),mod))

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

#define FOR(i,a,b) for(int i=(a);i<(int)(b);i++)
#define rep(i,n) FOR(i,0,n)
#define SZ(x) (int)(x).size()
#define pb push_back

typedef vector<int> vint;

bool search(vint v, int x) {
    for(auto& i : v) if(i == x) return true;
    return false;
}

bool OK(vint p, vint l) {
    if(SZ(p) < SZ(l)) return false;
    for(auto& li : l) {
        if(search(p, li)) continue;
        return false;
    }
    return true;
}

void solve(int n) {
    vector<vector<int>> ps;
    rep(i,n) {
        int m; cin>>m;
        vector<int> p(m);
        rep(i,m) cin>>p[i];
        ps.pb(p);
    }
    int k; cin>>k;
    vector<int> l(k);
    rep(i,k) cin>>l[i];

    int cnt=0, ans=0;
    rep(i,n) {
        if(OK(ps[i], l)) {
            cnt++;
            ans = i+1;
        }
    }
    cout << (cnt==1 ? ans : -1) << "\n";
}

int main() {
    for(int n; cin>>n && n; ) solve(n);
    return 0;
}

Measured memory_bytes: 3192
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define mod 1000000007
#define pb emplace_back
#define mp make_pair
#define fi first
#define sec second
typedef long long ll;
typedef long double  ld;
#define pii pair<ll,ll> 
#define vi vector< ll > 
#define vvi vector< vi > 
#define vpi vector< pii > 
#define vvpi vector< vpi > 
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define test(t) ll t;cin>>t;while(t--)
#define mem(a,b) memset(a,b,sizeof(a))
#define inn freopen("input.txt", "r", stdin)
#define outt freopen("output.txt", "w", stdout)
#define all(arr) arr.begin(),arr.end()
#define fr(i,n) for(ll i=0;i<(n);++i)
#define rep(i,a,b) for(ll i=a;i<=b;++i)
#define per(i,a,b) for(ll i=a;i>=b;i--)
#define remin(a,b) (a=min((a),(b)))
#define remax(a,b) (a=max((a),(b)))
#ifndef ONLINE_JUDGE
#define debarr(a,n)cerr<<#a<<":";for(int i=0;i<n;i++)cerr<<a[i]<<" ";cerr<<endl;
#define debmat(mat,row,col)cerr<<#mat<<":\n";for(int i=0;i<row;i++){for(int j=0;j<col;j++)cerr<<mat[i][j]<<" ";cerr<<endl;}
#define pr(...)dbs(#__VA_ARGS__,__VA_ARGS__)
template<class S,class T>ostream &operator<<(ostream &os,const pair<S,T> &p){return os<<"("<<p.first<<","<<p.second<<")";}
template<class T>ostream &operator<<(ostream &os,const vector<T> &p){os<<"[";for(auto&it:p)os<<it<<" ";return os<<"]";}
template<class T>ostream &operator<<(ostream &os,const set<T>&p){os<<"[";for(auto&it:p)os<<it<<" ";return os<<"]";}
template<class T>ostream &operator<<(ostream &os,const multiset<T>&p){os<<"[";for(auto&it:p)os<<it<<" ";return os<<"]";}
template<class S,class T>ostream &operator<<(ostream &os,const map<S,T>&p){os<<"[";for(auto&it:p)os<<it<<" ";return os<<"]";}
template<class T>void dbs(string str,T t){cerr<<str<<":"<<t<<"\n";}
template<class T,class...S>void dbs(string str,T t,S... s){int idx=str.find(',');cerr<<str.substr(0,idx)<<":"<<t<<",";dbs(str.substr(idx+1),s...);}
#else
#define pr(...){}
#define debarr(a,n){}
#define debmat(mat,row,col){}
#endif
ll power(ll x,ll y){ll res = 1;while(y){if(y&1) res = (res*x)%mod;y=y/2,x=(x*x)%mod;}return res%mod;}
signed main()
{
    fast;
    ll n;
    cin>>n;
    ll freq[26] = {0};
    string s;
    cin>>s;
    for(auto v:s)
        freq[v-'a']++;
    ll ans = 1;
    for(ll i=0;i<26;i++)
    {
        ans = (ans*(freq[i]+1))%mod;
    }
    ans = (ans+mod-1)%mod;
    cout<<ans;
    
}


Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <vector> //動的配列
#include <string>
#include <list> //双方向リスト
#include <map> //連想配列
#include <set> //集合
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <bitset>
#include <numeric>



typedef long long ll;


using namespace std;

typedef pair<int, int> P;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)



ll fast_pow(ll x,ll n,ll mod){
    if (n==0) return 1;
    ll res=fast_pow(x*x %mod,n/2,mod);
    if (n&1) res=res*x%mod;
    return res;
}

template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

//小さい順から取り出すヒープ
//priority_queue<ll, vector<ll>, greater<ll> > pque1;




int main(){
    ll c,r,x,y; //列の横と縦
    cin>>c>>r>>x>>y;
    bool check=false;
    if (2*x==c && 2*y==r) check=true;
    double sq;
    sq=(double)c*(double)r/2;
    printf("%9f",sq);
    if (check) cout<<' '<<1<<endl;
    else cout<<' '<<0<<endl;
    
    
}

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


int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	string s;
	cin >> s;
	
	int ans = 0;
	for (int i = 0; i < s.size(); ){
		if (s[i] == 'R'){
			int j = i;
			while (j < s.size() && s[j] == 'R') j++;
			ans = max(ans,j - i);
			i = j;	
		}
		else i++;	
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
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)

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

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

const int MAX = 200005;
const int INF = 1001001001;
const int MOD = 998244353;

struct mint {
    long long x;
    mint(long long x=0):x(x % MOD + (0 <= x ? 0 : MOD)) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint& a) { if ((x += a.x) >= MOD) x -= MOD; return *this; }
    mint& operator-=(const mint& a) { if ((x -= a.x) < 0) x += MOD; return *this; }
    mint& operator*=(const mint& a) { (x *= a.x) %= MOD; return *this; }
    mint operator+(const mint& a) const { return mint(x) += a; }
    mint operator-(const mint& a) const { return mint(x) -= a; }
    mint operator*(const mint& a) const { return mint(x) *= a; }

    // for prime mod
    mint inv() const {
        long long a = x, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        return mint(u);
    }
    mint& operator/=(const mint& a) { return *this *= a.inv(); }
    mint operator/(const mint& a) const { return mint(x) /= a; }
};
istream& operator>>(istream& is, const mint& a){ return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a){ return os << a.x; }

struct Combination{
    vector<long long> fac, finv, inv;
    Combination(int n=1001001):fac(n+1), finv(n+1), inv(n+1) {
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1] = 1;
        for (int i = 2; i <= n; 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 operator()(int n, int k) const {
        if (n < k || n < 0 || k < 0) return 0;
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
    }
};

long long mod_pow(long long x, long long n, int M=998244353) {
    long long ret = 1;
    while(n) {
        if(n & 1) (ret *= x) %= M;
        (x *= x) %= M;
        n >>= 1;
    }
    return ret;
}

int main(){
    int N, M, K;
    cin >> N >> M >> K;

    Combination c;

    mint ans = 0;
    rep(i, K+1) {
        if (i == 0) {
            ans += (ll)M * mod_pow(M-1, N-1) % MOD;
        } else {
            mint res = 1;
            res *= (ll)M * mod_pow(M-1, N-1-i) % MOD;
            res *= c(N-1, i);
            ans += res;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 26716
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <iomanip>
#include <complex>
#include <bitset>
#include <stack>
 
using namespace std;
 
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f3f3f3f3fLL
#define SIZE 200105
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
 
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
typedef pair<int,ll> pill; typedef pair<ll,int> plli; 
typedef pair<double, int> pdi;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
typedef complex<double> P;
//ll MOD = 1000000007;
ll MOD=998244353;
typedef ll Weight;
struct Edge {
	int src, dst;
	Weight weight;
};
bool operator < (const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
	e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;

int main(){
	int a[4];
	rep(i,4)cin>>a[i];
	sort(a,a+4);
	if(a[0]==1&&a[1]==4&&a[2]==7&&a[3]==9)cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	
}

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

int main(){
  int n,k;
  cin >> n >> k;
  vector<int>A(n);
  
  rep(i,n)cin >> A[i];
  
  rep(ki,k){
    vector<int>B(n + 1);
    rep(i,n){
      int l = max(0,i - A[i]);
      int r = min(n,i + A[i] +1);
      B[l]++;B[r]--;
    }
    rep(i,n)B[i+1]+=B[i];
    B.pop_back(); //これしないと範囲外が残る
    if(A == B)break;
    A = B;
    
  }
  rep(i, n)cout << A[i] << " ";
  cout << endl;
}

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

int main(){
  int n, d, x;
  cin >> n >> d >> x;
  int ret=x;
  for(int i=0; i<n; i++){
    int a;
    cin >> a;
    if(a*(d/a)==d)ret+=d/a;
    else ret+=(d/a+1);
  }
  cout << ret;
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
 
int main(void) {
    int input, ans = 0, ans2 = 234, ans3 = 567, flag;
    cin >> input;
 
    vector<int> side(input);
    for (int i = 0; i < input; i++) {
        cin >> side.at(i);
    }
 
    sort(side.begin(), side.end());
    reverse(side.begin(), side.end());
 
    vector<int> num;
    num.push_back(0);
    for (int i = 0; i < input; i++) {
        flag = 0;
        for (int j = i + 1; j < input; j++) {
            for (int k = j + 1; k < input; k++) {
                if (side.at(i) < side.at(j) + side.at(k) && side.at(j) < side.at(k) + side.at(i) && side.at(k) < side.at(i) + side.at(j)) {
                    ans++;
                    ans2++;
                  	ans3++;
                }
                else {
                    break;
                    flag++;
                }
            }
            if (flag != 0) {
                break;
            }
        }
    }
 
    cout << ans << endl;
 
}


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

int main() {
	long long int a, b, c,k;
	cin >> a >> b >> c >> k;

	if (k <= a) {
		cout << k << endl;
	}
	else if (k>a && k <= a+b) {
		cout << a << endl;
	}else if(k > a+b){
		cout <<  a - (k-a-b) << endl;
	}

	return 0;
}


Measured memory_bytes: 3584
#include<vector>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef vector<int> vi;

bool ck2(vi h){
	rep(i,9){
		if(h[i+1]>2)h[i+1]-=3;
		while(h[i]>0){
			h[i]--; h[i+1]--; h[i+2]--;
			if(h[i+1]<0||h[i+2]<0)return 0;
		}
	}
	return 1;
}
bool ck(vi h){
	bool suc;
	rep(pr,9){
		if(h[pr+1]>1){
			h[pr+1]-=2;
			suc=ck2(h);
			h[pr+1]+=2;
			if(suc)return 1;
		}
	}
	return 0;
}
int main(){
	char buf[20];
	while(cin>>buf){
		vi hand(14); bool flag=0;
		rep(i,13)hand[buf[i]-'0']++;
		
		rep(ad,9){
			if(hand[ad+1]>3)continue;
			hand[ad+1]++;
			if(ck(hand)){
				if(flag)cout<<" ";
				cout<<ad+1;
				flag=1;
			}
			hand[ad+1]--;
		}
		if(!flag)cout<<0<<endl;
		else cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<string>
using namespace std;
int main(){
    int n;
    while(cin >> n, n){
        int l = 0, r = 0;
        int ans = 0;
        int c = 0;
        for(int i = 0; i < n; i++){
            string s;
            cin >> s;
            if(s == "lu"){
                l++;
            }
            if(s == "ru"){
                r++;
            }
            if(s == "ld"){
                l--;
            }
            if(s == "rd"){
                r--;
            }
            if(l == r && c != l){
                c = 1 - c;
                ans++;
            }
        }
        cout << ans << endl;
    }
}



Measured memory_bytes: 3140
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
#define pb push_back
#define vi vector<int >
#define vii vector < pair<int ,int > >
#define IO ios::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0)
#define IOfiles freopen("input.txt","r+",stdin) ; freopen("output.txt","w+",stdout)
#define PI 3.14159265
const long long mod = 1e9 + 7LL;
typedef long long ll;
typedef pair<int, int> ii;
typedef double db;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;}
ll pwr(ll x , ll n) { ll ans = 1; while (n) {ans *= x; n--;} return ans;}

void solve(){
    
}

int main()
{
    IO;
    ll n,k;
    cin>>n>>k;
    ll ans=0LL;
    ll sum=0LL;
    for(ll i=k;i<=n+1;i++){
        sum=((i-1)*i)/2;
        ll temp=i*n-2*sum+1;
        //cout<<i<<" "<<sum<<" "<<temp<<endl;
        temp%=mod;
        ans+=temp;
        ans%=mod;
    }
    cout<<ans<<endl;
    
}   

Measured memory_bytes: 3652
n=int(input())

from numpy import array

i=0
o=array([0,0,0])
while i<n:
   c=list(map(int,input().split()))
   z=array(c)
   w=z-o
   a,b=map(int,[w[0],abs(w[1])+abs(w[2])])

   if a<b:
       print("No")
       break

   else:
       if (a+b)%2==0:
           o=z
           i=i+1
       else:
           print("No")
           break
else:
    print("Yes")


Measured memory_bytes: 12504
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

int readint() { return readln.chomp.to!int; }
int[] readints() { return readln.split.map!(to!int).array; }

void calc(string s) {
    int a = s[0] - '0';
    int b = s[1] - '0';
    int c = s[2] - '0';
    int d = s[3] - '0';

    int reduce(int lhs, int rhs, int op) {
        return op == 0 ? lhs + rhs : lhs - rhs;
    }
    char op(int op) {
        return op == 0 ? '+' : '-';
    }

    for (int i = 0; i < 2; i++) {
        int x = reduce(a, b, i);
        for (int j = 0; j < 2; j++) {
            int y = reduce(x, c, j);
            for (int k = 0; k < 2; k++) {
                int z = reduce(y, d, k);
                if (z == 7) {
                    // writeln(a, op(i), b, op(j), c, op(k), d, "=7");
                    writefln("%s%s%s%s%s%s%s=7", a, op(i), b, op(j), c, op(k), d);
                    return;
                }
            }
        }
    }
}

void main() {
    auto s = readln.chomp;
    calc(s);
}

Measured memory_bytes: 256
#include <iostream>
#include <string> 
#include <vector> 
#include <algorithm> 
#include <utility> 
#include <tuple> 
#include <cstdint> 
#include <cstdio> 
#include <map> 
#include <queue> 
#include <set> 
#include <stack> 
#include <deque> 
#include <unordered_map> 
#include <unordered_set> 
#include <bitset> 
#include <cctype> 
#include<math.h>
using namespace std;

//#define int long long
#define endl "\n"
#define fir first
#define sec second
#define fro front
#define m_p make_pair
#define mod 1000000007
#define all(v)  v.begin(),v.end()
#define rep(i,n)  for(int i=0; i<(int) (n); i++)
#define all(v)  v.begin(),v.end()
#define vecin(v) for(int i=0; i<(int)v.size(); i++)cin>>v[i];
using namespace std;

const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
int jousu(int x00, int y00) {
	int z00 = 1;
	for (int i = 0; i < y00; i++) {
		z00 *= x00;
	}
	return z00;
}
int keta(int x00) {
	int z00 = x00;
	int w00 = 0;
	while (z00 != 0) {
		z00 /= 10;
		w00++;
	}
	return w00;
}

int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
int modpow(int a, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) res* a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
int gcd(int xx, int yy) {
	int p = xx;
	int q = yy;
	if (q > p)swap(p, q);
	while (p % q != 0) {
		p %= q;
		swap(p, q);
	}
	return q;
}
int lcm(int xx, int yy) {
	return xx * yy / gcd(xx, yy);
}
bool prime(int xx) {
	int a = xx;
	for (int i = 2; i * i <= xx; i++) {
		if (xx % i == 0) {
			return 0;
		}
	}
	return 1;
}
int com(int xx, int yy) {
	int zz = 1;
	for (int i = xx; i > xx - yy; i--) {
		zz *= i;
		zz %= mod;
	}
	for (int i = 1; i <= yy; i++) {
		zz *= modinv(i, mod);
		zz %= mod;
	}
	return zz;
}

int a, n, x, t, c = 1;

int main() {
	cin >> n >> x;
	rep(i, n) {
		cin >> a;
		t += a;
		if (t > x) {
			break;
		}
		c++;
	}
	cout << c << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define sz size
#define se second
#define fe first
#define mper make_pair
#define all(x) x.begin(), x.end()
#define mal ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
#define vl vector<ll>
#define vi vector<int>
#define vli vector <pair <ll, int> >
#define vll vector <pair <ll, ll> >
#define vii vector <pair <int, int> >
using namespace std;

const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 100;
ll n, a[MAXN], pos[MAXN], dp[MAXN];

void compress() {

    vector <ll> g;

    for(int i = 1; i <= n; ++i) {

        if(a[i] != a[i - 1]) {g.pb(a[i]);}

    }

    n = g.sz();

    for(int i = 1; i <= n; ++i) {

        a[i] = g[i - 1];
        pos[a[i]] = i;
    }

}

void solve() {


    cin >> n;

    for(int i = 1; i <= n; ++i) {

        cin >> a[i];

    }

    compress();

    dp[0] = 1;

    for(int i = 1; i <= n; ++i) {

        dp[i] = (dp[i] + dp[pos[a[i]]] + dp[i - 1]) % MOD;
        pos[a[i]] = i;
    }

    cout << dp[n];

}

int main(){

mal
//freopen("ladder.in", "r", stdin);
//freopen("ladder.out", "w", stdout);

ll tt = 1;


while(tt--) {

    solve();

}

return 0;
}



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

using namespace std;
 
/// ----------------------------- (Debug) ------------------------------
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; }; sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...);
struct debug {
#ifndef ONLINE_JUDGE
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i));}
sim, class b dor(pair < b, c > d) {ris << "(" << d.first << ", " << d.second << ")";}
sim dor(rge<c> d) {*this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]";}
#else
sim dor(const c&) { ris; }
#endif
};
vector<char*> tokenizer(const char* args) {
	char *token = new char[111]; strcpy(token, args); token = strtok(token, ", ");
	vector<char*> v({token});
	while(token = strtok(NULL,", ")) v.push_back(token);
	return reverse(v.begin(), v.end()), v;
}
void debugg(vector<char*> args) { cerr << "\b\b "; }
template <typename Head, typename... Tail>
void debugg(vector<char*> args, Head H, Tail... T) {
	debug() << " [" << args.back() << ": " << H << "] ";
	args.pop_back(); debugg(args, T...);
}
#define harg(...) #__VA_ARGS__
#ifndef ONLINE_JUDGE
#define dbg(...) { debugg(tokenizer(harg(__VA_ARGS__, \b\t-->Line)), __VA_ARGS__, __LINE__); cerr << endl;}
#else
#define dbg(...) { }
#endif
/// -----------------------------------------------------------------------
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi; 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)    
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define print(x) cout << x << "\n";
#define REP(i,a,b) for(i=a;i<=b;i++)
#define RAP(i,a,b) for(i=a;i>=b;i--)
#define spa <<" "<<
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
ll mod=1e9+7;
const int MX=0x3f3f3f3f;

int main(){
	int x;
	cin>>x;
	cout<<(x>=30?"Yes":"No");
	return 0;
}

Measured memory_bytes: 3624