akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using int64 = int64_t;

struct edge {
    int to, weight;
    edge() {}
    edge(int a, int b): to(a), weight(b) {}
};

constexpr int LIM = 10005;

int N, M;
vector<edge> graph[100];

bool visited[100];
int search(int x, int llim, int ulim) {
    visited[x] = true;

    int ret = 1;
    for (const edge& e: graph[x]) {
        if (!visited[e.to] && llim <= e.weight && e.weight <= ulim) {
            ret += search(e.to, llim, ulim);
        }
    }

    return ret;
}

bool check(int llim, int ulim) {
    fill(visited, visited+N, false);
    int v = search(0, llim, ulim);
    return v == N;
}

int solve () {
    int ans = LIM;
    for (int j = 1; j <= LIM; ++j) {
        int lk = j, uk = LIM;
        while (lk < uk) {
            int mk = (lk + uk) / 2;
            if (check(j, mk)) {
                uk = mk;
            } else {
                lk = mk + 1;
            }
        }
        if (check(j, uk)) {
            ans = min(ans, uk - j);
        }
    }
    return ans >= LIM ? -1 : ans;
}

int main() {
    while (true) {
        cin >> N >> M;
        if (N == 0 && M == 0) break;
        for (int j = 0; j < N; ++j) graph[j].clear();
        for (int j = 0; j < M; ++j) {
            int a, b, w;
            cin >> a >> b >> w;
            --a; --b;
            graph[a].emplace_back(b, w);
            graph[b].emplace_back(a, w);
        }
        cout << solve() << endl;
    }
    return 0;
}

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

void insertionSort(int *A, int N) {
	for (int i=0; i<N; i++) {
		int v = A[i];
		int j = i-1;
		while (j >= 0 && A[j] > v) {
			A[j+1] = A[j];
			j--;
		}
		A[j+1] = v;

		for (int j=0; j<N; j++) {
			cout << A[j];
			if (j!=N-1) cout << ' ';
		}
		cout << endl;
	}
}

int main() {
	int N;
	cin >> N;

	int a[N];
	for (int i=0; i<N; i++)
		cin >> a[i];

	insertionSort(a, N);

	return 0;
}


Measured memory_bytes: 3108
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>

using namespace std;

int count_ab(string &s) {
	int ret = 0;
	for (int i = 1; i < s.size(); i++) {
		if (s[i-1] == 'A' && s[i] == 'B') {
			ret++;
		}
	}

	return ret;
}

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

	int ans = 0;
	string s;
	int bxa = 0;
	int xa = 0;
	int bx = 0;
	for (int i = 0; i < n; i++) {
		cin >> s;
		ans += count_ab(s);

		if (s.front() == 'B' && s.back() == 'A') {
			bxa++;
		} else if (s.front() == 'B') {
			bx++;
		} else if (s.back()  == 'A') {
			xa++;
		}
	}

	if (n == 1) {
		cout << ans << endl;
		return 0;
	}

	int add = 0;

	// printf("bxa %d, xa %d, bx %d, ans_tmp %d\n", bxa, xa, bx, ans);
	if (bxa == 0) {
		add += min(xa, bx);
	} else {
		if (xa + bx == 0) {
			add += bxa - 1;
		} else {
			add += bxa + min(xa, bx);
		}
	}

	ans += add;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))

import collections

c = collections.Counter(a)
total = 0

for i in c:
  if c[i] <=1:
    total += 0
  else:
  	total += c[i]*(c[i]-1)//2
#print(c)
delta = {}
for i in c:
  if c[i]==2:
    delta[i] = 1
  elif c[i]>=3:
    delta[i] = c[i]*(c[i]-1)//2 - (c[i]-1)*(c[i]-2)//2
  else:
    delta[i] = 0

for i in a:
  print(total - delta[i])

Measured memory_bytes: 32928
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]

MOD = 10 ** 9 + 7

S = [0] * (N + 1)
S[0] = 1
for a in A:
  S[a] = -1

for i in range(N):
  if S[i] != -1:
    if i + 1 < N + 1 and S[i + 1] != -1:
      S[i + 1] = (S[i + 1] + S[i]) % MOD
    if i + 2 < N + 1 and S[i + 2] != -1:
      S[i + 2] = (S[i + 2] + S[i]) % MOD
      
print(S[N])

Measured memory_bytes: 50008
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<P,ll> PPI;
typedef pair<ll,P> PIP;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vp;
#define PQ(T) priority_queue<T,vector<T>,greater<T>>
#define PQ2(T) priority_queue<T>
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define REP(i,a,b) for(ll (i)=a;(i)<(ll)(b);++(i))
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n+1)
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(x,y) ((x)=min((x),(y)))
#define chmax(x,y) ((x)=max((x),(y)))
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
#define DEBUG(x) cerr<<"line ("<<__LINE__<<")  "<<#x<<": "<<x<<endl;
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

#define N 51
int d[N][N];
int h, w;
string s[N];
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

int main(){
	cin>>h>>w;
	rep(i, h) cin>>s[i];
	queue<int> q;
	q.push(0);
	rep(i, h) fill(d[i], d[i]+w, INF);
	d[0][0] = 0;
	while(!q.empty()){
		int u = q.front(); q.pop();
		int x = u/w, y = u%w;
		rep(i, 4){
			int x2 = x+dx[i], y2 = y+dy[i];
			if(x2<0||x2>=h||y2<0||y2>=w||d[x2][y2]!=INF||s[x2][y2]=='#') continue;
			d[x2][y2] = d[x][y]+1;
			q.push(x2*w+y2);
		}
	}
	if(d[h-1][w-1]==INF){
		cout<<"-1"<<endl;
		return 0;
	}
	ll sum = 0;
	rep(i, h) rep(j, w) sum += (s[i][j]=='.');
	cout<<sum-d[h-1][w-1]-1<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<algorithm>//everybody dies in their nightmares
#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>
#include<map>
#include<queue>
#include<deque>
#include<string>
#include<vector>
#include<sstream>
#include<cmath>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ff(i,a,b) for(register int i=a;i>=b;--i)
#define debug(x) cerr << #x << " : " << x << " " << endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
const ll mod = 1e9 + 7;
const double tiaohe = 0.57721566490153286060651209;
ll oula(ll x) { ll res = x;f(i, 2, x / i) { if (x % i == 0) { res = res / i * (i - 1);while (x % i == 0) x /= i; } }if (x > 1) res = res / x * (x - 1);return res; }
ll quickmod(ll a, ll n, ll m) { ll s = 1;while (n) { if (n & 1) { s = s * a % m; }a = (a*a) % m;n = n / 2; }return s; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
void ex_gcd(ll a, ll b, ll &x, ll &y, ll &d) { if (!b) { d = a, x = 1, y = 0; } else { ex_gcd(b, a % b, y, x, d);y -= x * (a / b); } }
ll inv(ll t, ll p) { ll d, x, y;ex_gcd(t, p, x, y, d);return d == 1 ? (x % p + p) % p : -1; }
bool isPrime(ll x) { if (x == 2)return true;if (x % 2 == 0)return false;for (ll i = 2;i*i <= x;i++) if (x % i == 0)return false; return true; }
//double a = log(n) +tiaohe + 1.0 / (2 * n);
double eqa = (1 + sqrt(5.0)) / 2.0;

const int N = 6e5 + 5;
int t;
int n, a[N];
int mp[N];
int main()
{
	ll k;	
	cin >> n >> k;
	f(i, 1, n)
	{
		scanf("%d", &a[i]);
		mp[i] = a[i];

	}

	int now = 1;
	map<int, int> mpl;

	int cot = 1;
	if (a[1] == 1) { cout << 1 << endl;return 0; }
	int len, k1;
	while(1)
	{
		//debug(now);
		//debug(mpl[now]);
		if (mpl[now] > 0)
		{
			 len = cot - mpl[now];
			 k1 = mpl[now]-1;
			break;
		}
		mpl[now] = cot;
		now = mp[now];
		cot++;
	}

	int ans = 0;
	if (k>(ll)k1)
	{
		ans = k1 + (k-k1) % len;
	}
	else ans = k;
	now = 1;
	//debug(k1);
//	debug(len);
	f(i, 1, ans)
	{
		now = mp[now];
	}
	
	cout << now << endl;
	return 0;
}





Measured memory_bytes: 14468
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
from functools import reduce
# local only
# if not __debug__:
#     fin = open('in_1.txt', 'r')
#     sys.stdin = fin
# local only
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template




def main():
    N, s, t = mi()
    s -= 1; t -= 1
    print("?", s + 1, t + 1, flush=True)
    st = ii()
    lis = [0] * N
    lis[t] = st
    lit = [0] * N
    lit[s] = st
    for i in range(N):
        if i != s and i != t:
            print("?", s + 1, i + 1, flush=True)
            lis[i] = ii()
            print("?", t + 1, i + 1, flush=True)
            lit[i] = ii()
    # print(lis, lit)
    sub = []
    for i in range(N):
        if lis[i] + lit[i] == st:
            sub.append((i, lis[i]))
    sub.sort(key=itemgetter(1))
    # print(sub)
    if len(sub) == 2:
        print("!", s + 1, t + 1, flush=True)
        sys.exit()
    ans = []
    q = deque(sub)
    lastnode = s
    q.popleft()
    ans.append(s)
    u, w = q.popleft()
    ans.append(u)
    lastnode = u
    while True:
        u, w = q.popleft()
        if u == t:
            ans.append(u)
            lastnode = u
            break
        print("?", lastnode + 1, u + 1, flush=True)
        tmp = ii()
        if lis[lastnode] + tmp + lit[u] == st:
            ans.append(u)
            lastnode = u
            continue
        else:
            continue
    print("!", *list(map(lambda x: x + 1, ans)))





if __name__ == '__main__':
    main()





Measured memory_bytes: 7036
#include <stdio.h>

int count[7];

int main(void)
{
	int n;
	int i;
	int old;
	
	while (1){	
		scanf("%d", &n);
		
		if (n == 0){
			break;
		}
		
		for (i = 0; i < n; i++){
			scanf("%d", &old);
		
			if (old >= 60){
				count[6]++;
			}
			else if (old >= 50){
				count[5]++;
			}
			else if (old >= 40){
				count[4]++;
			}
			else if (old >= 30){
				count[3]++;
			}
			else if (old >= 20){
				count[2]++;
			}
			else if (old >= 10){
				count[1]++;
			}
			else if (old < 10){
				count[0]++;
			}
		}
		
		for (i = 0; i < 7; i++){
			printf("%d\n", count[i]);
			count[i] = 0;
			
		}
		
	}
	
	
	
	return (0);
}

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

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  rep(i, n) a[i]--;
  vector<int> s(n + 1);
  rep(i, n) s[i + 1] = (s[i] + a[i]) % k;
  map<int, int> mp;
  ll ans = 0;
  queue<int> q;
  rep(i, n + 1) {
    ans += mp[s[i]];
    mp[s[i]]++;
    q.push(s[i]);
    if (q.size() == k) {
      mp[q.front()]--;
      q.pop();
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 12032
#include <cstdio>
#include <algorithm>

using namespace std;

int log(int x, int b){
  int p = 1;
  int res = 0;
  while(1){
    if(x <= p){
      return res;
    }
    res++;
    p *= b;
  }
}

int pow(int x, int b){
  int res = 1;
  for(int i=0; i < x; i++){
    res *= b;
  }
  return res;
}

int get_min_times(int val, int base){
  int div = pow(log(val, base), base);
  int res = 0;
  // printf("debug %d, %d %d\n", val, div, val/div);
  while(val > 0){
    int temp = val/div;
    res += temp;
    val = val % div;
    div /= base;
  }

  return res;

}

void test(){
  printf("%d\n", pow(2, 3));
  printf("%d\n", log(81, 3));
  printf("%d\n", get_min_times(81, 3));
}

  

int main(){
  int n;
  scanf("%d", &n);

  // test();

  int cr_min = n;
  for(int i=0; i <= n; i++){
    cr_min = min(cr_min, get_min_times(i, 6) + get_min_times(n-i, 9));
  }
  
  printf("%d\n", cr_min);

  return 0;
}


Measured memory_bytes: 128
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/1
Solved on 2019/3/  WA
@author: shinjisu
"""


# ABC 107 C Candles
def getInt(): return int(input())


def getIntList(): return [int(x) for x in input().split()]


def zeros(n): return [0]*n


def getIntLines(n): return [int(input()) for i in range(n)]


def getIntMat(n):
    mat = []
    for i in range(n):
        mat.append(getIntList())
    return mat


def zeros2(n, m): return [zeros(m)]*n


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**12


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def probC_WA():
    N, K = getIntList()
    X = getIntList()
    dmp((N, K, X))
    X = [-INF] + X + [INF]
    dmp(X)
    for i in range(N+2):
        if X[i] >= 0:
            break
    zeroIdx = i
    dmp(zeroIdx, 'zeroIdx')
    fromIdx = max(1, zeroIdx-K+1)
    dmp(fromIdx, 'fromIdx')
    # X[fromIdx] = 0 if X[fromIdx] == -INF else X[fromIdx]
    minTime = INF
    # for i in range(fromIdx, N+2-fromIdx-K+1):
    # for i in range(fromIdx, N+2-K+1):
    for i in range(fromIdx, N+2-K):
        if X[i] >= 0:
            moveTime = X[i+K-1]
        elif X[i+K-1] <= 0:
            moveTime = abs(X[i])
        else:
            plDist = X[i+K-1]
            mnDist = abs(X[i])
            moveTime = min(plDist, mnDist)*2 + max(plDist, mnDist)
        dmp((i, minTime, moveTime), 'moveTime in loop')
        minTime = min(minTime, moveTime)
    return minTime


def probC():
    N, K = getIntList()
    X = getIntList()
    dmp((N, K, X))
    # X = [-INF] + X + [INF]
    # dmp(X)
    # for i in range(N+2):
    for i in range(N):
        if X[i] >= 0:
            break
    zeroIdx = i
    dmp(zeroIdx, 'zeroIdx')
    fromIdx = max(0, zeroIdx-K+1)
    dmp(fromIdx, 'fromIdx')
    # X[fromIdx] = 0 if X[fromIdx] == -INF else X[fromIdx]
    minTime = INF
    # for i in range(fromIdx, N+2-fromIdx-K+1):
    # for i in range(fromIdx, N+2-K+1):
    for i in range(fromIdx, N-K+1):
        if X[i] >= 0:
            moveTime = X[i+K-1]
        elif X[i+K-1] <= 0:
            moveTime = abs(X[i])
        else:
            plDist = X[i+K-1]
            mnDist = abs(X[i])
            moveTime = min(plDist, mnDist)*2 + max(plDist, mnDist)
        dmp((i, minTime, moveTime), 'moveTime in loop')
        minTime = min(minTime, moveTime)
    return minTime


debug = False  # True False
ans = probC()
print(ans)
#for row in ans:
#    print(row)


Measured memory_bytes: 14252
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#define rep(i, n) for(int i = 0; i<n; i++)
#define rep_s(i, start, n) for(int i= start;  i<n; i++)
#define ALL(a) (a).begin(), (a).end()
string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int s[100000],t[100000],c[100000]; 
int sm[200002]; 
int tt[200002]; 
/*
typedef struct  a {
  int num;
  int count;
};
*/
int main(void){
  int N;
  cin >> N;
  int a[N+1];
  int min_num=1e+8, max_num = -1e+8;
  int max_index, min_index;
  int count, count_sousa = 0;
  rep_s(i,1, N+1) {
    cin >> a[i]; 
    if (max_num < a[i]){
      max_num = a[i];
      max_index = i;
    }
    if (min_num > a[i]){
      min_num = a[i];
      min_index = i;
    }
  }
  
  if (min_num >=0){
    cout << N-1 << endl;
    rep_s(i,1, N){
      cout << i << " " <<i+1 << endl;
    }
  } else if (max_num <=0){
    count = N;
    cout << N-1 << endl;
    rep(i, N-1){
      cout << count-i << " " << count-i-1 << endl;
    }
  } else{
    if (abs(max_num)>=abs(min_num)){
      cout << 2*N -1 << endl;
      rep_s(i, 1, N+1) {
        cout << max_index <<" " << i << endl;
      }
      rep_s(i,1, N){
      cout << i << " " <<i+1 << endl;
    }
    } else {
      cout << 2*N-1 <<endl;
      rep_s(i, 1, N+1){
        cout << min_index << " " << i << endl;
      }
      count = N;
      rep(i, N-1){
        cout << count-i << " " << count-i-1 << endl;
      }
    }
  }
}


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

int main(){
	int a[3];
	int min = 1000000;
	int result = 0;
	cin >> a[0] >> a[1] >> a[2];
	
	sort(a,a+3);
	
	cout << (a[2] - a[1]) + (a[1] - a[0]) << endl;
	return 0;
}

Measured memory_bytes: 256
/**
*    created: 27.06.2020 17:43:55
**/
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pcnt(bit) __builtin_popcountll(bit)
#define mod 1000000007
#define pi acos(-1.0)
using namespace std;
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T> bool chmin(T &a, const T &b) {if (b < a) {a = b; return 1;} return 0;}

const int INF = 1LL << 60;

signed main() {

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

    int n;
    cin >> n;
    int res = n;
    vector<int> dp(100001,INF);
    dp[0] = 0;
    rep2(i,1,n+1) {
        int pow6 = 1; int pow9 = 1;
        while (pow6 <= i) {
            chmin(dp[i],dp[i-pow6]+1);
            pow6 *= 6;
        }
        while (pow9 <= i) {
            chmin(dp[i],dp[i-pow9]+1);
            pow9 *= 9;
        }
    }
    cout << dp[n] << endl;
    return 0;
}

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

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		for(;T>0;T--){
			var d = ria();
			var N = d[0];
			var D = d[1];
			
			if(N==1){
				Console.WriteLine(D);
				continue;
			}
			if(N%2 == 0){
				Console.WriteLine(127 * (N-1) +(127-D));
			}else{
				Console.WriteLine(127 *(N-1) + D );
			}
		}
		
		
	}
	int T;
	public Sol(){
		T = ri();
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 3032
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define Lens 1000100
#define Nil -1

using namespace std;

struct point
{
	int x;
	int y;
	int add;
};

struct node
{
	int lc;
	int rc;
	int key;
};

int N, q, h;
point p[Lens];
node T[Lens];
vector<int> ans;
bool lessx(point a, point b) { return a.x < b.x; }
bool lessy(point a, point b) { return a.y < b.y; }

int maketree(int l, int r, int depth)
{
	if (l >= r)
		return Nil;
	int mid = (l + r) / 2;
	if (depth % 2 == 0)
		sort(p + l, p + r, lessx);
	else
		sort(p + l, p + r, lessy);
	int t = h++;
	T[t].key = mid;
	T[t].lc = maketree(l, mid, depth + 1);
	T[t].rc = maketree(mid + 1, r, depth + 1);
	return t;

}

void findtree(int root, int lx, int hx, int ly, int ry, int depth)
{
	int tr = root;
	int tx = p[T[tr].key].x;
	int ty = p[T[tr].key].y;
	if (lx <= tx&&tx <= hx&&ly <= ty&&ty <= ry)
		ans.push_back(p[T[tr].key].add);
	if (depth % 2 == 0)
	{
		if (T[tr].lc != Nil&&lx <= tx)
			findtree(T[tr].lc, lx, hx, ly, ry, depth + 1);
		if (T[tr].rc != Nil&&tx <= hx)
			findtree(T[tr].rc, lx, hx, ly, ry, depth + 1);
	}
	else
	{
		if (T[tr].lc != Nil&&ly <= ty)
			findtree(T[tr].lc, lx, hx, ly, ry, depth + 1);
		if (T[tr].rc != Nil&&ty <= ry)
			findtree(T[tr].rc, lx, hx, ly, ry, depth + 1);
	}

}

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		scanf("%d %d", &p[i].x ,&p[i].y);
		p[i].add = i;
		T[i].lc = T[i].rc = T[i].key = Nil;

	}
	int root = maketree(0, N, 0);
	scanf("%d", &q);
	for (int i = 0; i < q; i++)
	{
		ans.clear();
		int lx, hx, ly, ry;
		scanf("%d %d %d %d", &lx, &hx,&ly,&ry);

		findtree(root, lx, hx, ly, ry, 0);
		sort(ans.begin(), ans.end());
		for (int i = 0; i < ans.size(); i++)
			printf("%d\n", ans[i]); 
		printf("\n");
	}
	return 0;
}


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

template<class Cost = int>
struct Edge {
    int from, to;
    Cost cost;
    Edge(const int &from = -1, const int &to = -1, const Cost &cost = 1) : from(from), to(to), cost(cost) {}
    
    bool operator<(const Edge<Cost> &rhs) const { return this->cost < rhs.cost; }
    bool operator>(const Edge<Cost> &rhs) const { return this->cost > rhs.cost; }
};

template<class Cost = int>
struct Graph : vector<vector<Edge<Cost>>> {
    int n;
    Graph(int _n = 0) : n(_n) { this->resize(n); }
    
    void push_directed(const int &src, const int &dst, const Cost &cost = 1) {
        (*this)[src].emplace_back(src, dst, cost);
    }
    void push_undirected(const int &src, const int &dst, const Cost &cost = 1) {
        (*this)[src].emplace_back(src, dst, cost);
        (*this)[dst].emplace_back(dst, src, cost);
    }
};

template<class T>
vector<int> topological_sort(const Graph<T> &g) {
    vector<int> res;
    vector<bool> vis(g.n, 0);
    
    auto dfs = [&](auto &&self, int curr) -> void {
        vis[curr] = true;
        for (auto &e: g[curr]) {
            if (vis[e.to]) continue;
            self(self, e.to);
        }
        res.emplace_back(curr);
    };

    for (int i = 0; i < g.n; i++) {
        if (!vis[i]) dfs(dfs, i);
    }
    
    if (res.size() != g.n) return vector<int>();
    reverse(res.begin(), res.end());
    return res; 
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    Graph<> g(n);
    for (int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;
        g.push_directed(--x, --y);
    }

    int ans = 0;
    auto v = topological_sort(g);
    vector<int> dp(n, 0);
    for (auto &x: v) {
        for (auto &e: g[x]) {
            dp[e.to] = max(dp[e.to], dp[x]+1);
        }
        ans = max(ans, dp[x]);
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 7672
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include<vector>
#include<iomanip>
#include<map>
#include <queue>
#include<cmath>
#include<cstdio>
#include<iomanip>
#include<set>
#include <bits/stdc++.h>

using namespace std;
using ll = long long int;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++) //REP(i, 5) cout<<i;
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
//#define MOD 1000000007 //10^9+7
#define MOD 10007

ll gcd(ll a, ll b) {
  ll tmp;
  if ( b > a) {
    tmp = a;
    a = b;
    b = tmp;
  }
  while (a % b !=0) {
    tmp = b;
    b = a % b;
    a = tmp;
  }
  return b;
}

int main(void){

  ll n;
  cin>>n;
  set<string> m;
  REP(i, n){
    string x;
    cin>>x;
    m.insert(x);
  }
  cout<<m.size()<<endl;
  return 0;
}

Measured memory_bytes: 19064
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, s, n) for(int i = s; i < (int)n; i++)
#define per(i, n) for(int i = n; i >= 0; i--)
#define ROF(i, s, n) for(int i = s; i >= (int)n; i--)
#define FORIT(i, A) for (auto i : A)
#define PRINT(x) cout << (x) << "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MP make_pair
#define EACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define SZ(a) int((a).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define NCLR(a) memset((a), -1 ,sizeof(a))
#define dump(x) cout << #x << " = " << (x) << "\n";
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << "\n";
#define sq(n) (n) * (n)
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef priority_queue<int> maxpq;
typedef priority_queue< int, vector<int>, greater<int> > minpq;
typedef complex<double> P;
static const double EPS = 1e-10;
static const double PI = acos( -1.0 );
static const int mod = 1000000007;
static const int INF = 1 << 29;
static const LL LL_INF = 1152921504606846976;
static const int dx[] = { -1, 0, 1, 0, 1, -1, 1, -1 };
static const int dy[] = { 0, -1, 0, 1, 1, 1, -1, -1 };

int n, m, b;
vector<vector<PII> > a;
int dp[ 153 ][ 153 ][ 153 ];

int solve( int now, int e, int w ) {
	if ( now >= n || ( w && now >= n - 1 ) ) {
		return 0;
	}
	if ( dp[ now ][ e ][ w ] >= 0 ) {
		return dp[ now ][ e ][ w ];
	}
	int res = INF;
	for ( int i = 0; i < a[ now ].size(); i++ ) {
		if ( now == 0 ) {
			res = min( res, solve( now + 1, i, w ) );
		}
		else {
			res = min( res, solve( now + 1, i, w ) + abs( a[ now - 1 ][ e ].first - a[ now ][ i ].first ) * ( a[ now - 1 ][ e ].second + a[ now ][ i ].second ) );
		}
	}
	if ( w ) {
		for ( int i = 0; i < a[ now + 1 ].size(); i++ ) {
			if ( now == 0 ) {
				res = min( res, solve( now + 2, i, w - 1 ) );
			}
			else {
				res = min( res, solve( now + 2, i, w - 1 ) + abs( a[ now - 1 ][ e ].first - a[ now + 1 ][ i ].first ) * ( a[ now - 1 ][ e ].second + a[ now + 1 ][ i ].second ) );
			}
		}
	}
	return dp[ now ][ e ][ w ] = res;
}

int main() {
	while ( ~scanf( "%d %d", &n, &m ) && n ) {
		a.resize( n );
		for ( int i = 0; i < n; i++ ) {
			scanf( "%d", &b );
			a[ i ].resize( b );
			for ( int j = 0; j < a[ i ].size(); j++ ) {
				scanf( "%d %d", &a[ i ][ j ].first, &a[ i ][ j ].second );
			}
		}
		NCLR( dp );
		printf( "%d\n", solve( 0, 0, m ) );
	}
	return 0;
}

Measured memory_bytes: 15224
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef set<int> si;
typedef map<int,int> mii;

#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) for (int i=0; i<a; i++)
#define FORd(i,a,b) for (int i = b-1; i >= a; i--)
#define F0Rd(i,a) for (int i = a-1; i >= 0; i--)
 
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
 
const int MOD = 1000000007;
double PI = 4*atan(1);

ll n,s;

ll f(ll b, ll n1) {
	if (n1<b) return n1;
	return f(b,n1/b)+(n1%b);
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n >> s;
	if (s>n) {
		cout << -1;
		return 0;
	}
	ll i = 2;
	while (i*i <= n) {
		if(f(i,n) == s) {
			cout << i;
			return 0;
		}
		i++;
	}
	for (ll j = min(s,i); j > 0; --j) {
		if ((n-(s-j)) % j == 0) {
			ll k = (n-(s-j))/j;
			if (k>j && k > (s-j)) {
				cout << k;
				return 0;
			}
		}
	}
	if (n == s) {
		cout << (n+1);
		return 0;
	}
	cout << -1;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main 
{

	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		
		String s = 		sc.next();
		
		String firstCheck = s.substring(0,(s.length()-1)/2);
		//System.out.println("firstCheck is: "+firstCheck);
		
		String seconCheck = s.substring((s.length()+3)/2 - 1, s.length());
		//System.out.println("seconCheck is: "+seconCheck);
		
		if(checkPalindrome(s) && checkPalindrome(firstCheck) && checkPalindrome(seconCheck))
		{
			System.out.println("Yes");
		}
		else
		{
			System.out.println("No");
		}
		
		
		
		

	}
	
	public static boolean checkPalindrome(String a)
	{
		String b = "";
		
		for(int i=a.length()-1; i>=0; i-- )
		{
			b += a.charAt(i);
		}
		
		//System.out.println("a is: "+a);
		//System.out.println("b is: "+b);
		
		if(a.equals(b))
		{
			return true;
		}
		
		return false;
	}

}


Measured memory_bytes: 22868
#include <stdio.h>

int main(void){
  int a;
  int b;
  int ans;
  int res;
  res = scanf("%d %d",&a,&b); 
  
  if(a > 9 || b > 9){
    printf("-1\n");
  }else{
    ans = a * b;
    printf("%d\n",ans);
  }
  return 0;
}


Measured memory_bytes: 128
using System;
class ProgramC
    {
        static void Main(string[] args)
        {
            
            //入力
            int n = int.Parse(Console.ReadLine());
            long[] a = new long[n];

            string[] input2 = Console.ReadLine().Split(' ');
            for(int i = 0;i < n;i++)
                a[i] = long.Parse(input2[i]);

            //小さい順にソートする
            Array.Sort(a);
         


            //小さい順に足していけばコストが少ない。k回引いた数だけ足す。
            for(int i = 0;i < n - 1;i++)
            {
                if(a[i] == a[i + 1])
                {
                    Console.WriteLine("NO");
                    return;
                }
            }

            //答え出力
            Console.WriteLine("YES");
        } 
    }  

Measured memory_bytes: 30668
import java.util.*;

public class Main {
    static int n;
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        solve();
    }
    public static void solve(){
        int ans=0;
        for(int i=1;i<=n;i+=2){
            if(func(i)==8){
                ans++;
            }
        }
        put(ans);
    }
    public static int func(int n){
        int ans=0;
        for(int i=1;i<=n;i++){
            if(n%i==0) ans++;
        }
        return ans;
    }

    public static void put(Object object){
        System.out.println(object);
    }
    public static String format(String string,Object... args){
        return String.format(string,args);
    }

    public static class Pair{
        final public int x,y;
        Pair(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
}


Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))
#define p(x) cout<<(x)<<endl

int mine_counter(const vector<string> s, int i, int j) {
  int count = 0;
  int hi, wi;
  hi = s.size(); wi = s[0].size();

    for (int l = max(0, i-1); l <= min(hi-1, i+1); l++) {
      for (int m = max(0, j-1); m <= min(wi-1, j+1); m++) {
        if (s[l][m] == '#'){
          count++;
        }
      }
    }

  return count;
}

int main() {
  int h, w; cin >> h >> w;
  vector<string> s(h);

  for (auto& e : s) {
    cin >> e;
  }

  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (s[i][j] != '#') {
        s[i][j] = '0' + mine_counter(s, i, j);
      }
    }
  }

  for(auto &e: s) {
    p(e);
  }
  
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int b ;
int main(){
    int a;
    while(1){
        int sou[2][1000]={};
        cin>>a;
        if(a==0)break;
        for(int q=0;q<a;q++){
            cin>>b;
            sou[0][b]=true;
        }
        for(int i=1;i<a*2+1;i++){
            if(!sou[0][i]){sou[1][i]=true;}
        }

        int aaa[2]={a,a};
        int no=0, cu=1;
        while(aaa[0]&&aaa[1]){
            for(;cu<a*2+1;cu++){
                if(sou[no][cu]){
                    aaa[no]--;
                    sou[no][cu]=false;
                    break;
                }
            }
            if(cu==2*a+1){cu=1;}
            no^=1;
        }
        cout<<aaa[1]<<"\n"<<aaa[0]<<endl;
    }
}

Measured memory_bytes: 3084
from sys import stdout
def Q(a):
    print '?', ' '.join(map(str, a))
    stdout.flush()
    res = raw_input().strip()
    return res[0]
def A(a):
    print '!', ''.join(a)
    quit()
n = int(raw_input())
a = range(1, n + 1)
b = range(n + 1, n * 2 + 1)
p = Q(a)
pp = 'R' if p == 'B' else 'B'
ans = [0] * (2 * n)
lo = 0
hi = n
while lo + 1 < hi:
    mid = (lo + hi) / 2
    r = Q(a[:-mid] + b[-mid:])
    if p == r:
        lo = mid
    else:
        hi = mid
ans[n-hi] = p
ans[2*n-hi] = pp
c = a[:-lo] + b[-lo:] if lo else a[:]
for j in xrange(n):
    if j == n - hi:
        continue
    t = c[:j] + c[j+1:] + [b[-hi]]
    r = Q(t)
    if p == r:
        ans[c[j]-1] = pp
    else:
        ans[c[j]-1] = p
c = a[-lo:] + b[:-lo] if lo else b[:]
for j in xrange(n):
    t = c[:j] + c[j+1:] + [a[-hi]]
    r = Q(t)
    if p == r:
        ans[c[j]-1] = pp
    else:
        ans[c[j]-1] = p
A(ans)


Measured memory_bytes: 3164
/*
   Creator - Glitched
   Yeet!!
*/

#include "bits/stdc++.h"

using namespace std;
#define testcases ll t;cin>>t;while(t--)
#define queries ll q;cin>>q;while(q--)
#define ll long long
#define loop(i,x,n) for(ll i=x;i<n;i++)
#define ff first
#define ss second
#define pb push_back
#define elif else if
#define flush cout<<"\n"
#define mod 1000000007
#define fastio ios_base::sync_with_stdio(false);

int main()
{
    long long n,x,sum=0;
    cin>>x>>n;
    std::vector<long> v(n);

    loop(i,0,n){
        cin>>v[i];

        sum+=v[i];
    }

    if(sum >= x)
        cout<<"Yes";
    else
        cout<<"No";
    flush;

    
}

Measured memory_bytes: 1024
n,d = map(int, input().split())
xy = [map(int, input().split()) for _ in range(n)]
x, y = [list(i) for i in zip(*xy)]

ans = 0

for i in range(n):
    if d >= ((x[i]**2) + (y[i]**2))**0.5:
        ans += 1
print(ans)

Measured memory_bytes: 116732
import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
h, w = map(int, input().split())
ans = []
for i in range(h):
    c = input()
    print(c)
    print(c)


Measured memory_bytes: 38896
#include<cstdio>
//atcoder 14 contest142
int odd(int n){
	if(n%2!=0){
		return 1; //奇数 
	}
	return 0; //偶数 
}
int main(){
	int n;
	int count = 0;
	scanf("%d",&n);
	for(int i = 1;i<=n;i++){
		if(odd(i)){
			count++;
		}
	}
	double res = count/(n*1.0);
	//printf("%d",count);
	printf("%.10f\n",res);
	return 0;
}

Measured memory_bytes: 128
// C - Go to School
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()

int main(){
	int N; cin>>N;
	vector<pair<int,int>> A;
	for(int no=1; no<=N; ++no){
		int nin; cin>>nin;
		A.emplace_back(nin, no);
	}
	sort(all(A));
	for(auto e:A) printf("%d ", e.second);
}

Measured memory_bytes: 1780
Continue = True
while Continue:
    a, op, b = input().split()
    if op == "?": break
    elif op == "/": print(int(a)//int(b))
    elif op == "+": print(int(a)+int(b))
    elif op == "-": print(int(a)-int(b))
    elif op == "*": print(int(a)*int(b))


Measured memory_bytes: 5592
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin >> n;
    ll a[n], x=0;

    for (int i = 0; i < n; ++i)
    {
    	cin >> a[i];
    	x^=a[i];
    }
    for (int i = 0; i < n; ++i)
    {
    	cout << (x^a[i])<<' ';
    }
    return 0;
}			

Measured memory_bytes: 5104
fun main() {
    val (c11, c12, c13) = readLine()!!.split(" ").map { it.toInt() }
    val (c21, c22, c23) = readLine()!!.split(" ").map { it.toInt() }
    val (c31, c32, c33) = readLine()!!.split(" ").map { it.toInt() }

    val a1 = 0
    val b1 = c11 - a1
    val b2 = c12 - a1
    val b3 = c13 - a1
    val a2 = c21 - b1
    val a3 = c31 - b1

    if (a2 + b2 == c22 && a3 + b2 == c32 && a2 + b3 == c23 && a3 + b3 == c33) {
        print("Yes")
    } else {
        print("No")
    }
}



Measured memory_bytes: 36324
/*|In The Name Of Allah|*/

#include <bits/stdc++.h>

using namespace std;

const int N = 1e2+5;

int n;
int W;
int w[N];
int v[N];
int mn = 1e9;
int mem[N][N][3*N];

int go(int idx , int tok , int totW){
    if(idx == n + 1){
        return 0;
    }
    if(~mem[idx][tok][totW])
        return mem[idx][tok][totW];
    int a = go(idx + 1 , tok , totW);
    if( (totW + w[idx]) + (1LL * (tok+1) * mn) <= W){
        a = max(a , go(idx + 1 , tok + 1 , totW + w[idx]) + v[idx]);
    }
    return mem[idx][tok][totW] = a;
}

int main(){
    scanf("%d%d" , &n , &W);
    for(int i = 1; i <= n; i++){
        scanf("%d%d" , &w[i] , &v[i]);
        if(i == 1){
            mn = w[i];
        }
        w[i] -= mn;
    }
    memset(mem , -1 , sizeof mem);
    printf("%d\n" , go(1 , 0 , 0));
}


Measured memory_bytes: 13824
// abc176_a
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF (ll)(1e9)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int idx=0;idx<(n-1);idx++) cout << (vec)[idx] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << "\n";}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    int N, X, T;
    cin >> N >> X >> T;

    int ans = (N + X - 1) / X * T;
    print(ans);

    return 0;
}


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

#define endl '\n'
#define PI acos(-1.0)
#define F first
#define S second

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int main()
{
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	
	int n, x;
	cin >> n;
	
	map<int, int> m;
	for(int i = 1; i < n; ++i) {
		cin >> x;
		m[x]++;
	}
	
	for(int i = 1; i <= n; ++i) {
		if(m.find(i) != m.end()) {
			cout << m[i] << endl;
		} else {
			cout << "0" << endl;
		}
	}
	
	return 0;
}


Measured memory_bytes: 12964
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5005;
int n,m,a[3],b[3];
ll ans,f[N*N];
int main()
{
	scanf("%d",&n);
	for(int i=0;i<3;i++)scanf("%d",&a[i]);
	for(int i=0;i<3;i++)scanf("%d",&b[i]);
	for(int i=0;i<3;i++)
	if(b[i]>a[i])
	for(int j=a[i];j<=n;j++)
	f[j]=max(f[j],f[j-a[i]]+b[i]-a[i]);
	for(int i=0;i<=n;i++)m=max(1ll*m,f[i]),f[i]=0;
	m+=n;
	for(int i=0;i<3;i++)
	if(a[i]>b[i])
	for(int j=b[i];j<=m;j++)
	f[j]=max(f[j],f[j-b[i]]+a[i]-b[i]);
	for(int i=0;i<=m;i++)ans=max(ans,f[i]);
	ans+=m;
	printf("%lld",ans);
}

Measured memory_bytes: 195584
//code by lynmisakura.wish to be accepted!
/*************************/
#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<bitset>
#include <climits>
#include<set>
#include<bitset>
using namespace std;
/***************************/
typedef long long ll;
typedef long long ijt;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef pair<int, int> pi;
typedef vector<pair<int, int>> vpi;

const long long INF = 1LL << 55;

#define itn int
#define endl '\n'
#define pb push_back
#define mp make_pair
#define ss second
#define ff first
#define dup(x,y) ((x) + (y) - 1)/(y)
#define mins(x,y) x = min(x,y)
#define maxs(x,y) x = max(x,y)
#define all(x) (x).begin(),(x).end()
#define Rep(n) for(int i = 0;i < n;i++)
#define rep(i,n) for(int i = 0;i < n;i++)
#define rrep(i,n) for(int i = n - 1;i >= 0;i--)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll qp(ll a, ll b) { ll ans = 1; do { if (b & 1)ans = 1ll * ans*a; a = 1ll * a*a; } while (b >>= 1); return ans; }
ll qp(ll a, ll b, int mo) { ll ans = 1; do { if (b & 1)ans = 1ll * ans*a%mo; a = 1ll * a*a%mo; } while (b >>= 1); return ans; }

#define _GLIBCXX_DEBUG
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main(void) {
	string s;cin >> s;
	if (s == "Sunny") {
		cout << "Cloudy" << endl;
	}
	else if (s == "Cloudy") {
		cout << "Rainy" << endl;
	}
	else {
		cout << "Sunny" << endl;
	}

}

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

int main(){
  
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  
  cout << ((abs(a-b) <= d && abs(b-c) <= d || abs(c-a) <= d) ? "Yes" : "No") << endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define f first
#define int long long
#define INTMAX 1e15+5
#define mp make_pair
#define N 1000005
#define pb push_back
#define pencho ios_base::sync_with_stdio(false);cin.tie(NULL);
#define s second
/*STL:
       (1) PRIORITY_QUEUE pq:
       -> priority_queue < int > pq; // max_heap
       -> priority_queue < int , vector < int > , greater < int > > pq; // min_heap
       -> pq.top()   --> returns the maximum or minimum element
       -> pq.push()  --> push element into the queue
       -> pq.pop()   --> remove top most element
       -> pq.empty() --> checks whether queue is empty or not

       (2) set / multiset  ss;
       --> ss.insert(key); (insertion)
       --> ss.erase(ss.find(key)) .. (deletion)
       --> ss.find(key) != ss.end() ..existence check
       --> ss.lower_bound(x) -> smallest value which is greater than or equals to x
       --> ss.upper_bound(x) --> first value strictly greater than x
       --> multiset< data_type , greater<data_type> > ms; // for max ordering

       (3) common functions
       lower_bound(v.begin(),v.end(),x) - v.begin() --> smallest value greater than or equals to x
       upper_bound(v.begin(), v.end(),x)- v.begin() --> smallest value greater than x
       memset(dp , val , sizeof(dp)) -> sets the value of array dp to val

       (4)    Comparator for set
                     struct comp {
                            bool operator()(pair<int, int>a, pair<int, int>b) {
                     };
};
*/
int mod = 1000000007;
int bp(int x, int y) {int ans = 1; x %= mod; while (y) {if (y & 1) ans = ans * x % mod; x = x * x % mod; y >>= 1;} return ans;}
int mod_inverse(int x) {return bp(x, mod - 2); }
int gcd (int a, int b) { while (b) {a %= b; swap(a, b);} return a;}
int max(int a, int b) {     if (a < b)    swap(a, b);   return a;}
int min(int a, int b) { if (a > b) swap(a, b); return a;}
int countSetBits(int n) {int count = 0; while (n) {count += n & 1; n >>= 1;} return count;}

int dp[100][100005];

int calc(int index, int rem, int n, int item[][2]) {
       if (index == n)  return 0;
       if (dp[index][rem] != -1)      return dp[index][rem];
       if (item[index][0] <= rem)     dp[index][rem] = item[index][1] + calc(index + 1, rem - item[index][0], n, item);
       dp[index][rem] = max(dp[index][rem], calc(index + 1, rem, n, item));
       return dp[index][rem];
}


void solve() {
       int n, w;      cin >> n >> w;
       int item[n][2];
       memset(dp, -1, sizeof(dp));
       for (int i = 0; i < n; i++) cin >> item[i][0] >> item[i][1];
       cout << calc(0, w, n, item);
}




signed main()
{
#ifndef ONLINE_JUDGE
       freopen("input.txt", "r", stdin);
       freopen("o.txt", "w", stdout);
#endif

       solve();
}

Measured memory_bytes: 81704
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct data{
  string str;
  int era,western;
  bool operator<(const data& right)const{
    return western<right.western;
  }
};
int main(){
  int n,q,qyear,cal,flag,i,j;
  while(1){
    cin >> n >> q;
    if(n==0&&q==0) break;
    vector<data> V(n);
    for(i=0;i<n;i++) cin >> V[i].str >> V[i].era >> V[i].western;
    sort(V.begin(),V.end());
    for(i=0;i<q;i++){
      cin >> qyear;
      flag=0;
      for(j=0;j<n;j++){
	if(j==0){
	  if(qyear<=V[j].western){
	    cal=V[j].era-V[j].western+qyear;
	    if(cal>0){
	      cout << V[j].str << ' ' << cal << endl;
	    }else cout << "Unknown" << endl;
	    flag=1;
	    break;
	  }
	}else{
	  if(V[j-1].western<qyear&&qyear<=V[j].western){
	    cal=V[j].era-V[j].western+qyear;
	    if(cal>0){
	      cout << V[j].str << ' ' << cal << endl;
	    }else cout << "Unknown" << endl;
	    flag=1;
	    break;
	  }
	}
      }
      if(flag==0){
	cout << "Unknown" << endl;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 1284
#include<bits/stdc++.h>
#include<string.h>
 
typedef long long int ll;
 
using namespace std;
 
void SieveOfEratosthenes(int n,vector <int> &primes) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          primes.push_back(p);
} 
 
ll max(ll a,ll b)
{
	if(a>b)
		return a;
	return b;
}
 
ll power(ll x, ll y,ll mod) 
{ 
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2,mod); 
    if (y%2 == 0) 
        return (temp*temp)%mod; 
    else
        return (((x*temp)%mod)*temp)%mod; 
} 
 
 
 
int main()
{
	
	int h,n;
    cin>>h>>n;
    int sum=0;
    int x;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        sum+=x;
    }
    if(sum>=h)
        cout<<"Yes\n";
    else
        cout<<"No\n";

	return 0;
}

Measured memory_bytes: 384
//#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<numeric>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#include<queue>
#include<list>
using namespace std;

typedef long long ll;

#define MOD 1000000007

class Comb{
private:
  ll *fac,*finv,*inv;
public:
  Comb(){
    fac = new ll[1000000];
    finv = new ll[1000000];
    inv = new ll[1000000];
    fac[0] = 1;
    for(int i=1;i<1000000;i++){
      fac[i] = i*fac[i-1];
      fac[i] %= MOD;
    }
    inv[1] = 1;
    for(int i=2;i<1000000;i++){
      inv[i] = MOD-inv[MOD%i]*(MOD/i)%MOD;
    }
    finv[0] = 1;
    for(int i=1;i<1000000;i++){
      finv[i] = inv[i]*finv[i-1];
      finv[i] %= MOD;
    }
  }
  ll calc(ll n,ll k){
    ll c = fac[n];
    c *= finv[k];c %= MOD;
    c *= finv[n-k];c %= MOD;
    return c;
  }
};

int main(){
  double n;
  cin >> n;
  int ans = floor(n/1.08);
  if(floor(1.08*ans) == n){
    cout << ans << endl;
    return 0;
  }
  else if(floor(1.08*(ans+1)) == n){
    cout << ans+1 << endl;
    return 0;
  }
  cout << ":(" << endl;


  return 0;
}


Measured memory_bytes: 256