akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include<sstream>
#include<vector>
#include<iterator>
#include<map>
using namespace std;

int main(void)
{
	int a, b, c;
	cin >> a >> b >> c;
	//cout << a << b << c << endl;

	map<int, bool> table;

	bool flag = false;
	int dis = a%b;
	int n = dis;
	table[n] = true;
	while(1)
	{
		n += dis;
		n %= b;
		if(n == c)
		{
			flag = true;
			break;
		}
		else if(table.find(n) != table.end()) break;
	}
	if(flag == true) cout << "YES" << endl;
	else cout << "NO" << endl;

	return 0;
}


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

sum = 0
ans1 = 0

for i in range(n):
    sum += a[i]
    if i % 2 == 0:
        if sum == 0:
            sum = 1
            ans1 +=1
        elif sum > 0:
            pass
        else:
            ans1 += 1 - sum  
            sum = 1
    else:
        if sum == 0:
            ans1 += 1
            sum = -1
        elif sum < 0:
            pass
        else:
            ans1 += 1 + sum
            sum = -1

sum = 0
ans2 = 0
# 奇数項までの和が正、偶数項が負とした場合
for i in range(n):
    sum += a[i]
    if i % 2 == 1:
        if sum == 0:
            ans2 +=1
            sum = 1
        elif sum > 0:
            pass
        else:
            ans2 += 1 - sum
            sum = 1       
    else:
        if sum == 0:
            sum = -1
            ans2 += 1
        elif sum < 0:
            pass
        else:
            ans2 += 1 + sum
            sum = -1


print(min(ans1, ans2))
            

Measured memory_bytes: 63216
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define N 1005

char x[N], y[N];

int lcs(void);

int main(){
  int i, n, result[N];

  scanf("%d", &n);

  for(i = 0; i < n; i++){
    scanf("%s %s", x, y);

    result[i] = lcs();
  }

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

  return 0;
}

int lcs(){
  int a, b, c[N][N], i, j;

  a = strlen(x) ;
  b = strlen(y) ;
  
  for(i = 0; i <= a; i++)
    c[i][0] = 0;

  for(j = 0; j <= b; j++)
    c[0][j] = 0;

  for(i = 1; i <= a; i++){
    for(j = 1; j <= b; j++){
      if(x[i - 1] == y[j - 1])
        c[i][j] = c[i - 1][j - 1] + 1;

      else if(c[i - 1][j] >= c[i][j - 1])
        c[i][j] = c[i - 1][j];

      else
      c[i][j] = c[i][j - 1];
    }
  }

  return c[a][b];
}


Measured memory_bytes: 5668
import heapq

n, k = map(int, input().split())
h = []
d = [0 for _ in range(n)]
ans = 100000000000

for _ in range(n):
    # h.append(int(input()))
    heapq.heappush(h, int(input()))

h = [heapq.heappop(h) for _ in range(n)]

for i in range(n - k + 1):
    diff = h[i + k - 1] - h[i]
    ans = min(ans, diff)

print(ans)

Measured memory_bytes: 8372
n, m = map(int, input().split())
h = list(map(int, input().split()))
p = [ set(map(int, input().split())) for _ in range(m) ]
d = [ 0 for _ in range(n)]
for i,j in p:
    d[i-1] = max(d[i-1], h[j-1])
    d[j-1] = max(d[j-1], h[i-1])
c = [ 1 for i,j in enumerate(d) if j < h[i] ]
print(sum(c))

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

namespace ConsoleApp1
{
    static class BResistorsinParallel
    {
        static void Main(string[] args)
        {
            var n = decimal.Parse(Console.ReadLine());
            var aList = Console.ReadLine().Split(' ').Select(x => 1 / decimal.Parse(x)).ToList();
                       
            Console.WriteLine(1 / aList.Sum());
            Console.ReadLine();
        }
    }
}

Measured memory_bytes: 13396
#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
  long long N,A,B;
  cin >> N >> A >> B >> N;
  if(B < A) cout << 0 << endl;
  else if(N == 1)
  {
    if(A == B) cout << 1 << endl;
    else cout << 0 << endl;
  }
  else
  {
    N -= 2;
    if(N == 0) cout << 1 << endl;
    else cout << ((B - A)* N + 1) << endl;
  }
  return 0;
}

Measured memory_bytes: 256
s=input()
n=len(s)
mod=2019
d=0
p=1
ml=[0]*mod
for i in range(1,n+1):
  k=int(s[-i])
  d+=p*k
  d%=mod
  ml[d]+=1
  p*=10
  p%=mod
ans=0
for i in ml:
  ans+=i*(i-1)//2
print(ans+ml[0])

Measured memory_bytes: 9368
parseInt(x) = parse(Int, x)
parseArray(x::Array{SubString{String}, 1}) = map(parseInt, x)

function main()
  n,k = readline() |> split |> parseArray
  a = readline() |> split |> parseArray

  ans=0
  escape=false
  for ans in reverse(divisor(sum(a)))
    d=sort(a.%ans)
    for i in 1:n-1
      sum(d[1:i])!=sum(ans-d[i+1:end]) && continue
      sum(d[1:i])>k && continue
      escape=true
      break
    end
    escape && break
  end
  println(ans)
end

function divisor(x::Int)
  a=Int[]
  for i in 1:floor(sqrt(x))
    x%i!=0 && continue
    push!(a, i)
    push!(a, x÷i)
  end
  sort!(a)
  a
end

main()


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

#include <iostream>
#include <fstream>

//code by lynmisakura.wish to be accepted!
#include <iostream>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>

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

/***************************/
using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<long long> vl;
typedef pair<ll, ll> pi;
typedef vector<pair<ll, ll>> vpi;

//const long long INF = 1LL << 55;

#define itn ll
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ss second
#define ff first
#define dup(x,y) ((x) + (y) - 1)/(y)
#define mins(x,y) x = min(x,y)
#define maxs(x,y) x = max(x,y)
#define all(x) (x).begin(),(x).end()
#define Rep(n) for(ll i = 0;i < n;i++)
#define rep(i,n) for(ll i = 0;i < n;i++)
#define flush fflush(stdout)
#define rrep(i,n) for(ll i = n - 1;i >= 0;i--)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
#define ioboost cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20)
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll qp(ll a, ll b) { ll ans = 1; do { if (b & 1)ans = 1ll * ans*a; a = 1ll * a*a; } while (b >>= 1); return ans; }
ll qp(ll a, ll b, ll mo) { ll ans = 1; do { if (b & 1)ans = 1ll * ans*a%mo; a = 1ll * a*a%mo; } while (b >>= 1); return ans; }

#define _GLIBCXX_DEBUG
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl

class DStaticSushi {
public:
    static constexpr int kStressIterations = 0;
    static void generateTest(std::ostream& test) {
    }

    void solve(std::istream& cin, std::ostream& cout) {
        ll n,c;cin >> n >> c;
        vector<ll> x(n+1,0),v(n+1,0),s(n+1,0),a(n+1,0),b(n+1,0);
        for(int i=1;i<=n;i++){
            cin >> x[i] >> v[i];
            s[i]=s[i-1]+v[i];
            a[i]=max(a[i-1],s[i]-2*x[i]);
            b[i]=max(b[i-1],s[i]-x[i]);
        }
        ll ans=b[n];
        ll a0=0,b0=0;
        for(int i=n;i>0;i--){
            a0=max(a0,s[n]-s[i-1]-2*(c-x[i]));
            b0=max(b0,s[n]-s[i-1]-(c-x[i]));
            ans=max({ans,a[i-1]+b0,b[i-1]+a0});
        }
        cout<<ans<<endl;
    }
};

int main() {
	DStaticSushi solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

int main()
{
    vector<int> ans;
    while (1)
    {
        int n;
        cin >> n;
        if (n == 0)
        {
            break;
        }

        int count = 0;
        string input1;
        cin >> input1;
        for (int i = 0; i < n - 1; i++)
        {
            string input2;

            cin >> input2;
            if (input1 == "lu" && input2 == "ru")
            {
                count++;
            }
            else if (input1 == "ru" && input2 == "lu")
            {
                count++;
            }
            else if (input1 == "ld" && input2 == "rd")
            {
                count++;
            }
            else if (input1 == "rd" && input2 == "ld")
            {
                count++;
            }
            input1 = input2;
        }

        ans.push_back(count);
    }

    for (int i = 0; i < ans.size(); i++)
    {
        cout << ans[i] << endl;
    }
}


Measured memory_bytes: 3168
#include<stdio.h>
#include<algorithm>
using namespace std;
#define NIL -1
#define MAX 25

struct Node { int parent, left, right; };
struct Node T[MAX];
int D[MAX], H[MAX];

void Preorder(int p) {
  printf(" %d", p);
  if (T[p].left != NIL) Preorder(T[p].left);
  if (T[p].right != NIL) Preorder(T[p].right);
}

void Inorder(int p) {
  if (T[p].left != NIL) Inorder(T[p].left);
  printf(" %d", p);
  if (T[p].right != NIL) Inorder(T[p].right);
}

void Postorder(int p) {
  if (T[p].left != NIL) Postorder(T[p].left);
  if (T[p].right != NIL) Postorder(T[p].right);
  printf(" %d", p);
}

int main() {
	int n;
  scanf("%d", &n);
  for ( int i = 0; i < n; i++ ) {
    T[i].parent = NIL;
    T[i].left = NIL;
    T[i].right = NIL;
  }

  int id, left, right;
  for ( int i = 0; i < n; i++ ) {
    scanf("%d %d %d", &id, &left, &right);
    T[id].left = left;
    T[id].right = right;
    if (left != NIL) T[left].parent = id;
    if (right != NIL) T[right].parent = id;
  }

  int p;
  for ( int i = 0; i < n; i++ ) {
    if (T[i].parent == NIL) {
      p = i;
    }
  }

  printf("Preorder\n");
  Preorder(p);
  printf("\n");
  printf("Inorder\n");
  Inorder(p);
  printf("\n");
  printf("Postorder\n");
  Postorder(p);
  printf("\n");

  return 0;
}



Measured memory_bytes: 2712
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>

int n, m;
std::vector<std::pair<int, int>> data[100010];
int main()
{
    std::cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        int tmp1, tmp2;
        std::cin >> tmp1 >> tmp2;
        data[tmp1 - 1].emplace_back(tmp2, i);
    }

    std::string ans[100010];
    for (int i = 0; i < n; ++i)
    {
        std::sort(data[i].begin(), data[i].end());
        for (int j = 0; j < data[i].size(); ++j)
        {
            std::string first = std::to_string(i+1);
            if (first.size() != 6)
                first = std::string(6 - first.size(), '0') + first;
            std::string second = std::to_string(j+1);
            if (second.size() != 6)
                second = std::string(6 - second.size(), '0') + second;
            ans[data[i][j].second] = first + second;
        }
    }

    for (int i = 0; i < m; ++i)
        std::cout << ans[i] << std::endl;
    return 0;
}


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

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO 自動生成されたメソッド・スタブ
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		String[] tmpArray = br.readLine().split(" ");

		int[] input = new int[n];

		for(int i = 0; i < n; i++){
			input[i] = Integer.parseInt(tmpArray[i]);
		}

		Node[] odd = new Node[100001];
		Node[] even = new Node[100001];

		for(int i = 0; i < odd.length; i++){
			odd[i] = new Node(i, 0);
			even[i] = new Node(i, 0);

		}

		for(int i = 0; i < n/2; i++){
			odd[input[2*i]].num++;
			even[input[2*i + 1]].num++;
		}

		//debug
//		for(int i = 0; i < 10; i++){
//			System.out.print(odd[i] + " ");
//		}
//
//		System.out.println();
//
//		for(int i = 0; i < 10; i++){
//			System.out.print(even[i] + " ");
//		}
//
//		System.out.println();

		Arrays.sort(odd);
		Arrays.sort(even);

		int result = 0;
		if(odd[0].index != even[0].index){
			result = n - odd[0].num - even[0].num;
		}
		else {
			if(odd[0].num > even[0].num){
				result = n - odd[0].num - even[1].num;
			}
			else if(odd[0].num < even[0].num){
				result = n - even[0].num - odd[1].num;
			}
			else {
				result = n - odd[0].num - Math.max(odd[1].num, even[1].num);
			}
		}

		System.out.println(result);
	}

}

class Node implements Comparable<Node>{
	int index;
	int num;

	Node(int i, int n){
		index = i;
		num = n;
	}

	@Override
	public int compareTo(Node o) {
		return -this.num + o.num;
	}


}

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

// typedef
using ll = long long;
using str = string;
using PL = pair<ll, ll>;
using P = pair<int, int>;
using VL = vector<ll>;
using vi = vector<int>;
using vs = vector<str>;
using vp = vector<P>;
using VPL = vector<PL>;
using VVL = vector<VL>;
using vvi = vector<vi>;

// const num
const ll INF = 1e18 + 18;
const ll MAX = 100005;
const ll MOD = 1000000007;
const long double PI = acosl(-1.0);

// Loop
#define REP(i, a, b) for (ll(i) = (a); (i) < (b); (i)++)
#define RREP(i, a, b) for (ll(i) = (a); (i) >= (b); (i)--)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) RREP(i, n, 0)

// YesNo
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define YES(n) cout << ((n) ? "YES" : "NO") << endl

// All
#define ALL(v) v.begin(), v.end()

int main(void)
{
    str s, t;
    int cnt = 0;
    cin >> s;
    cin >> t;
    rep(i, s.length())
    {
        if (s[i] != t[i])
        {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 3844
N = int(input())

a_list = []

b_list = []

for i in range(N):
    a,b = map(int,input().split())
    a_list.append(a)
    b_list.append(b)

a_list = a_list[::-1]
b_list = b_list[::-1]

#print(a_list)
#print(b_list)

st = 0

for i in range(N):
    a_list[i] += st
    if a_list[i] % b_list[i]:
        if a_list[i] < b_list[i]:
            st += b_list[i]-a_list[i]
        elif a_list[i] > b_list[i]:
            st += b_list[i]*((a_list[i]//b_list[i])+1)-a_list[i]
print(st)

Measured memory_bytes: 21712
n = int(input())
p = list(map(int, input().split()))

ans = 0
for i in range(n - 2):
    if (p[i] < p[i+1] and p[i+1] < p[i+2]) or (p[i+2] < p[i+1] and p[i+1] < p[i]):
        ans += 1
print(ans)


Measured memory_bytes: 61892
import java.util.Scanner;

public class Main {
	
	public static void main(String[]args) {
		try(Scanner scan = new Scanner(System.in)){
			int a = scan.nextInt();
			
			
			
			
			System.out.println(a+a*a+a*a*a);
			
		}
		
		
	}
		

}


Measured memory_bytes: 35744
#include <iostream>
#include <list>
#include <string>
#include <iomanip>
using namespace std;

void sort(int num[50], int n){
    int temp;
    for(int i=1; i<n; i++){
        for(int j=0; j<n-i; j++){
            if(num[j] > num[j+1]){
                temp = num[j+1];
                num[j+1] = num[j];
                num[j] = temp;
            }
        }
    }
}

int main()
{
    int N;
    long long int bite;
    int values[50];
    long long int bi[50];
    long double sum;
    bite = 1;
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> values[i];
        bi[i] = bite;
        if(i> 0){
            bite*=2;
        }
    }
    sort(values, N);
    sum = 0;
    /*
    for(int i=0; i<N; i++){
        cout << values[i] << " ";
    }
    cout << endl;
    for(int i=0; i<N; i++){
        cout << bi[i] << " ";
    }*/
    for(int i=0; i<N; i++){
        sum += values[i]*bi[i];
    }

    cout << setprecision(7)<< sum/(bi[N-1]*2) << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e12 + 5;

int main(){
	ll N, W, maxGain = 0, maxValue = 0;
        cin >> N >> W;
        vector<ll> weights(N), values(N), maxVal(N);
        for(ll rep = 0; rep < N; ++rep){
            cin >> weights[rep] >> values[rep];
            maxValue += values[rep];
            maxVal[rep] = maxValue;
        }
        vector<ll> minWeights(maxValue + 1, INF);
        minWeights[0] = 0;
        for(ll itemN = 0; itemN < N; ++itemN){
            ll maxLimit = maxVal[itemN];
            for(ll value = maxLimit; value >= values[itemN]; --value){
                minWeights[value] = min(minWeights[value],
                		minWeights[value - values[itemN]] + weights[itemN]);
            } 
        }
        for(ll value = 0; value <= maxValue; ++value){
            if(minWeights[value] <= W) maxGain = value;
        }
        cout << maxGain << endl;
    	return 0;
}

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

int main(){

    string S, T;
    int a, b;
    cin >> S >> T >> a >> b;

    string compare;
    cin >> compare;

    if (compare == S){
        cout << a-1 << " " << b << endl;
    }
    else{
        cout << a << " " << b-1 << 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 repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
ll powmod(ll n, ll k, ll m) {
ll r=1;
 for(; k>0; k >>=1) {
   if(k&1) r=(r*n)%m;
   n=(n*n)%m;
 }
  return r;
}

ll fact(ll n) {
ll a=1;
rep(i,n) {
a=a*(n-i);
}
return a;
}

ll pow(ll a, ll b) {
ll x=1;
rep(i,b) {
x=x*a;
}
return x;
}



int main() {


ll a;
ll b;
ll c;
ll d;
cin >>a>>b>>c>>d;
  //1
if(a>0) {
  if(c>0) {
cout<<b*d<<endl;
  }
else if(c==0) {
  cout<<b*d<<endl;
}
  else if((c<0) &&(d>0)) {
    cout<<b*d<<endl;
  }
else if((c<0) &&(d==0)) {
  cout<<0<<endl;
}
  else if((c<0) &&(d<0)) {
    cout<<a*d<<endl;
  }
}
  
  //2
  else if(a==0) {
  if(c>0) {
cout<<b*d<<endl;
  }
else if(c==0) {
  cout<<b*d<<endl;
}
  else if((c<0) &&(d>0)) {
    cout<<b*d<<endl;
  }
else if((c<0) &&(d==0)) {
  cout<<0<<endl;
}
  else if((c<0) &&(d<0)) {
    cout<<0<<endl;
  }
}
  
  //3
  
 else  if((a<0)&&(b>0)) {
  if(c>0) {
cout<<b*d<<endl;
  }
else if(c==0) {
  cout<<b*d<<endl;
}
  else if((c<0) &&(d>0)) {
    cout<<max(b*d,a*c)<<endl;
  }
else if((c<0) &&(d==0)) {
  cout<<a*c<<endl;
}
  else if((c<0) &&(d<0)) {
    cout<<a*c<<endl;
  }
}
  
  
  //4
 else  if((a<0)&&(b==0)) {
  if(c>0) {
cout<<b*d<<endl;
  }
else if(c==0) {
  cout<<b*d<<endl;
}
  else if((c<0) &&(d>0)) {
    cout<<a*c<<endl;
  }
else if((c<0) &&(d==0)) {
  cout<<a*c<<endl;
}
  else if((c<0) &&(d<0)) {
    cout<<a*c<<endl;
  }
}
 
  
  //5
  else if((a<0)&&(b<0)) {
  if(c>0) {
cout<<b*c<<endl;
  }
else if(c==0) {
  cout<<0<<endl;
}
  else if((c<0) &&(d>0)) {
    cout<<a*c<<endl;
  }
else if((c<0) &&(d==0)) {
  cout<<a*c<<endl;
}
  else if((c<0) &&(d<0)) {
    cout<<a*c<<endl;
  }
}
  
  
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define pb push_back
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ll long long
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int> v(n);
  int cnt = 1, pre, ans = 0;
  cin >> pre;
  for(int i = 1; i < n; i++){
    int a;
    cin >> a;
    if(a == pre){
      cnt++;
    }else{
      ans += cnt / 2;
      cnt = 1;
      pre = a;
    }
  }
  ans += cnt / 2;
  cout << ans << endl;
  return 0;
}

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

int main() {
  	int N;
  	cin >> N;
    int d[110];
  	int i;
  	int a = 0;
  	int mae = 101;
  for (i = 0; i < N; i++)
  {
    cin >> d[i];
  }
  sort (d,d + N, greater<int>());
  for (i = 0; i < N; i++)
  {
      if (d[i] < mae){
        mae = d[i];
        a++;
      }
  }
  cout << a << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  int a[n];
  for(int i = 0 ; i < n ; i++)
    cin >> a[i];
  int dp[n];
  dp[0] = 0;
  dp[1] = abs(a[1] - a[0]);
  for(int i = 2 ; i < n ; i++){
    dp[i] = INT_MAX;
  	for(int j = min(i, k) ; j > 0  ; j--)
    	dp[i] = min(dp[i], dp[i-j] + abs(a[i] - a[i-j]));
  }
  cout << dp[n-1];
}

Measured memory_bytes: 1024
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, m, n) for(int i=(m); i<(n); ++i)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define Cout(x) cout << (x) << endl
#define Cout2(x, y) cout << (x) << " " << (y) << endl
#define dump(x) cerr << #x << " = " << (x) << endl;
typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
const int inf = 1e9;
const double pi = acos(-1.0);

int main() {
	int n, h; cin >> n >> h;
	VI a(n), b(n);
	rep(i, n)cin >> a[i] >> b[i];

	int Amax = *max_element(all(a));
	VI B;
	rep(i, n)if (Amax < b[i])B.pb(b[i]);
	sort(all(B), greater<int>());

	int ans = 0, sum = 0;
	rep(i, sz(B)) {
		sum += B[i]; ans++;
		if (sum >= h)break;
	}

	if (sum < h) {
		ans += ((h - sum) + Amax - 1) / Amax;
	}

	Cout(ans);
}

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

#define REP(i, n) for (ll (i) = 0 ; (i) < (ll)(n) ; ++(i))
#define REPN(i, m, n) for (ll (i) = m ; (i) < (ll)(n) ; ++(i))
#define REP_REV(i, n) for (ll (i) = (ll)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (ll (i) = (ll)(n) - 1 ; (i) >= m ; --(i))

#define INF             2e9
#define INF_LL          1LL<<60
#define ll              long long
#define Ceil(x, n)      (((((x))+((n)-1))/n))
#define CeilN(x, n)     (((((x))+((n)-1))/n)*n)
#define FloorN(x, n)    ((x)-(x)%(n))
#define ALL(x)          (x).begin(),(x).end()

int main(){
    ll n;
    cin >> n;
    vector<ll> keta;
    while(1) {
        keta.push_back(n % 10);
        n /= 10;
        if(n == 0) break;
    }

    ll keta_size = keta.size();
    reverse(ALL(keta));

    ll dp[keta_size][2];    /* 0: いっしょ、1: より小さい */
    dp[0][0] = keta[0];
    dp[0][1] = keta[0] - 1;

    REP(i, keta.size()-1) {
        /* いっしょからいっしょ */
        dp[i+1][0] = dp[i][0] + keta[i+1];

        /* いっしょからより小さい */
        dp[i+1][1] = dp[i][0] + keta[i+1] - 1;

        /* より小さいからより小さい */
        dp[i+1][1] = dp[i][1] + 9;
    }

    cout << max(dp[keta_size-1][0], dp[keta_size-1][1]) << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	int a, b;
	cin >> a >> b;
	for (int i = 1; i < 1200; i++) {
		int t8 = (int)(i * 0.08);
		int t10 = (int)(i * 0.1);
		if (a == t8 && b == t10) {
			cout << i << endl;
			return 0;
		}
	}
	cout << -1 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define st first
#define nd second

using namespace std;

void debug_out() { cerr << endl; }
template<class T> ostream& prnt(ostream& out, T v) { out << v.size() << '\n'; for(auto e : v) out << e << ' '; return out;}
template<class T> ostream& operator<<(ostream& out, vector <T> v) { return prnt(out, v); }
template<class T> ostream& operator<<(ostream& out, set <T> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, map <T1, T2> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, pair<T1, T2> p) { return out << '(' << p.st << ' ' << p.nd << ')'; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...);}

#define dbg(...) cerr << #__VA_ARGS__ << " ->", debug_out(__VA_ARGS__)
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(long long _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"

// const long long N = ;
long long n, x, ans;

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> x;

	ans += n;

	long long a = x;
	long long b = n - x;
	if(a < b) swap(a, b);

	while(b) {
		// if(a < b) swap(a, b);
		long long c = a % b;
		ans += 2 * (a / b) * b;
		dbg(a, b, ans);
		if(c == 0) ans -= b;
		a = b;
		b = c;
	}
	// ans += b;
	cout << ans << '\n';

}	

	

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

long long n,m,a[100005],f[100005];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int x;
		cin >> x;
		a[x]=1;
	}
	f[0]=1;
	if(!a[1])f[1]=1;

	for(int i = 2; i <= n; i++){
		if(a[i]==0) f[i]=(f[i-1]+f[i-2]) % 1000000007;
	}
	cout << f[n] << "\n";
	return 0;
}

Measured memory_bytes: 1792
n=int(input())
A=list(map(int,input().split()))
cnt=0
for i in range(n-1):
  minj=i
  for j in range(i,n):
    if A[minj]>A[j]:
      minj=j
  if minj!=i:
    A[i],A[minj]=A[minj],A[i]
    cnt+=1
print(*A)
print(cnt)


Measured memory_bytes: 5608
using System;
using System.Collections.Generic;
using System.Linq;

namespace ABC
{
    class Program
    {
        static void Main(string[] args)
        {
            ABC092_B();
        }

        static void ABC092_B()
        {
            var N = int.Parse(Console.ReadLine());
            var DX = Console.ReadLine().Split(' ').Select(int.Parse).ToList();
            var ans = DX[1];
            for (var n = 0; n < N; n++)
            {
                var A = int.Parse(Console.ReadLine());
                ans++;
                for (var a = 1 + A; a <= DX[0]; a += A)
                    ans++;
            }
            Console.WriteLine(ans);
        }
    }
}

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

template<typename T>
ostream& operator<<(ostream &os, vector<T> &v){
	string sep = " ";
	if(v.size()) os << v[0];
	for(int i=1; i<v.size(); i++) os << sep << v[i];
	return os;
}

template<typename T>
istream& operator>>(istream &is, vector<T> &v){
	for(int i=0; i<v.size(); i++) is >> v[i];
	return is;
}

#ifdef DBG
void debug_(){ cout << endl; }
template<typename T, typename... Args>
void debug_(T&& x, Args&&... xs){
	cout << x << " "; debug_(forward<Args>(xs)...);
}
#define dbg(...) debug_(__VA_ARGS__)
#else
#define dbg(...)
#endif

int main() {
	ios_base::sync_with_stdio(false);
	cout << setprecision(20) << fixed;

	int n; cin >> n;
	vector<pair<int, int>> es(n-1);
	for(int i=0; i<n-1; i++){
		int u, v;
		cin >> u >> v;
		es[i] = {u, v};
	}

	ll ans = 0;
	for(ll i=0; i<n; i++){
		ans += (n-i+1)*(n-i)/2;
	}

	for(int i=0; i<n-1; i++){
		int u = es[i].first;
		int v = es[i].second;
		ans -= (ll)min(u, v) * (n+1-max(u, v));
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 4836
#include<iostream>
#include<string>
#include<vector>
using namespace std;
#define ll long long
int main()
{

	ll n, k, q,qpqp;
	vector<ll> a;
	cin >> n >> k >> q;
	for (ll i = 0; i < q; i++)
	{
		cin >> qpqp;
		a.push_back(qpqp);
	}
	vector<ll> points(n,k-q);

	for (ll i = 0; i < q; i++)
	{
		points[a[i] - 1]++; 
	}
	for (ll i = 0; i < n; i++)
	{
		if (points[i] > 0) {
			cout << "Yes" << endl;
		}
		else {
			cout << "No" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 2292
import sys
v=[0]*101
for e in sys.stdin:
 a,b=map(int,e.split())
 v[a]+=1;v[b]+=1
 if a==0:
  print(['NG','OK'][(v[1]&1)*(v[2]&1)*sum(x&1 for x in v)==2])
  v=[0]*101


Measured memory_bytes: 5608
#include<bits/stdc++.h>
using namespace std;
int main(void){
  char s[1000];
  cin >> s;
  int len = strlen(s);
  int cnt = 0;
  for(int i = 0; i < len / 2; i++) if(s[i] != s[len - i - 1]) cnt++;
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main () {
  char num[10], c=0;

  for (int i=0; i<3; i++) {
    scanf("%c", &num[i]);
  }
  for (int i=0; i<3; i++) {
    if (num[i]=='1')
     c++;
  }

  printf("%d\n", c);
  return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <utility>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cstdio>
#include <math.h>
#include <stdio.h>
#include <deque>

using namespace std;

#define REP(i,n,m) for( long long int i = (n); i < (m); i++ )
#define REV(v) for (auto itr = v.rbegin(); itr != v.rend(); itr++)
#define ll long long
#define ALL(a) (a).begin(), (a).end()
#define SORT(v) sort( ALL(v) );
#define LAST(v) v[v.size()-1]
#define ZERO(a) memset(a,0,sizeof(a));
#define MINUS(a) memset(a,-1,sizeof(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 pi pair<int, int>
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define IIN(a) int a; cin >> a;
#define LIN(a) ll a; cin >> a;
#define SIN(a) string a; cin >> a;
#define VL(v,n) vector<ll> v(n);
#define Read_VL(v,n) vector<ll> v(n);REP(i,0,n)cin>>v[i];
#define sumV(v,n) Vl(acm,n) REP(i,0,n) acm[i] = v[i] + ( i == 0 ? 0 : acm[i - 1]);
#define EPS (1e-10)
#define INF 1000000000000LL

void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}

template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}


template<class T=ll>struct Graph{
	int n;
	vector<vector<tuple<ll,T>>>edge;
	Graph(int N=1):n(N){edge.resize(n);}
	void add(ll f,ll t,T c,bool d=false){
		edge[f].emplace_back(t,c);
		if(!d)edge[t].emplace_back(f,c);
	}
	void view(){
		REP(i,0,n)for(auto&e:edge[i])
			puta(i,"=>",get<0>(e),", cost :",get<1>(e));
	}
};


bool length_cmp( string &a, string &b ){
  return a.size() < b.size();
}

ll StoLL( string s )
{
	ll num=0;
  REP( i, 0, s.size() ){
    num = num * 10 + ( s[i] ^ 48 );
  }
  return num;
}

ll CtoLL( char c )
{
	if( 'a' <= c && c <= 'z'){
		return (ll)( c ^ 96 ) ;
	}
	else if( 'A' <= c && c <= 'Z'){
		return (ll)( c ^ 64 );
	}
  return 0;
}

ll mod=1000000007;
ll dx[4] = { 1, 0, -1, 0 };
ll dy[4] = { 0, 1, 0, -1 };
//I ASCII code: '0' = 48; 'A' = 65; 'a' = 97

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    LIN(n) LIN(m) LIN(X) LIN(Y)
    if( X >= Y ){
      puta( "War" );
      return 0;
    }
    Read_VL(x,n)
    x.PB(X);
    Read_VL(y,m)
    y.PB(Y);
    
    SORT(x)
    SORT(y)
    if( LAST(x) >= y[0] ){
      puta( "War" );
      return 0;
    }

    puta( "No War" );

    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
//change null_type here for map/set
typedef tree<int,null_type,less<int>,rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;
typedef long long int  ll;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define F first
#define S second

template<class T>inline bool read(T &x){
    int c=getchar();int sgn=1;
    while(~c&&c<'0'||c>'9'){if(c=='-')sgn=-1;c=getchar();}
    for(x=0;~c&&'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';
    x*=sgn; return ~c;
}
///START HERE
///indexed_set pbd;
//pbd.insert()
//auto x = pbd.find_by_order(2);
//int od=pbd.order_of_key(7)
///rope<int> rp;
//rp.push_back()
//RandomAccess like vector
//mutable_begin, mutable_end()

int main(){
    ///read()+printf
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //fast;
    int n,x,t;
    cin>>n>>x>>t;
    int z=n/x;
    if(n%x!=0)
        z++;
    cout<<z*t;

    return 0;
}


Measured memory_bytes: 3592
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define mp make_pair
#define v vector
#define inp_push(no, v) \
    ll no;              \
    cin >> no;          \
    v.push_back(no);
#define pb push_back
#define fi first
#define se second
#define ALL(v) v.begin(), v.end()
#define UN(v) sort((v).begin(), (v).end()), v.erase(unique(v.begin(), v.end()), v.end())
#define N 300005
#define mod 1000000009
#define INF INT64_MAX

//////////////////////////IMPORTANT FUNCTIONS/////////////////////////////////////////////

/* Guidlines berfore submitting solution
1. Check N value before submitting
2. Check all constant kind of values you are using. Might give WA. Think
3. Check mod value
*/

v<ll> fact(N);
v<ll> prime_check(1e6 + 2);
v<ll> primes;

long long powmod(long long x, long long y, long long m)
{
    long long res = 1LL;
    while (y)
    {
        if (y & 1)
            res = (res * x) % m;
        x = (x * x) % m;
        y /= 2;
    }
    return res;
}

void init_fact()
{
    fact[0] = 1;
    for (ll i = 1; i < N; i++)
    {
        fact[i] = (fact[i - 1] * i) % mod;
    }
}

ll C(ll n, ll r)
{
    if (n < r)
        return 0;
    ll temp = fact[n] * powmod(fact[r], mod - 2, mod) % mod;
    temp *= powmod(fact[n - r], mod - 2, mod);
    temp %= mod;
    return temp;
}

void Sieve()
{
    for (ll i = 2; i <= 1e6 + 1; i++)
    {
        if (prime_check[i])
            continue;
        primes.pb(i);
        for (ll j = 2 * i; j <= 1e6 + 2; j += i)
            prime_check[j] = i;
    }
}
ll phi(ll n)
{
    ll i, res = n;
    for (i = 2; i * i <= n; i++)
        if (n % i == 0)
        {
            while (n % i == 0)
                n /= i;
            res -= res / i;
        }
    if (n > 1)
        res -= res / n;
    return res;
}

/////////////////////////////////////START CODE HERE/////////////////////////////////////////////

ll a;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // init_fact();
    // Sieve();
    cin >> a;
    cout << a + a * a + a * a * a << "\n";
}

Measured memory_bytes: 13340
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
using namespace std;
#define INF 110000000000
#define MAX 100000
typedef long long ll;
typedef pair<ll,int> P;



int main(){
  string s;
  cin>>s;
  if(s[0]==s[1] && s[2]==s[3] && s[0]!=s[2]) cout<<"Yes"<<endl;
  else if(s[0]==s[2] && s[1]==s[3] && s[0]!=s[1]) cout<<"Yes"<<endl;
  else if(s[0]==s[3] && s[2]==s[1] && s[0]!=s[2]) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}


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

static const int N =100;

int main(){
	int n, p[N+1], m[N+1][N+1];
	cin >> n;
	for( int i = 1; i <= n; i++){
	    cin >> p[i-1] >> p[i];
}

	for( int i = 1; i <= n; i++ ) m[i][i] = 0;
	for( int l = 2; l <= n; l++ ) {
	  for( int i = 1; i<= n-l+1; i++ ) {
		int  j = i + l - 1;
		m[i][j] = (1 << 21);
		for( int k = i; k <= j - 1; k++){
		  m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]);
		}
	}
}

	cout << m[1][n] << endl;

	return 0;
}

Measured memory_bytes: 3116
/*------------------------- Bism Allah Alruhmin Alrahim -------------------------------*/
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < n; i++)
#define ford(i, n) for (int i = n - 1; i > -1; i--)
#define forl(i, l, r) for (int i = l; i <= r; i++)
#define vc vector
#define f first
#define s second
#define L size()

#define pb(i) push_back(i)
#define mx(ar, n) (*max_element(ar, ar + n))
#define mn(ar, n) (*min_element(ar, ar + n))

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // ----------------------
    int n , l ;
    cin >> n >> l ;
    int sum = 0 , m = 1000000;
    for (int i = 1; i <= n; i++)
    {
       m = min(m , abs(l+i-1));
       sum+=(l+i-1);

    }
    for (int i = 1; i <= n; i++)
    {
       if(m == abs(l+i-1)){
           sum-=(l+i-1);
       }
    }
    cout << sum << endl ;
    
    return 0 ;
}

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

int main(){
  int N;
  cin >> N;
  vector<uint64_t> vec(87);
  
  vec[0] = 2;
  vec[1] = 1;
  
  for (int i = 2; i < 87; i++)
    vec[i] = vec[i-1] + vec[i-2];
  
  cout << vec[N] << endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;

void b_stone_monument(void) {
	int a, b;
	cin >> a >> b;

	int diff = b - a;
	int sum = 0;
	for (int i = 1; i <= diff; i++) sum += i;

	cout << sum - b << endl;
}

int main()
{
	b_stone_monument();
    return 0;
}

Measured memory_bytes: 3588
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <numeric>
using namespace std;
int main(){
  int n, k, l;
  int N[100001], ans, sum, tmp;
  while(cin >> n >> k, n && k){
    ans = 0, sum = 0;
    for(int i = 0 ; i < n ; i++){
      cin >> N[i];
    }

    for(l = 0 ; l < k ; l++){
      sum += N[l];
    }
    ans = max(ans, sum);
    tmp = sum;
    for(int i = l ; i < n ; i++){
      tmp = sum;
      sum += N[i];
      sum -= N[i-k];
      tmp = sum;
      ans = max(ans, sum);
    }
    cout << ans << endl;
  }
  return 0;
}

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

using namespace std;
typedef pair<int,int> pii;
typedef long long int ll;

#define INF 1 << 30
#define REP(i,n) for(ll i=0; i<(int)(n); i++)
#define FOR(i,k,n) for(ll i=(k);i<(int)(n);i++)



int n;
string s;

int main(){
  cin >> n;
  s = "";
  if(n==0){
    cout << 0 <<endl;
    return 0;
  }
  while(n!=0){
    if(n%2!=0){
      s.push_back('1');
      n -= 1;
    }else{
      s.push_back('0');
    }
    n/=-2;
  }
  reverse(s.begin(),s.end());
  cout << s <<endl;
}


Measured memory_bytes: 256
/*
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
*/
#include <bits/stdc++.h>

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

int main()
{
    int a[3][3],n;
    rep(i,3){
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }
    cin >> n;
    int b;
    rep(i,n){
        cin >> b;
        rep(j,3){
            rep(k,3){
                if(a[j][k] == b){
                    a[j][k] = 0;
                }
            }
        }
    }
    int count = 0;
    rep(i,3){
        if(!(a[i][0]+a[i][1]+a[i][2])) count++;
        if(!(a[0][i]+a[1][i]+a[2][i])) count++;
    }
    if(!(a[0][0]+a[1][1]+a[2][2])) count++;
    if(!(a[0][2]+a[1][1]+a[2][0])) count++;

    if(count == 0){
        cout << "No";
    }else{
        cout << "Yes";
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N, M, K;
  cin >> N >> M >> K;
  string ans = "No";
  for(int i=0; i<=N; i++){
    for(int j=0; j<=M; j++){
      int count = 0;
      count = i*j + (N-i)*(M-j);
      if(count == K){
        ans = "Yes";
      }
    }
  }
  cout << ans << endl;
}

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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(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) int(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>>;

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 = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n; cin>>n;
  vll s(n+1);
  
  rep(i,n){
    ll a; cin>>a;
    s[i+1]=s[i]+a;
  }
  map<ll,ll> m;
  rep(i,n+1) m[s[i]]++;
  
  ll ans=0;
  for(auto e: m){
    ans+=e.second*(e.second-1)/2;
  }
  
  cout<<ans<<endl;
}

Measured memory_bytes: 14336
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <assert.h>

using namespace std;
#define int long long
int MOD = 1000000007;
int N;
int askc = 0;
map<int, int> mp;
int ask(int i) {
	i = i%N;
	if (mp.count(i) == 1) {
		return mp[i];
	}
	askc++;
	cout << i << endl;
	cout << flush;
	string s;
	cin >> s;
	if (s == "Male") {
		return mp[i] = 1;
	}
	else if (s == "Female") {
		return mp[i] = -1;
	}
	else {
		return mp[i] = 0;
	}
}
vector<int>A;
//int ask(int i) {
//	cout << i << endl;
//	return A[i];
//}
signed main() {

	cin >> N;
	/*int xx = 99998;
	N = 99999;
	A.resize(N);
	A[0] = 1;
	for (int i = 1; i < xx; i++) {
		A[i] = -A[i - 1];
	}
	A[xx] = 0;
	A[xx + 1] = -A[xx - 1];
	for (int i = xx + 2; i < N; i++) {
		A[i] = -A[i - 1];
	}*/
	int u = N / 2;
	int d = 0;
	int uu = ask(0);
	if (uu == 0)return 0;
	int dd = ask(N / 2);
	if (dd == 0)return 0;
	int m;
	int mm;
	if ((((u - d) % 2 == 0) && (uu == dd)) || (((u - d) % 2 == 1) && (uu != dd))) {
		d = N / 2;
		u = N;
		swap(uu, dd);
	}
	while (true) {
		uu = ask(u);
		dd = ask(d);
		m = (u + d) / 2;
		mm = ask(m);
		if (mm == 0)break;
		//cerr << u << " " << m << " " << uu << " " << mm << endl;
		if ((((u - m) % 2 == 0) && (uu == mm)) || (((u - m) % 2 == 1) && (uu != mm))) {
			u = m;
			uu = mm;
		}
		else if ((((m - d) % 2 == 0) && (dd == mm)) || (((m - d) % 2 == 1) && (dd != mm))) {
			d = m;
			dd = mm;
		}
		else {
			assert(false);
		}
	}
	return 0;
	//cout << res << endl;
}

Measured memory_bytes: 852
/* ~ Programmer >> Tushar Mahajan */
#include <iostream>
#include <bits/stdc++.h> 
using namespace std;
#define ll long long int
#define MOD 1000000007
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL); 

int main() {
	ios;
	int n,k,sum =0;
	cin>>n>>k;
	int a[n];
	for(int i=0;i<n;i++)
	{
	    cin>>a[i];
	}
	sort(a,a+n);
	for(int i=0;i<k;i++)
	{
	    sum +=a[i];
	}
	cout<<sum<<endl;
	return 0;
}


Measured memory_bytes: 3660
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <array>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define loop(i, a, n) for (int i = a; i < (n); i++)
#define all(in) in.begin(), in.end()
#define INF 1e9;
#define MOD 1e9 + 7;
int main() {
    long long N, M;
    cin >> N >> M;
    long long A[N], B[N];
    pair<long long, long long> drink[N];
    rep(i, N) {
        int a, b;
        cin >> a >> b;
        drink[i].first = a, drink[i].second = b;
    }
    sort(drink, drink + N);
    long long ans = 0;
    long long count = 0;
    rep(i, N) {
        if (count <= M - drink[i].second) {
            ans = ans + drink[i].first * drink[i].second;
            count = count + drink[i].second;
        } else {
            ans = ans + drink[i].first * (M - count);
            break;
        }
        // cout << ans << endl;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1920
using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
    static void Main(string[] args)
    {
        string[] s = Console.ReadLine().Split(' ');
        int A = int.Parse(s[0]);
        int B = int.Parse(s[1]);
        for(int i = 1; i <= 3; i++)
        {
            if((A * B * i) % 2 == 1)
            {
                Console.WriteLine("Yes");
                return;
            }
        }
        Console.WriteLine("No");
    }
}


Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
int main(){
  int d, n;
  cin >> d >> n;
  int cnt = 0;
  int divise = 1;
  for(int i = 0; i < d; i++)
    divise *= 100;
  for(int i = 1; i >= 0; i++){
    if(i % divise == 0){
      int hoge = i / divise;
      if(hoge % 100 != 0){
        cnt++;
        if(cnt == n){
          cout << i << endl;;
          return 0;
        }
      }
    }
  }
}

Measured memory_bytes: 256
import scala.io.StdIn.{readLine, readInt}

object Main {
  def gcd(x:Long, y:Long):Long = if(y==0) x else gcd(y, x%y)
  def lcm(x:Long, y:Long) = (x/gcd(x,y))*y

  def main(args:Array[String]) = {
    val n = readInt
    val l = readLine.split(" ").map(_.toLong)
    var r = l(0)
    for(i<- 1 until n) {
      r = lcm(r,l(i))
    }
    println(r)
  }
}

Measured memory_bytes: 43880
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0 ; i < n ; i++) {
            String t = s.substring(i, i + 1);
            if (map.containsKey(t)) {
                map.put(t, map.get(t) + 1);
            } else {
                map.put(t, 1);
            }
        }
        long mod = 1000000007;
        long sum = 1l;
        for (Entry<String, Integer> entry : map.entrySet()) {
            long c = entry.getValue();
            sum *= (long) (c + 1) % mod;
            sum %= (long) mod;
        }

        System.out.println(sum - 1);

    }

}


Measured memory_bytes: 34360
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define shosu(n) setprecision(n)
#define INF 1000000000;
using namespace std;
int main() {
  long long A, B;
  while (cin >> A >> B) {
    int step = 0;
    if (A == 0 && B == 0)
      break;
    if (A < B)
      swap(A, B);
    for (int i = 0; B > 0; i++) {
      A = A % B;
      swap(A, B);
      step++;
    }
    cout << A << ' ' << step << endl;
  }
  return 0;
}

Measured memory_bytes: 2988
#include <iostream>
#include <string>

using namespace std;

int main(){
	int N;
	string S, T;

	cin >> N;
	cin >> S >> T;

	for(int i = 0; i < N; i++){
		cout << S.at(i) << T.at(i);
	}

	cout << endl;

	return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,A,B;
  cin>>N>>A>>B;
  int ans=0;
  for(int i=1;i<=N;i++){
    int sum;
    sum=i/10000+i%10000/1000+i%1000/100+i%100/10+i%10;
    if(sum>=A&&sum<=B) ans+=i;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256