akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct Node{
  int key;
  struct Node *right, *left, *parent;
};

struct Node *root, *NIL;

struct Node * treeMinimum(struct Node *x){
  while(x->left != NIL) x = x->left;
  return x;
}

struct Node * find(struct Node *u, int k){
  while(u != NIL && k != u->key){
    if(k < u->key) u = u->left;
    else u = u->right;
  }
  return u;
}

struct Node * treeSuccessor(struct Node *x){
  if(x->right != NIL) return treeMinimum(x->right);
  struct Node *y = x->parent;
  while(y != NIL && x == y->right){
    x = y;
    y = y->parent;
  }
  return y;
}

void treeDelete(struct Node *z){
  struct Node *y;
  struct Node *x;

  if(z->left == NIL || z->right == NIL) y = z;
  else y = treeSuccessor(z);

  if(y->left != NIL) x = y->left;
  else x = y->right;

  if(x != NIL) x->parent = y->parent;

  if(y->parent == NIL) root = x;
  else{
    if(y == y->parent->left) y->parent->left = x;
    else y->parent->right = x;
  }

  if(y != z) z->key = y->key;

  free(y);
}

void insert(int k){
  struct Node *y = NIL;
  struct Node *x = root;
  struct Node *z;

  z = (struct Node *)malloc(sizeof(struct Node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x != NIL){
    y = x;
    if(z->key < x->key) x = x->left;
    else x = x->right;
  }
  z->parent = y;
  if(y == NIL) root = z;
  else{
    if(z->key < y->key) y->left = z;
    else y->right = z;
  }
}

void inorder(struct Node *u){
  if(u == NIL) return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}

void preorder(struct Node *u){
  if(u == NIL) return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}

int main(){
  int n, i, x;
  char com[10];

  scanf("%d", &n);

  for(i = 0; i < n; i++){
    scanf("%s", com);
    if(com[0] == 'f'){
      scanf(" %d", &x);
      struct Node *t = find(root, x);
      if(t != NIL) printf("yes\n");
      else printf("no\n");
    }
    else if(com[0] == 'i'){
      scanf(" %d", &x);
      insert(x);
    }
    else if(com[0] == 'p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
    else if(com[0] == 'd'){
      scanf(" %d", &x);
      treeDelete(find(root, x));
    }
  }

  return 0;
}

Measured memory_bytes: 19364
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

int main(){
    int n;
    cin>>n;
    cout<<n/3<<endl;
    return 0;
}

Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
using ll=long long ;
int main()
{
    int n,ans=1e9;
    cin>>n;
    vector<int> a(n);
    int l=101,r=0;
    rep(i,n){
        cin>>a[i];
        l=min(l,a[i]);
        r=max(r,a[i]);
    }
    for(int i=l;i<=r;i++){
        int num=0;
        for(int j=0;j<n;j++){
            num+=(a[j]-i)*(a[j]-i);
        }
        ans=min(num,ans);
    }
    cout<<ans;
}

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

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

  ll N; cin >> N;
  ll X; cin >> X;
  ll M; cin >> M;

  if (N < 1e7) {
    ll x = X;
    ll ans = 0;
    for (ll i = 0; i < N; i++) {
      ans += x;
      x = (x * x) % M;
    }
    cout << ans << '\n';
    return 0;
  }


  vector<ll> A(2 * M + X, 0);
  vector<ll> ind(2 * M + X, -1);

  ll x = X;
  ll is, ie;

  A[0] = X;
  ind[X] = 0;
  for (ll i = 1; i < N; i++) {
    x = (x * x) % M;
    if (ind[x] >= 0) {
      A[i] = x;
      is = ind[x];
      ie = i;
      break;
    } else {
      A[i] = x;
      ind[x] = i;
    }
  }

  ll sum_start = 0, sum_set = 0;
  for (ll i = 0; i <= is; i++) {
    sum_start += A[i];
  }
  for (ll i = is + 1; i <= ie; i++) {
    sum_set += A[i];
  }

  ll m = (N - (is + 1)) / (ie - is);

  ll ans = 0;
  ans += sum_start;
  ans += sum_set * m;
  for (ll i = 0; i < N; i++) {
    ll index = i + is + (ie - is) * m + 1;
    if (index >= N) break;
    ans += A[i + is + 1];
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 7832
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		String[] input = sc.next().split("");
		if (input[2].equals(input[3]) && input[4].equals(input[5])) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 35584
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <limits>
#include <stack>
#include <queue>
#include <map>

using namespace std;

using ll = long long;
using ui = unsigned int;
const ll MOD = 1000000007;


//124
int main() {
	ll N, K;
	scanf("%lld %lld", &N, &K);

	char s[100010];
	scanf("%s", &s);

	vector<ll> state_length; //index0,2,4,...�͋t����

	int prev_state = 1; //�ŏ��������Ƃ�����index0��0������悤��
	ll length = 0;
	for (ll i = 0; i < N; i++) {
		char c = s[i];
		if (c == '0') {
			//��
			if (prev_state == 0) {
				length++;
			}
			else {
				state_length.push_back(length);
				length = 1;
				prev_state = 0;
			}
		}
		else {
			//�t
			if (prev_state == 1) {
				length++;
			}
			else {
				state_length.push_back(length);
				length = 1;
				prev_state = 1;
			}
		}
	}
	state_length.push_back(length);
	if (prev_state == 1) {
		state_length.push_back(0); //�Ō�͐��ŏI���悤��
	}
	else {
		state_length.push_back(0);
		state_length.push_back(0); //�Ō�͐��ŏI���悤��
	}

	ll state_length_size = (ll)state_length.size();
	ll window = std::min(state_length_size, 1 + K * 2);
	ll start = 0;
	ll end = window;
	ll sum = 0;
	for (int i = start; i < end; i++) {
		sum += state_length[i];
	}
	ll max = sum;

	while (true) {
		start += 2;
		end += 2;
		if (end >= state_length_size) {
			break;
		}

		sum -= state_length[start - 2];
		sum -= state_length[start - 1];
		sum += state_length[end - 2];
		sum += state_length[end - 1];

		if (sum > max) {
			max = sum;
		}
	}

	printf("%lld\n", max);

	return 0;
}


Measured memory_bytes: 1528
#include <cstdio>
#include <cctype>
#include <climits>
#include <vector>
#include <queue>
using namespace std;

#define si static inline
#define gcu getchar_unlocked
si int in() {
	int c, n = 0;
	bool minus = false;
	if ((c = gcu()) == '-') minus = true; else ungetc(c, stdin);
	while ((c = gcu()) >= '0' && c <= '9') n = 10 * n + (c - '0');
	//return n; }
	return minus ? -n : n; }
si void scan(char *s) {while (!isspace(*s++ = gcu()));}
#define pcu putchar_unlocked
#define svo si void out
template <typename T>
svo(T n) {
	static char buf[20];
	char *p = buf;
	//if(n < 0) pcu('-'), n *= -1;
	if (!n) *p++ = '0';
	else while (n) *p++ = n % 10 + '0', n /= 10;
	while (p != buf) pcu(*--p); }
svo(const char *s){while(*s)pcu(*s++);}
svo(char *s){while(*s)pcu(*s++);}
svo(char c){pcu(c);}
template <typename T>
//svo(vector<T> &v){for(T &x:v)out(' '),out(x);out('\n');}
svo(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);out('\n');}
template <typename head, typename... tail>
svo(head&& h, tail&&... t){out(h);out(move(t)...);}
#undef svo
#undef si

#define v vector
struct graph {
	struct node {int n, w;};
	v<v<node>> nodes;

	void read(int n) {
		nodes.resize(n);
		for (auto &x: nodes) {
			in();
			for (int k = in(); k--;) {
				int c = in();
				x.push_back({c, in()});
			}
		}
	}

	v<node> dks() {
		v<node> w(nodes.size(), {0, INT_MAX});
		w[0].w = 0;
		priority_queue<node> q;
		q.push({0, 0});
		while (!q.empty()) {
			node n = q.top();
			q.pop();
			if (w[n.n].n)
				continue;
			w[n.n].n = 1;
			for (node &x: nodes[n.n]) {
				w[x.n].w = min(w[x.n].w, n.w + x.w);
				q.push({x.n, w[x.n].w});
			}
		}
		return move(w);
	}
};

bool operator < (const graph::node &a, const graph::node &b) {
	return a.w > b.w;
}

int main() {
	graph g;
	g.read(in());
	int i = 0;
	for (auto &x: g.dks())
		out(i++, ' ', x.w, '\n');
}


Measured memory_bytes: 9180
X,Y,Z,V[4],E[51],A[51];double P0[51][4901],P1[51][4901],dp,sum;i,p,m,u,p0,p1,m1;main(){for(;scanf("%d%d%d",&X,&Y,&Z)*X;){memset(E,0,sizeof(E));memset(P0,0,sizeof(P0));memset(P1,0,sizeof(P1));for(i=0;i<X;i++)scanf("%d",V+i);for(P0[0][0]=1;Z--;E[p]=m,A[p]=u)scanf("%d%d%d",&p,&m,&u);for(u=1,p0=0;u;p0++){u=0;for(p=p0;p<Y;p++){for(m=0;m<=p*100;m++){if(P0[p][m]){dp=P0[p][m]/X;u=1;for(i=0;i<X;i++){p1=p+V[i];m1=m;if(p1>=Y){p1=Y;}else{if(E[p1]){if(E[p1]==1){p1+=A[p1];if(p1>=Y)p1=Y;}else if(E[p1]==2){m1+=A[p1];}else{m1-=A[p1];if(m1<0)m1=0;}}}P1[p1][m1]+=dp;}}}}memcpy(P0,P1,sizeof(*P0)*Y);memset(P1,0,sizeof(*P1)*Y);}sum=0;for(m=0;m<=4900;m++)sum+=P1[Y][m]*m;printf("%d\n",i=sum);}}

Measured memory_bytes: 4320
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)(b); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int D; //365
    cin >> D;

    int c[26];
    rep(i, 0, 26) {
        cin >> c[i];
    }

    int s[D][26];
    rep(i, 0, D) {
        rep(j, 0, 26) {
            cin >> s[i][j];
        }
    }

    int t[D] = {};
    srand(time(NULL));
    rep(i, 0, D) {
        t[i] = rand() % 26;
    }

    ll mx_score = -1;
    int cnt = 100000;
    while (cnt--) {
        srand(time(NULL));
        int d = rand() % 365;
        int q = rand() % 26;
        int old = t[d];
        t[d] = q;

        ll score[D] = {};
        vector<int> last_day(26, -1);
        rep(i, 0, D) {
            if (i != 0) score[i] = score[i - 1];
            score[i] += s[i][t[i]];
            last_day[t[i]] = i;
            int decrease = 0;
            rep(j, 0, 26) {
                decrease += c[j] * (i - last_day[j]);
            }
            score[i] -= decrease;
        }
        if (mx_score > score[D - 1]) {
            t[d] = old;
        } else {
            mx_score = score[D - 1];
        }
    }

    rep(i, 0, D) cout << t[i] + 1 << endl;
    return 0;
}


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

#define whole(f, x, ...)                                 \
  ([&](decltype((x)) whole) {                            \
    return (f)(begin(whole), end(whole), ##__VA_ARGS__); \
  })(x)

using namespace std;
using ll = int64_t;

const int mod = 1e9 + 7;

void solve() {
  int k, n;
  cin >> n >> k;

  auto sum = [](ll t) -> ll { return t * (t + 1) / 2; };

  ll cnt = 0;
  const ll sumall = sum(n);
  for (int i = k; i <= n; i++) {
    const ll ma = sumall - sum(n - i);
    const ll mi = sum(i - 1) % mod;
    cnt += ma - mi + 1 % mod;
  }
  ++cnt;

  cout << (cnt % mod) << endl;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);

  solve();
  return 0;
}


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

using namespace std;

#define int long long
#define endl '\n'
#define maxn 300010
const int MOD = 1000000007;

int n, k;
int bit[maxn];

int tree[4 * maxn], dp[maxn];

int doit(int a, int b) {
    return max(a, b);
}
int queryTree(int start, int end, int l, int r, int index = 1) {
    if (r < start or l > end)return 0;
    if (l <= start and r >= end)return tree[index];
    int mid = start + end >> 1;
    return doit(queryTree(start, mid, l, r, 2 * index), queryTree(mid + 1, end, l, r, 2 * index + 1));
}
void update(int start, int end, int x, int val, int index) {
    if (x < start or x > end)return;
    if (start == end) {
        tree[index] = val;
        return;
    }
    int mid = start + end >> 1;
    update(start, mid, x, val, 2 * index);
    update(mid + 1, end, x, val, 2 * index + 1);
    tree[index] = doit(tree[2 * index], tree[2 * index + 1]);
}

void solve() {
    cin >> n >> k;

    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
    dp[0] = 1;
    update(0, maxn - 1, v[0], 1, 1);
    for (int i = 1; i < v.size(); i++) {
        int lo = max(0ll, v[i] - k), hi = min((int) maxn - 10, v[i] + k);
        dp[i] = 1;
        dp[i] = max(dp[i], 1 + queryTree(0, maxn - 1, lo, hi, 1));
        update(0, maxn - 1, v[i], dp[i], 1);
    }
    cout << *max_element(dp, dp + n) << endl;
}

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

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}

Measured memory_bytes: 16192
public class Main{
	public static void main(String[] args){
		final int S = new java.util.Scanner(System.in).nextInt();
		int h = S / 3600;
		int m = S % 3600 / 60;
		int s = S % 3600 % 60;
		
		System.out.println(h + ":" + m + ":" + s);
	}
}

Measured memory_bytes: 26164
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mod 1000000007
#define h1 7897897897897897
#define h2 7897466719774591
#define b1 98762051
#define b2 98765431
#define inf 1000000000
#define pi 3.1415926535897932384626
#define LMAX 9223372036854775807
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pii>
#define SET(a, b) memset(a, b, sizeof(a));
#define all(x) (x).begin(), (x).end()
#define flush fflush(stdout)
#define debug printf("Hello\n")
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
int n, m, k, x, y, sum, cnt, ans;
vector<pair<int, ll> >edges[100005];
priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
ll w, dist[100005];
bool vis[100005];
int main () {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  FOR(i, 1, m) {
    cin >> x >> y >> w;
    edges[x].pb({y, w});
    //edges[y].pb({x, w});
  }
  FOR(i, 2, n) {
    edges[i].pb({i-1, 0});
  }
  FOR(i, 2, n) dist[i] = 1e15;
  pq.push({0, 1});
  while (!pq.empty()) {
    auto tmp = pq.top();
    pq.pop();
    int u = tmp.se;
    if (vis[u] || tmp.fi != dist[u]) continue;
    vis[u] = true;
    for (auto it: edges[u]) {
      if (dist[u] + it.se < dist[it.fi]) {
        dist[it.fi] = dist[u] + it.se;
        pq.push({dist[it.fi], it.fi});
      }
    }
  }
  if (dist[n] == 1e15) cout << "-1\n";
  else cout << dist[n] << endl;
  return 0;
}

Measured memory_bytes: 9464
#include "bits/stdc++.h"
using namespace std;
using namespace std;
typedef long long ll;
typedef vector<int> vi; 
typedef vector< vi > vvi; 
/////////////////////////
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define loop(i,a,b) for (int i = a; i < b; i++)
//////////////////////////
#define printvector(n) for(int i=0;i<n.size();i++){cout<<n[i]<<" ";}cout<<'\n'
#define printstack(n) for(int i=0;i<n.size();i++){cout<<n[i]<<" ";}cout<<'\n'
#define PI_val 3.14159265359
#define printpair(n) cout<<n.F<<" "<<n.S
#define printvop(n) loop(i,0,n.size()-1){printpair(n[i])<<endl;}
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define endl "\n"
long long int mod=1000000007;
//////////////////////////
int main()
{
    #ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("E:/codes/testcases/input.in", "r", stdin);
    // for writing output to output.txt
    freopen("E:/codes/testcases/output.in", "w", stdout);
    #endif
    ll t;
 	char s;
 	cin>>s;
 	if(islower(s)){
 		cout<<"a";
 	}   
 	else if(isupper(s)){
 		cout<<"A";
 	}


    return 0;
}



Measured memory_bytes: 3636
#include <stdio.h>

int main() {
  int X, verdict[4] = {0}; // AC, WA, TLE, RE
  scanf("%d", &X);

  for(int i = 0; i < X; i++) {
    char str[5];
    scanf("%s", str);
    switch(str[0]) {
      case 'A':
        verdict[0]++;
        break;
      case 'W':
        verdict[1]++;
        break;
      case 'T':
        verdict[2]++;
        break;
      case 'R':
        verdict[3]++;
        break;
    }
  }

  printf("AC x %d\n", verdict[0]);
  printf("WA x %d\n", verdict[1]);
  printf("TLE x %d\n", verdict[2]);
  printf("RE x %d\n", verdict[3]);
  return 0;
}

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

int main() {

    int N; // the length of a string S
    std::cin >> N;

    std::string S; // the string
    std::cin >> S;

    if (N % 2 == 1) {
        std::cout << "No" << std::endl;
        return 0;
    }

    std::string former = S.substr(0, N/2);
    std::string latter = S.substr(N/2, N/2);

    std::cout << (former.compare(latter) == 0 ? "Yes" : "No") << std::endl;

    return 0;

}


Measured memory_bytes: 3632
from math import ceil
N,H=list(map(int,input().split()))
a_max=0
b_list=[]
for _ in range(N):
    a,b=list(map(int,input().split()))
    a_max = max(a_max,a)
    b_list.append(b)
b_list = sorted(b_list,reverse=True)

ans=ceil(H/a_max)
bcount=0
for b in b_list:
    bcount+=1
    H=max(0,H-b)
    ans=min(ans,bcount+ceil(H/a_max))

print(ans)


Measured memory_bytes: 57432
def isok(arg):
    x = 0
    for i in a:
        if arg - i >= 0:
            if arg-i <= 10**5:
                x += cs[arg-i]
        else:
            x += n
    if x >= m:
        return True
    else:
        return False

def bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if isok(mid):
            ok = mid
        else:
            ng = mid
    return ok

n,m = map(int,input().split())
a = list(map(int,input().split()))
cs = [0]*(10**5+1)
for i in a:
    cs[i] += 1
for i in range(10**5):
    cs[10**5-i-1] += cs[10**5-i]
h = bisect(10**5*2+1,0)
count = 0
ans = 0
for i in a:
    num = max(0,h-i)
    if num <= 10**5:
        ans += 2*i*cs[num]
        count += cs[num]
ans -= (count-m)*h
print(ans)


Measured memory_bytes: 53656
//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("-Ofast","-funroll-all-loops","-ffast-math")
//~ #pragma GCC target ("avx2")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <random>
#include <cmath>
#include <chrono>
#include <cstring>
#include <string>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
using LL = long long;
#define eps 1e-8
#define fi first
#define se second
#define eb emplace_back
#define SZ(a) int(a.size())
#define ALL(x) (x).begin(),(x).end()
#define trav(a,x) for (auto& a: x)
#define LOG(FMT...) fprintf(stderr, FMT)
#define close std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define FOR(i, x, y) for (LL i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (LL i = (x), _##i = (y); i > _##i; --i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define CASET int ___T; cin>>___T; for(int __CS=1;__CS<=___T;__CS++)
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
mt19937 dlsrand(random_device{}());
mt19937 mrand(std::chrono::system_clock::now().time_since_epoch().count()); 
int rnd(int x) { return mrand() % x;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
LL bin(LL x, LL n, LL MOD) {LL ret = MOD != 1;for (x %= MOD; n; n >>= 1, x = x * x % MOD)if (n & 1) ret = ret * x % MOD;return ret;}
inline LL get_inv(LL x, LL p) { return bin(x, p - 2, p); }
const double PI = acos(-1.0);
constexpr int maxn = 1e6+10;
constexpr int mod = 1e9+7;
constexpr int INF = 0x3f3f3f3f;
constexpr ll linf = 0x3f3f3f3f3f3f3f3f;
constexpr ull base=2333, P_1=19260811, P_2=999998639;
void add(int &a,int b) {a+=b; if(a>=mod) a-=mod;}
void dec(int &a,int b) {a-=b; if(a<0) a+=mod;}
int main()
{
    int ans = 0;
    ll p = 100;    
    ll n;
    cin >> n;
    while(p < n){
        ll kp = p / 100;
        p+=kp;
        ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3172
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;

class UnionFindForest {
  std::vector<int> parent_;
  std::vector<int> rank_;
  std::vector<int> size_;

public:
  // Initialize forest.
  // parent_[i]=i, rank_[i]=0, size_[i]=1.
  UnionFindForest(const int &n);
  // Get the number of the root of the node q.
  int Root(const int &q);
  // Return true if the roots of x and y is same.
  bool IsSame(const int &x, const int &y);
  // Unite the tree x and tree y.
  void Unite(int x, int y);
  // Get the number of nodes which are the same group as node q.
  int Size(const int &q);
};
UnionFindForest::UnionFindForest(const int &n) {
  parent_.resize(n);
  rank_.resize(n);
  size_.resize(n);
  for (int i = 0; i < n; i++) {
    parent_[i] = i;
    rank_[i]   = 0;
    size_[i]   = 1;
  }
}
int UnionFindForest::Size(const int &q) {
  return size_[Root(q)];
}

int UnionFindForest::Root(const int &q) {
  if (parent_[q] == q) {
    return q;
  } else {
    return parent_[q] = Root(parent_[q]);
  }
}

bool UnionFindForest::IsSame(const int &x, const int &y) {
  return Root(x) == Root(y);
}

void UnionFindForest::Unite(int x, int y) {
  x = Root(x);
  y = Root(y);
  if (x == y) return;
  if (rank_[x] < rank_[y]) {
    parent_[x] = y;
    size_[y] += size_[x];
    size_[x] = 0;

  } else {
    parent_[y] = x;
    size_[x] += size_[y];
    size_[y] = 0;
    if (rank_[x] == rank_[y]) rank_[x]++;
  }
}

int main(void) {
  cout << std::fixed << std::setprecision(10);
  cin.tie(0);
  std::ios::sync_with_stdio(false);

  int n, m;
  cin >> n >> m;
  UnionFindForest uf(n);
  for (int i = 0; i < m; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    uf.Unite(x - 1, y - 1);
  }

  int result = 0;
  for (int i = 0; i < n; i++) {
    if (uf.Root(i) == i) {
      result++;
    }
  }
  cout << result << endl;

  return 0;
}


Measured memory_bytes: 1408
#![allow(unused_imports)]
#![allow(non_snake_case)]

use std::*;
use std::collections::*;
use std::ops::*;
use procon::*;

pub fn main() -> () {
    let (H, W, D) = {
        let xs = read_words::<usize>();
        (xs[0], xs[1], xs[2])
    };
    let mut A = make_vec(H, |_| make_vec(W, |_| 0));
    for y in 0..H {
        for (x, a) in read_words::<usize>().into_iter().enumerate() {
            A[y][x] = a - 1;
        }
    }

    let costs = {
        let HW = H * W;

        let distance =
            |(y1, x1): (i32, i32), (y2, x2): (i32, i32)| (y1 - y2).abs() + (x2 - x1).abs();

        let mut points = make_vec(HW, |_| (0, 0));
        for y in 0..H {
            for x in 0..W {
                points[A[y][x]] = (y as i32, x as i32);
            }
        }

        let mut costs = make_vec(HW, |_| 0i64);
        for i in 0..HW {
            costs[i] = if i < D {
                0
            } else {
                let d = distance(points[i], points[i - D]) as i64;
                costs[i - D] + d
            };
        }

        costs
    };

    let Q = read_line().parse::<usize>().unwrap();
    for _ in 0..Q {
        let (l, r) = {
            let xs = read_words::<usize>();
            (xs[0] - 1, xs[1] - 1)
        };
        let cost = costs[r] - costs[l];
        println!("{}", cost);
    }
    return;
}

pub mod procon {
    use std;
    use std::collections::*;
    use std::io;
    use std::mem;
    use std::str::FromStr;

    pub fn read_line() -> String {
        let mut buf = String::new();
        io::stdin().read_line(&mut buf).unwrap();
        buf.trim_right().to_owned()
    }

    pub fn read_words<T>() -> Vec<T>
    where
        T: std::str::FromStr,
        T::Err: std::fmt::Debug,
    {
        let mut buf = String::new();
        io::stdin().read_line(&mut buf).unwrap();
        buf.split_whitespace()
            .map(|word| T::from_str(word).unwrap())
            .collect()
    }

    pub fn read_vec(len: usize) -> Vec<String> {
        let mut vec = Vec::new();
        while vec.len() < len {
            let line = read_line();
            for word in line.split_whitespace() {
                vec.push(word.to_owned());
            }
        }
        assert!(vec.len() == len);
        vec
    }

    pub fn make_vec<T, F>(len: usize, f: F) -> Vec<T>
    where
        F: Fn(usize) -> T,
    {
        return (0..len).into_iter().map(f).collect();
    }
}


Measured memory_bytes: 7292
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
template <typename T> using V = vector<T>;

constexpr int Mod = 998244353;
constexpr int mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;

template <typename T> constexpr bool chmax(T &a, const T &b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <typename T> constexpr bool chmin(T &a, const T &b) {
    if(a <= b) return false;
    a = b;
    return true;
}

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

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

    int x, y, z;
    cin >> x >> y >> z;
    cout << z << " " << x << " " << y << endl;

    return 0;
}

Measured memory_bytes: 896
import java.util.*;
import java.lang.*;

public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		
		Scanner sc= new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int cost[] = new int[n];
		for(int i=0;i<n;i++){
		    cost[i] = sc.nextInt();
		}
		int dp[]=new int[n];
		for(int i=1;i<n;i++){
		    for(int j=1;j<=k;j++){
		        if (j==1){
		            dp[i] = dp[i-1]+Math.abs(cost[i]-cost[i-1]);
		        }
		        else {
		            if((i-j)>=0){
		                dp[i] = Math.min((dp[i-j]+Math.abs(cost[i-j]-cost[i])), dp[i]);
		            }
		            
		        }
		    }
		}
	    System.out.println(dp[n-1]);
		
	}
}

Measured memory_bytes: 50328
#include<iostream>
using namespace std;
int main(){
    int list[6]={};
    for(int i=0;i<6;i++){
        cin >> list[i];
        
    }
    int n=0;
    int a;
    string s;
    cin >> s;
    for(int i=0;i<s.size();i++){
        if(s[i]=='W'){
            a=list[0];
            list[0]=list[2];
            list[2]=list[5];
            list[5]=list[3];
            list[3]=a;
        }else if(s[i]=='S'){
            a=list[0];
            list[0]=list[4];
            list[4]=list[5];
            list[5]=list[1];
            list[1]=a;
        }else if(s[i]=='E'){
            a=list[0];
            list[0]=list[3];
            list[3]=list[5];
            list[5]=list[2];
            list[2]=a;
        }else if(s[i]=='N'){
            a=list[0];
            list[0]=list[1];
            list[1]=list[5];
            list[5]=list[4];
            list[4]=a;
        }
        }
        cout << list[0] << endl;

    }


Measured memory_bytes: 3176
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for(ll i = 0; i < (n); ++i )

using namespace std;
const long long INF = 1LL << 60;

string S;
ll C_0 = 0,C_1 = 0,sum = 0;
int main(){
  cin  >> S;
  rep(i,S.length()){
    if(S[i] == '0') C_0++;
    else C_1++;
  }
  sum = 2 * min(C_0,C_1);
  cout << sum << endl;
  return 0;
}


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

int main() 
{
	long long n, x;
	cin >> n;
	long long neg = 0, mini = int(1e9), sum = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> x;
		sum += abs(x);
		mini = min(mini, abs(x));
		if (x < 0) neg++;
	}
	
	if (neg % 2) sum -= 2*mini;
	cout << sum;
}

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

int main(){
    int n;
    double m;
    vector<int> a;
    cin>>n>>m;
    double sum=0;
    int temp=0;
    for(int i=0;i<n;i++){
        cin>>temp;
        a.push_back(temp);
        sum+=temp;
    }
    sort(a.begin(),a.end(),greater<int>());
    sum=sum/(4*m);
    for(int i=0;i<m;i++){
        if((double)a[i]<sum){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
    return 0;
}

Measured memory_bytes: 256
import Text.Printf

checkTiles :: Int -> Bool -> [Char] -> Int
checkTiles flip _ "" = flip
checkTiles flip True ('0' : rest) = checkTiles flip False rest
checkTiles flip False ('1' : rest) = checkTiles flip True rest
checkTiles flip True ('1' : rest) = checkTiles (flip + 1) False rest
checkTiles flip False ('0' : rest) = checkTiles (flip + 1) True rest

main = do
  (first:rest) <- getLine
  let fs = case first of
             '0' -> False
             '1' -> True
  let flipTiles = checkTiles 0 fs rest
  printf "%d\n" flipTiles

Measured memory_bytes: 4988
#include<iostream>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<vector>
#include<climits>
#define ll long long int
using namespace std;
int main(void) {
  string s;
  int n=0;
  cin>>s;
  for(auto i=s.begin(); i!=s.end(); i++) {
    if (*(i)=='+')
      n++;
    else
      n--;
  }
  cout<<n<<endl;;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N, M;
    cin >> N >> M;
    vector<int> A(M);
    int sum = 0;
    for (int i = 0; i < M; i++){
        cin >> A.at(i);
        sum += A.at(i);
    }
    if (sum > N) cout << "-1" << endl;
    else cout << N - sum << endl;
}

Measured memory_bytes: 3668
//Binary tree search 2

#include<stdio.h>
#include<stdlib.h>
#define N NULL

typedef struct node
{

  struct node *p, *l, *r;
  int w;

}*tree;

void prepare(tree *root, int w)
{
  (*root) = (tree)malloc(sizeof(struct node));
  (*root)->p = N;
  (*root)->l = N;
  (*root)->r = N;
  (*root)->w = w;
  
}

void ins(tree *root, tree imp)
{
  tree y = N;
  tree x = *root;

  while(x != N)
    {
      y = x;
      if(imp->w < x->w)
	{
	  x = x->l;
	} else {
	x = x->r;
      }
    }

  imp->p = y;


  if(y == N)
    {
      *root = imp;
    }
  else if(imp->w > y->w)
    {
      y->r = imp;
    }
  else y->l = imp;
}


tree find(tree root,int w)
{
  while(root != N && w != root->w)
    {
      if(w < root->w)
	{
	  root = root->l;
	}
      else root = root->r;
    }
  return root;
  }


void inorder(tree imp)
{
  if(imp != N)
    {
      inorder(imp->l);
      printf(" %d",imp->w);
      inorder(imp->r);
    }
}

void preorder(tree imp)
{
  if(imp != N)
    {
      printf(" %d",imp->w);
      preorder(imp->l);
      preorder(imp->r);
    }
}

void print(tree root)
{
  inorder(root);
  printf("\n");
  preorder(root);
  printf("\n");
}


int main()
{
  tree root, imp, f;

  root = N;

  int n,w,i;
  char arr[10];

  //input data
  scanf("%d",&n);
  for(i = 0; i < n; i++)
    {
      scanf("%s",arr);

      if(arr[0] == 'i')
	{
	  scanf("%d",&w);

	  prepare(&imp,w);

	  ins(&root,imp);
	}


      if(arr[0] == 'p')
	{	  
	  print(root);
	 
	}
      
      if(arr[0] == 'f')
	{
	  scanf("%d",&w);

	  f = find(root,w);

	  if(f != N)
	    {
	     
	      printf("yes\n");
	    }
	  else printf("no\n");
	}

    }

  return 0;
}





Measured memory_bytes: 20468
#include <iostream>

int main(){
  int x[5], k;
  for(int i = 0; i < 5; i++) std::cin >> x[i];
  std::cin >> k;

  int ret = 0;
  bool can = true;
  if(k < (x[4] - x[0])){
      can = false;
  }

  if(can) std::cout << "Yay!" << std::endl;
  else std::cout << ":(" << std::endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <float.h>
#include <iomanip>
#include <iostream>
using namespace std;

int main(){
    
    int N,L[110]={},s=0,m=0,f=1;

    cin >> N;

    for(int i=1;i<=N;i++){
        cin >> L[i];
        if(m<L[i]){
            m=L[i];
        }
        s+=L[i];
    }

    s-=m;

    if(m<s){
        cout << "Yes"<<endl;
    }else{
        cout << "No"<<endl;
    }


    return 0;

}

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

int top, S[1000];

void push(int x)
{
  S[++top] = x;
}

int pop()
{
  //top--;
  //return S[top+1];
  return S[top--];
}

int main()
{
  int a,b;
  top = 0;
  char s[100];
  while(scanf("%s", s) != EOF)
  {
    if(s[0] == '+')
    {
      a = pop();
      b = pop();
      push(a+b);
    }
    else if(s[0] == '-')
    {
      b = pop();
      a = pop();
      push(a-b);
    }
    else if(s[0] == '*')
    {
      a = pop();
      b = pop();
      push(a*b);
    }
    else push(atoi(s));
  }

  printf("%d\n", pop());

  return 0;
}



Measured memory_bytes: 2056
def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        temp = [int(a) for a in input().split()]
        A.append(temp)
        # print(temp)

    isHold = False
    cur = [0, 0]
    ops = []
    for i in range(H):
        if i % 2 == 0: start, end, dir = 0, W, 1
        else: start, end, dir = W-1, -1, -1
        for j in range(start, end, dir):
            if A[i][j] % 2 == 0:
                if isHold:
                    ops.append([cur[0]+1, cur[1]+1, i+1, j+1])
                    cur = [i, j]
            else:
                if not isHold:
                    isHold = True
                    cur = [i, j]
                else:
                    ops.append([cur[0]+1, cur[1]+1, i+1, j+1])
                    cur = [i, j]
                    isHold = False
    print(len(ops))
    if len(ops) > 0:
        for op in ops:
            print(" ".join(map(str, op)))

if __name__ == '__main__':
    main()

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

int main() {
  string S;
  cin >> S;
  string T = S;
  
  int N = S.length();
  reverse(T.begin(), T.end());
  string S_mae = S.substr(0,(N-1)/2);
  string S_ato = S.substr((N+3)/2 -1);
  
  bool jouken1=0, jouken2=0, jouken3=0;
  
  if (S == T) jouken1 = 1; 
  if (S_mae == T.substr((N+3)/2 -1)) jouken2 = 1;
  if (S_ato == T.substr(0,(N-1)/2)) jouken3 = 1;
  
  if (jouken1 && jouken2 && jouken3) cout << "Yes" << endl;
  else cout << "No" << endl;
}


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

int main() {
	int N;
	long long a[200010];
 
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		a[i] -= i + 1;
	}
 
	sort(a, a + N);
 
	long long mid = a[N / 2];
	long long ans = 0;
 
	for (int i = 0; i < N; i++) {
		ans += abs(mid - a[i]);
	}
 
	cout << ans << endl;
 
	return 0;
}

Measured memory_bytes: 1792
N = int(input())
A = list(map(int, input().split()))
B = [i for i in A if i % 2 == 0]
o = 'APPROVED'
for i in B:
	if i % 3 != 0 and i % 5 != 0:
		o = 'DENIED'
		break
print(o)

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

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

using namespace std;
using ll = long long;

const int NIL = -1;

struct Node {
    int id, parent, lchild, rsibling, depth;
    Node(): id(NIL), parent(NIL), lchild(NIL), rsibling(NIL) {}
};

struct Tree {
    vector<Node> nodes;
    int id_root;
    Tree(int n): nodes(vector<Node>(n)), id_root(NIL) {}

    Node& at(int i) {
        return nodes[i];
    }
    void get_root() {
        id_root = 0;
        while(nodes[id_root].parent != NIL) id_root = nodes[id_root].parent;
        nodes[id_root].depth = 0;
    }
    void set_depth_(int i) {
        if(nodes[i].lchild != NIL) {
            nodes[nodes[i].lchild].depth = nodes[i].depth + 1;
            set_depth_(nodes[i].lchild);
        }
        if(nodes[i].rsibling != NIL) {
            nodes[nodes[i].rsibling].depth = nodes[i].depth;
            set_depth_(nodes[i].rsibling);
        }
    }
    void set_depth() {
        get_root();
        set_depth_(id_root);
    }
    void print() {
        for(Node node: nodes) {
            printf("node %d: parent = %d, depth = %d, ", node.id, node.parent, node.depth);
            if(node.parent == NIL) printf("root");
            else if(node.lchild == NIL) printf("leaf");
            else printf("internal node");
            printf(", [");
            int id_child = node.lchild;
            while(id_child != NIL) {
                printf("%d", id_child);
                id_child = nodes[id_child].rsibling;
                if(id_child != NIL) printf(", ");
            }
            printf("]\n");
        }
    }
};

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

    int n, id, k, c, c_bfr;
    cin >> n;
    Tree tree(n);
    rep(i, n) {
        cin >> id >> k;
        tree.at(id).id = id;
        rep(j, k) {
            cin >> c;
            if(j == 0) tree.at(id).lchild = c;
            else tree.at(c_bfr).rsibling = c;
            tree.at(c).parent = id;
            c_bfr = c;
        }
    }

    tree.set_depth();
    tree.print();

    return 0;
}


Measured memory_bytes: 4992
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC target ("avx,avx2,tune=native")
#pragma GCC optimization ("unroll-loops")
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define len(v) ((int)v.size())
#define all(v) v.begin(), v.end()
#define oset tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define orz ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);    
#define inp freopen("input.txt","r",stdin);freopen("out.txt","w",stdout); 
ll mod=1e9+7;
void io(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);    
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
}
const int N=2e5+5;
int a[N],v[N];
int main() {
    //io();
    int i,j;
    int n;
   
   string s;
   cin>>s;
   if(s=="Sunny")	cout<<"Cloudy";
  	else if(s=="Cloudy") cout<<"Rainy";
  else	cout<<"Sunny";
   
   
}
 

 

Measured memory_bytes: 256
class SegmentTree:
  def __init__(self, size, default, op = max):
    self.size = 2**size.bit_length()
    self.dat = [default]*(self.size*2)
    self.op = op

  def update(self, i, x):
    i += self.size
    self.dat[i] = x
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

  def add(self, i, x):
    i += self.size
    self.dat[i] = self.op(self.dat[i], x)
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i], x)

  def get(self, a, b = None):
    #indexがaからbまでの要素についてopの結果をｇｅｔしたい場合は.get(a,b+1)とする。
    if b is None:
      b = a + 1
    l, r = a + self.size, b + self.size
    res = None
    while l < r:
      if l & 1:
        if res is None:
          res = self.dat[l]
        else:
          res = self.op(res, self.dat[l])
        l += 1

      if r & 1:
        r -= 1
        if res is None:
          res = self.dat[r]
        else:
          res = self.op(res, self.dat[r])
      l >>= 1
      r >>= 1
    return res

n,k = map(int,input().split())
a = []
for i in range(n):
  a.append(int(input()))
mxa = max(a)
s = SegmentTree(mxa+1,0)
for i in range(n):
  x = s.get(max(0,a[i]-k),min(mxa,a[i]+k)+1)
  s.update(a[i],x+1)
print(s.get(0,mxa+1))


Measured memory_bytes: 127508
N=input()
S=[]
for i in range(len(N)):
    S.append(int(N[i]))

T=sum(S)

if int(N)<10:
    print(N)
elif 9*(len(S)-1)+S[0]-1 >= T:
    print(9*(len(S)-1)+S[0]-1)
elif S[-1]==9: print(T)
elif S[0]==9: print(9*len(S))


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define floop(i,a,n) for (ll i=a;i<n;i++)
#define rfloop(i,a,n) for (ll i=n-1;i>=a;i--)
#define mloop(it,x) for(it=x.begin();it!=x.end();it++)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((ll)(x).size())
#define cases ll t; cin>>t; while(t--)
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef long long ll;
typedef unsigned long long int ull;
typedef vector<ll> vec;
typedef pair<ll,ll> pll;
typedef double db;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const ll mod=998244353;
ll pm(ll x,ll n) {ll result=1; while(n>0){if(n%2==1) result=((result%mod)*(x%mod))%mod; x=((x%mod)*(x%mod))%mod; n/=2;} return result;}
ll p(ll x,ll n) {ll result=1; while(n>0){if(n%2==1) result=result*x; x=x*x; n/=2;} return result;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll ncr(ll n,ll r) { ll p=1,k=1; if(n-r<r) r=n-r; if(r!=0) {while(r!=0) {p*=n; k*=r; ll temp=gcd(p,k); p/=temp; k/=temp; n--; r--;} } else p=1; return p;}
ll factorial[300000+1];
void fact(ll n) { factorial[0]=1; factorial[1]=1; floop(i,2,n+1) factorial[i] = (i * factorial[i-1]%mod) % mod; }
ll d,coeff1,coeff2; 
void euclid(ll a, ll b) { if(b==0) { d=a; coeff1=1; coeff2=0; } else { euclid(b,a%b); ll temp=coeff1; coeff1=coeff2; coeff2=temp-(a/b)*(coeff2); } }
ll modinv(ll a) { euclid(a,mod); return (coeff1%mod+mod)%mod; }
int prime[1000001]={};
int spf[1000001]={};
void sieve(ll n)
{
	prime[0]=1;
	prime[1]=1;
	for(ll i=2;i*i<=n;i++)
	{
		if(prime[i]==0)
		{
			for(ll j=i*i;j<=n;j+=i)
			{
				prime[j]=1;	
				if(spf[j]==j)
				spf[j]=i;	
			}		
		}
	}
}
/*
vec s(300000,0);
vec si(300000,1);
ll root(ll a)
{
	while(s[a]!=a)
	a=s[a];
	return a;
}
void uni(ll a,ll b)
{
	ll r1=root(a);
	ll r2=root(b);
	if(si[r1]<si[r2])
	{
		s[r1]=s[r2];
		si[r2]+=si[r1];
	}
	else
	{
		s[r2]=s[r1];
		si[r1]+=si[r2];
	}
}
vector<vec > adj(300000);
vec vis(300000,0);
vec dist(300000,0);
void dfs(ll t,ll n)
{
	vis[t]=1;
	floop(i,0,sz(adj[t]))
	{
		if(vis[adj[t][i]]==0)
		{
			dist[adj[t][i]]=dist[t]+1;
			vis[adj[t][i]]=1;
		//	sum[adj[t][i]]=sum[t]+c[t][adj[t][i]];
			dfs(adj[t][i],n);
		}
	}
}*/
struct my_comp
{
	bool operator()(pair<ll,pll> p1, pair<ll,pll> p2)
	{
		if(p1.fi!=p2.fi)
		return p1.fi>p2.fi;
		return p1.se.fi<p2.se.fi;
	}
};
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);	
int main()
{
	ll n,k;
	cin>>n>>k;
	vec l(n),r(n);
	floop(i,0,k)
	cin>>l[i]>>r[i];
	vec dp(n+5,0);
	dp[1]=1;
	vec pre(n+5,0);
	pre[1]=1;
	floop(i,2,n+1)
	{
		floop(j,0,k)
		{
			
			ll left=l[j];
			ll right=min(r[j],i-1);
			if(i<=l[j])
			continue;
			dp[i]=((dp[i]+pre[i-left]-pre[i-right-1])%mod+mod)%mod;
		}
		pre[i]=((pre[i-1]+dp[i])%mod+mod)%mod;
	}
	cout<<dp[n]<<"\n";
	return 0;
}

Measured memory_bytes: 9600
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<set>
#include<stack>
#include<sstream>
//#include <Eigen/Dense>
//#include <Eigen/Geometry>
//using namespace Eigen;
using namespace std;

const int maxn = 2005;
int a[maxn];
int p[maxn];
long long dp[maxn][maxn];
int n;
long long dfs(int start,int end,int cur)
{
	if (start > end || end < start)
		return 0;
	if (dp[start][end] != 0)
		return dp[start][end];
	long long cost1 = 1LL*a[p[cur]] * abs(p[cur] - start) + dfs(start + 1, end, cur + 1);
	long long cost2 = 1LL*a[p[cur]] * abs(p[cur] - end) + dfs(start, end - 1, cur + 1);

	dp[start][end] = max(cost1, cost2);
	return dp[start][end];
}
int main()
{
	
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < n; i++)
		p[i] = i;
	sort(p, p + n, [&](int i, int j) {return a[i] > a[j]; });

	cout << dfs(0, n - 1, 0) << endl;
	

	return 0;
}


Measured memory_bytes: 26388
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }


int main(){
    int a, b, c;
    cin>>a>>b>>c;
    if(a==b&&b==c){
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep2(i,n) for(int i=0;i<=n;i++)
#define repr(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define uni(e) e.erase(unique(e.begin(),e.end()),e.end())
#define double long double
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; }
int INF=1e10;
int MOD=1e9+7;
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
int keta(int a){
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
}
int kurai(int a,int b){
  int m=pow(10,b),n=pow(10,b-1);
  return (a%m)/n;
}
int ketawa(int a){
  int k=0;
  rep(i,keta(a)){
  k+=kurai(a,i+1);
  }
  return k;
}
int gcd(int a,int b){
  if(a%b==0)
    return b;
  return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
int mid(int a,int b,int c){
  vector<int> k(3);
  k[0]=a;k[1]=b;k[2]=c;
  sort(all(k));
  return k[1];
}
bool sosuu(int a){
  bool b=1;
  if(a<=1)
    return 0;
  else{
  rep1(i,sqrt(a)-1){
  if(a%(i+1)==0)
  b=0;
  }
  return b;
  }
}
int modpow(int a,int b,int m=MOD){
	if(!b)return 1;	if(b&1)return modpow(a,b-1,m)*a%m;
	int memo = modpow(a,b>>1,m);
	return memo*memo%m;
}
int fact_mod(int n) {
    int f=1; 
for(int i=2;i<n+1;i++) f=f*(i%MOD)% MOD;
    return f;
}
int mod_pow(int x,int n) {
    int res=1;
    while(n>0){
        if(n&1) res=(res*x)%MOD; 
        x=(x*x)%MOD;        
n>>=1; 
    }
    return res;
}
int c_mod(int n, int r) {
    if(r>n-r) r=n-r;
    if(r==0) return 1;
    int a=1;
    rep(i,r) 
a=a*((n-i)%MOD)%MOD;
    int b=mod_pow(fact_mod(r), MOD-2);
    return (a%MOD)*(b%MOD)%MOD;
}
signed main(){
  int a;
  cin>>a;
  vector<int> b(a),c(1000010,0);
  rep(i,a)
    cin>>b[i];
  rep(i,a){
  c[b[i]]+=1;
  }
  if(c[1]==0){
  int d=0;
  rep(i,a){
  int e=1;
  rep(j,sqrt(b[i])+0.1){
    if(j==0){
    if(c[b[i]]>1){
    e=0;
      break;
    }
      
    }
    else{
      if(b[i]!=2&&b[i]!=3){
  if(b[i]%(j+1)==0){
  if((c[j+1])||(c[b[i]/(j+1)])){
  e=0;
    break;
    }
  }
        }
      }
  }
    d+=e;
  }
  out(d);
    }
  else if(c[1]==1)
    out(1);
  else
    out(0);
}


Measured memory_bytes: 12652
fun main() {
    println(function(rint(), rl()))
}

fun function(N: Int, S: String): Long {
    val R = S.count { it == 'R' }
    val G = S.count { it == 'G' }
    val B = S.count { it == 'B' }
    var sum = R.toLong() * G * B
    if (sum == 0L) return 0L
    val max = (N+1)/2
    for (size in 1 until max) {
        for (i in 0 until N - size * 2) {
            val si = S[i]
            val sj = S[i + size]
            val sk = S[i + size * 2]
            if (si != sj && sj != sk && sk != si) {
                sum--
            }
        }
    }
    return sum
}

fun rl() = readLine()!!
fun rsp() = readLine()!!.split(" ")
fun rint() = readLine()!!.toInt()
fun rspint() = readLine()!!.split(" ").map { it.toInt() }

Measured memory_bytes: 36068
#include <bits/stdc++.h>
#define dum(x) cout<<#x<<'='<<x<<endl
#define ll long long
using namespace std;

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v.at(i);
  }

  sort(v.begin(), v.end());
  int h = 1000000000;
  int p = -1;
  for (int i = 0; i < n - k + 1; i++) {
    int tmp = v.at(i + k - 1) - v.at(i);
    if (h > tmp) {
      h = tmp;
      p = i;
    }
  }
  cout << v.at(p + k - 1) - v.at(p);
}


Measured memory_bytes: 640