akhauriyash/Code-Regression huggingface dataset:
package main

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

func main() {
	sc := NewScanner()

	s := sc.NextLine()

	curB := 0
	ans := 0

	for i := 0; i < len(s); i++ {
		if s[i] == 'B' {
			curB++
		} else {
			ans += curB
		}
	}
	fmt.Printf("%d\n", ans) // output for debug
}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			result = append(result, v)
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	result = append(result, v)

	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


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

class Dice{
    public:
    int f[6];
    Dice(){}
    void roll_x(){roll(1,4,6,3);} // to E
    void roll_y(){roll(1,2,6,5);} // to N
    void roll_z(){roll(2,3,5,4);} // 上から見て時計回り
    void roll(int i,int j,int k,int l){
        int t=f[i]; f[i]=f[j]; f[j]=f[k]; f[k]=f[l]; f[l]=t;
    }
    void move(char ch){
        if(ch == 'E') roll_x();
        if(ch == 'S') for(int i=0;i<3;i++) roll_y();
        if(ch == 'W') for(int i=0;i<3;i++) roll_x();
        if(ch == 'N') roll_y();
    }
};

int main(){
    Dice d;
    int n,x,y;
    for(int i=1;i<=6;i++) cin >> d.f[i];
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> x >> y;
        while(d.f[1]!=x){
            d.move('E');
            if(d.f[1]==x) break;
            d.move('N');
        }
        while(d.f[2]!=y){
            d.roll_z();
        }
        cout << d.f[3] << endl;
    }
    return 0;
}


Measured memory_bytes: 3076
import java.util.*;
public class Main {
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int h = sc.nextInt();
        int m = sc.nextInt();
        sc.close();
        double rad;
        double ans;

        rad = (double)((h*30)-(m*5.5));
        rad *= (rad<=0)?-1:1;
        rad = (rad>=180)?360-rad:rad;

        ans = (a*a)+(b*b)-((2*a*b)*(Math.cos(Math.toRadians(rad))));
        ans = Math.sqrt(ans);

        System.out.println(ans);

    }
}


Measured memory_bytes: 27148
<?php
while (true) {
    fscanf(STDIN, "%d %d", $a, $b);
    if ($a === 0 && $b === 0) {
        break;
    }else if ($a >= $b) {
        echo $b.' '.$a.PHP_EOL;
    }else{
        echo $a.' '.$b.PHP_EOL;
    }
}

Measured memory_bytes: 15204
open Batteries

let rec print_int_list = function
  | [] -> print_endline "DONE"
  | x :: xs -> Printf.printf "%d " x ; print_int_list xs

let () =
  let n, k = Scanf.scanf " %d %d " (fun n k -> (n, k)) in
  List.init n (fun _ -> Scanf.scanf " %d" (fun li -> li))
  |> List.sort (fun x y -> y - x)
  (* |> print_int_list *)
  |> List.take k |> List.fold_left ( + ) 0 |> Printf.printf "%d\n"


Measured memory_bytes: 3072
//////// Password 
// https://atcoder.jp/contests/abc140/tasks/abc140_a
// date: 2020-09-19T15:32:57.551766
// memo: 
    
//<editor-fold desc="my macro">

#include <bits/stdc++.h>
#ifdef LOCAL
    #include <my/dump.h>
#else
    #define dump(...) 42 
    #define dumpi(x) 42 
    #define dumpar(...) 42
#endif

typedef long long ll;
using namespace std;

#define repe(x, a) for(auto&& (x) : (a))
#define _overload3(_1, _2, _3, name, ...) name
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2,)(__VA_ARGS__)
#define _rep3(i, a, b) for(ll i=a, i##_len=(b);i<i##_len;i++)
#define _rep2(i, n) _rep3(i,0,n)
#define repd(...) _overload3(__VA_ARGS__,_repd3,_repd2,)(__VA_ARGS__)
#define _repd3(i, a, b) for(ll i=b-1, i##_len=(a);i>=i##_len;i--)
#define _repd2(i, n) _repd3(i,0,n)
#define loop(...) _overload3(__VA_ARGS__,,_loop2,_loop1)(__VA_ARGS__)
#define _loop2(i, a) for(ll i=a;; i++)
#define _loop1(i) _loop2(i,0)

#define all(x) x.begin(),x.end()
#define SIZE(x) ((ll)(x).size())

#define F first
#define S second
#define vec vector
#define umap unordered_map
#define uset unordered_set

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

#define bit(n) (1LL<<(n))
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define inrange(x,start,stop) ((start) <= (x) && (x) < (stop))
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 <typename Cont, typename Func>
Cont fmap(const Cont &container, Func functor) {
    Cont result(container.size());
    std::transform(container.begin(), container.end(), result.begin(), functor);// [](int x){return x * 2;}
    return result;
}
template <typename Cont, typename Pred>
Cont filter(const Cont &container, Pred predicate) {
    Cont result;
    std::copy_if(container.begin(), container.end(), std::back_inserter(result), predicate);// [](int x){return x == 2;}
    return result;
}   

template<typename T, typename ...Args>
void ci(T& first, Args&... args) {
    ((cin >> first), ..., (cin >> args)); //C++17
}

template<char Sep, typename T, typename ...Args>
void print_seq(const T& first, const Args&... args) {
    ((cout << first), ..., (cout << Sep << args)); //C++17
}

void co(){ cout << endl; }
template<typename... Words>
void co(Words... words) {
    print_seq<' '>(words...);
    cout << endl;
}
#define coi(x) cout<<(x)<<" "

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define sankou(n,a,b) cout << ((n) ? (a) : (b) ) << endl

#define asrt(expr...) assert((expr))
//</editor-fold>

//digit guide 9876543210987654321
#define LINF           2000000000 //2*10^9
#define INF   9000000000000000000 //9*10^18
#define MOD            1000000007 //1*10^9 + 7
#define MAXR               100000
//digit guide 9876543210987654321

void solve() {
    ll N;
    ci(N);
    co(N*N*N);
}

int main(){
    //入力の高速化用のコード
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    
    solve();
    return 0;
}


Measured memory_bytes: 3512
#include <iostream>

using namespace std;

int main()
{
   string s  ;
   cin >> s ;
   for (int i =0 ; i< s.length() ; i++)
   {
       if (  s[i]== ',' ){
          s[i] = ' ' ;
       }
       cout<<s[i]  ;
   }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
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;}




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

string s,t;
cin >> s >> t;

int ans = 0;

rep(i,3){
    if(s[i] == t[i]) ans++;
}

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

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

int chr[] = {3,3,3,3, 3,4,3,4};

string tobtn(string word)
{
	string res;
	for(int i=0; i<word.size(); i++) {
		int n = word[i]-'a';
		int c = 0;

		for(int j=0; j<8; j++) {
			c += chr[j];
			if(n < c) {
				res += (j+2+'0');
				break;
			}
		}
	}

	return res;
}

void output(vector<string>& words)
{
	for(int i=0; i<words.size(); i++) {
		if(i!=0) cout << " ";
		cout << words[i];
	}
	

	cout << "." << endl;
}

void solve(int p, string seq, vector<string>& used, vector<pair<string, string> >& dic)
{
	if(p == seq.size()) {
		output(used);
		return;
	}

	for(int i=0; i<dic.size(); i++) {
		string btn = dic[i].first;

		if(seq.size() - p < btn.size()) continue;
		string cut = seq.substr(p, btn.size());

		if(cut == btn) {
			used.push_back(dic[i].second);
			solve(p+btn.size(), seq, used, dic);
			used.pop_back();
		}
	}
}

int main()
{
	int N;
	while(cin >> N, N) {
		vector<string> words(N);
		
		for(int i=0; i<N; i++)
			cin >> words[i];

		string seq;
		cin >> seq;

		vector<pair<string, string> > dic(N);
		for(int i=0; i<N; i++) 
			dic[i] = make_pair(tobtn(words[i]), words[i]);
		
		
		vector<string> used;
		solve(0,seq, used, dic);
		cout << "--" << endl;
	}
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr ll mod=1e9+7;

int main()
{
  int n,w;
  cin>>n>>w;
  vector<pair<ll,ll>> product(n);
  for (int i = 0; i < n; ++i)
  {
    cin>>product[i].first>>product[i].second;
  }
  vector<vector<ll>> dp(n+1,
    vector<ll>(w+1,0));
  for (int i = 1; i < n+1; ++i)
  {
    for (int j = 0; j < w+1; ++j)
    {
      if(j-product[i-1].first<0) 
      {
        dp[i][j]=dp[i-1][j];
        continue;
      }
      dp[i][j]=max(dp[i-1][j],
        dp[i-1][j-product[i-1].first]
        +product[i-1].second);
    }
  }
  cout<<*max_element(dp[n].begin(),
   dp[n].end())<<endl;
}

Measured memory_bytes: 83072
#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>;
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)

const int INF = 1e9 + 10;

ll A;
double B;

int main() {
    cin >> A >> B;
    ll BLL = (ll)(B * 100 + 0.001);
    cout << (A * BLL) / 100 << endl;
}

Measured memory_bytes: 3720
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#ifdef rd
#define trace(...) cout<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
	cout<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
	const char *comma=strchr(names+1,',');
	cout.write(names,comma-names)<<" : "<<arg1<<" | ";
	__f(comma+1,args...);
}
#else
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef float f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b, int mod) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
int arr[200005];


void solve()
{
ll a,b;
 cin>>a>>b;
 auto k=(a+b)/2;
 if((a&1 and !(b&1) )|| (b&1 and !(a&1)) )
     cout<<"IMPOSSIBLE";
 else
    cout<<k;

}



signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(10);
	int t=1;
 	//cin>>t;
	fr(i,1,t) {
		solve();
	}
#ifdef rd
	cout<<endl<<endl<<endl<<endl<<"Time elapsed: "<<(double)(clock()-clk)/CLOCKS_PER_SEC<<endl;
#endif
	return 0;
}
/// template by rahuldugar




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;
 
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; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()


const int MAX = 500000, MS = 2;
const long long mod[] = {999999937LL, 1000000007LL}, base = 9973;
struct rolling_hash {
    int n;
    vector<long long> hs[MS], pw[MS];
    rolling_hash(){}
    rolling_hash(const string &s) {
        n = s.size();
        for (int i = 0; i < MS; i++) {
            hs[i].assign(n+1,0);
            pw[i].assign(n+1,0);
            hs[i][0] = 0;
            pw[i][0] = 1;
            for (int j = 0; j < n; j++) {
                pw[i][j+1] = pw[i][j]*base%mod[i];
                hs[i][j+1] = (hs[i][j]*base+s[j])%mod[i];
            }
        }
    }

    long long hash(int l, int r, int i) { return ((hs[i][r]-hs[i][l]*pw[i][r-l])%mod[i]+mod[i])%mod[i]; }
//1-indexed
    bool match(int l1, int r1, int l2, int r2) {
        bool ret = 1;
        for (int i = 0; i < MS; i++) ret &= hash(l1,r1,i)==hash(l2,r2,i);
        return ret;
    }

    bool match(int l, int r, long long h[]) {
        bool ret = 1;
        for (int i = 0; i < MS; i++) ret &= hash(l,r,i)==h[i];
        return ret;
    }
};

int main(){
  int p;cin>>p;
  string s;cin>>s;
  rolling_hash rh(s);
  int ok=0;int ng=((int)s.size()+3)/2;
  int n=s.size();
  while(ng-ok>1){
    int mid=(ng+ok)/2;
    bool flag=0;
    map<ll,vector<int>> m0,m1;
    rep(i,mid,n+1){
      ll tmp0=rh.hash(i-mid,i,0);
      ll tmp1=rh.hash(i-mid,i,1);
      if(m0[tmp0].size()&&m1[tmp1].size()){
        if(m0[tmp0].front()<i-mid&&m1[tmp1].front()<i-mid){
          flag=1;break;
        }
      }
      else{
        m0[tmp0].push_back(i-1);
        m1[tmp1].push_back(i-1);
      }
    }
    if(flag)ok=mid;
    else ng=mid;
  }
  cout<<ok<<endl;
}

Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int u32;
typedef pair<int, int> p;
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; }
int Inf = 1000000000;
ll inf = 1000000000000;
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; }
int main() {
	int h, n;
	cin >> h >> n;
	int i;
	int a[1100], b[1100];
	for (i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}
	int dp[1100][11000];
	for (i = 0; i <= n; i++) {
		for (int j = 0; j <= h; j++) {
			dp[i][j] = Inf;
		}
	}
	dp[0][0] = 0;
	for (i = 0; i < n; i++) {
		for (int j = 0; j <= h; j++) {
			int M = min(h, j + a[i]);
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]); // 呪文を選ばない
			dp[i + 1][M] = min(dp[i + 1][M], dp[i + 1][j] + b[i]);
		}
	}
	cout << dp[n][h];
	return(0);
}

Measured memory_bytes: 44800
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtCodeeeer
{
    class AtCOOOOOOOOOOOder
    {
        static void Main(string[] args)
        {
            int n = int.Parse(ReadLine());

            double ans = 0;
            for (int i = 1; i <= n; i++)
            {
                if (i % 2 == 0) ans++;
            }
            WriteLine(
                1D - (ans / (double) n)
                );
        }
    }
}

Measured memory_bytes: 11220
import math
S = input()
N = len(S)
count = 0
for i in range(N//2):
    if S[2 * i] != 'L' and S[2 * i + 1] != 'R':
        count += 2
    else:
        break
if N % 2 == 1:
    if S[N - 1] != 'L':
        count += 1
if count == N:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3060
import sys
#import string
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def solve():
    n = int(stdin.readline().rstrip())
    c = str(stdin.readline().rstrip())
    #A, B, C = map(int, stdin.readline().rstrip().split())
    #l = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    ans = 0
    l = 0
    r = -1
    for i in range(n):
        if l-r >= n:
            print(ans)
            exit()
        left = c[l]
        right = c[r]
        if left == "W" and right == "R":
            ans += 1
            l += 1
            r -= 1
        elif left =="W" and right =="W":
            r -= 1
        elif left == "R" and right =="R":
            l += 1
        else:#R,W
            l += 1
            r -= 1


if __name__ == '__main__':
    solve()


Measured memory_bytes: 9528
local DBG = false
function dbgpr(...)
    if DBG then
        io.write("[dbg]")
        print(...)
    end
end
function dbgpr_t(tbl)
    if DBG then
        dbgpr(tbl)
        io.write("[dbg]")
        for i,v in ipairs(tbl) do
            io.write(i)
            io.write(":")
            io.write(tostring(v))
            io.write(" ")
        end
        print("")
    end
end
function gentbl(n, f)
    local t = {}
    for i=1,n do
        t[i] = f(i)
    end
    return t
end
function parse_table(N)
    local tbl = {}
    for i=1,N do
        table.insert(tbl, io.read("n"))
    end
    return tbl
end
function parse_table_callback(N, f)
    for i=1,N do
        f(i, io.read("n"))
    end
end
function main()
    local cost = {2,5,5,4,5,6,3,7,6}
    local N, M = io.read("n", "n")
    io.read("l")
    local allowed = gentbl(9, function(i)
        return false
    end)
    parse_table_callback(M, function(i, v)
        assert(v >= 1 and v <= 9)
        allowed[v] = true
    end)
    --dbgpr_t(allowed)
    local function generate_max_ndigits(resource)
        local tbl = {}
        tbl[0] = 0
        for n=1,resource do
            local max_ndigit = -1
            --local i_at_max_ndigit = nil
            for i=9,1,-1 do
                -- try "i" as a digit
                local remain_n = n - cost[i]
                if allowed[i] and
                    cost[i] <= n and
                    tbl[remain_n] >= 0 then
                    local new_ndigit = tbl[remain_n] + 1
                    --dbgpr(n,i,cost[i],tbl[remain_n])
                    if max_ndigit < new_ndigit then
                        --i_at_max_ndigit = i
                        max_ndigit = new_ndigit
                    end
                end
            end
            tbl[n] = max_ndigit
        end
        return tbl
    end
    local max_ndigits = generate_max_ndigits(N)
    --dbgpr_t(max_ndigits)
    dbgpr("max_ndigits[N]", max_ndigits[N])
    local n = N
    local ans = {}
    for i=1,max_ndigits[N] do
        local selected = false
        for i=9,1,-1 do
            -- try "i" as a digit
            local remain_n = n - cost[i]
            if allowed[i] and max_ndigits[remain_n] == max_ndigits[n] - 1 then
                table.insert(ans, i)
                n = remain_n
                selected = true
                break
            end
        end
        assert(selected)
    end
    dbgpr("ans")
    print(table.concat(ans,""))
end
main()


Measured memory_bytes: 888
N = int(input())
h = [int(i) for i in input().split()]

dp = [float('inf')]*N
dp[0] = 0
dp[1] = abs(h[1] - h[0])

for i in range(2, N):
  a = abs(h[i] - h[i-1]) + dp[i-1]
  b = abs(h[i] - h[i-2]) + dp[i-2]
  dp[i] = min(a, b)
  
print(dp[N-1])


Measured memory_bytes: 13980
mod = 10**9+7
c = [[0 for i in range(2001)] for j in range(2001)]
c[0][0] = 1
c[1][0] = 1
c[1][1] = 1
for i in range(2,2001):
    for j in range(i+1):
        c[i][j] = (c[i-1][j-1]+c[i-1][j]) % mod
[N,K] = list(map(int,input().split()))
R = N - K
B = K
for i in range(1,B+1):
    ans = c[R+1][i]*c[B -1][i-1]
    print(ans % mod)

Measured memory_bytes: 99316
#include <stdio.h>
int main (void)
{
	int H,W;
	int y,t;

	while(1)
	{
		scanf("%d %d",&H,&W);

		if((H==0)&&(W==0)) break;
		
		for(t=0;t<H;t++)
		{
			for(y=0;y<W;y++)
			{	
				printf("#");
			}

			printf("\n");
		}
		printf("\n");
	}

	return 0;
}

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

#define int long long
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define vcopy(v1,v2) copy((v1).begin(), (v1).end(), back_inserter((v2)));
#define pb(n) push_back(n);

int n;

main() {
    cin >> n;
    ct(n/3)
}






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

int main(){
    int n; cin >> n;
    string s; cin >> s;
    vector<vector<int>> num_list(11);
    int tmp;
    rep(i,n){
        tmp = s[i] - '0';
        num_list[tmp].push_back(i);
    }
    int ans = 0;
    rep(i,10){
        rep(j,10){
            rep(k,10){
                if(num_list[i].size() == 0 || num_list[j].size() == 0 || num_list[k].size() == 0) continue;
                int a = num_list[i][0];
                auto b_iter = upper_bound(num_list[j].begin(),num_list[j].end(), a);
                int b = distance(num_list[j].begin(), b_iter);
                if(b == num_list[j].size()) continue;
                b = num_list[j][b];
                auto c_iter = upper_bound(num_list[k].begin(),num_list[k].end(), b);
                int c = distance(num_list[k].begin(), c_iter);
                if(c == num_list[k].size()) continue;
                ans++;
            }
        }
    }
    cout << ans << "\n";
}

Measured memory_bytes: 512
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws IOException{
		CountingRoads solver = new CountingRoads();
		solver.readInput();
		solver.solve();
		solver.writeOutput();
	}
	static class CountingRoads {
		private int city[];
		private Scanner scanner;
		private int n;
		private int m;

		public CountingRoads() {
			this.scanner = new Scanner(System.in);
		}

		public void readInput() {
			n = Integer.parseInt(scanner.next());
			m = Integer.parseInt(scanner.next());
			city = new int[n];
			Arrays.fill(city, 0);
		}
		public void solve() {
			for(int i=0; i<m; i++) {
				for(int j=0; j<2; j++) {
					city[Integer.parseInt(scanner.next())-1]++;
				}
			}
		}

		public void writeOutput() {
			for(int o:city) {
				System.out.println(o);
			}
		}
	}

}

Measured memory_bytes: 23380
while got = gets do
    array=got.chomp.split(",").map(&:to_i)
    l_array = array.shift(10)
    r = l_array.inject(:+).to_f * array[0] / (array[0] + array[1])
    ret = 0
    (0..9).each do |i|
        r -= l_array[i]
        if r <= 0
            puts i+1
            break
        end
    end
end



Measured memory_bytes: 6860
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
const int N=2005;
const int mod=1e9+7;
int n,m,fa[N];ll X,ans[N];
struct edge{
	int x,y,z;
	bool operator < (const edge &b)const{
		return z<b.z;
	}
}a[N];
int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
ll cal(int k){
	for(int i=1;i<=n;++i)fa[i]=i;
	fa[a[k].x]=a[k].y;ll res=a[k].z;
	for(int i=1;i<=m;++i){
		int x=find(a[i].x),y=find(a[i].y);
		if(x!=y)fa[x]=y,res+=a[i].z;
	}
	return res;
}
int fastpow(int x,int y){
	int res=1;
	while(y){if(y&1)res=1ll*res*x%mod;x=1ll*x*x%mod;y>>=1;}
	return res;
}
int main(){
	scanf("%d%d%lld",&n,&m,&X);
	for(int i=1,x,y,z;i<=m;++i){
		scanf("%d%d%d",&x,&y,&z);
		a[i]=(edge){x,y,z};
	}
	sort(a+1,a+m+1);
	for(int i=0;i<=m;++i)ans[i]=cal(i);
	if(X<ans[0])return puts("0"),0;
	else if(X==ans[0]){
		int res=0;
		for(int i=1;i<=m;++i)
			res+=(ans[i]==X);
		printf("%lld\n",1ll*(fastpow(2,res)+mod-2)*fastpow(2,m-res)%mod);
	}else{
		int res1=0,res2=0;
		for(int i=1;i<=m;++i)
			res1+=(ans[i]==X),res2+=(ans[i]>X);
		printf("%lld\n",2ll*(fastpow(2,res1)-1)*fastpow(2,res2)%mod);
	}
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(void){
    int i, j;
    string S;
    cin >> S;
    for(i=0;S[i] != '\0';i++){
        for(j=i+1; S[j] != '\0'; j++){
            if(S[i] == S[j]){
                cout << "no" << endl;
                return 0;
            }
        }
    }
    cout << "yes" << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <vector>
#include <queue>
#include <memory.h>
#include <functional>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
using namespace std;

//FILE * in = freopen("input.txt", "r" , stdin);

typedef unsigned int Color;

struct Point{
	Point(unsigned int x, unsigned int y) : x(x), y(y){}
	unsigned int x;
	unsigned int y;
	bool operator < (const Point &p) const {
		//return x < p.x ? true : y < p.y ?  ;
		return x == p.x ? y < p.y ? true : false : x < p.x;
	}
};

int surX[] = {0, 1, 0, -1};
int surY[] = {1, 0, -1, 0};

bool baketuTool(Point point, set<Point> * currentPoints, set<Point> * touchPoints, Color color, vector<vector<Color>> * table){
	if((*table)[point.y][point.x] == color){ // onazi color check
		currentPoints->insert(point);
		for(unsigned int i=0; i<4; i++){ // sihou check
			unsigned y = point.y + surY[i];
			if(0 > y || y >= table->size()) continue;
			unsigned x = point.x + surX[i];
			if(0 > x || x >= (*table)[y].size()) continue;
			Point p = Point(x,y);
			if(currentPoints->find(p)==currentPoints->end()){ // iranai
				if(baketuTool(p, currentPoints, touchPoints, color, table)){
					touchPoints->insert(p);
				}
			}
		}
		return false;
	}
	return true;
}

unsigned int recursion(set<Point> currentPoints, set<Point> touchPoints, map<set<Point>, unsigned int> * caches, vector<vector<Color>> * table, unsigned int count, Color lastColor){
	if(count > 5){
		return currentPoints.size();
	}
	unsigned int max_size = 0;
	for(Color color=1;color<=6;color++){
		if(count == 5 && color != lastColor) continue;
		auto new_currentPoints = currentPoints;
		set<Point> new_touchPoints;
		for(auto it=touchPoints.begin(); it!=touchPoints.end();it++){
			if(baketuTool(*it, &new_currentPoints, &new_touchPoints, color, table)){
				new_touchPoints.insert(*it);
			}
		}
		auto size = recursion(new_currentPoints, new_touchPoints, caches, table, count+1, lastColor);
		if((*caches)[new_currentPoints] < size){
			(*caches)[new_currentPoints] = size;
		}
		max_size = max(max_size, size);
	}
	return max_size;
}

void solution(unsigned int h, unsigned int w, Color c){
	map<set<Point>, unsigned int> caches;

	vector<vector<Color>> table;
	Color p;
	table.push_back(vector<Color>());
	for(unsigned int i = 0; i < h*w; i++){
		cin >> p;
		if(table.back().size()==w) table.push_back(vector<Color>());
		table.back().push_back(p);
	}
	unsigned int currentSize = 1;
	Color currentColor = table[0][0];
	set<Point> currentPoints;
	set<Point> touchPoints;
	
	baketuTool(Point(0,0), &currentPoints, &touchPoints,  currentColor, &table);


	auto size = recursion(currentPoints, touchPoints, &caches, &table, 1, c);
	cout << size << endl;
}

int main() {
	unsigned int h,w,c;
	while(true){
		cin >> h;
		cin >> w;
		cin >> c;
		if(h==0 && w==0 && c==0) break;
		solution(h,w,c);
	}
	return 0;

}

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

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

const int di[] = { -1, 1, 0, 0 }, dj[] = { 0, 0, -1, 1 };

int main(){
    int h, w;
    cin >> h >> w;
    vs a(h);
    rep(i, h) cin >> a[i];
    vector<vi> dist(h, vi(w, -1));
    queue<pii> q;
    auto ps = [&] (int i, int j, int d) {
        if (i<0||i>=h||j<0||j>=w) return;
        if (a[i][j]==' ') return;
        q.push({i, j});
        dist[i][j] = d;
        a[i][j] = ' ';
    };
    rep(i, h) rep(j, w) {
        if (a[i][j]=='#') ps(i, j, 0);
    }
    while (!q.empty()) {
        pii p = q.front(); q.pop();
        int i = p.first, j = p.second;
        int d = dist[i][j];
        rep(i2, 4) {
            int ni = i + di[i2], nj = j + dj[i2];
            ps(ni, nj, d+1);
        }
    }
    int ans = 0;
    rep(i, h) rep(j, w) ans = max(ans, dist[i][j]);
    cout << ans << endl;
    return 0;
}


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

namespace C044
{
    class C063
    {

        static bool[] calc(List<int> list)
        {
            int sum = list.Sum();
            bool[,] b = new bool[list.Count, sum + 1];

            for(int i = 0; i < list.Count; i++)
            {
                int a = list[i];
                if (i == 0)
                {
                    b[0, 0] = true;
                    b[0, a] = true;
                }
                else
                {
                    for(int j = 0; j < a; j++)
                    {
                        b[i, j] = b[i - 1, j];
                    }
                    for(int j = a; j <= sum; j++)
                    {
                        b[i, j] = b[i - 1, j] || b[i - 1, j - a];
                    }
                }
            }

            bool[] bl = new bool[sum + 1];
            for(int i = 0; i <= sum; i++)
            {
                bl[i] = b[list.Count - 1, i];
            }
            return bl;
        }
            
        public static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            List<int> s = new List<int>();
            for(int i = 0; i < N; i++)
            {
                int x = int.Parse(Console.ReadLine());
                s.Add(x);
            }
            bool[] point = calc(s);

            int max = 0;
            for(int i = 1; i < point.Length; i++)
            {
                if (i % 10 != 0 && point[i]) max=i;
            }

            Console.WriteLine(max);
        }
    }
}


Measured memory_bytes: 14048
a = input()
b = input()
c = input()

cur = "a"

while True:
    if cur == "a":
        if len(a) == 0:
            print("A")
            break
        else:
            cur = a[0]
            a = a[1:]
    elif cur == "b":
        if len(b) == 0:
            print("B")
            break
        else:
            cur = b[0]
            b = b[1:]
    else:
        if len(c) == 0:
            print("C")
            break
        else:
            cur = c[0]
            c = c[1:]

Measured memory_bytes: 8836
#include <bits/stdc++.h>
#define lli long long int
#define MOD 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<lli>
#define vvi vector<vector<lli>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    string a, b;
    cin >> a >> b;

    string aa = "";
    string ab = "";
    rep(i, b[0]-'0') aa += a;
    rep(i, a[0]-'0') ab += b;
    if(aa>ab) cout << ab << endl;
    else cout << aa << endl;
}

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

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

  vector<uint64_t> L(N + 1);
  L.at(0) = 2;
  L.at(1) = 1;

  if (N == 1) {
  } else {
    for (int i = 2; i < (int)L.size(); i++) {
      L.at(i) = L.at(i - 1) + L.at(i - 2);
    }
  }
  cout << L.at(N) << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int a, b, c;
  cin >> a >> b;
  c = a*b;
  if (c%2 == 0){
    cout << "Even" << endl;
  }
  else{
    cout << "Odd" << endl;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>
#include<unordered_map>
#define P pair<int,string>
using namespace std;

int main() {
	int a;
	while (cin >> a, a) {
		string b[20];
		vector<int>V[30];
		for (int c = 0; c < a; c++) {
			cin >> b[c];
			int d; cin >> d;
			for (int e = 0; e < d; e++) {
				int f; cin >> f;
				V[f].push_back(c);
			}
		}
		int S[31]{};
		for (int i = 0; i < 30; i++) {
			for (int j : V[i]) {
				S[j] += a + 1 - V[i].size();
			}
		}
		int n = 1<<29, m = 0;
		string K="zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz";
		set<P>O;
		for (int i = 0; i < a; i++) {
			O.insert({ S[i],b[i] });
		}
		cout << O.begin()->first<< " " << O.begin()->second << endl;
	}
}

Measured memory_bytes: 3140
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	public static void main(String args[]) {
		FastScanner cin = new FastScanner();
		PrintWriter cout = new PrintWriter(System.out);
		solve(cin, cout);
		cout.flush();
	}

	private static void solve(FastScanner cin, PrintWriter cout) {
		int n = cin.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = cin.nextInt() - 1;

		int ans = solve(n, a);
		cout.println(ans);
	}

	private static int solve(int n, int[] a) {
		int here = 0;
		int ans = 0;
		for (int i = 0; i < n; i++) {
			ans += 1;
			here = a[here];
			if (here == 1)
				return ans;
		}
		return -1;
	}

	/**
	 * How to read input in Java — tutorial <br />
	 * By Flatfoot<br />
	 * http://codeforces.com/blog/entry/7018
	 */
	static class FastScanner {
		private BufferedReader br;
		private StringTokenizer st;

		FastScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements())
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					throw new IllegalStateException(e);
				}
			return st.nextToken();
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				throw new IllegalStateException(e);
			}
			return str;
		}

		long nextLong() {
			return Long.parseLong(next());
		}
	}

}


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

int main() {
  int N; cin >> N;
  string S, T, ans = "";
  cin >> S >> T;
  for(int i = 0; i < N; i++) {
    ans.push_back(S[i]);
    ans.push_back(T[i]);
  }
  cout << ans << endl;
  return 0;
}


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

int main() {
  int N;
  cin >> N;
  
  vector<int> diameter(N);
  for (int i = 0; i < N; i++) {
    cin >> diameter.at(i);
  }
  
  sort(diameter.begin(), diameter.end());
  
  int type = 1;
  
  for (int i = 0; i < N-1; i++) {
    if (diameter.at(i) < diameter.at(i+1)) {
      type++;
    }
    else {
      continue;
    }
  }
  
  cout << type << endl;
      
}

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

typedef long long ll;
const int MN = 2e5+10, mod = 1e9+7;

ll A[MN];
ll AC[MN];
int N;

int main()
{
    #ifdef ACMTUYO
    //cout << "In ACM\n";
    freopen("a.in","r",stdin);
    #else
    cin.tie(0); ios_base::sync_with_stdio(0);
    #endif // ACMTUYO

    cin >> N;

    map<ll,ll> S;
    ll res=0;
    //ll sum=0;
    for (int i=1; i <= N; i++){
        cin >> A[i];
        AC[i] = AC[i-1] + A[i];
    }

    S[0]=1;
    for (int i=1; i <= N; i++){
        res += S[AC[i]];
        S[AC[i]]++;
    }

    cout << res << "\n";

    return 0;
}


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

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

    if (N == 0)
    {
        cout << X;
        return 0;
    }
    else
    {
        vector<int> p(N);
        for (int i = 0; i < N; i++)
        {
            cin >> p.at(i);
        }

        sort(p.begin(), p.end());

        int zure = 0;
        int target = X;

        for (zure = 0; zure <= 1000; zure++)
        {
            target = X - zure;
            if (find(p.begin(), p.end(), target) == p.end())
            {
                if (target != p.at(N - 1))
                {
                    cout << target;
                    return 0;
                }
            }
            else
            {
                target = X + zure;
                if (find(p.begin(), p.end(), target) == p.end())
                {
                    if (target != p.at(N - 1))
                    {
                        cout << target;
                        return 0;
                    }
                }
            }
        }
        return 0;
    }
}

Measured memory_bytes: 3600
from collections import deque
import sys
input = sys.stdin.readline

N, Q = [int(i) for i in input().split()]

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

M = [0] * (N + 1)
for _ in range(Q):
    p, x = [int(i) for i in input().split()]
    M[p] += x

ans = M[:]
visited = [False] * (N + 1)
visited[1] = True
Q = deque([1])
while Q:
    a = Q.popleft()
    for e in E[a]:
        if visited[e]:
            continue
        visited[e] = True
        ans[e] += ans[a]
        Q.append(e)

print(*ans[1:])


Measured memory_bytes: 98380
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

const double pi = 3.141592653589793238462643383279;
using namespace std;
using namespace __gnu_pbds;
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
 
 
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
 
 
//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
 
 
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
 
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)

const long double EPS = 1e-6, PI = acos((long double)-1);

//ここから編集


const int MOD2 = 998244353;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(7);


  int N, K; cin >> N >> K;
  vector<pair<int, int>> p;
  REP(i,K){
    int l, r; cin >> l >> r;
    r++;
    p.push_back({l, r});
  }
  vector<ll> dp(N);
  dp[0] = 1;
  dp[1] = -1;
  for(int i=0; i<N; i++){
    if(i > 0) dp[i] += dp[i-1];
    dp[i] %= MOD2;
    for(int j=0; j<K; j++){
      int l = p[j].first, r = p[j].second;
      if(i+l<N){
        dp[i+l] += dp[i];
        dp[i+l] %= MOD2;
      }
      if(i+r<N) {
        dp[i+r] = (dp[i+r]-dp[i]+MOD2)%MOD2;
      }
    }
  }
  cout << dp[N-1] << endl;

  return 0;
}

Measured memory_bytes: 4764
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
using namespace std;


int main() {
	long long int n, k, h, a[200005], b[200005] = {0,1},result = 0, cou = 1,num=1;
	cin >> n>>k;
	
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	sort(a, a + n);

	for (int i = 1; i < n; i++) {
		if (a[i] != a[i - 1]) {
			cou++;
			b[cou]++;
		}
		else {
			b[cou]++;
		}
	}

	sort(b + 1, b + cou + 1);
	cou -= k;

	while (cou > 0) {
		result += b[num];
		num++;
		cou--;
	}
	cout << result;
}



Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
 
const int N = 1e5 + 5;





int32_t main()
{
   IOS;
   int n;
   cin >> n;

   string ans;

   while(n>0)
   {
      n-=1;
      ans+= char((int)('a')+ n%26);
      n/=26;
   }

   reverse(ans.begin(), ans.end());

   cout << ans << endl;




return 0;   
}






Measured memory_bytes: 3652
n,k=map(int,input().split())
if k>((n-1)*(n-2))//2:
  print(-1)
else:
  m=((n-1)*(n-2))//2
  d=m-k
  print(n-1+d)
  for i in range(n-1):
    print(1,i+2)
  if d==0:exit()
  for i in range(2,n):
    for j in range(i+1,n+1):
      print(i,j)
      d-=1
      if d==0:
        exit()


Measured memory_bytes: 74652
#define loop(i, s, e) for(ll i = s;i < e;i++)

#include <iostream>
#include <iomanip>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <utility>
#include <algorithm>
#include <map>
#include <cmath>
//#include "vector2d.cpp"

using namespace std;
//using namespace libcgl;
typedef long long signed ll;

ll n,x[200000],xx[200000];

int main() {
    cin >> n;
    loop(i,0,n) {cin >> x[i];xx[i]=x[i];}
    sort(xx,xx+n);
    ll m = n / 2 - 1;
    loop(i,0,n) {
        if(x[i] <= xx[m]) cout << xx[m+1] << endl;
        else cout << xx[m] << endl;
    }
}



Measured memory_bytes: 5376
N, Y = map(int, input().split())

ans = [-1, -1, -1]
for i in range(Y//1000+1):
    for j in range(Y//5000+1):
        k = (Y - 10000*i - 5000*j)//1000
        if k < 0:
            break
        if i + j + k == N:
            ans = i, j, k
# print(10000*ans[0] + 5000*ans[1] + 1000*ans[2])
print(*ans)


Measured memory_bytes: 3060
#include<iostream>
#include<math.h>

using namespace std;

bool isPrime ( int n )
{
	if ( n == 2 )
		return true;

	if ( n<=1 || n%2==0 )
		return false;
	
	for ( int i = 3 ; i <= sqrt((double)n) ; i+=2 )
		if ( n%i == 0 )
			return false;

	return true;
}

int main ()
{

	int n,ni,count;

	cin >> n;

	count = 0;

	while ( n-- )
	{
		cin >> ni;
		if ( isPrime(ni) )
			count++;
	}

	cout << count << endl;

return 0;
}



Measured memory_bytes: 3084
// finish date: 2019/06/29

#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)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<vector<vector<double>>> vvvd;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, pair<int, int>> plii;
const int bigmod = 998244353;
const int INF = 1050000000;
const long long INFll = 100000000000000000;


int main() {
    int N;
    cin >> N;
    vi d(N);
    rep(i, N) cin >> d[i];
    sort(d.begin(), d.end());
    cout << d[N / 2] - d[N / 2 - 1] << endl;

    return 0;
}


Measured memory_bytes: 768
#include <iostream>
#include <vector>

using namespace std;

const int MOD = 998244353;

int main(){
    int N, S;
    while(cin >> N >> S){
        vector<int> A(N);
        for(auto& t : A) cin >> t;
        vector<long long> dp(S, 0);
        long long res = 0;
        for(int i=0;i<N;i++){
            for(int j=S-1;j>0;j--){
                if(j+A[i] == S){
                    res += dp[j] * (N-i);
                    res %= MOD;
                } else if(j+A[i] < S){
                    dp[j+A[i]] += dp[j];
                    dp[j+A[i]] %= MOD;
                }
            }
            if(A[i] == S){
                res += (i+1) * (N-i);
                res %= MOD;
            } else if(A[i] < S){
                dp[A[i]] += (i+1);
                dp[A[i]] %= MOD;
            }
        }
        cout << res << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <stack>
#include <queue>
using namespace std;
using ll = long long;
int main(){
    int X, Y, Z;
    cin >> X >> Y >> Z;
    cout << (X-Z)/(Y+Z) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using pii=pair<int,int>;

vector<pii> to[1010][1010];
int h[1010][1010]={};
bool used[1010]={};
void solve(int N, std::vector<std::vector<int>> A){
  for(int i=0;i<N;i++){
    for(int j=1;j<N-1;j++){
      int sx=min(i,A[i][j-1]);
      int sy=max(i,A[i][j-1]);
      int tx=min(i,A[i][j]);
      int ty=max(i,A[i][j]);
      to[sx][sy].push_back(make_pair(tx,ty));
      h[tx][ty]++;
    }
  }
  queue<pii> que;
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){
      if(h[i][j]==0)
	que.push(make_pair(i,j));
    }
  }
  int count=0;
  int ans=1;
  while(!que.empty()){
    pii p;
    int sz=que.size();
    for(int i=0;i<=sz;i++){
      p=que.front();que.pop();
      if(!(used[p.first]||used[p.second]))break;
      if(i<sz)que.push(p);
    }
    if(used[p.first]||used[p.second]){
      REP(i,N){
	used[i]=false;
      }
      ans++;
    }
    used[p.first]=true;
    used[p.second]=true;
    count++;
    for(auto& t:to[p.first][p.second]){
      h[t.first][t.second]--;
      if(h[t.first][t.second]==0)que.push(t);
    }
    //cout<<count<<":"<<p.first<<" "<<p.second<<" ->"<<ans<<endl;
  }
  if(count<((N*(N-1))>>1)){
    cout<<-1<<endl;
  }else{
    cout<<ans<<endl;
  }
}

int main(){
  int N;
  scanf("%d",&N);
  std::vector<std::vector<int>> A(N, std::vector<int>(N-1));
  for(int i = 0 ; i < N ; i++){
    for(int j = 0 ; j < N-1 ; j++){
      scanf("%d",&A[i][j]);
      A[i][j]--;
    }
  }
  solve(N, std::move(A));
  return 0;
}


Measured memory_bytes: 47744
#include"bits/stdc++.h"
using namespace std;

typedef long long ll;
#define FOR(i, a, n) for (ll i=(ll)a;i<(ll)n;i++)
#define REP(i, n) FOR(i, 0, n)


int main(){
    int a, b, k; cin >> a >> b >> k;
    int count = 0;
    int i = min(a,b)+1;
    while(count<k){
        i--;
        if (a%i==0&&b%i==0){
            count++;
        }
    }
    cout << i << endl;
}

Measured memory_bytes: 256