akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <queue>
#include <set>
#include <string>
#include <stdbool.h>
#include<ctime>

#include <cstring>

#define pb push_back
#define p push

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ll long long

#define getI(a) scanf("%d",&a)
#define getII(a, b) scanf("%d%d",&a,&b)
#define getIII(a, b, c) scanf("%d%d%d",&a,&b,&c)
#define getL(a) scanf("%lld",&a)
#define getLL(a, b) scanf("%lld%lld",&a,&b)
#define getLLL(a, b, c) scanf("%lld%lld%lld",&a,&b,&c)
#define BEND(c) (c).begin(),(c).end()
#define BEND2(c) (c).rbegin(),(c).rend()
#define fi first
#define se second
#define pi 3.1415926535897932384626
#define getS(a) scanf("%s",a)
#define pfb(a) printf("%.10lf\n",a);
#define pfi(a) printf("%d",a);
#define pfii(a, b) printf("%d%d",a,b);
#define pfl(a) printf("%lld",a);
#define pfll(a, b) printf("%lld%lld",a,b);
#define pfd(a) printf("%.12lf ",a);
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);
#define endl "\n"

#define MOD  ( int)(1e9 + 7)
#define MAXN (ll) ((1e6+5))
#define K 25
#define  ALPHABET_SIZE  26
//#define N (int)(1e5+10)
#define sag (sol|1)
#define sol (root<<1)
#define ort (bas+son)/2
#define INF (ll )1e18
#define int ll
using namespace std;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<pair<int, int>>> vvpi;
typedef vector<long long> vl;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<long long, long long>> vpl;
typedef pair<int, int> pii;
typedef pair <ll, ll> pll;
typedef vector<vi> graph;




signed main(){
	IOS;

	ll  a, b, c;
	cin >> a >> b >> c;
	cout << c<<" " << a << " "<< b;

	getchar();
	getchar();
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define DEBUG(X) cerr<<__LINE__<<" "<<#X<<": "<<X<<endl;
#define sci(x) int x;scanf("%d",&x);
#define scii(x, y) int x,y;scanf("%d%d",&x,&y);
#define REP(i, y) for(int i=0;i<y;i++)
typedef long long ll;
int main() {
  scii(N,T);
  int least = 0;
  ll sum=0;
  int pt=0, t=0;
  REP(i, N) {
    pt=t;
    scanf("%d",&t);
    if (least-(t-pt)>=0) {
      sum += t-pt;
    } else {
      sum+=T;
    }

    least=T;
  }
  sum+=least;
  printf("%llu\n", sum);
}

Measured memory_bytes: 760
//similar means +/- 1 - product is even when atleast one number is even
//will one number be always even
//i -1 or +1 3^10 chances 
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int >nos(10,0);
int calc(int i,int even){
    //cout<<i<<' '<<even<<'\n';
	if(i==n && even==0)return 0;
    if(i==n && even==1)return 1;
    int nways=0;
    //don't change
   	if(nos[i]%2==0)nways+=calc(i+1,1);
    else nways+=calc(i+1,even);
    //make -1
   	if((nos[i]-1)%2==0)nways+=calc(i+1,1);
    else nways+=calc(i+1,even);
    //make 1
   	if((nos[i]+1)%2==0)nways+=calc(i+1,1);
    else nways+=calc(i+1,even);
    return nways;
}
int main(){
	cin>>n;
    for(int i=0;i<n;i++)cin>>nos[i];
    //calc - index,even or not
    cout<<calc(0,0);
}

Measured memory_bytes: 3648
#[allow(unused_imports)] use proconio::{input, marker::{Bytes, Chars, Usize1, Isize1}};
#[allow(unused_imports)] use std::cmp::{min, max};

use std::collections::HashMap;

fn main() {
	input! {
		h: usize,
		w: usize,
		n: usize,
		ab: [(Usize1, Usize1); n],
	}

	// 3x3の中の黒の個数
	// 左上座標によるHashMapを作る
	let mut map = HashMap::new();

	for i in 0..n {
		// この点が含まれる3x3は最大9つある
		for y in max(0, ab[i].0 as isize -2) as usize..=min(h-2-1, ab[i].0) {
			for x in max(0, ab[i].1 as isize -2) as usize..=min(w-2-1, ab[i].1) {
				let count = map.entry((y, x)).or_insert(0usize);
				*count += 1;
			}
		}
	}

	let mut count = [0usize; 10];
	for value in &map {
		count[*value.1] += 1;
	}
	let mut tmp = 0;
	for i in 1..10 {
		tmp += count[i];
	}
	println!("{}", (h-2)*(w-2)-tmp);
	for i in 1..10 {
		println!("{}", count[i]);
	}
}



Measured memory_bytes: 44076
#include<bits/stdc++.h>
using namespace std;
int main()
{
     string s;
     cin>>s;
     int len=s.size();
     int t1=0,t2=0;
     for(int i=0;i<len;i++)
     {
          if(s[i]=='1')
                t1++;
          else t2++;
     }
     cout<<min(t1,t2)*2<<endl;
   return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <set>
#include <string>
#include <algorithm>
using namespace std;
int main() {
//    freopen("test.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    int a, b;
    cin >> a >> b;
    int cnt = 0;
    bool row = true, f = true;
    set<int> x;
    x.insert(0);
    set<int> y = x;
    for (char c : s) {
        if (c == 'F') cnt++;
        else {
            set<int> tmp;
            if (row) {
                for (int item : x) {
                    tmp.insert(item + cnt);
                    if (!f) tmp.insert(item - cnt);
                }
                swap(tmp, x);
            }
            else {
                for (int item : y) {
                    tmp.insert(item + cnt);
                    tmp.insert(item - cnt);
                }
                swap(tmp, y);
            }
            cnt = 0;
            row = !row;
            f = false;
        }
    }
    if (cnt != 0) {
        set<int> tmp;
        if (row) {
            for (int item : x) {
                tmp.insert(item + cnt);
                if (!f) tmp.insert(item - cnt);
            }
            swap(tmp, x);
        }
        else {
            for (int item : y) {
                tmp.insert(item + cnt);
                tmp.insert(item - cnt);
            }
            swap(tmp, y);
        }
    }
    if (x.find(a) != x.end() && y.find(b) != y.end()) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 896
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();

        System.out.printf("%d %d %.5f\n",a/b,a%b,(double)a/b);
        sc.close();
    }
}


Measured memory_bytes: 26512
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int mod = 1e9+7, maxn = 1e6+5;

int fac[maxn], revfac[maxn];
int n;
inline int fastpow(int a, int p){
	int ans = 1;
	while(p){
		if(p&1) ans = (ans*a)%mod;
		p >>= 1;
		a = (a*a)%mod;
	}
	return ans;
}
inline int rev(int a){return fastpow(a, mod-2);}
void init(){
	revfac[0]=fac[0] = 1; 
	for(int i = 1; i <= n; i++){
		fac[i] = fac[i-1]*i%mod;
		revfac[i] = rev(fac[i]);
//		cout<<fac[i]<<' '<<revfac[i]<<endl;
	}
}
inline int C(int n,int m){
	return 1ll*fac[n]*revfac[m]%mod*revfac[n-m]%mod;
}

void work(){
	int ans = 0, comb = 0, prev = 0;
	for(int k = (n+1)/2; k < n; k++){
		prev = comb;
		comb = C(k - 1, n - k - 1)%mod*fac[k]%mod*fac[n-k-1]%mod;
		ans += (comb - prev+ mod)%mod *k%mod;
		ans %= mod;
//		cout<<comb<<endl;
	}
	cout<<ans<<endl;
}
signed main(){
	cin>>n;
	init();
	work();
	return 0;
}


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

using namespace std;

int main(void) {
    int i, a, b, c, count;
    
    cin >> a >> b >> c;

    count = 0;
    for(i=a; i<=b; i++) {
        if(c%i==0) {
            count++;
            //cout << i << endl;
        }
    }
    
    cout << count << endl;
    
    return 0;
}

Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
int n,dp[1<<21],a[25][25];
int main(void){
    scanf("%d",&n);
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)scanf("%d",&a[i][j]);
    dp[0]=1;
    for(int k=0;k<(1<<21)-1;k++){
		int c=0;
		for(int i=0;i<n;i++)if(k>>i&1)c++;
		for(int j=0;j<n;j++)if(!(k>>j&1)&&a[c][j])dp[k^(1<<j)]=(dp[k^(1<<j)]+dp[k])%M;
	}
	printf("%d\n",dp[(1<<n)-1]);
}



Measured memory_bytes: 8576
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
    public static PrintWriter out;

    public static void main(String[] args) {
        Main.run();
    }

    private static void run() {
        out = new PrintWriter(new BufferedOutputStream(System.out));
        Scanner sc = new Scanner(System.in);
        out.println(count(Integer.parseInt(sc.next())));
        out.close();
        sc.close();
    }

    private static int count(int pnum) {
        int result = 0;
        for (int i = 0; (int) Math.pow(2, i) <= pnum; i++) {
            result = (int) Math.pow(2, i);
        }
        return result;
    }
}


Measured memory_bytes: 35712
class UnionFind:
    def __init__(self, size):
        self.parent = [-1] * size
        self.rank = [1] * size
        self.groups = size

    def get_root(self, node):
        parent = self.parent[node]
        if parent == -1:
            root = node
        else:
            root = self.get_root(parent)
            self.parent[node] = root
        return root

    def unite(self, node1, node2):
        main_root = self.get_root(node1)
        sub_root = self.get_root(node2)
        if main_root == sub_root:
            return
        if self.rank[main_root] < self.rank[sub_root]:
            main_root, sub_root = sub_root, main_root

        self.parent[sub_root] = main_root
        self.rank[main_root] += self.rank[sub_root]
        self.groups -= 1


n, m, *t = map(int,open(0).read().split())
uf = UnionFind(n)
X = t[::3]
Y = t[1::3]
for x, y in zip(X, Y):
    uf.unite(x-1, y-1)

print(uf.groups)

Measured memory_bytes: 32428
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
int main() {
    ll n;
    cin >> n;
    bool judge=false;
    ll ok=0;
    for(ll i=0;i<n;i++){
        ll a,b;
        cin >> a >> b;
        if(a==b){
            ok++;
        }else{
            ok=0;
        }
        if(ok>=3){
            judge=true;
        }
    }
    if(judge){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector<int> now(n);
    for (int i = n - 1; i >= 0; --i) {
        int sum = 0;
        for (int d = 2 * i + 2; d <= n; d += i + 1) sum += now[d - 1];
        if (sum % 2 != a[i]) now[i] = 1;
    }
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        cnt += now[i];
    }
    cout << cnt << endl;
    for (int i = 0; i < n; ++i) if (now[i]) cout << i + 1 << " ";
    cout << endl;
    return 0;
}


Measured memory_bytes: 3968
#include <bits/stdc++.h>
#define ll long long
#define pLL pair<ll, ll>
#define fs first
#define sc second
using namespace std;
const int N = 2e5 + 50;

#define inc(i, x, y) for (register int i = x; i <= y; ++i)
#define dec(i, x, y) for (register int i = x; i >= y; --i)
#define gc getchar

bool chkmin(int &x, int y) { return x > y ? x = y, 1 : 0; }
bool chkmax(int &x, int y) { return x < y ? x = y, 1 : 0; }

inline int rd() {
	int ret = 0; bool fl = 0; char ch = 0;
	while (!isdigit(ch)) fl |= (ch == '-'), ch = gc();
	while (isdigit(ch)) ret = (ret << 1) + (ret << 3) + (ch ^ 48), ch = gc();
	return fl ? -ret : ret;
}

#define go(i, v, x) for (int i = head[x], v = e[i].to; i; i = e[i].nxt, v = e[i].to)
struct edge { int nxt, to; ll w; } e[N << 1];
int head[N], odd[N], l[N], r[N], t[N], v[N], p[N], ecnt;

inline void add(int u, int v, int w) {
	e[++ecnt] = (edge) {head[u], v, w}, head[u] = ecnt;
	e[++ecnt] = (edge) {head[v], u, w}, head[v] = ecnt;
}

ll lim;

vector<pLL> tr, tl;
vector<pLL> f[N];

inline void init(int x, const pLL &t) {
    if (f[x].size() && f[x].back() <= t) return;
    while (f[x].size() && f[x].back().sc >= t.sc) f[x].pop_back();
    f[x].push_back(t);
}

inline bool dfs(int x, int fa) {
    f[x].clear();
    if(!e[head[x]].nxt) return f[x].push_back(pLL(0, 0)), true;
    ll lc, rc, disl, disr;
	bool fl = 0;
    go(i, v, x) {
        if (v==fa) continue;
        if (!dfs(v,x)) return false;
        if (!fl) fl=1, lc=v, disl = e[i].w;
        else rc=v, disr=e[i].w;
    }
    tl.clear(), tr.clear();
	ll lim2 = lim - disl - disr;
    if (lim2 < 0) return false; 
    int p1 = 0;
    inc (p2, 0, (signed) f[rc].size() - 1) {
        while (p1 < f[lc].size() && f[lc][p1].fs + f[rc][p2].sc > lim2) ++p1;
        if(p1 == f[lc].size()) break;
        tl.push_back(pLL(f[rc][p2].fs + disr, f[lc][p1].sc + disl));
    }
    int p2 = 0;
    inc (p1, 0, (signed)f[lc].size() - 1) {
        while (p2 < f[rc].size() && f[lc][p1].sc + f[rc][p2].fs > lim2) ++p2;
        if(p2 == f[rc].size()) break;
        tr.push_back(pLL(f[lc][p1].fs + disl, f[rc][p2].sc + disr));
    }
    int pl=0, pr=0;
    while (pl < tl.size() && pr < tr.size()) {
        if (tl[pl].fs > tr[pr].fs) init(x, tl[pl++]);
        else init(x, tr[pr++]);
    }
    while (pl < tl.size()) init(x, tl[pl++]);
    while (pr < tr.size()) init(x, tr[pr++]);
    return f[x].size() > 0;
}

int main() {
	int n = rd();
	inc(i, 2, n) {
		int v = rd(), w = rd();
		add(i, v, w);
	}
	ll l = 0, r = 17179869184, ans;
	while (l <= r) {
		ll mid = (l + r) >> 1;
		lim = mid;
		if (dfs(1, -1)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	printf("%lld\n", ans); 
}

Measured memory_bytes: 36700
#include <stdio.h>
#include <stdlib.h>

#define SENTINEL 1000000000

int cnt = 0;

void merge(int a[], int left, int mid, int right) {
  int n1 = mid - left;
  int n2 = right - mid;
  int *L;
  int *R;
  L = (int *)malloc(sizeof(int)*(n1 + 1));
  R = (int *)malloc(sizeof(int)*(n2 + 1));
  for (int i = 0; i < n1; i++) {
    L[i] = a[left + i];
  }
  for (int i = 0; i < n2; i++) {
    R[i] = a[mid + i];
  }
  L[n1] = SENTINEL;
  R[n2] = SENTINEL;
  int i = 0;
  int j = 0;
  for (int k = left; k < right; k++) {
    if (L[i] <= R[j]) {
      a[k] = L[i];
      i++;
    } else {
      a[k] = R[j];
      j++;
    }
    cnt++;
  }
  free(L);
  free(R);
}

void mergeSort(int a[], int left, int right) {
  int mid = 0;
  if (left + 1 < right) {
    mid = (left + right) / 2;
    mergeSort(a, left, mid);
    mergeSort(a, mid, right);
    merge(a, left, mid, right);
  }
}

int main() {
  int n;
  scanf("%d", &n);
  int a[500000];

  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  mergeSort(a, 0, n);

  for (int i = 0; i < n; i++) {
    if (i == n - 1) {
      printf("%d", a[n - 1]);
    } else {
      printf("%d ", a[i]);
    }
  }
  printf("\n");
  printf("%d\n", cnt);

  return 0;
}



Measured memory_bytes: 5456
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;

class MainClass
{
   static void Main(string[] args)
   {
      const string wrong = "Hoshino";
      const string correct = "Hoshina";

      var stringbuilder = new StringBuilder();

      int n;
      while ((n = int.Parse(Console.ReadLine())) != 0)
      {
         int[,] matrix = new int[n, n + 1];

         for (int row = 0; row < n; row++)
         {
            string[] datas = Console.ReadLine().Split(' ');

            int sum = 0;
            for (int column = 0; column < n; column++)
            {
               int val = int.Parse(datas[column]);
               matrix[row, column] = val;
               sum += val;

               stringbuilder.AppendFormat("{0,5}", val);
            }
            matrix[row, n] = sum;

            stringbuilder.AppendFormat("{0,5}\n", sum.ToString());
         }

         for (int column = 0; column <= n; column++)
         {
            int sum = 0;
            for (int row = 0; row < n; row++)
            {
               sum += matrix[row, column];
            }

            stringbuilder.AppendFormat("{0,5}", sum.ToString());
         }
         stringbuilder.AppendLine();
      }

      Console.Write(stringbuilder.ToString());
   }
}

Measured memory_bytes: 9344
/*  -*- coding: utf-8 -*-
 *
 * b.cc: B: Postal Code
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

/* typedef */

/* global variables */

/* subroutines */

/* main */

int main() {
  int a, b;
  string s;
  cin >> a >> b >> s;

  int n = s.size();
  if (n != a + b + 1) {
    puts("No");
    return 0;
  }

  for (int i = 0; i < n; i++)
    if ((i == a && s[i] != '-') ||
	(i != a && (s[i] < '0' || s[i] > '9'))) {
      puts("No");
      return 0;
    }

  puts("Yes");
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------






string S; int N;
int xy[2];
//---------------------------------------------------------------------------------------------------
int check(int x, vector<int> _v) {
    vector<int> v;
    fore(i, _v) if (i) v.push_back(i);

    int n = v.size();
    int cent = 8080;
    
    set<int> dp;
    dp.insert(0);
    fore(i, _v) {
        set<int> pd;
        fore(j, dp) {
            pd.insert(j + i);
            pd.insert(j - i);
        }
        swap(dp, pd);
    }

    fore(i, dp) if (i == x) return 1;
    return 0;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> xy[0] >> xy[1];
    N = S.length();

    int pre = -1, state = 0;
    vector<int> v[2];
    rep(i, 0, N) {
        if (S[i] == 'T') {
            v[state].push_back(i - pre - 1);
            state = 1 - state;
            pre = i;
        }
    }
    v[state].push_back(N - pre - 1);

    xy[0] -= v[0].front();
    v[0].erase(v[0].begin(), v[0].begin() + 1);

    rep(d, 0, 2) {
        if (!check(xy[d], v[d])) {
            printf("No\n");
            return;
        }
    }

    printf("Yes\n");
}

Measured memory_bytes: 656
#include <bits/stdc++.h>
#define REP(i, n) for(long long i=0; i<n; i++)
#define REPR(i, n) for(long long i=n-1; i>=0; i--)
#define FOR(i, m, n) for(long long i=m; i<=n; i++)
#define FORR(i, m, n) for(long long i=m; i>=n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
#define FIN ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;
const ll mod = 1e9+7;
const ll inf = 1e15;



int main(){FIN

    ll s;cin>>s;
    string ans;
    if(s==3 || s==5 || s==7) ans="YES";
    else ans="NO";
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main()
{
	int x;
	cin>>x;
	int ans = 0;
	int v = x/500;
	x = x %500;
	ans = ans + v*1000;
	v = x/5;
	ans = ans + v*5;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <numeric>
#include <bitset>
#include <vector>
#include <queue>

using namespace std;

typedef long long ll;
#define FOR(i,a,b)   for(ll i = (a); i < (b); i++ )
#define REP(i, n)    FOR(i,0,n)
typedef pair< ll, ll >   cp2;
typedef pair< ll, cp2 >   cp3;
#define fi first
#define se second
#define sec  se.fi
#define thr  se.se
const ll mod = 1000000007;
//              123456789

 
///////////////////////////////////////////////
//
//
///////////////////////////////////////////////

////////////////////////////////////////////////
////////////////////////////////////////////////

int A, B;

int main(){
	
	cin>>A>>B;
	
	if( A > 8 || B > 8 ){
		puts(":(");
	}
	else{
		puts("Yay!");
	}
	
}


Measured memory_bytes: 256
// C++ 14
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(ll __x = __start; __x < __end; __x++)

/* SegTreeLazy<X,M>(n,fx,fa,fm,ex,em): モノイド(集合X, 二項演算fx,fa,fm, 単位元ex,em)についてサイズnで構築
    set(int i, X x), build(): i番目の要素をxにセット。まとめてセグ木を構築する。O(n)
    update(i,x): i 番目の要素を x に更新。O(log(n))
    query(a,b):  [a,b) 全てにfxを作用させた値を取得。O(log(n))
*/
template <typename X, typename M>
struct SegTreeLazy {
    using FX = function<X(X, X)>;
    using FA = function<X(X, M)>;
    using FM = function<M(M, M)>;
    int n;
    FX fx;
    FA fa;
    FM fm;
    const X ex;
    const M em;
    vector<X> dat;
    vector<M> lazy;
    SegTreeLazy(int n_, FX fx_, FA fa_, FM fm_, X ex_, M em_)
        : n(), fx(fx_), fa(fa_), fm(fm_), ex(ex_), em(em_), dat(n_ * 4, ex), lazy(n_ * 4, em) {
        int x = 1;
        while (n_ > x) x *= 2;
        n = x;
    }
    void set(int i, X x) { dat[i + n - 1] = x; }
    void build() {
        for (int k = n - 2; k >= 0; k--) dat[k] = fx(dat[2 * k + 1], dat[2 * k + 2]);
    }
    /* lazy eval */
    void eval(int k) {
        if (lazy[k] == em) return;  // 更新するものが無ければ終了
        if (k < n - 1) {            // 葉でなければ子に伝搬
            lazy[k * 2 + 1] = fm(lazy[k * 2 + 1], lazy[k]);
            lazy[k * 2 + 2] = fm(lazy[k * 2 + 2], lazy[k]);
        }
        // 自身を更新
        dat[k] = fa(dat[k], lazy[k]);
        lazy[k] = em;
    }
    void update(int a, int b, M x, int k, int l, int r) {
        eval(k);
        if (a <= l && r <= b) {  // 完全に内側の時
            lazy[k] = fm(lazy[k], x);
            eval(k);
        } else if (a < r && l < b) {                     // 一部区間が被る時
            update(a, b, x, k * 2 + 1, l, (l + r) / 2);  // 左の子
            update(a, b, x, k * 2 + 2, (l + r) / 2, r);  // 右の子
            dat[k] = fx(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }
    void update(int a, int b, M x) { update(a, b, x, 0, 0, n); }
    X query_sub(int a, int b, int k, int l, int r) {
        eval(k);
        if (r <= a || b <= l) {  // 完全に外側の時
            return ex;
        } else if (a <= l && r <= b) {  // 完全に内側の時
            return dat[k];
        } else {  // 一部区間が被る時
            X vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
            X vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
            return fx(vl, vr);
        }
    }
    X query(int a, int b) { return query_sub(a, b, 0, 0, n); }
};


int main() {
  int n, q; cin >> n >> q;
  using X = int;
  using M = int;
  auto fx = [](X x1, X x2) { return min(x1, x2); };
  auto fa = [](X x, M m) { return m; };
  auto fm = [](M m1, M m2) { return m2; };
  int ex = numeric_limits<int>::max();
  int em = numeric_limits<int>::max();
  SegTreeLazy<X, M> seg(n, fx, fa, fm, ex, em);
  loop(i,0,q) {
    int com, x, y; cin >> com >> x >> y;
    if (com == 0)  seg.update(x, x+1, y);
    else cout << seg.query(x, y+1) << endl;
  }
  return 0;
}



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

typedef pair<int,int> ii;
const int MAX=1e5+5;
int n,rs=0;
ii a[MAX];

int main() {
	ios_base::sync_with_stdio(false);
	// freopen("input","r",stdin);
	cin>>n;
	int x,k;
	for(int i=1;i<=n;i++) {
		cin>>x>>k;
		a[i]=ii(x+k,x-k);
	}
	sort(a+1,a+n+1);
	int pre=-1e9;
	for(int i=1;i<=n;i++)
		if(pre<=a[i].second) {
			rs++;
			pre=a[i].first;
		}
	cout<<rs;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    int N;
    cin >> N;
    vector<int> V(N+2), T(N+2), accumT(N+2);
    rep(i,1,N+1){
        cin >> T[i];
        T[i] *= 2;
        accumT[i+1] = accumT[i] + T[i];
    }
    rep(i,1,N+1){
        cin >> V[i];
        V[i] *= 2;
    }
    vector<int> p(40010);
    rep(i,0,accumT[N+1]+1){
        rep(j,1,N+2){
            if(accumT[j] >= i){
                p[i] = V[j-1];
                break;
            }
        }
        rep(j,1,N+2){
            int d = abs(accumT[j] - i);
            p[i] = min(p[i], d + min(V[j-1], V[j]));
        }
    }
    int sum = 0;
    rep(i,0,accumT[N+1]+1)sum += p[i];
    printf("%.9lf\n", 0.25 * sum);
}

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

using namespace std;
#define X first
#define Y second
#define pb push_back
typedef double db;
typedef long long ll;
typedef pair<int,int> P;
const int MAXN=1e6+10,MOD=1e9+7;
int n,dp[MAXN],pre[MAXN];

int main()
{
    scanf("%d",&n);
    dp[0]=pre[0]=1;ll res=0;
    for(int i=1;i<=n;i++)
    {
        (dp[i]+=dp[i-1])%=MOD;
        if(i>=3) (dp[i]+=pre[i-3])%=MOD;
        pre[i]=(pre[i-1]+dp[i])%MOD;
    }
    for(int i=0;i<n-1;i++)
        (res+=1ll*dp[i]*(n-1)%MOD*(n-1)%MOD)%=MOD;
    for(int i=0;i<n;i++)
        (res+=1ll*dp[i]*min(i+1,n-1)%MOD)%=MOD;
    (res+=dp[n])%=MOD;
    printf("%lld",res);
    return 0;
}

Measured memory_bytes: 8064
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(obj)   (obj).begin(),(obj).end()

#define debug(var)  do{std::cout << __LINE__ << "> " << #var << ": ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

void Main() {
	int N; cin >> N;
	int n = N % 10;
	if (n == 3) {
		cout << "bon" << endl;
		return;
	} else if (n == 0 || n == 1 || n == 6 || n == 8) {
		cout << "pon" << endl;
		return;
	}
	cout << "hon" << endl;
}

int main() {
    cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
}


Measured memory_bytes: 3620
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>

using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); i++)

int main() {
  int K, N;
  cin >> N >> K;
  vector<int> cnt(N+1,0);
  REP(i,N) {
    int a; cin>>a;
    cnt[a]++;
  }
  vector<int> rec;
  REP(i,N+1) {
    if(cnt[i]>0) rec.push_back(cnt[i]);
  }
  int ans = 0;
  //  REP(i,rec.size()) cout << rec[i] << " " ; cout << endl;                       
  if(rec.size() <= K) {
  } else {
    sort(rec.begin(), rec.end());
    reverse(rec.begin(), rec.end());
    for(int i = K; i < rec.size(); i++) {
      ans += rec[i];
    }
  }

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


Measured memory_bytes: 2168
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	string s,t;
	cin>>s>>t;
	vector<vector<int> > v(s.length()+1,vector<int>(t.length()+1));
	for(int i=0;i<=(int)s.length();i++)
	{
		v[i][0]=0;
	}
	for(int i=0;i<=(int)t.length();i++)
	{
		v[0][i]=0;
	}
	for(int i=1;i<=(int)s.length();i++)
	{
		for(int j=1;j<=(int)t.length();j++)
		{
			if(s[i-1]==t[j-1])
			{
				v[i][j]=v[i-1][j-1]+1;
			}
			else
			{
				v[i][j]=max(v[i-1][j],v[i][j-1]);
			}
		}
	}
	int n=s.length();
	int m=t.length();
	string p="";
	while(n!=0&&m!=0)
	{
		if(v[n-1][m]>=v[n][m])
		{
			n--;
		}
		else
		if(v[n][m-1]>=v[n][m])
		{
			m--;
		}
		else
		{
			p+=s[n-1];
			n--;
			m--;
		}
	}
	reverse(p.begin(),p.end());
	cout<<p;
}


Measured memory_bytes: 35584
H, W = [int(_) for _ in input().split()]
A = []
for _ in range(H):
    A.append([int(_) for _ in input().split()])

ans = []
cnt = 0


def prt(i, j, k, l):
    global cnt
    cnt += 1
    ans.append((i + 1, j + 1, k + 1, l + 1))


for i in range(H):
    if i % 2 == 0:
        s, e, step = 0, W - 1, 1
    else:
        s, e, step = W - 1, 0, -1

    for j in range(s, e, step):
        if A[i][j] % 2:
            A[i][j + step] += 1
            prt(i, j, i, j + step)

    if i < H - 1:
        if A[i][e] % 2:
            A[i + 1][e] += 1
            prt(i, e, i + 1, e)
print(cnt)
for a in ans:
    print(*a)


Measured memory_bytes: 26632
#include<bits/stdc++.h>
#define mk make_pair
using namespace std;
long long a[100010], b[100010], trakm[100010];
int main()
{
//    int c[4]={1,3,4};
//    cout<<(lower_bound(c, c+3, 2)-c)<<endl;
    int h, w;
    cin>>h>>w;
    long long ans=0;
    for(int i=0; i<h; ++i){
      cin>>a[i];
      ans+=a[i];
    }
    for(int i=0; i<w; ++i){
      cin>>b[i];
      ans+=b[i];
    }
    sort(a, a+h);
    sort(b, b+w);
    trakm[0]=b[0];
    for(int i=1; i<w; ++i){
      trakm[i]=trakm[i-1]+b[i];
    }
    int tmp;
    for(int i=0; i<h; ++i){
      tmp=lower_bound(b, b+w, a[i])-b;
      if(tmp>0)
        ans+=trakm[tmp-1];
      tmp=w-tmp;
      ans+=tmp*a[i];
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 2688
#include <iostream>

using namespace std;

int main() {
    int n, s;
    while (cin >> n >> s) {
        if ((n | s) == 0) break;
        int dp[n + 1][s + 1];
        fill(dp[0], dp[n + 1], 0);
        dp[0][0] = 1;
        for (int i = 0; i <= 9; i++) {
            for (int j = n; j > 0; j--) {
                for (int k = i; k <= s; k++) {
                    dp[j][k] += dp[j - 1][k - i];
                }
            }
        }
        cout << dp[n][s] << endl;
    }
}


Measured memory_bytes: 3000
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * Built using CHelper plug-in Actual solution is at the top
 */

public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task solver = new Task();
		solver.solve(1, in, out);
		out.close();
	}

	static class Task {
		public void solve(int testNumber, InputReader in, PrintWriter out) {
			int a = in.nextInt();
			int b = in.nextInt();
			int c = in.nextInt();
			if(a == b && b == c) {
				out.println("1");
			} else if(((a == b || a == c) && b != c) || ((b == c || b == a) && c != a)) {
				out.println("2");
			} else {
				out.println("3");
			}
		}
	}

	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

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

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

	}
}

Measured memory_bytes: 21460
#include <stdio.h> 
#include <stdlib.h>
int main(void)
{
	int a, b, c;
	int max, min, total = 0;
	scanf("%d %d %d", &a, &b, &c);
	total = a + b + c;
	
	if(a > b && a > c)
	{
		max = a;
	}
	else if(b > a && b > c)
	{
		max = b;
	}
	else 
	{
		max = c;
	}
	
	if(a < b && a < c)
	{
		min = a;
	}
	else if(b < a && b < c)
	{
		min = b;
	}
	else
	{
		min = c;
	}
	printf("%d %d %d\n", min, total - max - min, max);
	return 0;
	
}


Measured memory_bytes: 2072
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
const int MOD = 1000000007;

int main() {
  int a,b;
  cin >> a >> b;
  cout << 6-a-b << endl;
  return 0;
}

Measured memory_bytes: 256
//Selection Sort

#include <stdio.h>
#include <stdlib.h>

main(){
  
  int n;
  int *a; //配列用ポインタ
  int minj;
  int c; //交換回数

  int i,j,tmp;

  scanf("%d", &n);

  a = (int *)malloc(sizeof( int ) * n);

  for( i=0; i<n; i++) {
    scanf("%d", &a[i]);
  }

  c = 0;

  for( i=0; i<n; i++) {
    minj = i;
    for( j=i; j<n; j++) {
      if( a[j] < a[minj] ) {
	minj = j;
      }
    }
    if(a[i] != a[minj]) {
      tmp = a[i];
      a[i] = a[minj];
      a[minj] = tmp;
      c++;
    }
  }
  
  
  for( i=0; i<n-1; i++) { 
    printf("%d ", a[i]);
  }
  printf("%d\n%d\n", a[n-1], c);
  
  free(a);
  
  return 0;
  
}

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

int main(){
	long long int n,p;
	cin>>n>>p;
	int a;
	int g=0;
	int k=0;
	for(int i=0;i<n;i++){
		cin>>a;
		if(a%2==0){
			g++;
		}else{
			k++;
		}
	}
	
	if((k==0)&&p==0){
		long long int ans=1;
		for(int i=0;i<n;i++)ans*=2;
		cout<<ans<<endl;
		return 0;
	}
	if((k==0)&&p==1){
		cout<<0<<endl;
		return 0;
	}
	
	long long int ans=1;
	for(int i=0;i<n-1;i++)ans*=2;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
/**
*	  Name: Ajay
*	  Institute: IIITH 
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <string.h>
#define ll long long
#define inf 0x7fffffff
#define mod 1000000007
#define pb push_back
#define ppi pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vii vector<ppi>
#define vll vector<ll>
#define mp make_pair
#define fi first
#define se second
using namespace std;

void fastio()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}
void input()
{
  #ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  #endif
}

int main()
{      
  fastio();
  ll n,k;
  cin>>n>>k;
  if(n==0){
  	cout<<0;
  	return 0;
  }
    if(n>k && n%k==0){
    	cout<<0;
        return 0;
    }
  	else if(n<k && k%n==0){
    	cout<<n;
    	return 0;
    }
   
	while(n>k){
    	n=n%k;
    }
    
	ll m1=abs(n-k);
  	cout<<min(n,m1);
  return 0;
}

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

//int q[11] = {2,3,4,5,6,7,2,3,4,5,6};
int q[11] = {6,5,4,3,2,7,6,5,4,3,2};

int calc_digit(string str){
	int ret = 0;
	for(int unsigned i = 0;i<str.size()-1;i++){
		ret += (int)(str[i]-'0')*q[i];
		ret%=11;
	}
	if(ret <= 1) return 0;
	return 11-ret;
}

int main(){
	string str;
	cin >> str;
	
	int idx = 0;
	for(int unsigned i = 0;i < str.size();i++){
		if(str[i] == '?') idx = i;
	}
	if(idx == str.size()-1){
		cout << calc_digit(str) << endl;
		return 0;
	}
	vector<int> ans;
	for(int i=0;i<=9;i++){
		str[idx] = i + '0';
		if(str[str.size()-1] - '0' == calc_digit(str)){
			ans.emplace_back(i);
		}
	}
	if(ans.size() == 1) cout << ans[0] << endl;
	else cout << "MULTIPLE" << endl;
	return 0;
}

Measured memory_bytes: 3196
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1e5 + 7;
ll fb[maxn];
vector<ll> a[4];
ll f2[maxn];
int n;
void mf(){
	freopen("input.in","r",stdin);
	//freopen("output.ou","w",stdout);
}

int findUpper(int x, int k){
	int l = 1, r = n;
	int rr = n + 1;
	while(l <= r){
		int mid = l + (r-l)/2;
		if(a[k][mid] > x){
			rr = mid;
			r = mid - 1;
		}else{
			l = mid + 1;
		}
	}	
	return rr;
}

void solve(){
	cin>>n;
	for(int k = 1; k <= 3; k ++){
		a[k].resize(n + 1);
		for(int i = 1; i <= n; i++){
			cin>>a[k][i];
		}
	}
		
	for(int k = 1; k <= 3; k++){
		sort(a[k].begin(), a[k].end());
	}
	f2[n + 1] = 0;
	for(int i = n; i >= 1; i--){
		f2[i] = f2[i + 1];		
		int j = findUpper(a[2][i], 3);		
		f2[i] += max(0, n - j + 1);
		// cout<<"f2 "<<i<<" "<<f2[i]<<" "<<a[2][i]<<endl;
	}

	ll sum = 0;
	for(int i = 1; i <= n; i++){
		int x = a[1][i];
		int j = findUpper(x, 2);
		sum += f2[j];
	}
	cout<<sum;
}

int main(){
	ios_base::sync_with_stdio(false);
	#ifdef tuanh
		mf();
	#endif
	solve();
	return 0;
}

Measured memory_bytes: 3456
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 110;
char lx[N];

int main() {
	ll k;
	scanf("%s%lld", lx + 1, &k);
	int n = strlen(lx + 1), be = 0, ed = 0, ans = 0;
	for(int i = 1; i <= n; ++i) {
		int j = i;
		for(; j <= n && lx[j] == lx[i]; ++j);
		j--;
		if(i == 1) be = j - i + 1;
		else if(j == n) ed = j - i + 1;
		else ans += (j - i + 1) / 2;
		i = j;
	}
	if(!ed) {
		ll res = 1ll * k * n / 2;
		printf("%lld\n", res);
		return 0;
	}
	if(lx[1] == lx[n]) {
		ll res = 1ll * (k - 1) * ((be + ed) / 2 + ans) + ans;
		res += be / 2 + ed / 2;
		printf("%lld\n", res);	
	} else {
		ll res = 1ll * k * (ans + (be / 2 + ed / 2));
		printf("%lld\n", res);
	}
	return 0;
}

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

int main()
{
    long long int n,k,ans,i;
    cin>>n>>k;
    ans=k;//for 1st ball we can select any color
    for(i=2;i<=n;i++){
        ans*=k-1;//rest of the balls can be selected in k-1 ways
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
long long n,a,b;
long long p=1000000007;
long long qpow(long long a,long long b){
	long long ans=1;
	while(b>0){
		if(b&1){
			ans=ans*a;
			ans%=p;
		}
		a=a*a;
		a%=p;
		b>>=1;
	}
	return ans;
}
long long C(long long n,long long m){
    if(m>n)return 0;
    long long ans=1;
    for(long long i=1;i<=m;i++){
        long long a=(n+i-m)%p;
        long long b=i%p;
        ans=ans*(a*qpow(b,p-2)%p)%p;
    }
    return ans;
}
int main(){
	cin>>n>>a>>b;
	cout<<(qpow(2,n)-C(n,a)-C(n,b)+p+p-1ll)%p;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;


struct UnionFind{
   vector<int> par;
   UnionFind(int n):par(n,-1){}
   int find(int x){
       if(par[x]<0)return x;
       return par[x]=find(par[x]);
   }
   bool unite(int x,int y){
       x=find(x);
       y=find(y);
       if(x==y)return false;
       if(par[x]>par[y]){
           par[y]+=par[x];
           par[x]=y;
       }
       else{
           par[x]+=par[y];
           par[y]=x;
       }
       return true;
   }

   bool same(int x,int y){
       return find(x)==find(y);
   }
   ll size(int x){
       return -par[find(x)];
   }
};
int main(){
    ll n,m;
    cin>>n>>m;
    vector<pint> p(m);
    rep(i,m){
        int x,y;
        cin>>x>>y;
        --x;--y;
        p[m-i-1]={x,y};
    }
    UnionFind uf(n);
    vector<ll> ans(m);
    ans[0]=n*(n-1)/2;
    rep(i,m-1){
        if(!uf.same(p[i].first,p[i].second))ans[i+1]=ans[i]-uf.size(p[i].first)*uf.size(p[i].second);
        else ans[i+1]=ans[i];
        uf.unite(p[i].first,p[i].second);
    }
    rep(i,m)cout<<ans[m-i-1]<<endl;
    return 0;
}

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

#define MOD 1000000007

int dp[100000][100][2] = {};

void add(int &a, int b) {
    a = (a + b) % MOD;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    string k;
    int d;
    cin >> k >> d;

    for (int kk=0; kk<k[0]-'0'; kk++)
        dp[0][kk%d][0]++;
    dp[0][(k[0]-'0')%d][1]++;
    for (int i=0; i<k.length()-1; i++)
        for (int j=0; j<d; j++) {
            for (int kk=0; kk<10; kk++)
                add(dp[i+1][(j+kk)%d][0], dp[i][j][0]);
            for (int kk=0; kk<k[i+1]-'0'; kk++)
                add(dp[i+1][(j+kk)%d][0], dp[i][j][1]);
            add(dp[i+1][(j+k[i+1]-'0')%d][1], dp[i][j][1]);
        }

    add(dp[k.length()-1][0][0], dp[k.length()-1][0][1]);
    cout << (dp[k.length()-1][0][0] + MOD - 1) % MOD << "\n";

    return 0;
}


Measured memory_bytes: 8448
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
int n;

int main(void){
    // Your code here!
    string S, T;
    int dp[1001][1001];
    cin >> n;
    for(int c = 0; c < n; c++){
        cin >> S >> T;
        
        for(int i = 0; i <= S.size(); i++){
            dp[i][0] = 0;
        }
        for(int j = 0; j <= T.size(); j++){
            dp[0][j] = 0;
        }
        
        for(int i = 0; i < S.size(); i++){
            for(int j = 0; j < T.size(); j++){
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
                if(S[i]==T[j]) dp[i+1][j+1] = max(dp[i][j] + 1, dp[i+1][j+1]);
            }
        }
        
        cout << dp[S.size()][T.size()] << endl;
    }
}



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

int main( ) {
  int N,l,r;
  cin>>N;
  int count=0;
  for(int i=0; i<N; i++) {
    cin>>l>>r;
    count+=r-l+1;
  }
  cout<<count<<endl;
}
    
    

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<cmath>
#include<string>
#include<bitset>
#include <sstream>
#include<queue>
#include<stack>
#include<iomanip>
#include<functional>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define sayyes cout<<"Yes"<<endl;
#define sayno cout<<"No"<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int mod=1e9+7;
const int MAX=510000;
struct mint
{
    ll x;
    //constructor
    mint(ll y=0):x((y%mod+mod)%mod){}

    
    mint operator-() const{return mint(-x);}

    mint& operator+=(const mint a)
    {
        if((x+=a.x)>=mod) x-=mod;
        return *this;
    }

    mint& operator-=(const mint a)
    {
        if((x+=mod-a.x)>=mod)x-=mod;
        return *this;
    }

    mint& operator*=(const mint a)
    {
        (x*=a.x)%=mod;
        return *this;
    }

    mint operator+(const mint a)const{
        mint res(*this);
        return res+=a;
    }

    mint operator-(const mint a)const
    {
        mint res(*this);
        return res-=a;
    }

    mint operator*(const mint a)const
    {
        mint res(*this);
        return res*=a;
    }

    mint pow(ll t)const{
        if(t==0)return 1;
        mint a=pow(t/2);
        a*=a;
        if(t%2==1)a*=2;
        return a;
    }

    mint inv() const{
        return pow(mod-2);
    }

    mint& operator/=(const mint a)
    {
        return (*this)*=a.inv();
    }

    mint operator/(const mint a)const{
        mint res(*this);
        return res/=a;
    }

};

mint choose(int n, int a)
{
    mint x=1,y=1;
    rep(i,a)
    {
        x*=n-i;
        y*=i+1;
    }
    return x/y;
}
int main()
{
    int n,k;
    cin>>n>>k;
    mint ans=0;
    for(ll i=k;i<=n+1;i++)
    {
        ll start=(i-1)*i/2;
        ll last=(n-i+1+n)*i/2;
       // cout<<start<<" :"<<last<<endl;
        ans+=(last-start+1);

    }
    cout<<ans.x;
    
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d", &x)
#define sz(v) (int) v.size()
#define pr(v) For(i, 0, sz(v)) {cout<<v[i]<<" ";} cout<<endl;
#define slld(x) scanf("%lld", &x)
#define all(x) x.begin(), x.end()
#define For(i, st, en) for(ll i=st; i<en; i++)
#define tr(x) for(auto it=x.begin(); it!=x.end(); it++)
#define fast std::ios::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define ll long long
#define int long long
#define mp make_pair
#define F first
#define S second
typedef pair<int, int> pii;
typedef vector<int> vi;
#define MOD 1000000007
#define INF 1000000000000000007LL

const int N = 100005;
 
// it's swapnil07 ;)
 
#ifdef SWAPNIL07
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
int begtime = clock();
#define end_routine() cout << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";
#else
#define endl '\n'
#define trace(...)
#define end_routine()
#endif


vector<int> adj[N];
int h[N];

void solve(){
    int n, m; cin>>n>>m;
    int ans = 0;
    For(i, 1, n+1){
        cin>>h[i];
    }
    For(j, 0, m){
        int u, v; cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    For(i, 1, n+1){
        bool fl = true;
        for(int v: adj[i]){
            if(h[i]<=h[v]){
                fl = false;
            }
        }
        if(fl)
            ans++;
    }
    cout<<ans;
}


signed main()
{
    fast
    #ifdef SWAPNIL07
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}





Measured memory_bytes: 10220
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define MAXN 30031
using namespace std;
char s[MAXN];
int n;
int find(int st,char x)
{
    for(int i=st;i<=n;i++)
    {
        if(x==s[i])
        {
            return i;
        }
    }
    return -1;
}
int main()
{
    cin>>n;
    scanf("%s",s+1);
    int ans=0;
    for(int i=0;i<=999;i++)
    {
        int a=i/100,b=(i/10)%10,c=i%10;
        int st=1;
        st=find(st,a+'0');
        if(st==-1)continue;
        st=find(st+1,b+'0');
        if(st==-1)continue;
        st=find(st+1,c+'0');
        if(st==-1)continue;
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}



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

const int INF = 1145141919;
const long long INFL = 1LL<<60;

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

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

int dp[3*1100][3*1100] = {};
int main()
{
	string s,t;
	cin >> s >> t;
	s = "@" + s;
	t = "@" + t;
	for (int i = 1; i < s.size(); ++i)
	{
		for (int j = 1; j < t.size(); ++j)
		{
			if(s[i] == t[j])
			{
				dp[i][j] = dp[i-1][j-1] + 1;
			}
			else
			{
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			}
		}
	}
	int len = dp[s.size() - 1][t.size() - 1];
	int i = s.size() - 1;
	int j = t.size() - 1;
	string ans;
	while(len > 0)
	{
		if(s[i] == t[j])
		{
			ans += s[i];
			--i;
			--j;
			--len;
		}
		else if(dp[i][j] == dp[i-1][j])
		{
			--i;
		}
		else
		{
			--j;
		}
	}
	for (int i = 0; i < ans.size(); ++i)
	{
		cout << ans[ans.size() - 1 - i];
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 39168
#include <bits/stdc++.h>
using namespace std;
int main(void){
    
    long long int aint, bint, ans;
    double bdouble;
    cin >> aint >> bdouble ;

    bint = round(bdouble * 100);
    
    ans = aint * bint / 100;

    cout << ans << endl;

    return 0; 
}


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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,k;cin>>n>>k;
    vector<int> a(n);
    rep(i,n){
      cin>>a[i];
      a[i]--;
    }
    vector<int> foo;
    vector<int> ss(n,-1);
    int key=a[0],tmp=0;
    while(ss[key]==-1){
      foo.push_back(key);
      ss[key]=tmp++;
      key=a[key];
    }
    if(k<=foo.size()){
        cout<<foo[k-1]+1<<endl;
        return 0;
    }
    tmp=ss[key];
    ll rot=foo.size()-tmp;
    k-=tmp;
    k%=rot;
    if(k==0)cout<<foo[tmp+rot-1]+1<<endl;
    else cout<<foo[k+tmp-1]+1<<endl;
    return 0;
}


Measured memory_bytes: 5844