akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
#define ll long long
int main()
{
	int n;
	cin>>n;
	vector<vector<ll>>dp(n,vector<ll>(3,0));
	vector<vector<ll>>v(n,std::vector<ll> (3));
	for(ll i=0;i<n;i++)
	{
		for(ll j=0;j<3;j++) cin>>v[i][j];
	}
	for(ll i=0;i<3;i++) dp[0][i]=v[0][i];
	for(ll i=1;i<n;i++)
	{
		for(ll j=0;j<3;j++)
		{
			for(ll k=0;k<3;k++)
			{
				if(j!=k)
				{
					dp[i][j]=max(dp[i][j],dp[i-1][k]+v[i][j]);
				}
			}
		}
	}
	cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]))<<"\n";
	return 0;
}


Measured memory_bytes: 11136
#include<bits/stdc++.h>
using namespace std;
int main()
{
  long long int n,w;
  cin>>n>>w;
  long long int wi,va;
  vector<long long int>dp(w+1);
  for(long long int i=1;i<=n;i++)
  {  cin>>wi>>va;
    for(long long int j=w-wi;j>=0;j-=1)
    {
      dp[j+wi]=max(dp[j+wi],va+dp[j]);
                           }
                           }
       cout<<dp[w];
                           return 0;
                           }
        


Measured memory_bytes: 1024
N = int(input())
D, X = map(int, input().rstrip().split())
A = [int(input()) for _ in range(N)]
answer = X
for i in A:
    count = 0
    for j in range(D):
        day = j*i + 1
        if day <= D:
            count += 1
        else:
            break
    answer += count
print(answer)

Measured memory_bytes: 3064
package main

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

func main() {

	// 繰り返し回数
	N, _ := strconv.Atoi(readLine())

	words := strings.Fields(readLine())

	intWords := make([]int, 0)
	for _, strWord := range words {
		intWord, _ := strconv.Atoi(strWord)
		intWords = append(intWords, intWord)
	}

	fmt.Println(reduce(intWords))

	// n
	for n := 0; n < N-1; {
		m := n + 1

		n_loop := n
		m_loop := m

		for ; n_loop >= 0 && intWords[n_loop] > intWords[m_loop]; {

			temp := intWords[n_loop]
			intWords[n_loop] = intWords[m_loop]
			intWords[m_loop] = temp
			m_loop--
			n_loop--

		}
		fmt.Println(reduce(intWords))
		n++
	}

	return
}

var rdr = bufio.NewReaderSize(os.Stdin, 1000000)

func readLine() string {
	buf := make([]byte, 0, 1000000)
	for {
		l, p, e := rdr.ReadLine()
		if e != nil {
			panic(e)
		}
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}

func reduce(intArray []int) string {
	reducedString := ""
	for _, inz := range intArray {
		reducedString += " " + strconv.FormatInt(int64(inz), 10)
	}
	return strings.Trim(reducedString, " ")
}



Measured memory_bytes: 3268
x = int(input())

def is_prime(p):
    if p in [2, 3]:
        return True
    if p % 2 == 0:
        return False
    if p % 3 == 0:
        return False
    for i in range(5, int(p**(1/2)+1)):
        if p % i == 0:
            return False
    return True

while True:
    if is_prime(x):
        print(x)
        break
    x += 1

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

int main(){
	int N,L;
	cin >> N >> L;
	
	if (L >= 1){
		cout << N*(L-1) + N*(N+1)/2 - L << endl;
	}else{
		int temp = min(1-L,N);
		cout << N*(L-1) + N*(N+1)/2 - (L + temp -1) << endl;
	}
	
	
	
	
}



Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>

using namespace std;

#define MAX_N 1121
#define MAX_K 15

vector<int> primes;
int dp[MAX_N][MAX_N / 3][MAX_K];

// m以上の素数をk個使ってnを作る方法
int rec(int n, int m, int k) {
    if (n == 0 && k == 0) return 1;
    if (k == 0) return 0;
    if (dp[n][m][k] != -1) return dp[n][m][k];

    int ret = 0;
    for (int i = m; i < primes.size(); ++i) {
        if (n - primes[i] >= 0) {
            ret += rec(n - primes[i], i + 1, k - 1);
        }
    }

    return dp[n][m][k] = ret;
}

void solve(int n, int k) {
    memset(dp, -1, sizeof(dp)); // dpの値をすべて-1に
    int ans = rec(n, 0, k);
    cout << ans << endl;
}

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

    for (int i = 2; i < MAX_N; ++i) {
        bool flag = true;
        for (int j = 2; j * j <= i; ++j) {
            if (i % j == 0) flag = false;
        }
        if (flag) primes.push_back(i);
    }

    while (true) {
        int n, k;
        cin >> n >> k;
        if (n == 0) break;
        solve(n, k);
    }

    return 0;
}



Measured memory_bytes: 27572
#include <iostream>
using namespace std;
int main(void){
  int n;
  cin >> n;
  
  int value;
  
  int ans = 0;
  
  for(int i=0;i<=25;i++){
    for(int j=0;j<=14;j++){
      value = i * 4 + j * 7;
      if(value == n)
        ans++;
    }
  }
  
  if(ans)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  
  return 0;
}
        
      

Measured memory_bytes: 256
/*by freesteed*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back
#define fill(x,c) memset(x,c,sizeof(x))
#define fi first
#define se second
#define sz(A) (int)(A.size())
#define all(x) (x).begin(),(x).end()
#define caset int ___T; cin>>___T; for(int cs=1;cs<=___T;cs++)
#define get_be(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
//get_be biger & equal
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
const ll mod=1e9+7;
const ll oo=1e9+10;
const int Max = 1e6+10;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll n;
void solve(){
	cin>>n;
	vector<PII> a;
	rep(i,0,n){
		int t;
		cin>>t;
		a.pb({t,i+1});
	} 
	sort(all(a));
	rep(i,0,n)cout<<a[i].se<<" ";
}
int main() {
	//ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//caset{
		solve();
	//}
  	return 0;
}





Measured memory_bytes: 1780
#include<iostream>
#include<algorithm>

using namespace std;

const int INF = (1<<15)-2;
const int MAX = 100001;
const int FOOT = 10;
short dp[MAX][FOOT][FOOT][2];
string s;

int getColumn(int num){
  int step[3][3] =
    {{7,8,9},
     {4,5,6},
     {1,2,3}};

  for(int i = 0; i < 3; i++)
    for(int j = 0; j < 3; j++)
      if(step[i][j] == num) return j;
}

void init(){
  fill(dp[0][0][0],dp[0][0][0]+MAX*FOOT*FOOT*2,INF);
  for(int i = 0; i < FOOT; i++)
    for(int j = i; j < FOOT; j++) dp[0][i][j][0] = dp[0][i][j][1] = 0;
}

void solve(){

  short ans = INF;

  for(int i = 0; i < (int)s.length(); i++){
    int pos = s[i]-'0';
    
    for(int l = 1; l < FOOT; l++){
      if(l == 5) continue;
      for(int r = 1; r < FOOT; r++){
	if(r == 5) continue;
	for(int x = 0; x < 2; x++){
	  // x = 0 -> left 1 -> right
	  if(x){
	    //follow the rule(right foot)
	    if(getColumn(l) <= getColumn(pos)) dp[i+1][l][pos][1] = min(dp[i+1][l][pos][1],dp[i][l][r][0]);
	    //violate(left foot)
	    if(getColumn(r) >= getColumn(pos)) dp[i+1][pos][r][0] = min(dp[i+1][pos][r][0],(short)(dp[i][l][r][0]+1));
	  }else{
	    //follow the rule(left foot)
	    if(getColumn(r) >= getColumn(pos)) dp[i+1][pos][r][0] = min(dp[i+1][pos][r][0],dp[i][l][r][1]);
	    //violate(right foot)
	    if(getColumn(l) <= getColumn(pos)) dp[i+1][l][pos][1] = min(dp[i+1][l][pos][1],(short)(dp[i][l][r][1]+1));
	  }
	}
      }
    }
    for(int i = 1; i < FOOT; i++)
      for(int j = 1; j < FOOT; j++)
	ans = min(ans,min(dp[s.length()][i][j][0],dp[s.length()][i][j][1]));
  }
  cout << ans << endl;
}

int main(){
  while(cin >> s && s != "#"){
    init();
    solve();
  }
  return 0;
}

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

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

    vector<long long> csum(100100);
    vector<long long> csum2(100100);
    vector<long long> a(100100);
    for(int i=0;i<N;i++){
        cin >> a[i];
    }
    long long c1=0,c2=0;
    //+-+-の順
    for(int i=0;i<N;i++){
        if(i==0)csum[i]=a[i];
        else csum[i]=csum[i-1]+a[i];

        if(i%2==0 && csum[i]<=0) {
            c1+=1-csum[i];
            csum[i]=1;
        }
        else if(i%2==1 && csum[i]>=0) {
            c1+=csum[i]+1;
            csum[i]=-1;
        }
    }
    //-+-+の順
    for(int i=0;i<N;i++){
        if(i==0)csum2[i]=a[i];
        else csum2[i]=csum2[i-1]+a[i];
        if(i%2==0 && csum2[i]>=0) {
            c2+=csum2[i]+1;
            csum2[i]=-1;
        }
        else if(i%2==1 && csum2[i]<=0) {
            c2+=1-csum2[i];
            csum2[i]=1;
        }
    }
    cout << min(c1,c2) << endl;
}

Measured memory_bytes: 2560
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
a=lnii()
total=sum(a)

mod=10**9+7

ans=0
for i in range(n-1):
  total-=a[i]
  ans+=a[i]*total
  ans%=mod

print(ans)

Measured memory_bytes: 31356
tmp = gets.split.map{|n| n.to_i}
A = tmp[0]
B = tmp[1]
if B == 1 then
  puts 0
else
  for i in 1..20 do
    n = ((A - 1) * i ) + 1
    if n >= B then
      puts i
      break
    end
  end
end

Measured memory_bytes: 1788
n = int(input())
s = input()

w = [1 if s[i] == '.' else 0 for i in range(n)]
b = [1 if s[i] == '#' else 0 for i in range(n)]
for i in range(n - 1):
    w[i + 1] += w[i]
    b[i + 1] += b[i]

ans = float('inf')
for i in range(n):
    ans = min(ans, b[i] + w[n - 1] - w[i])
ans = min(ans, b[n - 1], w[n - 1])
print(ans) 

Measured memory_bytes: 19304
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000050
#define ll long long
#define MOD 1000000007
#define pii pair<int,int>
#define all(v) (v).begin(),(v).end()

unordered_map<int,unordered_set<int> >mp;
int arr[MAX];
vector<int>divis[MAX];

void sieve(int n)
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = i; j <= n; j += i)
        {
            divis[j].push_back(i);
        }
    }
}

int main()
{
    sieve(1000000);
    int n, v;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &v);
        arr[i] = v;
        mp[v].insert(i);
    }
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        bool fnd = 0;
        for(int v : divis[arr[i]])
        {
            if(mp.find(v) != mp.end())
            {
                if(mp[v].size() > 1 || (mp[v].count(i) != 1)) fnd = 1;
            }
        }
        if(fnd == 0) ans++;
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 143088
def DFS(n):
    if len(n)>=3 and len(set(list(n))&{"3","5","7"})==3:
        A.append(int(n))
    if len(n)<10:
        for i in ("3","5","7"):
            DFS(n+i)


n=int(input())
A=[]
for i in ("3","5","7"):DFS(i)
A.sort()

cnt=0
while 1:
    if A[cnt]<=n:cnt +=1
    else:break
print(cnt)

Measured memory_bytes: 72156
#include <bits/stdc++.h>
//#define DEBUG
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
template <class T>
void print_vect(std::vector<T> v){
    for(int i = 0 ; i < v .size(); i++) cout << v[i] << " ";
    cout << endl;
}
bool cmp_vec(vi& a, vi& b){
    for(int i = 0 ; i < a.size() ; i++){
        if( a[i] != b[i]){
            return false;
        }
    }
    return true;
}
void solve(){
    int n;
    cin >> n;
    vi p(n), q(n);
    for( int i = 0 ; i < n ; i++){
        cin >> p[i];
    }
    for( int i = 0 ; i < n ; i++){
        cin >> q[i];
    }
    vi r(n);
    for(int i = 1; i <= n ; i++){
        r[i - 1] = i;
    }
    int a = -1, b = -1;
    int index = 0;
    do{
        if( a < 0){
            if( cmp_vec(p, r)){
                a = index;
            }
        }
        if( b < 0){
            if(cmp_vec(q,r)){
                b = index;
            }
        }
        index++;
    }while(next_permutation(r.begin(), r.end()));
    cout << abs( a - b) << endl;
}

int main()
{
    //making data IO Fast
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    /****************************/

    #ifdef DEBUG
    int TEST_CASES = 2;
    while(TEST_CASES--){
    #endif // DEBBUG

    solve();

    #ifdef DEBUG
    }
    #endif // DEBUG
    
    return 0;
}

//Thanks to CSES problemset
// I am trained with this kind of problem

Measured memory_bytes: 3568
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.Abc
{
    class Abc_049_C
    {
        // https://atcoder.jp/contests/abc049/tasks/arc065_a
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            string[] divide = new string[4] { "dream", "dreamer", "erase", "eraser" };

            for (int k = 0; k < 4; ++k) divide[k] = new string(divide[k].Reverse().ToArray());
            // 文字列の入力
            string s = Console.ReadLine();
            s = new string(s.Reverse().ToArray());
            bool can = true;
            int cnt = 0;
            while (can)
            {
                bool can2 = false;
                if (cnt == s.Length)
                {
                    Console.WriteLine("YES");
                    Console.Out.Flush();
                    return;
                }
                for (int j = 0; j < 4; j++)
                {
                    string d = divide[j];
                    if (s.Length - cnt >= d.Length && s.Substring(cnt, d.Length) == d)
                    {
                        can2 = true;
                        cnt += d.Length;
                    }
                    //if (s.Length >= d.Length && s.Substring(0, d.Length) == d)
                    //{
                    //    s = s.Remove(0, d.Length);
                    //    can2 = true;
                    //    if (string.IsNullOrEmpty(s)){
                    //        Console.WriteLine("YES");
                    //        Console.Out.Flush();
                    //        return;
                    //    }
                    //}
                }
                if (!can2)
                {
                    can = false;
                    break;
                }
            }

            Console.WriteLine("NO");

            Console.Out.Flush();
        }
    }
}


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

constexpr int max_a = 30000;
vector<int> solve(int n) {
    vector<int> answer;
    long long s = 0;
    REP3 (a, 1, max_a + 1) {
        if (a % 2 == 0 or a % 3 == 0 or a % 5 == 0 or a % 7 == 0) {
            answer.push_back(a);
            s += a;
        }
        if (answer.size() == n) break;
    }
    REP3 (a, answer.back() + 1, max_a + 1) {
        if (a % 2 == 0 or a % 3 == 0 or a % 5 == 0 or a % 7 == 0) {
            REP (i, n) {
                if ((s - answer[i] + a) % (2 * 3 * 5 * 7) == 0) {
                    answer[i] = a;
                    return answer;
                }
            }
        }
    }
    assert (false);
}

int main() {
    int n; cin >> n;
    auto answer = solve(n);
    for (int a : answer) {
        if (a != answer.front()) cout << ' ';
        cout << a;
    }
    cout << endl;
    return 0;
}


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

int main(){
	int N, A, B;
	cin >> N >> A >> B;
	int P[N];
	int one = 0, two = 0, three = 0;
	for(int i=0; i<N; i++){
		cin >> P[i];
		if(P[i] <= A){
			one++;
		}else if(P[i] <= B){
			two++;
		}else{
			three++;
		}
	}
	cout << min(min(one, two), three) << endl;
	return 0;
}

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

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

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

// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
  vector<mint> fact, ifact;
  combination(int n) : fact(n + 1), ifact(n + 1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
  }
  mint operator()(int n, int k) const {
    if (k < 0 || k > n) return 0;
    return fact[n] * ifact[k] * ifact[n - k];
  }
};

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  sort(a.begin(), a.end());
  combination c(n);
  mint ans;
  for (int i = k - 1; i < n; i++) {
    auto t = c(i, k - 1);
    ans += t * a[i];
    ans -= t * a[n - i - 1];
  }
  cout << ans.x << endl;
  return 0;
}


Measured memory_bytes: 2176
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <cmath>
#include <string>
#define FI first
#define SE second
#define PF push_front
#define PB push_back
#define PPF pop_front
#define PPB pop_back
#define MA make_pair
#define ll long long
#define PA pair<int,int>
#define VE vector<int>
#define VP vector<PA>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
using namespace std;
//
const int INF=1e9+7;
const int mod=1e9+7;
//
struct poi{
  int X;int Y;int Z;
  bool operator<(const poi&R)const{
    return X==R.X ? Y==R.Y ? Z<R.Z : Y<R.Y : X<R.X;
  }
};
/*
ll GCD(ll A,ll B){
  return (B==0)?(A):(GCD(B,A%B));
}
ll LCM(ll A,ll B){
  return A/GCD(A,B)*B;
}
*/
int main(){
	int N;
	VP T;
	VE V;
	cin>>N;
	T.PB(MA(0,0));
	V.PB(0);
	int pre=0;
	FOR(i,0,N){
		int t;
		cin>>t;
		T.PB(MA(pre*2,(pre+t)*2));
		pre+=t;
	}
	FOR(i,0,N){
		int v;
		cin>>v;
		V.PB(v*2);
	}
	T.PB(MA(pre*2,pre*2));
	V.PB(0);
	//
	int n[200000];
	fill(n,n+200000,INF);
	FOR(i,0,N+2){
		int l=T[i].FI,r=T[i].SE;
		FOR(j,l,r+1){
			n[j]=min(n[j],V[i]);
		}
		ROF(j,0,l){
			n[j]=min(n[j+1]+1,n[j]);
		}
		FOR(j,r+1,pre*2+1){
			n[j]=min(n[j-1]+1,n[j]);
		}
	}
	double ans=0;
	FOR(i,0,pre*2){
		ans+=(double)(n[i+1]+n[i])/8;
	}
	printf("%.9f\n",ans);
	return 0;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <cstdlib>
#include <queue>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#define f first
#define s second
#define mp make_pair

#include<complex>
#define EPS (1e-10)

using namespace std;

using std::complex;
typedef complex<double> P;

static inline bool eq(const P &a, const P &b){
  return abs(a-b) < EPS;
}

static inline double inp(const P &a, const P &b){
  return (conj(a)*b).real();
}

static inline double outp(const P &a, const P &b){
  return (conj(a)*b).imag();
}


struct S{
  P p1;
  P p2;
  S(P p,P q) : p1(p), p2(q) {}
  S(){}
};

int ccw(P p0, P p1, P p2){
  P d1 = p1-p0;
  P d2 = p2-p0;
  double dx1 = d1.real(), dx2 = d2.real();
  double dy1 = d1.imag(), dy2 = d2.imag();

  if(dx1*dy2 > dy1*dx2) return  1;
  if(dx1*dy2 < dy1*dx2) return -1;
  if((dx1*dx2 < 0) || (dy1*dy2 < 0)) return -1;
  if((dx1*dx1+dy1*dy1) < (dx2*dx2+dy2*dy2)) return 1;
  return 0;
}

bool intersect(const S &s1, const S &s2){
  return ((ccw(s1.p1, s1.p2, s2.p1)
	   *ccw(s1.p1, s1.p2, s2.p2)) <= 0)
    &&((ccw(s2.p1, s2.p2, s1.p1)
	*ccw(s2.p1, s2.p2, s1.p2)) <= 0);
}

class Line{
public:
  P p;
  P d;
  Line(){}
  Line(P pos, P dir){p=pos; d=dir/abs(dir);}
};

Line LineDirect(P pos, P dir){
  return Line(pos, dir);
}

Line LinePos(P p1, P p2){
  return Line(p1, p2-p1);
}

P crossPoint(const Line &l1, const Line &l2){
  double num = outp(l2.d, l2.p-l1.p);
  double denom = outp(l2.d, l1.d);
  return P(l1.p + l1.d * num/denom);
}


int main(){
  int x1, y1, x2, y2;
  while(scanf("%d%d%d%d", &x1, &y1, &x2, &y2), (x1 | x2 | y1 | y2)){
    S s[3];
    vector<P> p;

    s[0] = S(P(x1, y1), P(x2, y2));
    REP(i,2){
      scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
      s[i + 1] = S(P(x1, y1), P(x2, y2));
    }

    for(int i = 0; i < 3; i++){
      for(int j = i + 1; j < 3; j++){
	P dir1 = s[i].p1 - s[i].p2;
	P dir2 = s[j].p1 - s[j].p2;

	P tmp = dir1 / dir2;
	if(std::abs(tmp.imag()) > EPS && intersect(s[i], s[j])){
	  Line l1 = LinePos(s[i].p1, s[i].p2);
	  Line l2 = LinePos(s[j].p1, s[j].p2);
	  p.push_back(crossPoint(l1, l2));
	}
      }
    }

    const char *un[] = {
      "dai-kichi",
      "chu-kichi",
      "kichi",
      "syo-kichi",
      "kyo"
    };
    int ans = 4;

    if(p.size() == 3){
      P p1 = p[2] - p[0];
      P p2 = p[1] - p[0];

      double sz = std::abs(outp(p1, p2)) / 2.0;

      if(sz + EPS > 1900000){
	ans = 0;
      }else if(sz + EPS > 1000000){
	ans = 1;
      }else if(sz + EPS > 100000){
	ans = 2;
      }else if(sz > EPS){
	ans = 3;
      }
    }

    puts(un[ans]);
  }
  return 0;
}

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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

ll x,a,b;

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

  cin>>a>>b>>x;
  if(x<a){
    cout<<x%mod<<endl;
    return 0;
  }

  ll d=(a-b);
  ll n=(x-a)/d; n++;

  a%=mod; b%=mod; x%=mod; d%=mod; n%=mod;
  ll res=((a*n%mod)+(x-(d*n%mod)+mod))%mod;
  cout<<res<<endl;

  return 0;
}



Measured memory_bytes: 3184
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define krep(i,k,n,m) for(int i=k;i<n;i+=m)
#define erep(i,k,n) for(int i=k;i<n;i++)
//最大公約数
int gcd(int s,int b){
    if(b==0)return s;
    return gcd(b,s%b);
}
signed main() {
    int n;
    cin>>n;
    for(int i=n;i>=1;i--){
        if(i*i<=n){
            cout<<i*i<<endl;
            break;
        }
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<int,int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
const LL mod=1000000007;
const LL LINF=1LL<<62;
const int INF=1<<30;
int dx[]={1,0,-1,0,1,-1,1,-1};
int dy[]={0,1,0,-1,1,-1,-1,1};

int h,w,k;
int sx,sy,gx,gy;


int main(){
    cin >> h >> w >> k;
    cin >> sx >> sy >> gx >> gy;
    sx--,sy--,gx--,gy--;
    vector<string> s(h);
    for (int i = 0; i < h; i++) {
        cin >> s[i];
    }
    vector<vector<int>> dp(h + 1, vector<int> (w + 1, INF));
    queue<pair<P,int>> q;
    q.push({{sx, sy}, 0});
    while(not q.empty()){
        auto pp = q.front();q.pop();
        auto p = pp.fs;
        if(gx == p.fs && gy == p.sc){
            cout << pp.sc << endl;
            return 0;
        }
        for (int i = 0; i < 4; i++) {
            int x = p.fs, y = p.sc;
            for (int j = 0; j < k; j++) {
                int nx = x + dx[i], ny = y + dy[i];
                if(0<=nx&&nx<h&&0<=ny&&ny<w&&s[nx][ny]!='@'){
                    if(chmin(dp[nx][ny], pp.sc + 1)){
                        q.push({{nx, ny}, pp.sc + 1});
                    }
                    else if(dp[nx][ny] == pp.sc + 1){
                    }
                    else{
                        break;
                    }
                }
                else{
                    break;
                }
                x = nx, y = ny;
            }
        }
    }
    cout << -1 << endl;
    return 0;
}


Measured memory_bytes: 16124
#include<bits/stdc++.h>
using namespace std;
typedef	    long long       ll;
typedef	    vector<ll>      vll;
#define     pb              push_back
#define	    PB              pop_back
#define	    nn              "\n"
#define	    all(p)          p.begin(),p.end()
#define	    zz(v)           (ll)v.size()
#define	    mms(ar,a)       memset(ar,a,sizeof(ar))
#define	    ss              ' '
#define     S(a)            scanf("%lld",&a)
#define     SS(a,b)         scanf("%lld %lld",&a,&b)
#define     SSS(a,b,c)      scanf("%lld %lld %lld",&a,&b,&c)
#define     yes             printf("YES\n")
#define     no              printf("NO\n")
#define     P(a)            printf("%lld\n",a)
#define     PP(a,b)         printf("%lld %lld\n",a,b)
#define	    gcd(a,b)        __gcd(a,b)
#define	    lcm(a,b)        (a*b)/gcd(a,b)
#define	    pi              acos(-1.0)
#define	    OO              1000000007

void solve(){
    ll a,b,i,j,t,k,lie,m,n,o,x,y,z,ar[2010];
    ll p=0,sm=0,cnt=0;
    SS(n,k);
    for(i=0;i<n;i++) S(ar[i]);
    sort(ar,ar+n);
    for(i=0;i<k;i++){
        sm+=ar[i];
    }
    P(sm);
}

int main(){
//	freopen("input.txt", "r", stdin);
    ll i,t;
//    S(t);
//    while(t--){
        solve();
//    }

    return 0;
}



Measured memory_bytes: 3768
my (@sa, @sb, @sc);
{
  chomp (my $in = <STDIN>);
  @sa = split '', $in;
}
{
  chomp (my $in = <STDIN>);
  @sb = split '', $in;
}
{
  chomp (my $in = <STDIN>);
  @sc = split '', $in;
}
my $card = shift @sa;
while (1) {
  if ($card eq "a") {
    if (@sa == 0) {
      print "A\n";
      exit;
    }
    $card = shift @sa 
  } elsif ($card eq "b") {
    if (@sb == 0) {
      print "B\n";
      exit;
    }
    $card = shift @sb;
  } else {
    if (@sc == 0) {
      print "C\n";
      exit;
    }
    $card = shift @sc;
  }
}

Measured memory_bytes: 512
#include<iostream>
using namespace std;
#define N 100010
int a[N];
int main(void) {
  int n;
  int ans=-1;
  cin>>n;
  for(int i=0; i<n; i++) {
    int x;
    cin>>x;
    a[x+2]++;
    a[x+1]++;
    a[x]++;
  }
  for(int i=0; i<N; i++) {
    ans=max(ans, a[i]);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 640
// #pragma GCC target("avx2")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
using namespace std;
const long long mod=998244353;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3121000;
long long fact[C_SIZE];
long long finv[C_SIZE];
long long inv[C_SIZE];
long long Comb(int a,int b){
 	if(a<b||b<0)return 0;
 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
void init_C(int n){
	fact[0]=finv[0]=inv[1]=1;
	for(int i=2;i<n;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<n;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}
long long pw(long long a,long long b){
	if(a<0LL)return 0;
	if(b<0LL)return 0;
	long long ret=1;
	while(b){
		if(b%2)ret=ret*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return ret;
}
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
// ここから編集しろ
vector<int>g[210000];
int t[210000];
int ans[210000];
void dfs(int a,int b,int c){
	ans[a]=c+t[a];
	for(int i=0;i<g[a].size();i++){
		if(g[a][i]==b)continue;
		dfs(g[a][i],a,c+t[a]);
	}
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a-1;i++){
		int p,q;scanf("%d%d",&p,&q);
		p--;q--;
		g[p].push_back(q);
		g[q].push_back(p);
	}
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);
		p--;
		t[p]+=q;
	}
	dfs(0,-1,0);
	for(int i=0;i<a;i++){
		if(i)printf(" ");
		printf("%d",ans[i]);
	}printf("\n");
}

Measured memory_bytes: 32128
n, d = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for j in range(n)]

import itertools,math
cnt = 0
for i,j in itertools.combinations(range(n),2):
    distance = 0
    for y,z in zip(x[i],x[j]):
        distance += (abs(y-z))**2
    distance = math.sqrt(distance)
    if distance.is_integer():
        cnt += 1
print(cnt)

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

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)

using namespace std;

typedef int64_t ll;
typedef vector<int> Vi;

template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

const int inf = 2e8;

int n, m;
Vi va, open, dp;

void init()
{
	cin >> n >> m;
	va.resize(m);
	open.resize(m);
	dp.resize(1 << n, inf);

	REP(i, m)
	{
		int a, b; cin >> a >> b;
		va[i] = a;

		int open_mask = 0;
		REP(_i, b)
		{
			int chest; cin >> chest;
			open_mask |= 1 << (chest - 1);
		}

		chmin(dp[open_mask], a);
	}
}

int main()
{
	init();

	int target = (1 << n) - 1;

	REP(i, target)
	{
		if (dp[i] == inf)
			continue;

		for (int j = i + 1; j <= target; ++j)
			chmin(dp[i | j], dp[i] + dp[j]);
	}


	if (dp[target] == inf)
		cout << -1 << endl;
	else
		cout << dp[target] << endl;

}


Measured memory_bytes: 256
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        long ans = k;
        for (int i = 0; i < n - 1; i++) {
            ans *= (k-1);
        }
        System.out.println(ans);
    }
}

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

using namespace std;

typedef long long ll;

const int INF = 1000000000;

int main()
{
  int A, B, K;
  scanf("%d %d %d", &A, &B, &K);
  int len = min(K, B - A + 1);
  set<int> st;
  for (int i = 0; i < len; ++i) {
    st.insert(A + i);
    st.insert(B - i);
  }
  vector<int> v(st.begin(), st.end());
  sort(v.begin(), v.end());
  for (int i = 0; i < (int)v.size(); ++i) {
    printf("%d\n", v[i]);
  }

  return 0;
}


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

int main() {
  int n, res = 0;
  cin >> n;
  int a[n], maxInt;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for(int i = 0; i < n - 2; i++) {
    for(int j = i + 1; j < n - 1; j++) {
      for(int k = j + 1; k < n; k++) {
        if(a[i] != a[j] && a[j] != a[k] && a[i] != a[k]) {
          maxInt = max(a[i], a[j]);
          maxInt = max(maxInt, a[k]);
          if(maxInt < (a[i]+a[j]+a[k] - maxInt)) res++;
        }
      }
    }
  }
  cout << res << endl;
}


Measured memory_bytes: 3592
import java.io.*;
 
class Main{
    public static void main(String[]args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        String[] str1 = br.readLine().split(" ");
        int r = Integer.parseInt(str1[0]);
        int c = Integer.parseInt(str1[1]);
        int[][] data = new int[r][c];
        int[] sumR = new int[r];
        int[] sumC = new int[c];
        int sumX = 0;
 
        // r x c ?????¨??????\?????????????????´???????
        for(int i=0; i<r; i++){
            String[] str2 = br.readLine().split(" ");
            for(int k=0; k<c; k++){
                data[i][k] = Integer.parseInt(str2[k]);
            }
        }
 
        // sumR ???¨ sumX ?????¨??????????
        for(int i=0; i<r; i++){
            for(int k=0; k<c; k++){
                sumR[i] += data[i][k];
            }
            sumX += sumR[i];
        }
        // sumC ?????¨??????????
        for(int i=0; i<c; i++){
            for(int k=0; k<r; k++){
                sumC[i] += data[k][i];
            }
        }
 
        // ??????
        for(int i=0; i<r; i++){
            for(int k=0; k<c; k++){
                sb.append(data[i][k]).append(" ");
            }
            sb.append(sumR[i]).append("\n");
        }
        for(int k=0; k<c; k++){
            sb.append(sumC[k]).append(" ");
        }
        sb.append(sumX).append("\n");
 
        System.out.print(sb);
    }
}

Measured memory_bytes: 27376
#include <bits/stdc++.h>
using namespace std;
int main(){
	string s1, s2;
	cin >> s1 >> s2;
	int ans = 2147483647;
	for(int i = 0; i <= s1.size() - s2.size(); i++){
		int cnt = 0;
		for(int j = 0; j < s2.size(); j++){
			if(s1[i + j] != s2[j]) cnt++;
		}
		ans = min(ans, cnt);
	}
	cout << ans << endl; 
	return 0;
}

Measured memory_bytes: 3596
N, A, B = gets.split.map(&:to_i)
hs = []
N.times do |i|
    hs[i] = gets.to_i
end

lb = 0
ub = 10**9

while ub - lb > 1 do
    mid = (ub + lb) / 2
    asum = 0
    hs.each do |h|
        hrest = h - mid * B
        asum += hrest > 0 ? (hrest + A - B - 1) / (A - B) : 0
        break if asum > mid
    end
    if asum <= mid
        ub = mid
    else
        lb = mid
    end
end

puts ub


Measured memory_bytes: 3144
a,b = map(int,input().split())
s = list(input())
if s[a] == "-":
    s.remove(s[a])

    ls = "0123456789"
    c = 0
    for i in s:
        if i in ls:
            c += 1

    if c == a+b:
        print("Yes")
    else:
        print("No")
else:
    print("No")

Measured memory_bytes: 3060
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();
		int swap;
		if (a > b) {swap = a; a = b; b = swap;}
		if (a > c) {swap = a; a = c; c = swap;}
		if (b > c) {swap = b; b = c; c = swap;}
		System.out.println(a + " " + b + " " + c);
	}
}

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

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

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 60;

int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll pow10[10] = {}; pow10[0] = 1; rep(i, 9) pow10[i+1] = pow10[i]*10;
    //abs(x2*y3 - x3*y2) = S
    //abs(y3 - x3*10^9) = S
    //x3*10^9 - y3 = S
    ll S; cin >> S;
    ll x1 = 0, y1 = 0, x2 = 1, y2 = pow10[9];
    ll x3, y3;
    y3 = -S % pow10[9];
    if(y3 < 0) y3 += pow10[9];
    x3 = (y3+S)/pow10[9];
    cout << x1 << " " << y1 << " " << x2 << " " << y2 << " " << x3 << " " << y3 << endl;
    return 0;
}

Measured memory_bytes: 256
def I(): return int(input())
N = I()
ans = 0
if N>=105:
    for i in range(105,N+1,2):
        count_yakusuu = 0
        for j in range(1,int(i**0.5)+1):
            if i%j==0:
                count_yakusuu += 2
        if count_yakusuu==8:
            ans += 1
print(ans)

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

int main()
{
  char date[12];
  cin>>date;
  int month=(date[5]-'0')*10+(date[6]-'0');
  if(month>4)
    cout<<"TBD";
  else
    cout<<"Heisei";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("03")
#pragma GCC optimize ("unroll-loops")
#define ll long long
#define ms(a,b) memset(a,b,sizeof(a))
#define endl '\n'
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define mpp(a,b,c) make_pair(a,make_pair(b,c))
#define fi first
#define se second
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define repp(a,b,c) for(int a=b;a>=c;a--)

int main(){
/////////////////////////////////////////////
//	ios_base::sync_with_stdio(0);
//	cin.tie(0); cout.tie(0);
/////////////////////////////////////////////
	ll a;
	cin >> a;
	rep(i,1,9){
		if(a%i==0){
			if((a/i)<10){
				cout << "Yes" << endl;
				return 0;
			}
		}
	}
	cout << "No" << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int proc(int *v, int n)
{
  int i=0;
  for(i=0; i<n; i++){
    if(v[i] % 2 == 0){
      v[i] /= 2;
      break;
    }
  }

  return i<n;
}

int main() {
    int n, cnt;
    int v[10000];

    cin >> n;
    for(int i=0; i<n; i++) cin >> v[i];

    cnt = 0;
    while(proc(v, n)) cnt++;
    cout << cnt;


    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <stdio.h>
#include <math.h>
#include <cmath>
using namespace std;
#define vsort(vec) sort(vec.begin(), vec.end())
#define vreverse(vec) reverse(vec.begin(), vec.end())
using ll =long long;
using ull =unsigned long long;
const ll INF =1001001001;

//10億7。　　　100000007

//最大公約数
ll gcd(ll a, ll b){
   if (a%b==0){
       return(b);
   }else{
       return(gcd(b,a%b));
   }
}
//最小公倍数
ll lcm(ll a, ll b){
   return a*b/gcd(a,b);
}


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

ll N;
  cin>>N;
  vector<ll> vec(N);
  ll sum=0;
  for(int i=0;i<N;i++){
    cin>>vec[i];
    sum+=vec[i];
  }
  
  ll Q;
  cin>>Q;
  vector<ll> vecB(Q);
  vector<ll> vecC(Q);
  for(int i=0;i<Q;i++){
    cin>>vecB[i]>>vecC[i];
  }

  vector<int> vecN(100000);
  for(int i=0;i<100000;i++){
    vecN[i]=0;
  }
  vsort(vec);
  for(int i=0;i<N;i++){
    vecN[vec[i]]++;
  }

  for(int i=0;i<Q;i++){
    
    sum=sum-vecN[vecB[i]]*vecB[i]+vecN[vecB[i]]*vecC[i];
    cout<<sum<<endl;
    vecN[vecC[i]]+=vecN[vecB[i]];
    vecN[vecB[i]]=0;
    
  }
    
    
  
}



Measured memory_bytes: 5808
#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
#ifdef __LOCAL
#define debug(x) cerr << __LINE__ << ": " << #x << " = " << (x) << '\n'
#define debugArray(x, n)                                      \
  cerr << __LINE__ << ": " << #x << " = {";                   \
  for (long long hoge = 0; (hoge) < (long long)(n); ++(hoge)) \
    cerr << ((hoge) ? "," : "") << x[hoge];                   \
  cerr << "}" << '\n'
#define debugMatrix(x, h, w)                                         \
  cerr << __LINE__ << ": " << #x << " =\n";                          \
  for (long long hoge = 0; (hoge) < (long long)(h); ++(hoge)) {      \
    cerr << ((hoge ? " {" : "{{"));                                  \
    for (long long fuga = 0; (fuga) < (long long)(w); ++(fuga))      \
      cerr << ((fuga ? ", " : "")) << x[hoge][fuga];                 \
    cerr << "}" << (hoge + 1 == (long long)(h) ? "}" : ",") << '\n'; \
  }
#else
#define debug(x) (void(0))
#define debugArray(x, n) (void(0))
#define debugMatrix(x, h, w) (void(0))
#endif

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  int N;
  cin >> N;
  int H[N], P[N];
  for (int i = 0; i < N; i++) cin >> H[i] >> P[i];
  int idx[N];
  iota(idx, idx + N, 0);
  sort(idx, idx + N, [&](int l, int r) { return H[l] + P[l] < H[r] + P[r]; });
  int dp[N + 1];
  fill(dp, dp + N + 1, INT_MAX);
  dp[0] = 0;
  for (int i : idx) {
    for (int j = N; j >= 0; j--) {
      if (dp[j] <= H[i]) {
        dp[j + 1] = min(dp[j + 1], dp[j] + P[i]);
      }
    }
    // debugArray(dp, N + 1);
  }
  int ans = 0;
  for (int i = 0; i <= N; i++)
    if (dp[i] < INT_MAX) ans = i;
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 3648
N, A, B = map(int, input().split(' '))
sum_digits = 0
for num in range(1, N + 1):
    sum_digit = 0
    tmp = num
    while True:
        if tmp < 10:
            sum_digit += tmp
            break
        digit = tmp % 10
        tmp //= 10
        sum_digit += digit

    if A <= sum_digit <= B:
        sum_digits += num

print(sum_digits)


Measured memory_bytes: 2940
#include <iostream>
#include <iomanip>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <climits>
#include <limits.h>
#include <string>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <assert.h>
#include <cstring>
#include <bitset>
#include <complex>
using namespace std;
#define rep(i, n) for (int (i) = 0; (i) < (n); (i) ++)
#define rep1(i, n) for (int (i) = 1; (i) <= (n); (i) ++)
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define db(x) {cout << #x << " = " << (x) << endl;}
#define dba(a, x, y) {cout<<#a<<" :";FOR(i123,x,y)cout<<setw(4)<<(a)[i123];cout<<endl;}
#define clr(x) memset(x,0,sizeof(x));
#define mp make_pair
#define pb push_back
#define sz(x) int((x).size())
#define endl '\n'
typedef long long ll;
typedef long double ld;
const int INF = INT_MAX;
const ll INFL = LLONG_MAX;
const ld pi = acos(-1);
// const int MOD = ;

ll gcd(ll a, ll b)
{
  while (b != 0)
  {
    ll tmp = a % b;
    a = b;
    b = tmp;
  }
  return a;
}
int main()
{
  ios_base::sync_with_stdio(0); cout.precision(15); cout << fixed; cout.tie(0); cin.tie(0);
  ll a, b;
  while (cin >> a >> b)
  {
    ll g = gcd(a, b);
    cout << g << " " << a * (b / g) << endl;
  }
}

Measured memory_bytes: 1192
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int n = str.length();
        
        int count = 0;
        int now = 0;
        for (int i = 0; i < n; i++) {
            char c = str.charAt(i);
            
            if (c == 'S') {
                now++;
            } else {
                now--;
            }
            
            if (now < 0) {
                count++;
                now = 0;
            }
        }
        
        if (now > 0) {
            count += now;
        }
        System.out.println(count);
    }
}


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

struct UnionFind{
    vector<int> parent;
    vector<int> size;
    vector<int> rank;

    /* constructor (initialize) */
    UnionFind(int n){
        parent.resize(n);
        size.resize(n);
        rank.resize(n);
        for(int i=0; i<n; i++){
            parent[i] = i;// completely-disjoint
            size[i] = 1;
            rank[i] = 0;// union by rank
        }
    }

    int root(int x){
        // terminal case
        if(parent[x] == x){
            return x;// by definition
        }

        // recursion
        parent[x] = root(parent[x]);// path compression : keep tree as shallow as possible
        return parent[x];
    }

    void merge(int x, int y){
        int rx = root(x);
        int ry = root(y);

        // if (root(x) == root(y)) do nothing;
        if (rx != ry){
            if(rank[rx] < rank[ry]){
                parent[rx] = ry;// root of merged tree = ry
                size[ry] += size[rx];
            }
            else if(rank[rx] == rank[ry]){
                parent[rx] = ry;
                size[ry] += size[rx];
                rank[ry] += 1;
            }
            else if(rank[rx] > rank[ry]){
                parent[ry] = rx;// root of merged tree = rx
                size[rx] += size[ry];
            }
        }
        return;
    }

    bool same(int x, int y){
        return root(x) == root(y);
    }

    int nodes(int x){
        return size[root(x)];
    }
};

int main(){
    long long int n, m, k;
    cin >> n >> m >> k;

    vector<int> a(m), b(m);
    for(int i=0; i<m; i++){
        cin >> a[i] >> b[i];
        a[i] -= 1;
        b[i] -= 1;
    }

    vector<int> c(k), d(k);
    for(int i=0; i<k; i++){
        cin >> c[i] >> d[i];
        c[i] -= 1;
        d[i] -= 1;
    }
    
    UnionFind uf(n);
    for(int i=0; i<m; i++){// for each edge
        if(uf.same(a[i],b[i]) == false){
            uf.merge(a[i], b[i]);
        }
    }
    
    vector<int> ans(n);
    for(int i=0; i<n; i++){
        ans[i] = uf.nodes(i) - 1;// exclude oneself
    }
    for(int i=0; i<m; i++){
        ans[a[i]] -= 1;
        ans[b[i]] -= 1;
    }
    for(int i=0; i<k; i++){
        if(uf.same(c[i], d[i])){
            ans[c[i]] -= 1;
            ans[d[i]] -= 1;
        }
    }
    for(int i=0; i<n; i++){
        cout << ans[i];
        if(i != n-1) cout << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 3968
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define sp(n) cout << fixed << setprecision(n)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
using namespace std;
ll gcd(ll x,ll y){
    if (y == 0) return x;
    return gcd(y, x%y);
}
ll lcm(ll x,ll y){
    return x*y/gcd(x,y);
}
int main(void){
    ll a,b,c,d;cin>>a>>b>>c>>d;a--;
    ll g=lcm(c,d);
    ll buf1=a/c,buf2=a/d,buf3=b/c,buf4=b/d,buf5=a/g,buf6=b/g;
    ll res=buf3+buf4-buf2-buf1+buf5-buf6;
    res=b-a-res;
    cout<<res<<endl;
}

Measured memory_bytes: 3616
x,y = gets.split(' ').map(&:to_i)

#足が奇数の時
if y%2 != 0
    puts 'No' 
#足が偶数の時
else
    #足の数を満たすのに必要な鶴の数
    t = y / 4
    y = y - t*4
    #足の数を満たすのに必要な亀の数
    c = y / 2
    min = t + c
    max = t*2 + c
    #鶴・亀・鶴亀が総数よりも多い場合
    if x <= max && min <= x
        puts 'Yes'
    else
        puts 'No'
    end
end


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

int main() {
  int n;
  cin >> n;
  vector<int> l(n);
  rep(i,n) cin >> l[i];
  int ans = 0;
  rep(i,n)rep(j,n)rep(k,n) {
    if (i < j && j < k) {
      if (l[i] == l[j]) continue;
      if (l[i] == l[k]) continue;
      if (l[k] == l[j]) continue;
      if ((ll)l[i]+l[j]+l[k] <= max({l[i],l[j],l[k]})*2) continue;
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3632
N = int(input())
A = [int(x) for x in input().split()]
#a, b, c = map(int, input().split())
#name1 = str(input())
#alph = {"A": 1, "B": 2, "C": 3, "D": 4, "E": 5}
for i in range(N):
    A[i] = A[i] - (i + 1)
A.sort()
b = A[int(N / 2)]
ans = 0
for i in range(N):
    ans += abs(A[i] - b)
print(ans)


Measured memory_bytes: 25196