akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
using namespace std;



int main(){
    int n,r,ans;
    cin>>n;
    cin>>r;
    if(n<=10){
        ans=r+100*(10-n);
        cout<<ans<<endl;
    }
    else{
        cout<<r<<endl;
    }
    return 0;
}

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

int main(){
    int P,Q,R,A,B,C;
    cin >> P >> Q >> R;
    A=P+Q;
    B=Q+R;
    C=R+P; 
    if(P>=Q){
        if(P>=R){
            cout << B << endl;
        }
        else{
            cout << A << endl;
        }
    }
    else{
        if(R>=Q){
            cout << A << endl;
        }
        else{
            cout << C << endl;
        }
    }
}


Measured memory_bytes: 256
import math 
K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(i,K+1):
        for k in range(j,K+1):
            d = math.gcd(math.gcd(i,j),k)
            if i==j==k:
                ans += d
            elif i==j or j== k or k==i:
                ans += 3*d
            else:
                ans += 6*d
print(ans)


Measured memory_bytes: 68052
package main

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

func Solve() {
  var K int
  NextInt(&K)
  if K % 7 == 0 { K /= 7 }
  k := K % 10
  if k % 2 == 0 || k == 5 { Write(-1); return }
  B := make([][]int, 10)
  B[1] = []int{1, 0, 9, 8, 7, 6, 5, 4, 3, 2}
  B[3] = []int{7, 0, 3, 6, 9, 2, 5, 8, 1, 4}
  B[7] = []int{3, 0, 7, 4, 1, 8, 5, 2, 9, 6}
  B[9] = []int{9, 0, 1, 2, 3, 4, 5, 6, 7, 8}
  L := 0
  for X := K * B[k][0]; X > 0; X /= 10 {
    X += K * B[k][X % 10]
    L++
  }
  Write(L)
}

func main() {
  Solve()
  Output()
}

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt(A ...*int) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.Atoi(L[i])
  }
}
func NextIntSlice(A *[]int) {
  L := strings.Split(NextLine(), " ")
  if len(L) == 1 && L[0] == "" {
    (*A) = make([]int, 0)
    return
  }
  (*A) = make([]int, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.Atoi(l)
  }
}
func NextFloat(A ...*float64) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.ParseFloat(L[i], 64)
  }
}
func NextFloatSlice(A *[]float64) {
  L := strings.Split(NextLine(), " ")
  if len(L) == 1 && L[0] == "" {
    (*A) = make([]float64, 0)
    return
  }
  (*A) = make([]float64, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.ParseFloat(l, 64)
  }
}
func Write(S ...interface{}) {
  fmt.Fprintln(writer, S...)
}
func WriteIntSlice(A []int) {
  B := make([]interface{}, len(A))
  for i, a := range A { B[i] = a }
  fmt.Fprintln(writer, B...)
}
func Output() {
  _ = writer.Flush()
}
func MaxInt(A ...int) int {
  max := A[0]
  for _, a := range A {
    if max < a { max = a }
  }
  return max
}
func MinInt(A ...int) int {
  min := A[0]
  for _, a := range A {
    if a < min { min = a }
  }
  return min
}
func SumInt(A ...int) int {
  sum := 0
  for _, a := range A {
    sum += a
  }
  return sum
}
func AbsInt(x int) int {
  if x < 0 { x = -x }
  return x
}

Measured memory_bytes: 1836
object Main extends App {
    val in = io.Source.stdin.getLines
    for (n <- in if n != "0") {
        var town_size = 0
        val es = in.take(n.toInt).flatMap(e => {
            val Array(a, b, c) = e.split(" ").map(_.toInt)
            town_size = town_size max a max b
            Seq((a, b, c), (b, a, c))
        }).toList
        val costs = for (town <- (0 to town_size)) yield {
            val g = Array.fill(town_size+1)(Int.MaxValue-100)
            g(town) = 0
            var flag = true
            while(flag) {
                flag = false
                for (e <- es) if (g(e._1) + e._3 < g(e._2)) {g(e._2) = g(e._1) + e._3; flag = true}
            }
            Seq(town, g.sum)
        }
        println(costs.minBy(_(1)).mkString(" "))
    }
}

Measured memory_bytes: 44076
var i,n,tl,c,t,m:integer;

begin
  readln(n,tl);
  m := 1001;
  for i := 1 to n do begin
    readln(c,t);
    if (t <= tl) and (c < m) then m := c;
  end;
  if m = 1001 then writeln('TLE') else writeln(m)
end.

Measured memory_bytes: 128
from sys import stdin

def solve():
    file_input = stdin
    while True:
        D = float(file_input.readline())
        if D == 0:
            break
        px, py, vx, vy = map(float, file_input.readline().split())
        if px * vy - py * vx == 0:
            OP = (px ** 2 + py ** 2) ** 0.5
            if px * vx + py * vy < 0:
                if OP <= D:
                    print(OP)
                else:
                    print('impossible')
            else:
                d = 2 - OP
                if d <= D:
                    print(d)
                else:
                    print('impossible')
        else:
            print('impossible')

solve()


Measured memory_bytes: 5652
#include <bits/stdc++.h>
using namespace std;
const int sz=105;
int dp[sz][sz];
int m=1000000007;
int add(int a,int b){return (a%m+b%m)%m;}
int H,W,k;


int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d %d %d",&H,&W,&k);
    k--;
    dp[0][0]=1;
    for(int h=0;h<H;h++){
        for(int w=0;w<(1<<(W-1));w++){
            bool ok=1;
            for(int i=0;i+1<W-1;i++){
                if(((w>>i)&1)&&((w>>(i+1))&1)){
                    ok=0;
                    break;
                }
            }
            if(!ok) continue;
            for(int i=0;i<W;i++){
                if((w>>i)&1) dp[h+1][i+1]=add(dp[h+1][i+1],dp[h][i]);
                else if(i>0&&((w>>(i-1))&1)) dp[h+1][i-1]=add(dp[h+1][i-1],dp[h][i]);
                else dp[h+1][i]=add(dp[h+1][i],dp[h][i]);
            }
        }
    }
    printf("%d",dp[H][k]);

    return 0;
}


Measured memory_bytes: 256
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from heapq import heappop, heappush
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def main():
    K = int(input())
    dp = [INF] * K
    dp[1] = 1

    heap = []
    heappush(heap, (1, 1))

    while len(heap) != 0:
        k, p = heappop(heap)
        if dp[(p + 1) % K] > dp[p] + 1:
            dp[(p + 1) % K] = dp[p] + 1
            heappush(heap, (dp[p] + 1, (p + 1) % K))
        if dp[(p * 10) % K] > dp[p]:
            dp[(p * 10) % K] = dp[p]
            heappush(heap, (dp[p], (p * 10) % K))

        if dp[0] != INF:
            break

    print(dp[0])


if __name__ == '__main__':
    main()


Measured memory_bytes: 9704
module DoublyChainedTree = struct
  let nil = -1

  type t = {
    mutable parent : int;
    mutable child : int;
    mutable bro : int;
    mutable depth : int;
  }

  let make () = { parent = nil; child = nil; bro = nil; depth = nil }
end

module T = DoublyChainedTree

let () =
  let n = read_int () in
  let t = Array.init n (fun _ -> T.make ()) in
  let rec read_tree i =
    if i < n then begin
      match List.map int_of_string (Str.split (Str.regexp " ") (read_line ())) with
      | id :: _ :: tl -> begin
          let rec read_lst j left_child = function
            | [] -> ()
            | c :: cs -> begin
                t.(c).T.parent <- id;
                if j = 0 then t.(id).T.child <- c else t.(left_child).T.bro <- c;
                read_lst (j+1) c cs
              end
          in
          read_lst 0 0 tl;
          read_tree (i + 1)
        end
      | _ -> exit 1
    end
  in
  read_tree 0;
  let rec search_root i =
    if i = n then T.nil
    else if t.(i).T.parent = T.nil then i
    else search_root (i + 1)
  in
  let root = search_root 0 in
  let rec set_depth i p =
    t.(i).T.depth <- p;
    if t.(i).T.bro <> T.nil then set_depth t.(i).T.bro p;
    if t.(i).T.child <> T.nil then set_depth t.(i).T.child (p + 1);
  in
  set_depth root 0;
  let print_node i =
    Printf.printf "node %d: parent = %d, depth = %d, " i t.(i).T.parent t.(i).T.depth;
    print_string (if t.(i).T.parent = T.nil then "root, " else if t.(i).T.child = T.nil then "leaf, " else "internal node, ");
    print_string "[";
    let rec print_children c =
      if c <> T.nil then begin
        if c <> t.(i).T.child then print_string ", ";
        print_int c;
        print_children t.(c).T.bro
      end
    in
    print_children t.(i).T.child;
    print_endline "]"
  in
  let rec print i =
    if i < n then (print_node i; print (i + 1))
  in
  print 0

Measured memory_bytes: 19052
#include <cstdio>

int main(){
    int a,b,c,d;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    if(a + b > c + d){
        printf("Left\n");
    }else if(a + b < c + d){
        printf("Right\n");
    }else{
        printf("Balanced\n");
    }

    return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
int main(void){
	int n,k[100],i,j;
	char s[101];
	while(1){
		scanf("%d",&n);
		if(!n)
			break;
		for(i=0;i<n;i++)
			scanf("%d",&k[i]);
		scanf("%s",s);
		for(i=0;s[i];i++){
			for(j=0;j<k[i%n];j++){
				if(s[i]=='A')
					s[i]='z';
				else if(s[i]=='a')
					s[i]='Z';
				else
					s[i]--;
			}
		}
		printf("%s\n",s);
	}
	return 0;
}

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

using namespace std;

const int N = 100010;

int n;


int main() {
  int ta = 0, xa = 0, ya = 0;
  scanf("%d", &n);
  int ok = 1;
  for(int i = 0; i < n && ok; ++i) {
    int t, x, y; scanf("%d %d %d", &t, &x, &y);
    int d = abs(x - xa) + abs(y - ya);
    ok &= (d <= (t - ta));
    ok &= (((d - (t - ta)) % 2) == 0);
    xa = x;
    ya = y;
    ta = t;
  }
  puts(ok ? "Yes" : "No");

  return 0;
}

Measured memory_bytes: 256
n = int(input())
s = [input() for _ in range(n)]

tail_a_num = 0
head_b_num = 0
both_num = 0
cnt = 0
for i in s:
  if i[0] == 'B':
    head_b_num += 1
  if i[-1] == 'A':
    tail_a_num += 1
  if i[0] == 'B' and i[-1] == 'A':
    both_num += 1
  cnt += i.count('AB')

if both_num > 0:
  cnt += both_num - 1
  head_b_num -= both_num
  tail_a_num -= both_num
  if head_b_num > 0:
    cnt += 1
    head_b_num -= 1
  if tail_a_num > 0:
    cnt += 1
    tail_a_num -= 1

cnt += min(head_b_num,tail_a_num)
  
print(cnt)


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

#define PI 3.1415926535897932
#define MOD 1000000007
#define INF 1e9

#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define FOR(i, start, end) for(int i = (start); i < (end); i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;

void solve()
{
    int N; cin >> N;
    string S; cin >> S >> S;
    vi n;
    REP(i, S.length()-1)
    {
        if(S[i] == S[i+1])
        {
            n.push_back(2);
            i++;
        }
        else n.push_back(1);
    }
    if(S[S.length()-2] != S[S.length()-1]) n.push_back(1);

    ll ans;
    if(n[0] == 1) ans = 3;
    else ans = 6;

    REP(i, n.size()-1)
    {
        if(n[i] == 1 && n[i+1] == 1)
        {
            ans *= 2;
        }
        else if(n[i] == 1 && n[i+1] == 2)
        {
            ans *= 2;
        }
        else if(n[i] == 2 && n[i+1] == 1)
        {
            ans *= 1; 
        }
        else
        {
            ans *= 3;
        }
        ans %= MOD;
    }

    cout << ans << endl;
}

int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    solve();

    return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
ans=10**9
tmp_ans=10**9
prin=0
a=[]
b=[]
for i in range(n):
    x,y=map(int,input().split())
    a.append([x,y])
for i in range(m):
    x,y=map(int,input().split())
    b.append([x,y])
for i in range(n):
    tmp_x=a[i][0]
    tmp_y=a[i][1]
    for j in range(m):
        ans=min((abs(tmp_x-b[j][0])+abs(tmp_y-b[j][1])),ans)
        if tmp_ans!=ans:
            prin=j+1
            tmp_ans=ans
    print(prin)
    ans=10**9
    tmp_ans=10**9


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define lld      long long
#define mp       make_pair
#define pb       push_back
#define ff       first
#define ss       second
#define pll      pair<lld,lld>
#define pii      pair<int,int>
#define vll      vector<lld>
#define vii      vector<int>
#define umap     unordered_map
#define all(x)   x.begin(),x.end()
#define sort1(x) sort(x.begin(),x.end(),greater<int>())
#define rep(i,a,b) for(i = a; i < b; i++)
#define fio      ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;

namespace forever {
    template<class type1,class type2>
        inline istream &operator>>(istream &in,pair<type1,type2> &p)
        {
            in>>p.ff>>p.ss;
            return in;
        }
    template<class type1,class type2>
        inline ostream &operator<<(ostream &o,pair<type1,type2> &p)
        {
             o<<"("<<p.ff<<","<<p.ss<<")";
            return o;
        } 
    template<class type>
        inline ostream &operator<<(ostream &o,vector<type> &v)
        {
            for(int i=0;i<v.size();i++)
                o<<v[i]<<" ";
            return o;    
        }
    template<class t>
        inline istream &operator>>(istream &in,vector<t> &p)
        {
            for(auto & x : p)
                in >> x;
            return in;
        }
    struct custom_hash {
        static uint64_t splitmix64(uint64_t x) {
            x += 0x9e3779b97f4a7c15;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
            x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
            return x ^ (x >> 31);
        }
        size_t operator()(uint64_t x) const {
            static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
            return splitmix64(x + FIXED_RANDOM);
        }
    };
}
using namespace forever;

int main()
{
	fio; 	
	/*#ifndef ONLINE_JUDGE
    freopen("sip.txt","r",stdin);
   	//freopen("sout.txt","w",stdout);
    #endif
    */
    int n,i;
    cin >> n;
    vii a(n),b(n);
    cin >> a >> b ;
    string s="",ss="";
    int x = -1,flag=0;
    for(i=0;i<n;i++){
        if(a[i] == b[i]){
            
        }
        else if(flag==0){
            if(a[i] < b[i])
                x = 1;
            else
                x = 2; 
            flag = 1;    
        }
        
        s += a[i] + '0';
        ss += b[i] + '0';
    }
    if(x==-1){
        cout << "0\n";
        return 0;
    }
    if(x==2)
        swap(s,ss);
    int ans = 0;
    //cout << s << " " << ss << "\n";
    while(true){
        ans++;
        next_permutation(s.begin(),s.end());
        if(s == ss)
            break;                
    }
    cout << ans << "\n";
    
    
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
int main() {
  ll n,k;
  cin >> n >> k;
  if ( n == 0 ) {
    cout << 0 << endl;
  } else if ( n%k == 0 ) {
    cout << 0 << endl;
  } else {
    n %= k;
    cout << min(n,abs(n-k)) << endl;
  }
}


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

const int NUM = 3;

int main() {
  int b[10] = {0};

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

  if (b[5] == 2 && b[7] == 1) {
    printf("YES");
  } else {
    printf("NO");
  }
  return 0;
}


Measured memory_bytes: 256
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>

using namespace std;

typedef long long ll;

#ifdef iq
  mt19937 rnd(228);
#else
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

const int N = 2e5;

ll reg[N];

struct op {
  char x;
  int a, b, c;
};

int main() {
#ifdef iq
  freopen("a.in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
  int a = 0, b = 1;
  int ans = 2;
  int zero = 3;
  int sz = 4;
  vector <op> e;
  auto sum_query = [&] (int i, int j, int k) {
    reg[k] = reg[i] + reg[j];
    e.push_back({'+', i, j, k});
  };
  auto sum = [&] (int i, int j) {
    int k = sz++;
    sum_query(i, j, k);
    return k;
  };
  auto less = [&] (int i, int j) {
    int k = sz++;
    reg[k] = (reg[i] < reg[j]);
    e.push_back({'<', i, j, k});
    return k;
  };
  int tot = sum(a, b);
  int one = less(zero, tot);
  auto AND = [&] (int i, int j) {
    int x = sum(i, j);
    return less(one, x);
  };
  vector <int> pw(64);
  pw[0] = one;
  for (int i = 1; i < 64; i++) {
    pw[i] = sum(pw[i - 1], pw[i - 1]);
  }
  int a_plus_1 = sum(a, one);
  int b_plus_1 = sum(b, one);
  auto shift = [&] (int s, int j) {
    for (int i = 1; i <= j; i++) {
      s = sum(s, s);
    }
    return s;
  };
  auto binary = [&] (int p) {
    int cur = zero;
    vector <int> ord(32);
    for (int i = 31; i >= 0; i--) {
      int x = sum(cur, pw[i]);
      int check = less(x, p);
      int here = shift(check, i);
      cur = sum(cur, here);
      ord[i] = check;
    }
    return ord;
  };
  auto x = binary(a_plus_1), y = binary(b_plus_1);
  vector <int> s(64);
  for (int i = 0; i < 64; i++) {
    s[i] = zero;
  }
  for (int i = 0; i < 32; i++) {
    for (int j = 0; j < 32; j++) {
      int cur = AND(x[i], y[j]);
      s[i + j] = sum(s[i + j], cur);
    }
  }
  ans = zero;
  for (int i = 0; i < 64; i++) {
    ans = sum(ans, shift(s[i], i));
  }
  sum_query(ans, zero, 2);
  cout << e.size() << '\n';
  for (auto c : e) {
    cout << c.x << ' ' << c.a << ' ' << c.b << ' ' << c.c << '\n';
  }
}


Measured memory_bytes: 3772
c = []
for i in range(3):
  c.append([int(x) for x in input().split()])
res = "No"
for i in range(101):
  for j in range(101):
    for k in range(101):
      if c[0][0] - i == c[1][0] - j == c[2][0] - k:
        if c[0][1] - i == c[1][1] - j == c[2][1] - k:
          if c[0][2] - i == c[1][2] - j == c[2][2] - k:
            res = "Yes"
print(res)

Measured memory_bytes: 9032
#include<bits/stdc++.h>
using namespace std;
int a[100005];
map<int,int>mp;
int main()
{
	int n,ans=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&a[i]);
	for(int i=0;i<n;i++)mp[a[i]]++;
	for(int i=0;i<n;i++)ans=max(ans,mp[a[i]-1]+mp[a[i]]+mp[a[i]+1]);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 5120
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi M_PI
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int main() {
    string s, t;
    cin >> s;
    int ans = 0;
    while (cin >> t && t != "END_OF_TEXT"){
        if (s.length() != t.length()) continue;
        int f = 1;
        REP(i,s.length()){
            if ((s[i]-t[i])%('a'-'A') != 0) f = 0;
        }
        ans += f;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll n, m, Q;
  cin >> n >> m >> Q;
  vector<vl> g(n, vl(n, 0));
  rep(i, m) {
    ll l, r;
    cin >> l >> r;
    l--;
    r--;
    g[l][r]++;
  }
  vector<vl> s(n + 1, vl(n + 1, 0));
  rep(i, n) rep(j, n) s[i + 1][j + 1] =
      s[i + 1][j] + s[i][j + 1] - s[i][j] + g[i][j];
  rep(_, Q) {
    ll p, q;
    cin >> p >> q;
    p--;
    cout << s[q][q] - s[p][q] - s[q][p] + s[p][p] << '\n';
  }
}

Measured memory_bytes: 7540
# include <bits/stdc++.h>
using namespace std;
namespace Base{
	# define mr make_pair
	typedef long long ll;
	typedef double db;
	const int inf = 0x3f3f3f3f, INF = 0x7fffffff;
	const ll  infll = 0x3f3f3f3f3f3f3f3fll, INFll = 0x7fffffffffffffffll;
	template<typename T> void read(T &x){
    	x = 0; int fh = 1; double num = 1.0; char ch = getchar();
		while (!isdigit(ch)){ if (ch == '-') fh = -1; ch = getchar(); }
		while (isdigit(ch)){ x = x * 10 + ch - '0'; ch = getchar(); }
	    if (ch == '.'){
	    	ch = getchar();
	    	while (isdigit(ch)){num /= 10; x = x + num * (ch - '0'); ch = getchar();}
		}
		x = x * fh;
	}
	template<typename T> void chmax(T &x, T y){x = x < y ? y : x;}
	template<typename T> void chmin(T &x, T y){x = x > y ? y : x;}
}
using namespace Base;

const int P = 1e9 + 7, N = 5010, M = 1e7 + 10;
int mul[M], inv[M], m, n, ans, c[N][N];
int power(int x, int y){
	int i = x; x = 1;
	while (y > 0){
		if (y & 1) x = 1ll * i * x % P;
		i = 1ll * i * i % P;
		y /= 2;
	}
	return x;
}
int main(){
	read(m); read(n);
	mul[0] = 1; for (int i = 1; i <= m; i++) mul[i] = 1ll * mul[i - 1] * i % P;
	inv[m] = power(mul[m], P - 2); 
	for (int i = m - 1; i >= 0; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % P;
	for (int i = 0; i <= n; i++){
		c[i][0] = 1;
		for (int j = 1; j <= i; j++)
			c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P;
	}
	for (int i = n + 1; i >= 2; i--){
		int fh;
		for (int j = 0; j <= i - 1; j++){
			if (j % 2 == 0) fh = c[i - 1][j]; else fh = -c[i - 1][j];
			int a = i - 1 - j, b = m - n, c = max(0, n - i);
			ans = (ans + 1ll * fh * mul[a + b + c] % P * a % P * inv[a + b] % P * mul[a + b - 1] % P + P) % P;
		}
	}
	cout << ans << endl;
    return 0;
}


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

using namespace std;
using llong = long long;
using ldbl = long double;
using P = pair<llong, llong>;

#define ALL(x) x.begin(), x.end()

const llong inf = 1100100100100100ll;
const llong mod = 1e9+7;

llong GCD(llong a, llong b){
	a = abs(a), b = abs(b);
	if(a < b) swap(a, b);
	if(b == 0) return a;
	while(b){
		a %= b;
		swap(a,b);
	}

	return a;
}

llong LCM(llong a, llong b){
	return a / GCD(a, b) * b;
}

int main() {
	llong a,b,c,d;
	cin >> a >> b >> c >> d;
	a--;

	llong lcm = LCM(c,d);
	llong retb = b - b/c - b/d + b/lcm;
	llong reta = a - a/c - a/d + a/lcm;

	cout << retb - reta << endl;

	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;

int main() {
  int h, w;
  int dx[] = {-1, 0, 0, 1};
  int dy[] = {0, -1, 1, 0};
  cin >> h >> w;
  string map[h], r = "Yes";
  rep(i, h) cin >> map[i];
  rep(i, h) {
    rep(j, w) {
      if (map[i][j] == '#') {
        int match = 0, cnt = 0;
        rep(k, 4) {
          int x = i + dx[k];
          int y = j + dy[k];
          if (x >= 0 && x < h && y >= 0 && y < w) match++;
          if (x >= 0 && x < h && y >= 0 && y < w && map[x][y] == '.') cnt++;
        }
        if ((match == cnt) && (cnt > 0)) r = "No";
      }
    }
  }
  cout << r << endl;
  return 0;
}


Measured memory_bytes: 256
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))
ZIP = lambda: zip(*(MAP() for _ in range(n)))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N, M, K = MAP()
    A = LIST()  
    B = LIST() 

    # 3 4 350
    # 60 80 100
    # 90 110 5 5 

    a, b = [0], [0]
    for i in range(N):
        a.append(a[i] + A[i])
    for i in range(M):
        b.append(b[i] + B[i])

    # a = [0, 60, 140, 240]
    # b = [0, 90, 110, 5, 5]

    ans, j = 0, M
    for i in range(N+1):
        if a[i] > K: break
        while b[j] > K - a[i]: j -= 1
        ans = max(ans, i + j)

    # ai =   0, bj = 210 -> (i, j) = (0, 4)
    # ai =  60, bj = 210 -> (i, j) = (1, 4)
    # ai = 140, bj = 210 -> (i, j) = (2, 4) 
    # ai = 240, bj =  90 -> (i, j) = (1, 3) 

    print(ans)  # ans = 6


if __name__ == '__main__':
    main()


Measured memory_bytes: 48448
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;

int main(){
    int N;
    cin >> N;
    LL a[3*N];
    for(int i=0;i<3*N;i++){
        cin >> a[i];
    }
    sort(a,a+3*N);
    LL ans=0;
    for(int i=3*N-2;i>=N;i-=2){
        ans+=a[i];
    }
    cout << ans << endl;
    return 0;
}

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

namespace keyence2020_b
{
  class Program
  {
    static void Main(string[] args)
    {
      var N = CIn.ReadInt();
      var robots = new Robot[N];

      for (int i = 0; i < N; i++)
      {
        var x = CIn.ReadInt();
        var l = CIn.ReadInt();

        robots[i] = new Robot(x - l, x + l);
      }

      Array.Sort(robots, (a, b) => a.End - b.End);

      var ans = new List<int>() { 0 };

      for (int i = 1; i < N; i++)
      {
        if (robots[i].Start >= robots[ans[ans.Count - 1]].End) ans.Add(i);
      }

      Console.WriteLine(ans.Count);
    }
  }

  class Robot
  {
    public int Start { get; }
    public int End { get; }

    public Robot(int s, int e)
    {
      Start = s;
      End = e;
    }
  }

  static class CIn
  {
    private static readonly Queue<string> fieldBuffer = new Queue<string>();

    public static string Read()
    {
      if (fieldBuffer.Count == 0)
      {
        foreach (var field in Console.ReadLine().Split())
        {
          fieldBuffer.Enqueue(field);
        }
      }
      return fieldBuffer.Dequeue();
    }

    public static int ReadInt() => int.Parse(Read());
    public static long ReadLong() => long.Parse(Read());
    public static double ReadDouble() => double.Parse(Read());

    public static string[] ReadStringArray(long n)
    {
      var array = new string[n];
      for (var i = 0L; i < n; i++)
      {
        array[i] = Read();
      }
      return array;
    }

    public static int[] ReadIntArray(long n)
    {
      var array = new int[n];
      for (var i = 0L; i < n; i++)
      {
        array[i] = ReadInt();
      }
      return array;
    }

    public static long[] ReadLongArray(long n)
    {
      var array = new long[n];
      for (var i = 0L; i < n; i++)
      {
        array[i] = ReadLong();
      }
      return array;
    }

    public static double[] ReadDoubleArray(long n)
    {
      var array = new double[n];
      for (var i = 0L; i < n; i++)
      {
        array[i] = ReadDouble();
      }
      return array;
    }

    public static char[,] ReadCharMatrix(long h, long w)
    {
      var array = new char[h, w];
      for (var i = 0L; i < h; i++)
      {
        var l = Console.ReadLine().ToCharArray();
        for (var j = 0L; j < w; j++)
        {
          array[i, j] = l[j];
        }
      }
      return array;
    }
  }
}


Measured memory_bytes: 19016
#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 N;
	cin >> N;
	ll ans = 0;
	for (int a = 1; a < N; a++) {
		int k = N/a;
		if (N%a == 0) k--;
		ans += k;
	}
	cout << ans << endl;

	return 0;
}



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

#define int long long
#define flash ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define all(x) begin(x),end(x)

int mod = 1e9+7;
int inf = 4e18;
const int N = 5e5+5;
		
signed main()
{
    flash
    int tt = 1;
    //cin>>tt;
    while(tt--)
    {
		int n,k;
		cin>>n>>k;
		int arr[n];
		for(int i=0;i<n;++i)
		{
			cin>>arr[i];
		}
		int low=1,high = 1e9,mid,ans = -1;
		auto help = [&](int mid)
		{
			int cuts = 0;
			for(int i=0;i<n;++i)
			{
				cuts+= (arr[i]+mid-1)/mid -1;
			}
			return cuts<=k;
		};
		while(low<=high)
		{
			mid = low+(high-low)/2;
			if(help(mid))
			{
				ans = mid;
				high = mid-1;
			}
			else
			{
				low = mid+1;
			}
		}
		cout<<ans<<"\n";		
    }
    return 0;
}


Measured memory_bytes: 5088
import java.util.*;
public class Main {
	public static void main(String[] args){
	  Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int m = sc.nextInt();
      int[] a = new int[n];
      long sum = 0;
      long count = 0;
      for(int i=0;i<n;i++){
        a[i] = sc.nextInt();
        sum += a[i];
      }
      for(int i=0;i<n;i++){
        if( a[i] * 4 * m >= sum ){
          count++;
        }
      }
      if( m > count ){
        System.out.println("No");
      }else{
        System.out.println("Yes");
      } 
	}
}

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

using namespace std;

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

template<class T>void byebye(T _rpl) {
	cout<<_rpl<<endl;
	exit(0);
}
int nextint() {
	int x;
	scanf("%d",&x);
	return x;
}
ll nextll() {
	ll x;
	scanf("%lld",&x);
	return x;
}

int read() {
	int f=1,ret=0;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		ret=ret*10+(c-'0');
		c=getchar();
	}
	return ret*f;
}

int p[505][505];
int col[505];
int n,cnt;
void construct(int l,int r,int x) {
	if(l>=r||l+1==r)return;
	int mid=l+r>>1;
	for(int i=l;i<mid;++i){
		for(int j=mid;j<r;++j)	p[i][j]=x;
	}
	construct(l,mid,x+1);
	construct(mid,r,x+1);
}

int main() {
	n=read();
	construct(0,n,1);
	for(int i=0;i<n;++i){
		for(int j=i+1;j<n;++j){
			printf("%d ",p[i][j]);
		}
		puts("");
	}
	return 0;
}


Measured memory_bytes: 1536
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

using ll = long long;
using ld = long double;
const int INF = 1e15;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

struct Node
{
  vector<int> to;
  vector<int> cost;
};
Node Graph[100010];
void AddEdge(int from, int to, int cost, Node *graph)
{
  graph[from].to.push_back(to);
  graph[from].cost.push_back(cost);
  graph[to].to.push_back(from);
  graph[to].cost.push_back(cost);
}

vector<ll> dist;

void bfs(int x)
{
  queue<int> q;
  q.push(x);
  while (!q.empty())
  {
    int p = q.front();
    q.pop();
    for (int i = 0; i < Graph[p].to.size(); ++i)
    {
      int y = Graph[p].to[i];
      if (dist[y] == INF)
      {
        dist[y] = Graph[p].cost[i] + dist[p];
        q.push(y);
      }
    }
  }
}

int main()
{
  long long N;
  scanf("%lld", &N);
  for (int i = 0; i < N - 1; i++)
  {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    AddEdge(a, b, c, Graph);
  }
  long long Q;
  scanf("%lld", &Q);
  long long K;
  scanf("%lld", &K);
  K--;
  dist.assign(N + 1, INF);
  dist[K] = 0;
  bfs(K);
  for (int i = 0; i < Q; i++)
  {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    cout << dist[x] + dist[y] << endl;
  }

  return 0;
}


Measured memory_bytes: 13908
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()

def main():
    a = deque(input())
    b = deque(input())
    c = deque(input())
    d = {'a': a, 'b': b, 'c': c}
    turn = 'a'
    while d[turn]:
        turn = d[turn].popleft()
    print(str.upper(turn))



if __name__ == "__main__":
    main()


Measured memory_bytes: 64968
#include <stdio.h>
#include<math.h>
#include <algorithm>
using namespace std;


int main(){

	int year,month,day;

	while(scanf("%d %d %d",&year,&month,&day)!=EOF){
		if((year <= 1867) || (year == 1868 && month <= 8) || (year == 1868 && month == 9 && day <= 7)){
			printf("pre-meiji\n");
		}else if(year <= 1911 || (year == 1912 && month <= 6) || (year == 1912 && month == 7 && day <= 29)){
			printf("meiji %d %d %d\n",year-1868+1,month,day);
		}else if(year <= 1925 || (year == 1926 && month <= 11) || (year == 1926 && month == 12 && day <= 24)){
			printf("taisho %d %d %d\n",year-1912+1,month,day);
		}else if(year <= 1988 || (year == 1989 && month == 1 && day <= 7)){
			printf("showa %d %d %d\n",year-1926+1,month,day);
		}else{
			printf("heisei %d %d %d\n",year-1989+1,month,day);
		}
	}

    return 0;
}

Measured memory_bytes: 2672
/**
 * @brief  : c++ code for AtCoder
 * @author : rk222
 * @created: 2019.06.16 20:59:50
 */

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<int, P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i, x) for (int i = 0; i < x; i++)
#define rep1(i, x) for (int i = 1; i <= x; i++)
#define rrep(i, x) for (int i = x - 1; i >= 0; i--)
#define rrep1(i, x) for (int i = x; i > 0; i--)
#define sor(v) sort(v.begin(), v.end())
#define rev(s) reverse(s.begin(), s.end())
#define lb(vec, a) lower_bound(vec.begin(), vec.end(), a)
#define ub(vec, a) upper_bound(vec.begin(), vec.end(), a)
#define uniq(vec) vec.erase(unique(vec.begin(), vec.end()), vec.end())
#define mp1(a, b, c) P1(a, P(b, c))

#define disp(x) cout << #x << ": " << x << endl
#define disp_vec(v)                                                                           \
    cout << #v << ":";                                                                        \
    rep(i, v.size()) cout << " " << v[i];                                                     \
    cout << endl

const int INF = 100000000;
const int M = 100000000;
const int dir_4[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const int dir_8[8][2] = {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};

/* ------------------------------------- */

int main() {
    int x, a;
    scanf("%d%d", &x, &a);
    if (x < a) {
        printf("%d\n", 0);
    } else {
        printf("%d\n", 10);
    }

    /* --------------------------------- */
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 5
0 1 1
0 2 2
0 3 3
1 1 2
1 2 2

output:
3
2
"""

import sys


class BinaryIndexedTree(object):
    __slots__ = ('length', 'dat')

    def __init__(self, n):
        """
        Init a BIT with update and find for range sum queries.
        """
        self.length = int(n)
        self.dat = [0] * (self.length + 1)

    # sum(A[1] ... A[i])
    def __init_sum(self, i):
        _sum = 0
        while i > 0:
            _sum += self.dat[i]
            i -= i & (-i)
        return _sum

    def get_sum(self, s, t):
        return self.__init_sum(t) - self.__init_sum(s - 1)

    # A[i] += x
    def get_add(self, i, x):
        while i <= self.length:
            self.dat[i] += x
            i += i & (-i)
        return self.dat


def action(cmd_list):
    for query in cmd_list:
        cmd, ele_1, ele_2 = map(int, query)
        if cmd == 0:
            case.get_add(ele_1, ele_2)
        elif cmd == 1:
            res = case.get_sum(ele_1, ele_2)
            print(res)

    return case


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n_num, q_num = map(int, _input[0].split())
    q_list = map(lambda x: x.split(), _input[1:])

    case = BinaryIndexedTree(n_num)
    ans = action(q_list)

Measured memory_bytes: 18068
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int n,m;
priority_queue<P> q;

int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		q.push({-x,1});
	}
	for(int i=0;i<m;i++){
		int t,x,cnt=0;
		cin>>t>>x;
		while(-q.top().first<=x){
			P p=q.top();q.pop();
			cnt+=p.second;
			if(cnt>=t){
				if(cnt>t) q.push({p.first,cnt-t});
				cnt=t;
				break;
			}
		}
		q.push({-x,cnt});
	}
	ll res=0;
	while(!q.empty()){
		P p=q.top();q.pop();
		res-=(ll)p.first*p.second;
	}
	cout<<res<<endl;
}


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

int main()
{
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n + 1);
    rep(i, n) {
        cin >> a[i + 1];
    }
    ll fast = 1;
    ll slow = 1;
    ll p;
    while (1) {
        fast = a[a[fast]];
        slow = a[slow];
        if (fast == slow) {
            slow = 1;
            while (fast != slow) {
                fast = a[fast];
                slow = a[slow];
            }
            p = fast;
            break;
        }
    }

    ll D = 0;
    ll curr = 1;
    while (curr != p) {
        curr = a[curr];
        D++;
    }
    ll L = 1;
    while (1) {
        curr = a[curr];
        if (curr == p) {
            break;
        }
        L++;
    }
    ll K;
    K = k > D ? (k - D) % L : k;
    curr = k > D ? p : 1;
    rep(i, K) {
        curr = a[curr];
    }
    cout << curr << endl;

    return 0;
}


Measured memory_bytes: 4844
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vs = vector<string>;
using vll = vector<long long>;
using vvi = vector<vector<int>>;
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 (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll x;
    cin >> x;
    ll ans = 0;
    ans += (x/11)*2;
    x -= (x/11)*11;
    ans += x/6;
    x -= (x/6)*6;
    if (x) ans++;
    cout << ans << endl; 
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
#include<fstream>
#include<set>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define out(str) cout << str << endl
#define ALL(a) (a).begin(),(a).end()
#define INF (1<<29)

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; }

ll suma,N,a,b;

int main(){
    cin>>N;
    pair<ll,ll> v[N];
    rep(i,N){
        cin>>a>>b;
        v[i]=make_pair(b,a);

    }
    sort(v,v+N);
    rep(i,N){
        // printf("%lld : %lld\n",v[i].first,v[i].second);
        suma+=v[i].second;
        if(suma>v[i].first){
            out("No");
            return 0;
        }
    }
    out("Yes");
    

}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define int long long
using namespace std;
int n,m,dp[101][21],a[101];
main(){
  cin>>n;
  r(i,n)cin>>a[i];
  dp[0][a[0]]++;
  r(i,n-2)r(j,21)if(dp[i][j]){
    int a1=j+a[i+1],a2=j-a[i+1];
    if(a1>=0&&a1<21)dp[i+1][a1]+=dp[i][j];
    if(a2>=0&&a2<21)dp[i+1][a2]+=dp[i][j];
  }
  cout<<dp[n-2][a[n-1]]<<endl;
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
//const ull mod = 1e9 + 7;
const ll mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

// debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
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; }

// conversion number to bit
string num2bit(ll num, ll len){
  string bit = "";
  REP(i, len){
    bit += char('0'+(num>>i & 1));
  }
  return bit;
}

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

    ll N;
    cin >> N;
    vector<ll> H(N);
    REP(i, N) cin >> H[i];

    ll now = 0;
    REP(i, N){
    	if(H[i]-now>=1){
    		H[i]--;
    	}else if(H[i]<now){
    		cout << "No" << endl;
    		return 0;
    	}
    	now = H[i];
    }
    cout << "Yes" << endl;
    return 0;
}

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

using ll = int64_t;
#define int ll

#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, b) FOR(i, 0, b)
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(x) x.begin(), x.end()

using pi = pair<int, int>;
using vi = vector<int>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  REP(i, (int)v.size()) {
    if (i)
      os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

ll read() {
  ll i;
  scanf("%" SCNd64, &i);
  return i;
}

void printSpace() { printf(" "); }

void printEoln() { printf("\n"); }

void print(ll x, int suc = 1) {
  printf("%" PRId64, x);
  if (suc == 1)
    printEoln();
  if (suc == 2)
    printSpace();
}

string readString() {
  static char buf[3341000];
  scanf("%s", buf);
  return string(buf);
}

char *readCharArray() {
  static char buf[3341000];
  static int bufUsed = 0;
  char *ret = buf + bufUsed;
  scanf("%s", ret);
  bufUsed += strlen(ret) + 1;
  return ret;
}

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

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

template <class T> T Sq(const T &t) { return t * t; }

const int mod = 1e9 + 7;

signed main() {
  int a, b;
  std::cin >> a >> b;
  int diff = abs(a - b);
  if (diff & 1) {
    std::cout << "IMPOSSIBLE" << std::endl;
  } else {
    print(max(a, b) - diff / 2);
  }
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#include<map>
#include<vector>
#define llong long long
using namespace std;

inline int read()
{
	int x=0; bool f=1; char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
	for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
	if(f) return x;
	return -x;
}

const int N = 4e5;
int a[N+3];
int nxt[N+3];
int lst[N+3];
vector<int> ans;
int rd[N+3];
int num[N+3];
int mp[N+3],mpp[N+3];
int n; llong m;

void simulate(int pos)
{
//	printf("simulate %d\n",pos);
	for(; pos<=n; pos++)
	{
		if(num[a[pos]]==0)
		{
			num[a[pos]]++;
			ans.push_back(a[pos]);
		}
		else
		{
			while(num[a[pos]]>0)
			{
				int tmp = ans[ans.size()-1];
				num[tmp]--;
				ans.pop_back();
			}
		}
	}
	for(int i=0; i<ans.size(); i++) printf("%d ",ans[i]);
}

int main()
{
	scanf("%d%lld",&n,&m);
	for(int i=1; i<=n; i++) scanf("%d",&a[i]);
	for(int i=1; i<=n; i++)
	{
		if(lst[a[i]]) {nxt[lst[a[i]]] = i;}
		lst[a[i]] = i;
	}
	for(int i=1; i<=n; i++)
	{
		if(!nxt[lst[a[i]]]) {nxt[lst[a[i]]] = i;}
	}
//	printf("nxt: "); for(int i=1; i<=n; i++) printf("%d ",nxt[i]); puts("");
	int round = 1,pos = 1;
	for(int i=1; ; i++)
	{
//		printf("pos=%d round=%d\n",pos,round);
		if(i>1 && pos==1)
		{
//			printf("f");
			m = m%round; if(m==0) m = round;
			break;
		}
		mp[pos] = round;
		if(nxt[pos]<=pos) {round++;}
		pos = nxt[pos]+1; pos = pos==n+1 ? 1 : pos;
	}
//	printf("cyclen=round=%d\n",round);
//	printf("mp: "); for(int i=1; i<=n; i++) printf("%d ",mp[i]); puts("");
//	printf("m=%lld\n",m);
	for(int i=n; i>=1; i--)
	{
		if(mp[i]==m)
		{
			simulate(i);
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 9076
#include <bits/stdc++.h>
using namespace std;
int N , K;
int num=1;

int main(){
  cin >> N >> K;
  for(int i=0;i<N;i++){
    if(num * 2 < num + K){
      num *= 2;
    }else{
      num += K;
    }
  }
  cout << num << endl;
}

Measured memory_bytes: 3576
import sys
from collections import Counter
import math
input = sys.stdin.readline


def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table


n, p = map(int, input().split())
prime_list = list(Counter(prime_decomposition(p)).items())
ans = 1
for i in range(len(prime_list)):
    cnt = math.floor(prime_list[i][1] / n)
    if cnt >= 1:
        ans *= prime_list[i][0] ** cnt
print(ans)


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

using namespace std;

int main(void) {
	int n, v[20], c[20], sum = 0;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> v[i];
	}
	for(int i = 0; i < n; i++){
		cin >> c[i];
	}
	for(int i = 0; i < n; i++){
		if(v[i]-c[i]>0)
			sum += (v[i]-c[i]);
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256