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

// 最大公約数（a > b）
int gcd(int a, int b) {
  int r = a % b;
  while (r > 0) {
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}

int main() {
  int N, K;
  cin >> N >> K;
  int a[N];
  int maxi = 0;
  for (int i = 0; i < N; i++) {
    scanf("%d", a + i);
    maxi = max(maxi, a[i]);
  }

  sort(a, a + N);
  reverse(a, a + N);
  int gcd_num = gcd(a[0], a[1]);
  for (int i = 2; i < N; i++) {
    gcd_num = gcd(gcd_num, a[i]);
  }

  // 解答
  if (K % gcd_num == 0 && K <= maxi) {
    cout << "POSSIBLE" << endl;
  } else {
    cout << "IMPOSSIBLE" << endl;
  }

  return 0;
}


Measured memory_bytes: 640
#include "iostream"
#include "string"
using namespace std;

int main()
{
	char grade[50];
	int m[50], f[50], r[50], i = 0, count = 0;
	while (true)
	{
		cin >> m[i] >> f[i] >> r[i];
		if (m[i] == -1 && f[i] == -1 && r[i] == -1)
		{
			break;
		}
		if (m[i] == -1 || f[i] == -1)
		{
			grade[i] = 'F';
		}
		else if (m[i] + f[i] >= 80)
		{
			grade[i] = 'A';
		}
		else if (65 <= m[i] + f[i] && m[i] + f[i] < 80)
		{
			grade[i] = 'B';
		}
		else if (50 <= m[i] + f[i] && m[i] + f[i] < 65)
		{
			grade[i] = 'C';
		}
		else if (30 <= m[i] + f[i] && m[i] + f[i] < 50)
		{
			if (r[i] >= 50)
			{
				grade[i] = 'C';
			}
			else
			{
				grade[i]='D';
			}
		}
		else
		{
			grade[i] = 'F';
		}
		i++;
		count++;
	}
	for (int i = 0; i < count; i++)
	{
		cout << grade[i] << endl;
	}
}


Measured memory_bytes: 3108
using System;
//using System.Text;
namespace AIZU_Cs_
{
    class Program
    {
        static void Main()
        {
            int n,i;
            while ((n = int.Parse(Console.ReadLine())) != -1)
            {
                double x = 1.0, y = 0.0;
                for(i=1;i<n;i++)
                {
                    double d = Math.Sqrt(x * x + y * y);
                    double dx = -y / d, dy = x / d;
                    x += dx;
                    y += dy;
                }
                Console.WriteLine("{0}\n{1}", x, y);
            }
        }
    }
}

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

#define rep(i, a, b) for (int i = int(a); i < int(b); i++)
#define rrep(i, a, b) for (int i = int(a) - 1; i >= b; i--)
#define sz(x) (int)(x).size()

using namespace std;
using ll = long long;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

int main() {
  string s;
  cin >> s;
  rep(i, 0, sz(s)) cout << "x";
  cout << endl;
}

Measured memory_bytes: 256
n,s;
 
int f(int d,int p,int b)
{
    int c=0,i=b+1;
    if(d==n+1)  return p==s;
    for(;i<=9;i++)
        c+=f(d+1,p+i,i);
    return c;
}
 
main(){
    for(;scanf("%d%d",&n,&s),n+s;)printf("%d\n",f(1,0,-1));
    exit(0);
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void solve() {
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    vector<bool> dp(300000, false);
    rep(i, K) {
        rep(j, N) {
            ll a = A[j];
            if (!dp[i]) {
                dp[i + a] = true;
            }
        }
    }
    if (dp[K]) {
        cout << "First" << '\n';
    } else {
        cout << "Second" << '\n';
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}


Measured memory_bytes: 3656
class Dice:
    def __init__(self, list):
        self.list = list

    def roll_n(self):
        self.list = [self.list[1], self.list[5], self.list[2], self.list[3], self.list[0], self.list[4]]

    def roll_s(self):
        self.list = [self.list[4], self.list[0], self.list[2], self.list[3], self.list[5], self.list[1]]

    def roll_e(self):
        self.list = [self.list[3], self.list[1], self.list[0], self.list[5], self.list[4], self.list[2]]

    def roll_w(self):
        self.list = [self.list[2], self.list[1], self.list[5], self.list[0], self.list[4], self.list[3]]

    def rotate_r(self):
        self.list = [self.list[0], self.list[2], self.list[4], self.list[1], self.list[3], self.list[5]]


dice_1 = Dice(list(map(int, input().split())))
dice_2 = Dice(list(map(int, input().split())))
c = 0
for i in range(4):
    dice_1.rotate_r()
    for j in range(4):
        dice_1.roll_n()
        if dice_1.list == dice_2.list:
            c = 1

for i in range(4):
    dice_1.rotate_r()
    for j in range(4):
        dice_1.roll_e()
        if dice_1.list == dice_2.list:
            c = 1
if c == 1:
    print('Yes')
else:
    print('No')



Measured memory_bytes: 5608
import numpy as np
n,t=map(int,input().split())
a=[list(map(int,input().split()))for i in range(n)]
b=np.zeros((n+1,t))
c=np.zeros((n+1,t))
for i in range(n):
    b[i+1]=b[i]
    b[i+1][a[i][0]:]=np.maximum(b[i+1][a[i][0]:],b[i][:-a[i][0]]+a[i][1])
    c[-i-2]=c[-i-1]
    c[-i-2][a[-i-1][0]:]=np.maximum(c[-i-2][a[-i-1][0]:],c[-i-1][:-a[-i-1][0]]+a[-i-1][1])
q=0
for i in range(n):
    q=max(q,max(b[i]+c[i+1][::-1])+a[i][1])
print(int(q))

Measured memory_bytes: 153432
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
int n , k;
int num;

int main ( void ) {
    cin>>num;
    int a=num/100;
    int b=num%100;
	if((a == 0 || a > 12) && (b == 0 || b > 12))
        cout << "NA" << endl;
    else if((a <= 12 && a != 0) && (b > 12 || b == 0))
        cout << "MMYY";
    else if((a > 12 || a == 0) && b <= 12 && b != 0)
        cout << "YYMM";
    else cout << "AMBIGUOUS";
	return 0;
}

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

int main() {
  int N, T, A;
  cin >> N >> T >> A;
  T *= 1000, A *= 1000;
  vector<int> H(N);
  for (int i = 0; i < N; i++) cin >> H[i];

  vector<int> dif(N);
  for (int i = 0; i < N; i++) dif[i] = abs(T - H[i] * 6 - A);

  int min_dif = 650000, ans = -1;
  for (int i = 0; i < N; i++) {
    if (dif[i] < min_dif) {
      min_dif = dif[i];
      ans = i + 1;
    }
  }

  cout << ans << endl;

  return 0;
}

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

#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; i++)
typedef long long ll;
ll MOD = 1e9 + 7;

int main() {
    ll n; cin >> n;
    map<ll, ll> m1;
    for(ll i = 0; i < n; i++){
        ll a; cin >> a;
        m1[a]++;
    }
    map<ll, ll> m2;
    ll j = n - 1;
    for(ll i = 0; i < n; i++){
        ll t = abs(j - i);
        m2[t]++;
        j--;
    }
    bool flag = true;
    for(ll i = 0; i < n; i++){
        if(m1[i] != m2[i]){
            flag = false;
            break;
        }
    }
    ll ans = 1;
    for(int i = 1; i <= n / 2; i++){
        ans *= 2;
        ans %= MOD;
    }
    if(flag) cout << ans << endl;
    else cout << 0 << endl;
}


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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, a, b) for(ll i = a; i < b; i++)
#define out(x) std::cout << x << '\n'
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define sz(x) ((int)(x).size())
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INF = INT_MAX / 2;
const ll  inf = LLONG_MAX / 2;
const int mod = 1000000007;
const int MAX_N = 101010;
const long double PI = acos(-1);

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	/*------------------------------*/

	int n, m;
	cin >> n >> m;

	vector<int> a(m);
	vector<bool> ok(n + 1, true);
	rep(i, m) {
		cin >> a[i];
		ok[a[i]] = false;
	}

	vector<int> dp(n + 1, 0);
	dp[0] = 1;
	if (ok[1]) {
		dp[1] = 1;
	}

	for (int i = 2; i <= n; i++) {
		if (ok[i - 1]) {
			dp[i] += dp[i - 1];
		}
		if (ok[i - 2]) {
			dp[i] += dp[i - 2];
		}
		dp[i] %= mod;
	}

	out(dp[n]);

	return 0;
}

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

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

  int N, M, X; cin >> N >> M >> X;
  int l = 0, r = 0;
  for (int i = 0; i < M; i++) {
    int A; cin >> A;
    if (A < X) l++;
    else r++;
  }
  cout << min(l, r) << "\n";
}

Measured memory_bytes: 256
S = list(input())
N = len(S)

sub1 = S[:(N-1)//2]
sub2 = S[(N+2)//2:]

Sc = S.copy()
sub1c = sub1.copy()
sub2c = sub2.copy()

Sc.reverse()
sub1c.reverse()
sub2c.reverse()

#print("S:{}, Sc:{}".format(S, Sc))
#print("sub1:{}, sub1c:{}".format(sub1,sub1c))
#print("sub2:{}, sub2c:{}".format(sub2,sub2c))

if S==Sc and sub1==sub1c and sub2==sub2c:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3060
#include<bits/stdc++.h>
int main(void)
{
    int a,s,d,f,g,h,j,i,k;
    while(1){
        scanf("%d",&a);
        if(a==0) break;
        d=0;
        f=0;
        for(i=0;i<a;i++){
            scanf("%d",&s);
            if(s>=2) d++;
            if(s>=1) f++;
        }
        if(d<1)  printf("NA\n");
        else printf("%d\n",f+1);
    }
    return 0;
}

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

using namespace std;

typedef int in;
#define int long long

int n,m;
vector<int> adj[100005];
bool vis[100005];

void dfs(int node){
    vis[node] = 1;
    for(int i = 0 ; i < adj[node].size() ; i ++){
        int f = adj[node][i];
        if(!vis[f]){
            dfs(f);
        }
    }
}

in main()
{
    cin >> n >> m;
    for(int i = 0 ; i < m ; i ++){
        int x,y,z;
        cin >> x >> y >> z;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int ans = 0;
    for(int i = 1 ; i <= n ; i ++){
        if(!vis[i]){
            dfs(i);
            ans ++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 8960
class Bridge:
    def __init__(self, nodeA, nodeB):
        self.edges = [BridgeEdge(nodeA, self), BridgeEdge(nodeB, self)]
        nodeA.addEdge(self.edges[1])
        nodeB.addEdge(self.edges[0])
        self.dir = True
        self.vec = None
    def __repr__(self):
        return str((self.vec, self.dir))

class BridgeEdge:
    def __init__(self, node, edge):
        self.edge = edge
        self.node = node
    def another(self):
        return self.edge.edges[1 if self.edge.edges[0] == self else 0]

class Node:
    def __init__(self, id):
        self.id = id
        self.bridges = []
        self.parent = None
        self.judge = True
    def addEdge(self, bridgeEdge):
        self.bridges.append(bridgeEdge)
    def __repr__(self):
        return str((self.id, None if self.parent is None else self.parent.node.id, self.judge))

N, M = map(int, input().split())

nodes = [Node(i) for i in range(N+1)]
bridges = []
for A, B in (map(int, input().split()) for _ in range(M)):
    bridges.append(Bridge(nodes[A], nodes[B]))

s = [(0, nodes[1])]
idx = 0
while len(s) > 0:
    level, cur = s.pop()

    nxtlevel = level + 1
    for nxt in cur.bridges:
        if nxt.edge.vec is None:
            cur.judge ^= True
            nxt.edge.vec = (cur.id, nxt.node.id)
            if nxt.node.parent is None:
                nxt.node.parent = nxt.another()
                s.append((nxtlevel, nxt.node))

    if len(s) > 0:
        nl = s[-1][0]
    else:
        nl = 1
    while level >= nl:
        if not cur.judge:
            cur.judge ^= True
            cur.parent.node.judge ^= True
            cur.parent.edge.dir ^= True
        level -= 1
        cur = cur.parent.node
  
if nodes[1].judge:
    for br in bridges:
        if br.dir:
            print("{} {}".format(br.vec[0], br.vec[1]))
        else:
            print("{} {}".format(br.vec[1], br.vec[0]))
else:
    print("-1")


Measured memory_bytes: 113824
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner stdin = new Scanner(System.in);
    int n = stdin.nextInt();
    int[][][] house = {
        { new int[10], new int[10], new int[10] },
        { new int[10], new int[10], new int[10] },
        { new int[10], new int[10], new int[10] },
        { new int[10], new int[10], new int[10] }
    };

    for (int i = 0; i < n; i++) {
      int b = stdin.nextInt();
      int f = stdin.nextInt();
      int r = stdin.nextInt();
      int v = stdin.nextInt();
      house[b - 1][f - 1][r - 1] += v;
    }

    for (int i = 0; i < 4; i++) {
      for (int[] arr : house[i]) {
        for (int j = 0; j < 10; j++) {
          System.out.printf(j < 9 ? " %d" : " %d%n", arr[j]);
        }
      }

      if (i < 3) {
        System.out.println("####################");
      }
    }
  }

}

Measured memory_bytes: 23216
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <stack>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
ll ans,n,a[200005];
ll d[22],x;
int main(void){
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(ll i=0;i<n;i++){
        while(x<n){
            bool o=true;
            for(int j=0;j<21&&o;j++){
                if(((a[x]>>j)&1)&&d[j]==1)o=false;
            }
            if(o){
                for(int j=0;j<21;j++){
                    if((a[x]>>j)&1)d[j]=1;
                }
                x++;
            }else break;
        }
        ans+=x-i;
        for(int j=0;j<21;j++){
            if((a[i]>>j)&1)d[j]=0;
        }
    }
    printf("%lld\n",ans);
}


Measured memory_bytes: 1792
import sys
from itertools import product

ops = '+-'

s = sys.stdin.readline().rstrip()

def main():
    formula = [None] * 7
    formula[::2] = list(s)
    
    for op in product(ops, repeat=3):
        f = formula.copy()
        f[1::2] = list(op)
        f = ''.join(f)
        if eval(f) == 7:
            return f + '=7'

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

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main{
	public static void main(String[] args)
	{
		Scanner sc =new Scanner(System.in);
		String s=sc.next(); //入力された文字列
		int AC_exi=0;
		
		//ACが連続して含まれているか確認
		for(int i=0;i<s.length()-1;i++){
			if(s.charAt(i)=='A' && s.charAt(i+1)=='C') AC_exi=1;
		}
		//YesかNoを出力
		if(AC_exi==1) System.out.println("Yes");
		else System.out.println("No");
	}
} 

Measured memory_bytes: 21972
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

int main() {
  int n;
  cin >> n;
  vector<int> p(n);
  for (int i = 0; i < n; i++) {
    cin >> p[i];
  }
  vector<int> temp = p;
  sort(all(p));
  int wrong = 0;
  for (int i = 0; i < n; i++) {
    if (p[i] != temp[i]) wrong++;
  }
  if (wrong <= 2)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> ipair;
typedef tuple<int, int, int> ituple;

// const int INF = INT_MAX;
// const ll INF = LLONG_MAX;
// const int MOD = ((int)1e9 + 7);
// const ld EPS = (1e-10);
#define PI acosl(-1)
#define MAX_N (100000 + 2)

void lcs(){
  string s1, s2;
  cin >> s1 >> s2;
  vector<vector<pair<int, pair<int, int> > > > dp(s1.size()+1, vector<pair<int, pair<int, int> > >(s2.size()+1));
  for(int i = 0; i <= s1.size(); i++) {
    for(int j = 0; j <= s2.size(); j++) {
      if(i==0 || j==0) {
        dp[i][j] = make_pair(0, make_pair(-1, -1));
      } else {
        dp[i][j] = dp[i][j-1];
        if(dp[i][j].first < dp[i-1][j].first) {
          dp[i][j] = dp[i-1][j];
        }
        if(s1[i-1] == s2[j-1] && dp[i][j].first < dp[i-1][j-1].first+1) {
          dp[i][j] = make_pair(dp[i-1][j-1].first+1, make_pair(i-1, j-1));
        }
      }
    }
  }
  vector<char> subseq_stack;
  for(int i=s1.size(), j=s2.size();i>0 && j>0;) {
    pair<int, int> next = dp[i][j].second;
    //make_pair(i,j) = next;
    i = next.first; j = next.second;
    if(i < 0 || j < 0){
      break;
    }
    subseq_stack.push_back(s1[i]); // s1[i] == s2[j]
  }
  while(!subseq_stack.empty()) {
    printf("%c", subseq_stack.back());
    subseq_stack.pop_back();
  }
  printf("\n");
}

void exec(){
  lcs();
}

void solve(){
  int t = 1;
  // scanf("%d", &t);
  for (int i = 0; i < t; i++){
    exec();
  }
}

int main(){
  solve();
  return 0;
}


Measured memory_bytes: 105984
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;
typedef pair<long long ,long long> ii; 	


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	string a;
	cin >> a;
	cout << char(a[0]+1) << endl;
}

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

using namespace std;
#define MOD 1000000007
#define pi 3.1415926535897932384626433832795028841971693993751058209749445923078164062
#define ll long long
#define pb push_back
#define pf push_front
#define mp make_pair
#define mt make_tuple
#define popb pop_back()
#define popf pop_front()
#define ff first
#define ss second
#define vl vector<ll>
#define vi vector<int>
#define vs vector<string>
#define vll vector< pair<ll,ll> >
#define vii vector< pair<int,int> >
#define viii vector< tuple <int,int,int> >
#define vlll vector< tuple <ll,ll,ll> >
#define vvl vector<vector<ll>>
#define vv vector<vector<int>>
#define all(v) v.begin(),v.end()
#define sqrt sqrtl
#define cbrt cbrtl
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mapcl map<char,ll>
#define mapci map<char,int>
#define mapll map<ll,ll>
#define mapii map<int,int>
#define seti set<int>
ifstream fin("input.txt");
ofstream fout("output.txt");

int gcd(int a,int b){while (a&&b)a>b?a%=b:b%=a;return a+b;}
ll pows(int a , int b){ll res=1;for(int i=0; i<b; ++i){res*=a;}return res;}
ll logx(ll base, ll num){int cnt=0;while(num!=1){num/=base; ++cnt;}return cnt;}

vi vis(100001,0);
vi adj[100001];

int main()
{	
    std::ios::sync_with_stdio(false);
    //cin.tie(NULL);
    //cout.tie(NULL);
    int n;cin>>n;
    vi vec;
    for(int i=0; i<n; ++i)
    {
    	int x;cin>>x;vec.pb(x);
    }
    ll cnt=0;
    ll maxi = 0;
    for(int i=0; i<vec.size()-1; ++i)
    {
    	if(vec[i]>=vec[i+1])
    		++cnt;
    	else
    	{
    		maxi=max(cnt,maxi);
    		cnt=0;
    	}
    	if(i==vec.size()-2)
    	{
    		maxi=max(cnt,maxi);
    		cnt=0;
    	}
    }
    cout<<maxi<<"\n";
}

Measured memory_bytes: 3708
##x_1+x_2+...+x_N=K, 0<=x_i<=a_i
N,K=list(map(int,input().strip().split(' ')))
A=list(map(int,input().strip().split(' ')))
dp=[[0] * (K+1)  for i in range(N)]
for i in range(min(A[0]+1,K+1)):
    dp[0][i]=1
for i in range(N):
    dp[i][0]=1
MOD=10**9+7
for i in range(1,N):
    pre=[]
    temp=0
    for j in range(K+1):
        temp+=dp[i-1][j]
        temp%=MOD
        pre+=[temp]
        
    for j in range(1,K+1):
        ## j-A[i],j-(A[i]-1),...,j
        ## pre[j]-pre[j-A[i]-1]
        temp=0
        if j-A[i]>0:
            temp=pre[j-A[i]-1]
        dp[i][j]=pre[j]-temp
        dp[i][j]%=MOD

print(dp[-1][K])
        
        




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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 333;
int n;
ll a[maxn][maxn];

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

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

  for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
      for (int k=0; k<n; k++) {
	if (a[i][k]+a[k][j] < a[i][j]) out(-1);
      }
    }
  }

  ll tot = 0;
  for (int i=0; i<n; i++) {
    for (int j=i+1; j<n; j++) {
      bool flag = true;
      for (int k=0; k<n; k++) {
	if (i!=k && k!=j && a[i][k]+a[k][j] == a[i][j]) {
	  flag = false; break;
	}
      }
      if (flag) {
	tot += a[i][j];
      }
    }
  }

  cout<<tot<<endl;
  

  return 0;
}


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

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a) {
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
    out<<'[';
    for(const T &i: a) out<<i<<',';
    out<<']';
    return out;
}
template<class T>
ostream &operator <<(ostream& out, const set<T>& a) {
    out<<'{';
    for(const T &i: a) out<<i<<',';
    out<<'}';
    return out;
}
template<class T, class S>
ostream &operator <<(ostream& out, const map<T,S>& a) {
    out<<'{';
    for(auto &i: a) out<<i<<',';
    out<<'}';
    return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

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

    ll k, x, y;
    cin >> k >> x >> y;

    if(k%2==0 && (x+y+200000)%2==1) {
        cout << "-1" << endl;
        return 0;
    }

    ll nx = 0, ny = 0;
    vector<PII> ans;
    while(x != nx || y != ny) {
        ll dx = abs(nx-x), dy = abs(ny-y);
        ll fx = nx<x?1:-1, fy = ny<y?1:-1;

        if(dx+dy == k) nx = x, ny = y;
        else if(dx+dy>=2*k || (k%2 && (dx+dy)%2)) {
            ll move = min(k, dx);
            nx += fx * move;
            ny += fy * (k - move);
        } else {
            ll move = (2*k-dx-dy)/2, mx, my;
            if(dx <= k-move) {
                mx = dx + move;
                my = k - mx;
            } else {
                my = dy + move;
                mx = k - my;
            }
            nx += fx * mx;
            ny += fy * my;
        }
        ans.emplace_back(nx, ny);
    }

    cout << ans.size() << endl;
    for(auto p: ans) cout << p.first << " " << p.second << '\n';

    return 0;
}


Measured memory_bytes: 6128
object Main extends App {
  var i = 0
  val sb = StringBuilder.newBuilder
  for(x <- io.Source.stdin.getLines() if x != "0") {
    i += 1
    // sb.append("Case ").append(i).append(": ")
    //   .append(x).append('\n')
    sb.append(s"Case $i: $x\n")
  }
  print(sb.toString())
}


Measured memory_bytes: 55660
from collections import deque
h, w =  map(int, input().split())
a = [list(input()) for i in range(h)]
mv = [[1, 0], [0, 1]]

sx, sy = 0, 0
gx, gy = h - 1, w - 1
nxt = deque()
nxt.appendleft([sx, sy])

for i in range(h - 1):
    count = 0
    check = 0
    count2 = 0
    for j in range(w):
        if a[i][j] == "#":
            if a[i][j] == a[i + 1][j]:
                count += 1
                if check == 0:
                    check = 1
                    if count2 > 0:
                        count = 2
                        break
        else:
            if a[i + 1][j] == "#":
              count2 += 1  

    if count > 1:
        nxt.clear()
        break

flag = 0
while len(nxt) > 0:
    tmp = nxt.pop()
    nwx, nwy = tmp[0], tmp[1]
    if nwx == gx and nwy == gy:
        flag = 1
        break
    count = 0
    for i in range(2):
        tmpx = mv[i][0] + nwx
        tmpy = mv[i][1] + nwy
        if tmpy < w and tmpx < h:
            if a[tmpx][tmpy] == '#':
                nxt.appendleft([tmpx, tmpy])
                count += 1
    if count > 1:
        break

if flag:
    print("Possible")
else:
    print("Impossible")

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
//typedef vector<unsigned int>vec;
//typedef vector<ll>vec;
//typedef vector<vec> mat;
typedef vector<vector<int>> Graph;

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll  MOD = 1000000007;
const double PI = acos(-1.0);
const double EPS = 1e-10;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> P(N), mi(N+1,INF);
    mi[0] = INF;
    REP(i,N){
        cin >> P[i];
        mi[i+1] = mi[i];
        chmin(mi[i+1], P[i]);
    }
    int cnt = 0;
    
    REP(i,N){
        if(P[i] <= mi[i+1]) cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <iomanip> // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple> // get<n>(xxx)
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set> // S.insert(M);
// if (S.find(key) != S.end()) { }
// for (auto it=S.begin(); it != S.end(); it++) { }
// auto it = S.lower_bound(M);
#include <random> // random_device rd; mt19937 mt(rd());
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib> // atoi(xxx)
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.
// insert #if<tab> by my emacs. #if DEBUG == 1 ... #end

typedef long long ll;

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

// const int C = 1e6+10;
// const ll M = 1000000007;

int N;
ll K;
ll w[100010];
ll d[100010];

ll count(int ind, ll x) {
  if (x < w[ind]) return 0;
  return (x - w[ind])/d[ind] + 1;
}

ll count(ll x) {
  ll ans = 0;
  for (auto i = 0; i < N; ++i) {
    ans += count(i, x);
  }
  return ans;
}

ll heikin(ll x, ll y) {
  ll ans = 0;
  ll amari = 0;
  ans += x/2;
  ans += y/2;
  amari += x%2;
  amari += y%2;
  ans += amari/2;
  return ans;
}

int main () {
  cin >> N >> K;
  for (auto i = 0; i < N; ++i) {
    cin >> w[i] >> d[i];
  }
  ll lb = 0;
  ll ub = 1999999999000000000+10;
  while (ub - lb > 1) {
    ll t = heikin(lb, ub);
    if (count(t) >= K) {
      ub = t;
    } else {
      lb = t;
    }
  }
  cout << ub << endl;
}


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

using namespace std;

typedef long long ll;

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

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

const int MOD = 1000000007;
const int MAX_N = 100000;

// auto mod int
// ref. https://github.com/atcoder-live/library/blob/master/mint.cpp
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= MOD;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime MOD
  mint inv() const {
    return pow(MOD-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

mint comb(const ll n, const ll k) {
    mint ans(1);
    for (int i = 0; i < k; i++) {
        ans = ans * (n - i);
    }
    for (int i = 0; i < k; i++) {
        ans = ans / (i + 1);
    }
    return ans;
}

int main(void) {
    int n, a, b;
    cin >> n >> a >> b;

    mint ans(2);
    ans = ans.pow(n);

    ans = ans - comb(n, a) - comb(n, b) - mint(1);
    cout << ans.x << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A, B, C;
		A = sc.nextInt();
		B = sc.nextInt();
		C = sc.nextInt();

		for (int i = 0; i <= B * A; i += A) {
			if(i % B == C) {
				System.out.print("YES");
				return;
			}
		}
		System.out.print("NO");
	}
}


Measured memory_bytes: 21844
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main()
{
	//freopen("C.in","r",stdin);
	int a,b,c;
	cin >> a >> b >> c;
	int m = max(max(a,b),c);
	while (true)
	{
		int t = 3*m-a-b-c;
		if (t % 2 ==0)
		{
			cout << t / 2 << endl;
			break;
		}
		m++;
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<x<<endl
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;
const ll LINF = LLONG_MAX;
const int INF = INT_MAX;
const double PI=acos(-1);
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 main(){
	ll n,d; cin>>n>>d;
	ll ans=0;
	rep(i,0,n){
		ll x,y; cin>>x>>y;
		if(x*x + y*y <= d*d){
			ans++;
		}
	}
	cout<<ans<<endl;
}

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

#define LL long long
#define LD long double
#define Mod 1000000007
#define L_Mod 17100000013

const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const double PI = 3.1415926535;

#define NO_TLE std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define ree(a,n) memset(a,n,sizeof(a));

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define red(i,l,u) for(int (i)=(int)(l);(i)>=(int)(u);--(i))

int main()
{
    int h,a;
    cin>>h>>a;
    cout<<(h+a-1)/a<<endl;
    return 0;
}




















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

int a[100002], b[100002];
signed main(){
	int c; scanf("%lld", &c);
	a[0] = 0; b[0] = LLONG_MAX / 3;
	a[c + 1] = LLONG_MAX / 3; b[c + 1] = 0;
	for (int d = 0; d < c; d++) {
		scanf("%lld", &a[d+1]);
	}
	for (int d = 0; d < c; d++) {
		scanf("%lld", &b[d+1]);
	}
	if (a[c] != b[1]) { puts("0"); return 0; }
	int ans = 1;
	for (int i = 1; i <= c; i++) {
		if (a[i - 1] != a[i]) {
			if (b[i] != b[i + 1]) {
				if (a[i] != b[i]) { puts("0"); return 0; }
			}
			else {
				if (a[i] > b[i]) { puts("0"); return 0; }
			}
		}
		else {
			if (b[i] == b[i + 1]) {
				ans *= min(a[i], b[i]);
				ans %= mod;
			}
			else {
				if (a[i] < b[i]) { puts("0"); return 0; }
			}
		}
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 1792
/*input
1
1

*/
 
/*
                                                    ______________
                                                          |       )
                                                          |   )   /
                                                          |______/
                                                    |     |      \
                                                    |     |   )   \
                                                    |_____|_______)
 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <iomanip>
#include <fstream>
#include <stack>

using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll , ll> PLL;
typedef long double ld;
 
#define pb push_back
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
int mod = 1000000007;
const int inf = 1034567891;
const ll LL_INF = 1234567890123456789ll;
#define PI 3.14159265
#define endl '\n'
#define F first
#define S second
#define debug(x) cout << #x << " = " << x << endl;
#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 
#define out(container) for (auto it : container) cout << it << " "; cout << endl;
 
 
template < typename T > T GCD(T a, T b)            { ll t; while(a) { t = a; a = b % a; b = t; } return b; }
template < typename T > string toString(T a)       { return to_string(a); }
template < typename T > void toInt(string s, T &x) { stringstream str(s); str >> x;}
inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}
inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % mod;}
inline int powr(int a, ll b){
  int x = 1 % mod;
  while(b){
    if(b & 1) x = mul(x, a);
    a = mul(a, a);
    b >>= 1;
  }
  return x;
}
inline int inv(int a){ return powr(a, mod - 2);}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int n;
  cin >> n;
  vector<int> vec;
  int v;
  int ans = 0;
  for (int i = 0; i < n; i++) {
    cin >> v;
    vec.pb(v);
    if (i % 2 == 0 && v % 2)
      ans++;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3652
import java.util.Scanner;

public class Main {
	int n;
	int s[];
	int q;
	int t[];
	public static void main(String args[]) {
		new Main().run();
	}
	Main() {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		s = new int[n];
		for (int i = 0; i < n; i++) {
			s[i] = scan.nextInt();
		}
		q = scan.nextInt();
		t = new int[n];
		for (int i = 0; i < q; i++) {
			t[i] = scan.nextInt();
		}
		scan.close();
	}
	public void run() {
		int cnt = 0;
		for (int j = 0; j < q; j++) {
			int left = 0;
			int right = n;
			while (left < right) {
				int mid = (left + right) / 2;
				if (s[mid] == t[j]) {
					cnt++;
					break;
				}
				if (s[mid] <= t[j]) {
					left = mid + 1;
				} else {
					right = mid;
				}
			}
		}
		System.out.println(cnt);
	}
}



Measured memory_bytes: 67720
#include <bits/stdc++.h>
#define rep(i,n) for (int i = (0); i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout << #x << " = " << (x) << endl
#define show2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
#define show3(x,y,z) cout << #x << " = " << (x) << ", " << #y << " = " << (y) <<  ", " << #z << " = " << (z) << endl
#define showv(v) rep(i,v.size()) printf("%d%c", v[i], i==v.size()-1?'\n':' ')
#define showv2(v) rep(j,v.size()) showv(v[j])
#define showt(t,n) rep(i,n) printf("%d%c", t[i], i==n-1?'\n':' ')
#define showt2(t,r,c) rep(j,r) showt(t[j],c)
#define showvp(p) rep(i,p.size()) printf("%d %d\n", p[i].first, p[i].second);
#define printv(v) rep(i,v.size()) printf("%d\n", v[i])
#define printt(t,n) rep(i,n) printf("%d\n", t[i])
#define incl(v,x) find(rng(v),x)!=v.end()
#define incls(s,c) s.find(c)!=string::npos
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define bit(n,k) ((n>>k)&1) // nのk bit目
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vs = vector<string>;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using vp = vector<P>;
using vt = vector<T>;
const int mod = 1000000007;
const double EPS = 1e-9;
//const long double EPS = 1e-14;
const int INF = (1<<30)-1;
//const ll INF = (1LL<<62)-1;
#define dame { puts("No"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
inline int in() { int x; scanf("%d",&x); return x;}
//template<class T = int> inline T in() { T x; cin >> x; return (x);}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main () {
  int n;
  cin >> n;
  vi x(n);
  rep(i,n) cin >> x[i];
  
  vi xs = x;
  sort(xs.rbegin(), xs.rend());

  int ml = xs[(n-1)/2];
  int mr = xs[(n-1)/2+1];
  //show2(ml,mr);

  rep(i,n) {
    int ans;
    if (x[i] <= mr) ans = ml;
    else ans = mr;
    printf("%d\n", ans);
  }
  return 0;
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REV(c) reverse(ALL(c))
#define sz(v) (int)v.size()
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
const char EOL = '\n';
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

void solve() {
    int n;
    cin >> n;
    vector<pair<int, int>> v(n);
    int x, l;
    REP(i, n) {
        cin >> x >> l;
        v[i] = make_pair(x - l, x + l);
    }
    sort(ALL(v), [&](auto p1, auto p2){return p1.second < p2.second;});
    int ans = 0;
    int prev = -INF;
    REP(i, n) {
        // cout << v[i].first << "/" << v[i].second << EOL;
        if (prev <= v[i].first) {
            ans++;
            prev = v[i].second;
        }
    }
    cout << ans << EOL;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
    int A, B, C, D, N, ans=0;
    vector<int> V(3);
    char tmp, tmp2;
    string S, S2;
    bool flag=true;
    
    cin >> A >> B >> C;
    
    ans = min(A*B, C);
    cout << ans << endl;

    // if(S[1]==S[2] &&(S[0]==S[1] | S[2]==S[3]))
    // 	cout << "Yes" <<endl;
    // else
    // 	cout << "No" <<endl;

    // string S;
    // cin >>S;
    // cout << S + "pp"<<endl;
    // if(A+B==C || B+C==A || C+A==B)
    // 	puts("Yes");
    // else
    // 	puts("No");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
const int INF{int(1e9)};

int main()
{
  string s;
  cin >> s;
  if (s == "ABC")  cout << "ARC" << endl;
  else   cout << "ABC"  << endl;
}

Measured memory_bytes: 3624
#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <string>
#include <vector>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(a) begin(a),end(a)
typedef long long ll;
typedef pair<int,int> P;
const int inf=1e+9;
const ll mod=1000000007;
const double PI=3.14159265358979323846;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
ll gcd(ll a, ll b){
  if (b==0) return a;
  else return gcd(b,a%b);
}
int cans(bool f){
  if(f) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

#define NIL -1
#define MAX 100005

struct Node{
  int p,l,r;
};


Node T[MAX];
int n,D[MAX],H[MAX];



void setDepth(int u, int d) {
  if(u == NIL) return;
  D[u] = d;
  setDepth(T[u].r,d+1);
  setDepth(T[u].l,d+1);
}

int setHeight(int u) {
  int h1=0, h2=0;
  if(T[u].r != NIL) h1 = setHeight(T[u].r) + 1;
  if(T[u].l != NIL) h2 = setHeight(T[u].l) + 1;
  return H[u] = max(h1,h2);
}

int getSibling(int u) {
  if(T[u].p == NIL) return NIL;
  if(T[T[u].p].l != u && T[T[u].p].l != NIL) return T[T[u].p].l;
  if(T[T[u].p].r != u && T[T[u].p].r != NIL) return T[T[u].p].r;
  return NIL;
}


void print(int u) {
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].p);
  printf("sibling = %d, ",getSibling(u));
  int deg = 0;
  if(T[u].r != NIL) deg++;
  if(T[u].l != NIL) deg++;
  printf("degree = %d, ",deg);
  printf("depth = %d, ",D[u]);
  printf("height = %d, ",H[u]);
  
  if(T[u].p == NIL) printf("root\n");
  else if(T[u].r == NIL && T[u].l == NIL) printf("leaf\n");
  else printf("internal node\n");
}


void preParse(int u) {
  if(u == NIL) return;
  printf(" %d",u);
  preParse(T[u].l);
  preParse(T[u].r);
}

void inParse(int u) {
  if(u == NIL) return;
  inParse(T[u].l);
  printf(" %d",u);
  inParse(T[u].r);
}
void postParse(int u) {
  if(u == NIL) return;
  postParse(T[u].l);
  postParse(T[u].r);
  printf(" %d",u);
}


int main() {
  int v,l,r;
  int N;
  cin >> N;
  rep(i,N) T[i].l = T[i].r = T[i].p = NIL;
  rep(i,N) {
    cin >> v >> l >> r;
    T[v].l = l;
    T[v].r = r;
    if(l != NIL) T[l].p = v;
    if(r != NIL) T[r].p = v;
  }
  int root; 
  rep(i,N) if(T[i].p == NIL) root = i;
  cout << "Preorder" << endl;
  preParse(root);
  cout << endl;
  cout << "Inorder" << endl;
  inParse(root);
  cout << endl;
  cout << "Postorder" << endl;
  postParse(root);
  cout << endl;
  return 0;
}






Measured memory_bytes: 3228
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <queue>
#include <map>

#define rep(i,n) for(int i = 0; i < n; i++)
#define rep1(i,n) for(int i = 1; i <= n; i++)
#define co(x) cout << x <<endl
#define cs(x) cout << x <<" "
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
using namespace std;

int main()
{
	int N;
	cin >> N;
	map<int, int> a;
	rep(i, N) { int tmp; cin >> tmp; a[tmp]++; }
	int ans = 0;
	for (auto x : a) { if (x.second % 2 == 1)ans++; }
	co(ans);
	return 0;
}

Measured memory_bytes: 4864
#include "bits/stdc++.h"
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

using ll = long long;

ll gcd(ll x, ll y) {
    if (y == 0) return x;
    return gcd(y, x % y);
}

string solve(ll A, ll B, ll C, ll D) {
    if (A < B || B > D) return "No";
    if (B == D) {
        if (A % B <= C) return "Yes";
        return "No";
    }
    if (B < C + 2) return "Yes";
    ll dmin = A - B;
    ll dmax = A - C - 1;
    ll g = gcd(B, D);
    if (dmin / g < dmax / g) return "No";
    return "Yes";
}

int main() {
    int T;
    cin >> T;
    ll A, B, C, D;
    rep(i, T) {
        cin >> A >> B >> C >> D;
        cout << solve(A, B, C, D) << endl;
    }
}

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

struct Edge{
    int from,to;
    int cost;    
};
int main(){
    int l;
    cin>>l;
    l--;
    vector<Edge> res;
    int fr=19;
    int th=1;
    res.push_back(Edge{1,20,l});
    while(fr>=3 && l){
        int frr=fr;
        if(l/5==0){
            frr=1;
        }
        else{
            if(l*th<=1e6) res.push_back(Edge{1,fr,l/5*th*5});
        }
        for(int i=0;i<l%5;i++){
            if(i*th<=1e6) res.push_back(Edge{frr,fr+1,i*th});
        }
        
        if(frr!=1){
            res.push_back(Edge{fr-1,frr,0});
            for(int i=l%5;i<5;i++){
                if(i*th<=1e6) res.push_back(Edge{fr-1,fr+1,i*th});
            }
        }
        th*=5;
        fr-=2;
        l/=5;
    }
    cout<<20<<" "<<res.size()<<endl;
    for(int i=0;i<res.size();i++){
        cout<<res[i].from<<" "<<res[i].to<<" "<<res[i].cost<<endl;
    }
    return 0;
}


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

using namespace std;

typedef long long ll;

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

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

int main(void) {
    int A, P;
    cin >> A >> P;

    cout << (A * 3 + P) / 2 << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int n, a[1111111], c, g[20];
int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	g[0] = 1; c = 0;
	while(true) {
		g[c + 1] = g[c] * 3 + 1;
		if(g[++c] >= n) break;
	}
	int ret = 0;
	for(int i = c - 1; i >= 0; i--) {
		for(int j = g[i]; j < n; j++) {
			int v = a[j], w = j - g[i];
			while(w >= 0 && a[w] > v) {
				a[w + g[i]] = a[w];
				w -= g[i];
				ret++;
			}
			a[w + g[i]] = v;
		}
	}
	printf("%d\n", c);
	for(int i = c - 1; i >= 0; i--) printf(i ? "%d " : "%d\n", g[i]);
	printf("%d\n", ret);
	for(int i = 0; i < n; i++) printf("%d\n", a[i]);
	return 0;
}

Measured memory_bytes: 7036