akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;
int main(void){
    int x, y, z, w, u;
    w = 0,u = 0; 
    cin >> x >> y >> z;
    while(true){
        u += 1;
        w += x;
        if(u%7 == 0){
           w += y;
        }
        if (w >= z){
           break;
        }
    }
    cout << u <<endl;
}


Measured memory_bytes: 3104
import Control.Applicative

findMinimumIndex :: [Int] -> Int
findMinimumIndex (x : xs) = (\(minj, _, _) -> minj) $ foldl f (0, 1, x) xs
  where f (minj, i, v) x = if x < v then (i, i + 1, x) else (minj, i + 1, v)

swapMinimum :: ([Int], Int) -> Int -> ([Int], Int)
swapMinimum (xs, c) i = if i > 0 then (b : as ++ a : bs, c + 1) else (xs, c)
  where (a : as, b : bs) = splitAt i xs

selectionSort :: [Int] -> ([Int], Int)
selectionSort xs = foldl f (xs, 0) [0 .. length xs - 2]
  where
    f (xs, c) i = (as ++ ys, c')
      where
        (as, bs) = splitAt i xs
        (ys, c')  = swapMinimum (bs, c) $ findMinimumIndex bs

main :: IO ()
main = do
  _  <- getLine
  xs <- map read . words <$> getLine
  let (ys, c) = selectionSort xs
  putStrLn $ unwords $ map show ys
  print c



Measured memory_bytes: 4112
import java.util.*;
import java.util.ArrayDeque;
import java.util.Queue;
import java.math.RoundingMode;
import java.math.BigDecimal;
 
 
 
public class Main{
	 public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		long x = sc.nextLong();
		long count = 0;
		long money = 100;
		while(money<x) {
			money=money+money/100;
			count++;
		}
		System.out.println(count);
	 }
}

Measured memory_bytes: 35616
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    const int dx[4] = {1,-1,0,0};
    const int dy[4] = {0,0,1,-1};
    const int INF = INT32_MAX>>2;
    vector<bool> k (n*n,true);
    vector<int> d(n*n,INF);
    rep(i,n*n) {
        int x = i%n;
        int y = i/n;
        chmin(d[i], x);
        chmin(d[i], y);
        chmin(d[i], n-x-1);
        chmin(d[i], n-y-1);
    }
    int ans = 0;
    rep(i,n*n) {
        int p;
        cin >> p;
        p--;
        ans+=d[p];
        k[p] = false;
        queue<int> q;
        q.emplace(p);
        while(!q.empty()) {
            int nowp = q.front();
            q.pop();
            int x = nowp%n;
            int y = nowp/n;
            rep(j,4) {
                int nx = x + dx[j];
                int ny = y + dy[j];
                int np = ny*n + nx;
                if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                if(d[np] > d[nowp] + k[nowp]) {
                    d[np] = d[nowp] + k[nowp];
                    q.emplace(np);
                }
            }
        }
    }
    cout << ans << endl;
}

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

int main () {
	int N;
	double sum = 0.0;
	cin >> N;
	for (int i=0; i<N; i++) {
		double tmp;
		cin >> tmp;
		sum += 1.0/tmp;
	}
	printf ("%lf\n", 1.0/sum);
	return 0;
}

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

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>

using namespace std;

int n,a[105],diff;
int i;

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

  sort(a,a+n,greater<int>());

  for (i=0; i<n; i++){
    if (i%2==0 | i == 0 ) {
      //      cout << "Alice\n";
      //cout << i << a[i] << endl;
      diff += a[i]; }
    else {
      //cout << "Bob\n";
      //cout << i << a[i] << endl;
      diff -= a[i];}
  }

  cout << diff;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
const ll INF = 1001001001;
const ll mod = 1000000007;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}
//printf("%.10f\n", N);
/*
ll memo[100000];
ll fibo(ll n){
    if(memo[n] != 0)return memo[n];
    if(n <= 1)return n;
    else return memo[n] = fibo(n - 1)+ fibo(n - 2);
}*/

int main(){
    ll N;
    cin >> N;
    ll ans = 1;
    ll dame = 1;
    ll n;
    rep(i,N){
        cin >> n;
        if(n % 2 == 0)dame *= 2;
        ans *= 3;
    }
    cout << ans - dame << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,k;
    cin >> n >> k;
    int p_1;
    for(int i = 0;i < n;i++)
    {
        int a;
        cin >> a;
    }
    cout << ceil((n - 1) / double(k - 1));

    return 0;
}

Measured memory_bytes: 256
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def lcm(a, b):
    return (a * b) // gcd(a, b)

n, m = map(int, input().split())
s = input()
t = input()
L = lcm(n, m)
l = lcm(L // n, L // m)
for i in range(0, L, l):
    if s[i // (L // n)] != t[i // (L // m)]:
        print(-1)
        exit()
print(L)

Measured memory_bytes: 3316
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
	int a,b,d,r;
	cin>>a>>b;
	double f;
	d=a/b;
	r=a%b;
	f=(double)a/(double)b;
	cout<<d<<" "<<r<<" ";
	printf("%.5lf\n",f);
return 0;
}

Measured memory_bytes: 3228
#include<iostream>
#include<cstdio>
#include <stdio.h>
#include<algorithm>
#include<cstring>
#include <string>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
#include<vector>
#include<bits/stdc++.h>
#include <set>
#define ll   long long
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#define inf 0x3f3f3f
#define pi 3.1415926535898
using namespace std;
const int N=2e5+10;
const int mod=1e9+7;
char s[4];
int main()
{
    cin>>s;
    int sum=0;
    for(int i=0;i<3;i++)
    {
        int x=0;
        if(s[i]=='R')
        {
            x++;
            while(s[i+1]=='R')
            {
                x++;
                i++;
            }
        }
        sum=max(sum,x);
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 3628
x,y=map(int,input().split())
if x*y>0:
    if x<y:
        print(abs(x-y))
    elif x>y:
        print(abs(x-y)+2)
elif x*y<0:
    print(abs(abs(y)-abs(x))+1)
else:
    if x<0 and y==0:
        print(abs(x))
    elif x>0 and y==0:
        print(x+1)
    elif x==0 and y<0:
        print(abs(y)+1)
    else:
        print(y)
        

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



int main()
{   
    int a,b,c;
    cin >> a >> b >> c;
    int ans = 0;
    for (int i = a; i < b+1; i++)
    {
        if (c%i == 0)
        {
            ans++;
        }
        
    }
    cout << ans << endl;
    return 0;
    
    
    
    


}



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

std::string solve(int a, int b, int c) {
  for(int i = 1; i <= b; ++i) {
    const auto ai { a * i };
    if(ai % b == c) {
      return "YES";
    }
  }
  return "NO";
}

int main() {
  int a, b, c;
  std::cin >> a >> b >> c;
  std::cout << solve(a, b, c) << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#define MN 101000

typedef long long ll;

int n, rt;
int d[MN], v[MN];
ll c[MN];
bool ok = 1; 

int h[MN], nxt[2 * MN], to[2 * MN], K = 0;

void ins(int u, int v) {nxt[++K] = h[u]; h[u] = K; to[K] = v;}

void dfs(int x, int fa)
{
	c[x] = v[x];
	for(int i = h[x]; i; i = nxt[i])
	{
		if(to[i] == fa) continue;
		dfs(to[i], x);
		c[x] -= c[to[i]];
	}
	if(c[x] < 0 || (x == rt && c[x] != 0)) ok = 0; 
	if(d[x] > 1)
	{
		ll sum = 0, Max = 0;
		for(int i = h[x]; i; i = nxt[i])
			if(to[i] != fa) sum += c[to[i]], Max = std::max(Max, c[to[i]]);
		if(((sum - c[x]) & 1) || sum - c[x] < 0) ok = 0;
		if((sum - c[x]) / 2 < Max - c[x]) ok = 0; 
	}
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &v[i]);
	for(int i = 1; i < n; i++)
	{
		int a, b; scanf("%d%d", &a, &b);
		ins(a, b); ins(b, a); 
		d[a]++; d[b]++; 
	}
	if(n == 2)
	{
		if(v[1] == v[2]) puts("YES");
		else puts("NO");
		return 0;
	}
	for(int i = 1; i <= n; i++)
		if(d[i] > 1) rt = i, v[i] *= 2;
	dfs(rt, 0);
	if(!ok) puts("NO");
	else puts("YES");
}

Measured memory_bytes: 14160
#include<stdio.h>
#include<string.h>
#define LEN 100005

typedef struct pp {
  char name[100];
  int t;
} P;

P Q[LEN];
int head, tail, n;

void enqueue(P x) {
  Q[tail] = x;
  tail = (tail + 1) % LEN;
}

P dequeue() {
  P x = Q[head];
  head = (head + 1) % LEN;
  return x;
}

int min(int a, int b) { return a < b ? a : b; }

int main() {
  int elaps = 0, c;
  int i, q;
  P u;
  scanf("%d %d", &n, &q);

  for ( i = 1; i <= n; i++ ) {
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }
  head = 1; tail = n + 1;

  while(head != tail) {
    u = dequeue();
    c = min(q, u.t);
    u.t -= c;
    elaps += c;
    if (u.t > 0) enqueue(u);
    else {
      printf("%s %d\n", u.name, elaps);
    }
  }

  return 0;
}



Measured memory_bytes: 12716
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main()
{
  int n, m;
  cin >> n >> m;
  vector<int> a(n), b(n);

  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    if (x == 1) a[y] = 1;
    if (y == n) b[x] = 1;
  }
  int v = inner_product(begin(a), end(a), begin(b), 0);
  cout << (v > 0 ? "POSSIBLE" : "IMPOSSIBLE") << endl;
}


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

using namespace std;

#define int long long
#define endl '\n'
#define MOD 1000000007
#define maxn 100010

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<int> v(n), dp(n + 1);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
        if (i - k + 1 >= 0)
            dp[i] = 1 + dp[i - k + 1];
    }
    int mx = dp[n - 1];
    for (int i = n - 2; i >= 0; i--)
        if (mx == dp[i]) {
            mx++;
            break;
        }
    cout << mx << endl;
}

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

using namespace std;

void solve() {
  int64_t A, B, K;
  cin >> A >> B >> K;
  auto num1 = min(A, K);
  A -= num1;
  K -= num1;
  auto num2 = min(B, K);
  B -= num2;
  cout << A << " " << B << endl;
}

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


Measured memory_bytes: 256
#include <iostream>
#include <cmath>

using namespace std;

typedef long long int ll;
#define REP(i, I, N) for (int i = I; i < N; ++i)
#define rep(i, N) REP(i, 0, N)


int main() {
    int N, K;
    cin >> N >> K;
    double point, ans = 0.0;

    rep(i, N) {
        point = round(i + 1 * 1.0);
        int count = 0;
        while (1 <= point && point < K) {
            point *= 2.0;
            count++;
        }

        ans += (1.0 / N) * pow((1.0 / 2.0),  count);
    }


    printf("%.12f\n", ans);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>
#include <vector>
 
using namespace std;
 
int a[1111111],b[1111111];
int c[1111],sz;
 
int main() {
  int n,q,p;
  char cmd[55];
  cin >> n >> q;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
    b[i] = a[i];	
  }
  sort(b,b+n);
  for(int L = 0; L < q; L++) {
    scanf("%s%d",cmd,&p);
    if( *cmd == 'A' ) {
      --p;
      c[sz++] = a[p];
    }
    if( *cmd == 'C' ) {
      if( sz == 0 ) {
        if( p == n ) {
          printf("%d\n",0);
        } else {
          puts("NA");
        }
        continue;
      }
      int l,r,m,res;
      l = 0; r = 1000000000; res = r+1;
      while( l <= r ) {
        vector<pair<int,int> > rng;
        m = (l+r)/2;
        for(int i = 0; i < sz; i++) {
          int u = lower_bound(b,b+n,max(c[i]-m,0))-b;
          int v = upper_bound(b,b+n,c[i])-b;
          rng.push_back(make_pair(u,v));
        }
        sort(rng.begin(),rng.end());
        int nl,nr,lv=0;
        nl = rng[0].first;
        lv += nl;
        nr = rng[0].second;
        for(int i = 1; i < int(rng.size()); i++) {
          if( rng[i].first <= nr ) {
            nr = rng[i].second;
          } else {
            lv += rng[i].first-nr;
            nl = rng[i].first;
            nr = rng[i].second;
          }
        }
        lv += n-nr;
        if( lv <= p ) {
          r = m-1;
          res = min(res,m);
        } else {
          l = m+1;
        }
      }
      if( res > 1000000000 ) {
        puts("NA");
      } else {
        printf("%d\n",res);
      }
    }
    if( *cmd == 'R' ) {
      p--;
      for(int i = 0; i < sz; i++) {
        if( c[i] == a[p] ) {
          swap(c[i],c[sz-1]);
          --sz;
          break;
        }
      }
    }
  }
  return 0;
}

Measured memory_bytes: 9504
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

const int INF = (1 << 30) - 1;
const ll INF64 = ((ll)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

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

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

	string s;
	cin >> s;

	int n = s.size();
	ll ans = 0;
	for (int i = 0; i < 1 << (n - 1); i++) {
		ll score = 0;
		ll v = s[0] - '0';
		for (int j = 0; j < n - 1; j++) {
			if ((1 & i >> j) == 1) {
				score += v;
				v = s[j + 1] - '0';
				continue;
			}
			v = 10 * v + (s[j + 1] - '0');
		}

		score += v;
		ans += score;
	}

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


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

int main()
{
    int n;
    cin>>n;
    int a[n+2],b[n+1];
    for(int i=0; i<n+1; i++)cin>>a[i];
    for(int i=0; i<n; i++)cin>>b[i];
    long long int res=0;
    for(int i=0; i<n; i++)
    {
        if(b[i] >= a[i])
        {
            b[i]= b[i]-a[i];
            res+=a[i];
            //a[i]=0;
        }
        else
        {
            res+=a[i]-(a[i]-b[i]);
            b[i]=0;
        }
        if(b[i] != 0)
        {
            if(b[i] >= a[i+1])
            {
                res+=a[i+1];
                a[i+1]=0;
            }
            else
            {
                res+=b[i];
                a[i+1]=a[i+1]-b[i];
            }
        }

    }
    cout<<res<<endl;



    return 0;
}


Measured memory_bytes: 1024
import scala.io.StdIn._

object Helpers {
  def readIntLine = readLine.split(" ").map(_.toInt)
  def readInts(n: Int) = Array.fill(n)(readInt)

  def splitDigits(i: Int): Seq[Int] = i.toString.map(_.asDigit)

  def log[A](x: A): A = {println(x); x}

  implicit class IntImplicits(val i: Int) {
    def isEven = i % 2 == 0
    def isOdd = !isEven
  }
}

object Main extends App {
  import Helpers._

  val s = readLine

  println(if (s(1) == 'B') "ARC" else "ABC")
}



Measured memory_bytes: 54472
import collections
import itertools
import sys

def getint(): return int(input())
def getints(): return list(map(int, input().split()))

deq = collections.deque()
n=getint()
vs=getints()

front = True if n % 2 == 0 else False
for d in vs:
    if front:
        deq.append(d)
    else:
        deq.appendleft(d)
    front = not front

res = list(map(lambda s: str(s), deq))

print(" ".join(res))


Measured memory_bytes: 32964
import sys
from heapq import heappush, heappop

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    heap = []
    for a in A:
        heappush(heap, -a)

    for _ in range(K):
        price = heappop(heap)
        heappush(heap,-(- price//2))

    return -sum(heap)


if __name__ == '__main__':
    print(main())


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

//{{{
/********************************************************************/
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef queue<int> qi;
typedef stack<int> si;
typedef deque<int> dqi;

#define reps(i, a, b) for (int i = a; i < b; ++i)
#define rep(i, n) reps(i, 0, n)
#define REPS(i, a, b) reps(i, a, b)
#define REP(i, n) rep(i, n)
#define deps(i, a, b) for (int i = a; i >= b; --i)
#define dep(i, n) deps(i, n, 0)
#define DEPS(i, a, b) deps(i, a, b)
#define DEP(i, n) dep(i, n)

#define pf push_front
#define pb push_back
#define mp make_pair
#define fst first
#define FST fst
#define sec second
#define SEC sec
#define sz(obj) ((int)(obj).size())
#define all(v) (v).begin(), (v).end()
#define ALL(v) all(v)
#define endl '\n'

const int INF = 999999999;
const int MOD = 1e9 + 7;
const int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

//vector<string> split(const string &s, char delim) {
//  vector<string> elems;
//  string item;
//  for (char ch: s) {
//    if (ch == delim) {
//      if (!item.empty()) elems.push_back(item);
//      item.clear();
//    }
//    else item += ch;
//  }
//  if (!item.empty()) elems.push_back(item);
//  return elems;
//}

inline bool inside(int y, int x, int H, int W) { return y >= 0 && x >= 0 && y < H && x < W; }
inline int in() { int x; std::cin >> x; return x; }
template <typename T>
void print(std::vector<T>& v, char c = ' ') {
  REP(i, v.size()) {
    if (i != 0) std::cout << c;
    std::cout << v[i];
  }
  std::cout << '\n';
}
template <typename T> void print(T x) { std::cout << x << '\n'; }

/****************************************************************/
//}}}

signed main()
{
  int W = in(), H = in(), N = in(), ans = 0;
  vector<int> X(N), Y(N);
  rep(i, N) cin >> X[i] >> Y[i];

  rep(i, N - 1) {
    int x = X[i + 1] - X[i];
    int y = Y[i + 1] - Y[i];
    if (x >= 0 && y >= 0) {
      ans += max(x, y);
    }
    else if (x <= 0 && y <= 0) {
      ans += -min(x, y);
    }
    else {
      ans += abs(x) + abs(y);
    }
  }

  print(ans);

  return (0);
}

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

public class Hello
{
    public static void Main()
    {
        hoge();
        System.Console.ReadLine();
    }

    public static void hoge()
    {
        var line = System.Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
        var n = line[0];

        var xs = System.Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();

        List<long> lst = new List<long>();

        var min = long.MaxValue;
        for (long i = 0; i < 100; i++)
        {
            long sum = 0;
            for (long j = 0; j < n; j++)
            {
                sum += (xs[j] - (i + 1)) * (xs[j] - (i + 1));
            }
            min = sum < min ? sum : min;
        }
        System.Console.WriteLine(min);
    }

}


Measured memory_bytes: 13268
def main():
    #from sys import stdin, setrecursionlimit
    #setrecursionlimit(10**9)
    #r = input()
    #n = int(input())
    #a, b = map(int, input().split())
    #s, y = input().split()
    #a = input().split()
    #a = list(map(int, input().split()))
    #a = [list(input().split()) for i in range(n)]
    #a = [int(input()) for i in range(n)]
    #a = [list(map(int, input().split())) for i in range(n)]
    #a = [int(s) - 1 for s in input().split()]
    #l=[int(input()) for _ in range(int(input()))]
    #res = 0
    x,m=map(int,input().split())
    a=sorted(list(map(int,input().split())),reverse=True)
    if a[m-1] >= sum(a)/(m*4):
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()



Measured memory_bytes: 38256
#include<iostream>
using namespace std;
int main()
{
	int n;cin>>n;
	int arr[n];
	long long xorx=0;
	for(int i=0;i<n;++i)
	{
		cin>>arr[i];
		xorx = (xorx^arr[i]);
	}
	for(int i=0;i<n;++i)
	{
		cout<<(arr[i]^xorx)<<" ";
	}
}

Measured memory_bytes: 4260
#include <iostream>
using namespace std;
int main(){
    char b;cin>>b;
    if(b == 'A'){cout << 'T' << endl;}
    if(b == 'C'){cout << 'G' << endl;}
    if(b == 'G'){cout << 'C' << endl;}
    if(b == 'T'){cout << 'A' << endl;}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define br cout << endl;
using namespace std;
const int INF = 1e9;
const int MOD = 1e9+7;
using Graph = vector<vector<ll>>;
template<class T> inline bool chmin(T &a, T b) { if(a > b){ a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b) { if(a < b){ a = b; return true;} return false;}

// 0 false, 1 true 
// stringの数字をint型にしてアスキーコードになったら -48する
// 切り上げ　ceil(a)


int main() {
    
    ll h, n;
    cin >> h >> n;

    vector<pair<ll,ll>> vec(n);
    rep(i,n){
        ll a, b;
        cin >> a >> b;
        vec.at(i) = make_pair(a,b);
    }

    vector<ll> dp(h+1, INF);
    dp[0] = 0;

    
    rep(i,n){
        rep(j,h){
            ll tmp = min(j+vec.at(i).first, h);
            dp[tmp] = min(dp[tmp], dp[j] + vec.at(i).second);
        }
    }

    cout << dp[h] << endl;


    

}


Measured memory_bytes: 384
/*
      author  : nishi5451
      created : 15.08.2020 11:42:46
*/

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
typedef long long ll;


int main(){
    int n;
    cin >> n;
    int index=0;
    int t = n;
    while(t){
        t/=10;
        index++;
    }
    int ans = 0;
    int now = 9;
    for(int i=1; i<=index/2; i++){
        ans += now;
        now *= 100;
    }   
    if(index%2!=0){
        int k = now/9;
        ans += (n-k+1);
    }
    cout  << ans << endl;
    return 0;
}

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

const bool DEBUG = false;

int main(int argc, char const *argv[]) {
  int N;
  cin >> N;
  int total = 0;
  vector<int> d(N);
  for (int i = 0; i < N; i++) {
    cin >> d[i];
  }
  for (int i = 0; i < N; i++) {
    for (int j = (i + 1); j < N; j++) {
      if (DEBUG) cout << i << ", " << j << ", " << d[i] * d[j] << endl;
      total += d[i] * d[j];
    }
  }
  cout << total << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 4 , MOD = 1e9 + 7;
int n;
vector<int> adj[N];
int memo[N][2];
int add(int a, int b){
   a += b;
   while(a >= MOD)
      a -= MOD;
   while(a < 0)
      a += MOD;
   return a;
}

int mul(int a , int b){
   return (1ll * a * b) % MOD;
}

int solve(int u , int s , int p){

   int &ret = memo[u][s];
   if(~ret)
      return ret;
   ret = 1;
   for(int c : adj[u]){
      if(c == p)continue;
      int cr = solve(c , 0 , u);
      if(!s)cr = add(cr , solve(c , 1 , u));
      ret = mul(ret , cr);
   }
   return ret;
}
int main() {
#ifndef ONLINE_JUDGE
#endif
   ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
   cin >> n;
   for(int i = 1 ; i < n ; ++i){
      int u , v;
      cin >> u >> v;
      adj[u].push_back(v);
      adj[v].push_back(u);
   }
   memset(memo , -1 , sizeof(memo));
   cout << add(solve(1 , 0 , -1) , solve(1 , 1 , -1)) << "\n";
}

Measured memory_bytes: 18152
import java.io.*;

class Main{
 public static void main(String[] arg) throws IOException{
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  String str = br.readLine();
  String [] div = str.split(" ");
  int s = Integer.parseInt(div[0]);
  int l = Integer.parseInt(div[1]);
  System.out.println(s*l + " "+ 2*(s+l));
 }
}

Measured memory_bytes: 24220
#include <iostream>
#include <bits/stdc++.h>
#include <string.h>
typedef long long int l;
using namespace std;


int main(){
   string str;
   cin>>str;
   for(int i=0;i<str.size();i++){
   if(i%2==1 && str[i]=='R'){
cout<<"No";
return 0 ;
}
   		
		if(i%2==0&&str[i]=='L'){
cout<<"No";
return 0 ;
}
}
cout<<"Yes";
    return 0;
}



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

typedef long long ll;

bool check(int n){
  // n は5けた
  string x = to_string(n);
  if(x[0] == x[4] && x[1] == x[3]){
    return true;
  } else {
    return false;
  }
}

int main(){
  ll ans = 0;
  int a,b;
  cin >> a >> b;
  for(int i = a; i <= b; i++){
    if(check(i)) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
object Main extends App{
  import java.io.{BufferedOutputStream, BufferedReader, InputStreamReader, PrintWriter}
  val in=new BufferedReader(new InputStreamReader(System.in))
  val out = new PrintWriter(new BufferedOutputStream(System.out))
  val n = in.readLine().toInt
  val s=in.readLine().split(" ").map(_.toInt)
  val m = scala.collection.mutable.HashMap[Int,Int]()
  for{i <- ( 0 until(n) )}{
    m(s(i)) = if(m.contains(s(i))) m(s(i)) + 1 else 0
  }
  var ans = "YES"
  m.toSeq.collect{case r if r._2 > 0 => ans = "NO"}
  out.println(ans)
  out.flush()
}

Measured memory_bytes: 77912
# -*- coding: utf-8 -*-
n, p = list(map(int, input().split()))

#素因数分解
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass
ls = prime_factor(p)
#print(ls)

#重複をリストで取得
import collections
lsm = collections.Counter(ls)
lsm = lsm.most_common()
#print(lsm)
#print(len(lsm))

#素因数
key = []
for k in range(len(lsm)):
    if lsm[k][1] >= n:
        #key.append(lsm[k][0])
        #print(int(lsm[k][1]/n))
        key.append(lsm[k][0]**int(lsm[k][1]/n))
    else:
        key.append(1)

#print(key)
v = 1
for j in range(len(key)):
    v = v*key[j]
print(v)

Measured memory_bytes: 3316
A,B,K = map(int,input().split())
ans = []
for i in range(A,K+A):
    if i > B:
        break
    ans.append(i)

for i in range(B-K+1,B+1):
    if i < A:
        continue
    ans.append(i)

ans = set(ans)
ans = list(ans)
ans.sort()
for i in range(len(ans)):
    print(ans[i])

Measured memory_bytes: 3064
cnt = [0]*26
while True:
    try:
        s = input().lower()
    
        for i in range(len(s)):
            m = ord(s[i]) - ord('a')
            if m >= 0 and m <= 25:
                cnt[m] += 1

    except:
        break
                
for i in range(26):
    print('{0} : {1}'.format(chr(i+ord('a')),cnt[i]))


Measured memory_bytes: 5564
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
typedef long long ll;
#define INF 1LL<<40

int N, M, C, S, G;
ll d[20][100][100];
int P[20];
int Q[20][50];
int R[20][50];

ll dd[100][100];

ll getCost(int c, ll dist)
{
	if (P[c] == 1) return dist * R[c][0];
	if (dist <= Q[c][0]) return dist * R[c][0];

	ll ret = 0;

	int i = 0;
	while (Q[c][i] < dist)
	{
		if (i == 0)
			ret += Q[c][0] * R[c][0];
		else
			ret += (Q[c][i] - Q[c][i - 1]) * R[c][i];

		i++;
		if (i == P[c] - 1)
		{
			ret += (dist - Q[c][i-1]) * R[c][i];
			return ret;
		}
	}

	ret += (dist - Q[c][i - 1]) * R[c][i];
	return ret;
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	while (cin >> N >> M >> C >> S >> G)
	{
		if (N == 0) return 0;
		S--; G--;

		rep(i, 0, C) rep(j, 0, N) rep(k, 0, N) d[i][j][k] = INF;
		rep(i, 0, C) rep(j, 0, N) d[i][j][j] = 0;
		rep(i, 0, N) rep(j, 0, N) dd[i][j] = INF;
		rep(i, 0, N) dd[i][i] = 0;
		
		rep(i, 0, M)
		{
			int x, y, c; 
			ll _d;
			cin >> x >> y >> _d >> c;
			x--; y--; c--;

			d[c][x][y] = min(d[c][x][y], _d);
			d[c][y][x] = min(d[c][y][x], _d);
		}

		rep(_i, 0, C) rep(k, 0, N) rep(i, 0, N) rep(j, 0, N)
			d[_i][i][j] = min(d[_i][i][j], d[_i][i][k] + d[_i][k][j]);

		rep(i, 0, C) cin >> P[i];
		rep(i, 0, C)
		{
			rep(j, 0, P[i] - 1) cin >> Q[i][j];
			rep(j, 0, P[i]) cin >> R[i][j];
		}

		rep(i, 0, N) rep(j, 0, N) rep(k, 0, C) if(d[k][i][j] != INF) if(i != j)
		{
			ll cost = getCost(k, d[k][i][j]);

			dd[i][j] = min(dd[i][j], cost);

			//printf("[%d %d %d] -> %lld -> %lld\n", k, i, j, d[k][i][j], cost);
		}

		rep(k, 0, N) rep(i, 0, N) rep(j, 0, N)
			dd[i][j] = min(dd[i][j], dd[i][k] + dd[k][j]);

		if (dd[S][G] == INF)
			cout << -1 << endl;
		else
			cout << dd[S][G] << endl;
	}
}

Measured memory_bytes: 4736
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int a[N];
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,k,s;
    cin>>n>>k>>s;
    if(s>1e6){
        while(n--,k--) cout<<s<<' ';n++;
        while(n--) cout<<1<<' ';
        cout<<endl;
    }
    else{
        while(n--,k--) cout<<s<<' ';n++;
        while(n--) cout<<s*2<<' ';
        cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 1280
N, M = gets.chomp.split.map(&:to_i)
tenboudai_hyoukou = gets.chomp.split.map(&:to_i)
tenboudai = N.times.map do
  []
end

M.times.each do
  a, b = gets.chomp.split.map(&:to_i)
  tenboudai[a - 1].push b
  tenboudai[b - 1].push a
end

count = 0

tenboudai.each_with_index do |ways, index|
  if ways.empty?
    count += 1
    # puts 'empty'
    next
  end
  ways.uniq!
  # p ways
  count += 1 if ways.all? do |point|
    tenboudai_hyoukou[index] > tenboudai_hyoukou[point - 1]
  end
  # p [index, count]
end

puts count


Measured memory_bytes: 33848
n = int(input())

def factorization(n):
    arr = []
    temp = n
    for i in range(2,int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i,cnt])
    if temp != 1:
        arr.append([temp,1])

    if arr == []:
        arr.append([n,1])

    return arr

f = factorization(n)
l = []
for i in range(len(f)):
    for _ in range(f[i][1]):
        l.append(str(f[i][0]))

ans = ' '.join(l)
print(f'{str(n)}: ' + ans)


Measured memory_bytes: 5660
#include<iostream>
#include<cassert>
#include<ctime>
#include<climits>
#include<queue>
#include<fstream>
#include<deque>
#include<iomanip>
#include<list>
#include<stack>
#include<sstream>
#include<string>
#include<cctype>
#include<cstdio>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<map>
#include<set>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS 1e-10
#define F first
#define S second
#define all(n) n.begin(),n.end()
#define pb push_back
#define insert(a,b,c,d) PP(P(a,b),P(c,d))
#define INF (1<<27)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<P,int> PI;
typedef pair<P,P> PP;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};

int main(){
  int h,n;
  while(true){
  cin >> n >> h;
  if(n+h == 0)break;
  long area = n*n*n;

  
  map<PI,bool> coor;
  while(h-- > 0){
    string coordinate;
    int a,b;
    cin >> coordinate >> a >> b;
    int x,y,z;
   
    if(coordinate == "xy"){
      REP(i,1,n+1){
	if(!coor[PI(P(a,b),i)]){
	  coor[PI(P(a,b),i)] = true;
	}
      }
    }
    else if(coordinate == "xz"){
      REP(i,1,n+1){
	if(!coor[PI(P(a,i),b)])coor[PI(P(a,i),b)] = true;
      }
    }
    else if(coordinate == "yz"){
      REP(i,1,n+1){
	if(!coor[PI(P(i,a),b)])coor[PI(P(i,a),b)] = true;
      }
    }
    else assert(false);
    
  }
  cout << n*n*n - coor.size() << endl;
  }
return 0;
}

Measured memory_bytes: 4336
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string s; cin >> s;
  if(s.size()==1){
    cout << 0 << endl;
    return 0;
  }
  int left = 0;
  int right = s.size() - 1;
  int cnt = 0;
  while((right-left)>=1){
    if(s[left]==s[right]){
      left++;
      right--;
    }else if(s[left]=='x'){
      left++;
      cnt++;
    }else if(s[right]=='x'){
      right--;
      cnt++;
    }else{
      cout << -1 << endl;
      return 0;
    }
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define MAX 100001
using namespace std;
int main() {
	int n, ans = 0, m = 0, count = 0;
	cin >> n;
	vector<int> arr(MAX, 0);
	for(int i = 0; i < n; i++) {
		int num;
		cin >> num;
		if(num != 0) arr[num - 1]++;
		arr[num]++;
		if(num != 100000) arr[num + 1]++;
	}

	for(int i = 0; i < MAX; i++) {
		if(ans < arr[i]) {
			ans = arr[i];
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 640
#include "bits/stdc++.h"
#pragma warning(disable:4996)
using namespace std;

int main() {
	int a;
	map<int, int>mp;
	while (cin >> a) {
		mp[a]++;
	}
	int amax = 0;
	vector<int>anss;
	for (auto m : mp) {
		if (m.second > amax) {
			anss.clear();
			amax = m.second;
		}
		if (m.second == amax) {
			anss.push_back(m.first);
			
		}
	}
	sort(anss.begin(), anss.end());
	for (auto ans : anss) {
		cout << ans << endl;
	}
	return 0;
}

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

int main() {

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

    vector< int > b;
    for(int i = 0; i < n; i++) {
        if(i % 2 == 0) b.push_back(a[i]);
        else           b.insert(b.begin(), a[i]);
    }

    if(n % 2) {
        for(auto p = b.rbegin(); p != b.rend(); p++) {
            cout << *p << (p == b.rend() - 1 ? '\n' : ' ');
        }
    } else {
        for(auto p = b.begin(); p != b.end(); p++) {
            cout << *p << (p == b.end() - 1 ? '\n' : ' ');
        }
    }
}


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

int main(){
  int N;
  cin >> N;
  
  //cout << N << endl;
  
  vector<int> V(N);  
  for(int i = 0; i < N; i++){
    cin >> V.at(i);
  }
  //for(int i = 0; i < N; i++){
    //cout << V.at(i)<< endl;
  //}
  
  
  vector<int> C(N);
  for(int i = 0; i < N; i++){
    cin >> C.at(i);
  }
  //for(int i = 0; i < N; i++){
    //cout << C.at(i)<< endl;
  //}
  
  
  int max = 0;
  
  for(int i = 0; i < N; i++){
    if(V.at(i) - C.at(i) > 0){
      max = max + V.at(i) - C.at(i);
    }
  }
  
  cout << max << endl;

  // ここにプログラムを追記
     
  }


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n) for(int i=1;i<=(n);i++)
#define lol long long
#define SUM(n) ((n)+1)*(n)/2　//1〜nまでの総和を求める式
#define mp make_pair
#define fi first
#define se second
#define pu push_back
#define SYOU(x) setprecision(x+1) //小数点桁数を指定する
#define abs(x,y) (max(x,y)-min(x,y))
#define all(v) v.begin(),v.end()
#define UPDight(a,b) (a+b-1)/b //小数点切り上げ 
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD=int(1e9)+7; 
using namespace std;
using pii = pair<int,int>;
typedef vector<int> vit;
//八方向を見るのに使うと便利(楽)
const int dy[] = {0, 1, 0, -1, -1, 1, 1, -1};
const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};

int h, w, dist[25][25];
char mas[25][25];
queue<pair<int, int>> que;

void BFS(){
  int y, x;
  while(!que.empty()){
    tie(y, x) = que.front();
    que.pop();
    rep(i, 4){
      int ny = y + dy[i];
      int nx = x + dx[i];
      if(mas[ny][nx] != '#' && dist[ny][nx] > dist[y][x] + 1 && (ny <= h && 1 <= ny && nx <= w && 1 <= nx)){
	dist[ny][nx] = dist[y][x] + 1;
	que.emplace(ny, nx);
      }
    }
  }
  return;
}

signed main(void){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cin >> h >> w;
  reps(i, h){
    reps(j, w){
      cin >> mas[i][j];
    }
  }
  int ans = 0;
  reps(i, h){
    reps(j, w){

      if(mas[j][i] == '.'){
	memset(dist, INF, sizeof(dist));
	que.emplace(j, i);
	dist[j][i] = 0;
	BFS();
	
	reps(na, h){
	  reps(su, w){
	    //cout << dist[na][su] << " ";
	    if(dist[na][su] != INF) ans = max(ans, dist[na][su]);
	  }
	  //cout << '\n';
	}
      }
      //cout << '\n';
    }
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 3632
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<bitset>
#include<deque>
#include<functional>
#include<iterator>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<utility>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz(x) (ll)((x).size())
#define pb push_back
#define mp make_pair
#define bg begin()
#define ed end()
#define all(x) (x).bg,(x).ed
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep1(i,n) for(ll i=1;i<=(n);i++)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(ll i=(n);i>=1;i--)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
const ll MOD=1000000007;
const ll INF=1000000000000000;
template<class T> inline bool chmin(T& a, T b){if(a>b){a=b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a=b;return true;}return false;}
ll maxx(ll x,ll y,ll z){return max(max(x,y),z);}
ll minn(ll x,ll y,ll z){return min(min(x,y),z);}
ll gcd(ll x,ll y){if(x%y==0) return y;else return gcd(y,x%y);}
ll lcm(ll x,ll y){return x*(y/gcd(x,y));}

vector<ll> pw2(51,1);vector<ll> pw10(19,1);
int main(){
    {rep1(i,50) pw2[i]=2*pw2[i-1];}
    {rep1(i,18) pw10[i]=10*pw10[i-1];}
    
    ll N,K; cin>>N>>K;
    ll ans=0;
    vector<ll> t(N);
    vector<ll> d(N);
    priority_queue<P,vector<P> > sushi;
    priority_queue<P,vector<P>,greater<P> > trash;
    
    rep(i,N){
        cin>>t[i]>>d[i];
        sushi.push(P(d[i],t[i]));
    }
    set<ll> se;
    
    ll point=0;
    rep(i,K){
        point+=sushi.top().a;
        if(se.find(sushi.top().b) != se.ed) trash.push(sushi.top());
        else se.insert(sushi.top().b);
        sushi.pop();
    }
    ans=point+sz(se)*sz(se);
    while(!sushi.empty() && !trash.empty()){
        P tmp=sushi.top();
        if(se.find(tmp.b) != se.ed){
            //何もしない
        }
        else{
            se.insert(tmp.b);
            point-=trash.top().a;
            trash.pop();
            point+=tmp.a;
        }
        sushi.pop();
        chmax(ans,point+sz(se)*sz(se));
    }
    cout<<ans<<endl;
}



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

typedef long long int ll;
typedef unsigned long long int ull;
#define rep(i,n) for(auto i=0;i<(n);i++)
#define rep1(i,n) for(auto i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()

using namespace std;


struct init{ init(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); }; }aaaaaaa;


int main(){
    ll l;
    cin >> l;
    vector<ll> a(l+1, 0);
    rep(i, l) cin >> a[i+1];
    
    vector<vector<ll>> dp(l+1, vector<ll>(5, 0));
    rep(i, l+1){
        if(i == 0) continue;
        ll x = a[i];
        dp[i][0] = dp[i-1][0] + x;
        dp[i][1] = min(dp[i][0], dp[i-1][1] + (x? x%2:2));
        dp[i][2] = min(dp[i][1], dp[i-1][2]+((x+1)%2));
        dp[i][3] = min(dp[i][2], dp[i-1][3]+(x? x%2:2));
        dp[i][4] = min(dp[i][3], dp[i-1][4]+x);
    }

    cout << dp[l][4] << endl;

    // even odd even

    return 0;
}



Measured memory_bytes: 15872
#include <bits/stdc++.h>
#define ll long long
#define mx 200007
#define lchild 2*node
#define mod 998244353
#define rchild lchild+1
#define mid (l+r)/2
using namespace std;

int tree[4*mx], arr[mx];
int dp[mx];
bool vis[mx];

void update( int node, int l, int r, int i, int j, int x )
{
    if( l>j or r<i )
        return;
    if( l>=i and r<=j )
    {
        tree[node]= x;
        return;
    }

    update( lchild, l, mid, i, j, x );
    update( rchild, mid+1, r, i, j, x );

    tree[node]= (tree[lchild]+tree[rchild])%mod;
}

ll query( int node, int l, int r, int i, int j )
{
    if( l>j or r<i )
        return 0;
    if( l>=i and r<=j )
        return tree[node];      

    ll q1= query( lchild, l, mid, i, j );
    ll q2= query( rchild, mid+1, r, i, j );

    return (q1+q2)%mod;
}

int a[mx], b[mx];

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

    int n,k;
    cin>>n>>k;

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

    dp[n]= 1;
    update( 1, 1, n, n, n, 1 );

    for( int i=n-1;i>=1;i-- )
    {
        ll ans= 0;
        for( int j=0;j<k;j++ )
        {   
            if( i+a[j]<=n )
                ans= (ans+query( 1, 1, n, i+a[j], min( n, i+b[j] ) ))%mod;
        }

        update( 1, 1, n, i, i, ans );
        dp[i]= ans;
    }

    cout<< dp[1] <<"\n";
}


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

using namespace std;

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

typedef long long ll; typedef vector<int> VI; typedef pair<ll,int> pii;
const ll mod = 1e9+7;


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

	int n;
	string s;
	cin >>n >> s;
	auto os =s;
	
	for(bool nxt=true; nxt;){
		nxt = false;
		int ps=0;
		while(ps = s.find("()", 0), ps !=-1){
			s[ps]=s[ps+1]='#';
			ps++;
		}
		repr(i,sz(s)-1,0) if(s[i]=='#'){ s.erase(i,1); nxt=true; }
	}
	//cout <<s <<"##\n";
	
	int bf=0, af=0;
	for(auto x: s){
		if(x==')') bf++;
		if(x=='(') af++;
	}
	//printf("ba=%d:%d:%d\n",bf, af, n);
	cout << string(bf, '(') + os + string(af, ')')<<"\n";
	return 0;
}




Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    // Your code here!
    int a,l=0;
    for(int i=1;i<=3;i++){
        scanf("%d",&a);
        l+=a;
    }
    if(l<=21)printf("win\n");
    else printf("bust\n");
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define X 1000000007
#define ff first.first
#define fs first.second
#define sf second.first
#define ss second.second
typedef pair<int,int> P;
typedef pair<P,P> PP;
int main(void)
{
	int n,m,s,g,v,p;
	int pp,kou,min;
	int i,j,k;
	int ri[21][21],leng[21],flg[21];
	
	PP d[100];
	
	scanf("%d %d",&n,&m);
	for(i=0;i<m;i++) scanf("%d,%d,%d,%d",&d[i].ff,&d[i].fs,&d[i].sf,&d[i].ss);
	scanf("%d,%d,%d,%d",&s,&g,&v,&p);
	
	for(i=0;i<=n;i++) fill(ri[i]+1,ri[i]+n+1,X);
	for(i=0;i<m;i++) ri[d[i].ff][d[i].fs]=d[i].sf,
					 ri[d[i].fs][d[i].ff]=d[i].ss;
					 
	for(i=1;i<=n;i++) leng[i]=X,flg[i]=0;
	leng[s]=0;
	
	kou=0;
	for(i=1;i<=n;i++){
		min=X;
		
		for(j=1;j<=n;j++) if(flg[j]==0&&leng[j]<min) pp=j,min=leng[j];
		flg[pp]=1;
		
		for(k=1;k<=n;k++){
			if(leng[pp]+ri[pp][k]<leng[k]) leng[k]=leng[pp]+ri[pp][k];
		}	
	}
	kou+=leng[g];
	
	for(i=1;i<=n;i++) leng[i]=X,flg[i]=0;
	leng[g]=0;
	
	for(i=1;i<=n;i++){
		min=X;
		
		for(j=1;j<=n;j++) if(flg[j]==0&&leng[j]<min) pp=j,min=leng[j];
		flg[pp]=1;
		
		for(k=1;k<=n;k++){
			if(leng[pp]+ri[pp][k]<leng[k]) leng[k]=leng[pp]+ri[pp][k];
		}	
	}
	kou+=leng[s];

	printf("%d\n",v-p-kou);
}	
	


Measured memory_bytes: 3168
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define COUT(x) cout<<(x)<<endl
#define dump(x)  cout << #x << " = " << (x) << endl;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
using M = map<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int, vector<int>, greater<int>>;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main() {
  int n,d,x; cin >> n >> d >> x;
  int a,ans = 0;
  REP(i,n) {
    cin >> a;
    REP(i,d) {
      if (a*i+1 > d) break;
      ans++;
    }
  }
  COUT(ans + x);
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b;
	cin>>a>>b;
	if(a==1 && b==2 || a==2 && b==1) cout<<"3";
	else if(a==1 && b==3 || a==3 && b==1) cout<<"2";
	else if(a==3 && b==2 || a==2 && b==3) cout<<"1";
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main(){
	int n;
	std::cin >> n;

	std::vector<std::string> a(n);
	bool zero = false;
	unsigned int lensum = 0;
	for(int i = 0; i < n; ++i){
		std::cin >> a.at(i);
		if(a.at(i) == "0"){
			zero = true;
		}
		lensum += a.at(i).size() - 1;
	}

	if(zero){
		std::cout << "0" << std::endl;
		return 0;
	}

	if(lensum > 19){
		std::cout << "-1" << std::endl;
		return 0;
	}


	std::string final_result = a.at(0);
	for(int i = 1; i < n; ++i){
		std::string u = a.at(i);
		std::vector<std::string> temps(u.size(), "");
		
		for(unsigned int j = 0; j < u.size(); ++j){
			int p = std::stoi(u.substr(u.size() - 1 - j, 1));
			int kuriagari = 0;
			
			for(unsigned int k = 0; k < final_result.size(); ++k){
				int q = std::stoi(final_result.substr(final_result.size() - 1 - k, 1));
				int r = p * q;
				temps.at(j) += std::to_string((kuriagari + r) % 10);
				kuriagari = (kuriagari + r) / 10;
				if(k == final_result.size() - 1 && kuriagari != 0){
					temps.at(j) += std::to_string(kuriagari);
				}
			}
			std::reverse(temps.at(j).begin(), temps.at(j).end());
			
			for(unsigned int l = 0; l < j; ++l){
				temps.at(j) += "0";
			}
			//std::cout << temps.at(j) << std::endl;
		}
		
		unsigned int maxlen = 0;
		for(unsigned int j = 0; j < u.size(); ++j){
			if(temps.at(j).size() > maxlen){
				maxlen = temps.at(j).size();
			}
		}
		
		for(unsigned int j = 0; j < u.size(); ++j){
			while(temps.at(j).size() != maxlen){
				temps.at(j).insert(0, "0");
			}
			//std::cout << temps.at(j) << std::endl;
		}

		final_result = "";
		int kuriagari = 0;
		for(unsigned int l = 0; l < maxlen; ++l){
			int sum = 0;
			
			for(unsigned int j = 0; j < u.size(); ++j){
				sum += std::stoi(temps.at(j).substr(maxlen - 1 - l, 1));
			}

			final_result += std::to_string((kuriagari + sum) % 10);
			kuriagari = (kuriagari + sum) / 10;
			if(l == maxlen - 1 && kuriagari != 0){
				final_result += std::to_string(kuriagari);
			}
		}
		std::reverse(final_result.begin(), final_result.end());
		if(final_result.substr(0, 1) == "0"){
			final_result = "0";
		}
		//std::cout << final_result << std::endl;
	}
	
	//std::cout << final_result << std::endl;
	if(final_result.size() >= 19 && final_result > "1000000000000000000"){
		final_result = "-1";
	}
	
	std::cout << final_result << std::endl;

	return 0;
}


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

int main(){
  int A, B;
  cin >> A >> B;

  if(A >= 13){
    cout << B << endl;
  } else if (A >= 6){
    cout << B/2 << endl;
  } else {
    cout << 0 << endl;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
using namespace std;
int main() {
	char s[1000];
	string str;
	int n,kari,count=0,ans=0,a,b,c;
	vector<int> x, y;
	cin >> a>>b>>c;
  if(b>c)swap(b,c);
	n = a + b;
	if (c - n <= 0)cout << "0" << endl;
	else cout << c - n << endl;
}

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

int main() {
  string s;

  int n;
  cin >> n;
  map<string, int> m;
  for (int i = 0; i < n; i++) {
    cin >> s;
    if (m.count(s) == 0)
      m[s] = 1;
    else
      m[s]++;
  }

  int t;
  cin >> t;
  for (int i = 0; i < t; i++) {
    cin >> s;
    if (m.count(s) == 0)
      m[s] = -1;
    else
      m[s]--;
  }

  int ans = 0;
  for (auto x : m) ans = max(ans, x.second);
  cout << ans << endl;
}


Measured memory_bytes: 256