akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VL = vector<LL>;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define F first
#define S second
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define FILL(a, b) memset(a, b, sizeof(a))

void dout() { cerr << endl; }

template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

const LL INF = (LL)1e18 + 47;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<VL> a(n, VL(n));
    vector<tuple<LL, LL, LL>> edges;
    FOR(i, 0, n)
    {
        FOR(j, 0, n)
        {
            cin >> a[i][j];
            if (i < j)
                edges.EB(a[i][j], i, j);
        }
    }
    bool ok = true;
    FOR(k, 0, n)
    {
        FOR(i, 0, n)
        {
            FOR(j, 0, n)
            {
                if (a[i][k] + a[k][j] < a[i][j])
                    ok = false;
            }
        }
    }
    if (!ok)
    {
        cout << -1;
        return 0;
    }
    LL ans = 0;
    sort(ALL(edges));
    vector<VL> f(n, VL(n, INF));
    FOR(i, 0, n) f[i][i] = 0;
    for (auto& e : edges)
    {
        LL d, u, v;
        tie(d, u, v) = e;
        if (d < f[u][v])
        {
            f[u][v] = d;
            ans += d;
            FOR(i, 0, n)
            {
                FOR(j, 0, n)
                {
                    f[i][j] = min({f[i][j], f[i][u] + f[v][j] + d, f[i][v] + f[u][j] + d});
                }
            }
        }
    }
    cout << ans;
    return 0;
}

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

ll ruijo(ll x, ll n){
	if(n == 0)return 1;
    if(n%2 == 0)return ruijo(x*x%mod ,n/2)%mod;
	return x * ruijo(x*x%mod ,n/2)%mod;
}

int main(){
	ll n,k; cin >> n >> k;
	vl ans(k);
	for(ll i = k-1;i>=0;i--){
		ans[i] = ruijo(k/(i+1),n);
		for(ll j = 2*i+1;j<k;j += (i+1)){
			ans[i] -= ans[j];
		}
	}
	ll sum = 0;
	rep(i,k){
		sum += ans[i]*(i+1);
		sum %= mod;
	}
	if(sum < 0)sum += mod;
	cout << sum << endl;
} 

Measured memory_bytes: 3948
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <tuple>
#include <utility>
#include <vector>
#define ll long long
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl
#define COYE cout<<"YES"<<endl
#define COYe cout<<"Yes"<<endl
#define COye cout<<"yes"<<endl
#define CONO cout<<"NO"<<endl
#define CONo cout<<"No"<<endl
#define COno cout<<"no"<<endl
#define FORE(i,a) for(auto &i:a)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define PB push_back
#define MP make_pair
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define EACH(V,i) for(typeof((V).begin()) i=(V).begin();i!=(V).end();++i)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MAX 5100000
using namespace std;
using Edge=pair<ll,ll>;
using Graph=vector<vector<int>>;
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T>inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
  ll N,P,ans=0;
  string S;
  cin>>N>>P>>S;
  
  ll RUI[200010],X[200010];
  RUI[0]=1;
  X[0]=0;
  RREP(i,200009){
    RUI[i]=RUI[i-1]*10%P;
    X[i]=0;
  }
  
  if(P==2 || P==5){
    REP(i,S.size()){
      if((S[i]-'0')%P==0) ans+=i+1;
    }
    cout<<ans<<endl;
  }
  else{
    for(int i=1; i<=S.size(); ++i){
      X[i]=(X[i-1]+(S.at(S.size()-i)-'0')*RUI[i-1])%P;
    }
    
    ll ANS[P];
    REP(i,P) ANS[i]=0;
    for(int i=0; i<=S.size(); ++i) ANS[X[i]]++;
    
    REP(i,P)  if(ANS[i]>1) ans+=ANS[i]*(ANS[i]-1)/2;
    cout<<ans<<endl;
  }
  return 0;
}

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

#define REP(i, start, count) for(int i=(start); i<(int)(count); ++i)
#define rep(i, count) REP(i, 0, count)
#define ALLOF(c) (c).begin(), (c).end()

typedef long long ll;
typedef unsigned long long ull;

int N;
vector<int> A;

int main(void) {
    cin >> N;
    A.assign(N, 0);
    rep(i, N) cin >> A[i];

    sort(ALLOF(A));
    vector<ll> Asums(N, 0);
    Asums[0] = A[0];
    REP(i, 1, N) {
        Asums[i] = Asums[i - 1] + A[i];
    }


    int ans = 0;
    for(int i = 0; i < N; ++i) {

        ll size = Asums[i];
        bool flag = false;
        auto beg_itr = A.begin() + i + 1;
        while(true) {
            // 条件を満たさない最初のidx
            auto itr = upper_bound(beg_itr, A.end(), size * 2);

            if (itr == A.end()) {
                flag = true;
                break;
            } 
            if (itr == beg_itr) {
                flag = false;
                break;
            }

            itr--;
            size = Asums[distance(A.begin(), itr)];
            beg_itr = itr + 1;
        }

        if (flag) {
            ans = N - i;
            break;
        }


    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1408
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True


def main():
    X = LI()

    for i in range(len(X)):
        if X[i] == 0:
            print(i+1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 10012
#include <bits/stdc++.h>
//For ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define MOD 1000000007
#define test int t; cin>>t; while(t--)
#define init(arr,val) memset(arr,val,sizeof(arr))
#define loop(i,a,b) for(int i=a;i<b;i++)
#define loopr(i,a,b) for(int i=a;i>=b;i--)
#define loops(i,a,b,step) for(int i=a;i<b;i+=step)
#define looprs(i,a,b,step) for(int i=a;i>=b;i-=step)
#define ull unsigned long long int
#define ll long long int
#define P pair
#define PLL pair<long long, long long>
#define PII pair<int, int>
#define PUU pair<unsigned long long int, unsigned long long int>
#define L list
#define V vector
#define D deque
#define ST set
#define MS multiset
#define M map
#define UM unordered_map
#define mp make_pair
#define pb push_back
#define pf push_front
#define MM multimap
#define F first
#define S second
#define IT iterator
#define RIT reverse_iterator
#define FAST ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define FILE_READ_IN freopen("input.txt","r",stdin);
#define FILE_READ_OUT freopen("output.txt","w",stdout);
#define all(a) a.begin(),a.end()
#define ld long double
using namespace std;
const ll N = 3e6;
const ll inf = 1e9;
const double pi = acos(-1);
map<PLL,ll> dp;
ll moves(ll x, ll y){
   if(x == 0 && y == 0)return 1;
   if(x < 0 || y < 0)return 0;
   if(dp.find(mp(x,y)) == dp.end()){
      dp[mp(x,y)] = (moves(x-2,y-1) + moves(x-1,y-2))%MOD;
   }
   return dp[mp(x,y)]%MOD;
}
ll power(ll a, ll n){
   if(n == 0)return 1;
   if(n == 1)return a%MOD;
   ll p = power(a,n/2);
   p*=p;
   p%=MOD;
   if(n & 1)p*=a;
   p%=MOD;
   return p;
}
int main(){
 FAST
   V<ll> arr(N);
   V<ll> rarr(N);
   arr[0] = 1;
   rarr[0] = 1;
   arr[1] = 1;
   rarr[1] = 1;
   for(ll i = 2; i < arr.size(); ++i){
      arr[i]=arr[i-1]*i;
      arr[i]%=MOD;
      rarr[i] = rarr[i-1]*power(i,MOD-2);
      rarr[i]%=MOD;
   }
   ll x,y;
   cin >> x >> y;
   ll ans = 0;
   ll z = 0;
   while(z*3 <= x && z*3 <= y){
      ll right = z;
      ll up = z;
      ll rem_right = x-z*3;
      ll rem_up = y-z*3;
      if(rem_right*2 == rem_up){
         up+=rem_right;
         ll tmp = arr[up+right];
         tmp*=rarr[up];
         tmp%=MOD;
         tmp*=rarr[right];
         tmp%=MOD;
         ans+=tmp;
         ans%=MOD;
      }else if(rem_up*2 == rem_right){
         right+=rem_up;
         ll tmp = arr[up+right];
         tmp*=rarr[up];
         tmp%=MOD;
         tmp*=rarr[right];
         tmp%=MOD;
         ans+=tmp;
         ans%=MOD;
      }
      z++;
   }
   cout << ans;
   return 0;
}

Measured memory_bytes: 47232
#include <bits/stdc++.h>
using i64 = long long;

int main() {
    int n, q;
    std::cin >> n >> q;
    std::vector<std::pair<int, std::pair<int, int>>> v;
    for (int i = 0; i < n; i++) {
        int a, b, c;
        std::cin >> a >> b >> c;
        v.push_back({ c, { a - c, b - c } });
    }
    std::sort(v.begin(), v.end());
    std::set<std::pair<int, int>> d;
    for (int i = 0; i < q; i++) {
        int in;
        std::cin >> in;
        d.emplace(in, i);
    }
    std::vector<int> ret(q, -1);
    for (int i = 0; i < n; i++) {
        auto it = d.lower_bound(std::make_pair(v[i].second.first, 0));
        while (it != d.end() && it->first < v[i].second.second) {
            ret[it->second] = v[i].first;
            it = d.erase(it);
        }
    }
    for (const auto e : ret) std::cout << e << std::endl;

    return 0;
}


Measured memory_bytes: 14448
#include <iostream>

using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    
    long long int count=0;
    int a, b=K+1;
    while(b<=N) {
        a = K;
        // cout << "b = " << b << endl;
        // cout << count << " -> ";
        if(K==0) {
            count += N;
        } else {
            if(b-a-1>(N-a)%b) {
                count += ((N-a)/b+1)*((N-a)%b+1);
                count += ((N-a)/b)*((b-a)-(N-a)%b-1);
            } else {
                count += ((N-a)/b+1)*(b-a);
            }
        }
        // cout << count << endl;
        // while(a<b) {
        //     if(a==0) {
        //         count += (N-a)/b;
        //     } else {
        //         count += (N-a)/b+1;
        //     }
        //     a++;
        // }
        
        b++;
    }
    
    cout << count << endl;
    
    return 0;
    
}

Measured memory_bytes: 256
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <iomanip>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> P;
const ll MOD=1000000007;
const ll MAX_N=500010;
const ll INF=999999999999;

int main(){
    ll k,n;
    cin>>k>>n;
    vector<ll> a(n);
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    ll dis=k-a[n-1]+a[0];
    for(ll i=1;i<n;i++){
        dis=max(dis,a[i]-a[i-1]);
    }
    cout<<k-dis<<endl;
}

Measured memory_bytes: 4832
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define pb push_back
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using vst=vector<string>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };


int main(){cout<<fixed<<setprecision(10);
		   int n,k;
           cin>>n>>k;
           vin l(n);
           rep(i,0,n)cin>>l[i];
           sort(all(l));reverse(all(l));
           int ans=0;
           rep(i,0,k){
             ans+=l[i];

           }
           cout<<ans<<endl;
}

Measured memory_bytes: 3640
n = gets.to_i

cons = {}

n.times{ |i|
	cons[i+1] = []

	a = gets.to_i
	a.times{
		x, y = gets.split.map &:to_i
		y = (y == 1)
		cons[i + 1] << [x, y]
	}
}

max = 0

tf = [true,false]
tf_s = tf

(n-1).times {
	tf_s = tf_s.product(tf)
}

if n > 1 then
	tf_s = tf_s.map{ |x| x.flatten}
else
	tf_s = [[true],[false]]
end

tf_s.each{ |tf_e|
	flag = true
	count = 0
	tf_e.each_with_index{ |tf_ee, i|
		if tf_ee then
			count += 1
			
			cons[i+1].each{ |cons_e|
				if tf_e[cons_e[0] - 1] != cons_e[1] then
					flag = false
					break
				end
			}
		end
#		break if ! flag
	}
	
	if flag then
		puts count
		exit
	end
}

puts 0


Measured memory_bytes: 22808
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const long long INF = 1e15;

#include <math.h>
#define PI 3.14159265358979323846264338327950L

int mxN = 50000000;
vector<int> cnt(mxN + 1);

int main() {
    int n, m;
    cin >> n >> m;
    int mn= mxN, mx = 0;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        mx = max(x, mx);
        mn = min(y, mn);
    }
    int ans = mn - mx + 1;
    if (ans <= 0) {
        cout << 0;
    }
    else {
        cout << ans;
    }

    return 0;
}

Measured memory_bytes: 198432
n = gets.to_i
a = gets.chomp
b = gets.chomp
c = gets.chomp

count = 0
n.times do |i|
  # same
  if a[i] == b[i] && b[i] == c[i]
    next
  end

  # only c
  if a[i] == b[i]
    count += 1
    next
  end

  # only b
  if a[i] == c[i]
    count += 1
    next
  end

  # only a
  if b[i] == c[i]
    count += 1
    next
  end

  count += 2
end

puts count


Measured memory_bytes: 1788
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	ar := make([]int, n+2)
	ar[0] = 0
	for i := 1; i <= n; i++ {
		fmt.Scan(&ar[i])
	}
	ar[n+1] = 0

	sr := make([]int, n+2)
	sr[0] = 0
	for i := 1; i < n+2; i++ {
		sr[i] = sr[i-1] + abs(ar[i-1]-ar[i])
	}
	sr[len(sr)-1] = sr[len(sr)-2] + abs(ar[len(ar)-2])

	for i := 1; i <= n; i++ {
		v := sr[i-1] + (sr[n+1] - sr[i+1]) + (abs(ar[i-1] - ar[i+1]))
		fmt.Println(v)
	}
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}


Measured memory_bytes: 6528
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
ll a,b,c,ret;
int main()
{
	scanf("%lld%lld%lld",&a,&b,&c);
	if(a%2==0||b%2==0||c%2==0)
		printf("0\n");
	else
	{
		ret=min(a*b,min(a*c,b*c));
		printf("%lld\n",ret);
	}
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

int main(){
	int a[3];
	while(~scanf("%d %d %d", &a[0], &a[1], &a[2])){
		int m = 3;
		for(int i = 0; i < 2; i++)
			for(int j = i + 1; j < 3; j++)
				if(a[i] == a[j]) m--;
		if(!m) cout << m + 1 << endl;
		else cout << m << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;(i)--)
#define rrep1(i,n) for(int i=((int)(n));i>0;(i)--)
#define sz(c) ((int)(c).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> P;
typedef pair<int, pair<int, int> > PP;
//const int MAX=;


void input(){

}

void solve(){

}

void output(){
  
}

int main(){
  int N;
  cin>>N;
  if(N<=9)cout<<N;
  else if(N<=99)cout<<9;
  else if(N<=999)cout<<N-90;
  else if(N<=9999)cout<<909;
  else if(N<=99999)cout<<N-9090;
  else cout<<90909;
  
  input();
  solve();
  output();
}


Measured memory_bytes: 256
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception{
		new Main(new Scanner(System.in), System.out, System.err).exec();
	}
	public final Scanner sc;
	public final PrintStream out, err;
	public Main(final Scanner sc, final PrintStream out, final PrintStream err) {
		this.sc = sc;this.out = out;this.err = err;
	}
	static private final long pair(int a, int b) {return (((long)a) << 32) + b;}
	static private final int upper(long v) {return (int)(v >> 32);}
	static private final int lower(long v) {return (int)(v & 0xFFFFFFFF);}

	//-----------------------------------------

	static public final long load(int end, int length) {
		return pair(end, length);
	}
	static public final int end(long load) {
		return upper(load);
	}
	static public final int length(long load) {
		return lower(load);
	}
	static public final long score(int count, int last) {
		return pair(count, last);
	}
	static public final int count(long score) {
		return upper(score);
	}
	static public final int last(long score) {
		return lower(score);
	}

	//------------------------------------------

	private int p;
	private int[] inv;
	private int[] fact;
	private int[] finv;
	public final int mod(long v) {
		v %= p;
		return (int)(v < 0 ? v+p : v);
	}
	public final int mul(long a, long b) {
		return mod(a*b);
	}
	public final void initFact(double limit, double p) {
		initFact((int)limit, (int)p);
	}
	public final void initFact(int limit, int p) {
		this.p = p;
		this.inv = new int[limit+1];
		this.fact = new int[limit+1];
		this.finv = new int[limit+1];
		fact[1] = finv[1] = inv[0] = inv[1] = 1;
		for(int i=2;i<=limit;i++) {
			int a = p / i;
			int b = p % i;
			inv[i]  = mul(-a, inv[b]);
			fact[i] = mul(fact[i-1], i);
			finv[i] = mul(finv[i-1], inv[i]);
		}
	}
	public final int comb(int m, int n) {
		return mul(mul(fact[m], finv[n]), finv[m-n]);
	}

	//------------------------------------------

	public void exec() throws Exception{
		final int X = sc.nextInt();
		final int Y = sc.nextInt();

		if((X+Y)%3 != 0) {
			out.println(0);
			return;
		}

		int m = (2*X-Y)/3;
		int n = (2*Y-X)/3;
		if(m<0 || n<0) {
			out.println(0);
			return;
		}
		if(m==0 || n==0) {
			out.println(1);
			return;
		}
		initFact(1e6, 1e9+7);
		out.println(comb(m+n, n));
	}
}


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

bool flag;
int n;

void Search(int*A, int i, int m, int sum) {
    if(sum == m) {
        flag = true;
    } else if(i < n && sum < m) {
        Search(A, i + 1, m, sum);
        Search(A, i + 1, m, sum + A[i]);
    }
}


int main(void) {
    int q;
    int A[2000];
    int m;
    
    cin >> n;
    
    for(int i = 0; i < n; ++i) {
        cin >> A[i];
    }
    
    cin >> q;
    
    for(int i = 0; i < q; ++i) {
        cin >> m;
        
        flag = false;
        Search(A, 0,  m, 0);
        
        if(flag) {
            cout << "yes" << endl;
        } else {
            cout << "no" << endl;
        }
    }
}



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

#define all(x) (x).begin(), (x).end()
#define sz(x) static_cast<int>((x).size())

using LL = long long;
template<class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
  template<class... Args>
  vec(size_t n = 0, Args... args)
    : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template<class T>
struct vec<T, 1> : vector<T> {
  template<class... Args>
  vec(Args... args)
    : vector<T>(args...) {}
};

template<class T>
inline bool asMn(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T& a, const T& b) { return a < b ? a = b, true : false; }
inline int nex(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int pre(int i, int n) { return !i ? n - 1 : i - 1; }

const int LIM = 1e8;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

template<int MOD>
struct ModInt {
  int a;
  ModInt(int a_ = 0) {
    a = a_ < MOD ? (a_ < 0 ? a_ + MOD : a_) : a_ - MOD;
  }
  friend ostream& operator<<(ostream& os, const ModInt& o) {
    os << o.a;
    return os;
  }

  bool operator==(const ModInt& o) const { return a == o.a; }

  ModInt operator+(const ModInt& o) const { return ModInt(a + o.a); }
  ModInt operator-(const ModInt& o) const { return ModInt(a - o.a); }
  ModInt operator*(const ModInt& o) const { return ModInt(static_cast<int>(static_cast<LL>(a) * o.a % MOD)); }
  ModInt& operator+=(const ModInt& o) { return *this = *this + o; }
  ModInt& operator-=(const ModInt& o) { return *this = *this - o; }
  ModInt& operator*=(const ModInt& o) { return *this = *this * o; }
};
using Mint = ModInt<static_cast<int>(1e9 + 7)>;

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

//  freopen("input.txt", "r", stdin);

  int s; cin >> s;
  vec<pair<int, int>, 1> a;
  for (int i = 1, j = 1; i < LIM; i *= 10, ++j) {
    a.emplace_back(i, j);
  }
  Mint ans;
  for (int l = 1, r = 1, iL = 1, iR = 1, cur = 1; r < LIM; ) {
    while (cur > s) {
      cur -= a[iL - 1].second;
      ++l;
      while (iL < sz(a) && a[iL].first <= l) {
        ++iL;
      }
    }

    ans += Mint(cur == s);

    ++r;
    while (iR < sz(a) && a[iR].first <= r) {
      ++iR;
    }
    cur += a[iR - 1].second;
  }

  Mint lst(1), prv;
  for (int i = 1; i < 9; ++i) {
    prv = lst;
    lst *= Mint(10);
  }
  for (int i = 9; i <= s; ++i) {
    prv = lst;
    lst *= Mint(10);
    if (!(s % i)) {
      ans += lst - prv - Mint(s / i - 1);
    }

    int tmp = s - (s + i) / i * (i - 1);
    ans += Mint((tmp + i - 2) / (i - 1));
  }

  cout << ans << '\n';

  return 0;
}


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

int main(void)
{
  long long a,b;
  scanf("%lld %lld",&a,&b);
  for(long long k=0;k<=1000000000;k++){
    if(abs(a-k)==abs(b-k)){
      printf("%lld\n",k);
      return 0;
    }
  }

  puts("IMPOSSIBLE");
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;

int main(int argc, const char * argv[]) {
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n;
    cin >> n;
    
    vector<ll> a(n);
    
    for ( ll i = 0; i < n; i++ )
        cin >> a[i];
    
    ll l = 0;
    ll r = 0;
    
    ll len = 0;
    
    for ( ; r < n; ){
        if ( a[r] >= a[r+1] ){
            r++;
            continue;
        }

        len = max(len, r-l);
        l = r+1;
        
        if ( r == n ) break;
        ++r;
    }
    len = max(len, r-l-1);

    cout << len << endl;
    
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main(){
	int m1,d1,m2,d2;
  	cin>>m1>>d1;
  	cin>>m2>>d2;
  	if(m1+1==m2)cout<<1<<endl;
  	else if(m1==12 && d1==31)cout<<1<<endl;
  	else cout<<0<<endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>

using namespace std;

int main(){
   int N;
   cin >> N;
   cout << 180*(N-2) << endl;

   return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
  long long n, bsm[100009];
  vector<long long> a, b, c;
  long long tmp;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> tmp; a.push_back(tmp);
  }
  for(int i=0;i<n;i++){
    cin >> tmp; b.push_back(tmp);
  }
  for(int i=0;i<n;i++){
    cin >> tmp; c.push_back(tmp);
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  sort(c.begin(), c.end());
  int cur_a = a.size()-1,cur_b = b.size()-1;
  for(;cur_b>=0;cur_b--){
    if(cur_a==-1){
      bsm[cur_b]=0;
      continue;
    }
    while(cur_a>=0&&b[cur_b]<=a[cur_a]){
      cur_a--;
    }
    bsm[cur_b]=cur_a+1;
  }
  for(int i=1;i<n;i++){
    bsm[i] = bsm[i]+bsm[i-1];
  }
  int cur_c=n-1;
  cur_b=n-1;
  long long ans=0;
  for(;cur_c>=0;cur_c--){
    while(cur_b>=0&&c[cur_c]<=b[cur_b]){
      cur_b--;
    }
    if(cur_b==-1)break;
    ans+=bsm[cur_b];
  }
  cout << ans << endl;
}

Measured memory_bytes: 3444
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>

typedef  long long ll;
#define mop 1000000007
using namespace std;

int main() {
   

    multiset <ll> s;
    ll n;
    cin >> n;
    for (ll i=0;i<n;i++){
        ll a;
        cin >> a;
        auto itr = s.lower_bound(a);
        if(itr == s.begin()){
            s.insert(a);
        }else{
            itr--;
            s.erase(itr);

            s.insert(a);
        }
//        cout << i << " ";
//        for(auto itr = s.begin(); itr != s.end(); itr++){
//            cout << *itr << " ";
//        }
//        cout << endl;
    }
    cout << s.size() << endl;
}

Measured memory_bytes: 4992
//package practice;
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.Stack;
import java.util.regex.Pattern;






public class Main {

	
	 
	
	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;
		//it reads the data about the specified point and divide the data about it ,it is quite fast
		//than using direct 

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception r) {
					r.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());//converts string to integer
		}

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

		long nextLong() {
			return Long.parseLong(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception r) {
				r.printStackTrace();
			}
			return str;
		}
	}
	
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	static long mod = (long) (1e9+7);
	static int n = (int) 1e5;
	public static void main(String[] args) {
		 FastReader sc = new FastReader();
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			out.print(Math.max(0, c-a+b));
			
			 out.close();
		}
		
	 
		
	}

Measured memory_bytes: 21204
def main():
    n=int(input())
    a=list(map(int,input().split()))
    s=sum(a)
    if s%(n*(n+1)//2) != 0:
        return "NO"
    k=s//(n*(n+1)//2)
    for i in range(n-1):
        if (a[i]-a[i+1]+k)%n!=0 or a[i+1]-a[i]>k or a[i+1]-a[i]<k*(1-n):
            return "NO"
    if (a[-1]-a[0]+k)%n!=0:
        return "NO"
    return "YES"

print(main())

Measured memory_bytes: 62704
#include<iostream>
#include<limits.h>

using namespace std;

int gcd(int a, int b) {
	if (a % b == 0){
		return(b);
	}
	else{
		return(gcd(b, a % b));
	}
}

int GCD(int a, int b, int c) {
	return gcd(gcd(a, b), c);
}

int main() {
	int k;
	cin >> k;
	int sum = 0;
	for (int i = 0; i < k; i++) {
		for (int j = 0; j < k; j++) {
			for (int l = 0; l < k; l++) {
				sum += GCD(i + 1, j + 1, l + 1);
			}
		}
	}
	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 3648
// #define DEBUGGING
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()

template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
template <typename T, typename U> using P = pair<T, U>;
using ll = int64_t;
using PLL = P<ll, ll>;

template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return max(low, min(high, t)); }
template <typename T> void chclamp(T &t, const T &low, const T &high) { t = clamp(t, low, high); }

namespace init__ {

struct InitIO {
    InitIO() {
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

}

#ifdef DEBUGGING
#include "../debug.cpp"
#else
#define DEBUG(...) 0
#define DEBUG_SEPARATOR_LINE 0
#endif

template <typename T>
T make_v(T init) { return init; }

template <typename T, typename... Tail>
auto make_v(T init, size_t s, Tail... tail) {
#define rec make_v(init, tail...)
    return V<decltype(rec)>(s, rec);
#undef rec
}

int main() {
    ll N, Q;
    string S;
    cin >> N >> S >> Q;
    V<ll> sum_M(N + 1);
    V<ll> cnt_C(N + 1);
    V<ll> sum_M_befor_C(N + 1);

    for(ll i = 0; i < N; i++) {
        char c = S[i];
        sum_M[i + 1] = sum_M[i];
        cnt_C[i + 1] = cnt_C[i];
        sum_M_befor_C[i + 1] = sum_M_befor_C[i];
        if(c == 'M') sum_M[i + 1]++;
        if(c == 'C') {
            cnt_C[i + 1]++;
            sum_M_befor_C[i + 1] += sum_M[i + 1];
        }
    }

    DEBUG(cnt_C, sum_M, sum_M_befor_C);

    while(Q--) {
        ll K;
        cin >> K;
        ll ans = 0;
        for(ll i = 0; i + 2 < N; i++) {
            char c = S[i];
            if(c != 'D') continue;
            ll right = min(i + K, N);
            ll cnt_c = cnt_C[right] - cnt_C[i];
            ll sum_m_befor_c = sum_M_befor_C[right] - sum_M_befor_C[i];
            sum_m_befor_c -= cnt_c * sum_M[i];
            DEBUG(make_tuple(cnt_c, sum_m_befor_c));
            ans += sum_m_befor_c;
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 24860
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int y = sc.nextInt();
		if (x < y) {
			System.out.println("a < b");
		}else if(x > y){
			System.out.println("a > b");
		}else {
				System.out.println("a == b");
			}
		}
	}

Measured memory_bytes: 17352
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,fa[N],x[N],black[N],white[N];
vector<int> e[N];
//black[x]表示在x选择黑色的情况下,子树中白色的最小和
int dp[2][N*10],a=0,b=1;
int main()
{
	scanf("%d",&n);
	for (int i=2;i<=n;i++) scanf("%d",&fa[i]),e[fa[i]].push_back(i);
	for (int i=1;i<=n;i++) scanf("%d",&x[i]);
	for (int v=n;v;v--){
		for (int i=1;i<=x[v];i++) dp[a][i]=1e9;
		dp[a][0]=0;
		for (int i=0;i<e[v].size();i++,swap(a,b)){
			int u=e[v][i];
			for (int i=0;i<=x[v];i++) dp[b][i]=1e9;
			for (int i=x[v];i>=0;i--){
				if (i+x[u]<=x[v])
					dp[b][i+x[u]]=min(dp[b][i+x[u]],dp[a][i]+black[u]);
				if (i+white[u]<=x[v])
					dp[b][i+white[u]]=min(dp[b][i+white[u]],dp[a][i]+x[u]);
			}
		}
		black[v]=1e9;
		for (int i=0;i<=x[v];i++) black[v]=min(black[v],dp[a][i]);
		for (int i=1;i<=x[v];i++) dp[a][i]=1e9;
		dp[a][0]=0;
		for (int i=0;i<e[v].size();i++,swap(a,b)){
			int u=e[v][i];
			for (int i=0;i<=x[v];i++) dp[b][i]=1e9;
			for (int i=x[v];i>=0;i--){
				if (i+black[u]<=x[v])
					dp[b][i+black[u]]=min(dp[b][i+black[u]],dp[a][i]+x[u]);
				if (i+x[u]<=x[v])
					dp[b][i+x[u]]=min(dp[b][i+x[u]],dp[a][i]+white[u]);
			}
		}
		white[v]=1e9;
		for (int i=0;i<=x[v];i++) white[v]=min(white[v],dp[a][i]);
		if (black[v]>1e8&&white[v]>1e8) return puts("IMPOSSIBLE"),0;
	}
	puts("POSSIBLE");
	return 0;
}

Measured memory_bytes: 384
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using Console = System.Console;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var r = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            if ((r[0] * r[1]) % 2 == 0)
            {
                Console.WriteLine("Even");
            }
            else
            {
                Console.WriteLine("Odd");
            }
        }
    }
}

Measured memory_bytes: 11348
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from collections import deque
from decimal import *
import queue

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	L,R,d = inputMap()

	ans = 0
	for i in range(L,R+1):
		if i % d == 0:
			ans += 1

	print(ans)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()


Measured memory_bytes: 76868
#include <bits/stdc++.h>
#define ss second
#define ff first
#define all(x) x.begin(), x.end()
    
using namespace std;
using ll = long long;
using pii = pair<int, int>;
    
const int oo = 1e9 + 7;
const int mod = 1e9 + 7;
const double PI = acos(-1);

int main(){
    ll n, m, xsum=0, ysum=0;
    cin >> n >> m;

    vector<ll> xs(n), ys(m);

    for (int i=0; i<n; i++){
        cin >> xs[i];
        xsum = (xsum - (xs[i]*(n - i -1)) + xs[i]*i + mod)%mod;
    }

    for (int i=0; i<m; i++){
        cin >> ys[i];
        ysum = (ysum - (ys[i]*(m - i -1)) + ys[i]*i + mod)%mod;
    }

    cout << (xsum*ysum)%mod << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(k,i,n) for(ll i=k;i<n;++i)
#define pb push_back
int main(void){
    string s,t;
    cin>>s;
    cin>>t;
    if(s==t.substr(0,s.length())){
        
        cout<<"Yes";
    }else{
        cout<<"No";
    }
}


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

int main(){
    int N,A,G1,G2;
    G1 = 0;
    G2 = 0;
    int a[100];

    cin >> N;

    for(int i=1;i<=N;i++){
        cin >> a[i];
    }

    for(int i=1;i<=N-1;i++){
        int M = i;
        for(int j=i+1;j<=N;j++){
            if(a[M] < a[j]){
                M = j;
            }
        }
        if(M != i){
            a[0] = a[M];
            a[M] = a[i];
            a[i] = a[0];
        }
    }

    for(int i=1;i<=N;i++){
        if(i % 2 != 0){
            G1 += a[i];
        }else{
            G2 += a[i];
        }
    }

    cout << G1 - G2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef pair<ll, ll> P;

const int mod =  1000000007;  //出力は (ans % mod + mod) % mod  (負の剰余を正にする)
const int inf = 1e9;
const long long INF = 1LL << 60;   // INF = 11

int main()
{
    int cnt = 0;
    int l,r,d; cin >> l >> r >> d;
    for(int i =l ; i <= r; i++){
        if(i % d == 0) cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 3632
#include <stdio.h>

int main(void) {
	int X[5];
	int min = 10;
	int sum = 0;
	int a = 0;
	for (int i = 0; i < 5; i++) {
		scanf("%d", &X[i]);
		if (X[i] % 10 != 0&&X[i]%10<min) {
			min = X[i] % 10;
			a = i;

		}
	}
	if (X[a]%10!=0) {
		sum += X[a];
		X[a] = 0;
	}
	for (int i = 0; i < 5; i++) {
		sum += ((X[i]+9)/10)*10;
	}
	printf("%d", sum);
	return 0;

}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
typedef vector<string> vstring;
#define _GLIBCXX_DEBUG
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
const int INF = 1 << 30;
const int dx[] = {1,0,-1,0,1,1,-1,-1};
const int dy[] = {0,-1,0,1,1,-1,-1,1};
#define stp(x)  setprecision(x)
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  vector<vector<int> > c(3,vector<int>(3));
  rep(i,3){
    rep(j,3){
      cin>>c[i][j];
    }
  }
  vint a(3);
  vint b(3);
  rep(a1,101){
    rep(a2,101){
      rep(a3,101){
        a[0]=a1,a[1]=a2,a[2]=a3;
        b[0]=c[0][0]-a[0],b[1]=c[1][1]-a[1],b[2]=c[2][2]-a[2];
        bool fg=true;
        rep(i,3){
          rep(j,3){
            if(c[i][j]!=a[i]+b[j]){
              fg=false;
            }
          }
        }
        if(fg){
          cout<<"Yes"<<'\n';
          return(0);
        }
      }
    }
  }
  cout<<"No"<<'\n';
  return(0);
}


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

#define rep(i,x,y) for(ll i=(x);i<(y);i++)
#define rrep(i,x,y) for(ll i=(ll)(y)-1;i>=(x);i--)
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define dump(x)  cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#define dassert(...) assert(__VA_ARGS__)
#else
#define dump(x)
#define debug(x)
#define dassert(...)
#endif
//#define int long long

typedef long long ll;
const ll MOD = 998244353;
const long double EPS = 1e-8;

class SegmentTree {
    vector<int> nodes_;
    int size_;
    const int INIT = -1;

    int query (const int left, const int right, const int index, const int l, const int r) const {
        if (r <= left || right <= l) return INIT;
        if (left <= l && r <= right) return nodes_[index];

        return max (
                query(left, right, 2 * index + 1, l, (l + r) / 2),
                query(left, right, 2 * index + 2, (l + r) / 2, r)
        );
    }

public:
    SegmentTree(const int maxSize) {
        size_ = 1;
        while (size_ < maxSize) size_ *= 2;
        nodes_ = vector<int> (2 * size_, INIT);
    };

    void update (int index, const int value) {
        index += size_ - 1;
        nodes_[index] = value;
        while (index > 0) {
            index = (index - 1) / 2;
            nodes_[index] = max(nodes_[2 * index + 1], nodes_[2 * index + 2]);
        }
    }

    // get value in [left, right)
    int get (const int left, const int right) const {
        return query(left, right, 0, 0, size_);
    }
};

void solve(long long N, std::vector<long long> X, std::vector<long long> D){
    vector<vector<ll>> dp(N, vector<ll>(2));
    vector<pair<ll, ll>> robots(N);
    rep(i,0,N) robots[i] = {X[i], D[i]};
    sort(all(robots));
    SegmentTree st(N+1);
    vector<int> rights(N+1, -1);
    rrep(i,0,N) {
        auto itr = lower_bound(all(robots), make_pair(robots[i].first + robots[i].second, 0LL));
        int value;
        if (itr == robots.end()) {
            value =  N;
            st.update(i, value);
        } else {
            int j = distance(robots.begin(), itr);
            value = j != i+1 ? st.get(i+1, j) : i+1;
            st.update(i, value);
        }
        rights[i] = value;
    }
    dp[N-1][1] = 1;
    dp[N-1][0] = 1;
    rrep(i,0,N-1) {
        dp[i][1] = dp[i+1][1] + dp[i+1][0];
        if (rights[i] == N) {
            dp[i][0] = 1;
        } else {
            dp[i][0] = dp[rights[i]][0] + dp[rights[i]][1];
        }
        dp[i][1] %= MOD;
        dp[i][0] %= MOD;
    }
    cout << (dp[0][0] + dp[0][1]) % MOD << endl;
}

signed main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> X(N);
    std::vector<long long> D(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&X[i]);
        scanf("%lld",&D[i]);
    }
    solve(N, std::move(X), std::move(D));
    return 0;
}


Measured memory_bytes: 20224
//#pragma GCC optimize ('O3')
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
#define mp make_pair
#define f first
#define s second
#define pb push_back

const int N = 5000 + 5;
const int M = 5e5 + 5;
const int OO = 1e9;
const int mod = 1e9 + 7;

int n,k;
map<int,int> cnt;
ll ans;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;

    for (int i = 1; i <= n; ++i) {
        if(i%k==(-i%k + k)%k) cnt[i%k]++;
    }

    for(auto i:cnt) ans += 1LL*i.s*i.s*i.s;

    cout << ans << '\n';

    return 0;
}

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

#define ll long long
const int mod = pow(10,9)+7;

vector<vector<ll>> arr(1000,vector<ll> (1000,-1));
vector<vector<char>> grid(1000,vector<char> (1000));

ll help(int i,int j,int h,int w)
{
    if(i<0 || i>h) return 0;
    if(j<0 || j>w) return 0;

    if(arr[i][j]!=-1) return arr[i][j];
    if(grid[i][j]=='#') arr[i][j]=0;
    else{
        arr[i][j] = help(i+1,j,h,w);
        arr[i][j]+= help(i,j+1,h,w);
        arr[i][j]%= mod;
    }
    return arr[i][j];
}
int main()
{
    int h,w;
    cin>>h>>w;

    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++)
            cin>>grid[i][j];

    arr[h-1][w-1]=1;
    cout<<help(0,0,h-1,w-1);
    //cout<<arr[0][0];
    return 0;
}

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

using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)

int main(void){
    string X; cin >> X;
    int S = 0, cou = 0;

    rep(i, X.size()){
        if(X[i] == 'S')S++;
        else{
            if(S == 0)continue;
            cou += 2;
            S--;
        }
    }

    cout << X.size() - cou << "\n";
    return 0;
}


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

using namespace std;

using ll = long long;

const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

int main () {
  cin.tie(0);
  cout << fixed << setprecision(10);
  
  int n, m; cin >> n >> m;
  vector<vector<int>> g(n);
  for(int i=0;i<m;++i) {
    int a, b; cin >> a >> b;
    a--; b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  vector<int> sel(n, -1);
  sel[0] = 0;
  bool bigraph = true;
  stack<pair<int, bool>> st;
  st.push(make_pair(0, 1));
  while(bigraph && !st.empty()) {
    pair<int, int> p = st.top(); st.pop();
    int now = p.first;
    bool col = p.second;
    int sz = g[now].size();
    for(int i=0;i<sz;++i) {
      int next = g[now][i];
      if(sel[next] == -1) {
        sel[next] = col;
        st.push(make_pair(next, !col));
      } else if(sel[next] != col) {
        bigraph = false;
        break;
      }
    }
  }

  if(bigraph) {
    ll cnt1 = 0, cnt2 = 0;
    int sz = sel.size();
    for(int i=0;i<sz;++i) {
      if(sel[i] == 0) cnt1++;
    }
    cnt2 = n - cnt1;
    cout << cnt1 * cnt2 - (ll)m << endl;
  } else {
    cout << (ll)n * ((ll)n - 1) / 2 - (ll)m << endl;
  }
}


Measured memory_bytes: 6272
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<list>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;

const int NIL = -1;
const int MAX = 1 << 21;

int color[10001], d[10001];

struct Node {
	int node, weight;
};
vector<Node>M[10001];

struct cmp {
	bool operator () (Node a, Node b)
	{
		return a.weight > b.weight;
	}
};

int next(int u) {
	for (int i = 0; i < M[u].size(); i++) {
		if (color[M[u][i].node] == 0) {
			color[M[u][i].node] = 1;
			return i;
		}
	}
	return -1;
}

int main(void)
{
	int n, u, k, v, c;
	priority_queue<Node, vector<Node>, cmp>PQ;
	Node s;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> u >> k;
		for (int j = 0; j < k; j++) {
			cin >> v >> c;
			s.node = v;
			s.weight = c;
			M[u].push_back(s);
		}
	}
	for (int i = 0; i < n; i++) {
		color[i] = 0;
		d[i] = MAX;
	}
	d[0] = 0;
	s.node = s.weight = 0;
	PQ.push(s);
	while (!PQ.empty()) {
		Node u = PQ.top();
		PQ.pop();
		color[u.node] = 2;
		for (int i = 0; i < n; i++) {
			if (color[i] != 2)
				color[i] = 0;
		}
		if (d[u.node] < u.weight)
			continue;
		while ((v = next(u.node)) != NIL) {
			int tmp = M[u.node][v].node;
			if (color[tmp] != 2) {
				if (d[u.node] + M[u.node][v].weight < d[tmp]) {
					d[tmp] = M[u.node][v].weight + d[u.node];
					s.node = tmp;
					s.weight = d[tmp];
					PQ.push(s);
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		cout << i << " " << d[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 8152
#include<bits/stdc++.h>
#define fastio     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(x)     (x).begin() , (x).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define endl       '\n'
#define MAX        1000000
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
typedef long long int ll;
using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}


const ll mod = 1e9+7;
const double eps = 1e-9;
const double pi = acos(-1);

void solve(){
    int a[3];
    int aa=0,b=0;
    for(int i=0;i<3;i++) {
        cin>>a[i];
        aa+=(a[i]==5);
        b+=(a[i]==7);
    }
    if(aa==2&&b==1)cout<<"YES";
    else cout<<"NO";
}





int main(){
    fastio
    int test=1;
    while(test--)
        solve();
    return 0;
}


Measured memory_bytes: 256