akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <algorithm>
#include <iomanip>

const int DEPTH_LIMIT = 45;

using namespace std;

void PrintBoard( const vector<int>& b ) {
    for ( int row=0; row<4; ++row ) {
	for ( int col=0; col<4; ++col ) cout << setw(2) << " " << b[row*4+col];
	cout << endl;
    }
}

bool IsCompleted( const vector<int>& b ) {
    for ( int i=0; i<15; ++i ) {
	if ( b[i] != i+1 ) return false;
    }
    return b[15] == 0;
}

int H1( const vector<int>& b ) {
    int dist = 0;
    for ( int i=0; i<15; ++i ) dist += b[i] == (i+1) ? 1 : 0;
    return dist;
}

int H2( const vector<int>& b ) {
    static int tab[16][2] = {
	{ 3, 3 },//0
	{ 0, 0 }, { 1, 0 }, { 2, 0 }, { 3, 0 },
	{ 0, 1 }, { 1, 1 }, { 2, 1 }, { 3, 1 },
	{ 0, 2 }, { 1, 2 }, { 2, 2 }, { 3, 2 },
	{ 0, 3 }, { 1, 3 }, { 2, 3 } };
	
    int dist = 0;
    for ( int i=0; i<16; ++i ) {
	if ( b[i] == 0 ) continue;//ignore pos of 0
	int x = i%4;
	int y = i/4;
	dist += abs( tab[b[i]][0] - x ) + abs( tab[b[i]][1] - y );
    }
    return dist;
}

const int dx[4] = { -1, 0, 1,  0 };
const int dy[4] = {  0, 1, 0, -1 };
vector<int> board, board_org( 16 );
    
bool Solve( int x, int y, int curr, int lim, int prev ) {

    if ( IsCompleted( board ) ) return true;

    //    cout << "--- " << x << " " << y << " " << curr << " " << lim << endl;
    //    PrintBoard( board );
    
    if ( curr == lim ) return false;
    
    for ( int i=0; i<4; ++i ) {

	if ( (i+2)%4 == prev ) continue;
	
	int nx = x + dx[i];
	int ny = y + dy[i];

	if ( nx < 0 || nx > 3 || ny < 0 || ny > 3 ) continue;

	swap( board[4*y+x], board[4*ny+nx] );
	
	//	cout << "i = " << i << " " << curr + H2( board ) << endl;
	//	PrintBoard( board );
	
	if ( curr + H2( board ) > lim ) {
	    swap( board[4*y+x], board[4*ny+nx] );
	    continue;
	}

	if ( Solve( nx, ny, curr+1, lim, i ) ) return true;

	swap( board[4*y+x], board[4*ny+nx] );	
    }

    return false;
}

int main() {

    int x, y;
    
    for ( int i=0; i<4; ++i ) {
	for ( int j=0; j<4; ++j ) {
	    cin >> board_org[i*4+j];
	    if ( board_org[i*4+j] == 0 ) {
		x = j;
		y = i;
	    }
	}
    }

    for ( int d=0; d<DEPTH_LIMIT; ++d ) {
	board = board_org;
	if ( Solve( x, y, 0, d, 5 ) ) {
	    cout << d << endl;
	    return 0;
	}
	//	cout << endl;
    }

    cout << DEPTH_LIMIT << endl;
    
    return 0;
}



Measured memory_bytes: 3144
package main

import (
	"bufio"
	"fmt"
	"io"
	"math"
	"os"
	"strconv"
	"strings"

)


func main() {
	solve(os.Stdin, os.Stdout)
}

type ReaderEx struct {
	baseScanner *bufio.Scanner
	words       []string
	nextWordIdx func() int
	initWordIdx func(int)
}

func NewScannerEx(stdin io.Reader) *ReaderEx {
	var this ReaderEx
	var idx int
	var wordsCnt int
	this.baseScanner = bufio.NewScanner(stdin)
	this.baseScanner.Buffer(make([]byte, 0), 1E+11)
	this.nextWordIdx = func() int {
		cur := idx
		idx = (idx + 1) % wordsCnt
		return cur
	}
	this.initWordIdx = func(wc int) {
		idx = 0
		wordsCnt = wc
	}
	return &this
}

func (me *ReaderEx) Scan(doSplit bool) (isScanned bool) {
	isScanned = me.baseScanner.Scan()
	if doSplit {
		me.words = strings.Fields(me.baseScanner.Text())
	} else {
		me.words = []string{me.baseScanner.Text()}
	}
	me.initWordIdx(len(me.words))
	return
}

func (me *ReaderEx) nextBytes() []byte {
	return []byte(me.words[me.nextWordIdx()])
}
func (me *ReaderEx) nextString() string {
	return me.words[me.nextWordIdx()]
}

type StringArray []string

func (me *ReaderEx) nextStringArray() StringArray {
	return me.words[me.nextWordIdx():]
}

func (me StringArray) toStrings() []string {
	return me
}

func (me StringArray) toInts() []int {
	strValues := me.toStrings()
	values := make([]int, len(strValues))
	for i, v := range strValues {
		n, err := strconv.Atoi(v)
		if err != nil {
			panic(err)
		}
		values[i] = n
	}
	return values
}
func (me *ReaderEx) nextInt() int {
	n, err := strconv.Atoi(me.words[me.nextWordIdx()])

	defer func() {
		if err != nil {
			panic(fmt.Sprintf("getInt(%d)", n))
		}
	}()
	return n
}

func pow(x, y, mod int) (ans int) {

	ans = 1
	for bit := 1 << uint(math.Floor(math.Log2(float64(y)))); ; bit >>= 1 {
		if y&bit != 0 {
			ans *= x
			if mod > 0 {
				ans %= mod
			}
		}
		if bit <= 1 {
			return
		}
		ans *= ans
		if mod > 0 {
			ans %= mod
		}
	}
}

type factType struct {
	prime int
	count int
}

func fact(n int) (facts []*factType) {

	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			fa := factType{prime: i}
			for n%fa.prime == 0 {
				n /= fa.prime
				fa.count++
			}
			facts = append(facts, &fa)
		}
	}
	if n > 1 {
		facts = append(facts, &factType{prime: n, count: 1})
	}
	return facts
}
func dec2bin(n int) (ret []bool) {
	for bit := 1 << uint(math.Floor(math.Log2(float64(n)))); ; bit >>= 1 {
		ret = append(ret, n&bit != 0)

		if bit <= 1 {
			return
		}
	}

}

func abs(v int) int {
	if v < 0 {
		v = -v
	}
	return v
}

func b2i(b bool) (i int) {
	if b {
		i = 1
	} else {
		i = 0
	}
	return
}

func solve(stdin io.Reader, stdout io.Writer) {

	r := NewScannerEx(stdin)
	r.Scan(true)
	n, k := r.nextInt(), r.nextInt()

	minInt := func(a int, vs ...int) int {
		for i := range vs {
			v := &vs[i]
			if a > *v {
				a = *v
			}
		}
		return a
	}
	x := n % k
	fmt.Fprintln(stdout, minInt(x, k-x))
}


Measured memory_bytes: 640
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
signed main(){
  ll ans;
  bool al9=true;
  string n;
  cin >> n;
  for(int i=1;i<n.size();i++){
    if(n[i]!='9'){
      al9 = false;
      break;
    }
  }
  ans = n[0]-'0' + 9*(n.size()-1);
  if(!al9){
    ans--;
  }
  cout << ans << endl;
}


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

int main() {
  int N;
  string S;
  int l;
  int sum = 0;
  
  cin >> N >> S;
  l = N-1;
  for(int i=0;i<N;++i){
    if(i == l) break;
    if(S.at(i) == 'W'){
      for(int j=l;j>i;--j){
        if(S.at(j) == 'R'){
          swap(S.at(i),S.at(j));
          l = j-1;
          sum += 1;
          break;
        }
        if(j == i+1) l = j;
      }
    }
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 3728
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
int main(void){
long int A3,A1,A2,r;
scanf("%ld" "%ld",&A1,&A2);
if (A1>A2){
	A3=A1;
	A1=A2;
	A2=A3;
}
A3=A1*A2;
  r = A2 % A1;
  while(r!=0){
     A2= A1;
    A1 = r;
   r = A2 % A1;
  }
printf("%ld",A3/A1);
}

Measured memory_bytes: 128
#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;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T>& V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> >& Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T>& mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }
template<typename T>vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t,const V &v){t=v;}
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t,const V &v){for(auto &e:t) fill_v(e,v);}
/*
 <url:https://atcoder.jp/contests/abc142/tasks/abc142_a>
 問題文============================================================
 =================================================================
 解説=============================================================
 (N-N/2)/Nが答え
 ================================================================
 */

template<class Type>
Type solve(Type res = Type()){
    int N; cin >> N;
    res = (N-N/2)/(double)N;
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    // solve(0);
    cout << fixed << setprecision(15) << solve<double>() << endl;
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 998244353
#define llMAX 9223372036854775807
#define llMIN -9223372036854775808
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

ll n,m,k;



ll moddiv(ll a,ll b){
	ll x0=MOD,x1=b,x2,n0=0LL,n1=1LL,n2,t=a%b,m,ans;
	if (t==0) return a/b;
		for(int i=0;i<900;i++){
      m=x0/x1;
      x2=x0-x1*m;
      n2=(n0-m*n1)%MOD;
      if (x2==1){
        ans=(n2+MOD)%MOD;
        break;
      }
      x0=x1;x1=x2;
      n0=n1;n1=n2;
    }
	return (a+((t*ans)%MOD)*b-t)/b;
}
//剰余の割ざん

//aのn乗 mod c
ll expmod(ll a,ll n){
  ll ans=1LL,aa=a,beki=n;
  for(int i=0;i<64;i++){
    if (beki%2==1) ans=ans*aa%MOD;
    aa=aa*aa%MOD;
    beki/=2;
    if (beki==0)break;
  }
  return ans;
}

/*
//nCk
vi mulmod(500001);//0!,1!,2!,3!,4!,,,,
void first_nCk(){
  mulmod[0]=1;
  for(ll i=1;i<500001;i++){
    mulmod[i]=mulmod[i-1]*i%MOD;
  }
}
ll nCk(ll nn,ll kk){
  return moddiv(mulmod[nn],mulmod[kk]*mulmod[nn-kk]%MOD);
}
*/




int main(){
  ll ans=0;
  cin >> n >> m>>k;

  vi nck(n);
  ll tmp=1;
  for(ll i=0;i<n;i++){
    nck[i]=tmp;
    tmp=tmp*(n-1-i)%MOD;
    tmp=moddiv(tmp,i+1);
  }



  k++;  
  tmp=m;
  for(ll j=0;j<n-k;j++){
    tmp=tmp*(m-1)%MOD;
  }


  //m*(m-1)^(n-k)
  

  for(ll i=0;i<k;i++){
    ans=(ans+nck[n-k+i]*tmp)%MOD;
    tmp=tmp*(m-1)%MOD;

  }
  /*
  REP(i,n){
    cout<<nck[i]<<endl;
  }
  */
  cout<<ans<<endl;
  return 0;
}

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


int main() {
  long long int a,b,k;
  cin >> a >> b >> k;
  if(a+b<=k) cout << 0 << " " << 0 << endl;
  else if (a<k && k<a+b)  cout << 0 << " " << a+b-k << endl;
  else {
      cout << a-k << " " << b << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(),a.end()
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    vector<int> dp(1000001,0);
    vector<int> dp2(1000001,0);
    iota(all(dp),0);
    iota(all(dp2),0);
    for(int i=2;(i*(i+1)*(i+2)/6)<=1000000;i++){
        int po=(i*(i+1)*(i+2)/6);
        for(int j=0;j+po<=1000000;j++){
            dp[j+po]=min(dp[j+po], dp[j]+1);
        }
        if(po%2==0)continue;
        for(int j=0;j+po<=1000000;j++){
            dp2[j+po]=min(dp2[j+po], dp2[j]+1);
        }
    }
    while(cin>>n,n){
        cout<<dp[n]<<" "<<dp2[n]<<endl;
    }
    return 0;
}


Measured memory_bytes: 10572
use std::io;

// I'm really really not sure if this is the right way
fn get_line() -> Vec<char> {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).ok();
    buf.chars().collect()
}

fn solve(input: Vec<char>) -> u32 {
    input.iter().skip_while(|&c| *c != 'A').fold((0,0), |(t,buf), &c| {
        match c {
            'Z' => (1+t+buf,0),
            _ => (t,buf+1)
        }
    }).0
}

fn main() {
    let input = get_line();
    println!("{}", solve(input));
}

Measured memory_bytes: 1404
#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 m, d;
    cin >> m >> d;
    int cnt = 0;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= d; j++)
        {
            if (j / 10 <= 1 || j % 10 <= 1)
            {
                continue;
            }
            if (i == (j / 10) * (j % 10))
            {
                cnt++;
            }
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
N,K=map(int,input().split())
R,S,P=map(int,input().split())
T=input()
A=[0]*(len(T))
for i in range(len(T)):
 A[i]=T[i]
BR=[0]*K
BS=[0]*K
BP=[0]*K
for j in range(N):
 s=j%K
 f=int(j/K)
 if f==0:
  if A[j]=="r":
   BP[s]=P
  elif A[j]=="s":
   BR[s]=R
  else:
   BS[s]=S 
 else:
  if A[j]=="r":
   a=max(BS[s],BP[s])
   b=max(BR[s],BP[s])
   c=max(BR[s],BS[s])+P
   BR[s]=a
   BS[s]=b
   BP[s]=c
  elif A[j]=="s":
   a=max(BS[s],BP[s])+R
   b=max(BR[s],BP[s])
   c=max(BR[s],BS[s])
   BR[s]=a
   BS[s]=b
   BP[s]=c
  else:
   a=max(BS[s],BP[s])
   b=max(BR[s],BP[s])+S
   c=max(BR[s],BS[s])
   BR[s]=a
   BS[s]=b
   BP[s]=c
d=0
for k in range(K):
 d+=max(BR[k],BS[k],BP[k])
print(d)

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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using tll = tuple<ll,ll,ll>;
using vtll = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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

const ll INF = 1e9;
const ll MOD = 1e9+7;
const ll LINF = 1e18;


ll dp[10005][2][105];

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  string s; cin>>s;
  ll d; cin>>d;
  ll n=s.size();
  
  dp[0][0][0]=1;
  rep(i,n) rep(j,2) rep(k,d){
    ll now=s[i]-'0';
    rep(nxt,10){
      if(nxt>now&&j==0) continue;
      ll nj=j,nk;
      if(nxt<now) nj=1;
      nk=(k+nxt)%d; // 各桁の和より、k*10とする必要はない
      (dp[i+1][nj][nk]+=dp[i][j][k])%=MOD;
    }
  }
  // 対象となる数字は1以上なので、0に対応する1個分を減算する必要がある
  // ちなみに0とは、初期化時のdp[0][0][0]に対応する
  ll ans=(dp[n][0][0]+dp[n][1][0]+MOD-1)%MOD;
  cout<<ans<<endl;
}

Measured memory_bytes: 16768
import sys
input = sys.stdin.buffer.readline

def main():
    N,M = map(int,input().split())
    x = list(map(int,input().split()))
    y = list(map(int,input().split()))
    MOD = 10**9+7
    
    ax,ay = 0,0
    for i,num in enumerate(x):
        ax += num*(i-(N-i-1))
        ax %= MOD
    
    for j,num in enumerate(y):
        ay += num*(j-(M-j-1))
        ay %= MOD
        
    print((ax*ay)%MOD)

if __name__ == "__main__":
    main()


Measured memory_bytes: 16988
import sys
from string import ascii_lowercase

o = dict(zip(ascii_lowercase, range(26)))

s, t = sys.stdin.read().split()

def main():
    g1 = [set() for _ in range(26)]
    g2 = [set() for _ in range(26)]
    for i in range(len(s)):
        a = o[s[i]]; b = o[t[i]]
        g1[a].add(b); g2[b].add(a)

    for i in range(26):
        if len(g1[i]) >= 2 or len(g2[i]) >= 2:
            print('No')
            return
    print('Yes')

if __name__ ==  '__main__':
    main()

Measured memory_bytes: 4472
#include<stdio.h>
#define ll long long
int d[100100] = {0};
int main(){
    int n, q;
    scanf("%d",&n);
    ll a[n];
    ll sum = 0;
    for(int i = 0; i < n; i++){
        scanf("%lld",&a[i]);
        sum += a[i];
        d[a[i]]++;
    }
    scanf("%d",&q);
    ll b[q], c[q];
    for(int i = 0; i < q; i++)
        scanf("%lld%lld",&b[i],&c[i]);
    for(int i = 0; i < q; i++){
        ll di = c[i] - b[i];
        ll p = d[b[i]];
        d[b[i]] = 0;
        d[c[i]] += p;
        sum += p * di;
        printf("%lld\n",sum);
    }
    return 0;
}

Measured memory_bytes: 4452
import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    SC = [il() for _ in range(M)]

    for n in range(pow(10, N)):
        if len(str(n)) == N and all(str(n)[s - 1] == str(c) for s, c in SC):
            print(n)
            exit()

    print(-1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <iostream>
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#include <algorithm>
#include <bits/stdc++.h>
#define MOD 1000000007
#define ll long long
#define l long
#define mm(arr) memset(arr, 0, sizeof(arr))
#define scanArray(a,n) for(int i = 0; i < n; i++){cin >> a[i]}
using namespace std;

int main(){
    FAST
    ll a,b,c,d,x,y; cin >> a >> b >> c >> d;
    x=max(a*c,a*d);
    y=max(b*c,b*d);
    cout << max(x,y) << endl;



    return 0;
}



Measured memory_bytes: 3640
#include<iostream>
#include<cmath>
#define min(a, b) (a <= b) ? a : b

int main(){
  long n;
  std::cin >> n;
  
  long sq = std::sqrt(n);
  long curr_steps = 0, min_steps = n-1;
  for(long i = 2; i <= sq+1; i++){
    if(n % i == 0){ 
    	curr_steps = i + n/i - 2;
      	min_steps = min(curr_steps, min_steps);
    }
  }
  std::cout << min_steps << std::endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb(x) push_back(x)
#define all(x) x.begin(), x.end()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = 1e9;
const ll INF = 1e18;
const ld EPS = 1e-10;

int main(){
    int N;
    cin >> N;
    deque<int> deq;
    int a;
    rep(i, N){
        cin >> a;
        if(i&1) deq.push_front(a);
        else deq.push_back(a);
    }
    while(!deq.empty()){
        if(N&1) cout << deq.back() << ' ', deq.pop_back();
        else cout << deq.front() << ' ', deq.pop_front();
    }
    cout << endl;
}

Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
using ll = long long;
#define vl vector<long long>
#define vvl vector<vector<long long>>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
using pll = pair<long long,long long>;
#define cY cout<<"Yes"<<endl
#define cN cout<<"No"<<endl
const long long INF = 1LL << 60;
const long long MOD = 1000000007;
const long double pi = (acos(-1));
#define pb push_back

//最大最小の入れ替え
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

//約数列挙
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    sort(ret.begin(), ret.end()); // 昇順に並べる
    return ret;
}
//コンビネーション
ll nCr(ll n, ll r) {
    ll ans = 1;
    for (ll i = n; i > n - r; --i) {
        ans = ans*i;
    }
    for (ll i = 1 ; i < r + 1; ++i) {
        ans = ans / i;
    }
    return ans;
}
//素因数分解
map< ll, ll > prime_factor(ll n) {
  map< ll, ll > ret;
  for(ll i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

//切り上げの割り算は(a + b - 1) / bでできる
//時間を意識しろ
//コードテストちゃんとして
//画面とにらめっこするな書け
//WA出すたびにABCは五億円払え
//わからない問題はとばせ
//躊躇なくぐぐれ

//ここから
int main(){
    ll N;
    cin>>N;
    if(N>=64){
        cout<<64<<endl;
    }else if(N>=32){
        cout<<32<<endl;
    }else if(N>=16){
        cout<<16<<endl;
    }else if(N>=8){
        cout<<8<<endl;
    }else if(N>=4){
        cout<<4<<endl;
    }else if(N>=2){
        cout<<2<<endl;
    }else{
        cout<<1<<endl;
    }
}

Measured memory_bytes: 256
n = int(input())
z = []
pre = 0
for _ in range(n):
    i = int(input())
    if i != pre:
        z.append(i)
    pre = i
n = len(z)
dp = [1] * (n+1)
dpp = [0] * 2 * 10 ** 5
for i in range(n):
    dp[i+1] = dp[i] + dpp[z[i]-1]
    dpp[z[i]-1] += dp[i]
    dp[i+1] %= 10 ** 9 + 7
print(dp[n])

Measured memory_bytes: 62552
def cal(n,s):
	cum = np.cumsum(s == 'W')
	val = [-1]*n
	for i in range(n):
		W = cum[i-1]  if i-1 >= 0 else 0 #i <- W
		H = (n-i-1) - (cum[-1] - cum[i])	 #i -> H 
		val[i] = W+H
	return min(val)

import numpy as np

n = int(input())
s = np.array(list(input()))
print(cal(n,s))


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

int main(){

  string s;

  cin>>s;

  int cnt=0;
  for(int i=0;i<s.size()-1;i++){
    if(s[i]>=s[i+1]) cnt++;
  }

  if(s[0]=='A') cnt++;

  cout<<cnt<<endl;
  
  return 0;
}

Measured memory_bytes: 3208
N=int(input())
ES = []
for i in range(N):
    x,l = list(map(int,input().split()))
    ES.append((x+l,x-l+1))
 
ES = sorted(ES)
# print(ES)

sel = []
cur = None
ans = 0
for E,S in ES:
    if cur is None or cur < S:
        sel.append((S,E))
        cur = E
        ans += 1
print(ans)



Measured memory_bytes: 60888
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <limits>
#include <set>
#include <stack>
#include <queue>
#include <list>
#include <cmath>

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

int main() {
    int n;
    double ansInv = 0;
    cin >> n;
    rep(i, n) {
        double a;
        cin >> a;
        ansInv += 1/a;
    }

    double ans = 1 / ansInv;
    cout << ans << endl;

}

Measured memory_bytes: 256
#include<string>
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>
using ll = long long;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i,x) for(int i=1;i<=(int)(x);i++)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(int i=((int)(x) - 1 * 100);i>0;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define vll vector<ll>
#define vi vector<int>
#define mp make_pair
#define vpll vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>
#define ctoi(c) (c) -'0'
using namespace std;
int n, m;
int main(void) {
	string s;
	cin >> s;
	int sz = s.size()-1;
	ll sum = 0;
	rep(i, 1 << sz) {
		string tm = "";
		rep(j, sz+1) {
			tm += s[j];
			if (i >> j & 1) {
				sum += stoll(tm);
				tm = "";
			}
			if (tm != "" && j == sz) {
				sum += stoll(tm);
			}
		}
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

/**
 * Card Game
 */
public class Main {
    private static final int WIN = 3;
    private static final int DRAW = 1;

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

        int count[] = new int[2];   // 太郎[0]と花子[1]のポイントカウンター
        int n = scan.nextInt();
        for (int i = 0; i < n; i++) {
            int point = scan.next().compareToIgnoreCase(scan.next());
            if (point > 0) {
                count[0] += WIN;
            } else if (point < 0){
                count[1] += WIN;
            } else {
                count[0] += DRAW;
                count[1] += DRAW;
            }
        }
        System.out.println(count[0] + " " + count[1]);
    }
}

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    int mx = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        a[i] = x;
        mx = max(mx, x);
    }
    cout << mx << " ";
    int target = mx / 2;
    int ans = 0;
    int mn = 1001001001;
    for (int j = 0; j < n; ++j) {
        if (a[j] == mx) continue;
        if (mn > abs(a[j] - target)) {
            mn = abs(a[j] - target);
            ans = a[j];
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 768
#include <cstdio>
#define Maxn 200000
char s[Maxn+5];
int n;
int main(){
	scanf("%s",s+1);
	while(s[++n]!='\0');
	n--;
	int len=0;
	int ans=0;
	for(int i=1,j;i<=n;i+=j){
		j=1;
		ans++;
		if(j!=len){
			len=j;
			continue;
		}
		if(s[i]==s[i-1]){
			j++;
			if(i==n){
				ans--;
				break;
			}
			len=j;
		}
		else{
			len=j;
		}
	}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5,mo=1e9+7;
void Inverse(int p,int a[],int n){//线性求<=n的数%p意义下的逆元 
	a[1]=1;
	for(int i=2;i<=n;i++){
		a[i]=1ll*(p-p/i)*a[p%i]%p;
	}
}
int inv[N],fac[N];
int C(int n,int m){
	return 1ll*fac[n]*inv[m]%mo*inv[n-m]%mo;
}
int main(){
	int a,b,c,d;scanf("%d%d%d%d",&a,&c,&b,&d);
	Inverse(mo,inv,1e6+2);
	fac[0]=inv[0]=1;for(int i=1;i<=2000002;i++)fac[i]=1ll*fac[i-1]*i%mo,inv[i]=1ll*inv[i]*inv[i-1]%mo;
	int ans=0,sum=0;
	for(int i=a;i<=b;i++)
		(ans+=C(d+i+1,i+1)-C(i+c,i+1))%=mo;//朱世杰恒等式
	printf("%d",(ans+mo)%mo);
	return 0;
}

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

int main() {
  
  int N, K; cin >> N >> K; int ans = 0;
  
  for (int i = 0; i < N; i++) {
    int x; cin >> x;
    int lengthA = x * 2;
    int lengthB = abs(x - K) * 2;
    ans += min(lengthA, lengthB);
  }
  
  cout << ans << endl;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int R,G,B,N;
  cin >> R >> G >> B >> N;
  int ans = 0;
  for(int i = 0;i <= N/R;i++){
    for(int j = 0;j <= N/G;j++){
      if((N-R*i-G*j)% B == 0 && N-R*i-G*j >= 0)ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long
 
const int N = 305;
 
int n, c[N][N][N], dp[N][N][N], f[N][N], mod = 998244353;
string s;
 
void go(int idx, int z, int o){
    if(c[idx][z][o]) return;
    c[idx][z][o] = 1;
    if(z >= 2) go(idx, z - 1, o);
    if(o >= 2) go(idx, z, o - 1);
    if(o >= 1 && z >= 1){
        go(idx, z - 1, o);
        go(idx, z, o - 1);
    }
    if(idx < n && s[idx] == '1' && z){
        go(idx + 1, z, o);
        go(idx + 1, z - 1, o + 1);
    }
    if(idx < n && s[idx] == '0' && o){
        go(idx + 1, z, o);
        go(idx + 1, z + 1, o - 1);
    }
    if(idx < n && s[idx] == '0' && z){
        go(idx + 1, z, o);
    }
    if(idx < n && s[idx] == '1' && o){
        go(idx + 1, z, o);
    }
    if(idx + 1 < n && (s[idx] == '0' || s[idx + 1] == '0')){
        go(idx + 2, z + 1, o);
    }
    if(idx + 1 < n && (s[idx] == '1' || s[idx + 1] == '1')){
        go(idx + 2, z, o + 1);
    }
}
int solve(int idx, int z, int o){
    if(idx == n && z == 0 && o == 0) return 1;
    int &ret = dp[idx][z][o];
    if(ret != -1) return ret;
    ret = 0;
    // 0
    if(s[idx] == '0') ret += solve(idx + 1, z, o);
    else if(z) ret += solve(idx, z - 1, o);
    if(ret >= mod) ret -= mod;
    // 1
    if(s[idx] == '1') ret += solve(idx + 1, z, o);
    else if(o) ret += solve(idx, z, o - 1);
    if(ret >= mod) ret -= mod;
    return ret;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(dp, -1, sizeof dp);
    cin >> s;
    n = s.size();
    go(0, 0, 0);
    vector <int> suff(n + 1);
    for(int i = n - 1 ; i >= 0 ; i--){
        suff[i] = suff[i + 1];
        suff[i] += s[i] - '0';
    }
    memset(f, -1, sizeof f);
    for(int i = 0 ; i <= n ; i++){
        for(int z = 0 ; z <= n ; z++){
            for(int o = 0 ; o <= n ; o++){
                if(c[i][z][o]){
                    int zeros = n - i - suff[i] + z;
                    int ones = suff[i] + o;
                    f[zeros][ones] = i;
                }
            }
        }
    }
    int ans = 0;
    for(int z = 0 ; z <= n ; z++){
        for(int o = 0 ; o <= n ; o++){
            int i = f[z][o];
            if(i == -1) continue;
            int zeros = z - (n - i - suff[i]);
            int ones = o - suff[i];
            ans += solve(i, zeros, ones);
            if(ans >= mod) ans -= mod;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 142720
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;
const ll INF=(ll)1e18+10;
const double PI=acos(-1);

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int dy[]={-1,1,0,0};
int dx[]={0,0,-1,1};

void solve(int cn) {
    ll N,D; cin>>N>>D;

    int cnt=0;
    ll x,y;
    for (int i = 0; i < N; ++i) {
        cin>>x>>y;
        if(x*x+y*y<=D*D) cnt++;
    }
    cout<<cnt<<endl;

}


#define SINGLE
int main() {
#ifdef SINGLE
    solve(1);
#else
    int N;
    cin>>N;
    for(int i=0;i<N;++i){
        solve(i);
    }
#endif
    return 0;
}


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

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second

template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> pip;

const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS = 1e-10;

int n;
int a[2][100], d[2][100];
int dp[2][100];

int main() {
	while (cin >> n, n) {
		REP(i, n) scanf("%d", a[0] + i);
		REP(i, n) scanf("%d", a[1] + i);
		
		memset(d, -1, sizeof(d));
		fill(dp[0], dp[2], INF);
		
		REP(i, 2) {
			int last = -1;
			REP(j, n) {
				if (a[i][j] == 2) d[i][j] = last;
				else last = j;
			}
			
			last = -1;
			for (int j = n - 1; j >= 0; j--) {
				
				if (a[i][j] == 1) {
					if (last == -1) last = j;
					d[i][j] = last;
				}
				else last = -1;
				
				if (a[i][j] == 0) d[i][j] = j;
			}
			
		}
		
		queue<pii> que;
		REP(i, 2) {
			if (d[i][0] != -1) {
				que.push(pii(i, d[i][0]));
				dp[i][d[i][0]] = 0;
			}
		}
		
		while (!que.empty()) {
			int idx = que.front().fi;
			int p = que.front().se;
			que.pop();
			
			int nidx = !idx;
			REP(i, 3) {
				int np = d[nidx][min(p + i, n - 1)];
				if (chmin(dp[nidx][np], dp[idx][p] + 1))
					que.push(pii(nidx, np));
			}
		}
		
		int ans = min(dp[0][n - 1], dp[1][n - 1]);
		if (ans == INF) puts("NA");
		else cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3132
N=int(input())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
pre=sum(A)
 
for i in range(N):
  if B[i]<=A[i]:
    A[i]-=B[i]
  else:
    A[i+1]=max(0, A[i+1]-B[i]+A[i])
    A[i]=0
print(pre-sum(A))

Measured memory_bytes: 24108
#include <bits/stdc++.h>
using namespace std;
int a[101];
int b[101];
int main(){
int n;
  cin>>n;
  for(int i=1;i<n;i++){
  cin>>b[i];}
  a[1]=b[1];
  a[2]=b[1];
  for(int i=2;i<n;i++){
  	if(b[i]>=b[i-1]){
      a[i+1]=b[i];
    }
    else{
    	a[i+1]=a[i]=b[i];
    }
  }
  int sum=0;
  for(int i=1;i<=n;i++){
  	sum+=a[i];
  }
  cout<<sum<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)
#define mp std::make_pair

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> P;
typedef std::pair<int,P> State;

const int INF = 1001001001;
const int MAX_N = 26;

// S N E W(南北東西)
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

class UnionFind{
public:
    UnionFind(int n){
        REP(i, n){
            par[i] = i;
            rank[i] = 0;
        }
    }
    int find(int x){
        if(x == par[x])return x;
        return par[x] = find(par[x]);
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y){return;}
        
        if(rank[x] > rank[y]){
            par[y] = x;
        }else{
            par[x] = y;
            if(rank[x] == rank[y]){rank[y]++;}
        }
    }
private:
    int rank[MAX_N], par[MAX_N];
};

int main(){
    int N;
    while(std::cin >> N, N){
        int deg_in[26], deg_out[26];

        std::fill(deg_in, deg_in+26, 0);
        std::fill(deg_out, deg_out+26, 0);

        UnionFind uf(26);

        REP(i, N){
            std::string s;
            std::cin >> s;

            // printf("%c -> %c\n", s[0], s[s.size()-1]);

            deg_out[s[0]-'a'] += 1;
            deg_in[s[s.size()-1]-'a'] += 1;
            uf.unite(s[0]-'a', s[s.size()-1]-'a');
        }

        int scc = 0;
        bool allZero = true;
        REP(i, 26){
            if((deg_in[i] > 0 || deg_out[i] > 0) && i == uf.find(i)){scc += 1;}
            if(deg_in[i] - deg_out[i] != 0){allZero = false;}
        }

        if(scc == 1 && allZero){puts("OK");}
        else{puts("NG");}
    }
}

Measured memory_bytes: 1180
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)  
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

ll modpow(ll n,ll k){
  if(k == 1){
    return n;
  }else if(k == 0){
    return 1;
  }else if(k%2==0){
    ll memo = modpow(n,k/2)%MOD;
    return memo*memo%MOD;
  }else{
    return n * modpow(n,k-1)%MOD;
  }
}

int main(){

  int a,b,c,d,e,k;
  cin>>a>>b>>c>>d>>e>>k;
  if((e-a)>k){
    cout<<":("<<endl;
  }else{
    cout<<"Yay!"<<endl;
  }

 

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h> 
using namespace std;
int main()
{
	long long n;
	cin>>n;
	long long a[n+1];
	for(long long i=1;i<=n;i++)
		cin>>a[i];
	long long tall=0,ans=0;
	for(long long i=1;i<=n;i++)
	{
		if(a[i]<tall)
			ans+=tall-a[i];
		tall=max(tall,a[i]);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 5184
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
using P = pair<ll,ll>;
const ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REPS(i,n) for(ll (i)=1;(i)<=(n);(i)++)
#define RREP(i,n) for(ll (i)=(n-1);(i)>=0;(i)--)
#define RREPS(i,n) for(ll (i)=(n);(i)>0;(i)--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());

template<class T> inline void chmin(T& a, T b){
    if (a > b){
        a = b;
    }
}

template<class T> inline void chmax(T& a, T b){
    if (a < b){
        a = b;
    }
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    string A,B,C;
    cin >> A >> B >> C;
    cout << (A[A.size()-1] == B[0] && B[B.size()-1] == C[0] ? "YES" : "NO") << "\n";
}

Measured memory_bytes: 256
import sys
import collections
import bisect


def main():
    n = int(input())
    ac, bc = collections.Counter([str(i + 1)[0] + str(i + 1)[-1] for i in range(
        n)]), collections.Counter([str(i + 1)[-1] + str(i + 1)[0] for i in range(n)])
    print(sum(ac[i] * bc[i] for i in ac.keys()))


if __name__ == '__main__':
    main()


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

const int N=2e5+100;
const int mod=1e9+7;
typedef long long ll;


typedef pair<int,int> pa;

int fa[N];

int _find(int root)
{
     if(fa[root]==root)
        return root;
     return fa[root]=_find(fa[root]);
}
int p[N];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
     int n,m;
     cin>>n>>m;
     for(int i=1;i<=n;i++) fa[i]=i;

     for(int i=1;i<=n;i++){
        cin>>p[i];
     }
     for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        int xx=_find(x);
        int yy=_find(y);
        if(xx!=yy){
            fa[xx]=yy;
        }
     }
  //   cout<<10<<endl;
     int ans=0;
     for(int i=1;i<=n;i++){
            int x=_find(i);
            int y=_find(p[i]);
        if(x == y) ans++;
     }
     cout<<ans<<endl;
    return 0;
}


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

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define AND(x,y,z) 
#define DUMP(xs) for (auto x:xs) cout<<x<<' ';cout<<endl
#define DUMPP(xs) for (auto x:xs) cout<<'('<<x.first<<','<<x.second<<')';cout<<endl
#define FOR(i,a,b) for (ll i=(ll)(a);i<(ll)(b);++i)
#define OUT(x) cout<<x<<endl
#define REP(i,n) FOR(i,0,n)
#define YES(cond) cond ? OUT("YES") : OUT("NO")
#define Yes(cond) cond ? OUT("Yes") : OUT("No")

template<class T> T gcd(const T x,const T y){if(!y){return x;}return gcd(y,x%y);}
template<class T> T lcm(const T x,const T y){return x/gcd(x,y)*y;};
template<class T> T modpow(T x,T n,const T mod) {
  T res=1;while(n>0){if(n%2)res=res*x%mod;x=x*x%mod;n/=2;};return res;
}
template<class T> T modinv(T x,const T mod){return modpow(x,mod-2,mod);}
template<class T> bool alltrue(const T &a){return all_of(ALL(a),[](bool x){return x;});}
template<class T> bool anytrue(const T &a){return any_of(ALL(a),[](bool x){return x;});}
template<class T> bool contain(const T &a,const T &b){for(auto x:b){if (a.find(x)==a.end()){return false;}}return true;}
template<class T> bool mmax(T &m,const T q){ if (m < q) {m = q; return true;} else return false; }
template<class T> bool mmin(T &m,const T q){ if (m > q) {m = q; return true;} else return false; }
template<class T> int siz(const T &a) {return (int)a.size();}
template<class T> set<T> devisers(T n) {
  set<T> res;for(T i=1;i<(T)sqrt(n)+1;i++){if(n%i==0){res.insert(i);res.insert(n/i);}}return res;
}
template<class T> void concat(T &a, const T &b){a.insert(a.end(),b.begin(),b.end());}
template<class T> void getand(const T &a,const T &b,T &c) {
  set_intersection(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.end()));
}
template<class T> void getor(const T &a,const T &b,T &c) {
  set_union(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.end()));
}

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

const ll MOD=1e9+7;
const int MAX=1e7+100;

int main() {
  ll N,K;cin>>N>>K;
  vector<ll> AS(N);

  REP(i,N) {
    cin>>AS[i];
    AS[i]--;
  }

  vector<ll> sumAS(N+1,0);
  REP(i,N) sumAS[i+1]=(sumAS[i]+AS[i])%K;

  map<ll,ll> mp;
  ll ans=0;
  REP(i,N+1) {
    if (i-K>=0) mp[sumAS[i-K]]--;
    ans += mp[sumAS[i]];
    mp[sumAS[i]]++;
  }
  OUT(ans);

  return 0;
}

Measured memory_bytes: 15872
#include <bits/stdc++.h>
#define INF 2e9
using namespace std;
typedef long long llong;
typedef long double ldouble;

using Graph = vector<vector<int>>;

int main()
{
  string S;
  cin >> S;
  if(S == "AAA" || S == "BBB") cout << "No" << endl;
  else cout << "Yes" << endl;
}


Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<utility>
#include<queue>
using namespace std;
#define REP(i, a,b) for(i=a;i<b;i++) 
#define REP1(i,b,a) for(i=b-1;i>=a;i--)
#define output(x) cout<<x<<endl;
#define pb(x) push_back(x);
typedef long long int ll;
const int MAX = 510000;
const int MOD = 1000000007;

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

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

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

long long ruijyo(ll n, ll k) {
	if (k == 0) {
		return 1;
	}
	ll sum = 1;
	ll i;
	REP(i, 0, k) {
		sum *= n;
		sum %= MOD;
	}
	return sum;
}

int main()
{
	ll  i, j, k, l, m,n, sum, flag, N,  M, K, H, W, B,C,D,x,y;
	sum = 0;
	flag = 0;
	cin >> x >> y;
	k = abs(abs(x) - abs(y));
	if (x <= y) {
		if (x*y >= 0){
			k += 0;
		}
		else {
			k += 1;
		}
	}
	else {
		if (x*y > 0) {
			k += 2;
		}
		else {
			k += 1;
		}
	}
	output(k);
	return 0;
	

	
}













Measured memory_bytes: 256
n, m = list(map(int, input().split()))

a = [0]*(n+10)
w = [0]*(n+10)

for i in range(0, m):
    p, s = input().split()
    p = int(p)
    if ((s == "AC")&(a[p] == 0)):
        a[p] += 1
    if ((s == "WA")&(a[p] == 0)):
        w[p] += 1
ac = 0
wa = 0
for i in range(0, n+10):
    ac += a[i]
    if a[i]==1:
        wa += w[i]
print(str(ac)+" "+str(wa))

Measured memory_bytes: 45656
N = int(input())
CSF = [list(map(int,input().split())) for i in range(N-1)]
T = []

for j in range(N):
    t = 0
    for i in range(j,N-1):
        C,S,F = CSF[i]
        if t >= S:
            if t%F == 0:
                t += C
            else:
                t = (1+t//F)*F + C
        else:
            t = S+C
    T.append(t)
print(*T, sep="\n")

Measured memory_bytes: 43632
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) int((x).size())
#define debug(x) cout << #x << ":" << x << ' ';
#define debugg(x) cout << #x << ":" << x << ' ' << "\n";
#define endl '\n'
#define ff first
#define ss second
#define L(X) ((X)<<1)
#define R(X) (((X)<<1)|1)
#define M(X,Y) (((X)+(Y))>>1)

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int MAXN = 1e3 + 7;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const long long int LLINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-9;
const double PI = acos(-1);

template<typename T>   T add(T x, T y, T m) { return ((x % m)  + (y % m)) % m;}
template<typename T>   T mul(T x, T y, T m) { return ((x % m) * (long long)(y % m)) % m;}
template<typename T>   T sub(T x, T y, T m) { return add(x, -y + m);}
template<typename T>   T gcd(T a, T b) { return b ? gcd(b, a % b) : a;}
template<typename T>   T lcm(T a, T b) { return a / gcd(a, b) * b;}

int lg2(long long x)   {   return 64 - __builtin_clzll(x) - 1;	}
int lg2(int x)   {   return 32 - __builtin_clzll(x) - 1;	}

struct pair_hash{
	template<class T1, class T2>
	size_t operator() (const pair<T1, T2> &p) const {
		auto h1 = hash<T1>{}(p.first);
		auto h2 = hash<T2>{}(p.second);
		return h1 ^ h2;
	}
};

int n, a[MAXN], b[MAXN], dp[10000007];


int solve(int h) {
	if(h <= 0) return 0;
	if(dp[h] != -1) return dp[h];

	int ans = INF;

	for(int i = 0 ; i < n ; ++i) {
		ans = min(ans, solve(h - a[i]) + b[i]);
	}

	return dp[h] = ans;
}

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

	int h;
	cin >> h >> n;

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

	memset(dp, -1, sizeof dp);

	cout << solve(h) << endl;

	return 0;
}

Measured memory_bytes: 39808
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#ifndef FAST_IO
 #define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);
#endif

#define FILE_IO freopen("input.txt","r",stdin)
#define int long long
#define f first
#define s second
#define endl '\n'
#define all(c) c.begin(),c.end()
#define bp __builtin_popcount
#define debug(x) cerr << #x << " = " << x << endl;

const int MOD = 1e9 + 7;
const int INF = 1e18;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>void print(T t){for(auto &it : t)cout<<it<<" ";}
inline int powerexp(int a, int b, int m = MOD){ int res = 1;while(b){if(b&1)res = res * a % m;a = a * a % m,b >>= 1;}return res % m;}
inline int modinv(int a){ return powerexp(a,MOD-2,MOD);}
inline int lcm(int a, int b){ int g = __gcd(a,b);return a/g*b;}
inline int add(int x, int y){ x += y; if (x >= MOD) x -=  MOD; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % MOD;}
inline int sub(int x, int y){ x -= y; if (x<0) x += MOD; return x ;}

//-------------------< start here >-------------------------// 

void solve(){
    int a, b;
    while(cin >> a >> b){
    cout << __gcd(a, b) <<  " " << lcm(a, b) << endl;
    }
}

//-----------------------------
//comment from here for TOPCODER 
int32_t main(){
   IOS;
   solve();
   //find();
   #ifdef LOCAL_DEFINE
   cerr << "time elapsed " << (double)clock()/CLOCKS_PER_SEC << endl;
   #endif
}



Measured memory_bytes: 3108
#include<iostream>

using namespace std;

int main()
{
    char a[3];
    cin>>a;
    if(a[0]=='7' || a[1]=='7' || a[2]=='7')
    {
        cout<<"Yes\n";
    }
    else
    {
        cout<<"No\n";
    }
    return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define repreverse(i, start, end) for (long long i = start; i >= end; --i)
#define all(x) (x).begin(), (x).end()
#define len(x) ((long long)(x).size())
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
using pll = pair<ll, ll>;
template<class T>void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T>void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
template<class T, class U>bool haskey(T mp, U key) { return mp.find(key) != mp.end(); }
template<class T, class U>bool isin(T el, U container) { return find(all(container), el) != container.end(); }
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; }
template<class T>bool even(T n) { return ! (n & 1); }
template<class T>bool odd(T n) { return n & 1; }
template<class T>ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T>ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
ll intpow(ll a,ll n){ll p=1;while(n){if(n&1)p*=a;a*=a;n>>=1;}return p;}
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;



int main()
{
        ll N, K;
        cin >> N >> K;
        vll x(N);
        rep(i, 0, N) cin >> x[i];

        ll ans = inf;
        rep(i, 0, N-K+1) {
                ll tmp = x[i+K-1] - x[i];
                ll c1 = tmp + abs(x[i+K-1]);
                ll c2 = tmp + abs(x[i]);
                chmin(ans, min(c1, c2));
        }
        cout << ans << endl;
}



Measured memory_bytes: 3968