akhauriyash/Code-Regression huggingface dataset:
// this program implements Dinitz's algorithm

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

const int N = 110;
const int M = 2010;
const int inf = 0x3fffffff;

struct Edge {
	int to, cap, cost, next;
} es[M];

int S, T;  // source, sink
int SIZE = 0; // number of edges
int h[N]; // pointer to edge list
int dist[N], queue[N], inq[N]; // for calculating shortest path
int prev[N];

// add forward and backtracked edge
void add(int u, int v, int cap, int cost) {
	int i = SIZE++;
	es[i].to = v;
	es[i].cap = cap;
	es[i].cost = cost;
	es[i].next = h[u];
	h[u] = i; 
	int j = SIZE++;
	es[j].to = u;
	es[j].cap = 0;
	es[j].cost = -cost;
	es[j].next = h[v];
	h[v] = j; 
}

// returns whether find a shortest path from S to T
bool sssp(int n) {
	int front = 0, back = 0;
	for (int i = 0; i < n; i++) {
		dist[i] = inf;
		inq[i] = 0;
	}
	queue[back++] = S;
	dist[S] = 0;
	while (front != back) {
		int x = queue[front++];
		if (front == N) front = 0;
		inq[x] = 0;
		for (int i = h[x]; i != -1; i = es[i].next)
			if (es[i].cap > 0) {
				int y = es[i].to;
				int new_d = dist[x] + es[i].cost;
				if (new_d < dist[y]) {
					dist[y] = new_d;
					prev[y] = x;
					if (!inq[y]) {
						queue[back++] = y;
						if (back == N) back = 0;
						inq[y] = 1;
					}
				}
			}
	}
	return (dist[T] < inf);
}

// returns the flow pushed from x to T
int dfs(int x, int flow) {
	if (x == T) return flow;
	int ret = 0;
	for (int i = h[x]; i != -1 && flow > 0; i = es[i].next) {
		int y = es[i].to;
		if (prev[y] != x) continue;
		int f = dfs(y, std::min(flow, es[i].cap));
		if (f != 0) {
			es[i].cap -= f;
			es[i^1].cap += f;
			ret += f;
			flow -= f;
		}
	}
	return ret;
}

void run() {
	int n, m, u, v, c, d, flow, cost = 0;
	scanf("%d%d%d", &n, &m, &flow);
	memset(h, -1, sizeof(h));
	S = 0, T = n - 1;
	for (int i = 0; i < m; i++) {
		scanf("%d%d%d%d", &u, &v, &c, &d);
		add(u, v, c, d);
	}
	while (flow > 0 && sssp(n)) {
		int f = dfs(S, flow);
		cost += f * dist[T];
		flow -= f;
	}
	if (flow > 0)
		printf("-1\n");
	else
		printf("%d\n", cost);
}

int main() {
	run();
}

Measured memory_bytes: 2752
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>

using namespace std;
#define int long long int
const int INF = 1001001001001001LL;
const int MOD = 1000000007;

int di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
int dj[] = {0, 1, 0, -1, 1, 1, -1, -1};

signed main(){
    
    string s, t; cin >> s >> t;
    int n = (int)s.size();
    int m = (int)t.size();

    vector<vector<int> > dp(n + 1, vector<int> (m + 1, 0));
    dp[0][0] = 1;

    for(int i = 0; i < n; i++){
        for(int j = 0; j <= m; j++){
            if(dp[i][j] == 0) continue;

            dp[i + 1][j] += dp[i][j];
            dp[i + 1][j] %= MOD;

            if(j != m && t[j] == s[i]){
                dp[i + 1][j + 1] += dp[i][j];
                dp[i + 1][j + 1] %= MOD;
            }
        }
    }

    cout << dp[n][m] << endl;
    return 0;
}



Measured memory_bytes: 10680
#include<bits/stdc++.h>
using namespace std;
#define mk make_pair
int main(){
  int s,d,m;
  while(cin>>s>>d>>m){
    int dp[5001][301]={},pp=0,ppp=100000000,k,w,p,cc;
    vector<pair<int,int> >a[101],c;
    for(int i=0;i<s;i++){
      cin>>k;
      for(int j=0;j<k;j++){
        cin>>w>>p;
        a[i].push_back(mk(p,w));
      }
    }
    for(int i=0;i<d;i++){
      cin>>cc;
      for(int j=0;j<a[cc].size();j++)
        c.push_back(a[cc][j]);
    }
    for(int i=1;i<=c.size();i++)
     for(int j=0;j<=m;j++){
      if(j<c[i-1].first)
        dp[i][j]=dp[i-1][j];
      else
         dp[i][j]=max(dp[i-1][j-c[i-1].first]+c[i-1].second,dp[i-1][j]);
      pp=max(pp,dp[i][j]);
     }
     /*for(int i=0;i<=c.size();i++){
      for(int j=0;j<=m;j++)cout<<dp[i][j]<<' ';
        cout<<endl;
     }*/
    for(int i=0;i<=c.size();i++)
      for(int j=0;j<=m;j++)
        if(pp==dp[i][j])ppp=min(ppp,j);
    cout<<pp<<' '<<ppp<<endl;
  }
}

Measured memory_bytes: 9068
def resolve():
    n = int(input())
    b = list(map(int, input().split()))
    a = [b[0]]
    for i in range(1, n - 1):
        a.append(min(b[i - 1], b[i]))
    a.append(b[-1])
    print(sum(a))


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 3064
q, h, s, d = map(int, input().split())
n = int(input())

half = min(2 * q, h)
one = min(2 * half, s)
two = min(2 * one, d)

l = zip([2, 1, 0.5, 0.25], [two, one, half, q])

ans = 0
rest = n
for vol, cost in l:
    ans += (rest // vol) * cost
    rest %= vol
    if rest == 0:
        print(ans)
        break

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main()
{
	string a,b;
	getline(cin,a);
	getline(cin,b);
	for(int i=0;i<a.size();i++)
	{
		cout<<a[i];
		if(i!=b.size())cout<<b[i];
	}
	cout<<endl;
	return 0;
}



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

using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;

int main(){
	int N;
	scanf("%d", &N);
	vector<int> v1, v2;
	for (int i = 0; i < N; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		v1.pb(x);
		v2.pb(y);
	}
	sort (v1.begin(), v1.end());
	sort (v2.rbegin(), v2.rend());
	if (N % 2) {
		printf("%d\n", v2[N / 2] - v1[N / 2] + 1);
	} else printf("%d\n", v2[N / 2 - 1] + v2[N / 2] - v1[N / 2 - 1] - v1[N / 2] + 1);
}

Measured memory_bytes: 5028
import java.util.Scanner;

class Main{
	public static void main(String[] args) {



		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int T = scanner.nextInt();
		int[] c = new int[N] ;
		int[] t = new int[N] ;


		for(int i = 0;i < N;i++){
			c[i] =  scanner.nextInt();
			t[i] =  scanner.nextInt();

		}
		int ans = 100000;
		for(int i= 0;i < N;i++){
			if(t[i] <= T){
			ans = 	Math.min(ans, c[i]);
			}
		}
		if(ans == 100000){
			System.out.println("TLE");
		}else{
		System.out.println(ans);


		}
	}


}

class Pair implements Comparable{
	int from;
	int end;
	@Override
	public int compareTo(Object other) {
		Pair otherpair = (Pair)other;

		return end - otherpair.end;
	}
}



Measured memory_bytes: 21716
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int SIZEN = 3 * 100010;
const int SIZEM = 100010;
int l[SIZEN] = {0},r[SIZEN] = {0};
int ans[SIZEM] = {0};
int N,M;


void Input(){
	scanf("%d%d",&N,&M);
	for(int i = 1;i <= N;i++)scanf("%d%d",&l[i],&r[i]);
}


void Judge(int x){
//	printf("x = %d\n",x);
	int ll,rr;
	int n = sqrt(l[x]);
	int last = M+1;
	for(int i = 1;i <= n;i++){
		if(l[x]%i == 0) ll = l[x]/i;
		else ll = l[x]/i+1;
		rr = r[x]/i;
		rr = min(last-1,rr);
		last = min(ll,last);
		if(ll > rr)continue;
		ans[ll]++;ans[rr+1]--;
	}
	for(int i = 1;i < last;i++){
		if(l[x]%i == 0) ll = l[x]/i;
		else ll = l[x]/i+1;
		rr = r[x]/i;
		if(ll > rr)continue;
		
		ans[i]++;ans[i+1]--;
	} 
} 
void Work(){
	for(int i = 1;i <= N;i++)Judge(i);
	for(int i = 1;i <= M;i++)ans[i] += ans[i-1];
	for(int i = 1;i <= M;i++)printf("%d\n",ans[i]);
}
int main(){
	Input();
	Work();
	return 0;
}

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

using namespace std;

int main() {

	string S;
	cin >> S;
   int a=0;
   for(int i=1;i<S.size();i++){
      if(S[i]=='0'&&S[i-1]=='0'){
         S[i]='1';
         a++;
      }
      else if(S[i]=='1'&&S[i-1]=='1'){
         S[i]='0';
         a++;
      }
   }
   cout<<a<<endl;
   return 0;
}



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

int a[100000],b[100000];
int binary(int l,int r,int c){
    while(l<=r){
        int p=(l+r)/2,x,y;
        if(a[p]==c)return 1;
        else if(c<a[p])r=p-1;
        else l=p+1;
    }
    return 0;
}

int ar(int n){
    for (int i=0;i<n;i++) {
        cin>>b[i];
        for(int j=0;j<i;j++)
        if(b[i]==b[j])i--,n--;
	   }
    return n;
}

int main(){
    int p,q,n=0;
    cin>>p;
    for(int i=0;i<p;i++)cin>>a[i];
    cin>>q,q=ar(q);
    for(int i=0;i<q;i++)
        n+=binary(0,p-1,b[i]);
    cout<<n<<endl;
    
    return 0;
}

Measured memory_bytes: 3572
A, B, C, K = map(int, input().split())

tmp_A = B + C
tmp_B = A + C
if abs(tmp_A - tmp_B) > (10 ** 18):
    print('Unfair')
else:
    if K % 2 == 1:
        print(tmp_A - tmp_B)
    else:
        print(tmp_B - tmp_A)

Measured memory_bytes: 2940
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

goal = ord("z") + 1 
s = input()
k = int(input())
n = len(s)
ans = [0] * n
for i,si in enumerate(s):
  if si == "a":ans[i] = "a"
  elif goal - ord(si) <= k:
    k -= goal - ord(si)
    ans[i] = "a"
  else:
    ans[i] = si
m = k % 26
ans[-1] = chr((ord(ans[-1]) - ord("a") + m)%26 + ord("a"))
print(*ans,sep="")

Measured memory_bytes: 53204
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <string>
#define MAX(x, y)	(((x) > (y))? (x) : (y))
#define ABS(x)		(((x) < 0)? (-1*(x)) : (x))
#define REPI(x,y)	for (i=(x);i<(y);i++)
#define REPJ(x,y)	for (j=(x);i<(y);i++)
#define MEMCLR(X)	memset((X),0,sizeof((X)))

int i,j,Q,L,R;
bool np[100001];
int cnt[100002];
using namespace std;

int main() {


	for (i=2;i<=100000;i++) if (!np [i]) for (j=i+i;j<=100000;j+=i)
		np[j]= true ;
	for(i=3;i<=100000;i+=2) if(!np[i]&&!np[(i+1)/2])cnt[i]++;
	for(i=3;i<=100000;i++)cnt[i]+=cnt[i-1];
	cin >> Q;

	while (Q--) {
		cin >> L >> R;
		cout << cnt[R] - cnt[L-1] << endl;
	}
	
	return 0;
}


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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef pair<ii, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef map<ll, ll> mpii;
typedef unordered_map<ll, ll> umpii;

#define pb(v) push_back(v)
#define all(v) v.begin(), v.end()
#define upb(v, key) (upper_bound(all(v), key) - v.begin())
#define lob(v, key) (lower_bound(all(v), key) - v.begin())

ll inf = 1e9;
ll INF = inf * 1ll * inf;
ll mod = 1e9 + 7;
double eps = 1e-9;
const ld pi = ld(3.1415926535897932384626433832795);
ll dr[] = {-1, 0, 0, 1};
ll dc[] = {0, 1, -1, 0};

template <class TH>
void _dbg(const char *sdbg, TH h) { cerr << sdbg << '=' << h << endl; }
template <class TH, class... TA>
void _dbg(const char *sdbg, TH h, TA... a)
{
  while (*sdbg != ',')
    cerr << *sdbg++;
  cerr << '=' << h << ',';
  _dbg(sdbg + 1, a...);
}
template <class T>
ostream &operator<<(ostream &os, vector<T> V)
{
  os << "[";
  for (auto vv : V)
    os << vv << ",";
  return os << "]";
}
template <class L, class R>
ostream &operator<<(ostream &os, pair<L, R> P)
{
  return os << "(" << P.st << "," << P.nd << ")";
}
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)

/*...................................................*/
ll dp[3010][3010][2];
ll a[3010];

main()
{
  int n, i, j;
  cin >> n;
  for(i = 0; i < n; i++)
  cin >> a[i];
  for(i = 0; i < n; i++)
  dp[i][i][0] = a[i], dp[i][i][1] = -a[i];

  for(i = n - 1; i >= 0; i--)
  for(j = i + 1; j < n; j++)
  {
    dp[i][j][0] = max((i + 1 == n? -INF: dp[i + 1][j][1] + a[i]), dp[i][j - 1][1] + a[j]);
    dp[i][j][1] = min((i + 1 == n? INF: dp[i + 1][j][0] - a[i]), dp[i][j - 1][0] - a[j]);
  }
  cout << dp[0][n - 1][0];
}

Measured memory_bytes: 141568
import fractions

A, B = map(int, input().split())

N = fractions.gcd(A, B)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

  
if((A-1)*(B-1) == 0):
  print(1)
else:
  print(1 + len(factorization(N)))

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

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 300; 
int d[N][N];

void solve() {
    int n; cin >> n;
    memset(d, INF, sizeof d);
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        for (int j = 0; j < n; j++) {
            if (s[j] == '1') d[i][j] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        d[i][i] = 0;
    }
    vector<int> co(n, -1);
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (co[u] == -1) co[u] = 0;
        for (int v = 0; v < n; v++) {
            if (d[u][v] == 1) {
                if (co[v] == -1) {
                    co[v] = co[u] ^ 1;
                    q.push(v);
                } else if ((co[v]^co[u]) == 0) {
                    cout << -1; return;
                }
            }
        }
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (d[i][k] < INF && d[k][j] < INF) {// for negative
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            res = max(res, d[i][j]);
        }
    }
    cout << res+1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


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

using namespace std;

#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<int, pii> para;
const int inf = 1e9 + 7;
const int maxN = 1e6 + 5;

ll n, arr[maxN], ans;
ll k;

void sim() {
	ll maxim = 49;
	ll ind = -1;
	REP(i, 50) {
		if (arr[i] > maxim) {
			maxim = arr[i];
			ind = i;
		}
	}
	if (ind == -1) return;
	ans++;
	REP(i, 50) {
		if (ind != i) arr[i]++;
		else arr[i] -= 50;
	}
	sim();
}

int main() {
	ios_base::sync_with_stdio(0);
	cin>>k;
	ll minim = (k / 50);
	REP(i, 50)
		arr[i] = minim + i;
	//REP(i, 50) cout<<arr[i]<<" ";
	k -= minim * 50;
	REP(ind, k) {
		arr[ind] += 50;
		REP(i, 50)
			if (i != ind) arr[i]--;
	}
	//sim();
	cout<<50<<endl;
	REP(i, 50) cout<<arr[i]<<" ";
	return 0;
}


Measured memory_bytes: 256
package main
import (
	"fmt"
)

func main() {
	var N int
	fmt.Scan(&N)
	if N == 1 {
		fmt.Println("Hello World")
	} else if N == 2 {
		var A,B int 
		fmt.Scan(&A,&B)
		fmt.Println(A + B)
	}
}

Measured memory_bytes: 512
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



const int N = 110;
short h, w, a[N][N];
char s[N][N];
short dp[N][N][N];
short C(int x1, int y1, int x2, int y2) {
	if (x1>x2||y1>y2) return 0;
	--y1,--x1;
	return a[x2][y2]-a[x1][y2]-a[x2][y1]+a[x1][y1];
}
void chkmax(short &a, short b) {a<b?a=b:0;}
int main() {
	scanf("%hd%hd", &h, &w);
	int x, y;
	REP(i,1,h) { 
		scanf("%s",s[i]+1);
		REP(j,1,w) a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+(s[i][j]=='o');
		REP(j,1,w) if (s[i][j]=='E') x = i, y = j;
	}
	short ans = 0;
	PER(a,1,x) REP(c,x,h) PER(b,1,y) REP(d,y,w) {
		int x1=1-x+c,x2=h-x+a;
		int y1=1-y+d,y2=w-y+b;
		short r = dp[b][c][d];
		if (a>1) {
			chkmax(dp[b][c][d],r+C(max(x1,a-1),max(y1,b),min(x2,a-1),min(y2,d)));
		}
		if (c<h) {
			chkmax(dp[b][c+1][d],r+C(max(x1,c+1),max(y1,b),min(x2,c+1),min(y2,d)));
		}
		if (b>1) {
			chkmax(dp[b-1][c][d],r+C(max(x1,a),max(y1,b-1),min(x2,c),min(y2,b-1)));
		}
		if (d<w) {
			chkmax(dp[b][c][d+1],r+C(max(x1,a),max(y1,d+1),min(x2,c),min(y2,d+1)));
		}
		chkmax(ans,r);
	}
	printf("%hd\n", ans);
}








Measured memory_bytes: 2688
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<set<int>> Adj(n);
  for (int i = 0; i < n; i++){
    int u, k;
    cin >> u >> k;
    u--;
    for (int j = 0; j < k; j++){
      int v;
      cin >> v;
      v--;
      Adj[u].insert(v);
    }
  }
  for (int i = 0; i < n; i++){
    for (int j = 0; j < n; j++){
      if (Adj[i].count(j)){
        cout << 1;
      } else {
        cout << 0;
      }
      if (j < n - 1){
        cout << ' ';
      }
    }
    cout << endl;
  }
}


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


int main() {
  int n;  cin >> n;
  vector<int> v(n), w(n);
  rep (i, n) {
    char x;  cin >> x;
    if (x == 'R') v[i] = 0;
    else v[i] = 1;
  }

  w = v;
  sort(all(w));

  int a=0, b=0;
  rep (i, n) {
    if (v[i] == 0) {
      if (w[i] == 1) ++a;
    }
    if (v[i] == 1) {
      if (w[i] == 0) ++b;
    }
  }

  cout << min(a, b) + abs(a - b) << endl;
}

Measured memory_bytes: 4820
#include<bits/stdc++.h>
using namespace std;
struct node{int h,p;bool operator<(node b) const {return h+p<b.h+b.p;}}t[5005];
int n,ans=0;long long dp[5005];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&t[i].h,&t[i].p);
	sort(t+1,t+n+1),memset(dp,0x3f,sizeof(dp)),dp[0]=0;
	for(int i=1;i<=n;i++) for(int j=i;j>=1;j--) if(dp[j-1]<=t[i].h) dp[j]=min(dp[j],dp[j-1]+t[i].p);
	for(int i=0;i<=n;i++) if(dp[i]<dp[n+1]) ans=i;
	return printf("%d\n",ans),0;
}

Measured memory_bytes: 3856
#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
using ld=long double;
using VI=vector<ll>;
using VD=vector<ld>;
using VVI=vector<VI>;
using VC=vector<char>;
using VVC=vector<VC>;
using VS=vector<string>;
using PLL =pair<ll,ll>;
using PLD=pair<ld,ld>;
using VPLL=vector<PLL>;
#define REP(i,n) for(ll i=0;i<(ll)(n);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 FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element((x).begin(),(x).end())
#define MIN(x) *min_element((x).begin(),(x).end())
#define SORTR(x) sort((x).rbegin(),(x).rend())
#define SORT(x) sort((x).begin(),(x).end())
#define SUM(x) accumulate((x).begin(),(x).end(), 0)
#define FILL(x,a) fill(x.begin(),x.end(),a)
#define EACH(i,x) for(typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i)

const int INF  = 1<<30;
const ld EPS   = 1e-10;
const int MOD  = int(1e9)+7;
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; }
template <class BidirectionalIterator>
bool next_partial_permutation(BidirectionalIterator first, BidirectionalIterator middle,BidirectionalIterator last){reverse(middle, last); return next_permutation(first , last);}
#define COUT(x) cout<<x<<"\n"


void Main()
{
	ll result=0;
	string S;
	cin>>S;
	VI ten(SIZE(S),1);
	const int DIV=2019;
	FOR(i,1,SIZE(S)){
		/*2019は2でも5でも割り切れないので、
		 * mod2019では10に逆元が存在します。
		 * そのため、10nが2019の倍数であることと
		 * nが2019の倍数であることは同値です。
		 * (2020ではこの性質が成り立たないので、
		 * この問題では2019が使われています*/
		ten[i]=10*ten[i-1];	//10の倍数？？
		ten[i]%=DIV;		//2019で割ったあまり
	}
	ll tmp=0;
	ll appear[3000];//あまりの数？？
	appear[0]=1;
	FORD (i,SIZE(S)-1,0) {
		// k+ 1文字目以降の数字列を整数とみなした時の値an+ 10an−1+...+ 10n−k−1ak+1をTkとします
		tmp+=ten[SIZE(S)-i-1]*(S[i]-'0');	//
		//すると、(i, j)が条件をみたすのは10n−j(Ti−1−Tj)が2019の倍数のとき、すなわちTi−1==Tj(mod2019)のときです
		tmp%=DIV;							//
		//modの値が同じごとに個数を計算して足せば良いことになります。Ti= 10Ti+1+aiより、
		result+=appear[tmp];				//2019で割り切れる数だけ加える？
		//これはDPで計算でき、modごとにm(m−1)/2 (mはTimod2019がある値になるiの個数)を足せば良いです。
		appear[tmp]++;						//
	}
	cout << result << "\n";
	return;
}

int main()
{
	std::cin.tie(0);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}


Measured memory_bytes: 5152
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n, w[101000], pv, Res[101000];
long long sum = 0;
vector<int>E[101000];
void DFS(int a, int pp) {
	Res[a] = w[pv];
	pv--;
	if (pp)sum += Res[a];
	for (auto &x : E[a]) {
		if (x == pp)continue;
		DFS(x, a);
	}
}
int main() {
	int i, a, b;
	scanf("%d", &n);
	for (i = 1; i < n; i++) {
		scanf("%d%d", &a, &b);
		E[a].push_back(b);
		E[b].push_back(a);
	}
	for (i = 1; i <= n; i++)scanf("%d", &w[i]);
	sort(w + 1, w + n + 1);
	pv = n;
	DFS(1, 0);
	printf("%lld\n", sum);
	for (i = 1; i <= n; i++)printf("%d ", Res[i]);
}

Measured memory_bytes: 3584
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np
from functools import reduce

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

n, x = rm()
li = [ri() for _ in range(n)]
a = min(li)
x -= sum(li)
print(n + x//a)












Measured memory_bytes: 27080
/*..............................................*\
Author:Kishor Kumar Paroi
Dept:CSE-1703053
email.kishor.josephite@gmail.com
RUET,BANGLADESH
\*---------------------------*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <string>
#include <fstream>
#include <sstream>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include<bits/stdc++.h>
#include<iostream>
#include<iterator>

#define max(a,b) ((a>b)?a:b)                        //finding max
#define min(a,b) ((a<b)?a:b)                        //finding min
#define Max(a,b,c) max(a,max(b,c))                  //finding max between 3 numbers
#define Min(a,b,c) min(a,min(b,c))                  //finding min between 3 numbers
#define Pi acos(-1.0)                               //defining Pi for mathematical uses
#define Clear(a) memset(a,0,sizeof(a))              //clearing memory of an array
#define setfalse(a) memset(a,false,sizeof(a))       //setting the array into false
#define settrue(a) memset(a,true,sizeof(a))         //setting the array into true
#define clrstr(a) memset(a,'\0',sizeof(a))          //setting string array to null
#define open freopen("input.txt","r",stdin)         //opening input file
#define close freopen ("output.txt","w",stdout)     //opening output file
#define Case(a) printf("Case %d: ",a)               //printing case number
#define caseh(a) printf("Case #%d: ",a)             //printing case number having '#'
#define getcase(a) scanf("%d",&a)                   //scanning case number
#define caseloop(a,b) for(a=1;a<=b;a++)             //making case loop
#define EPS 1e-9                                    //small value for avoiding preccesion error
#define LL long long                                //long long short form
#define fori(i,n) for(int i=1;i<=n;++i)
#define forn(i,n) for(int i=0;i<n;++i)
#define sz(x) int(x.size())
#define error(x) cout<<#x<<" "<<x<<endl
#define IOS  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define vi vector<int>v
//const int N=100*1000;
//const int mod=1e9+7;

//# define int min3(int a,int b,int c){return min(a,min(b,c));}
//#define int max3(int a,int b,int c){return max(a,max(b,c));}
//#define int min4(int a,int b,int c,int d){return min(min(a,b),min(c,d));}
//#define int max4(int a,int b,int c,int d){return max(max(a,b),max(c,d));}

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string s;
    cin>>s;
    int x,m;
    vi;
    //m=abs(753-a[0]);
    for(int i=0; i<s.size(); i++)
    {
        int a;
        a=stoi(s.substr(i,3));
        v.push_back(abs(753-a));
    }
    sort(v.begin(),v.end());
    cout<<v.front();
    cout<<endl;
}



Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

typedef int64_t  ll;
typedef uint64_t ull;

#define rep(i,n)   for (int i = 0; i < (n); i++)
#define rrep(i,n)  for (int i = (n)-1; i >= 0; i--)
#define rep1(i,n)  for (int i = 1; i <= (n); i++)
#define rrep1(i,n) for (int i = (n); i > 0; i--)

ll a, b, m, n, tmp;
int main(void) {
    cin >> a >> b;
    m = max(a,b);
    n = min(a,b);
    while (m%n != 0) {
        tmp = n;
        n = m%n;
        m = tmp;
    }
    cout << a*b/n << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <map>
#include <numeric>
using namespace std;

int main()
{
  int N,ans=0,now=1;
  cin>>N;
  vector<int> a(N+1);
  for(int i=1;i<=N;i++){
    cin>>a[i];
  }
  while(true){
    ans++;
    now=a[now];
    if(now==2){
      cout<<ans<<endl;
      break;
    }
    if(ans>100010){
      cout<<-1<<endl;
      break;
    }
  }
}


Measured memory_bytes: 640
#include <iostream>
#include <bitset>
#include <fstream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
//#include <boost/multiprecision/cpp_int.hpp>

const double EPS = (1e-10);


using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const Int MOD = 1000000007;

Int mod_pow(Int x, Int n) {
    Int res = 1;
    while(n > 0) {
        if(n & 1) res = (res * x) % MOD; //ビット演算(最下位ビットが1のとき)
        x = (x * x) % MOD;
        n >>= 1; //右シフト(n = n >> 1)
    }
    return res;
}

Int a[300005];

int check(int i){
    if (a[i] > a[i-1]) return 1;
    else if (a[i] == a[i-1]) return 0;
    else return -1;
}

int main(){
    cin.tie(0);
    
    int N;
    cin >> N;
    for (int i = 0; i < N; i++){
        cin >> a[i];
    }
    int ans = 1;
    if (N == 1 || N == 2){
        cout << ans << endl;
        return 0;
    }
    int flag1 = 0;
    for (int i = 2; i < N; i++){
        if (flag1 == 0) flag1 = check(i-1);
        int flag2 = check(i);
        if (flag1 * flag2 == -1){
            ans++;
            i++;
            flag1 = 0;
        }
    }
    cout << ans << endl;
    return 0;
} 


Measured memory_bytes: 1024
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
  let stdin = stdin();
  let stdin = stdin.lock();
  let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char)
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
  token.parse().ok().expect("failed to parse token")
}

use std::cmp::{max, min};

fn main() {
  let r = read::<i32>();

  if r < 1200 {
    println!("ABC");
  } else if r < 2800 {
    println!("ARC");
  } else {
    println!("AGC");
  }
}



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

// #define int ll
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using si = set<int>;
using ii = pair<int, int>;
using vii = vector<ii>;

#define rep(i, n) for (int i = 0; i < n; i++)
#define dotc()    int tcs; if (cin >> tcs) rep(tc, tcs)
#define sz(x)     (int)x.size()
#define eb        emplace_back
#define pb        push_back
#define mp        make_pair
#define all(x)    x.begin(), x.end()
#define rall(x)   x.rbegin(), x.rend()
#define fi        first
#define se        second

int inf(0x3fffffff);
int mod(1000000007);
double pi(acos(-1.0));

int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL
  freopen("io\\in.txt", "r", stdin);
  freopen("io\\out.txt", "w", stdout);
#endif

  int x, y, a, b, c;
  cin >> x >> y >> a >> b >> c;
  vi p(a), q(b), r(c);
  rep(i, a) cin >> p[i];
  rep(i, b) cin >> q[i];
  rep(i, c) cin >> r[i];
  sort(rall(p));
  sort(rall(q));
  sort(rall(r));

  vi v(x + y);
  copy(p.begin(), p.begin() + x, v.begin());
  copy(q.begin(), q.begin() + y, v.begin() + x);
  sort(all(v));

  ll sum = accumulate(all(v), 0ll);
  rep(i, c) {
    if (r[i] > v[i]) sum += r[i] - v[i];
    else break;
  }

  cout << sum;

  return 0;
}


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

using namespace std;

int main(){
 string s;
  cin >> s;
  int n;
  cin >> n;
  
  
 string t="";
  
  for(int i=0;i<s.length();i+=n){
   t+=s[i];
  }
  
  
  cout << t << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
using ldb = long double;
using pa = pair < int, int >;
using vec = vector < int >;
template < typename T > using index_set = tree < T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update >;
template < typename T > using MinPriorityQueue = priority_queue < T, vector < T >, greater < T > >;
#define pb push_back
#define all(c) c.begin(),c.end()
#define unique_sort(x) sort(all(x)), x.resize(distance(x.begin(), unique(all(x))))
#define F  first
#define S  second
#define f(i,x,n) for(int i=x;i<n;i++) 
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

const int MOD = 1e9 + 7, INF = INT_MAX, N = 5e5 + 10;
const double PI = acos(-1);
const int LINF = LLONG_MAX;
int32_t main() {
    fast();
    int n;
    cin >> n;
    vector<int>q(n);
    f(i,0,n){
        cin >> q[i];
    }
    unique_sort(q);
    if(q.size()==n){
        cout<<"YES\n";
    }
    else
        cout<<"NO\n";
    return 0;
}



Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
using namespace std;
int x[10][100];
int main() {
	int n, cnt = 0, cnt2;
	while (true) {
		cin >> n; cnt2 = 0; if (n == 0) { break; }
		cnt++; cout << "Case " << cnt << ":" << endl;
		int cx = 0, cy = 0, d = 0;
		while (true) {
			cnt2++; x[cx][cy] = cnt2;
			if (n % 2 == 0) {
				if (cx == n - 1 && cy == 0) { cnt2--; }
			}
			else {
				if (cx == 0 && cy == n - 1) { cnt2--; }
			}
			if (cx == n - 1 && cy == n - 1) { break; }
			if (d == 1) { cx++; cy--; if (cy == 0 || cx == n - 1) { d = 0; } }
			else if (d == 2) { cx--; cy++; if (cx == 0 || cy == n - 1) { d = 0; } }
			else if (cx == 0) { cy++; d = 1; }
			else if (cy == n - 1) { cx++; d = 1; }
			else if (cy == 0) { cx++; d = 2; }
			else if (cx == n - 1) { cy++; d = 2; }
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				printf("% 3d", x[i][j]);
			}
			cout << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1208
#include <iostream>
#include <string>
//#include <array>

bool shitumon(int i)
{
    std::cout << i << '\n';
    std::string res;
    std::cin >> res;
    if (res == "Male") {
        return 0;
    } else if (res == "Female") {
        return 1;
    } else {
        exit(0);
    }
}

void judge(int& a, int& b, bool& gen_a)
{
    if (b - a == 2) {
        shitumon(a + 1);
        shitumon(a + 2);
    }
    bool gender_next = shitumon(a + ((b - a) / 4) * 2);
    if (gender_next == gen_a) {
        a = a + ((b - a) / 4) * 2;
        gen_a = gender_next;
    } else {
        b = a + ((b - a) / 4) * 2;
    }
}


int main()
{
    int n;
    std::cin >> n;
    int a = 0;
    bool gen_a;
    int b = n - 1;

    gen_a = shitumon(0);

    //2番目以降の判定
    while (true) {
        judge(a, b, gen_a);
    }
    return 0;
}


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

#define _1 first
#define _2 second
#define pb push_back
#define mp make_pair
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define uni(x) (x).erase(unique(all(x)), (x).end())
#define reset(x, y) memset(x, y, sizeof(x))
#define BUG(x) cerr << #x << " = " << (x) << endl
#define BUGP(x) cout << #x << " = " << (x)._1 << ", " << (x)._2 << endl
using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;

const int dr[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dc[] = {0, -1, 0, 1, -1, 1, -1, 1};
// Head

const int N = 1123456;
const int M = 1000000;
const int MOD = 998244353;

int n;
LL w[N], cnt[N];

LL inv(LL x) {
    int pw = MOD - 2;
    LL ans = 1;
    while (pw) {
        if (pw & 1) ans = ans * x % MOD;
        pw >>= 1;
        x = x * x % MOD;
    }
    return ans;
}

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

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        ++cnt[x];
    }

    for (int i = 1; i <= M; ++i) {
        w[i] = (inv(i) + w[i]) % MOD;
        for (int j = i * 2; j <= M; j += i) w[j] = (w[j] - w[i] + MOD) % MOD;
    }

    //cout << w[1] << ' ' << w[2] << endl;

    LL ans = 0;
    for (int i = 1; i <= M; ++i) {
        LL sum = 0;
        LL sum2 = 0;
        for (int j = i; j <= M; j += i) {
            sum = (sum + cnt[j] * j) % MOD;
            sum2 = (sum2 + cnt[j] * j * j) % MOD;
        }

        LL cur = (sqr(sum) - sum2 + MOD) % MOD;
        cur = cur * w[i] % MOD;
        //if (i < 10) cout << cur << endl;
        ans = (ans + cur) % MOD;
    }

    cout << ans * inv(2) % MOD << '\n';
    return 0;
}

Measured memory_bytes: 16896
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

import java.util.*;

public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);

        int T = in.nextInt();
        for (int i=0;i<T;i++) {
        	int N = in.nextInt();
        	int[] K = new int[N];
        	int[] L = new int[N];
        	int[] R = new int[N];
        	long ans = 0L;
        	ArrayList<HashSet<Integer>> list_l = new ArrayList<HashSet<Integer>>();
        	ArrayList<HashSet<Integer>> list_r = new ArrayList<HashSet<Integer>>();
        	for (int j=0;j<N;j++) {
        		HashSet<Integer> add_l = new HashSet<Integer>();
        		HashSet<Integer> add_r = new HashSet<Integer>();
        		list_l.add(add_l);
        		list_r.add(add_r);
        	}
        	for (int j=0;j<N;j++) {
        		K[j] = in.nextInt();
        		L[j] = in.nextInt();
        		R[j] = in.nextInt();
        		// ans += Math.min(L[j], R[j]);
        		if (L[j]>=R[j]) {
        			list_l.get(K[j]-1).add(j);
        			ans += L[j];
        		} else {
        			list_r.get(K[j]-1).add(j);
        			ans += R[j];
        		}
        	}
        	PriorityQueue<int[]> pq_l = new PriorityQueue<int[]>((o1, o2)->Integer.compare(o1[0], o2[0]));
        	for (int j=0;j<N;j++) {
        		for (Integer tmp : list_l.get(j)) {
        			int[] add = {L[tmp]-R[tmp]};
        			pq_l.add(add);
        		}
        		while (pq_l.size()>j+1) {
        			ans -= pq_l.poll()[0];
        		}
        	}
        	PriorityQueue<int[]> pq_r = new PriorityQueue<int[]>((o1, o2)->Integer.compare(o1[0], o2[0]));
        	for (int j=N-1;j>=0;j--) {
        		for (Integer tmp : list_r.get(j)) {
        			int[] add = {R[tmp]-L[tmp]};
        			pq_r.add(add);
        		}
        		while (pq_r.size()>(N-1)-j) {
        			ans -= pq_r.poll()[0];
        		}
        	}
        	out.println(ans);
        }

		out.close();
	}

	static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

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

    }
}


Measured memory_bytes: 124036
N = int(input())
A = [int(i) for i in input().split()]

S = [0]*3
total = 1
for i in range(N):
    count = 0
    flag=0
    for j in range(3):
        if S[j]==A[i]:
            count += 1
            if flag==0:
                S[j] += 1
                flag=1
    total = (total*count)%1000000007
    
print(total)

Measured memory_bytes: 13928
while True:
   m, f, r = map(int, input().split())
   if m == -1 and f == -1 and r == -1:
      break
   
   if m == -1 or f == -1 or m + f < 30:
      print("F")
   elif m + f >= 80:
      print("A")
   elif m + f >= 65 and m + f < 80:
      print("B")
   elif m + f >= 50 and m + f < 65:
      print("C")
   else:
      if r >= 50:
         print("C")
      else:
         print("D")


Measured memory_bytes: 5592
#include<bits/stdc++.h>
using namespace std;
typedef long long signed int ll;
int main(){
	int n,m;
	cin>>n>>m;
	bool visit[n+1];
	memset(visit,false,sizeof(visit));
	int arr[n+1];
	
	for(int i=0;i<=n;i++) arr[i] = 1;
	

	int x,y;
	int cur = 1;
	int one = 0;
	int tot = 0;
	visit[1] = true;
	for(int i=0;i<m;i++){
		cin>>x>>y;
		if(visit[x]==true && arr[x]>=1) {
			
				
				visit[y] = true;
				
				arr[x]--;
				arr[y]++;
				if(arr[x]==0) {
					visit[x] = false;
			}
		
		}
		
	   else {
				arr[x]--;
				arr[y]++;
				
		}
	
		
	}
	for(int i=1;i<=n;i++) if(visit[i]==true) tot++;
	cout<<tot<<endl;
	return 0;
}
	
	

Measured memory_bytes: 768
import java.util.*;
 
public class Main{
    static int N;
    static int[][] x;
    static int cx;
    static int cy;
    public static void main(String args[]){
       Scanner sc = new Scanner(System.in); 
       
        N = sc.nextInt();
        x = new int[3][N];
       for(int i = 0; i < N; i++){
           x[0][i] = sc.nextInt();
           x[1][i] = sc.nextInt();
           x[2][i] = sc.nextInt();
       }
       sc.close();

       for(int i = 0; i <= 100; i++){
            loop: for(int j = 0; j <= 100; j++){
                cx = i;
                cy = j;
                int H = decide_h();
                for(int k = 0; k < N; k++){
                    if(Math.max(H - Math.abs(x[0][k] - cx) - Math.abs(x[1][k] - cy), 0) != x[2][k]){
                        continue loop;
                    }
                    if(k == N-1){
                        System.out.println(cx + " " + cy + " " + H);
                        break;
                    }
                }
            }
       }
    }
    static int decide_h(){
        for(int l = 0; l < N; l++){
            if(x[2][l] > 0){
                return x[2][l] + Math.abs(x[0][l] - cx) + Math.abs(x[1][l] - cy);
            }
        }

        return 0;
    }
}

Measured memory_bytes: 21844
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define PI 3.14159265358979323846264338327950L
int main(){
    int n,i;
    scanf("%d",&n);
    ll int a[n],sum=0,min=1000000010,minus=0,zero=0;
    rep(i,n){
        scanf("%lld",&a[i]);
        if(abs(a[i])<min) min=abs(a[i]);
        if(a[i]<0) minus++;
        if(a[i]==0) zero=1;
        sum+=abs(a[i]);
    }
    if(zero==1||minus%2==0){
        printf("%lld",sum);
    }else{
        printf("%lld",sum-2*min);
    }
    return 0;
}

Measured memory_bytes: 2488
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
print((n - 1) // 2)



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

int main()
{
    long long int a,b,c,d,n,m;
    while(~scanf("%lld %lld %lld %lld",&a,&b,&c,&d))
    {
        n=a*b;
        m=c*d;
        if(n>m)
            printf("%lld\n",n);
        else
            printf("%lld\n",m);
    }
    return 0;
}


Measured memory_bytes: 128
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string str = Console.ReadLine();
		int[,]D = new int[str.Length,2];
		for(var i=0;i<str.Length;i++){
			int a = int.Parse(str.Substring(i,1));
			if(i==0){
				if(a==0){
					D[0,1] = 1;
				} else {
					D[0,0] = 1;
				}
			} else {
				if(a==0){
					D[i,0] = D[i-1,1];
					D[i,1] = D[i-1,0]+1;
				} else {
					D[i,0] = D[i-1,1]+1;
					D[i,1] = D[i-1,0];
				}
			}
		}
		Console.WriteLine(Math.Min(D[str.Length-1,0],D[str.Length-1,1]));
	}
}

Measured memory_bytes: 15268
#include <cstdio>

int n;
int a[100100];
bool b[100100];

int main(){
	scanf("%d", &n);
	for(int i=0; i<n; ++i) scanf("%d", a+i);
	b[0] = true;
	int t = 0;
	for(int i=0; i<n; ++i){
		t = a[t]-1;
		if(b[t]){
			printf("-1\n");
			break;
		}
		if(t == 1){
			printf("%d\n", i+1);
			break;
		}
		b[t] = true;
	}
}

Measured memory_bytes: 640
s=input()
if s!=s[::-1]:
  print("No")
  exit()
n=len(s)
chk_s=s[0:(n-1)//2]
if chk_s!=chk_s[::-1]:
  print("No")
  exit()
chk_s=s[(n+3)//2-1:]
if chk_s!=chk_s[::-1]:
  print("No")
  exit()
print("Yes")

Measured memory_bytes: 3064
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())

int cost[100][100];

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

	int n,m;
	bool e[100][100];
	cin >> n >> m;
	rep(i, n)rep(j, n)cost[i][j] = INF;
	rep(i, n)rep(j, n)e[i][j] = false;
	rep(i,m) {
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		cost[a][b] = cost[b][a] = c;
		e[a][b] = e[b][a] = true;
	}
	rep(a,n) {
		int d[100];
		fill_n(d, n, INF);
		d[a] = 0;
		bool used[100] = {};
		rep(i, n - 1) {
			int minv = -1;
			rep(b, n) {
				if (!used[b] && (minv == -1 || d[b] < d[minv])) {
					minv = b;
				}
			}
			used[minv] = true;
			rep(b, n) {
				d[b] = min(d[b], d[minv] + cost[minv][b]);
			}
		}
		rep(b,n)rep(c,n) {
			if (d[b]+cost[b][c] == d[c]){
				e[b][c] = e[c][b] = false;
			}
		}
	}
	int ans = 0;
	rep(a,n)rep(b,n)if(e[a][b]) {
		ans++;
	}
	cout << ans / 2 << endl;


	return 0;
}

Measured memory_bytes: 256
/////////////////////////////////TEST CASES////////////////////////////////////
/*
*/
/////////////////////////////////////CODE//////////////////////////////////////		
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORD(i, a, b) for (ll i = a ; i > b ; i--)
#define fastio ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PI 3.14159265
typedef long long ll;
#define vl vector<ll> 
#define IN(inp) ll inp;cin>>inp;
#define pb push_back
#define all(a) a.begin(),a.end()
#define FR(i,a) for(auto i:a)
#define what(A) cout<<#A<<" is "<<A<<endl;
ll MAX = 100000000000;
ll MOD = 1000000007;
void solve()
{
	string s;
	cin >> s;
	ll sum = 0;
	FOR(i, 0, s.length())
	{
		sum += s[i] - '0';
		sum %= 9;
	}
	if (sum == 0)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}
int main()
{
	fastio
		//freopen("input.txt", "rt", stdin);
		//freopen("output.txt", "wt", stdout);
		ll test = 1;
	//cin >> test;
	while (test--)
	{
		solve();
	}
}

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

int main(){
  string S;
  cin >> S;
  int flag = 0;
  for(int i = 1;i <= S.size();i++){
    if(i % 2 == 1 && S[i - 1] != 'R' && S[i - 1] != 'U' && S[i - 1] != 'D'){
      flag = 1;
    }else if (i % 2 == 0 && S[i - 1] != 'L' && S[i - 1] != 'U' && S[i - 1] != 'D'){
      flag = 1;
    }
  }
  if(flag){
    cout << "No";
  }else{
    cout << "Yes";
  }
} 

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define inf 1072114514
#define llinf 1145141919810364364
#define mod 1000000007

int max(int a,int b){if(a>b){return a;}return b;}
int min(int a,int b){if(a<b){return a;}return b;}
int zt(int a,int b){return max(a,b)-min(a,b);}
int round(int a,int b){if((a%b)*2 >= b){return (a/b)+1;}return a/b;}
int ceil(int a,int b){if(a%b==0){return a/b;}return (a/b)+1;}
int gcd(int a,int b){int c;while(b!=0){c=a%b;a=b;b=c;}return a;}
int lcm(int a,int b){int c=gcd(a,b);a/=c;return a*b;}
int nCr(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
int fact(int a){int i,r=1;for(i=1;i<=a;i++){r*=i;}return r;}
int pow(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}
long long llmax(long long a,long long b){if(a>b){return a;}return b;}
long long llmin(long long a,long long b){if(a<b){return a;}return b;}
long long llzt(long long a,long long b){return llmax(a,b)-llmin(a,b);}
long long llround(long long a,long long b){if((a%b)*2 >= b){return (a/b)+1;}return a/b;}
long long llceil(long long a,long long b){if(a%b==0){return a/b;}return (a/b)+1;}
long long llgcd(long long a,long long b){long long c;while(b!=0){c=a%b;a=b;b=c;}return a;}
long long lllcm(long long a,long long b){long long c=llgcd(a,b);a/=c;return a*b;}
long long llnCr(long long a,long long b){long long i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
long long llfact(long long a){long long i,r=1;for(i=1;i<=a;i++){r*=i;}return r;}
long long llpow(long long a,long long b){long long i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}
double dbmax(double a,double b){if(a>b){return a;}return b;}
double dbmin(double a,double b){if(a<b){return a;}return b;}
double dbzt(double a,double b){return dbmax(a,b)-dbmin(a,b);}
int sortfncsj(const void *a,const void *b){if(*(int *)a>*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}
int sortfnckj(const void *a,const void *b){if(*(int *)a<*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}
int llsortfncsj(const void *a,const void *b){if(*(long long *)a>*(long long *)b){return 1;}if(*(long long *)a==*(long long *)b){return 0;}return -1;}
int llsortfnckj(const void *a,const void *b){if(*(long long *)a<*(long long *)b){return 1;}if(*(long long *)a==*(long long *)b){return 0;}return -1;}
int dbsortfncsj(const void *a,const void *b){if(*(double *)a>*(double *)b){return 1;}if(*(double *)a==*(double *)b){return 0;}return -1;}
int dbsortfnckj(const void *a,const void *b){if(*(double *)a<*(double *)b){return 1;}if(*(double *)a==*(double *)b){return 0;}return -1;}

int main(void){
    int i;
    char s[131072];
    scanf("%s",s);
    for(i = 0;i < strlen(s);i++){
        if(i%2==0){printf("%c",s[i]);}
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 256