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

typedef long long int ll;
ll MOD = 1000000007;

int main() {
  ll n, m;
  cin >> n >> m;
  vector<ll> v(n);
  for (int i = 0; i < n; i++) cin >> v[i];

  vector<ll> rui(n + 1);  // 累積和
  for (int i = 0; i < v.size(); i++)
    rui[i + 1] = (rui[i] + v[i]) % m;

  map<ll, ll> mp;  // それぞれの個数を数える
  for (int i = 0; i < rui.size(); i++) mp[rui[i]]++;

  ll ans = 0;
  for (auto x : mp)
    if (2 <= x.second)
      ans += x.second * (x.second - 1) / 2;

  cout << ans << endl;
}


Measured memory_bytes: 5760
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	public static boolean isValid(int[] u){
		int[] x = new int[10];
		for(int i=1;i<10;i++){
			x = Arrays.copyOf(u, 10);
			if(x[i]>=2){
				x[i]-=2;
				if(search(x, 1))return true;
				x[i]+=2;
			}
		}
		return false;
	}
	public static boolean search(int[] x,int k){
		if(k==10)return true;
		if(x[k]==0)return search(x, k+1);
		// あんこ
		if(x[k]>=3){
			x[k]-=3;
			if(search(x, k))return true;
			x[k]+=3;
		}
		if(k>=8)return false;
		// しゅんつ
		boolean f = true;
		for(int i=k;i<k+3;i++)if(x[i]==0)f = false;
		if(!f)return false;
		for(int i=k;i<k+3;i++)x[i]--;
		if(search(x, k))return true;
		for(int i=k;i<k+3;i++)x[i]++;
		return false;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String s;
		int[] u = new int[10];
		while((s=bf.readLine())!=null){
			char[] c = s.toCharArray();
			Arrays.fill(u, 0);
			for(int i = 0;i<c.length;i++){
				int n = c[i]-'0';
				u[n]++;
			}
			StringBuffer sb = new StringBuffer();
			for(int i = 1;i<10;i++){
				if(u[i]>=4)continue;
				u[i]++;
				if(isValid(u)){
					sb.append(" "+i);
				}
				u[i]--;
			}
			System.out.println(sb.length()>0?sb.substring(1):"0");
		}
	}
}

Measured memory_bytes: 9412
def main():
    n = int(input())
    s = input()
    ans = c = s[1:].count("E")
    for i in range(1, n):
        if s[i - 1] == "W":
            c += 1
        if s[i] == "E":
            c -= 1
        ans = min(ans, c)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3784
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const double eps = 1e-7;
const double PI = acos(-1.0);
#define DEBUG(x) cout << x << '\n'

long double a, b;
int main(){
#ifdef Irene
    freopen("in.txt", "r", stdin);
#endif // Irene
    ios::sync_with_stdio(false);

    cin >> a >> b;
    cout << (ll)(a * b);
}


Measured memory_bytes: 3816
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy


if __name__ == "__main__":
    x,y = map(int,input().split())
    for a in range(100):
        for b in range(100):
            if 2*a + 4*b == y and a+b == x:
                print("Yes")
                sys.exit()
    print("No")

Measured memory_bytes: 9616
#exec({'RUBY_THREAD_VM_STACK_SIZE'=>'100000000'},'/usr/bin/ruby', $0) if !ENV['RUBY_THREAD_VM_STACK_SIZE']
require 'prime'

def inpf() a=gets.chomp.split(" ").map(&:to_f)end

def inps() a=gets.chomp.split(" ")end

def copy(a) Marshal.load(Marshal.dump(a)) end

def kaijo(n,r = 10**9+7)(n < 2)? 1 : (2..n).inject{|memo,u|memo=(memo*u)%r} end

def na(n,d=0) Array.new(n,d)end

def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end

def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end

def inp() a=gets.chomp.split(" ").map(&:to_i)end

def r_up(a, b) (a+b-1)/b end

def sum(a) a.inject(:+) end

def big(a,b) return (a>b)? a:b end

def small(a,b) return (a<b)? a:b end

n,k = inp
t = na(n,false)
k.times do
  d = inp[0]
  inp.each do |x|
    t[x-1] = true
  end
end
p t.count(false)



Measured memory_bytes: 14520
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
typedef vector<int> vec;
int main(){
  int n,k,ans,m; ans=0; m=1;
  cin>>n>>k;
  while(m<=n){
    ans++;
    m=m*k;
  }
  cout<<ans;
}

Measured memory_bytes: 256
#include<stdio.h>
const int  mod=1e9+7;
int main(){
	int n;
 scanf("%d",&n);
 long long a=1,b=1,c=1,ans;
 for(int i=0;i<n;i++)
 {
 	a*=10;
 	b*=9;
 	c*=8;
 	a%=mod;
 	b%=mod;
 	c%=mod;
 }
 ans=a-b*2%mod+c;
 ans=ans+mod+mod;
 ans%=mod;
 printf("%lld\n",ans); 
}


Measured memory_bytes: 1732
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)

	n = n % 10

	if n == 2 || n == 4 || n == 5 || n == 7 || n == 9 {
		fmt.Println("hon")
	} else if n == 0 || n == 1 || n == 6 || n == 8 {
		fmt.Println("pon")
	} else {
		fmt.Println("bon")
	}
}


Measured memory_bytes: 1752
/*
for (int i = 0; i < N; ++i){}

// 各桁の和を計算する関数
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

sort(a, a + N, greater<int>());  // a[0:N] を大きい順にソート

int num[110] = {0};  // バケット
for (int i = 0; i < N; ++i) {
    num[d[i]]++;  // d[i] が 1 個増える
}

map<string, int> mp; // 連想配列 map<キー型, 値型> オブジェクト名
for (int i = 0; i < N; ++i) {
    auto itr = mp.find(s[i]);        // s[i] が設定されているか？
    if(itr != mp.end() ) {
         mp[s[i]] += 1;
    }
    else {
         mp[s[i]] += 1 ;
    }
}
stack<int> s;	//intをデータとするスタックを用意
s.push(1);		//{} -> {1}
printf("%d\n", s.top());	// 3
s.pop();

queue<int> que;	//intをデータとするキューを用意
que.push(1);		//{} -> {1}
printf("%d\n", que.front());	// 1
que.pop();
*/
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<int,int> point;
#define rep(i,n) for(i,0,n)
 
int main() {
	// 入力
	int R;
	cin >> R;


	//出力
	if (R<1200) printf("ABC\n");
	else if (R<2800) printf("ARC\n");
	else printf("AGC\n");
}
 


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

#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

const int INF=1e9;
const int MOD=1e9+7;
const double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

inline bool ok(int w,const vi& xs,int sp)
{
	int n=xs.size();
	vi sum(n+1);
	rep(i,n) sum[i+1]=sum[i]+xs[i];
	
	vi dp(n+1); dp[0]=1;
	int l=0,r=0,cnt=0;
	rep(i,n){
		for(;l<i;cnt-=!!dp[l++]) if(sum[i+1]-sum[l]+(i-l)<=w) break;
		for(;r<i;cnt+=!!dp[r++]) if(sum[i+1]-sum[r]+(i-r)*sp<w) break;
		dp[i+1]=!!cnt;
	}
	
	int res=dp[n];
	for(int i=n;i--;){
		if(sum[n]-sum[i]+(n-i-1)>w) break;
		res|=dp[i];
	}
	return res;
}

int main()
{
	for(int w,n;~scanf("%d%d",&w,&n) && w|n;){
		vi xs(n);
		rep(i,n) scanf("%d",&xs[i]);
		
		int lo=1,hi=w;
		while(lo<hi){
			int mi=(lo+hi)/2;
			if(ok(w,xs,mi))
				hi=mi;
			else
				lo=mi+1;
		}
		printf("%d\n",lo);
	}
}

Measured memory_bytes: 1736
N, M= map(int, input().split())
A = []
for i in range(N):
    a = list(map(int, input().split()))
    A.append(a)
A = sorted(A)
count = 0
cost = 0
i = 0
while count < M:
    cost += A[i][0] * min(A[i][1],M-count)
    count += min(A[i][1],M-count)
    i += 1    
print(cost)

Measured memory_bytes: 28656
#include<algorithm>
#include <iostream>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<string>
using namespace std;
int main(){
   
    int a,b;
    cin>>a>>b;
    
    if(a%3==0){
        cout<<"Possible"<<endl;
        return 0;
    }else if(b%3==0){
        cout<<"Possible"<<endl;
        return 0;
    }else if((a+b)%3==0){
        cout<<"Possible"<<endl;
        return 0;
    }else{
        cout<<"Impossible"<<endl;
        
    }
   
    
   
    
    return 0;
}






Measured memory_bytes: 256
package main

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

const N = 2019

func main() {
	sc := NewScanner()

	s := sc.ReadString()
	sLen := len(s)

	remCounts := make([]int, N)
	rem := 0
	remPow10 := 202
	for i := sLen - 1; i >= 0; i-- {
		n, _ := strconv.Atoi(string(s[i]))

		remPow10 = remPow10 * 10 % N
		rem = (rem + n*remPow10) % N

		remCounts[rem]++
	}
	remCounts[0]++

	cnt := 0
	for _, remCount := range remCounts {
		if remCount < 2 {
			continue
		}

		cnt += (remCount - 1) * remCount / 2
	}

	fmt.Println(cnt)
}

// util
// *   math/simple

func Abs(x int) int {
	if x >= 0 {
		return x
	}
	return -x
}

func Min(values ...int) int {
	if len(values) == 0 {
		panic("no values")
	}
	min := values[0]
	for _, v := range values {
		if v < min {
			min = v
		}
	}
	return min
}

func Max(values ...int) int {
	if len(values) == 0 {
		panic("no values")
	}
	max := values[0]
	for _, v := range values {
		if v > max {
			max = v
		}
	}
	return max
}

func Pow(base int, exponent uint) int {
	answer := 1
	for i := uint(0); i < exponent; i++ {
		answer *= base
	}
	return answer
}

// *   io

type Scanner struct {
	bufScanner *bufio.Scanner
}

func NewScanner() *Scanner {
	bufSc := bufio.NewScanner(os.Stdin)
	bufSc.Split(bufio.ScanWords)
	bufSc.Buffer(nil, 100000000)
	return &Scanner{bufSc}
}

func (sc *Scanner) ReadString() string {
	bufSc := sc.bufScanner
	bufSc.Scan()
	return bufSc.Text()
}

func (sc *Scanner) ReadInt() int {
	bufSc := sc.bufScanner
	bufSc.Scan()
	text := bufSc.Text()

	num, err := strconv.Atoi(text)
	if err != nil {
		panic(err)
	}
	return num
}

func (sc *Scanner) ReadInt64() int64 {
	bufSc := sc.bufScanner
	bufSc.Scan()
	text := bufSc.Text()

	num, err := strconv.ParseInt(text, 10, 64)
	if err != nil {
		panic(err)
	}
	return num
}


Measured memory_bytes: 2484
H, W = map(int, input().split())
S = [[x for x in input().split()] for _ in range(H)]

num2alpha = lambda c: chr(64+c)

for i in range(H):
    for j in range(W):
        if S[i][j]=='snuke':
            print(num2alpha(j+1) + str(i+1))
            break

Measured memory_bytes: 3060
#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <vector>
#include <cstdlib>
#include <map>
#include <queue>
#include <deque>
#include <algorithm>
#include <stack>
#include <functional>
#include <sstream>
#define rep(i,j,n) for(i=j;i<(n);i++)
#define rrep(i,j,n) for(i=j;i>(n);i--)
typedef long long int lli;
#define N 1000000007

using namespace std;

int main(){
    lli n,m,check;
    string a,b,ans="No",s;
    vector<string> temp,comp;
    lli i,j,k;
    cin>>n>>m;
    rep(i,0,n){
        cin>>a;
        temp.push_back(a);
    }
    rep(i,0,m){
        cin>>b;
        comp.push_back(b);
    }
    rep(i,0,n-m+1){
        rep(j,0,n-m+1){
            check=0;
            rep(k,0,m){
                s=temp[i+k].substr(j,m);
//                cout<<s<<"と"<<comp[k]<<"を比較"<<endl;
                if(s==comp[k]){
                    check++;
                }
            }
            if(check==m){
                ans="Yes";
            }
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
N = int(input())
L = list(map(int, input().split()))

import itertools
X = list(itertools.combinations(L, 3))
     
ans = 0

for i in X:
    temp = list(sorted(list(i)))
    if temp[0]+temp[1]>temp[2] and len(list(set(temp)))==3:
        ans += 1
        
print(ans)

Measured memory_bytes: 20616
#include <stdio.h>
int main(void)
{
	int n,m,t,i,j;

	scanf("%d %d",&n,&m);
	
	int a[100][100],b[100],ans[100];

	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}



	for(i=0;i<m;i++)
	{
		scanf("%d",&b[i]);
	}

	for(i=0;i<n;i++)
	{
		t = 0;
		
		for(j=0;j<m;j++)
		{
			t = t + (a[i][j]*b[j]);
			
		}

		ans[i] = t;
		
	}

	for(i=0;i<n;i++)
	{
		printf("%d\n",ans[i]);
	}


	
	return 0;

}

Measured memory_bytes: 640
n,m,c=map(int,input().split())
b_list=list(map(int,input().split()))

ans=0
for i in range(n):
  a_list=list(map(int,input().split()))
  num=0
  for j in range(m):
    num+=b_list[j]*a_list[j]
  if num+c>0:
    ans+=1

print(ans)

Measured memory_bytes: 9160
#include<bits/stdc++.h>
using namespace std;
int main()
{
  bool f=true;
  int N;
  cin>>N;
  while(N--)
  {
    int X;
    cin>>X;
    if(X%2==0)
      if(X%3&&X%5)
        f=false;
  }
  if(f)
    puts("APPROVED");
  else	puts("DENIED");
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define rep(i,n) for(int i=0;i<n;i++)
int gcd(int a, int b){
    int r=1;
    while(r!=0){
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
void revStr(char* str){
    int size = strlen(str);
    int i,j;
    char tmp = {0};
    for(i = 0, j = size - 1; i < size / 2; i++, j--){
        tmp = str[i];
        str[i] = str[j];
        str[j] = tmp;
    }return;
}
typedef struct{
    int a,b,c;
}data;

//昇順
int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}
//構造体降順
int comp( const void *c1, const void *c2 )
{
  data test1 = *(data *)c1;
  data test2 = *(data *)c2;
  int tmp1 = test1.b;   /* b を基準とする */
  int tmp2 = test2.b;
  return tmp2 - tmp1;
}

#define MAXSIZE 200000
int list[MAXSIZE];
int tail;

void Init(void){
    tail=0;
}
int Top(void){
    return 0;
}

int Next(int pos){
    if(pos<tail-1){
        return pos+1;
    }else{
        return -1;
    }
}
int Count(void){
    return tail;
}

int Item(int pos){
    if((pos>=0)&&(pos<tail)){
        return list[pos];
    }else{
        return 0;
    }
}
void Add(int value){
    if(tail<MAXSIZE){
        list[tail]=value;
        tail++;
    }
}
void Delete(int pos){
    if((pos>=0)&&(pos<tail)){
        int i;
        for(i=pos;i<tail-1;i++){
            list[i]=list[i+1];
        }
        tail--;
    }
}
int kai(int n){
    if(n==0){
        return 1;
    }
    int sum=1;
    for(int i=1;i<=n;i++){
        sum*=i;
    }
    return sum;
}

int main(){
    int N;
    scanf("%d",&N);
    int a[N],b[N];
    rep(i,N){
        scanf("%d",&a[i]);
    }
    rep(i,N){
        scanf("%d",&b[i]);
    }
    int p=0,q=0,a1=0,b1=0;
    while(p<N-1){
        int temp=0;
        for(int j=0;j<p;j++){
            if(a[j]<a[p]){
                temp++;
            }
        }
        a1+=(a[p]-1-temp)*kai((N-(p+1)));
        p++;
    }
    while(q<N-1){
        int temp=0;
        for(int j=0;j<q;j++){
            if(b[j]<b[q]){
                temp++;
            }
        }
        b1+=(b[q]-1-temp)*kai((N-(q+1)));
        q++;
    }
    printf("%d",abs(a1-b1));
}



Measured memory_bytes: 1716
#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=(long long)(k); i<(long long)(n); i++)
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define PQ(T) priority_queue<T>
#define PQS(T) priority_queue<T, vector<T>, greater<T> >
#define deci cout << fixed << setprecision(15);
typedef long long ll;
const ll inf = 1020304050607080910;
const int INF = 2000000000;
const ll mod = 1000000007;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
template<class T> bool chmin(T&x,T y){if(x>y){x=y;return true;}return false;}
template<class T> bool chmax(T&x,T y){if(x<y){x=y;return true;}return false;}
ll gcd(ll x,ll y){if(x>y)swap(x, y);while(x!=0){y%=x;swap(x, y);}return y;}
ll mpow(ll x,ll r){if(r==0)return 1;if(r%2==1){return x*mpow(x,r-1)%mod;}else{ll aa=mpow(x,r/2);return aa*aa%mod;}}


int main(){
	int h, w, k, ans = 0; cin >> h >> w >> k;
	char c[h][w];
	rep(i, h)rep(j, w) cin >> c[i][j];
	rep(i, (1<<h))rep(j, (1<<w)){
		int cnt[h][w];
		rep(x, h)rep(y, w) cnt[x][y] = 0;
		rep(x, h){
			if(i&(1<<x)){
				rep(y, w) cnt[x][y] = 1;
			}
		}
		rep(x, w){
			if(j&(1<<x)){
				rep(y, h) cnt[y][x] = 1;
			}
		}
		int p = 0;
		rep(x, h)rep(y, w){
			if(c[x][y]=='#' && cnt[x][y] == 0) p++;
		}
		if(p==k){ ans++; }
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
using namespace std;
#define i64  long long
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true

// int DP[MEM_SIZE][MEM_SIZE] = {0};
// int GMEM[MEM_SIZE][MEM_SIZE] = {0};
template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return;std::cout << e << std::endl;}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T> void DEBUG(string str, T e){if(DEBUG_OUT == false)return;std::cout <<str<<" ";DEBUG(e);};
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
template<typename T> void SORT_(vector<int>& v,bool GREATER = 0){if(GREATER == 0)sort(v.begin(),v.end());else{sort(v.begin(),v.end(),std::greater<T>());}}

//CODE
void solve(void)
{
  int N,X;
  cin>>N>>X;
  int MIN =INF;
  for (int i = 0; i < N; i++)
  {
    int M;
    cin>>M;
    chmin(MIN,M);
    X -= M;
  }
  cout<<N+X/MIN<<endl;
    
  return;
}


int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(9);
  solve();

 
  return 0;
}

Measured memory_bytes: 256
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <complex>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

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

int main() {
  int N, M;
  string s;
  static int dp[100002];
  static int pre[100002];

  while (cin >> N >> M) {
    cin >> s;
    fill(dp, dp + N + 1, INT_MAX);

    dp[0] = 0;
    priority_queue<P,vector<P>,greater<P>> open;
    open.push(P(0, 0));

    for (int i = 1; i <= N; i++) {
      if (s[i] == '1') {
        continue;
      }

      /*
      priority_queue<P,vector<P>,greater<P>> tmp;
      while (!open.empty()) {
        P p = open.top(); open.pop();
        tmp.push(p);
        cout << p.first<<","<<p.second<<" ";
      }
      cout<<endl;
      open = tmp;
      */
      
      while (!open.empty()) {
        P p = open.top(); open.pop();
        int cost = p.first;
        int preIdx = (p.second);
        if (i - preIdx > M) {
          continue;
        }
        dp[i] = cost + 1;
        pre[i] = preIdx;
        open.push(p);
        open.push(P(dp[i], i));
        break;
      }
    }

    if (dp[N] == INT_MAX) {
      cout << -1 << endl;
      continue;
    }

    /*
    for (int i = 0; i <= N; i++) {
      cout<<dp[i]<<",";
    }
    cout<<endl;
    */

    vector<int> ans;
    int idx = N;
    while (idx > 0) {
      ans.push_back(idx - pre[idx]);
      idx = pre[idx];
    }
    for (int i = ans.size() - 1; i >= 0; i--) {
      if (i != ans.size() - 1) {
        cout << " ";
      }
      cout << ans[i];
    }
    cout << endl;
  }
}


Measured memory_bytes: 1912
/*================================================================
*
*   创 建 者： badcw
*   创建日期： 2020/6/21 20:51
*
================================================================*/
#include <bits/stdc++.h>

#define ll long long
using namespace std;

const int maxn = 2e6+50;
const int mod = 1e9+7;
ll qp(ll a, ll n, ll mod = ::mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

ll jie[maxn] = {1};
char s[maxn];

ll inv(ll x) { return qp(x, mod - 2); }

ll C(int x, int y) {
    if (x < y) return 0;
    if (x == 0) return 0;
    return jie[x] * inv(jie[y]) % mod * inv(jie[x - y]) % mod;
}

int main(int argc, char* argv[]) {
    int k;
    cin >> k >> s;
    int len = strlen(s);
    k += len;
    for (int i = 1; i <= k; ++i) jie[i] = jie[i - 1] * i % mod;
    ll res = qp(26, k);
    ll TC = 0;
    ll TQ = qp(25, k);
    ll tt = inv(25);
    for (int i = 0; i < len; ++i) {
        if (i == 0) {
            TC = 1;
        } else TC = TC * (k - i + 1) % mod * inv(i) % mod;
        res -= TC * TQ;
        res %= mod;
        TQ = TQ * tt % mod;
//        res -= C(k, i) * qp(25, k - i) % mod;
//        res %= mod;
    }
    if (res < 0) res += mod;
    cout << res << endl;
//    printf("%lld\n", res);
    return 0;
}

Measured memory_bytes: 20108
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
#include<time.h>
#include<cassert>

using namespace std;
#define ll long long
#define ld long double
#define int long long
#define all(a) (a).begin(),(a).end()
#define EPS (1e-13)
#define fs first
#define sc second
#define xx first
#define yy second.first
#define zz second.second
#define H pair<int, int>
#define P pair<int, pair<int, int>>
#define Q(i,j,k) mkp(i,mkp(j,k))
#define rep(i,n) for(int (i) = 0 ; (i) < (n) ; (i)++)
#define mkp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end())
const int Mod = 1e9 + 7;
const int mod = 998244353;
const ll Inf = 3 * 1e18;
const int inf = 15 * 1e8;
ll read() {
	ll u, k = scanf("%lld", &u);
	return u;
}
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j % i, i);
}
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}
ll bcount(ll x) {
	int sum = 0;
	for (int i = 0; i < 20; i++)
		if ((1ll << i) & x) sum++;
	return sum;
}
/*const int fn_ = 2000000;
ll fact_[fn_], comp_[fn_];
ll comb(ll x, ll y, ll mod = Mod) {
	if (!fact_[0]) {
		fact_[0] = 1; comp_[0] = 1;
		for (int i = 1; i < fn_; i++) {
			fact_[i] = fact_[i - 1] * i % mod;
			comp_[i] = mod_pow(fact_[i], mod - 2, mod);
		}
	}
	if (x < y) return 0;
	return fact_[x] * comp_[x - y] % mod * comp_[y] % mod;
}*/
//---------------------------------------------------
int a[5000], b[5000];
int dp[5000][5000];
int n;
string s;
signed main() {
	cin >> s;
	n = s.size();
	//a[i]=i個の赤い球を入れるために必要な最小操作回数
	//a[i]=k  前からi個めの球を入れるまでにk回の操作が必要であった。
	//a[i]    i個めのボールが前からa[i-1]番目以降の場所にいる場合、その回数分が必要
	for (int i = 1; i < 5000; i++)
		a[i] = inf, b[i] = inf;
	int t = 1, sum = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '0') {
			if (a[t - 1] >= i) {
				a[t] = a[t - 1] + 1;
				t++;
				a[t] = a[t - 1] + 1;
				t++;
				sum += 2;
			}
			else {
				a[t++] = i + 1;
				a[t++] = i + 2;
				sum++;
			}
		}
		else if (s[i] == '1') {
			if (a[t - 1] >= i) {
				a[t] = a[t - 1] + 1;
				t++;
			}
			else a[t++] = i + 1;
		}
	}
	t = 1;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '2') {
			if (b[t - 1] >= i) {
				b[t] = b[t - 1] + 1;
				t++;
				b[t] = b[t - 1] + 1; 
				t++;
			}
			else {
				b[t++] = i + 1;
				b[t++] = i + 2;
			}
		}
		else if (s[i] == '1') {
			if (b[t - 1] >= i) {
				b[t] = b[t - 1] + 1;
				t++;
			}
			else b[t++] = i + 1;
		}
	}
	dp[0][0] = 1;
	for (int i = 1; i <= 2 * n; i++) {
		for (int j = 0; j <= 2 * n; j++) {
			if (a[j] <= i && b[i - j] <= i) {
				dp[i][j] = ((j == 0 ? 0 : dp[i - 1][j - 1]) + dp[i - 1][j]) % mod;
			}
		}
	}
	int ans = 0;
	for (int i = 0; i <= 2 * n; i++) {
		(ans += dp[2 * n][i]) %= mod;
	}
	cout << ans << endl;
}

Measured memory_bytes: 156160
#include <bits/stdc++.h>
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

using namespace std;

using ll=long long;
using pll = pair<ll,ll>;

const static int h = 17;
const static int n = 1 << h;

pll data[2 * n];
const pll out = pll(0LL, 0LL);

inline pll vmerge(pll l, pll r) {
	return max(l, r);
}

void init() {
	fill_n(data, 2 * n, out);
}

void update(int p, pll x) {
	for (data[p += n] = x; p > 1; p >>= 1){
		data[p >> 1] = vmerge(data[p], data[p ^ 1]);
	}
}

pll query(int l, int r) {
	pll resl = out, resr = out;
	for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
		if (l & 1) resl = vmerge(data[l++], resl);
		if (r & 1) resr = vmerge(resr, data[--r]);
	}
	return vmerge(resl, resr);
}

int main(void){
	int m;
	cin >> m;

	vector<pll> ary;

	rep(i, m){
		int val;
		cin >> val;
		ary.push_back(pll(val, -i));
	}

	sort(begin(ary), end(ary));
	init();

	for(auto &elem:ary){
		const ll val = elem.first;
		const int idx = -elem.second;
		pll cur = query(0, idx);
		cur.first++, cur.second += val;
		update(idx, cur);
	}

	pll ans = query(0, n);
	cout << ans.second << endl;

	return 0;
}


Measured memory_bytes: 8568
// khodaya khodet komak kon
#include <bits/stdc++.h>
#define pb push_back
#define ers erase
#define ins insert
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x)  cerr << #x << " = " << x << endl
#define kill(x) return cout << x, 0;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#pragma GCC optimize ("Ofast")
using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<pll> vpl;

const ld Pi = 3.14159265359;
const ll MOD = 1000 * 1000 * 1000 + 7;
const ll N = 2e5 + 10;
const ll INF = 1e18;
const ll LOG = 20;

ll k, a, b;

int main(){
	IOS;
	cin >> k >> a >> b;
	if (b - a <= 1){
		
		kill(k + 1);
	}
	
	else{
		if (a - 1 >= k){
			kill(k + 1);
		}
		else k -= a - 1;
		kill(a + (b - a) * (k / 2) + (k % 2));
		
	}
	
	
	
	
	
	
	
	return 0;
}






/*
     ,---,           ___                 ,--,
    '  .' \        ,--.'|_             ,--.'|                             ,--,
   /  ;    '.      |  | :,'            |  | :                           ,--.'|    ,---.        ,---,
  :  :       \     :  : ' :            :  : '                 .--.--.   |  |,    '   ,'\   ,-+-. /  |
  :  |   /\   \  .;__,'  /    ,--.--.  |  ' |     ,--.--.    /  /    '  `--'_   /   /   | ,--.'|'   |
  |  :  ' ;.   : |  |   |    /       \ '  | |    /       \  |  :  /`./  ,' ,'| .   ; ,. :|   |  ,"' |
  |  |  ;/  \   \:__,'| :   .--.  .-. ||  | :   .--.  .-. | |  :  ;_    '  | | '   | |: :|   | /  | |
  '  :  | \  \ ,'  '  : |__  \__\/: . .'  : |__  \__\/: . .  \  \    `. |  | : '   | .; :|   | |  | |
  |  |  '  '--'    |  | '.'| ," .--.; ||  | '.'| ," .--.; |   `----.   \'  : |_|   :    ||   | |  |/
  |  :  :          ;  :    ;/  /  ,.  |;  :    ;/  /  ,.  |  /  /`--'  /|  | '.'\   \  / |   | |--'
  |  | ,'          |  ,   /;  :   .'   \  ,   /;  :   .'   \'--'.     / ;  :    ;`----'  |   |/
  `--''             ---`-' |  ,     .-./---`-' |  ,     .-./  `--'---'  |  ,   /         '---'
                            `--`---'            `--`---'                 ---`-'
*/




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

using namespace std;
typedef long long ll;
const ll M=1000000007;
int a[maxn],b[maxn],n,m,k;
ll ans,s,t,w;

int main(){
    cin >> n >> m; ans=1;
    for (int i=1;i<=n;i++){
        cin >> k; a[k]=i;
    }
    for (int i=1;i<=m;i++){
        cin >> k; b[k]=i;
    }
    for (int i=n*m;i;i--){
        if (a[i]&&b[i]) s++,t++;
        else if (a[i]) ans=ans*t%M,s++;
        else if (b[i]) ans=ans*s%M,t++;
        else ans=ans*(s*t-w)%M;
        w++;
    }
    cout << ans << endl;
}


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

struct Fast {Fast(){cin.tie(0);ios::sync_with_stdio(0);}} fast;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define ceiv(a, b) (1 + (int)((a) - 1)/(int)(b))
#define int long long

int dist(int x, int y, int to_x, int to_y){
    return abs(x-to_x) + abs(y-to_y);
}

signed main(){
    int n; cin >> n;
    vector<int> t(n+1), x(n+1), y(n+1);
    t[0] = x[0] = y[0] = 0;
    rep(i, n) cin >> t[i+1] >> x[i+1] >> y[i+1];
    
    bool ans = true;
    reps(i, 1, n){
        int d = dist(x[i],y[i],x[i-1],y[i-1]);
        int limit = t[i] - t[i-1];
        if(limit < d || limit % 2 != d % 2){
            ans = false;
            break;
        }
    }
    
    cout << (ans ? "Yes" : "No") << endl;
}

Measured memory_bytes: 2560
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int fn = 0;
		int t = n;

		while (true) {
			fn += t % 10;
			t = t / 10;
			if (t == 0)
				break;
		}
		if (n % fn == 0) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
		sc.close();
	}
}

Measured memory_bytes: 23764
#include <iostream>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>

using namespace std;
typedef long long int ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
ll MOD = 1000000007;
#define INF (1e9)

ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
typedef pair <ll,ll> P;


int main()
{
    ll A, B, C, D;
    cin >> A >> B >> C >> D;
    if (A*B > C*D) {
        cout << A*B << endl;
    }else {
        cout << C*D << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

int h, w;
char map[101][101];

void part(int y, int x){
  char now = map[y][x];
  map[y][x] = ' ';
  if(y > 0 && now == map[y - 1][x]) part(y - 1, x);
  if(x > 0 && now == map[y][x - 1]) part(y, x - 1);
  if(y < h && now == map[y + 1][x]) part(y + 1, x);
  if(x < w && now == map[y][x + 1]) part(y, x + 1);
  return;
}

int main(){
  int i, j, c;
  while(scanf("%d%d", &h, &w) && h && w){
    memset(map, '\0', sizeof(map));
    for(i = 0;i < h;i++) scanf("%s", map[i]);
    c = 0;
    for(i = 0;i < h;i++){
      for(j = 0;j < w;j++){
	if(map[i][j] != ' '){
	  part(i, j);
	  c++;
	}
      }
    }
    printf("%d\n", c);
  }
  return 0;
}

Measured memory_bytes: 1392
n = int(input())
cnt = 0
for i in range(100):
    if 4*i>n:
        break
    for j in range(100):
        if 7*j>n:
            break
        if 4*i+7*j==n:
            cnt+=1
if cnt>0:
    print('Yes')
else:
    print('No')

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

int main(){
	int A,B,K;
	int count=0;
	int tmp[100];
	cin >> A >> B >> K;
	for(int i=1;i<101;i++){
		if(A % i == 0 && B % i == 0){
			tmp[count] = i;
			count++;
		}
	}
	cout << tmp[count-K] << endl;
}


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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    long int N, A, B;
    cin >> N >> A >> B;
    if (A > B || (N == 1 && (A != B))) {
        cout << 0 << endl;
    } else {
        cout << (N - 2) * (B - A) + 1 << endl;
    }
}


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

int main()
{
    int N, M;
    std::cin >> N >> M;
    std::vector<long long> A(N);
    for(int i=0; i<N; i++) scanf(" %lld", &A[i]);

    std::vector<long long> r(1, 0); // r[i] = sum(A[0]: A[i]) % M
    for(int i=0; i<N; i++) r.push_back((r.back()+A[i]) % M);
    std::sort(r.begin(), r.end());

    long long count = 1, sum = 0;
    for(int i=0; i<N; i++){
        if(r[i] == r[i+1]) count++;
        else{
            sum += count * (count-1) / 2;
            count = 1;
        }
    }
    sum += count * (count-1) / 2;

    std::cout << sum << std::endl;
}

Measured memory_bytes: 2168
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream &operator << (ostream& out,const pair<S,T>& o){
    out << "(" << o.first << "," << o.second << ")"; return out;
}

/*
<url:https://arc081.contest.atcoder.jp/tasks/arc081_c>
問題文============================================================
 文字列 S に対して，その文字列を構成する文字を 0 文字以上取り除き，
 残った文字を元の順番で並べて得られる文字列を S の部分列と呼びます．
 たとえば，arc や artistic や (空文字列) は artistic の部分列ですが，
 abc や ci は artistic の部分列ではありません．
 
 英小文字からなる文字列 A が与えられます．
 このとき，英小文字からなる文字列で，A の部分列ではないようなもののうち，最も短いものを求めてください．
 ただし，そのようなものが複数ある場合には，辞書順で最小のものを求めてください．
=================================================================

解説=============================================================
解説を見た
================================================================
*/

string solve(){
    string res = "";
    string A; cin >> A;
    vector<int> f(26,0);
    vector<int> nextC(A.length()+1,0);
    for(int i = (int)A.length()-1; i >= 0; i--){
        int cnt = 0;
        f[A[i]-'a'] = true;
        nextC[i] = nextC[i+1];
        for(int j = 0; j < 26;j++){
            if(f[j]) cnt++;
            else break;
        }
        if(cnt == 26) for(int j = 0; j < 26;j++) f[j] = false;
        nextC[i] = cnt%26;
    }
    for(int i = 0; i < A.length(); i++){
        char c = nextC[i] + 'a';
        res += c;
        while(i < A.length() && A[i] != c) i++;
    }
    return res;
}
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    cout << solve() << endl;
	return 0;
}


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

#define ll long long
#define debug(x) cerr << fixed << #x << " is " << x << endl;

const int MAX_N = 105;
const int MAX_A = 105;
int n;
int dp[2][MAX_N][MAX_N*MAX_A];
int grid[2][MAX_N];

int dp_solve(int x, int y, int sum)
{
	if(x >= 2 || y >= n)
		return sum;
	if(dp[x][y][sum] != -1)
		return dp[x][y][sum];

	int Max = dp_solve(x + 1, y, sum) + grid[x][y];
	Max = max(Max, dp_solve(x, y + 1, sum) + grid[x][y]);

	return dp[x][y][sum] = Max;
}

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

	cin >> n;
	for(int i = 0; i < 2; i++)
		for(int j = 0; j < n; j++)
			cin >> grid[i][j];
	memset(dp, -1, sizeof(dp));
	cout << dp_solve(0, 0, 0) << endl;

	return 0;
}


Measured memory_bytes: 9344
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define repk(i,m,n) for(ll i=m;i<n;i++)
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define F first
#define S second
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD1=1e9+7;
const int MOD2=998244353;
const int INF=2*1e9;
int main()
{
    ll h,w,sum;
    cin>>h>>w;
    sum=h*w;
    if(h==1||w==1) cout<<1;
    else
    {
        if(sum%2==0) cout<<sum/2;
        else cout<<sum/2+1;
    }
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <cmath>
#include <numeric>
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <list>
#include <unordered_map>
#include <tuple>
#include <complex>


#define FOR(i, a, b)		for(int i = (int)(a); i < (int)(b); ++i)
#define FORE(i, a, b)		for(int i = (int)(a); i <= (int)(b); ++i)
#define REP(i, n)			FOR(i, 0, n)
#define REPE(i, n)			FORE(i, 0, n)
#define ALL(x)				(x).begin(),(x).end()
#define DEBUG_DC(x)			cout << #x << ": " << x << endl
#define VEC_TYPE			ll
#define INF					1e5+1

using namespace std;
typedef long long ll;
typedef vector<VEC_TYPE> vdef;
typedef vector<vdef> vvdef;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmaxE(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; }
template<class T> inline bool chminE(T& a, T b) { if (a >= b) { a = b; return 1; } return 0; }
template<typename T> inline T mygcd(T a, T b) { return b ? mygcd(b, a%b) : a; }
template<typename T> inline T mylcm(T a, T b) { return a * b / mygcd(a, b); }

int main()
{
	ll ans = 0;
	int n;
	cin >> n;
	vdef a(n + 1);
	for (int i = 0; i < n + 1; ++i) cin >> a[i];
	vdef b(n);
	for (int i = 0; i < n; ++i) cin >> b[i];

	vdef f(n + 1);
	f[0] = min(a[0], b[0]);
	ll f_plus = min(a[1], (b[0] - f[0]));
	ans += (f[0] + f_plus);

	for (int i = 1; i < n; ++i)
	{
		f[i] = min((a[i] - f_plus), b[i]);
		f_plus = min(a[i + 1], (b[i] - f[i]));
		ans += (f[i] + f_plus);
	}

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

Measured memory_bytes: 2560
def bishop(H, W):
    if H==1 or W== 1:
        return 1
    result  = int((H-1)/2 + 1) * int((W-1)/2 + 1) + int(H/2) * int(W/2)
    return result
ans = input().split(" ")
H = int(ans[0])
W = int(ans[1])
print(bishop(H,W))


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

int main(){
    string S, T;
    cin >> S;
    cin >> T;
    
    int sum;
    int i;
    sum = 0;

    for(i=0;i<S.size();i++){
        if(S.at(i) != T.at(i)){sum += 1;} 
    }
    cout << sum << endl;


    return 0;
}


Measured memory_bytes: 3912
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ll long long int
int compare_longlong(const void *a, const void *b) {long long *A = (long long *)a;long long *B = (long long *)b;if (*A > *B) return 1;if (*A < *B) return -1;return 0;}
int main(void){
	int n;
	ll c,k;
	scanf("%d%lld%lld",&n,&c,&k);
	ll t[n];
	for(int i=0;i<n;i++)scanf("%lld",&t[i]);
	qsort(t,n,sizeof(ll),compare_longlong);
	int num=0;
	int ans=0;
	while(num<n){
		ll s = t[num];
		ll p=0;
		ll nowT = t[num];
		while(p<c && nowT<=s+k){
			p++;
			num++;
			nowT = t[num];
		}
		ans++;
	}
	printf("%d",ans);
	
	return 0;
}

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define WHATIS(x) cout << #x << " is " << x << endl;
#define ERROR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x

using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<ll, II> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << *it << " = " << a << endl;
    err(++it, args...);
}

const ll MODBASE = 1000000007LL;
const int MAXN = 100010;

int n, a[MAXN], l[MAXN], r[MAXN];

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n;
    FOR(i,1,n) cin >> a[i];
    int cnt = 0;
    FOR(i,1,n) 
        if (a[i] < 0) cnt++;
    FOR(i,1,n) a[i] = abs(a[i]);
    ll res = 0;
    FOR(i,1,n) res += a[i];
    if (cnt % 2) {
        int u = a[1];
        FOR(i,1,n) u = min(u, a[i]);
        res -= (ll) u * 2;
    }
    cout << res;
    return 0; 
}

Measured memory_bytes: 640
# coding: utf-8 
# Your code here! 
H,W=map(int,input().split()) 
S=[] 

ku=0
for _ in range(H): 
    S.append(list(input()))
    ku+=S[-1].count(".")


def bfs(h,w,num):
    if h==H-1 and w==W-1:
        print(ku-num-1)
        exit() 
    else:
        pass

    if h!=0: 
        if S[h-1][w]!="#": 
            temp.append([h-1,w])
            S[h-1][w]="#"

    if w!=0: 
        if S[h][w-1]!="#": 
            temp.append([h,w-1]) 
            S[h][w-1]="#"

    if h!=H-1: 
        if S[h+1][w]!="#": 
            temp.append([h+1,w]) 
            S[h+1][w]="#"

    if w!=W-1: 
        if S[h][w+1]!="#": 
            temp.append([h,w+1]) 
            S[h][w+1]="#"
        
q=[[0,0]] 
count=-1
while True: 
    count+=1
    #print(q)
    temp=[]
    while q:
        l=q.pop(0)
        bfs(l[0],l[1],count)
        
    q=temp[:]
    if len(q)==0:
        print(-1)
        exit()



Measured memory_bytes: 3064
#include<stdio.h>
int main()
{
	int N,i,flag=0;
	scanf("%d",&N);
	while(N)
	{
		i = N%10;
		if (i==7){
			flag = 1;
			break;
		}
		N/=10;
	}
	if(flag)
		printf("Yes");
	else
		printf("No");
}

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

using namespace std;
#define chmax(a,b) a=max(a,b)
#define N 100010
vector<ll> g[N];
ll nz[N],n,m,f[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)f[i]=1,nz[i]=0;
    for(int i=0;i<m;i++){
     ll x,y;cin>>x>>y;
     g[x].push_back(y);
     nz[y]++;
    }
    queue<ll> Q;
    for(int i=1;i<=n;i++){ 
     if(nz[i]==0)Q.push(i);
    }
    while(!Q.empty()){
        ll x=Q.front(); Q.pop();
        for(auto y:g[x]){
            chmax(f[y],f[x]+1);
         nz[y]--;
         if(nz[y]==0)Q.push(y);
        }
    }
    ll ans=1;
    for(int i=1;i<=n;i++)chmax(ans,f[i]);
    cout<<ans-1<<endl;
 return 0;   
}

Measured memory_bytes: 7296
s1=input()
s2=input()

def lcs(s,t):
    l1=len(s)
    l2=len(t)
    tb=[[0]*l2 for i in range(l1)]

    for i in range(l1):
        for j in range(l2):
            if s[i]==t[j]:
                if i==0 or j==0:
                    tb[i][j]=abs(j-i)
                    continue
                tb[i][j]=tb[i-1][j-1]
                continue
            if i!=0 and j!=0:
                tb[i][j]=min(tb[i-1][j],tb[i][j-1],tb[i-1][j-1])+1
            elif i==0:
                tb[i][j]=tb[i][j-1]+1
            else:
                tb[i][j]=tb[i-1][j]+1
    print(tb[l1-1][l2-1])

lcs(s1,s2)


Measured memory_bytes: 41912
#include <iostream>
#include <vector>
#include <algorithm>

typedef long long ll;

using namespace std;

static const int MAX = 10001;

ll n, m;
pair<ll, ll> poll[MAX];

int main(void){

	while(1){
		cin >> n >> m;
		if(n == 0 && m == 0)break;
		for(ll i=0; i<n; i++){
			poll[i].first = 0;
			poll[i].second = 0;
		}
		for(ll i=0; i<m; i++){
			ll s;
			cin >> s;
			ll k=0;
			cin >> k;
			for(ll j=0; j<k; j++){
				ll tmp = 0;
				cin >> tmp;
				tmp--;
				if(k==1){
					poll[tmp].first+=s;
				}
				poll[tmp].second+= s;
			}
		}

		ll sa = 0;
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(i!=j){
					sa = max(sa, poll[i].second - poll[j].first);
				}
			}
		}

		cout << sa + 1 << endl;
	}

	return 0;
}


Measured memory_bytes: 3280
n, m, l = map(int, input().split())
A = [[0 for i in range(m)] for j in range(n)]
B = [[0 for i in range(l)] for j in range(m)]
C = [[0 for i in range(l)] for j in range(n)]

for i in range(n):
    A[i] = list(map(int, input().split()))

for i in range(m):
    B[i] = list(map(int, input().split()))
    
for i in range(n):
    for j in range(l):
        for k in range(m):
            C[i][j] += A[i][k] * B[k][j]
            
for i in range(n):
    print(" ".join(map(str, C[i])))


Measured memory_bytes: 6900
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<string>
#include<vector>
using namespace std;

int main(void){
	int a, b, x;
	cin >> a >> b >> x;
	if (a > x) {
		cout << "NO";
		return 0;
	}
	if (b >= x - a) {
		cout << "YES";
		return 0;
	}
	cout << "NO";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   

using namespace std;
#define i64  long long

#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807


void solve(void)
{ 

  int N;
  cin>>N;
  vector<double> X(N,0);
  vector<double> Y(N,0);

  vector<double> ABS(N,0);
  for (int i = 0; i < N; i++)
  {
    cin>>X[i];
  }
  
   for (int i = 0; i < N; i++)
  {
    cin>>Y[i];
  }
  for (int i = 0; i < N; i++)
  {
    ABS[i] = abs(X[i] - Y[i]);
  }

  double N1 = 0,N2 = 0 ,N3 = 0,NI = 0;

  std::vector<double>::iterator iter = std::max_element(ABS.begin(), ABS.end());
  size_t index = std::distance(ABS.begin(), iter);

  NI = ABS[index];

  for (int i = 0; i < N; i++)
  {
    N1 += ABS[i];
    //  cout<<ABS[i]<<endl;
  }
  
  for (int i = 0; i < N; i++)
  {
    N2 += ABS[i]*ABS[i];
  }

  N2 = sqrt(N2);
  
  for (int i = 0; i < N; i++)
  {
    N3 += pow(ABS[i],3);
  }

  N3 = pow(N3,0.3333333333333333);
  
  cout<<fixed;
  cout<<setprecision(8);
  cout<<N1<<endl;
  cout<<N2<<endl;
  cout<<N3<<endl;
  cout<<NI<<endl;
  


  return;
}

int main(int argc, const char *argv[])
{

  solve();

  return 0;
}



Measured memory_bytes: 3448
N =  int(input())
S = [input() for i in range(N)]

ac = S.count('AC')
wa = S.count('WA')
tle = S.count('TLE')
re = S.count('RE')

print('AC x %d' %ac) 
print('WA x %d' %wa) 
print('TLE x %d' %tle) 
print('RE x %d' %re) 

Measured memory_bytes: 16148
import java.util.Scanner;
import java.util.Arrays;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        int K = sc.nextInt();
        int max = Math.max(A,Math.max(B,C));
        int sum = 0;
        sum += A + B + C - max;
        for(int i = 0;i < K;i++){
            max *= 2;
        }
        sum += max;
        System.out.println(sum);
    }
}


Measured memory_bytes: 21716
#include<stdio.h>
int main()
{
  int r,D;
  long long int x;
  scanf("%d %d %lld",&r, &D, &x);
  int i;
  
  for(i=0;i<10;i++)
  {
    x=r*x-D;
    printf("%lld\n",x);
  }
  return 0;
}

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

using namespace std;

int n, a, b, cnt[3];

int main()
{
    cin >> n >> a >> b;
    for(int i = 1, p; i <= n; ++i)
    {
        cin >> p;
        if(p <= a) cnt[0]++;
        else if(p <= b) cnt[1]++;
        else cnt[2]++;
    }
    cout << min(cnt[0], min(cnt[1], cnt[2])) << endl;
    return 0;
}

Measured memory_bytes: 256
from sys import stdin

n, d = [int(x) for x in stdin.readline().rstrip().split()]

x_lst = []
for _ in range(n):
  x_lst.append([int(x) for x in stdin.readline().rstrip().split()])

def calc_distance(l1, l2):
  return sum([(l1[x]-l2[x])**2 for x in range(d)])**0.5
  
count = 0
for i in range(n):
  for j in range(n):
    if i < j:
      di = calc_distance(x_lst[i], x_lst[j])
      if di == int(di):
        count += 1

print(count)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll sx,sy,ex,ey;
	cin>>sx>>sy>>ex>>ey;
	ll dx=ex-sx;
	ll dy=ey-sy;
	for(ll i=0;i<dx;i++){
		cout << 'R';
	}
	for(ll i=0;i<dy;i++){
		cout << 'U';
	}
	for(ll i=0;i<dx;i++){
		cout << 'L';
	}
	for(ll i=0;i<dy;i++){
		cout << 'D';
	}
	cout << 'D';
	for(ll i=0;i<dx+1;i++){
		cout << 'R';
	}
	for(ll i=0;i<dy+1;i++){
		cout << 'U';
	}
	cout<< 'L';
	cout << 'U';
	for(ll i=0;i<dx+1;i++){
		cout << 'L';
	}
	for(ll i=0;i<dy+1;i++){
		cout << 'D';
	}
	cout << 'R';
	// your code goes here
	return 0;
}

Measured memory_bytes: 256