akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <ctype.h>
#define MAX 1200

int main(void){
	int i;
	char c[MAX];

	fgets(c, MAX, stdin);

	for(i = 0; c[i] != '\0'; i++){
		if(isalpha(c[i])){
			if(isupper(c[i])){
				printf("%c", tolower(c[i]));
			}
			else if(islower(c[i])){
				printf("%c", toupper(c[i]));
			}
		}
		else{
			printf("%c", c[i]);
		}
	}
	return 0;
}

Measured memory_bytes: 524
N = gets.to_i
A = gets.split.map(&:to_i).sort
B = gets.split.map(&:to_i).sort
C = gets.split.map(&:to_i).sort

s = 0
i = 0
k = 0
for j in 0...N
  b = B[j]
  while i<N and A[i]<b
    i += 1
  end
  while k<N and C[k]<=b
    k += 1
  end
  s += i * (N-k)
end

puts s


Measured memory_bytes: 24688
Scanf.scanf "%d" (fun n ->
    let l = Array.init n (fun _ -> Scanf.scanf " %d" (fun a -> a)) in
    Array.sort compare l;

    let rec loop_a1 a1 acc =
        let rec loop_a2 a2 acc =
            let rec loop_a3 a3 acc =
                if a3 = n then acc else
                    loop_a3 (a3 + 1) (if l.(a1) <> l.(a2) && l.(a2) <> l.(a3) && l.(a1) + l.(a2) > l.(a3) then acc + 1 else acc)
            in
            if a2 = n then acc else loop_a2 (a2 + 1) (loop_a3 (a2 + 1) acc)
        in
        if a1 = n then acc else loop_a1 (a1 + 1) (loop_a2 (a1 + 1) acc)
    in
    loop_a1 0 0 |> Printf.printf "%d\n"
)

Measured memory_bytes: 4136
#include <bits/stdc++.h>
using namespace std;
int main() {
    string s; cin >> s;
    int ans = 1e9;
    for (int i = 0; i < 2; i++) {
        int tmp = 0;
        for (int j = 0; j < s.size(); j++) {
            if (s[j] - '0' == (i+j) % 2) tmp++;
        }
        ans = min(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
  int x;
  cin>>x;
  if (x==7||x==5||x==3) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  
  if ((A + B) > (C + D)) {
    cout << "Left" << endl;
  }
  else if ((A + B) == (C + D)) {
    cout << "Balanced" << endl;
  }
  else {
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <string>
#include<sstream>
using namespace std;
int main(void){
    
    long long int n , m;
    while(1){
    cin >> n >> m;
    if(n ==0 &&m ==0){
        break ;
    }
    string  a[n] ;//当選番号
    int g[n] ;//賞金
    for(int i = 0 ; i < n ; i++){
        cin >> a[i] >> g[i] ;
    }

    int b[m] ;//宝くじの番号

    for(int j = 0 ; j < m ; j++){
        cin >> b[j] ;

    }
    int countc = 0;//*の数
    int tempg = 0;
    char hh;
    string temp ;//当選番号（一時保存）
    int atemp ;//当選番号（int）
    long long int sum = 0;//賞金合計


    for(int i = 0; i < n ; i++){
        temp = a[i];
        for(int k = 0 ; k < 8 ; k++){
                if(temp[k] == '*'){
                    countc++ ;
                    
                }
        }//〇
        if(countc ==7){
            hh = temp[7]  ;
            atemp = ((int)hh) -48;
        }else{
        for(int o = 0 ; o < 8 - countc ; o++){
            hh = temp[7 - o]  ;
            
            atemp += (int)(((int)hh-48) * (int)pow(10.0 , (double)o)) ;
           
        }
        //cout <<"atemp" << atemp << endl;
        }
        for(int j = 0;  j < m ; j++){
            
            if(b[j] % ((long long int )pow( 10.0, 8-countc)) == atemp ){
                sum += g[i] ;
               
            }  
            //cout <<"TAKARA"<<   b[j] % ((long long int )pow( 10.0, 8-countc)) << endl;
        }

         atemp = 0 ;
         countc = 0;
       
    }

    cout << sum << endl;
    }
    return 0;
}


Measured memory_bytes: 3288
import bisect

def solve(N,A,B,C):

    # A=['3', '14', '159', '2', '6', '53']
    # B=['58', '9', '79', '323', '84', '6']
    # C=['2643', '383', '2', '79', '50', '288']
    A,B,C=list(map(int, A)),list(map(int, B)),list(map(int, C))
    A=sorted(A)
    B=sorted(B)
    C=sorted(C)
    # print(A)
    # print(B)
    # print(C)
    D = [0]*N
    # E = [0]*N
    # for i in range(N):
    #     a = A[i]
    #     # print(N-bisect.bisect_right(B,a))
    #     D[i]= N-bisect.bisect_right(B,a)
    #     #bはaより大きい数字が何個あるか分かれば良い
    #     #cはbの
    # # print(D)

    for i in range(N):
        b = B[i]
        D[i]=bisect.bisect_left(A,b)*(N-bisect.bisect_right(C,b))
        # print(b,'より小さいのは',bisect.bisect_left(A,b))
        # print(b,'より大きいのは',N-bisect.bisect_right(C,b))
    print(sum(D))
    # print(E)
    # answer = 0
    # for i in range(N):
    #     d=N-D[i]
    #     answer+=sum(E[d:])

    # print(answer)

    
 
 
def main():
    N = int(input())
    # A,B,C=0,0,0
    A=input().rstrip().split()
    B=input().rstrip().split()
    C=input().rstrip().split()
    solve(N,A,B,C)

 
 
if __name__ == '__main__':
    main()

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

#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

long long int dp[101][100001], inf = 1e18; 


int main()
{
	fastio;
	int n, w;
	cin >> n >> w;
	vector<pair<int, int> > v(n+1);
	for(int i = 1; i <= n; i++) {
		cin >> v[i].first >> v[i].second;
	}
	
	for(int i = 0; i < 101; i++) { //Always set all to inf when minimizing, we are minimizing weight.
		for(int j = 0; j < 100001; j++) {
			dp[i][j] = inf;	
		}
	}
	
	dp[1][0] = 0;
	dp[1][v[1].second] = v[1].first;
	
	for(int i = 2; i <= n; i++) {
		dp[i][0] = 0;
		for(int j = 1; j < 100001; j++) {
			if(v[i].second > j) dp[i][j] = dp[i-1][j];
			else dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i].second] + v[i].first);
			// ye value aane k liye "iss minus present item ki value" me jitna weight tha wo wt + ye item ka wt inme jo min hai wo lena hai 
		}
	}
	
	long long int ans;
	for(int i = 100000; i >= 0; i--) {
		if(dp[n][i] <= w) {
			ans = i;
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 82560
import math
n = int(input())

target_ls = [1]
target_6 = 6
while target_6 <= n:
    target_ls.append(target_6)
    target_6 *= 6
target_9 = 9
while target_9 <= n:
    target_ls.append(target_9)
    target_9 *= 9

dp = [float('inf')] * (n+1)
dp[0] = 0
for i in range(n):
    for j in target_ls:
        if i+j <= n:
            dp[i+j] = min(dp[i+j],dp[i] + 1)
print(dp[n])
    

Measured memory_bytes: 46032
N=int(input())
ans=[0]*(N+1)
rN=int(N**(1/2))
for x in range(1,rN+1):
    for y in range(1,rN+1):
        for z in range(1,rN+1):
            n=x**2+y**2+z**2+x*y+y*z+z*x
            if n<=N:
                ans[n]+=1
                
for i in range(1,N+1):
    print(ans[i])

Measured memory_bytes: 9568
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]

ans = 0
S = list(rs())
T = list(rs())
for i in range(len(S)):
    if S[i] != T[i]:
        ans += 1
print(ans)

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

int main() {
  int N;
  cin >> N;
  vector<string> vecs(N);
  for (int i = 0; i < N; i++) {
    string s;
    cin >> s;
    vecs.at(i) = s;
  }
 
  int M;
  cin >> M;
  vector<string> vect(M);
  for (int i = 0; i < M; i++) {
    string t;
    cin >> t;
    vect.at(i) = t;
  }
  int ans = 0;
  for (int i = 0; i < N; i++) {
    int a = 0;
    for (int j = 0; j < N; j++) {
      if (vecs.at(i) == vecs.at(j)) a++;
    } 
    for (int j = 0; j < M; j++) {
      if (vecs.at(i) == vect.at(j)) a--;
    }
    if (ans < a) ans = a;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str[] = br.readLine().split(" ");
		int p = Integer.parseInt(str[0]);
		int q = Integer.parseInt(str[1]);

		q /= gcd(p, q);

		int ans = 1;
		for (int i = 2; i <= Math.sqrt(q); i++) {
			if (q % i == 0) {
				while (q % i == 0) {
					q /= i;
				}
				ans *= i;
			}
		}
		ans *= q;
		System.out.println(ans);
	}

	static int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}
}


Measured memory_bytes: 24444
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
  int x=sc.nextInt();
  int y=sc.nextInt();
  boolean v=false;
  if(x==0&&y==0){
System.out.println("Yes");
  }else{
  for(int i=0;i<=x;i++){
		int c=i*2+(x-i)*4;
  
    if(y!=0&&(c==y)){
      v=true;
      System.out.println("Yes");
      break;
    }
  }
    
  
  if(v==false){
System.out.println("No");
  }
  }
}
}

Measured memory_bytes: 35680
#include <bits/stdc++.h>
#define int long long
#define MOD 1000000007
#define N (int) 3e5
using namespace std;
int n;
struct Edge {
	int v, nxt;
} edge[N<<1];
int fst[N], ecnt;
void add_edge (int u, int v) {
	edge[ecnt].v = v, edge[ecnt].nxt = fst[u], fst[u] = ecnt ++;
}
void init_e () {
	memset (fst, -1, sizeof (fst));
}

int ksm (int x, int y) {
	int ret = 1;
	while (y) {
		if (y & 1) (ret *= x) %= MOD;
		(x *= x) %= MOD;
		y >>= 1;
	}
	return ret;
}

int inv (int x) {
	return ksm (x, MOD-2);
}

int sz[N], dp1[N], dp2[N];
void DP1 (int u, int f) {
	sz[u] = 1;
	dp1[u] = 1;
	for (int e = fst[u]; e != -1; e = edge[e].nxt) {
		int v = edge[e].v;
		if (v == f) continue;
		DP1 (v, u);
		sz[u] += sz[v];
		(dp1[u] *= dp1[v]) %= MOD;	
	}
	(dp1[u] *= sz[u]) %= MOD;
//	cout << u << " " << dp1[u] << endl;
}
void DP2 (int u, int f) {
	if (u != 1) dp2[u] = dp2[f] * (n - sz[u]) % MOD * inv (sz[u]) % MOD;
//	cout << u << " " << dp2[u] << endl;
	for (int e = fst[u]; e != -1; e = edge[e].nxt) {
		int v = edge[e].v;
		if (v == f) continue;
		DP2 (v, u);
	}
}

signed main () {
	init_e ();
	
	cin >> n;
	for (int i = 1; i < n; i ++) {
		int u, v; cin >> u >> v;
		add_edge (u, v); add_edge (v, u);
	}
	
	DP1 (1, 0);
	dp2[1] = dp1[1];
	DP2 (1, 0);
	
	int tmp = 1;
	for (int i = 1; i <= n; i ++) (tmp *= i) %= MOD;
	
	for (int i = 1; i <= n; i ++) cout << (1ll * tmp * inv (dp2[i]) % MOD) << endl;
	
	return 0;
}

Measured memory_bytes: 18176
#include<stdio.h>
#include<string.h>
int main()
{
  char a[100];
  scanf("%s", a);
  int l=strlen(a);
  int i, c=0,c1=0,s;
  for(i=0;i<l;i++)  {
        if(i%2==0)
      {if(a[i]=='R'||a[i]=='U'||a[i]=='D')
      c++;}
  else if(i%2==1){
    if(a[i]=='L'||a[i]=='U'||a[i]=='D')
    c1++;}
}
  s=l/2;
  if((l%2==1&&c==(s+1)&&c1==s)||(l%2==0&&s==c&&c1==s))
  printf("Yes\n");
  else
    printf("No\n");
  return 0;
}




Measured memory_bytes: 128
ans=0
N=int(input())
if N<=0:
    exit()
elif N>=1000001:
    exit()
else:

    for n in range(1,N+1):
        if n%15==0:
            n=str("FizzBuzz")
        elif n%3==0:
            n=str("Fizz")
        elif n%5==0:
            n=str("Buzz")
        else:
            ans+=n

print(ans)

Measured memory_bytes: 9104
#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; i++)
#define out(ans) cout << ans << endl;
const long long mod = 1e9 + 7;

int main(){

  int w,a,b;cin>>w>>a>>b;

  if(b+w<a)out(a-b-w)
  else if(a+w<b)out(b-a-w)
  else out(0)

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

typedef long long ll;

int main(void){

	ll N, A, B;
	ll ans;
	ll rem;

	scanf("%lld %lld %lld", &N, &A, &B);

	ans = (N / (A + B)) * A;
	rem = N % (A + B);
	ans += ((rem > A) ? A : rem);

	printf("%lld", ans);

  return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define mod 1000000007
ll n,k,p[200010];
int main(){
  cin>>n>>k;
  for(int i=0;i<n;i++){
      cin>>p[i];
  }
  ll cnt=0;
  for(int i=0;i<k-1;i++){
      cnt+=(p[i]>p[i+1]);
  }
  set<int> st;
  for(int i=0;i<=k;i++){
      st.insert(p[i]);
  }
  ll ans=n-k+1;
  bool th=0;
  for(int i=0;i<n-k;i++){
      if(cnt==0){
	  ans--;
	  th=1; //cout<<i<<"*"<<endl;
      }
      else{
	  auto it=st.end(); it--;
	  if(p[i]==*st.begin()&&p[i+k]==*it){
	      ans--;
	  }
      }
      st.erase(p[i]);
      st.insert(p[i+k+1]);
      cnt-=(p[i]>p[i+1]);
      cnt+=(p[i+k-1]>p[i+k]);
  }
  if(cnt==0)ans--,th=1;
  ans+=th;
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 11136
#include <bits/stdc++.h>
#define int llint
#define rep(i, a, n) for(int (i) = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int (i) = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int (i) = (int)(a);(x);++(i))
#define repr(i, a, n) for(int (i) = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int (i) = (int)(a);(i) >= (int)(n);--(i))
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define SIZE(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define RNG(x, a, n) &((x)[a]), &((x)[n])
#define ADD(a, b) ((((a+MOD)%MOD)+((b+MOD)%MOD))%MOD)
#define MUL(a, b) ((((a)%MOD)*((b)%MOD))%MOD)
#define CEIL(x) ((int)ceil(((double)x)))
#define POW(x, y) ((int)pow(x, y))
#define UNIQUE(x) (x).erase(unique(ALL((x))), (x).end())
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define fcout cout << fixed << setprecision(10)
#define pb push_back
#define pf push_front
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define EPS (1e-20)
#define INF INT_MAX
#define INFLL LLONG_MAX
#define MOD 1000000007
using llint = long long;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using SI = std::set<int>;
using MII = std::map<int, int>;
using TIII = std::tuple<int, int, int>;
using MCI = std::map<char, int>;
using VPII = std::vector<PII>;
using namespace std;


int N, A, B;
int X[100010];


int solve(){
	int ans = 0;
	rep(i, 1, N) ans += min((X[i]-X[i-1])*A, B);
	return ans;
}


signed main(){
	cin >> N >> A >> B;
	rep(i, 0, N) cin >> X[i];

	cout << solve() << endl;

	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <math.h>
#include <bitset>
#include <vector>
#include <climits>

using namespace std;

template<size_t N>
bitset<N> to_bitset(vector<int>& v) {
  bitset<N> r;
  for (int i = 0; i < N; i++) {
    r[i] = v[i];
  }
  return r;
}

int main(){
  int n;
  cin >> n;
  vector<vector<int>> f(n, vector<int>(10));
  for (auto& e1 : f) {
    for (int& e2 : e1) cin >> e2;;
  }

  vector<vector<int>> p(n, vector<int>(11));
  for (vector<int>& e1 : p) {
    for (int& e2 : e1) {
      cin >> e2;
    }
  }
  long long answer =LONG_MIN;

  for(unsigned int i=1;i<1024;i++){
    bitset<10> my{i};
    long long temp=0;
    // cout<<my<<endl;
    for(int j=0;j<n;j++){
      temp += p[j][(to_bitset<10>(f[j]) & my).count()];
    }
    if(temp>answer) {
      // for(int j=0;j<n;j++){
      //   int index = (to_bitset<10>(f[j]) & my).count();
      //   cout << "shop[" << j << "][" << index << "] = " << p[j][index] << endl;
      // }
      // cout << "score = " << temp << ", " << my << endl;
      answer=temp;
    }
  }
  cout<<answer<<endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < n; i++)
#define REPR(i,n) for(int i = n; i >= 0; i--)
#define FOR(i,m, n) for(int i = m-1; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
#define chmax(x,y) (x = max(x,y))
#define chmin(x,y) (x = min(x,y))
#define FILL2D(A,c) fill(A[0], A[0] +sizeof(A)/sizeof(**A),c)
#define FILL3D(A,c) fill(A[0][0], A[0][0] +sizeof(A)/sizeof(***A),c)
//vector<vector<要素の型>> 変数名(要素数1, vector<要素の型>(要素数2, 初期値))
//vector<intなど> 変数名(要素数,初期値)
using namespace std;
typedef long long ll;
int main(){
    int n,x;
    int w;
    ll  v;
    cin>>n>>x;
    vector<vector<ll>> dp(n+1, vector<ll>(x+1));
    REP(i,n){
        cin>>w>>v;
        for(int j=0;j<x+1;j++) {
          if(j>=w) dp[i+1][j]=max(dp[i][j],dp[i][j-w]+v);
         else dp[i+1][j]=dp[i][j];}
      //REP(j,x+1) cout<<"dp["<<i+1<<"]["<<j<<"]="<<dp[i+1][j]<<endl;
    }
    cout<<dp[n][x]<<endl;
}


Measured memory_bytes: 80256
#include <bits/stdc++.h> 
 
#define INF (1<<31) - 1 //INT_MAX/2
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using P = std::pair<int, int>;

int main(int argc, char *argv[])
{
    std::string S, T;
    std::cin >> S >> T;

    int N = S.size();
    bool flag = false;
    for (int i = 0; i < N; i++) {
        if (S == T) {
            flag = true;
            break;
        }

        std::string temp;
        temp = S[N-1];
        S = temp + S.substr(0, N-1);
    }

    if (flag) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No"  << std::endl;
    }
    return 0;
}

Measured memory_bytes: 256
n=int(input())
s=list(input())

w=[0]*n
i=1
while i<n:
    if s[i-1]=='W':
        w[i-1]+=1
    w[i]+=w[i-1]
    i+=1
i=n-1
e=[0]*n
while i>0:
    if s[i]=='E':
        e[i]+=1
    e[i-1]+=e[i]
    i-=1
    
ans=10**9

i=0
while i<n:
    ans=min(ans,e[i]+w[i]-1)
    i+=1
print(ans)


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

Measured memory_bytes: 23124
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
	"strings"
)

func main() {
	var sample = []int{1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51}
	A := oneInt()
	fmt.Print(sample[A-1])
}

func exp(val int) float64 {
	var temp float64
	for index := 1; index <= val; index++ {
		temp += float64(index)
	}
	return temp / float64(val)
}

func searchAbove(slice []int, target int, index int) int {
	for i := index + 1; i < len(slice); i++ {
		v := slice[i]
		if v >= target {
			return i
		}
	}
	return -1
}

var sc = bufio.NewScanner(os.Stdin)

func oneInt() int {
	var a int
	fmt.Scan(&a)
	return a
}
func oneStr() string {
	var a string
	fmt.Scan(&a)
	return a
}

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func scanNums() (nums []int) {
	s := nextLine()
	numStr := strings.Split(s, " ")

	for _, n := range numStr {
		i, _ := strconv.Atoi(n)
		nums = append(nums, i)
	}
	return nums
}

func scanStrings() (strs []string) {
	s := nextLine()
	list := strings.Split(s, " ")
	strs = append(strs, list...)
	return strs
}

func abs(a int) int {
	return int(math.Abs(float64(a)))
}

func pow(p, q int) int {
	return int(math.Pow(float64(p), float64(q)))
}

func min(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func max(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return res
}

func strSearch(a []string, b string) bool {
	for i := 0; i < len(a); i++ {
		if a[i] == b {
			return true
		}
	}
	return false
}

func sortAsc(a []int) []int {
	sort.Ints(a)
	return a
}

func sortDesc(a []int) []int {
	sort.Sort(sort.Reverse(sort.IntSlice(a)))
	return a
}

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

func lcm(a, b int) int {
	if a == 0 && b == 0 {
		return 0
	}
	return a * b / gcd(a, b)
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=924844033,MAX=1503*1503;
const ll INF=1LL<<60;
struct data{
    ll b;
    ll l;
    ll r;
};

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll N,X;cin>>N>>X;
    
    vector<data> S(N);
    ll need=0;
    
    for(int i=0;i<N;i++){
        cin>>S[i].b>>S[i].l>>S[i].r;
        need+=S[i].b*S[i].l;
    }
    
    sort(all(S),[&](data a,data b){
        return a.r*(X-a.b)+a.b*a.l>b.r*(X-b.b)+b.b*b.l;
    });
    
    vector<ll> sum(N+1);
    for(int i=1;i<=N;i++){
        sum[i]=sum[i-1]+S[i-1].r*(X-S[i-1].b)+S[i-1].b*S[i-1].l;
    }
    
    ll ans=INF;
    for(int i=0;i<N;i++){
        ll diff=S[i].r*(X-S[i].b)+S[i].b*S[i].l;
        auto it=upper_bound(all(sum),need);
        ll re=it-sum.begin()-1;
        if(re>i){
            if(S[i].b*S[i].l>=need-((*it)-diff)){
                ans=min(ans,re*X+(need-((*it)-diff)+S[i].l-1)/S[i].l);
            }else{
                ans=min(ans,re*X+(need+S[i].b*(S[i].r-S[i].l)-((*it)-diff)+S[i].r-1)/S[i].r);
            }
        }else{
            it--;
            diff=0;
            
            if(S[i].b*S[i].l>=need-((*it)-diff)){
                ans=min(ans,re*X+(need-((*it)-diff)+S[i].l-1)/S[i].l);
            }else{
                ans=min(ans,re*X+(need+S[i].b*(S[i].r-S[i].l)-((*it)-diff)+S[i].r-1)/S[i].r);
            }
        }
    }
    bool ok=true;
    
    for(int i=0;i<N;i++) if(S[i].b!=X) ok=false;
    
    if(ok) ans=X*N;
    
    cout<<ans<<endl;
}






Measured memory_bytes: 3456
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define pi pair<int,int>
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define ln(x) ((int)x.length())
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define dbg(x) cout<<#x<<": "<<x<<endl
#define clr(x,v) memset(x, v, sizeof(x))
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
const double eps = 1e-9;
const double PI = acos(-1.0);
const ll mod = 1e9 + 7;
const int MAXN = 1e7 + 5;

void cp()
{
    int k;
    cin >> k;
    bool ok = false;
    int sum = 0;
    int ans = -1;
    for(int i = 1; i < MAXN; i++)
    {
        sum = sum * 10 + 7;
        sum %= k;
        if(sum == 0)
        {
            ans = i;
            break;
        }
    }
    cout << ans;
}

int main()
{
    FASTIO;
    int t;
    t = 1;
    // cin >> t;
    while(t--)
    {
        cp();
    }
    return 0;
}

Measured memory_bytes: 3664
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        s:usize
    }
    let mut m:usize = s/100;
    let mut y:usize = s % 100;
    if 1 <= m && m  <= 12 && 1 <= y && y <= 12{
        println!("AMBIGUOUS");
    }else if 1 <= m && m <= 12{
        println!("MMYY");
    } else if 1 <= y && y <= 12{
        println!("YYMM");
    }else{
        println!("NA");
    }
}


Measured memory_bytes: 4352
import java.io.*;
import java.util.*;
 
public class Main {
  private static boolean debug = false;
  private static boolean elapsed = false;
 
  private static PrintWriter _err = new PrintWriter(System.err);
 
  private void solve(Scanner sc, PrintWriter out) {
    int N = sc.nextInt();
    int x = sc.nextInt();
    int[] a = new int[N];
    int[] sum = new int[N - 1];
    for (int i = 0; i < N; ++i) {
      a[i] = sc.nextInt();
    }
 
    long count = 0;
    if (a[0] > x) {
      count += a[0] - x;
      a[0] = x;
    }
    for (int i = 0; i < a.length - 1; ++i) {
      if (a[i] + a[i + 1] > x) {
        int t = a[i] + a[i + 1] - x;
        count += t;
        a[i + 1] -= t;
      }
    }
 
    out.println(count);
  }
  private long P(long n, long r) {
    long res = 1;
    for (long i = n; i > n - r; --i) {
      res *= i;
    }
    return res;
  }
  /*
   * 10^10 > Integer.MAX_VALUE = 2147483647 > 10^9
   * 10^19 > Long.MAX_VALUE = 9223372036854775807L > 10^18
   */
  public static void main(String[] args) {
    long S = System.currentTimeMillis();
 
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
    new Main().solve(sc, out);
    out.flush();
 
    long G = System.currentTimeMillis();
    if (elapsed) {
      _err.println((G - S) + "ms");
    }
    _err.flush();
  }
}

Measured memory_bytes: 60456
#include "bits/stdc++.h"
using namespace std;
typedef long long ll ;

int main(){

int n;
cin>>n;
vector<int> input[3];
int a,b,c;

for(int i=0;i<n;i++) {
    cin>>a>>b>>c;
    input[0].push_back(a);
    input[1].push_back(b);
    input[2].push_back(c);
}

int dp[3][n];
memset(dp,0,sizeof(dp));

dp[0][0]=input[0][0];
dp[1][0]=input[1][0];
dp[2][0]=input[2][0];

for(int i=1;i<n;i++){

    for(int act=0;act<3;act++){
    
       if(act==0){
         dp[0][i]=max(dp[1][i-1],dp[2][i-1])+input[0][i];
       } 
       else if(act==1){
         dp[1][i]=max(dp[0][i-1],dp[2][i-1])+input[1][i];  
       }
       else if(act==2){
         dp[2][i]=max(dp[1][i-1],dp[0][i-1])+input[2][i]; 
       }

    }
}

/*for(int i=0;i<3;i++){

 for(int j=0;j<n;j++){
     cout<<dp[i][j]<<" ";
 }
 cout<<endl;

}
*/
cout<<max(dp[0][n-1],max(dp[1][n-1],dp[2][n-1]));


}




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

typedef long long LL;
typedef unsigned long long ULL;

#define debug printf("fuck %d\n", __LINE__);

inline LL read() {
	LL res = 0, bo = 1; char ch = getchar();
	while(ch < '0' || ch > '9') { if (ch == '-') bo = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9') { res = (res << 1) + (res << 3) + ch - '0'; ch = getchar(); }
	return bo * res;
}

template<typename T> void read(T &x) { x = read(); }
template<typename T, typename ...Argv> void read(T &a, Argv &...argv) { read(a); read(argv...); }

const int N = 5010, p = 1e9 + 7;
std::vector<int> e[N];
int siz[N], f[N][N], tmp[N], g[N];

void dfs(int x, int fa) {
	f[x][1] = siz[x] = 1;
	for (auto y : e[x]) {
		if (y == fa) continue;
		dfs(y, x);
		for (int i = 0; i <= siz[x] + siz[y]; ++ i) tmp[i] = 0;
		for (int i = 1; i <= siz[x]; ++ i) {
			for (int j = 0; j <= siz[y]; ++ j) {
				tmp[i + j] = (tmp[i + j] + 1LL * f[x][i] * f[y][j] % p) % p;
			}
		}
		siz[x] += siz[y];
		for (int i = 1; i <= siz[x]; ++ i) f[x][i] = tmp[i];
	}
	for (int i = 2; i <= siz[x]; i += 2) f[x][0] = (f[x][0] - 1LL * g[i] * f[x][i] % p + p) % p;
}

int main() {
	int n = read();
	for (int i = 1; i < n; ++ i) {
		int u = read(), v = read();
		e[u].push_back(v);
		e[v].push_back(u);
	}
	g[0] = 1;
	for (int i = 2; i <= n; i += 2) g[i] = 1LL * g[i - 2] * (i - 1) % p;
	dfs(1, 0);
	std::cout << p - f[1][0] << std::endl;
	return 0;
}

Measured memory_bytes: 97536
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
t=[["$"]*(w+2) for i in range(h+2)]
for i in range(h):
    for j in range(w):
        t[i+1][j+1]=s[i][j]
v=[1,0,-1]
for i in range(h):
    for j in range(w):
        cnt=0
        if t[i+1][j+1]==".":
            for k in v:
                for l in v:
                    if t[i+1+k][j+1+l]=="#":
                        cnt+=1
            t[i+1][j+1]=str(cnt)
for i in range(h+2):
    t[i]="".join(t[i])
for i in range(1,h+1):
    print(t[i][1:w+1])

Measured memory_bytes: 9168
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int a, b;
	cin >> a >> b;
	string s = to_string(a), t = to_string(b), ss, tt;
	for (int i = 0; i < b; i++)
		ss += s;
	for (int i = 0; i < a; i++)
		tt += t;
	cout << min(ss, tt);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
#define MAX 200005

vector<int> seg(4*MAX, 0), ai(MAX), hei(MAX);

int query(int idx, int l, int r, int ql, int qr){
	if( l > qr || r < ql )
		return 0;
	if( ql <= l && r <= qr )
		return seg[idx];

	int md = (l+r)/2;
	return max(query(2*idx, l, md, ql, qr), query(2*idx+1, md+1, r, ql, qr));
}

void update(int idx, int l, int r, int pos, int vl){
	if( l == r ){
		seg[idx] = vl;
		return;
	}

	int md = (l+r)/2;
	if( pos <= md )
		update(2*idx, l, md, pos, vl);
	else
		update(2*idx+1, md+1, r, pos, vl);

	seg[idx] = max(seg[2*idx], seg[2*idx+1]);
}

int32_t main(){
	IOS;
	int n;
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> hei[i];
	for(int i = 0; i < n; i++)
		cin >> ai[i];

	for(int i = n-1; i >= 0; i--){
		int vl = query(1, 0, n, hei[i], n);
		update(1, 0, n, hei[i], vl+ai[i]);
	}

	cout << seg[1] << endl;

	return 0;
}

Measured memory_bytes: 12600
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
using ll = long long;
int main(){
	int n;
	cin>>n;
	vector<pair<int,int>> v(n);
	for(int i=0;i<n;i++){
		cin>>v[i].first>>v[i].second;
	}
	int current =0;
	int ans = 0;
	for(int i=0;i<n;i++){
		int left = v[i].first - v[i].second;
		int right = v[i].first + v[i].second;
		v[i].first = right;
		v[i].second= left;
		//cerr<<right<<left<<"\n";
		
	}
	sort(v.begin(),v.end());
	current = v[0].first;
	cerr<<current<<"\n";
	ans =1 ;
	for(int i=1;i<n;i++){
		if(v[i].second >= current){
			current = v[i].first;
			cerr<<current<<"\n";
			ans++;
		}
	}
	cout<<ans;
		
}




Measured memory_bytes: 1024
/* ＵＴＦ－８ */
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <array>
#include <queue>
#include <stack>
#include <algorithm>
#include <tuple>
#include <numeric>
#include <type_traits>
#include <limits>

#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>

#define USE_COLORED 1

#ifdef USE_COLORED
static const char stdout_pre[]  = "\033[1m"; // bold black
static const char stderr_pre[]  = "\033[31;1m"; // bold red
static const char stdxxx_post[] = "\033[m";

// 当然ながら GCC(g++)/libstdc++ 依存
#include <ext/stdio_filebuf.h>
using stdio_filebuf = __gnu_cxx::stdio_filebuf<char>;
class colored_stdio_filebuf : public stdio_filebuf {
private:
	const char* const pre_;
	const char* const post_;

public:
	colored_stdio_filebuf(FILE* fp, const char* pre, const char* post) : stdio_filebuf(fp, std::ios_base::out), pre_(pre), post_(post)
	{
	}

protected:
	std::streamsize xsputn(const char* s, std::streamsize count) override
	{
		stdio_filebuf::xsputn(pre_, strlen(pre_));
		auto ret = stdio_filebuf::xsputn(s, count);
		stdio_filebuf::xsputn(post_, strlen(post_));
		return ret;
	}
};
#endif

int main()
{
#ifdef USE_COLORED
	if (getenv("DEBUG")) {
		std::cout.rdbuf(new colored_stdio_filebuf(stdout, stdout_pre, stdxxx_post));
		std::cerr.rdbuf(new colored_stdio_filebuf(stderr, stderr_pre, stdxxx_post));
	} else
#endif
	{
		int fd = open("/dev/null", O_WRONLY);
		dup2(fd, 2);
		close(fd);
	}
	
	std::string S;
	std::cin >> S;
	if (S.size() >= 4 && S.substr(0, 4) == "YAKI")
		std::cout << "Yes\n";
	else
		std::cout << "No\n";
}


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

/* メモリ食い過ぎ注意 */
#define int long long

typedef long long ll;

int euclid(int a, int b)
{
    if (a < b)
        euclid(b, a);
    if (b == 0)
        return a;
    int r;
    while ((r = a % b))
    {
        a = b;
        b = r;
    }
    return b;
}

/* define const */
const ll INF = (1ll << 60);
const ll MOD = (ll)1e9 + 7;
/* end defineing */

signed main()
{
    ll n, p;
    cin >> n >> p;

    ll x = -1, y = -1, z = -1;
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; i + j <= n; j++)
        {
            ll sum = i * 10000 + j * 5000 + (n - i - j) * 1000;
            if (sum == p)
            {
                x = i;
                y = j;
                z = (n - i - j);
            }
        }
    }
    cout << x << " " << y << " " << z << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include <cassert>
#include<string>
#include<vector>
#include <utility>
#include <math.h>
#include<cmath>
#include<map>
#include <limits>
# include <iomanip>
#define INF 1000000009;

using namespace std;
int gcd(int a, int b) {
	while (a % b != 0) {
		int c = 0;
		c = a % b;
		a = b;
		b = c;
	}
	return  b;
}
int kaizyo(int a) {
	long long ans = 1;
	for (int i = a; i > 0; i--) {
		ans *= i;
		ans = ans % 1000000007;
		//cout << ans << endl;
	}
	ans = ans % 1000000007;
	return ans;
}

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


int main() {
	int tate, yoko;
	char masu[60][60];
	cin >> tate >> yoko;
	for (int i = 0; i < tate; i++) {
		for (int j = 0; j < yoko; j++) {
			cin >> masu[i][j];
		}
	}
	for (int i = 0; i < tate; i++) {
		for (int j = 0; j < yoko; j++) {
			if (masu[i][j] == '#') {
				bool ok = false;
				for (int q = 0; q < 4; q++) {
					if (i + dx[q] >= 0 && i + dx[q] < tate && j + dy[q] >= 0 && j + dy[q] < yoko) {
						if (masu[i + dx[q]][j + dy[q]] == '#') {
							ok = true;
							break;
						}
					}
				}
				if (ok != true) {
					cout << "No" << endl;
					return 0;
				}
			}
		}
	}
	cout << "Yes" << endl;
	return 0;
}


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

int main() {
    cout << fixed << setprecision(0);
    int N;
    cin >> N;
    int ans = 0;
    int A = 1;
    while(N > A) {
        int b_cnt = N / A;
        ans += b_cnt;
        if(A * (N / A) == N)
            ans--;
        A++;
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3632
let () =
  let x1, y1, x2, y2 = Scanf.sscanf (read_line ()) "%f %f %f %f" (fun x y z w -> x, y, z, w) in
  Printf.printf "%f\n" ( sqrt @@ (x1 -. x2)  ** 2. +. (y1 -. y2) ** 2.)
;;


Measured memory_bytes: 2516
#include<iostream>
#include<math.h>
#include <iomanip>


using namespace std;
const double PI = acos(-1.0);
int main(){
	double a,b,h,m;
	cin >> a >> b >> h >> m;
	long double mdu = (long double)m/60.0;
	long double hdu = ((long double)h + (long double)m/60.0)/12.0;
	long double difdu = hdu - mdu;
	long double ans = sqrt((long double)a*a + (long double)b*b - (long double)2* a * b * cos(difdu * 2*PI));
	cout << setprecision(20) << ans;
	return 0; 
}

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

#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >=0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

typedef long long ll;

string S;
int ans = 0;

// int func(){
//   int sum = 0;
//   REP(i, S.length()-1){
//     bool flag = true;
//     while(flag){
//       flag = false;
//       if(S[i] != S[i+1]){
//         S.erase(S.begin()+i, S.begin()+i+2);
//         flag = true;
//         ans+=2;
//         sum+=2;
//       }
//       if(S.length()-i <2)
//         return sum;
//     }
//   }
//   return sum;
// }
void func(){
  REP(i, (int)S.length()-1){
    if(S[i] != S[i+1]){
      ans+=2;
      S.erase(S.begin()+i);
      S.erase(S.begin()+i);
      i -= i!=0 ? 2 : 1;
      
    }
  }
}

int main(){
  cin >> S;
  func();
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 512
#define LOCAL
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos((ld)-1.0))
#define MAXN (300006)
#define ll long long int 
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < (ll)ee; ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph push
#define btinpct(x) __builtin_popcountll((x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
string to_string(char c) {string s(1,c);return s;}string to_string(bool b){return (b ? "true" : "false");}template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}template <typename A>string to_string(A v) {bool first = true;string res = "{";for (const auto &x : v) {if (!first) {res += ", ";}first = false;res += to_string(x);}res += "}";return res;}void degug_out() { cerr << endl; }template <typename Head, typename... Tail>void degug_out(Head H, Tail... T) {cerr << " " << to_string(H);degug_out(T...);}inline ll gcd(ll a,ll b){if(a>b)swap(a,b);if(a==0)return b;return gcd(b%a,a);}
#ifdef LOCAL
#define degug(...) cerr << "[" << #__VA_ARGS__ << "]:", degug_out(__VA_ARGS__)
#else
#define degug(...) 42
#define cerr if(0)cout
#endif
ll n,A[3],B[3],dp[5006*5006];
vector<pi>items; // value, weight
int main()
{
	FAST
	cin>>n>>A[0]>>A[1]>>A[2]>>B[0]>>B[1]>>B[2];
	FOR(i,0,3){
		if(B[i]>A[i]){
			items.eb(B[i]-A[i],A[i]);
		}
	}
	for(auto x:items)for(ll i=x.s;i<=5001*5001;++i){
		dp[i]=max(dp[i],dp[i-x.s]+x.f);
	}
	ll have=dp[n]+n;
	swap(A,B);
	items.clear();
	mmst(dp,0);
	FOR(i,0,3){
		if(B[i]>A[i]){
			items.eb(B[i]-A[i],A[i]);
		}
	}
	for(auto x:items)for(ll i=x.s;i<=5001*5001;++i){
		dp[i]=max(dp[i],dp[i-x.s]+x.f);
	}
	cout<<dp[have]+have<<'\n';
}


Measured memory_bytes: 196096
from collections import defaultdict
N,C=map(int,input().split())
stc=[]
c_st=defaultdict(list)
for i in range(N):
    ss,tt,cc = map(int,input().split())
    stc.append((ss,tt,cc))
    c_st[cc].append((ss,tt))

S=[]
T=[]
for c,lst in c_st.items():
    ss=sorted(lst)
    s,t=ss[0]
    for i in range(1,len(lst)):
        if ss[i][0]==ss[i-1][1]:
            t=ss[i][1]
            continue
        else:
            S.append(s-0.5)
            T.append(t)
            s,t=ss[i]
    S.append(s-0.5)
    T.append(t)
S=sorted(S)
T=sorted(T)
count=0
maxc=0
si,ti=0,0
while si<len(S):
    s=S[si]
    t=T[ti]
    if s<t:
        count+=1
        si+=1
    else:
        count-=1
        ti+=1
    if count>maxc:
        maxc=count
print(maxc)

Measured memory_bytes: 30312
import numpy as np

p = int(input())
aaa = list(map(int, input().split()))

bins = [1]
for i in range(1, p):
    bins.append(bins[-1] * (p - i) * pow(i, p - 2, p) % p)
bins = np.array(bins, dtype=np.int32)

pows_base = -np.arange(p, dtype=np.int32)
pows = np.zeros((p, p), dtype=np.int32)
pows[:, p - 1] = 1
for i in range(p - 2, -1, -1):
    pows[:, i] = pows[:, i + 1] * pows_base % p

coefs = np.zeros(p, dtype=np.int32)

for i, a in enumerate(aaa):
    if a == 0:
        continue

    coefs[0] += 1
    coefs = (coefs - bins * pows[i]) % p

print(*coefs)


Measured memory_bytes: 49604
#include<stdio.h>

int main() {
	int n, m, l, r;
	int min = 0,max;
	int cou = 0;

	scanf("%d%d", &n, &m);
	max = n;

	for (int i = 0; i < m; ++i) {
		scanf("%d%d", &l, &r);
		min = (l > min) ? l : min;
		max = (r < max) ? r : max;
	}

	for (int i = min; i <= max; ++i)
		++cou;

	printf("%d", cou);

		return 0;
}

Measured memory_bytes: 128
//dlang template---{{{
import std.stdio;
import std.conv;
import std.string;
import std.array;
import std.algorithm;

// MIT-License https://github.com/kurokoji/nephele
class Scanner
{
  import std.stdio : File, stdin;
  import std.conv : to;
  import std.array : split;
  import std.string;
  import std.traits : isSomeString;

  private File file;
  private char[][] str;
  private size_t idx;

  this(File file = stdin)
  {
    this.file = file;
    this.idx = 0;
  }

  this(StrType)(StrType s, File file = stdin) if (isSomeString!(StrType))
  {
    this.file = file;
    this.idx = 0;
    fromString(s);
  }

  private char[] next()
  {
    if (idx < str.length)
    {
      return str[idx++];
    }

    char[] s;
    while (s.length == 0)
    {
      s = file.readln.strip.to!(char[]);
    }

    str = s.split;
    idx = 0;

    return str[idx++];
  }

  T next(T)()
  {
    return next.to!(T);
  }

  T[] nextArray(T)(size_t len)
  {
    T[] ret = new T[len];

    foreach (ref c; ret)
    {
      c = next!(T);
    }

    return ret;
  }

  void scan()()
  {
  }

  void scan(T, S...)(ref T x, ref S args)
  {
    x = next!(T);
    scan(args);
  }

  void fromString(StrType)(StrType s) if (isSomeString!(StrType))
  {
    str ~= s.to!(char[]).strip.split;
  }
}

//Digit count---{{{
int DigitNum(int num) {
  int digit = 0;

  while (num != 0) {
    num /= 10;
    digit++;
  }

  return digit;
}
//}}}
//}}}

void main() {
  Scanner sc = new Scanner;

  int N, A, B;

  sc.scan(N, A, B);
  int res = 0;

  foreach (i; 0 .. N + 1) {
    if (A <= num(i) && num(i) <= B)
      res += i;
  }

  writeln(res);
}

int num(int n) {
  if (n / 10 == 0) return n % 10;

  return num(n / 10) + (n % 10);
}


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

int read(){
	int a = 0; char c = getchar(); while(!isdigit(c)) c = getchar();
	while(isdigit(c)){a = a * 10 + c - 48; c = getchar();} return a;
}

const int _ = 2e5 + 7 , MOD = 998244353 , iv2 = (MOD + 1) / 2;
struct Edge{int end , upEd;}Ed[_ << 1];
int dp[_][3][3] , N , cntEd , head[_];
void addEd(int a , int b){Ed[++cntEd] = (Edge){b , head[a]}; head[a] = cntEd;}

int mx , id , pre[_];
void dfs1(int x , int p , int l){
	pre[x] = p; if(l > mx){mx = l; id = x;}
	for(int i = head[x] ; i ; i = Ed[i].upEd)
		if(Ed[i].end != p) dfs1(Ed[i].end , x , l + 1);
}

int mxdep[_];
void dfs2(int x , int p){
	for(int i = head[x] ; i ; i = Ed[i].upEd)
		if(Ed[i].end != p){dfs2(Ed[i].end , x); mxdep[x] = max(mxdep[x] , mxdep[Ed[i].end] + 1);}
}

void DP(int x , int p){
	dp[x][0][0] = 1; bool flg = 0;
	for(int i = head[x] ; i ; i = Ed[i].upEd)
		if(Ed[i].end != p){
			flg = 1; DP(Ed[i].end , x); static int tmp[3][3]; memset(tmp , 0 , sizeof(tmp));
			for(int j = 0 ; j < 3 ; ++j)
				for(int k = 0 ; k < 3 ; ++k)
					for(int p = 0 ; p < 3 ; ++p)
						for(int q = 0 ; q < 3 ; ++q){
							int coef = 3;
							if(mxdep[Ed[i].end] + 1 == mxdep[x]){
								tmp[min(j + p , 2)][k] = (tmp[min(j + p , 2)][k] + 1ll * dp[x][j][k] * dp[Ed[i].end][p][q]) % MOD;
								tmp[j][min(k + q , 2)] = (tmp[j][min(k + q , 2)] + 1ll * dp[x][j][k] * dp[Ed[i].end][p][q]) % MOD;
								coef -= 2;
							}
							tmp[j][k] = (tmp[j][k] + 1ll * coef * dp[x][j][k] * dp[Ed[i].end][p][q]) % MOD;
						}
			memcpy(dp[x] , tmp , sizeof(tmp));
		}
	if(!flg){dp[x][0][0] = 0; dp[x][1][1] = 1;}
}

int main(){
	N = read(); for(int i = 1 ; i < N ; ++i){int x = read() , y = read(); addEd(x , y); addEd(y , x);}
	dfs1(1 , 0 , 0); mx = 0; int t = id; dfs1(t , 0 , 0);
	for(int i = 0 ; i < mx / 2 ; ++i) id = pre[id];
	if(mx & 1){
		dfs2(id , pre[id]); DP(id , pre[id]); dfs2(pre[id] , id); DP(pre[id] , id); int sum = 0;
		for(int i = 0 ; i < 3 ; ++i)
			for(int j = 0 ; j < 3 ; ++j)
				for(int k = 0 ; k < 3 ; ++k)
					for(int l = 0 ; l < 3 ; ++l){
						if(i == 1 && l == 1) sum = (sum + 1ll * dp[id][i][j] * dp[pre[id]][k][l]) % MOD;
						if(j == 1 && k == 1) sum = (sum + 1ll * dp[id][i][j] * dp[pre[id]][k][l]) % MOD;
					}
		printf("%lld\n" , 1ll * sum * iv2 % MOD);
	}else{dfs2(id , 0); DP(id , 0); printf("%lld\n" , 1ll * iv2 * dp[id][1][1] % MOD);}
	return 0;
}

Measured memory_bytes: 21376
#include <iostream>
using namespace std;
#define debug 0
int main(){
	int n;
	int d[102][102],e[102][102],D[102][102];
	int ans;
	while(cin>>n,n){
		for(int i=0;i<=100;i++)for(int j=0;j<=100;j++)d[j][i]=e[j][i]=D[j][i]=0;
		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>d[j][i];
		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)e[j][i]=e[j-1][i]+d[j][i];
		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)D[j][i]=D[j][i-1]+e[j-1][i]+d[j][i];
		ans=D[1][1];
		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=0;k<i;k++)for(int l=0;l<j;l++)if(ans<D[j][i]+D[l][k]-D[l][i]-D[j][k])ans=D[j][i]+D[l][k]-D[l][i]-D[j][k];
		cout<<ans<<endl;
		if(debug==0)break;
	}
	return 0;
}


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

int main() {
  int X;
  cin >> X;
  
  if (X <= 1199) {
    if (X <= 799) {
      if (X >= 600) {
        cout << 7 << endl;
      }
      else if (X >= 400) {
        cout << 8 << endl;
      }
    }
    else {
      if (X <= 999) {
        cout << 6 << endl;
      }
      else {
        cout << 5 << endl;
      }
    }
  }
  else {
    if (X <= 1599) {
      if (X <= 1399) {
        cout << 4 << endl;
      }
      else {
        cout << 3 << endl;
      }
    }
    else {
      if (X <= 1799) {
        cout << 2 << endl;
      }
      else {
        cout << 1 << endl;
      }
    }
  }
}

Measured memory_bytes: 3628
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;

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);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }

    static class Task {
        void solve(InputReader in, PrintWriter out) {
            int N = in.nextInt(), Q = in.nextInt();
            String S = in.next();

            int ac[] = new int[N];

            int cnt = 0;
            char prev = 'Q';
            for (int i = 0; i < N; ++i) {
                if (prev == 'A' && S.charAt(i) == 'C') ++cnt;
                ac[i] = cnt;
                prev = S.charAt(i);
            }

            for (int i = 0; i < Q; ++i) {
                int l = in.nextInt() - 1, r = in.nextInt() - 1;
                int ans = ac[r];
                if (l > 0) {
                    ans -= ac[l - 1];
                    if (S.charAt(l - 1) == 'A' && S.charAt(l) == 'C') --ans;
                }
                out.println(ans);
            }
        }
    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

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

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

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

        int[] nextIntArray(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; ++i) arr[i] = this.nextInt();
            return arr;
        }
    }
}


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

int main(){
		
	ll n,w,wt,val;
	cin>>n>>w;
	ll dp[100003];
	for(int i=0;i<100003;++i)
		dp[i]=1000000000007;
	dp[0]=0;
	for(int i=1;i<=n;++i){
		cin>>wt>>val;
		for(int j=100000-val;j>=0;--j)
			dp[j+val]=min(dp[j+val],dp[j]+wt);
	}
	for(ll i=100000;i>=0;--i)
		if(dp[i]<=w){
			cout<<i;
			break;
		}
	return 0;
}


Measured memory_bytes: 4340