akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;
constexpr double PI = 3.14159265358979323846;
constexpr int di[] = {0, 0, 1, -1};
constexpr int dj[] = {1, -1, 0, 0};

int n, m;

bool c[710][710];

V g[710];

int color[710];

vector<P> p;

bool check;

void dfs(int s, int t)
{
    if (color[s] != -1)
    {
        if (color[s] != t)
            check = false;
        return;
    }

    color[s] = t;

    if (t == 0)
        p[p.size() - 1].first++;
    else
        p[p.size() - 1].second++;

    /*
    for (int i = 1; i <= n; i++)
    {
        if (!c[i][s])
            dfs(i, 1 - t);
    }
    */

    for (int i : g[s])
        dfs(i, 1 - t);

    return;
}

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

    cin >> n >> m;

    REP(i, n)
    REP(j, n)
    c[i + 1][j + 1] = i + 1 == j + 1;

    REP(i, m)
    {
        int a, b;
        cin >> a >> b;

        c[a][b] = true;
        c[b][a] = true;
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            if (!c[i][j])
            {
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }

    memset(color, -1, sizeof(color));

    check = true;

    while (true)
    {
        bool ch = false;
        for (int i = 1; i <= n; i++)
        {
            if (color[i] == -1)
            {
                p.push_back({0, 0});
                dfs(i, 0);
                ch = true;
            }
        }

        if (!ch)
            break;
    }

    if (!check)
    {
        cout << -1 << endl;
        return 0;
    }

    bool dp[2][1000];

    auto *cur = dp[0];
    auto *nex = dp[1];

    fill(cur, cur + n + 1, false);
    fill(nex, nex + n + 1, false);

    cur[0] = true;

    V num;

    REP(j, p.size())
    {
        for (int i = 0; i < 1000; i++)
        {
            if (!cur[i])
                continue;

            if (i + p[j].first < 1000)
                nex[i + p[j].first] = true;

            if (i + p[j].second < 1000)
                nex[i + p[j].second] = true;
        }

        swap(cur, nex);
        fill(nex, nex + n + 1, false);
    }

    int res = INT_MAX;

    for (int i = 0; i <= n; i++)
    {
        if (!cur[i])
            continue;

        int tmp = (i * (i - 1) / 2) + ((n - i) * (n - i - 1) / 2);
        res = min(res, tmp);
    }

    cout << res << endl;

    return 0;
}

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

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

using namespace std;
using lint=long long;

int main(){
	int n;
	string s; cin>>n>>s;

	lint ans=0;
	rep(S,1<<n){
		string t1,t2;
		rep(i,n){
			if(S>>i&1) t1+=s[i];
			else       t2+=s[i];
		}
		reverse(t1.begin(),t1.end());
		reverse(t2.begin(),t2.end());

		int m=t1.length();
		lint dp[19][19]={}; // dp[i][j] := t1[0,i) と t2[0,j) を使って s[n,n+i+j) を作る方法の数
		dp[0][0]=1;
		rep(k,n+1){
			rep(i,k+1){
				int j=k-i;
				if(i< m  && s[n+k]==t1[i]) dp[i+1][j]+=dp[i][j];
				if(j<n-m && s[n+k]==t2[j]) dp[i][j+1]+=dp[i][j];
			}
		}
		ans+=dp[m][n-m];
	}
	cout<<ans<<'\n';

	return 0;
}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, C;
  cin >> N >> C;
  int D[30][30], grid[N][N];
  for (int i = 0; i < C; i++) {
    for (int j = 0; j < C; j++) {
      cin >> D[i][j];
    }
  }
  int cost[3][30] = {};
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cin >> grid[i][j];
      cost[(i + j) % 3][--grid[i][j]]++;
    }
  }
  int minn = 1 << 29;
  for (int x = 0; x < C; x++) {
    for (int y = 0; y < C; y++) {
      if (x == y) continue;
      for (int z = 0; z < C; z++) {
        if (x == z || y == z) continue;
        int t = 0;
        for (int i = 0; i < C; i++) {
          t += cost[0][i] * D[i][x];
          t += cost[1][i] * D[i][y];
          t += cost[2][i] * D[i][z];
        }
        minn = min(minn, t);
      }
    }
  }
  cout << minn << '\n';
  return 0;
}


Measured memory_bytes: 1280
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

x=int(input())
x-=400
print(8-x//200)

Measured memory_bytes: 68300
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def SS(): return map(str,sys.stdin.readline().rstrip().split())
def II(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

N,M,X = II()
A = LI()

print(min(len([a for a in A if a < X]),len([a for a in A if a > X])))

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

int main() {
  int N,a,b;
  a = 0;
  cin >> N;
  b = N;
  rep(i,8) {
    a = a + N%10;
  	N = N/10;
  }
  if(b%a == 0) {
  	cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

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

int is_right_triangle(int min, int mid, int max) {
  return max * max == min * min + mid * mid;
}

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

  for (auto i = 0; i < ntriangle; i++) {
    std::vector<int> tri;
    for (auto j = 0; j < 3; j++) {
      int len;
      std::cin >> len;
      tri.push_back(len);
    }
    std::sort(tri.begin(), tri.end());
    if (is_right_triangle(tri[0], tri[1], tri[2])) {
      std::cout << "YES\n";
    } else {
      std::cout << "NO\n";
    }
  }
  return 0;
}

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

int main()
{
    long long n,a,b;
    std::cin >> n >> a >> b;
    long long res;
    //偶数のときは近づくだけ
    if(std::abs(b-a) % 2 == 0){
        res = std::abs(a - b) / 2;
    }else{
        if(std::max((a - 1) , (b - 1)) < std::max((n - a) , (n - b))){ //左端
            res = (((a - 1) + (b - 1)) + 2 - 1) / 2;
        }else{
            res = (((n - a) + (n - b)) + 2 - 1) / 2;
        }
    }
    std::cout << res << std::endl;
}

Measured memory_bytes: 256
n = int(input())
w_list = list(map(int, input().split()))
sum_all = sum(w_list)
sum_acm = 0
for i in range(len(w_list)):
  sum_tmp = sum_acm + w_list[i]
  if sum_tmp > sum_all / 2:
    if sum_tmp - (sum_all - sum_tmp) < (sum_all - sum_acm) - sum_acm:
      print(sum_tmp - (sum_all - sum_tmp))
    else:
      print((sum_all - sum_acm) - sum_acm)
    break
  sum_acm = sum_tmp

Measured memory_bytes: 3064
//#include<iostream>
//#include<sstream>
//#include<cstdio>
//#include<cmath>
//#include<cstring>
//#include<cctype>
//#include<string>
//#include<vector>
//#include<list>
//#include<set>
//#include<map>
//#include<queue>
//#include<stack>
//#include<algorithm>
//#include<functional>
//#include<bits/stdc++.h> 
//using namespace std; 
//
//int main()
//{
//    ios_base::sync_with_stdio(false);
//    cin.tie(0);
//    cout.tie(0);
//  
//    string s1, s2;
//    cin>>s1;
//    s2=s1;
//    int i, j=0, c=0;
//    for(i=s1.length()-1; i>=s1.length()/2; i--)
//    {
//    	if(s1[i]!=s2[j])c++;
//    	j++;
//	}
//	
//    cout<<c<<endl;
//    
//    return 0;
//}
// C++ Implementation of the above approach 
#include<bits/stdc++.h> 
using namespace std; 

// Function to find the minimum number 
// character change required 

void change(string s) 
{ 

	// Finding the length of the string 
	int n = s.length(); 

	// To store the number of replacement operations 
	int cc = 0; 

	for(int i=0;i<n/2;i++) 
	{ 

		// If the characters at location 
		// i and n-i-1 are same then 
		// no change is required 
		if(s[i]== s[n-i-1]) 
			continue; 

		// Counting one change operation 
		cc+= 1; 

		// Changing the character with higher 
		// ascii value with lower ascii value 
		if(s[i]<s[n-i-1]) 
			s[n-i-1]= s[i] ; 
		else
			s[i]= s[n-i-1] ; 
	} 
	printf("%d\n", (cc)) ; 
	//cout<<s<<endl; 
} 
// Driver code 
int main() 
{ 
string s;
cin>>s; 
change((s)); 
return 0; 
} 
//contributed by Arnab Kundu 


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

#define pb push_back
#define mp make_pair
#define ll long long int
#define all(x) x.begin(), x.end()

long long int MOD = (int)1e9 + 7;

void solve() {

    int n, m;
    cin >> n >> m;
    unordered_set<int> arr;
    for (int i = 0; i < m; i++)
    {
        int tmp; cin >> tmp;
        arr.insert(tmp);
    }

    vector<long long int> w(n + 5, 0);
    w[0] = 1;

    for (int i = 1; i <= n; i++)
    {
        if(arr.find(i) != arr.end()) continue;

        if(i-1 >= 0 && arr.find(i-1) == arr.end()) {
            w[i] += w[i-1];
        } 

        if(i-2 >= 0 && arr.find(i-2) == arr.end()) {
            w[i] += w[i-2];
        } 

        w[i] %= MOD;
    }

    cout << w[n] << "\n";
    
     


}

int main() {
    ios_base::sync_with_stdio(false);

    solve();
    return 0;
}

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

int main(){
  int n,k;
  cin>>n>>k;
  cout<<(n-1+k-2)/(k-1);
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

# input
S = input()

# solve
is_YYMM = False
is_MMYY = False

if '00' <= S[:2] and ('01' <= S[2:] and S[2:] <= '12'):
    is_YYMM = True
if ('01' <= S[:2] and S[:2] <= '12') and '00' <= S[2:]:
    is_MMYY = True

# output
if is_YYMM and is_MMYY:
    print('AMBIGUOUS')
elif is_YYMM:
    print('YYMM')
elif is_MMYY:
    print('MMYY')
else:
    print('NA')


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

int main()
{
  string s;
  cin>>s;
  ll sum=0;
  
  for(ll i=0; i<s.length(); i++)
  {
    sum += (s[i]-48);
  }
  
  if(sum%9==0)
    cout<<"Yes\n";
  else
    cout<<"No\n";
}

Measured memory_bytes: 3692
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,n,m,i,j=0,k=10000;
	int a1=700;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++)
	{
		scanf("%d",&a);
		if(a<k)
		{
			k=a;
		}
		j+=a;
	}
	j=m-j;
	if(j>0)
	{
		n+=j/k;
	}
	printf("%d",n);
	return 0;
 } 

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long int ll;
typedef vector<pair<ll,ll> > Q;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
const ll inf=1e9+7;

int n,m;
int k[10],s[10][10];
int p[10],ans=0;

int main(){
  cin>>n>>m;

  rep(i,m){
    cin>>k[i];
    rep(j,k[i]) cin>>s[i][j];
  }
  rep(i,m) cin>>p[i];

  for(int bit=0;bit<(1<<n);bit++){
    int cnt2=0;
    rep(i,m){
      int cnt=0;
      rep(j,n){
        int tmp=s[i][j];
        if(bit & (1<<tmp)) cnt++;
      }
      if(cnt%2==p[i]) cnt2++;
  }
  if(cnt2==m) ans++;
}
cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define PB push_back
#define MP make_pair
#define pri 1000000007
using namespace std;
void run(){
	
	ll a,b,c;
	cin>>a>>b>>c;
	if(a==b&&b==c){cout<<"Yes";}
	else cout<<"No";
	
}
int main() {
	ll t=1;
	//cin>>t;
	for(ll i=0;i<t;i++)run();
	// your code goes here
	return 0;
}

Measured memory_bytes: 256
n, a, b, c, d = map(int, input().split())
s = input()
if "##" in s[a-1:c] or "##" in s[b-1:d]:
    print("No")
else:
    if c < d:
        print("Yes")
    else:
        if "..." in s[b-2:d+1]:
            print("Yes")
        else:
            print("No")

Measured memory_bytes: 3572
n, m, q = map(int,input().split())
a, b, c, d = [0] * q,[0] * q, [0] * q, [0] * q

for i in range(q):
    a[i], b[i], c[i], d[i] = map(int,input().split())
    a[i] -= 1
    b[i] -= 1

def score(z):
    tmp = 0
    for ai, bi, ci, di in zip(a, b, c, d):
        if z[bi] - z[ai] == ci:
            tmp += di
    return tmp

def dfs(a):
    if len(a) == n:
        return score(a)
    ans = 0
    prev_last = a[-1] if len(a) > 0 else 0
    for v in range(prev_last,m):
        a.append(v)
        ans = max(ans,dfs(a))
        a.pop()
    return ans

print(dfs([]))

Measured memory_bytes: 80056
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <numeric>
using namespace std;
typedef pair<int, int> PII;
int main(){
  int N;
  while(true){
    cin >> N;
    if(N == 0){
      break;
    }
    vector<PII> rw(N);
    for(int i = 0; i < N; ++i){
      cin >> rw[i].first >> rw[i].second;
    }
    sort(rw.begin(), rw.end(), greater<PII>());
    int p_s = 0;
    for(int i = 1; i < N; ++i){
      p_s += rw[i].first;
    }
    int r_time = 0, w_time = 0;
    if(p_s > rw[0].first){      
      r_time = rw[0].first + p_s;
      for(int i = 0; i < N; ++i){
	w_time += rw[i].second;
      }
    }
    else{
      r_time = rw[0].first * 2;
      int rem = rw[0].first - p_s;
      bool table[rem+1];
      fill_n(table, rem+1, false);
      table[0] = true;
      int max_w = 0;
      for(int i = 1; i < N; ++i){
	  int w = rw[i].second;
	  for(int j = rem; j >= w; --j){
	    if(table[j-w]){
	      table[j] = true;	    
	      max_w = max(max_w, j);
	  }
	}
      }
      w_time = 0;
      for(int i = 0; i < N; ++i){
	w_time += rw[i].second;
      }
      w_time -= max_w;
    }    
    cout << r_time + w_time << endl;
  }
  return 0;
}

Measured memory_bytes: 1204
import java.util.*;
import java.io.*;

public class Main {
    private static HashMap<Integer, List<Integer>> graph;
    private static HashMap<Integer, List<Integer>> temp;
    public static void main(String[] args) throws Exception{
        FastScanner scanner = new FastScanner();
        int V = scanner.nextInt();
        int E = scanner.nextInt();

        graph = new HashMap<>(V);
        temp = new HashMap<>(V);
        for(int i = 0; i < V; ++i){
            graph.put(i, new LinkedList<>());
            temp.put(i, new LinkedList<>());
        }

        for(int i = 0; i < E; ++i){
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            graph.get(u).add(v);
            temp.get(v).add(u);
        }

        LinkedList<Integer> queue = new LinkedList<>();
        for(int i = 0; i < V; ++i){
            if(temp.get(i).isEmpty()){
                queue.add(i);
            }
        }

        List<Integer> result = new ArrayList<>(V);
        while(!queue.isEmpty()){
            Integer u = queue.remove();
            result.add(u);
            for(Integer v : graph.get(u)){
                temp.get(v).remove(u);
                if(temp.get(v).isEmpty()){
                    queue.add(v);
                }
            }
        }

        PrintWriter printWriter = new PrintWriter(System.out);
        for(Integer n : result){
            printWriter.println(n);
        }
        printWriter.flush();
    }

    private static class FastScanner{
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte() {
            if(ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch(IOException e) {
                    e.printStackTrace();
                }
                if(buflen <= 0) {
                    return false;
                }
            }
            return true;
        }
        private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
        private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
        private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
        public boolean hasNext() { skipUnprintable(); return hasNextByte();}
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public int nextInt(){
            return Integer.parseInt(next());
        }
        public double nextDouble(){
            return Double.parseDouble(next());
        }
    }
}

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

dlist = list(map(int,input().split()))
lendlist = len(dlist)
ans = -1
dictdist = {}

for i in range(100001):
    dictdist[i] = 0

for i in range(lendlist):
    if i==0:
        if dlist[i]!=0:
            ans = 0
            
    elif i!=0:
        if dlist[i]==0:
            ans = 0
        else:
            dictdist[dlist[i]] += 1
                
if ans != 0:
    temp = 1
    for k,v in dictdist.items():
        if k != 1:
            for _ in range(v):
                temp *= dictdist[k-1]
                temp %= 998244353
                #print(temp)
    ans = temp
    
print(ans)

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

using namespace std;
using ll = long long;
using ii = pair<ll, ll>;

const int MAX { 200010 };
const ll MOD { 1000000007 }, oo { 1LL << 62 };

ll solve(int N, const vector<ll>& xs)
{
    return 0;
}

int main()
{
    ios::sync_with_stdio(false);

    string S;
    cin >> S;

    cout << (S == "AAA" or S == "BBB" ? "No" : "Yes") << '\n';

    return 0;
}


Measured memory_bytes: 3656
#code festival2016-B
n,a,b = map(int,input().split())
s = input()
c = a+b
kaigai = []
yosen = []

for i in s:
    if i == 'a':
        if len(yosen) < c:
            print('Yes')
            yosen.append(i)
        else:
            print('No')
    elif i == 'b':
        if len(yosen) < c and len(kaigai) < b:
            print('Yes')
            yosen.append(i)
            kaigai.append(i)
        else:
            print('No')
            
        
    else:
        print('No')

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

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string s;
	cin >> s;
	for (int i = 0 ; i < s.size() ; i++)
	{
		if (s[i] != '?') cout<<s[i];
		else cout<<'D';
	}
	cout<<endl;
}

Measured memory_bytes: 3792
#!/usr/bin/env python3
import sys


def solve(n: int, p: "List[int]"):
    count = 0
    for i in range(n - 2):
        arr = sorted([p[i], p[i+1], p[i+2]])
        if arr[1] == p[i+1]:
            count += 1
    return count


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    p = [ int(next(tokens)) for _ in range(n) ]  # type: "List[int]"
    print(solve(n, p))

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
[n, m, l] = [int(x) for x in raw_input().split()]

A = []
B = []
counter = 0
while counter < n:
    A.append([int(x) for x in raw_input().split()])
    counter += 1

counter = 0
while counter < m:
    B.append([int(x) for x in raw_input().split()])
    counter += 1

B = list(zip(*B))

for i in range(n):
        print(' '.join([str(x) for x in [sum([x[0] * x[1] for x in zip(A[i], B[j])]) for j in range(l)]]))

Measured memory_bytes: 7016
while True:
    a,op,b = input().split()

    a = int(a)
    b = int(b)
    if op == "+":
        print(a+b)
    elif op == "-":
        print(a-b)
    elif op == "*":
        print(a*b)
    elif op == "/":
        print(a//b)
    else:
        break





Measured memory_bytes: 5592
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=100005;
const ll INF=(1LL<<60)-1;
ll ty[MAXN],a[MAXN],dp[MAXN][3];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        if(i>1)
        {
            char op[5];
            scanf("%s",op);
            ty[i]=(*op=='-');
        }
        scanf("%lld",&a[i]);
    }
    for(int i=0;i<=n;i++)
        for(int j=0;j<3;j++)
            dp[i][j]=-INF;
    dp[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<3;j++)
        {
            ll now=(ty[i] ? -1 : 1)*a[i];
            if(j<3 && ty[i-1])
                dp[i][j+1]=max(dp[i][j+1],dp[i-1][j]+((j+1)&1 ? -1 : 1)*now);
            dp[i][j]=max(dp[i][j],dp[i-1][j]+(j&1 ? -1 : 1)*now);
        }
        for(int j=1;j>=0;j--)
            dp[i][j]=max(dp[i][j],dp[i][j+1]);
    }
    return 0*printf("%lld\n",dp[n][0]);
}

Measured memory_bytes: 4096
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
#include <map>
#include <unordered_map>
#include <chrono>
#include <numeric>
using namespace std;
using ll = long long;
const long long INF = (long long)1e18+1;
#define DIV 1000000007
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
#ifdef TEST
    chrono::system_clock::time_point start, end;
    start = chrono::system_clock::now();
#endif
    long idx=0;
    long N;
    cin >> N;
    ll total = 0;
    for(size_t i=1;i<=N; i++)
    {
        if(i % 3 == 0 || i % 5 == 0 ) continue;
        total+=i;
    }
    cout << total << endl;
#ifdef TEST
    end = chrono::system_clock::now();
    cerr << static_cast<double>(chrono::duration_cast<chrono::microseconds>(end - start).count() / 1000.0) << "[ms]" << endl;
#endif
    return 0;
}

Measured memory_bytes: 3652
#include <stdio.h>
#include <string.h>
int n; bool used[22370000]; char com[7], s[13];
int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		scanf("%s %s", com, s);
		int h = 0, l = strlen(s);
		for(int j = 0; j < l; j++) {
			h *= 4;
			if(s[j] > 'A') h++;
			if(s[j] > 'C') h++;
			if(s[j] > 'G') h++;
		}
		h += (1 << (2 * l));
		if(com[0] == 'i') used[h] = true;
		else puts(used[h] ? "yes" : "no");
	}
}

Measured memory_bytes: 3992
N,K=gets.chomp.split.map(&:to_i)
h = []
N.times {h << gets.to_i}
h.sort!
ans = Float::INFINITY
0.upto(N-K) do |i|
    ans = h[i+K-1] - h[i] if h[i+K-1] - h[i] < ans 
end
puts ans

Measured memory_bytes: 4016
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define REP(i, n) for(int i = 1; i < (int)(n); ++i)
using namespace std;

int main() {
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<vector<int>> S(N + 1, vector<int>(N + 1, 0));
    rep(i, M) {
        int L, R;
        cin >> L >> R;
        ++S[L][R];
    }
    REP(i, N + 1) REP(j, N + 1) S[i][j] += S[i][j - 1];
    
    rep(i, Q) {
        int p, q;
        cin >> p >> q;
        int ans = 0;
        for (int i = p; i <= q; ++i) ans += S[i][q];
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 1920
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd, log10
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, chain
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
from copy import copy, deepcopy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


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

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


n, k = LI()
ans = 0
if k == 0:
    ans = n ** 2
else:
    for b in range(k + 1, n+1):
        ans += (b - k) * (n // b) + max(0, n % b - k + 1)
print(ans)


Measured memory_bytes: 71556
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second

#define pb push_back
#define es erase
#define in insert

#define pii pair<ll, ll>
#define ll long long
#define lb long double

#define ioss                     \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);

#define m_p(i, j) make_pair(i, j)
#define mem(a, x) memset(a, x, sizeof(a))
#define endl "\n"
#define all(x) x.begin(), x.end()

const ll mod = 1e9 + 7;
const ll maxn = 6e5 + 7;
ll n, fa[maxn], m, num[maxn];
ll ifind(ll x)
{
    if (x == fa[x])
        return x;
    return fa[x] = ifind(fa[x]);
}
ll cmb(ll x, ll y)
{
    ll fx = ifind(x), fy = ifind(y);
    if (fx != fy) {
        fa[fx] = fy;
        num[fy] += num[fx];
    }
  return 0;
}
int main()
{
    cin >> n >> m;
    for (ll i = 1; i <= n; i++) {
        fa[i] = i;
        num[i] = 1;
    }
    for (ll i = 1; i <= m; i++) {
        ll x, y;
        cin >> x >> y;
        cmb(x, y);
    }
    cout << *max_element(num + 1, num + 1 + n) << endl;
}


Measured memory_bytes: 6636
#include <bits/stdc++.h> 
using namespace std;
int d[(int)3e6][2], n, g;
int main () {
	string s; cin >> s; 
	reverse (s.begin(),s.end());
	s += '0';n = s.size();
	d[0][0] = (s[0] - '0'), d[0][1] = 10 - (s[0]-'0');
	for (int i = 1; i < n; i ++) {
		g = s[i]-'0';
		d[i][0] = min (d[i-1][0] + (g), d[i-1][1] + (g+1)), d[i][1] = min (d[i-1][0] + (10 - g), d[i-1][1] + (10 - (g+1))); 
	}
	cout << d[n-1][0];
}

Measured memory_bytes: 9476
d, g = [int(i) for i in input().split()]

score = 0
p = []
c = []
for i in range(d):
    p_tmp, c_tmp = [int(i) for i in input().split()]
    p.append(p_tmp)
    c.append(c_tmp)

num = []
for i in range(2**d):
    num_tmp = 0
    score = 0
    not_comp = []
    for j in range(d):
        if i >> j & 1:
            score += p[j] * 100 * (j+1) + c[j]
            num_tmp += p[j]
        else:
            not_comp.append(j)

    for j in not_comp[::-1]:
        if score < g:
            num_j = min(p[j]-1, (g-score-1)//(100*(j+1))+1)
            score += num_j * 100*(j+1)
            num_tmp += num_j
    if score >= g:
        num.append(num_tmp)

ans = min(num)
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a;
  cin >> a;
  int B = 0;
  int R = 0;
  string s;
  cin >> s;
  for(int i=0;i<a;++i){
    if(s.at(i) == 'B') B++; 
    else R++;
  }
  if(B >= R)  cout << "No" << endl;
  else cout <<"Yes" << endl;
}
  

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


using namespace std;

int main()
{
    string N;

    cin >> N;

    for(int i=0; i<=2; i++)
    {
        if(N[i]=='7')
        {
            cout<<"Yes";
            return 0;
        }
    }

    cout<<"No";

    return 0;
}


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


int main() {
  char s[6];
  int ans=0;
  rep(i,6){
    cin >> s[i];
    if(s[i]=='1'){ans++;}
    }
  cout << ans << endl;
}

Measured memory_bytes: 256
from math import factorial

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

if N <= 1:
    combN = 0
else:
    combN = factorial(N) // (factorial(N - 2) * factorial(2))

if M <= 1:
    combM = 0
else:
    combM = factorial(M) // (factorial(M - 2) * factorial(2))

print(combN + combM)


Measured memory_bytes: 9020
#include <bits/stdc++.h>
using namespace std;
int isValid[1000005 ];

int main() {
    int n;
    cin >> n;
    int a[n],ans = 0;
    for(int i=0;i<n;i++) {
        cin >> a[i];
    }
    sort(a, a+n );
    memset(isValid,0, sizeof(isValid));
        
    for(int i=0 ; i < n  ; i++) {
        if(i-2 >=0 && a[i] == a[i-2]) continue;
        for(int j = a[i] ; j <= 1000005 ; j+= a[i])
        isValid[j]++;
        
    }
   
    for(int i=0; i < n ; i++) {
        
        if(isValid[a[i]] == 1) ans ++;
    }
            
    cout << ans << endl;
    
    return 0;
}

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

#define OM ios::sync_with_stdio(0);cin.tie(0)
#define endl '\n'
#define pi 3.14159265358979323846

typedef long long ll;

/*LETS BEGIN WITH THE NAME OF MAHADEV*/

int main(){
	OM;
	string s, t;
	cin >> s >> t;
	int max_match = 0;
	for(int i = 0; i < s.size() - t.size() + 1; ++i){
		int match = 0;
		for(int j = 0; j < t.size(); ++j){
			if(t[j] == s[i + j])
				++match;
		}
		// cout << i << ' ' << match << endl;
		max_match = max(max_match, match);
	}
	// cout << max_match << endl;
	cout << t.size() - max_match;
	return 0;
}

Measured memory_bytes: 3652
inList = input().split()
n = int(inList[0])
k = int(inList[1])

workList = [1] * n

for i in range(k):
    di = int(input())
    inList = input().split()
    for di in inList:
        workList[int(di)-1] = 0


print(sum(workList))


Measured memory_bytes: 9152
#include<bits/stdc++.h>
using namespace std;
int dfs(vector<vector<int> >&g, vector<bool>&visited, vector<int>&dp, int u){
    if(visited[u]) return dp[u];
    visited[u] = true;
    for(int i = 0; i < g[u].size(); i++){
        int v = g[u][i];
        dp[u] = max(dp[u], 1 + dfs(g, visited, dp, v ));
    }
    return dp[u];
}
int main(){
    int n, m, x, y;
    cin >> n >> m;
    vector<vector<int> >g(n);
    for(int i = 0; i < m; i++){
        cin >> x >> y;
        x --, y --;
        g[x].push_back(y);
    }
    vector<bool>isvisited(n, false);
    vector<int>dp(n, 0);
    for(int i = 0; i < n; i++){
        if(!isvisited[i]){
            dfs(g, isvisited, dp, i);
        }
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        ans = max(dp[i], ans);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 9600
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <functional>
#include <numeric>
#include <iomanip>
#define fi first
#define se second
#define fcout(n) cout<<fixed<<setprecision((n))
#define cinl(str) getline(cin,(str))
using namespace std;
bool value(int y,int x,int R,int C){return 0<=y&&y<R&&0<=x&&x<C;}
typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long > vll;
typedef vector< vi > vvi;
double pie=acos(-1);
int INF=10000009;
int dx[4] = { 0,-1,0,1 };
int dy[4] = { -1,0,1,0 };
int main() {
	int a[4],d[4];
	while(true){
		int h=0,b=0;
		cin>>a[0]>>a[1]>>a[2]>>a[3]>>d[0]>>d[1]>>d[2]>>d[3];;
		if (cin.eof())break;
		for(int i=0;i<4;i++){
			for(int j=0;j<4;j++){
				if(i==j&&a[i]==d[j]) h++;
				if(i!=j&&a[i]==d[j]) b++;
			}
		}
		cout<<h<<" "<<b<<endl;
	}
}

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


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

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = (int)1e9 + 7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <class T, class ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T, class T2> void amin(T& a,T2 b){ if(a > b) a = b;}

int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n; ll k;
	cin >>n >>k;
	
	VL sk(100010);
	rep(i, n){
		int a, b; cin >>a >>b;
		sk[a] += b;
	}
	rep(i,100001){
		if(sk[i] >= k){
			cout << i <<"\n";return 0;
		}
		k -= sk[i];
	}
	return 0;
}


Measured memory_bytes: 1024
//
// Created by Tetsuya Shiota on 2019-04-11.
//

#include<iostream>

using namespace std;

int main(){
    int N, Y;
    cin >> N >> Y;
    for(int i = 0; i<=N; i++){
        for(int j = 0; j+i<=N; j++){
            int now = 0, k = (N-i-j);
            now += i*10000;
            now += j*5000;
            now += k * 1000;
            if(Y == now){
                cout << i <<' '<<j<<' '<<k<<endl;
                return 0;
            }

        }
    }
    cout << "-1 -1 -1"<<endl;

}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	var A, B int
	scanner.Scan()
	fmt.Sscanf(scanner.Text(), "%d %d", &A, &B)

	ans := -1
	if A == 1 && B == 1 {
		ans = 1
	} else if A == 1 && B == 2 {
		ans = 0
	} else if A == 2 && B == 1 {
		ans = 0
	} else if A == 1 {
		ans = B - 2
	} else if B == 1 {
		ans = A - 2
	} else if A == 2 {
		ans = 0
	} else if B == 2 {
		ans = 0
	} else {
		ans = (A - 2) * (B - 2)
	}
	fmt.Println(ans)
}


Measured memory_bytes: 640
s = int(input())

m = 1
a=[]
a.append(s)
while True:
    m += 1
    if s%2 == 0:
        an = s//2
    else:
        an = 3*s+1

    try:
        a.index(an)
        break
    except:
        a.append(an)
        s = an


print(m)

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

using namespace std;
using ll = long long;

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

int main() {
  int a, b;
  cin >> a >> b;
  if (a >= 13)
    cout << b << endl;
  else if (a <= 5)
    cout << 0 << endl;
  else
    cout << b / 2 << endl;
  return 0;
}


Measured memory_bytes: 3604
import math
while True :
    try :
        a, l, x = map(int, input().split())
    except EOFError :
        break

    HC = math.sqrt(l**2 - a**2 / 4)
    I = math.sqrt(((l+x)/2)**2 - l**2 / 4)
    S1 = a * HC / 2
    S2 = l * I / 2
    print('{:.8f}'.format(S1 + S2*2))


Measured memory_bytes: 5692
import Control.Applicative
import Control.Monad
import Data.List

solve :: String -> String -> String -> String
solve as bs cs = iter 'a' as bs cs
  where
    iter 'a' xs ys zs
        | null xs   = "A"
        | otherwise = iter (head xs) (tail xs) ys zs
    iter 'b' xs ys zs
        | null ys   = "B"
        | otherwise = iter (head ys) xs (tail ys) zs
    iter 'c' xs ys zs
        | null zs   = "C"
        | otherwise = iter (head zs) xs ys (tail zs)

main :: IO ()
main = do
    as <- getLine
    bs <- getLine
    cs <- getLine
    putStrLn $ solve as bs cs

Measured memory_bytes: 508
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;    using vvi = vector<vi>;
using vb = vector<bool>;   using vvb = vector<vb>;
using vl = vector<ll>;     using vvl = vector<vl>;
using vd = vector<double>; using vvd = vector<vd>;

#define REP(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(c) (c).begin(), (c).end()
#define FOR(i,s,n) for(ll i=s, i##_len=(n); i<i##_len; ++i)
#define TEN(x) ((ll)1e##x)
const ll mod = TEN(9) + 7;

int main() {
#ifdef INPUT_FROM_FILE
	ifstream cin("sample.in");
	ofstream cout("sample.out");
#endif
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(50);
	ll n; cin >> n;
	vl a(n); REP(i, n) cin >> a[i];
	ll cnt = 0;
	REP(i, n-1) {
		cnt += a[i] / 2;
		a[i] %= 2;
		if (a[i]==1 && a[i+1] > 0) {
			cnt += 1;
			a[i + 1]--;
			a[i]--;
		}
	}
	cnt += a[n - 1] / 2;
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <limits.h>
#include <cinttypes>
#include <string.h>
#include <bits/stdc++.h>

#define countof(a) (sizeof(a)/sizeof(*a))

#define vi vector<int>
#define vvi vector<vector<int> >
#define pi pair<int,int>
#define fi first
#define se second

#define FOR(var, to)          for (register s64 var = 0; var < (s64)to; var++)
#define FROMTO(var, from, to) for (register s64 var = from; var <= (s64)to; var++)

#define INIT(var) FOR(i,countof(var)) var[i] = 0
#define INPUT(var) FOR(i,countof(var)) var[i] = ri()

#define SORT(v) qsort(v,countof(v),sizeof(*v),int_less)
#define SORTT(v) qsort(v,countof(v),sizeof(*v),int_greater)

#define MOD 1000000007
#define INF (1 << 30)

typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t s8;
typedef int16_t s16;
typedef int32_t s32;
typedef int64_t s64;

using namespace std;

static inline int ri() {
  int a;
  scanf("%d", &a);
  return a;
}

static inline s64 rs64() {
  s64 a;
  scanf("%" SCNd64, &a);
  return a;
}

static inline void wi(int a) {
  printf("%d", a);
}

static inline void wu64(u64 a) {
  printf("%" PRIu64, a);
}

static inline void ws64(s64 a) {
  printf("%" PRId64, a);
}

int int_less(const void *a, const void *b) {
  return (*((const int*)a) - *((const int*)b));
}
int int_greater(const void *a, const void *b) {
  return (*((const int*)b) - *((const int*)a));
}

int main() {
    int n = ri();
    cout << n/3 << endl;
 return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cstring>
#define RG register
using namespace std;
int n,flg=1;
string upp[4]={".",".","#","#"}, dwn[4]={".","#","#","."}, lst[2],nw[2];
char ss[4];
template<typename I> inline void read(I &ot){
	I ch=getchar(), x=0, f=1;
	while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar();	}
	while(ch>='0' && ch<='9'){x=x*10+ch-'0'; ch=getchar();	}
	ot=x*f;}
template<typename I, typename... U> inline void read(I &x,U&... y){read(x); read(y...);}
int main()
{
	//freopen("Long Blackboard.in","r",stdin);
	read(n);
	while( true )
	{
		for(RG int i=0;i<4;i++)
		{
			nw[0]= flg ? lst[0]+upp[i] : upp[i]+lst[0];
			nw[1]= flg ? lst[1]+dwn[i] : dwn[i]+lst[1];
			cout<<nw[0]<<endl<<nw[1]<<endl;
			scanf("%s",ss);
			if(ss[0]=='T')
			{
				lst[0]=nw[0];
				lst[1]=nw[1];
				if(lst[0].size()==n) return 0;
				break;
			}
			if(i==3) flg=0;
		}
	}
	return 0;
}

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

using namespace std;
#define int long long
#define rep(i, n) for(int i=0;i<(n);++i)
#define INF (1ll<<60)
#define FI first
#define SE second

int N;
string S1, S2;
int X[55];

signed main() {
    cin >> N;
    cin >> S1 >> S2;
    if (S1[0] == S2[0]) {
        X[0] = 3;
    } else {
        X[0] = 6;
    }

    for (int i = 1; i < N; ++i) {
        if (S1[i - 1] == S2[i - 1]) {
            X[i] = X[i - 1] * 2;
        } else if (S1[i - 1] == S1[i] || S2[i - 1] == S2[i]) {
            X[i] = X[i - 1];
        } else if (S1[i] == S2[i]) {
            X[i] = X[i - 1];
        } else {
            X[i] = X[i - 1] * 3;
        }
        X[i] %= 1000000007;
    }
    cout << X[N - 1] << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
char s[N];
int main()
{
	int flag=0;
	scanf("%s",s);
	int len=strlen(s);
	for(int i=0;i<len-1;i++)
	{
		if(s[i]==s[i+1])
		{
			cout<<i+1<<" "<<i+2<<endl;
			flag=1;
			break;
		}
		else if(i<len-2&&s[i]==s[i+2])
		{
			cout<<i+1<<" "<<i+3<<endl;
			flag=1;
			break;
		}
	}
	if(!flag)
	cout<<-1<<" "<<-1<<endl;
	return 0;	
} 

Measured memory_bytes: 384
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long int
// #define lli long long int
#define ld long double
#define ff first
#define ss second
#define mp make_pair
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define eb emplace_back
#define pii pair<int, int>
#define endl '\n'
#define all(x) x.begin(),x.end()
#define f(i,j,l) for(i=j;i<l;i++)
// #if !defined(ONLINE_JUDGE)
// #include "debugging.h"
// #endif
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// int const mod = 7340033;
int const mod = 1e9+7;
int power(int a,int b,int m){
    int res = 1;
    while(b){
        if(b&1){
            res = res*a;
            res %= m;
        }
        a=a*a;
        a%=m;
        b=b/2;
    }
    return res;
}
 
int inverse(int x){
    return power(x,mod-2,mod);
}

int const N = 1e5+5;
int const inf = 1e18;
vector<pair<int,pii> > v;

void solve(){
    int i,j,l;
    int n;
    cin>>n;
    for(i=0;i<n;i++){
        int x,lt;
        cin>>x>>lt;
        v.pb({x+lt,{x,lt}});
    }
    sort(all(v));
    set<int> st;
    map<int,int> m1;
    for(i=0;i<n;i++){
        int x = v[i].ss.ff - v[i].ss.ss;
        int rt = v[i].ss.ff + v[i].ss.ss;
        auto it = st.upper_bound(x);
        
        if(it != st.begin()){
            it--;
            int z = *it;
            m1[rt] = max(m1[rt] , 1 + m1[z]);
        }
        m1[rt] = max(m1[rt] , 1LL);
        auto it1 = st.upper_bound(rt);
        if(it1!=st.begin()){
            it1--;
            int z = *it1;
            m1[rt] = max(m1[rt] , m1[z]);
        }
        st.insert(rt);
    }
    int ans = 0;
    for(auto x:m1){
        ans = max(ans , x.second);
    }
    cout<<ans<<endl;
}   

int32_t main(){
    IOS;
    int t;
    t = 1;
    // pre();
    // cin>>t;
    for(int tt=1;tt<=t;tt++){
        solve();
    }
    return 0;
}

/*

*/

Measured memory_bytes: 13808
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char* argv[])
{
	int N,i;
	cin>>N;
	vector<int> X(N),Y(N);
	for (i=0;i<N;i++){
		cin>>X[i];
	}
	for (i=0;i<N;i++){
		cin>>Y[i];
	}
	int ans=0;
	for (i=0;i<N;i++){
		if (X[i]-Y[i]>0){
			ans+=X[i]-Y[i];
		}
	}
	cout<<ans<<endl;	
	return 0;
}

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

template<unsigned mod>
struct RollingHash{
  vector<unsigned> hashed,power;

  inline unsigned mul(unsigned a,unsigned b) const{
    unsigned long long x = (unsigned long long)a*b;
    unsigned xh=unsigned(x>>32),xl=(unsigned)x,d,m;
    asm("divl %4; \n\t" : "=a"(d),"=d"(m):"d"(xh),"a"(xl),"r"(mod));
    return m;
  }

  RollingHash(const string &s, unsigned base=10007){
    int sz=(int)s.size();
    hashed.assign(sz+1,0);
    power.assign(sz+1,0);
    power[0]=1;
    for(int i=0;i<sz;i++){
      power[i+1]=mul(power[i],base);
      hashed[i+1]=mul(hashed[i],base)+s[i];
      if(hashed[i+1]>=mod)hashed[i+1] -=mod;
    }
  }
  unsigned get(int l,int r) const{
    unsigned ret=hashed[r]+mod-mul(hashed[l],power[r-l]);
    if(ret>=mod)ret-=mod;
    return ret;
  }
};

using RH = RollingHash<1000000181>;
using SH = RollingHash<1000000007>;

#define int long long

int calc(vector<string> &v,string s){
  int l=lower_bound(v.begin(),v.end(),s)-v.begin();
  s[s.size()-1]++;
  int r=lower_bound(v.begin(),v.end(),s)-v.begin();
  return abs(l-r);
}


signed main(){
  int n,q;
  cin>>n>>q;
  map<pair<int,int>,vector<string>> m;
  lp(i,n){
    string s;
    cin>>s;
    RH rh(s);
    SH sh(s);
    lp(i,s.size()){
      m[{(int)rh.get(i,s.size()),(int)sh.get(i,s.size())}].push_back(s);
    }
  }
  set<int> ch;
  lp(i,q){
    string a,b;
    cin>>a>>b;
    RH rh(b);
    SH sh(b);
    int hs=rh.get(0,b.size());
    int ss=sh.get(0,b.size());
    vector<string> &v=m[{hs,ss}];
    if(v.empty()){
      cout<<0<<endl;
      continue;
    }
    if(ch.find(hs)==ch.end()){
      sort(v.begin(),v.end());
      ch.insert(hs);
    }
    cout<<calc(v,a)<<endl;
  }
}



Measured memory_bytes: 175456
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

int main(){
    ll N, M;
    cin >> N;
    map<string, ll> s;
    rep(i, 0, N){
        string ss;
        cin >> ss;
        s[ss]++;
    }
    cin >> M;
    map<string, ll> t;
    rep(i, 0, M){
        string ss;
        cin >> ss;
        t[ss]++;
    }
    ll mx = 0;
    for(auto p : s){
        if(t.count(p.first) > 0){
            mx = max(mx, p.second - t[p.first]);
        }else{
            mx = max(mx, p.second);
        }
    }
    cout << mx << endl;
    return 0;
}

Measured memory_bytes: 256
"""
二分探索
"""
def BinaraySearch(A, key):
    count = 0
    left = 0
    right = len(A)
    while left < right:
        mid = int((left + right) / 2)
        if A[mid] == key:
            count += 1
            return count
        elif key < A[mid]:
            right = mid
        else:
            left = mid + 1
    else:
        return count

n = int(input())
s = list(map(int, input().split()))
q = int(input())
t = list(map(int, input().split()))

ans = 0
for i in range(q):
    ans += BinaraySearch(s, t[i])

print(ans)




Measured memory_bytes: 16720
#include <iostream>
#include <vector>

int main()
{
  uint64_t N,K;
  std::cin>>N>>K;
  
  std::vector<uint64_t> A(N);
  for(auto &e:A)
    std::cin>>e;
  
  uint64_t pos=1;
  std::vector<uint64_t> firstFoundCount(N, 0);
  uint64_t loopLength=0;
  uint64_t loopStartCount=0;
  for(uint64_t i=1;;i++)
  {
    pos=A[pos-1];
    if(i==K)
    {
      std::cout<<pos<<std::endl;
      return 0;
    }
    if(firstFoundCount[pos-1]!=0)
    {
      loopStartCount=firstFoundCount[pos-1];
      loopLength=i-loopStartCount;
      break;
    }
    firstFoundCount[pos-1]=i;
  }
  
  for(uint64_t i=(K-loopStartCount)%loopLength;i!=0;i--)
  {
    pos=A[pos-1];
  }
  
  std::cout<<pos<<std::endl;
  
  return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double, int> pdbi;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()

const ll mod = 1000000000 + 7;
const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const ll INF = 1<<30;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;

int n, ma, mb;
int dp[45][405][405];
int a[105], b[105], c[105];

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> ma >> mb;
    rep(i, n) cin >> a[i] >> b[i] >> c[i];
    rep(i, 41)rep(j, 401)rep(k, 401) dp[i][j][k] = INT_MAX / 10;
    dp[0][0][0] = 0;
    rep(i, n)rep(j, 401)rep(k, 401) {
        dp[i + 1][j][k] = dp[i][j][k];
        if (j - a[i] >= 0 && k - b[i] >= 0) {
            dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j - a[i]][k - b[i]] + c[i]);
        }
    }
    int ans = INT_MAX;
    rep2(j, 1, 401)rep2(k, 1, 401) {
        if (j % ma == 0 && k % mb == 0) {
            if (j / ma == k / mb) {
                ans = min(ans, dp[n][j][k]);
            }
        }
    }
    if (ans == INT_MAX / 10) cout << -1 << endl;
    else cout << ans << endl;
}


Measured memory_bytes: 26880
def examC():
    N = I()
    C = [0]*N; S =[0]*N; F = [0]*N
    for i in range(N-1):
        C[i], S[i], F[i] = LI()
    ans = []
    for i in range(N):
        cur = 0
        for j in range(i,N-1):
            cur = max(((cur-1)//F[j] +1)*F[j],S[j])+C[j]
        ans.append(cur)
    for v in ans:
        print(v)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()


Measured memory_bytes: 41328